MIT 6.006 Intro to Algorithms

WARNING: This is not MIT 6.046J, which is Design and Analysis of Algorithms
(All Contents belong to MITOpenCourseware)

READINGS

• Unit 1: Introduction

  • Algoirthmic thinking, peak finding: Book Ch 1, Ch 3, D.1
    • Assignment 1
  • Models of computation, Python cost model, document distance: Book Ch 1, Ch 3, Python Cost Model

• Unit 2: Sorting and Trees

  • Insertion sort, merge sort: Book Ch 1.2, Ch 2.1 ~ 2.3, Ch 4.3 ~ 4.6
    • Assignment 2
  • Heaps and heap sort: Book Ch 6.1 ~ 6.4
  • BInary search trees, BST sort: Book Ch 10.4, 12.1 ~ 12.3, Binary Search Trees
  • AVL trees, AVL sort: Book Ch 13.2, Ch 14
    • Assignment 3
  • Counting sort, radix sort, lower bounds for sorting and searching: Book Ch 8.1 ~ 8.3

• Unit 3: Hashing

  • Hashing with chaining: Book Ch 11.1 ~ 11.3
  • Table doubling, Karp-Rabin: Book Ch 17
    • Assignment 4
  • Open addressing, cryptographic hashing: Book Ch 11.4
  • Quiz 1

• Unit 4: Numerics

  • Integer arithmetic, Karatsuba multiplication (No readings)
    • Assignment 5
  • Square roots, Newton's method (No readings)

• Unit 5: Graphs

  • Breadth-first search (BFS): Book Ch 22.1 ~ 22.2, B.4
  • Depth-first search (DFS), topological sorting: Book Ch 22.3 ~ 22.4
    • Assignment 6

• Unit 6: Shortest Paths

  • Single-source shortest paths problem: Book Ch 24.0, 24.5
  • Dijkstra: Book Ch 24.3
  • Bellman-Ford: Book Ch 24.1 ~ 24.2
  • Speeding up Dijkstra
  • Quiz 2

• Unit 7: Dynamic Programming

  • Memoization, subproblems, guessing, bottom-up, Fibonacci, shortest paths: Book Ch 15.1, Ch 15.3
    • Assignment 7
  • Parent pointers; text justification, perfect-information blackjack: Book Ch 15.3, Problem 15-4, Blackjack rules
  • String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack: Book Ch 15.1, Ch 15.2, Ch 15.4
  • Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros.

• Unit 8: Advanced Topics

  • Computational complexity: Book Ch 34.1 ~ Ch 34.3
  • Algorithms research topics (No readings)

Assignments

• Assignment 1
  • Asymptotic complexity
  • Recurrence relations
  • Peak finding
• Assignment 2
  • Fractal rendering
  • digital circuit simulation
• Assignment 3
  • Range queries
  • digital circuit layout
• Assignment 4
  • Hash functions
  • Python dictionaries
  • matching DNA sequences
• Assignment 5
  • The knight's Shield
  • RSA public key encryption
  • Image decryption
• Assignment 6
  • Social networks
  • Rubik's Cube
  • Dijkstra
• Assignment 7
  • Seam carving
  • Stock purchasing and knapsack