CS 4820 - Introduction to Algorithms

General Information

The undergraduate algorithms course, and the second theory course in the CS major. This course is required for all CS majors. Most students take it their sophomore or junior year spring. This course is very useful to have when applying for internships, since it will improve your interviewing skills and most interviewers will expect it as a sign of CS maturity.

Prerequisites

CS 2800 - Discrete Structures and CS 3110 - Data Structures and Functional Programming. These aren’t really strict requirements - the only thing you really need is some familiarity with graph algorithms. With Robert, he may remove you from the course if you have not taken both or if you have only taken one and earned less than an A-.

Topics Covered

• Greedy Algorithms
• Divide and Conquer
• Dynamic Programming
• Flow Networks
• NP-Completeness
• Turing Machines
• Approximation Algorithms
• Randomized Algorithms

Workload

Previously (with Professor Bobby Kleinberg) one problem set per week, each consisting of three problems. Despite only being three problems, these problems are fairly time consuming and require quite a bit of thought. While it is not recommended, many students spend all Thursday nights working on the problem sets before the Friday morning deadlines.

I’ve heard that the workload is somewhat lower with Professor Kozen, since the course enrollment has grown in comparison to the size of the course staff. With Kozen, the deadlines are now Thursday night at midnight, not Friday morning.

General Advice

Start thinking about the problems as early as possible. It helps to think about the problems when walking between classes or generally just being “idle.”

It’s tempting to ignore problem sets for a few days after release, since it’s likely you just pulled an all-nighter working on the last one. Don’t fall into this trap. Think about problem sets over the weekend, and go to office hours early in the week after putting significant thought into the problems and getting stuck.

Testimonials

It’s as fun as shit. You should take it.

–Eisenhower

^This is the funnest class ever (no joke). You walk around all day thinking about algo problems. Exams don’t require much prep or memorization because its just 3 algo problems that requires you to do something clever.

When Robert teaches, the course explores Turing Machines and undecidability a lot more than when Eva Tardos teaches. It’s generally agreed that Robert’s offering is more rigorous and difficult.

Past Offerings

Resources