# Introduction to Algorithms (2011)

## by Erik Demaine, Srini Devadas

To listen to an audio podcast, mouse over the title and click Play. Open iTunes to download and subscribe to iTunes U collections.

#### Description

Lecture videos from 6.006 Introduction to Algorithms, taught by Erik Demaine and Srini Devadas. The course is divided into eight units: introduction, sorting and trees, hashing, numerics, graphs, shortest paths, dynamic programming, and advanced topics.

Name | Description | Released | Price | ||
---|---|---|---|---|---|

1 | VideoLecture 1: Algorithmic Thinking, Peak Finding | 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. | 12/7/12 | Free | View In iTunes |

2 | VideoRecitation 1: Asymptotic Complexity, Peak Finding | This recitation covers asymptotic complexity, recurrences, and peak finding. | 12/10/12 | Free | View In iTunes |

3 | VideoLecture 2: Models of Computation, Document Distance | 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. | 8/16/13 | Free | View In iTunes |

4 | VideoRecitation 2: Python Cost Model, Document Distance | This recitation covers the Python cost model and looks at the code for document distance, including main and most functions except count_frequency. | 12/10/12 | Free | View In iTunes |

5 | VideoLecture 3: Insertion Sort, Merge 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. | 8/16/13 | Free | View In iTunes |

6 | VideoRecitation 3: Document Distance, Insertion and Merge Sort | This recitation continues to look at versions of the document distance code, and briefly discusses insertion and merge sort. | 12/10/12 | Free | View In iTunes |

7 | VideoLecture 4: Heaps and Heap Sort | Priority queues are introduced as a motivation for heaps. The lecture then covers heap operations and concludes with a discussion of heapsort. | 12/7/12 | Free | View In iTunes |

8 | VideoLecture 5: Binary Search Trees, BST Sort | In this lecture, binary search trees are introduced, and several operations are covered: insertion, finding a value, finding the minimum element. | 12/7/12 | Free | View In iTunes |

9 | VideoRecitation 5: Recursion Trees, Binary Search Trees | This recitation starts with a review of recursion trees and recurrences, and then discusses binary search trees. | 12/10/12 | Free | View In iTunes |

10 | VideoLecture 6: AVL Trees, AVL Sort | This lecture covers AVL trees, including how to insert elements and rebalance the tree, and then discusses the difference between abstract data types and data structures. | 12/7/12 | Free | View In iTunes |

11 | VideoRecitation 6: AVL Trees | This recitation covers insertion, deletion, and rebalancing of AVL trees. | 12/10/12 | Free | View In iTunes |

12 | VideoLecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting | 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. | 12/7/12 | Free | View In iTunes |

13 | VideoRecitation 7: Comparison Sort, Counting and Radix Sort | This recitation starts with a review of comparison sorting methods, and then discusses counting sort and radix sort. | 8/16/13 | Free | View In iTunes |

14 | VideoLecture 8: Hashing with Chaining | 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. | 12/7/12 | Free | View In iTunes |

15 | VideoRecitation 8: Simulation Algorithms | This recitation discusses the first problem from Problem Set 3, covering sweep-line algorithms and range queries. | 8/16/13 | Free | View In iTunes |

16 | VideoLecture 9: Table Doubling, Karp-Rabin | This lecture covers table resizing, amortized analysis, string matching with the Karp-Rabin algorithm, and rolling hashes. | 12/7/12 | Free | View In iTunes |

17 | VideoRecitation 9: Rolling Hashes, Amortized Analysis | This recitation mostly covers rolling hashes, with a short discussion of amortized analysis at the end. | 12/10/12 | Free | View In iTunes |

18 | VideoRecitation 9b: DNA Sequence Matching | 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. | 12/10/12 | Free | View In iTunes |

19 | VideoLecture 10: Open Addressing, Cryptographic Hashing | 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. | 12/7/12 | Free | View In iTunes |

20 | VideoRecitation 10: Quiz 1 Review | This recitation covers several practice problems for Quiz 1, taken from previous semesters of 6.006. | 12/10/12 | Free | View In iTunes |

21 | VideoLecture 11: Integer Arithmetic, Karatsuba Multiplication | This is the first of two lectures on numerics, covering irrational numbers, high-precision computation, and Karatsuba multiplication. | 12/7/12 | Free | View In iTunes |

22 | VideoRecitation 11: Principles of Algorithm Design | This recitation discusses principles of algorithm design, using example problems from previous final exams. | 12/10/12 | Free | View In iTunes |

23 | VideoLecture 12: Square Roots, Newton's Method | 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. | 12/7/12 | Free | View In iTunes |

24 | VideoRecitation 12: Karatsuba Multiplication, Newton's Method | This recitation briefly discusses Karatsuba multiplication, then covers Newton's method. | 12/10/12 | Free | View In iTunes |

25 | VideoLecture 13: Breadth-First Search (BFS) | 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. | 2/4/13 | Free | View In iTunes |

26 | VideoRecitation 13: Breadth-First Search (BFS) | This recitation starts with a discussion of Problem Set 5, and then covers graph representations and breadth-first search. | 12/10/12 | Free | View In iTunes |

27 | VideoLecture 14: Depth-First Search (DFS), Topological Sort | This lecture covers depth-first search, including edge classification, and how DFS is used for cycle detection and topological sort. | 12/7/12 | Free | View In iTunes |

28 | VideoRecitation 14: Depth-First Search (DFS) | This recitation covers depth-first search and DFS edge classification. | 12/10/12 | Free | View In iTunes |

29 | VideoLecture 15: Single-Source Shortest Paths Problem | 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. | 12/7/12 | Free | View In iTunes |

30 | VideoRecitation 15: Shortest Paths | This recitation covers breadth-first search for shortest paths. | 12/10/12 | Free | View In iTunes |

31 | VideoLecture 16: Dijkstra | 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. | 12/7/12 | Free | View In iTunes |

32 | VideoRecitation 16: Rubik's Cube, StarCraft Zero | 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. | 12/10/12 | Free | View In iTunes |

33 | VideoLecture 17: Bellman-Ford | 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. | 12/7/12 | Free | View In iTunes |

34 | VideoLecture 18: Speeding up Dijkstra | 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. | 12/7/12 | Free | View In iTunes |

35 | VideoRecitation 18: Quiz 2 Review | This recitation reviews numerics and graphs in preparation for Quiz 2. | 12/10/12 | Free | View In iTunes |

36 | VideoLecture 19: Dynamic Programming I: Fibonacci, Shortest Paths | 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. | 12/7/12 | Free | View In iTunes |

37 | VideoRecitation 19: Dynamic Programming: Crazy Eights, Shortest Path | This recitation uses dynamic programming to find subsequences in the card game Crazy Eights, and to find the shortest path in a graph. | 12/10/12 | Free | View In iTunes |

38 | VideoLecture 20: Dynamic Programming II: Text Justification, Blackjack | 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. | 12/7/12 | Free | View In iTunes |

39 | VideoRecitation 20: Dynamic Programming: Blackjack | This recitation revisits the perfect-information blackjack problem that was covered in lecture. | 12/10/12 | Free | View In iTunes |

40 | VideoLecture 21: DP III: Parenthesization, Edit Distance, Knapsack | 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. | 12/7/12 | Free | View In iTunes |

41 | VideoRecitation 21: Dynamic Programming: Knapsack Problem | This recitation discusses the knapsack problem and polynomial time vs. pseudo-polynomial time. | 12/10/12 | Free | View In iTunes |

42 | VideoLecture 22: DP IV: Guitar Fingering, Tetris, Super Mario Bros. | 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. | 12/7/12 | Free | View In iTunes |

43 | VideoRecitation 22: Dynamic Programming: Dance Dance Revolution | This recitation looks at player positions in the Dance Dance Revolution game, along the lines of the guitar fingering example shown in lecture. | 12/10/12 | Free | View In iTunes |

44 | VideoLecture 23: Computational Complexity | This lecture introduces computational complexity, including how most decision problems are uncomputable, hardness and completeness, and reductions. | 12/7/12 | Free | View In iTunes |

45 | VideoRecitation 23: Computational Complexity | This recitation reviews the computational complexity concepts presented in lecture. | 12/10/12 | Free | View In iTunes |

46 | VideoLecture 24: Topics in Algorithms Research | In this lecture, both professors present areas of current research, including parallel processor architecture and algorithms, geometric folding algorithms, data structures, and graph algorithms. | 12/7/12 | Free | View In iTunes |

47 | VideoRecitation 24: Final Exam Review | This recitation covers the wood-cutting problem (dynamic programming) and Bloom filters (hashing, probability). | 12/10/12 | Free | View In iTunes |

47 Items |

#### Customer Reviews

##### Lecture 2 is actually the video of lecture 3

Lecture 2 is actually the video of lecture 3

- Free
- Category: Computer Science
- Language: English
- http://ocw.mit.edu; Creative Commons Attribution-NonCommercial-ShareAlike 3.0; http://ocw.mit.edu/terms; Album image by Srini Devadas.