CS161 covers in depth fundamental data structures and techniques for algorithm design and analysis. Specific topics to be covered include:

• Algorithm analysis: worst and average case
• Recurrences and asymptotic behavior
• Algorithms for sorting and selection
• Randomized techniques
• Search structures: heaps, balanced trees, hash tables
• Dynamic programming and greedy algorithms
• Amortized analysis
• Graph algorithms: breadth- and depth-first search, MSTs, shortest paths

The official prerequisites for this course are CS 103 and Stat 116. If you have not taken Stat 116 or its equivalent, you should expect to do some independent reading during the course on topics including probability, random variables, expectation, and basic combinatorics.

The required text is Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, MIT Press.

There are two optional readings on order at the bookstore, as well. Data Structures and Algorithms by Aho, Hopcroft, and Ullman is a classic text, somewhat smaller in scope than CLR but sometimes clearer. Algorithm Design by John Kleinberg and Eva Tardos is a excellent recent book which is highly recommended.

Copies of in-class handouts, such as homework assignments and problem set solutions, will be posted on the class web page.

The lecture schedule for this quarter can be found here

The requirements for the course will be approximately six weekly written assignments, an in-class midterm exam, and a final exam. Grading will be based primarily on the written assignments (30%), midterm (30%) and the final (40%), with class participation being factored in for borderline cases. There also may be a programming project, to be decided upon at a later date.

Each homework will be due at the end of lecture one week after it is distributed. Assignments can be submitted in class or slipped under Professor Plotkin's door (Gates 472). They can also be emailed (in pdf format) to the staff mailing list with the subject HOMEWORK SUBMISSION and file name "Full name.pdf" (e.g. John Smith.pdf). Lateness of assignments will be measured in terms of class periods. You will have two grace periods which you can use at any time during the term without penalty; you may only use one late period on any given assignment. Once these are exhausted, homework will not be accepted, unless prior arrangements have been made with the instructor. In no cases will homework be accepted after solution sets have been distributed. We will aslo disregard the score for the worst homework.

Graded homeworks will be distributed in class. Whatever is not picked up will be placed into a handout bin marked "cs161" in Gates 4B, near the elevators.

One of the aims of this class is to teach you to reason about algorithms, describe them, and formally prove claims about them. In writing up your assignments, be as clear, precise, and concise. Understandability will be an important factor in the grading of these assignments.

You are permitted and encouraged to work in groups of up to three students when discussing the homework assignments. If you do collaborate, however, you must still write up the solutions individually and clearly acknowledge anyone with whom you have discussed the problems. It will be considered an honor code violation to consult previous years' solutions in the event that homework problems have been previously assigned.

Class announcements, assignment clarifications, etc., will be posted to the web site. Please make sure to visit it frequently !

Questions about assignments should be directed to cs161-aut0910-staff@lists.stanford.edu.  E-mail sent to this address will reach the entire course staff and will likely be answered more promptly.

Class handouts, including homeworks, but NOT including solution sets, will be made available electronically at the class web site.