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.

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 htiek@cs.stanford.edu with questions.

See you soon!

## Office Hours

Keith (Gates 178):

• Tuesday, 2:15PM - 4:15PM
• Thursday, 2:15PM - 4:15PM

Andy (Clark S250):

• Monday / Wednesday, 4PM - 6PM

Sean (Remote OH):

• Sunday, 1PM - 5PM

Kostas (Gates 460):

• Monday / Wednesday, 6PM - 8PM

Phil (Gates B26A):

• Tuesday / Thursday, 10AM - Noon

Julie (Gates B24A):

• Tuesday / Thursday, 6PM - 8PM

## Lectures

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
Slides