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

Description: This recitation mostly covers rolling hashes, with a short discussion of amortized analysis at the end. Instructor: Victor Costan