CS 201 Computer Science I and CS 202 Computer Science II: Difference between pages

Revision as of 19:47, 17 May 2021

Catalog Description

This course is a continuation of CS 201. It involves a deeper study of programming languages, but emphasizes programming in a particular language. Topics include algorithm design and analysis, data structures, recursion, threads, network programming, graphics, security, and ethics. Prerequisites - C or better in CS 201.

Prerequisites

basic programming concepts
ability to use unix

Standard Content

Course Outline

Review (2 weeks)
- C Programming - all keywords and operations, libraries and header files
- Data formats and number systems (binary, decimal, octal, hex), signed/unsigned, two’s complement, floating point, long, int, short char, C strings
- I/O with different data formats and number systems
- Basic data structures - unsorted array, sorted array, linked list, heap, stack, queue - code for all in class and as assignments
- Search and sorting - linear and binary search, selection and insertion sort, mergesort, heapsort, quicksort - code for all in class and as assignments
Asymptotic analysis and running time (1 week) - big O/Omega/Theta, little o/omega, definitions, basic proofs, polynomials / exponentials / logarithms, recursion trees
Memory organization (1 week) - text, data, heap, stack, malloc, free, pointer arithmetic
Unix and debugging (1 week) - gdb, grep, sed, awk, find, compiler options, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection
Disk organization (1 week) - inodes, superblocks, etc.
New data structures (4 weeks) - binary search tree (including balanced), hash table, skip list, trie, B tree - code for some in class and as assignments
Graphs (1 week) - terminology, adjacency matrix, adjacency list, basic algorithms (BFS, DFS, shortest path, minimum spanning tree) - do all algorithms on the board, code for some in class, running time for all
Classes and objects in C++ (2 weeks) - data abstraction and encapsulation, defining classes, creating objects, inheritance, protection, virtual functions and polymorphism
The Standard Template Library (1 week)
Comparison of C++ and other OO Languages (Java, Python, etc.) (1 week)

Learning Outcomes

C programming and debugging,
data structures understanding (can explain lookup/insert/delete for each DS, work small examples on paper, know running times) and
coding (can finish partially complete DS code, write new functions to traverse DS)

Important Assignments and/or Exam Questions

Programming assessment - must pass with 3 and 2 halves to get a C or better
Data structures programming, exam/homework question - given prototype for insert/lookup/delete, can give correct code
Data structures programming, exam/homework question - given prototype for function that should use data structure functions, can give correct code
C programming play computer, exam question - given any short C program (a few dozen lines, say) and sample input, can trace execution and final output
Some large project that is interesting - game, etc.

Standard resources

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
The C Programming Language by Kernighan and Ritchie
Online courses/tutorials - MIT course - Practical Programming in C , How to Think Like a Computer Scientist, C++ Version - an online textbook, CS 50: Intro to CS I at Harvard - has videos, lecture notes, Reference on C and C++, The C Programming Language, C Programming Tutorial, Fresh2fresh C Tutorial

@@ Line 1: / Line 1: @@
 == Catalog Description ==
-This course begins with a history of programming languages, then focuses on programming in a particular language. The following topics are covered in some detail: variables, expressions and operators, control structures, simple data types, arrays, classes, and objects. Algorithm design and security issues are also discussed.  Prerequisite - C or better in CS 151.
+This course is a continuation of CS 201. It involves a deeper study of programming languages, but emphasizes programming in a particular language. Topics include algorithm design and analysis, data structures, recursion, threads, network programming, graphics, security, and ethics.  Prerequisites - C or better in CS 201.
 == Prerequisites ==
-* ''TODO''
+* basic programming concepts
+* ability to use unix
 == Standard Content ==
 ===Course Outline ===
-Data formats and number systems (binary, decimal, octal, hex), signed/unsigned, two’s complement, floating point, long, int, short char, C strings
+* Review (2 weeks)
-C Programming - all keywords and operations
+** C Programming - all keywords and operations, libraries and header files
-C compiler, command-line arguments
+** Data formats and number systems (binary, decimal, octal, hex), signed/unsigned, two’s complement, floating point, long, int, short char, C strings
-C library functions - formatted I/O, C strings,
+** I/O with different data formats and number systems
-I/O with different data formats and number systems
+** Basic data structures - unsorted array, sorted array, linked list, heap, stack, queue - code for all in class and as assignments
-Basic data structures - unsorted array, sorted array, linked list, heap, stack, queue, binary search tree.  Can do all on paper, do code for some in class and as assignments.
+** Search and sorting - linear and binary search, selection and insertion sort, mergesort, heapsort, quicksort - code for all in class and as assignments
+* Asymptotic analysis and running time (1 week) - big O/Omega/Theta, little o/omega, definitions, basic proofs, polynomials / exponentials / logarithms, recursion trees
+* Memory organization (1 week) - text, data, heap, stack, malloc, free, pointer arithmetic
+* Unix and debugging (1 week) - gdb, grep, sed, awk, find, compiler options, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection
+* Disk organization (1 week) - inodes, superblocks, etc.
+* New data structures (4 weeks) - binary search tree (including balanced), hash table, skip list, trie, B tree - code for some in class and as assignments
+* Graphs (1 week) - terminology, adjacency matrix, adjacency list, basic algorithms (BFS, DFS, shortest path, minimum spanning tree) - do all algorithms on the board, code for some in class, running time for all
+* Classes and objects in C++ (2 weeks) - data abstraction and encapsulation, defining classes, creating objects, inheritance, protection, virtual functions and polymorphism
+* The Standard Template Library (1 week)
+* Comparison of C++ and other OO Languages (Java, Python, etc.) (1 week)
+===Learning Outcomes===
+* C programming and debugging,
+* data structures understanding (can explain lookup/insert/delete for each DS, work small examples on paper, know running times) and
+* coding (can finish partially complete DS code, write new functions to traverse DS)
 ===Important Assignments and/or Exam Questions===
-* ''TODO''
+* Programming assessment - must pass with 3 and 2 halves to get a C or better
+* Data structures programming, exam/homework question - given prototype for insert/lookup/delete, can give correct code
+* Data structures programming, exam/homework question - given prototype for function that should use data structure functions, can give correct code
+* C programming play computer, exam question - given any short C program (a few dozen lines, say) and sample input, can trace execution and final output
+* Some large project that is interesting - game, etc.
 === Standard resources ===
-* ''TODO''
+* Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
+* The C Programming Language by Kernighan and Ritchie
-== Notes ==
+* Online courses/tutorials - MIT course - Practical Programming in C , How to Think Like a Computer Scientist, C++ Version - an online textbook, CS 50: Intro to CS I at Harvard - has videos, lecture notes, Reference on C and C++, The C Programming Language, C Programming Tutorial, Fresh2fresh C Tutorial
-Taking CS 201 and CS 202 Simultaneously
-If a student requests taking CS 201 and 202 simultaneously to stay on track to graduate on time, the following must be met.
-At least an A- in CS 151
-Number systems (binary, octal, decimal, hex)
-Firm understanding of programming fundamentals - variables / data types, arrays, control flow, loops, scope, string manipulation, pointers.
-Ability to write basic programs in C or python - anything that can be done with a few nested control structures (loops, if’s).
-Review all of tutorialspoint - data structures & algorithms
-Good understand of the following data structures - unsorted array, sorted array, linked list, stack, queue, hash table, binary search tree.  For each can do the following - explain the operations (insert, delete, lookup), run examples on the board, explain the running time of the basic operations
-Programming assessment - problems 1, 2, 5 correct, get problems 3 and 4 correct possibly with assistance
-Taking CS 201 and 303 Simultaneously
-To take CS 303 simultaneously, you must
-At least a B in CS 151
-Meet items b), e), f) from the above list