CS 161: Course Info

Semih Salihoglu, Stanford University, Summer Quarter 2014

Catalog Description

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

You 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., O{left(f(n)right)}, Omega{left(f(n)right)}, and Theta{left(f(n)right)} )

  • The relative speed of growth of functions like f(n) = n, f(n) = nlog{n}, and f(n) = n^2 as n to infty

  • Mergesort, together with an argument that its worst-case running time is O(nlog{n})

  • Recurrence relations

  • Breadth- and depth-first search

Lectures

Lectures 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

A few copies of KT and CLRS are on reserve at the Stanford Libraries. We will post excerpts from DPV as handouts.

Late Policy

This 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 Policy

One 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, you must write up your own solutions to all of the problems, and you must cite all people you worked with on the problem set. If you do not do so, you may be guilty of plagiarism. Additionally, if you consult any resources other than the course textbook, lecture slides, or lecture notes, you must cite your sources. We reserve the right to assign a penalty if your answers are substantially derived from other sources, but as long as you provide citation you will not be committing plagiarism.

In any event, you are responsible for understanding and being able to explain all of the statements in your homeworks and exam solutions. Most importantly, the solutions must be written up independently of the other students.

Grading Considerations

You grade on assignments and the exam will usually depend on two things:

  1. correctness

  2. 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

Homework

There will be six homework assignments assigned during the quarter. You will have about a week to do each of them.

Project

There 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.

Final

There 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 Breakdown

  • Homework: 45%

  • Project: 20%

  • Final: 35%

Scoryst

We 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 8FELFqp0RF.