CS 202 Computer Science II

From Computer Science
Jump to: navigation, search

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