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.
- Grading Basis: Letter Grade or Credit/No Credit
- Unit-Range Information: Matriculated Stanford graduate students may enroll for 3, 4, or 5 units; everyone else must take the course for 5 units. All students do 5 units worth of work, including Stanford graduate students enrolled for 3 or 4 units.
- Intensive Studies: This course is offered as part of the Computer Science Intensive and must be taken for 5 units. See the Intensive Studies page for more information on how to receive an official Document of Completion.
CS 103; CS 109, STATS 116, or equivalents