Final Project Solutions Released
August 19, 2013

We've just released our solutions set for the final project, which also includes statistics and common mistakes. The projects are available for pickup in the Gates building, and electronic submissions should be returned soon. Problem Set Six will also be returned soon.

Thanks for a wonderful quarter, and enjoy the rest of the summer!

Final Project Out
August 12, 2013

The final project goes out today. It's due this Saturday, August 17 at 12:15PM. No late submissions will be accepted! Also remember that unlike on the problem sets, you must work on the project entirely on your own. Good luck!

Correction to "Guide to DP"
August 6, 2013

The algorithm we gave for solving the Longest Increasing Subsequence problem on the "Guide to Dynamic Programming" handout had an error in it (sorry about that!) We've posted a corrected version online.

Problem Set Six Out
August 5, 2013

Problem Set Six goes out today. It's due next Monday, August 12 at 2:15PM. This final problem set of the quarter explores dynamic programming in a variety of contexts.

We've also released a guide to dynamic programming outlining how to structure correctness proofs for DP algorithms.

EDIT: Ooops! There was a small typo in the counterexample to why the greedy algorithm for change making doesn't work. It's now fixed in the online version.

Problem Set Five Out
July 29, 2013

Problem Set Five goes out today. It's due next Monday, August 5 at 2:15PM. This problem set explores greedy algorithms and the proof techniques associated with them. Some problems are standard greedy algorithms, while others show how greedy algorithms can find approximately good solutions to hard problems.

We've also released a guide to greedy algorithms that should give you some extra assistance writing proofs. As you'll see, proving greedy algorithms work correctly can be challenging, and we hope that this handout helps out!

Problem Set Four Out
July 22, 2013

Problem Set Four went out today. It's due next Monday, July 29 at 2:15PM. This problem set is about randomness: expected values, probabilities, and universal hashing all make an appearance here, and by the time you've completed the problem set we hope you'll have a much deeper understanding of just how powerful a tool randomness can be.

We've also released a guide to randomized algorithms that should give you a sense for the level of detail we're looking for in your answers.

Problem Set Three Out
July 12, 2013

Problem Set Three went out today. It's due next Monday, July 22 at 2:15PM. This problem set explores divide-and-conquer algorithms and recurrence relations, and we hope that it will cement your understanding of this algorithmic technique!

Math Handout Posted
July 10, 2013

We have just posted a handout containing useful mathematical terms and identities. We hope that this handout helps you navigate some of the mathematically trickier parts of the course!

Problem Set Two Out
July 3, 2013

Problem Set Two went out today. It's due next Friday, July 12 at 2:15PM. In this problem set, you'll get to play around with graphs and graph algorithms and will gain experience applying the techniques from the course across a variety of domains.

Correction on Definition of Ω
June 26, 2013

There was a small bug in Monday's lecture's definition of Ω notation. The constant c must be positive, since otherwise f(n) = Ω(g(n)) for any f and g by just setting c = 0. The slides have been updated to correct for this.

Sorry about that!

Problem Set One Out
June 26, 2013

Problem Set One went out today. It's due next Wednesday, July 3 at 2:15PM. This problem set explores O, Ω, and Θ notations, algorithm design and correctness, and basic graph algorithms. By the time you're done, we hope that you'll have a much better understanding of how to design and analyze algorithms!

We've also put together a handout containing advice and policies for problem sets. We recommend reading over it before starting the problem set.

Hope this helps!

Welcome to CS161!
June 21, 2013

Welcome to CS161! We've got an exciting quarter ahead of us filled with beautiful algorithms and problem-solving strategies. Over the upcoming weeks, we'll explore a variety of ways to model and solve problems that arise in computer science, biology, operations research, networking, and much more.

In the meantime, feel free to check out the course information handout and syllabus to learn more about what this class is all about, the prerequisites, and the course policies. If you have any questions in the meantime, feel free to email me at with questions.

See you soon!


00: Course Information
01: Syllabus
02: Problem Set Advice
05: Math Terms and Identities
07: Guide to Reductions
08: Guide to Divide-and-Conquer
10: Guide to Randomized Algorithms
12: Guide to Greedy Algorithms
14: Guide to Dynamic Programming
15: Final Project


Problem Set One
Problem Set Two
Problem Set Three
Problem Set Four
Problem Set Five
Problem Set Six
Final Project

Programming Section

Week 1: Introduction
  (data | code)
Week 2: Graph Search
   (data | code)
Week 3: Divide and Conquer
   (data | code)
Week 4: Randomized Algorithms
   (data | code)
Week 5: Greedy Algorithms
   (data | code)
Week 6: Minimum Spanning Trees
   (data | code)
Week 7: Dynamic Programming
   (data | code)
Week 8: Contest Programming
   (data | code)

Office Hours

Keith (Gates 178):

Andy (Clark S250):

Sean (Remote OH):

Kostas (Gates 460):

Phil (Gates B26A):

Julie (Gates B24A):


Lecture Videos


00: Algorithmic Analysis
  Slides (Condensed)
01: Fundamental Graph Algorithms I
  Slides (Condensed)
02: Fundamental Graph Algorithms II
  Slides (Condensed)
03: Fundamental Graph Algorithms III
  Slides (Condensed)
04: Fundamental Graph Algorithms IV
  Slides (Condensed)
05: Divide-and-Conquer Algorithms I
  Slides (Condensed)
06: Divide-and-Conquer Algorithms II
  Slides (Condensed)
07: Divide-and-Conquer Algorithms III
  Slides (Condensed)
08: Divide-and-Conquer Algorithms IV
  Slides (Condensed)
09: Randomized Algorithms I
  Slides (Condensed)
10: Randomized Algorithms II
  Slides (Condensed)
11: Randomized Algorithms III
  Slides (Condensed)
12: Randomized Algorithms IV
  Slides (Condensed)
13: Greedy Algorithms I
  Slides (Condensed)
14: Greedy Algorithms II
  Slides (Condensed)
15: Greedy Algorithms III
  Slides (Condensed)
16: Dynamic Programming I
  Slides (Condensed)
17: Dynamic Programming II
  Slides (Condensed)
18: Dynamic Programming III
  Slides (Condensed)
19: Intractable Problems I
  Slides (Condensed)
20: Intractable Problems II
  Slides (Condensed)
21: Intractable Problems III
  Slides (Condensed)
22: Where to Go from Here