Computer Science 302
Introduction to Data Structures
Fall 2008

Syllabus

• Mathematical Review.
  • Logarithms (1.2).
  • Efficiency measures (Big-O, etc.). Basics of non-recursive running time analysis (2.1-2.4).
  • Recurrence relations (1.3).
  • Run time of recursive algorithms, master theorem (10.2.1)
• C++ Review (1.5-1.7)
• A simple example which represents the course: the maximum subsequence sum problem (2.4.1-2.4.3).
• Searching and Sorting
  • Linear search.
  • Binary search.
  • Bubblesort.
  • Insertion sort (7.2).
  • Shellsort (7.4).
  • Selection sort.
  • Mergesort (7.6).
  • Quicksort (7.7).
  • Bucket sort (7.10).
• Elementary Data Structures.
  • Abstract Data Types (3.1).
  • Lists (3.2).
  • Stacks (3.6).
  • Queues (3.7).
  • Arrays.
• Binary trees.
  • Preorder, postorder, and inorder traversal (4.1, 4.2, 4.6)
  • Binary search trees (4.2, 4.3).
  • Balanced search trees (4.4, 4.7).
• Hashing. (5.1-5.5).
• Heaps (6.1-6.4).
• More sophisticated sorting algorithms.
  • Heapsort (7.5).
  • Divide and conquer strategy, and mergesort revisited (7.6, 10.2).
  • Quicksort (7.7).
  • Binary tree sort (my personal favorite).
  • Polyphase mergesort (7.11.5).
  • Lower bounds (7.9).
• Disjoint set algorithm, union-find (8.1-8.5)
• Graph algorithms
  • Representing graphs (9.1).
  • Topological sort (9.2).
  • Graph traversal, depth-first and breadth-first search (9.3).
  • Shortest paths (9.3).
  • Kruskal's algorithm (9.5).
• Algorithm paradigms (10)
  • Greedy algorithms (10.1).
  • Divide and conquer (10.2).
  • Dynamic programming (10.3).
  • Randomized algorithms (10.4).
  • Backtracking algorithms (10.5).