CompSci 161 - Design and Analysis of Algorithms - Winter, 2025 (Dillencourt)

Preliminary list of topics

This is a preliminary, prospective list of topics, posted at the start of the quarter. Its primary purpose is to give you an idea of what topics we intend to cover. It is unlikely that we will follow this schedule exactly.

For an more accurate list of topics that have been covered and which slides have been covered in each lecture, click here.

• Week 1: Introduction; review of prerequisite material. Asymptotic notation. Harmonic numbers. Proofs, proofs by induction. Basic probability. Binary trees. Binary search: correctness, analysis, proof of optimality.
• Week 2: Comparison-based sorting. Insertion sort. Selection sort. Quicksort. Merge sort.
• Week 3: Priority queues, binary heaps. Heap sort. Lower bounds on comparison-based sorting. Optimal sorting of small sets. Address calculation sorting: Bucket sort, radix sort, counting sort. Disk-based sorting: polyphase merge.
• Week 4: Greedy algorithms. Fractional knapsack problem. Scheduling problems. Huffman coding. Midterm 1.
• Week 5: Divide and conquer. The Master Method. Some examples. Strassen's method for matrix multiplication. Introduction to dynamic programming.
• Week 6: Dynamic programming examples. Subset sum. 0/1 Knapsack. Optimal matrix chain multiplication. Optimal binary search trees.
• Week 7: Graph basics. Depth-first search. Breadth-first search. Strong connectivity. Topological sorting.
• Week 8: Biconnected component analysis. Weighted graphs. Dijkstra's algorithm. Midterm 2.
• Week 9: Minimum spanning trees. Selection.
• Week 10: Review. Additional topics as time permits.