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.


Lecture 1: Asymptotic complexity, recurrences, peak finding

Lecture 2: Python cost model, document distance

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

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

Lecture 5: Binary search trees

Lecture 6: AVL trees

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

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

Lecture 10: Hashing III: Open-addressing

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

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

Lecture 13: Graphs, Breadth first search (BFS)

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

Lecture 15: Shortest paths, edge relaxation

Lecture 16: Dijkstra's shortest path algorithm

Lecture 17: Bellman-Ford shortest path algorithm

Lecture 18: Dijkstra optimizations (bidirectional search)

Quiz 2

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

Lecture 20: Dynamic Programming II: Text justification

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

Lecture 22: Dynamic Programming IV

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