Introduction to Algorithms (2011)

This recitation discusses the first problem from Problem Set 3, covering sweep-line algorithms and range queries.

This recitation starts with a review of comparison sorting methods, and then discusses counting sort and radix sort.

Sorting is introduced, and motivated by problems that become easier once the inputs are sorted. The lecture covers insertion sort, then discusses merge sort and analyzes its running time using a recursion tree.

This lecture describes an algorithm as a computational procedure to solve a problem, covers the random access machine and pointer models of computation, and introduces the document distance problem.

This lecture begins with a review of graphs and applications of graph search, discusses graph representations such as adjacency lists, and covers breadth-first search.

This recitation covers the wood-cutting problem (dynamic programming) and Bloom filters (hashing, probability).

This recitation discusses the knapsack problem and polynomial time vs. pseudo-polynomial time.

This recitation reviews numerics and graphs in preparation for Quiz 2.

This recitation looks at player positions in the Dance Dance Revolution game, along the lines of the guitar fingering example shown in lecture.

This recitation uses dynamic programming to find subsequences in the card game Crazy Eights, and to find the shortest path in a graph.

This recitation reviews the computational complexity concepts presented in lecture.

This recitation revisits the perfect-information blackjack problem that was covered in lecture.

This recitation covers breadth-first search for shortest paths.

This recitation discusses the Rubik's cube problem from Problem Set 6, and then uses a graph model to find an optimal build order for a simplified version of the StarCraft game.

This recitation briefly discusses Karatsuba multiplication, then covers Newton's method.

This recitation starts with a discussion of Problem Set 5, and then covers graph representations and breadth-first search.

This recitation covers depth-first search and DFS edge classification.

This recitation mostly covers rolling hashes, with a short discussion of amortized analysis at the end.

This recitation discusses principles of algorithm design, using example problems from previous final exams.

This recitation starts with a short discussion of hashing, and then discusses problem set code for most of the hour. Amortized analysis is also discussed briefly.

This recitation covers several practice problems for Quiz 1, taken from previous semesters of 6.006.

This recitation starts with a review of recursion trees and recurrences, and then discusses binary search trees.

This recitation covers insertion, deletion, and rebalancing of AVL trees.

This recitation continues to look at versions of the document distance code, and briefly discusses insertion and merge sort.

This recitation covers the Python cost model and looks at the code for document distance, including main and most functions except count_frequency.

This recitation covers asymptotic complexity, recurrences, and peak finding.

This lecture introduces computational complexity, including how most decision problems are uncomputable, hardness and completeness, and reductions.

In this lecture, both professors present areas of current research, including parallel processor architecture and algorithms, geometric folding algorithms, data structures, and graph algorithms.

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.

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.

This lecture starts with a five-step process for dynamic programming, and then covers text justification and perfect-information blackjack. The lecture also describes how parent pointers are used to recover the solution.

This lecture reviews shortest path notation, considers a generic shortest path algorithm, and then describes and proves the Bellman-Ford algorithm, which can handle graphs with negative cycles.

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.

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.

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.

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.

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

This lecture begins with error analysis of Newton's method and a comparison of multiplication algorithms. It then covers high-precision division, which is required for Newton's method, and discusses the complexity of division and computing square roots.

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

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.

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

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.

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.

In this lecture, binary search trees are introduced, and several operations are covered: insertion, finding a value, finding the minimum element.

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

Overview of course content, including an motivating problem for each of the modules. The lecture then covers 1-D and 2-D peak finding, using this problem to point out some issues involved in designing efficient algorithms.