Courses:

Introduction to Algorithms >> Content Detail



Recitations



Recitations

Special software is required to use some of the files in this section: .py, .rb, and .zip.

These recitation slides are courtesy of Victor Costan, one of the course TAs, and are used with permission.


REC #TOPICSSUPPORTING FILES
Introduction and document distance
R1Document distance in Python (docdist{1,2,3,4}.py) (PDF)
R2Python cost model, review for asymptotic notation and mergesort (PDF)

Zipped data (numbers) (ZIP) (This zip file includes: 2 .jpg files, 1 .gz file, 1 .tiff file, 1 .numbers file, and 1 .pkginfo file.)

Python Cost Model
Binary search trees
R3Binary search trees (PDF)Code for binary search trees augmented with subtree size (PY)
R4AVL Trees (balanced binary search trees) (PDF)Code for AVL trees (uses the BST code from R3) (PY)
Hashing
R5Hashing in Python, mutability (PDF)The dangers of mutable dictionary keys (PY)
R6Karp-Rabin review, rolling hashes principles and code (PDF)Rolling hash code (PY)
R7

Open addressing: theory review, Python code

More rolling hashes (PDF)

Open addressing code (PY)
Sorting
R8

Overview of sorting methods

Heaps as data structures: principles, sorting, priority queues (PDF)

R9Quiz review: interesting problems (PDF)
R10Counting, radix and bucket sorting, gas simulation
Searching
R11Breadth-first search and depth-first search (PDF)

Code for breadth-first search (PY)

Code for depth-first search (PY)

Shortest paths
R12Assistance for problem set (PDF)
R13

Generic shortest-path algorithm: concepts, properties

Bellman-Ford: examples, negative-cost cycles

R14

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

Priority queues: review, extended Python implementation (PDF)

R15Array implementation of Dijkstra
Dynamic programming
R16Hands-on dynamic programming: big ideas, memoization in Fibonacci, crazy cards, Dijkstra and Bellman-Ford algorithm as dynamic programming (PDF)
R17More dynamic programming: beating Super Mario Brothers, getting points back on tests (LCS), Crazy Eights (PDF)
R18Even more dynamic programming: maximum-sum sub-array, more Tetris (PDF)
R19Knapsack and its variants, structural dynamic programming: covering a tree with templates, dominating set
Numerics
R20Dynamic programming practice: live Python coding, dominating sets, structural dynamic programming: covering a tree with templates

Live Python Coding problems (problem statement, tests, and solutions are included):

- Matrix chain multiplication (ZIP) (This zip file includes: 3 .py files, 1 .pyc file, 1 .rb file, and 6 data files.)

- Longest zig-zag subsequence (ZIP) (This zip file includes: 3 .py files, 1 .pyc file, 1 .rb file, and 4 data files.)

R21Divide and conquer vs. dynamic programming on problems: matrix multiplication, tower, max-sum subarray, closest pair
R22Numerics review, Strassen's algorithm for matrix multiplicationStrassen's algorithm for fast matrix multiplication is covered in CRLS, chapter 28, pp. 735-742.
Beyond 6.006
R23Review for the final exam (PDF)

 








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