6.006 Intro to Algorithms: Extra Materials

A big "thank you" to my students for submitting their evaluations and for their great feedback :)

The materials I posted for my two 6.006 recitations in Spring 2014 can be found below.

"Prependix"

• Fun, fun: Why you should "grind" on algorithms and ask questions in recitation...
• Textbooks:
  • Introduction to Algorithms, 3rd edition, by Cormen, Leiserson, Rivest & Stein
  • The Algorithm Design Manual, 2nd edition, by Steven Skiena
  • Algorithms, by Dasgupta, Papadimitriou & Vazirani

Lecture 1: Asymptotic complexity, recurrences, peak finding

• Lecture 1 notes, from Tuesday, February 4th, Week 1
• {n \choose n/2} example, from Wednesday, February 5th, Week 1
• Big O notation and limits
• Big O notation, from Wikipedia
• Big O notation notes, from 16.070
• Code: 1D peak finding, in Python

Lecture 2: Python cost model, document distance

• Lecture 2 notes, from Thursday, February 6th, Week 1
• Algorithm Analysis, by Prof. Ray Toal

Lecture 3: Insertion sort, merge sort, expanding recurrences into trees

• Romanian folk dancing: Insertion sort
• Transylvanian-Saxon (German) folk dancing: Merge sort
• Code: Insertion sort, in Python
  • Output of code here.
• Master theorem, from Wikipedia

Lecture 4: Priority queues, heaps, heapify, heap-sort

• Why building a heap takes linear time, from Univ. of Maryland

Lecture 5: Binary search trees

• Deleting a node from a BST, from Univ. of Alberta

Lecture 6: AVL trees

• AVL tree simulator here. Watch insertions, deletions, traversals, etc. User controlled, step by step animations.
• Another AVL tree simulator here.
• AVL implementation in C++ here
• Why are AVL trees \log{n} in height?

Lecture 7: Counting sort, radix sort, lower bounds on sorting

• Comparison or decision trees, from Univ. of Cincinnati

Lecture 8: Hashing I: Python dictionaries, hash-tables with chaining, simple uniform hashing assumption

Lecture 9: Hashing II: Division method, multiplication method, amortized analysis of hash-table inserts, Rabin Karp string matching

• Recitation 9 notes on amortized analysis and Rabin Karp
• Recitation notes on Rabin Karp, from 6.006 Spring 2011

Lecture 10: Hashing III: Open-addressing

• Double hashing examples with deletions (tricky), from Univ. of Alberta
• Recitation 10 notes on open-addressing and cryptographic hash functions
• PSET3 Problem 3-1: Set using an abstract dictionary
• PSET3 Problem 3-3: Searching a matrix using rolling hashes

Lecture 11: Catalan numbers, Newton's method, Karatsuba multiplication

• Catalan numbers, from Univ. of South Carolina
• Catalan numbers, from Univ of California, Berkeley
• When does the Newton method fail?
• Karatsuba multiplication, from Wikipedia

Lecture 12: Using Newton's method to compute \sqrt(a)

• Fun, fun: Quake 3's fast inverse square root explained, by Christian Plesner Hansen

Lecture 13: Graphs, Breadth first search (BFS)

Lecture 14: Depth first search (DFS), topological sorting

• Reading: Depth first search: edge and node classification, CLRS 3rd ed., pg. 603-612
• Reading: Topological sorting using depth first search, CLRS 3rd ed., pg. 612-615

Lecture 15: Shortest paths, edge relaxation

Lecture 16: Dijkstra's shortest path algorithm

• Dijkstra lecture notes, from The Hong Kong Univ. of Science and Technology

Lecture 17: Bellman-Ford shortest path algorithm

• Recitation notes from 6.006 Fall 2010

Lecture 18: Dijkstra optimizations (bidirectional search)

Quiz 2

• Previous years 6.006 materials here
• Stuff to know: open-addressed hash tables (linear probing, double hashing, uniform hashing assumption, etc.), numerics (Karatsuba, Newton approximations, etc.), graphs, Depth-first search, Breadth-first search, edge classification, shortest path algorithms, Dijkstra's algorithm, the Bellman-Ford algorithm

Lecture 19: Dynamic Programming I: Memoization, subproblems and dependencies, Fibonacci numbers, Coin Row problem, bottom-up DP

Lecture 20: Dynamic Programming II: Text justification

• Worked out text justification, from Cornell University
• Transcript of a lecture on text justification, from Cal Poly

Lecture 21: Dynamic Programming III: Matrix chain multiplication, edit distance, knapsack

• Reading: CLRS 3rd ed., Chapter 15 Dynamic programming, pg. 359-389
• Reading: The Algorithm Design Manual, 2nd ed., Chapter 8 Dynamic programming, pg. 273-304
• Worked out matrix chain multiplication

Lecture 22: Dynamic Programming IV

• Practice problems, from University of Illinois, at Urbana-Champaign

Lecture 23: Computational complexity, P, NP, EXP, the halting problem, reductions

• Fun, fun: Scott Aaronson's TED talk

Appendix

• Geometric series, from Wikipedia
• Change of base in logarithms, from ProofWiki