## CS 161: Course InfoSemih Salihoglu, Stanford University, Summer Quarter 2014
## Catalog DescriptionWorst 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. ## PrerequisitesYou should have taken the following classes (or equivalent alternatives): CS 103 CS 106B CS 109 or STATS 116
It is particularly important that you've seen the following concepts: The definition of asymptotic notation (i.e., , , and ) The relative speed of growth of functions like , , and as Mergesort, together with an argument that its worst-case running time is Recurrence relations Breadth- and depth-first search
## LecturesLectures are Mondays and Wednesdays, 9:00-10:50am, in Gates B1. The lectures will be available (to registered students) a few hours after each live lecture, but you are encouraged to attend the live lectures if possible. ## Textbooks**Required**: Kleinberg and Tardos.*Algorithm Design*Optional: Cormen, Leiserson, Rivest, and Stein. *Introduction to Algorithms*Optional: Dasgupta, Papadimitriou, and Vazirani. *Algorithms*
A few copies of KT and CLRS are on reserve at the Stanford Libraries. We will post excerpts from DPV as handouts. ## Late PolicyThis course has no “late days”. Extensions will be granted only in the case of severe medical emergency. You can upload your problem sets multiple times on Scoryst until the deadline (Fridays at noon). Scoryst will disable uploading afterwards. So upload however much you have done before the deadline. ## Honor Code and Collaboration PolicyOne of our goals in CS161 is to teach you the art of algorithm design. Many algorithms are “nondeterministically trivial”: they are very easy to understand, but difficult to come up with. Consequently, when doing the homework assignments, it is extremely important that you do as much of the work as possible on your own without consulting anyone else or any other outside resources. We hope that the problem sets will give you an opportunity to learn how to devise your own algorithms. That said, I understand that you may want to work on the problem sets in groups.
If you'd like to do this, that's totally fine. However, if you do, In any event, you are responsible for understanding and being able
to explain all of the statements in your homeworks and exam solutions. ## Grading ConsiderationsYou grade on assignments and the exam will usually depend on two things: correctness clarity
The correctness aspect of your grade pertains to how correct your solution is. If you turn in a working algorithm with a valid correctness proof and runtime analysis, you'll get full points here. If your algorithm is buggy, or your correctness proof is flawed, or your runtime analysis is incorrect, you will lose some of these points. Your clarity score reflects how clean your submission is. If you have a simple algorithm that runs correctly and write a short but elegant proof of correctness and runtime bounds, you'll get full credit for this part. If your algorithm has unnecessary special cases or could be easily be simplified, we may deduct points here. Additionally, we will deduct points for proofs that are unclear or are far more complicated than necessary. We encourage you to be critical of your answers. This is a useful skill to have when designing and analyzing algorithms and more generally when writing mathematical proofs. If at any point you're curious whether one of your answers is sufficiently clean, you can always stop by office hours or email the staff list to have one of us look over it. ## Course Assignments## HomeworkThere will be six homework assignments assigned during the quarter. You will have about a week to do each of them. ## ProjectThere will be a project assigned at the end of week 5 that will be due at the end of week 7. You will be able to work on it individually or in teams of two. See the Project page for more details. ## FinalThere will be a three-hour final on Saturday, August 16th, from 3:30 - 6:30 pm. A room and more details will be announced towards the end of the course. ## Final Grade BreakdownHomework: 45% Project: 20% Final: 35%
## ScorystWe will be using Scoryst for homework and project submissions.
We will auto-enroll all students in the course, but should you wish to do this
yourself, you may do so by using the class token |