Instructor: Karey Shi (kareyshi at stanford.edu)
Time: Mondays and Wednesdays, 7pm-8:20pm (PDT)
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 recommended. While all concepts that are fair game for quizzes 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!
Staff Contact: The best way to reach the staff is by making a private post on Ed Discussion.
The elements of your grade are:
- Homework (60%)
- 5 Concept Checks (15%)
- 5 Problem Sets (45%)
- 5 Quizzes (40%)
Some notes: Your lowest Concept Check will be dropped. Your lowest Problem Set score will be down-weighted: it will only be weighted half as much as the other 4. That is, your lowest score will account for 5% of your total grade, while your other 4 scores will each account for 10% of your total grade. Your lowest Quiz score will also be dropped.
Your score on each homework component and quiz will be computed as (points scored)/(points possible), and these scores will be aggregated together using 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. We may curve your final numerical grades to produce letter grades (we will never curve down, e.g. a 90% will always map to at least an A-). You can expect the distribution to be similar (not necessarily identical) to the historical grade distribution for CS 161.
Bonus Points: Throughout the quarter, there will be optional opportunities to get "bonus points":
- Completing bonus problem parts that may be offered on some problem sets.
- Being a top contributor on Ed Discussion.
These points will not officially impact your numeric grade, and all letter-grade cut-offs will be established without factoring in any student's bonus points (so these bonus points are truly optional). However, at the end of the quarter, if your numerical grade puts you near to a letter-grade cut-off, then if you have lots of bonus points (compared to your classmates) you may be "bumped" above the cut-off. (You cannot be bumped down.) For example, if your numerical grade is 0.814 and the cut-off for an A- is 0.820, then bonus points could promote you from a B+ to an A-.
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 quizzes.
- Using any animate resources during the quizzes.
If we have reason to believe that you are in violation of the honor code, we will follow the university policy to report it.
OAE Accommodations: Students who may need academic accommodations based on the impact of a disability must initiate the request with the Office of Accessible Education (OAE) and notify us as soon as possible to coordinate necessary accommodations. While we wait for mailing list technical issues to smooth over, please email OAE forms to email@example.com AND firstname.lastname@example.org (Allison is our CA who will be in charge of coordinating OAE accommodations).