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. Introduction to network flows and graph matchings.Prerequisites:
Before taking CS 161, it is important that you complete
CS 103 and CS 109/STATS 116, or the equivalents.
In particular, you should be comfortable with proofs, discrete mathematics, basic graph and set theory, and introductory probability theory.
There will be two exams for the course: one midterm and one final.
The midterm will be on Tuesday, May 3th, in class: 3-4:20pm.. The final exam will be on Saturday, June 4, 7-10pm, as specified by the registrar.
Midterm Location: NVidia Auditorium, Hewlett 200 (please see this post on Piazza. If you do not have a Piazza account, you can see the announcements here. )
Final Location: TBA
There will NOT be an alternate final exam, so plan accordingly.
Before working on the homework, please read the homework policy.