Instructor: Karey Shi (kareyshi at stanford.edu)
Time: Mondays and Wednesdays, 1:30pm-3:20pm (PST)
Location: Zoom. See Canvas for all Zoom lecture information (e.g. meeting links and authentication details).
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.
Textbooks: Tim Roughgarden, Algorithms Illuminated, Volumes I, II, and III. Soundlikeyourself publishing. Even though these are three books, they are small, paperback, and relatively cheap! These texts are optional but highly recommended. While all concepts that are fair game for exams will be covered in lecture and practiced through homework and section problems, these books provide details that may be skipped during lecture, and contain helpful supplementary material.
Alternative Textbook: CLRS. This textbook has much more detail, and is actually available online for free through the Stanford Library!
The elements of your grade are:
- 6 homework assignments (60%)
- Midterm Exam (20%)
- Final Exam (20%)
Your score on each assignment and exam will be computed as (points scored)/(points possible), and these scores will be added together with the above weights to obtain your final numerical grade. The numerical grade will be converted to a letter grade at the end of the course. The final letter grade distribution will depend on the class's performance, but you can expect the distribution to be similar (not necessarily identical) to the historical grade distribution for CS 161.
Students must adhere to the Stanford Honor Code. The following things are examples of what will be considered a violation of the honor code in this course:
- Violation of the homework collaboration policy.
- Using old solution sets for CS161, unless specifically approved by the instructor. (These should not be available; if you learn of any floating around, please alert the course staff).
- Collaborating with others during the exams.
- Using any resources other than your cheat sheet(s) during the exams.
If we have reason to believe that you are in violation of the honor code, we will follow the university policy to report it.