Courses:

Introduction to Algorithms >> Content Detail



Calendar / Schedule



Calendar

This table provides information about both the lecture (L) and recitation (R) sessions.


SES #TOPICSKEY DATES
Introduction and document distance
L1Introduction and document distance
R1Document distance in Python (docdist{1,2,3,4}.py)
L2More document distance, mergesort
R2Python cost model, review for asymptotic notation and mergesort
Binary search trees
L3Airplane scheduling, binary search trees
R3Binary search trees
L4Balanced binary search trees
R4AVL Trees (balanced binary search trees)
Hashing
L5Hashing I: chaining, hash functionsProblem set 1 due
R5Hashing in Python, mutability
L6Hashing II: table doubling, Karp-Rabin
R6Karp-Rabin review, rolling hashes principles and code
L7Hashing III: open addressing
R7

Open addressing: theory review, Python code

More rolling hashes

Sorting
L8Sorting I: heaps
R8

Overview of sorting methods

Heaps as data structures: principles, sorting, priority queues

L9Sorting II: heapsProblem set 2 due
L10Sorting III: lower bounds, linear-time sorting
R9Quiz review: interesting problemsQuiz 1
L11Sorting IV: stable sorting, radix sort
R10Counting, radix and bucket sorting, gas simulation
Searching
L12Searching I: graph search, representations, and applications
L13Searching II: breadth-first search and depth-first searchProblem set 3 due
L14Searching III: topological sort and NP-completeness
R11Breadth-first search and depth-first search
Shortest paths
L15Shortest paths I: intro
R12Assistance for problem set
L16Shortest paths II: Bellman-FordProblem set 4 due
R13

Generic shortest-path algorithm: concepts, properties

Bellman-Ford: examples, negative-cost cycles

L17Shortest paths III: Dijkstra
R14

Hands-on Dijkstra: pseudocode, preconditions, examples, why it works

Priority queues: review, extended Python implementation

L18Shortest paths IV: Dijkstra speedups
R15Array implementation of DijkstraQuiz 2
Dynamic programming
L19Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing
R16Hands-on dynamic programming: big ideas, memoization in Fibonacci, crazy cards, Dijkstra and Bellman-Ford algorithm as dynamic programming
L20Dynamic programming II: longest common subsequence (LCS), parent pointers
R17More dynamic programming: beating Super Mario Brothers, getting points back on tests (LCS), Crazy Eights
L21Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris trainingProblem set 5 due
R18Even more dynamic programming: maximum-sum sub-array, more Tetris
L22Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond
R19Knapsack and its variants, structural dynamic programming: covering a tree with templates, dominating set
Numerics
L23Numerics I
R20Dynamic programming practice: live Python coding, dominating sets, structural dynamic programming: covering a tree with templates
L24Numerics IIProblem set 6 due
R21Divide and conquer vs. dynamic programming on problems: matrix multiplication, tower, max-sum subarray, closest pair
R22Numerics review, Strassen's algorithm for matrix multiplication
Beyond 6.006
L25Beyond 6.006: follow-on classes, geometric folding algorithms
R23Review for the final exam

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.