Instructor: Mary Wootters
When and where? M/W 10:30 - 11:50am, NVIDIA Auditorium.
Course Description: This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching.
Prerequisites: CS 103 or CS 103B; CS 109 or STATS 116.
What do I need to do? Eight homework assignments, a midterm, and a final. See the Course Policies for more details.
Announcements: Please check Piazza for course announcements.
| Monday | Wednesday |
|---|---|
| 1/6. Lecture 1: Why are you here? | 1/8. Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort (AI Part 1, Ch. 1 and 2).
Homework 1 Assigned |
| 1/13. Lecture 3: Solving Recurrences and the Master Theorem (AI Part 1, Ch. 4) | 1/15. Lecture 4: Median and Selection (AI Part 1, Ch. 6.1, 6.3, 6.4)
Homework 1 Due; Homework 2 Assigned |
| 1/20. MLK Day. No class. | 1/22. Lecture 5: Randomized Algorithms and QuickSort (AI Part 1, Ch. 5.1--5.5)
Homework 2 Due; Homework 3 Assigned Note: HW3 will be shorter since we didn't cover as much material this week. |
| 1/27. Lecture 6: BucketSort and Lower Bounds for Sorting (AI Part 1, Ch. 5.6; CLRS 8.2 and 8.3) | 1/29. Lecture 7: Binary Search Trees and Red-Black Trees (AI Part 2, Ch. 11.)
Homework 3 Due; Homework 4 Assigned. |
| 2/3. Lecture 8: Hashing (AI Part 2, Ch. 12.1-12.4) | 2/5. Lecture 9: Graphs and BFS and DFS (AI Part 2, Ch 8.1-8.5)
Homework 4 Due; study for the midterm next week! |
| 2/10. Lecture 10: Strongly Connected Components (AI Part 2, Ch. 8.6) | 2/12. Lecture 11: Dijkstra and Bellman-Ford (AI Part 2, Ch. 9)
Homework 5 Assigned. |
| 2/17. President's Day. No class. | 2/19. Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall (AI Part 3, Ch. 16,18)
Homework 5 Due; Homework 6 Assigned. |
| 2/24. Lecture 13: More dynamic programming: LCS, Knapsack, Independent Set (AI Part 3, Ch. 17) | 2/26. Lecture 14: Greedy Algorithms (AI Part 3, Ch. 13,14)
Homework 6 due; Homework 7 Assigned |
| 3/2. Lecture 15: Minimum Spanning Trees (AI Part 3, Ch. 15) | 3/4. Lecture 16: Min Cuts and Karger's algorithm (Kleinberg and Tardos Ch. 13.2)
Homework 7 Due; Homework 8 Assigned. Note: HW8 will be on the short end! Almost there! |
| 3/9. Lecture 17: Max-Flow and the Ford-Fulkerson Algorithm. (CLRS Ch. 26.1, 26.2, 26.3) | 3/11. Lecture 18: What's next? (No reading).
Homework 8 Due; Study for the final! |
| 3/16. Final Exam, 3:30-6:30pm. |