Introduction

I showed up to this lecture half an hour late because I had a phone call, just in time for the "Points of Advice" slide telling us to avoid office hours unless we're totally stuck. 🙃 The day after, I looked at the slides I'd missed, and wow, I get why people were already complaining about this on Twitter.

Slide 33 crosses out "Attend lectures, attend recitations, spend several hours on each problem set" in favor of "[internalizing] the material," presumably by spending a bunch of your free time thinking about 6.006. They say similar things about how to work on an assignment and the rationale for the grading scheme.

Anyway, this course is about: efficient algorithms, which we'll analyze runtime for (as a function of input size, usually interested in worst case, disregarding constant factors) and prove correctness of. The modules include:

1. Data structures: searching and sorting, hashing, sets, heaps
2. Graph algorithms: searching in graphs, shortest paths
3. Algorithmic design: greedy algorithms, dynamic programming
4. Advanced topics: complexity

The grading policy is:

• 25% for 9 psets
• 60% for 3 quizzes
• 15% for final

We previewed some problems that correspond to modules:

1. Finding a 2D peak
2. Finding bridges
3. How to win the alternating coin game