The following documents outline the notes and lecture slides for the course CS 161 Design and Analysis of Algorithms.

Notes by Lecture Schedule

• 1: Introduction. Review.
  • Algorithm Analysis
• 2: Data Structures.
• Priority Queues
• Heaps
• Hash Tables
• Data Structures review; intro. to sorting
• 3: Sorting and Selection.
• Skip Lists
• MergeSort
• QuickSort
• Sorting lower bound
• RadixSort
• Selection
• 4: The greedy method.
• The Greedy Method
• 5: Divide-and-conquer.
• Divide-and-Conquer, part 1
• Odd-even mergesort
• Divide-and-Conquer, part 2
• The closest pair problem
• 6: Dynamic programming.
• Dynamic Programming
• Telescope Scheduling
• Game Strategies
• Longest Common Subsequence
• 0/1 Knapsack
• 7: No lectures (exam and holiday).
• 8: Graph algorithms.
• Graphs
• Depth-first search
• Breadth-first search
• Directed Graphs
• Shortest Paths
• 9: Minimum Spanning Trees.
• Minimum Spanning Trees
• Union-Find Data Structures
• 10: Network flow.
• Network Flow