Description: This lecture introduces the topics covered in the course and its motivation. Examples of applications are provided, along with types and charaterizations of geometric objects, foldability and design questions, and results. Select open problems are also ...

This lecture covers some history of digital communication, with a focus on Samuel Morse and Claude Shannon, measuring information and defining information, the significance of entropy on encodings, and Huffman's coding algorithm.

Description: This lecture starts with how to define useful subproblems for strings or sequences, and then looks at parenthesization, edit distance, and the knapsack problem. The lecture ends with a brief discussion of pseudopolynomial time. Instructor: Erik Demaine

Description: This lecture covers open addressing, which is another approach to dealing with collisions (hashing with chaining was covered in Lecture 8). Cryptographic hashing is also introduced. Instructor: Srini Devadas

Description: This lecture covers depth-first search, including edge classification, and how DFS is used for cycle detection and topological sort. Instructor: Erik Demaine

Description: This lecture introduces weighted graphs and considers general approaches to the shortest paths problem. The lecture discusses single source shortest paths, negative-weight edges, and optimal substructure. Instructor: Srini Devadas

Description: This lecture introduces dynamic programming, in which careful exhaustive search can be used to design polynomial-time algorithms. The Fibonacci and shortest paths problems are used to introduce guessing, memoization, and reusing solutions to subproblems. ...

Description: This recitation covers several practice problems for Quiz 1, taken from previous semesters of 6.006. Instructor: Victor Costan

Description: This recitation revisits the perfect-information blackjack problem that was covered in lecture. Instructor: Victor Costan

Description: This recitation covers the wood-cutting problem (dynamic programming) and Bloom filters (hashing, probability). Instructor: Victor Costan

Description: This lecture introduces computational complexity, including how most decision problems are uncomputable, hardness and completeness, and reductions. Instructor: Erik Demaine

Description: This is the first of two lectures on numerics, covering irrational numbers, high-precision computation, and Karatsuba multiplication. Instructor: Srini Devadas

Description: Priority queues are introduced as a motivation for heaps. The lecture then covers heap operations and concludes with a discussion of heapsort. Instructor: Srini Devadas

Description: This lecture starts by using the comparison model to prove lower bounds for searching and sorting, and then discusses counting sort and radix sort, which run in linear time. Instructor: Erik Demaine

Description: This lecture starts with dictionaries in Python, considers the problems with using a direct-access table, and introduces hashing. The lecture discusses hashing with chaining, which is one way of dealing with collisions. Instructor: Erik Demaine

Description: This lecture covers table resizing, amortized analysis, string matching with the Karp-Rabin algorithm, and rolling hashes. Instructor: Erik Demaine

Description: This lecture introduces a second type of guessing, in which more subproblems are created so that more features of the solution can be found. This type of guessing is illustrated with piano/guitar fingering and the Tetris and Super Mario Brothers games. ...

Description: This lecture shows how to find shortest paths in directed acyclic graphs (DAGs) using topological sort, and in graphs without negative edges using Dijkstra's algorithm. Instructor: Srini Devadas

Description: This lecture covers optimizations that can improve real-life, average case performance of shortest path algorithms. These include using Dijkstra for a single source and single target, bi-directional search, and goal-directed or A* search. Instructor: Srini ...

Description: This recitation discusses principles of algorithm design, using example problems from previous final exams. Instructor: Victor Costan