Instructor: Mary Wootters
When and where? M/W 1:30 - 2:50pm, Bishop 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; CS106B/X.
What do I need to do? Seven homework assignments and two exams (plus, you know, learning the material). See the Course Policies for details on grading.
Do I have to come to class? Lectures will be recorded and videos will be available on Canvas. If you learn better by watching the lecture videos at your own speed and on your own schedule, that's fine.
Announcements: Please check Ed for course announcements.
| Monday | Wednesday | Assignments |
|---|---|---|
| 4/3. Lecture 1: Why are you here? | 4/5. Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort (AI Part 1, Ch. 1 and 2). | FRIDAY 4/7: Homework 0 Due; Wed. 4/5: Homework 1 Released |
| 4/10. Lecture 3: Solving Recurrences and the Master Theorem (AI Part 1, Ch. 4) | 4/12. Lecture 4: Median and Selection (AI Part 1, Ch. 6.1, 6.3, 6.4) | 4/12. Homework 1 Due; Homework 2 Released |
| 4/17. Lecture 5: Randomized Algorithms and QuickSort (AI Part 1, Ch. 5.1--5.5) | 4/19. Lecture 6: BucketSort and Lower Bounds for Sorting (AI Part 1, Ch. 5.6; CLRS 8.2 and 8.3) | 4/19. Homework 2 Due; Homework 3 Released |
| 4/24. Lecture 7: Binary Search Trees and Red-Black Trees (AI Part 2, Ch. 11.) | 4/26. Lecture 8: Hashing (AI Part 2, Ch. 12.1-12.4) | 4/26. Homework 3 Due; Study for Exam I! |
| 5/1. Lecture 8.5: Embedded EthiCS lecture, and review for midterm | 5/3. Lecture 9: Graphs and BFS and DFS (AI Part 2, Ch 8.1-8.5) | THURSDAY 5/4, 6-9pm. Exam I! (HW4 released Wednesday 5/3). |
| 5/8. Lecture 10: Strongly Connected Components (AI Part 2, Ch. 8.6) | 5/10. Lecture 11: Dijkstra and Bellman-Ford (AI Part 2, Ch. 9) | 5/10. HW5 Released. FRIDAY 5/12 Homework 4 Due. |
| 5/15. Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall (AI Part 3, Ch. 16,18) | 5/17. Lecture 13: More dynamic programming: LCS, Knapsack, Independent Set (AI Part 3, Ch. 17) | 5/17. Homework 5 Due; Homework 6 Released. |
| 5/22. Lecture 14: Greedy Algorithms (AI Part 3, Ch. 13,14) | 5/24. Lecture 15: Minimum Spanning Trees (AI Part 3, Ch. 15) | 5/24. Homework 6 due; Homework 7 Released |
| 5/29. Memorial Day (no class) | 5/31. Lecture 16: Max-Flow and the Ford-Fulkerson Algorithm. (CLRS Ch. 26.1, 26.2, 26.3) | 5/31. Homework 7 Due. All done with homework! |
| 6/5. Lecture 16.5: Embedded EthiCS II and Review. | 6/7. Lecture 17: What's next? (No reading). | Study for the final! |
| 6/12. Exam II (Final Exam), 3:30-6:30pm. |
Comments? Concerns? If you have non-anonymous feedback or a question, please ask on Ed. If you'd like to leave anonymous feedback, you can do so here.
Notes: