Introduction to Algorithms (2011)

Introduction to Algorithms (2011)

Follow Introduction to Algorithms (2011)
Share on
Copy link to clipboard

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.

Erik Demaine, Srini Devadas


    • Aug 16, 2013 LATEST EPISODE
    • infrequent NEW EPISODES
    • 53m AVG DURATION
    • 47 EPISODES


    Search for episodes from Introduction to Algorithms (2011) with a specific topic:

    Latest episodes from Introduction to Algorithms (2011)

    Recitation 8: Simulation Algorithms

    Play Episode Listen Later Aug 16, 2013 55:38


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

    Recitation 7: Comparison Sort, Counting and Radix Sort

    Play Episode Listen Later Aug 16, 2013 51:08


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

    Lecture 3: Insertion Sort, Merge Sort

    Play Episode Listen Later Aug 16, 2013 51:19


    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.

    Lecture 2: Models of Computation, Document Distance

    Play Episode Listen Later Aug 16, 2013 48:51


    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.

    Lecture 13: Breadth-First Search (BFS)

    Play Episode Listen Later Feb 4, 2013 50:47


    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.

    Recitation 24: Final Exam Review

    Play Episode Listen Later Dec 10, 2012 51:43


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

    Recitation 21: Dynamic Programming: Knapsack Problem

    Play Episode Listen Later Dec 10, 2012 69:11


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

    Recitation 18: Quiz 2 Review

    Play Episode Listen Later Dec 10, 2012 65:29


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

    Recitation 22: Dynamic Programming: Dance Dance Revolution

    Play Episode Listen Later Dec 10, 2012 53:15


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

    Recitation 19: Dynamic Programming: Crazy Eights, Shortest Path

    Play Episode Listen Later Dec 10, 2012 52:46


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

    Recitation 23: Computational Complexity

    Play Episode Listen Later Dec 10, 2012 47:12


    This recitation reviews the computational complexity concepts presented in lecture.

    Recitation 20: Dynamic Programming: Blackjack

    Play Episode Listen Later Dec 10, 2012 52:57


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

    Recitation 15: Shortest Paths

    Play Episode Listen Later Dec 10, 2012 56:30


    This recitation covers breadth-first search for shortest paths.

    Recitation 16: Rubik's Cube, StarCraft Zero

    Play Episode Listen Later Dec 10, 2012 54:34


    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.

    Recitation 12: Karatsuba Multiplication, Newton's Method

    Play Episode Listen Later Dec 10, 2012 53:07


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

    Recitation 13: Breadth-First Search (BFS)

    Play Episode Listen Later Dec 10, 2012 54:52


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

    Recitation 14: Depth-First Search (DFS)

    Play Episode Listen Later Dec 10, 2012 53:38


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

    Recitation 9: Rolling Hashes, Amortized Analysis

    Play Episode Listen Later Dec 10, 2012 61:00


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

    Recitation 11: Principles of Algorithm Design

    Play Episode Listen Later Dec 10, 2012 58:25


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

    Recitation 9b: DNA Sequence Matching

    Play Episode Listen Later Dec 10, 2012 57:27


    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.

    Recitation 10: Quiz 1 Review

    Play Episode Listen Later Dec 10, 2012 54:48


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

    Recitation 5: Recursion Trees, Binary Search Trees

    Play Episode Listen Later Dec 10, 2012 59:15


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

    Recitation 6: AVL Trees

    Play Episode Listen Later Dec 10, 2012 53:27


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

    Recitation 3: Document Distance, Insertion and Merge Sort

    Play Episode Listen Later Dec 10, 2012 54:09


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

    Recitation 2: Python Cost Model, Document Distance

    Play Episode Listen Later Dec 10, 2012 52:20


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

    Recitation 1: Asymptotic Complexity, Peak Finding

    Play Episode Listen Later Dec 10, 2012 53:49


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

    Lecture 23: Computational Complexity

    Play Episode Listen Later Dec 7, 2012 51:11


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

    Lecture 24: Topics in Algorithms Research

    Play Episode Listen Later Dec 7, 2012 46:45


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

    Lecture 22: DP IV: Guitar Fingering, Tetris, Super Mario Bros.

    Play Episode Listen Later Dec 7, 2012 49:19


    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.

    Lecture 21: DP III: Parenthesization, Edit Distance, Knapsack

    Play Episode Listen Later Dec 7, 2012 52:40


    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.

    Lecture 20: Dynamic Programming II: Text Justification, Blackjack

    Play Episode Listen Later Dec 7, 2012 52:11


    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.

    Lecture 17: Bellman-Ford

    Play Episode Listen Later Dec 7, 2012 48:50


    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.

    Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths

    Play Episode Listen Later Dec 7, 2012 51:46


    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.

    Lecture 18: Speeding up Dijkstra

    Play Episode Listen Later Dec 7, 2012 53:15


    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.

    Lecture 16: Dijkstra

    Play Episode Listen Later Dec 7, 2012 51:25


    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.

    Lecture 15: Single-Source Shortest Paths Problem

    Play Episode Listen Later Dec 7, 2012 53:14


    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.

    Lecture 11: Integer Arithmetic, Karatsuba Multiplication

    Play Episode Listen Later Dec 7, 2012 47:23


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

    Lecture 12: Square Roots, Newton's Method

    Play Episode Listen Later Dec 7, 2012 51:16


    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.

    Lecture 14: Depth-First Search (DFS), Topological Sort

    Play Episode Listen Later Dec 7, 2012 50:30


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

    Lecture 10: Open Addressing, Cryptographic Hashing

    Play Episode Listen Later Dec 7, 2012 50:54


    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.

    Lecture 9: Table Doubling, Karp-Rabin

    Play Episode Listen Later Dec 7, 2012 52:46


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

    Lecture 8: Hashing with Chaining

    Play Episode Listen Later Dec 7, 2012 51:15


    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.

    Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting

    Play Episode Listen Later Dec 7, 2012 52:08


    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.

    Lecture 5: Binary Search Trees, BST Sort

    Play Episode Listen Later Dec 7, 2012 52:39


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

    Lecture 6: AVL Trees, AVL Sort

    Play Episode Listen Later Dec 7, 2012 51:58


    Lecture 4: Heaps and Heap Sort

    Play Episode Listen Later Dec 7, 2012 52:31


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

    Lecture 1: Algorithmic Thinking, Peak Finding

    Play Episode Listen Later Dec 7, 2012 53:21


    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.

    Claim Introduction to Algorithms (2011)

    In order to claim this podcast we'll send an email to with a verification link. Simply click the link and you will be able to edit tags, request a refresh, and other features to take control of your podcast page!

    Claim Cancel