Introduction to Algorithms - Lecture 21: Dynamic ...
Introduction to Algorithms - Lecture 21: Dynamic Programming III: ...
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
Introduction to Algorithms - Lecture 10: Open Addressing, ...
Introduction to Algorithms - Lecture 10: Open Addressing, Cryptographic ...
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
Introduction to Algorithms - Lecture 14: Depth-First Search ...
Introduction to Algorithms - Lecture 14: Depth-First Search (DFS), ...
Description: This lecture covers depth-first search, including edge classification, and how DFS is used for cycle detection and topological sort. Instructor: Erik Demaine
Introduction to Algorithms - Lecture 15: Single-Source ...
Introduction to Algorithms - Lecture 15: Single-Source Shortest Paths ...
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
Introduction to Algorithms - Lecture 19: Dynamic ...
Introduction to Algorithms - Lecture 19: Dynamic Programming I: Fibonacci, ...
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. ...
Introduction to Algorithms - Recitation 10: Quiz 1 Review
Introduction to Algorithms - Recitation 10: Quiz 1 Review
Description: This recitation covers several practice problems for Quiz 1, taken from previous semesters of 6.006. Instructor: Victor Costan
Introduction to Algorithms - Recitation 20: Dynamic ...
Introduction to Algorithms - Recitation 20: Dynamic Programming: Blackjack
Description: This recitation revisits the perfect-information blackjack problem that was covered in lecture. Instructor: Victor Costan
Introduction to Algorithms - Recitation 24: Final Exam ...
Introduction to Algorithms - Recitation 24: Final Exam Review
Description: This recitation covers the wood-cutting problem (dynamic programming) and Bloom filters (hashing, probability). Instructor: Victor Costan
Introduction to Algorithms - Lecture 23: Computational ...
Introduction to Algorithms - Lecture 23: Computational Complexity
Description: This lecture introduces computational complexity, including how most decision problems are uncomputable, hardness and completeness, and reductions. Instructor: Erik Demaine
Introduction to Algorithms - Lecture 11: Integer ...
Introduction to Algorithms - Lecture 11: Integer Arithmetic, Karatsuba ...
Description: This is the first of two lectures on numerics, covering irrational numbers, high-precision computation, and Karatsuba multiplication. Instructor: Srini Devadas
Introduction to Algorithms - Lecture 4: Heaps and Heap Sort
Introduction to Algorithms - Lecture 4: Heaps and Heap Sort
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
Introduction to Algorithms - Lecture 7: Counting Sort, ...
Introduction to Algorithms - Lecture 7: Counting Sort, Radix Sort, Lower ...
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
Introduction to Algorithms - Lecture 8: Hashing with ...
Introduction to Algorithms - Lecture 8: Hashing with Chaining
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
Introduction to Algorithms - Lecture 9: Table Doubling, ...
Introduction to Algorithms - Lecture 9: Table Doubling, Karp-Rabin
Description: This lecture covers table resizing, amortized analysis, string matching with the Karp-Rabin algorithm, and rolling hashes. Instructor: Erik Demaine
Introduction to Algorithms - Lecture 22: Dynamic ...
Introduction to Algorithms - Lecture 22: Dynamic Programming IV: Guitar ...
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. ...
Introduction to Algorithms - Lecture 16: Dijkstra
Introduction to Algorithms - Lecture 16: Dijkstra
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
Introduction to Algorithms - Lecture 18: Speeding up ...
Introduction to Algorithms - Lecture 18: Speeding up Dijkstra
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 ...
Introduction to Algorithms - Recitation 11: Principles of ...
Introduction to Algorithms - Recitation 11: Principles of Algorithm Design
Description: This recitation discusses principles of algorithm design, using example problems from previous final exams. Instructor: Victor Costan
Introduction to Algorithms - Recitation 9: Rolling Hashes, ...
Introduction to Algorithms - Recitation 9: Rolling Hashes, Amortized ...
Description: This recitation mostly covers rolling hashes, with a short discussion of amortized analysis at the end. Instructor: Victor Costan
Introduction to Algorithms - Recitation 2: Python Cost ...
Introduction to Algorithms - Recitation 2: Python Cost Model, Document ...
Description: This recitation covers the Python cost model and looks at the code for document distance, including main and most functions except count_frequency. Instructor: Victor Costan