# Lectures and Recitations

## Contents

### Hashing

#### Lecture 6, Hashing II: Table Doubling, Karp-Rabin

• Reading: CLRS, Chapter 17 and Section 32.2

#### Lecture 7, Hashing III: Open Addressing

• Reading: CLRS, Section 11.4 (and 11.3.3 and 11.5 if interested)

### Sorting

#### Lecture 8, Sorting I: Heaps

• Reading: CLRS, Sections 2.1-2.3 and 6.1-6.2

#### Recitation 10, Counting,Radix and Bucket Sorting, Gas simulation

• Hueihan's Slides [PDF]

### Searching

#### Lecture 14, Searching III: Topological Sort and NP-completeness

• Reading: CLRS, Sections 22.4 and 34.1-34.3 (at a high level)

### Shortest Paths

#### Lecture 15, Shortest Paths I: Intro

• Reading: CLRS, Chapter 24 (Intro)

#### Recitation 14, Generic Shortest-Path Algorithm: Concepts, Properties; Bellman-Ford: Examples, Negative-Cost Cycles

No slides, you had to be there to get the material :)

### Dynamic Programming

#### Recitation 20, Knapsack and Its Variants, Structural Dynamic Programming: Covering a Tree with Templates, Dominating Set

• Covering a Tree with Templates
• Problem statement and original solution [PDF]
• Victor's solution during the quiz [PDF] (read and stop complaining about long psets :P)
• Dominating Set: the problem and solution are described in the Lecture 22 Notes

### Numerics

#### Lecture 23, Numerics I

• Demos (tested on IE 7, Firefox 2/3 or Safari 3; the latter renders the prettiest results)

#### Recitation 21, Dynamic Programming Practice: Live Python Coding, Dominating Sets, Structural Dynamic Programming: Covering a Tree with Templates

• Hueihan's Slides [PDF] |
• The problems for the Live Python Coding (problem statement, tests, and solutions are included):
• Matrix Chain Multiplication [Zip]
• Longest Zig-Zag Subsequence [Zip]
• Dominating Set: the problem and solution are described in the Lecture 22 Notes

#### Recitation 22(1)(2), Divide and Conquer vs Dynamic Programming on Problems: Matrix Multiplication, Tower, Max-sum Subarray, Closet Pair

• Hueihan's Slides [PDF] |
• MaxSumSubarray[PDF]