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

(solutions)

Problem Set Two

(solutions)

Problem Set Three

(solutions)

Problem Set Four

(solutions)

Problem Set Five

(solutions)

Problem Set Six

(solutions)

Final Project

(solutions)

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)

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

**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