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.
Prerequisite
CS 103 or 103B; CS 109 or STATS 116 (or equivalents)
Notes
- This course is offered as part of the Summer Intensive in Computer Science, and qualifies toward the Certificate of Completion in Computer Science.
- Stanford graduate students (with instructor approval) may choose to enroll in this course for 3-5 units. All other students must enroll in this course for 5 units.