everything.study
6.006

Introduction to Algorithms

Undergraduate · Historical course

Spring 2020

This course is an introduction to mathematical modeling of computational problems, as well as common algorithms, algorithmic paradigms, and data structures used to solve these problems. It emphasizes the relationship between algorithms and programming and introduces basic performance measures and analysis techniques for these problems.

Readings

Fall 2011

Topics

  • Algorithmic thinking, peak finding
  • Models of computation, Python cost model, document distance
  • Insertion sort, merge sort
  • Heaps and heap sort
  • Binary search trees, BST sort
  • AVL trees, AVL sort
  • Counting sort, radix sort, lower bounds for sorting and searching
  • Hashing with chaining
  • Table doubling, Karp-Rabin
  • Open addressing, cryptographic hashing
  • Integer arithmetic, Karatsuba multiplication
  • Square roots, Newton’s method
  • Breadth-first search (BFS)
  • Depth-first search (DFS), topological sorting
  • Single-source shortest paths problem
  • Dijkstra
  • Bellman-Ford
  • Speeding up Dijkstra
  • Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths
  • Parent pointers; text justification, perfect-information blackjack
  • String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack
  • Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros.
  • Computational complexity
  • Algorithms research topics

Readings

Spring 2008

Topics

  • Introduction and document distance
  • Document distance in Python (docdist{1,2,3,4}.py)
  • More document distance, mergesort
  • Python cost model, review for asymptotic notation and mergesort
  • Airplane scheduling, binary search trees
  • Binary search trees
  • Balanced binary search trees
  • AVL Trees (balanced binary search trees)
  • Hashing I: chaining, hash functions
  • Hashing in Python, mutability
  • Hashing II: table doubling, Karp-Rabin
  • Karp-Rabin review, rolling hashes principles and code
  • Hashing III: open addressing
  • Sorting I: heaps
  • Sorting II: heaps
  • Sorting III: lower bounds, linear-time sorting
  • Sorting IV: stable sorting, radix sort
  • Counting, radix and bucket sorting, gas simulation
  • Searching I: graph search, representations, and applications
  • Searching II: breadth-first search and depth-first search
  • Searching III: topological sort and NP-completeness
  • Breadth-first search and depth-first search
  • Shortest paths I: intro
  • Assistance for problem set
  • Shortest paths II: Bellman-Ford
  • Shortest paths III: Dijkstra
  • Shortest paths IV: Dijkstra speedups
  • Array implementation of Dijkstra
  • Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing
  • Hands-on dynamic programming: big ideas, memoization in Fibonacci, crazy cards, Dijkstra and Bellman-Ford algorithm as dynamic programming
  • Dynamic programming II: longest common subsequence (LCS), parent pointers
  • More dynamic programming: beating Super Mario Brothers, getting points back on tests (LCS), Crazy Eights
  • Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training
  • Even more dynamic programming: maximum-sum sub-array, more Tetris
  • Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond
  • Knapsack and its variants, structural dynamic programming: covering a tree with templates, dominating set
  • Numerics I
  • Dynamic programming practice: live Python coding, dominating sets, structural dynamic programming: covering a tree with templates
  • Numerics II
  • Divide and conquer vs. dynamic programming on problems: matrix multiplication, tower, max-sum subarray, closest pair
  • Numerics review, Strassen’s algorithm for matrix multiplication
  • Beyond 6.006: follow-on classes, geometric folding algorithms

Readings

  • The primary written reference for the course is the following textbook:
    Listed reading
  • Buy at MIT Press Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms . 2nd ed. Cambridge, MA: MIT Press, 2001. ISBN: 9780262032933. ↗
    Listed reading
  • Miller, Bradley, and David Ranum. Problem Solving with Algorithms and Data Structures Using Python . Wilsonville, OR: Franklin, Beedle and Associates, 2005. ISBN: 9781590280539.
    Listed reading
  • In the table below, readings listed as CLRS are taken from the course textbook:
    Listed reading
  • LEC #: L1 · TOPICS: Introduction and document distance · READINGS: CLRS, chapters 1-3
    Reading assignment
  • LEC #: L2 · TOPICS: More document distance, mergesort · READINGS: CLRS, sections 11.1-11.2
    Reading assignment
  • LEC #: L3 · TOPICS: Airplane scheduling, binary search trees · READINGS: CLRS, chapter 10 and sections 12.1-12.3
    Reading assignment
  • LEC #: L4 · TOPICS: Balanced binary search trees · READINGS: CLRS, sections 13.1 and 13.2 for a different approach (red-black trees)
    Reading assignment
  • LEC #: L6 · TOPICS: Hashing II: table doubling, Karp-Rabin · READINGS: CLRS, chapter 17 and section 32.2
    Reading assignment
  • LEC #: L7 · TOPICS: Hashing III: open addressing · READINGS: CLRS, section 11.4 (and 11.3.3 and 11.5 if interested)
    Reading assignment
  • LEC #: L8 · TOPICS: Sorting I: heaps · READINGS: CLRS, sections 2.1-2.3 and 6.1-6.2
    Reading assignment
  • LEC #: L9 · TOPICS: Sorting II: heaps · READINGS: CLRS, sections 6.1-6.4
    Reading assignment
  • LEC #: L10 · TOPICS: Sorting III: lower bounds, linear-time sorting · READINGS: CLRS, sections 8.1-8.4
    Reading assignment
  • LEC #: L12 · TOPICS: Searching I: graph search, representations, and applications · READINGS: CLRS, sections 22.1-22.3 and B.4
    Reading assignment
  • LEC #: L13 · TOPICS: Searching II: breadth-first search and depth-first search · READINGS: CLRS, sections 22.2-22.3
    Reading assignment
  • LEC #: L14 · TOPICS: Searching III: topological sort and NP-completeness · READINGS: CLRS, sections 22.4 and 34.1-34.3 (at a high level)
    Reading assignment
  • LEC #: L15 · TOPICS: Shortest paths I: intro · READINGS: CLRS, chapter 24 (intro)
    Reading assignment
  • LEC #: L17 · TOPICS: Shortest paths III: Dijkstra · READINGS: CLRS, sections 24.2-24.3
    Reading assignment
  • Wagner, Dorothea, and Thomas Willhalm. “Speed-Up Techniques for Shortest-Path Computations.” In Lecture Notes in Computer Science: Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science . Berlin / Heidelberg: Springer, 2007. ISBN: 9783540709176. Read up to section 3.2.
    Listed reading
  • LEC #: L19 · TOPICS: Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing · READINGS: CLRS, chapter 15
    Reading assignment
  • Parncutt, Richard, et al. “An Ergonomic Model of Keyboard Fingering for Melodic Fragments.” Music Perception 14, no. 4 (1997): 341-382.
    Listed reading
  • Al Kasimi, Alia, Eric Nichols, and Christopher Raphael. “A Simple Algorithm for Automatic Generation of Polyphonic Piano Fingerings.” In Proceedings of the 8th International Conference on Music Information Retrieval , 2007, pp. 355-356.
    Listed reading
Sources