Welcome to CS500!
This course will cover the basics of how to design and analyze data structures and algorithms. This course aims to:
- Develop your ability to think algorithmically. (What does this even mean? The answer will emerge gradually during the course.)
- Ensure that you understand some well-established techniques, algorithms, and methods of analysis.
- Give you some technical tools to predict for a given computational problem what kind of performance is possible.
- Hone your ability to reason rigorously about computational problems and algorithms and quantities such as running time.
Tweets
- Undergraduate at Rutgers disproves a 40-year-old conjecture about the limits of hashing (see here)
- Claire Mathieu, the scientist interviewed in this video, might be teaching Brown CS’s next-level algorithms course, CS 1570, in a year or two.
- As mentioned in class, a faster algorithm has been discovered for the problem addressed by Bellman-Ford, the problem of finding single-origin shortest paths in a graph with cycles when the lengths are allowed to be negative. The first algorithm was published in 2022. Here is a more recent and more complete article about the algorithm; the article appeared in 2025. In follow-up research, some other computer scientists, who referred to the first algorithm as a “breakthrough result”, came up with a somewhat faster algorithm using the same approach and published a paper in 2023. Here is a version of that paper. I mention these as further evidence that research in algorithms continues to uncover new and exciting results.
Course Info
Lectures
Assignments
Labs
| Lab | Out | Due | Handout |
|---|---|---|---|
| Sorting | 1/27 | 1/30 | |
| BigPrime | 2/6 | 2/9 | |
| BigPrime2 | 2/10 | 2/13 | |
| Hashing | 2/24 | 2/27 | |
| Heaps | 3/1 | 3/9 | |
| BST | 3/3 | 3/6 | |
| Treaps | 3/10 | 3/13 | |
| Bipartite Matching | 3/17 | 3/19 | |
| Single Origin Shortest Path | 4/7 | 4/9 | |
| Traveling Salesperson Problem | 4/14 | 4/16 |
Calendar
Staff
Hello! I was born in Berkeley, California. I’ve been a professor at Brown since the (very late) 80's. My research area is algorithms. In my free time, I like to rock climb, in the gym and outdoors.
Philip Klein | Professor | pklein
Hi! I’m Akash, a senior studying CS. Outside of class, you’ll probably find me restoring vintage fountain pens, binge-watching procedurals, or climbing rocks.
Akash Singirikonda | HTA | asingir1
Hello! I'm a senior from Portland, Maine studying CS and Education. I'm an avid chess player and love to cook and discover new music!
Oscar McNally | HTA | omcnally
Hi! I am a senior from Carlisle, MA, studying computational biology. I enjoy running, going to coffee shops, and watching Boston sports!
Hannah Beakley | UTA | hbeakley
Hello! I’m a junior from Barrington, Illinois studying CS and Biology. I play violin in the orchestra and enjoy eating and sleeping in my free time.
Ethan Park | UTA | epark73
Hi! I'm a junior from Milwaukee, WI studying CS and history. Talk to me about reading, Brown Taekwondo, and Ratty desserts.
Jake Schmidman | UTA | jschmidm
Kevin is from San Diego, and he has IBS <3
Kevin Luo | UTA | khluo