Date | Lecture notes | Video/Audio | Reading |
11/22/2011 | Dynamic Programming: Sequence Alignment |
Problem Description, starting the solution of subproblems
Continuing to match "mean" and "name"
Conclusion of matching "mean" and "name"; Traceback
|
KT: pp 278 - 284 |
11/17/2011 | Dynamic Programming: Subset Sums (almost the Knapsack problem) |
Problem Statement, Brute Force Solution
Recursive solution: first half
second half
Dynamic programming solution
'Higher-level' execution trace and trace back: first half
second half
|
KT: 266 - 271 |
11/10/2011 | Dynamic Programming: Weighted Interval Scheduling |
Problem Statement, Recursive Solution
Execution trace through the recursive solution
Dynamic programming solution
Trace back to get the intervals in the solution |
KT: 252-259 |
11/7/2011 | FFT algorithm | FFT is a divide and conquer algorithm
FFT step through, part 1
FFT step through, part 2
Same problem solved with matrix multiply
DFT, (recursive) FFT, and matrix Fn give the same answers |
|
11/1/2011 | (2)* Fourier Transform: Notes
(1)* Nice: intuitive explanation of Fourier transform
(0) Nice: FT from the fundamental mathematics
(3)* 1D FT examples
(4) Applet to do 2D FT
(5)*
A Sweet explanation of using FFT to do polynomial multiplication |
|
KT: 234-239 |
11/1/2011 | Complex Numbers (for the Fast Fourier Transform) | Representation: Cartesian, polar, and phasor
Complex Arithmetic
Complex Roots of Unity (2nd and 4th)
Complex Roots of Unity (8th) | |
10/13/2011 | Minimum Cost Arborescence |
1: What is an arborescence?
2: What is a minimum arborescence?
3: Finding minimum arborescence on directed graph with NO CYCLE
4: Another example of minimum arborescence on graph with no cycle
5: Finding minimum arborescence (need to make recursive call)
6: Finding minimum arborescence the original graph has a cycle, but can get an arborescence without recursion.
|
KT: 177-179, 181 |
10/13/2011 | Huffman Encoding |
1: Motivation and the Greedy Algorithm
2: Using the Huffman code
| KT: pp 161-162, 166-168, 172-173 |
10/11/2011 | Minimum Spanning Tree: Kruskal's, Prim's, Reverse Delete | | KT: pp 142-144 |
10/11/2011 | Clustering | | KT: pp 157-159 |
10/6/2011 | Shortest Path ( x --> y )
Dijkstra pseudo code (shortest path, single pair)
Floyd pseudo code (shortest paths, all pairs) |
Depth First Traversal doesn't work
Breadth First Traversal succeeds only if start x AND graph is unweighted
Dijkstra's Algorithm shortest path
Floyd's all-pairs shortest path (part 1)
Floyd's all-pairs shortest path (part 2)
Floyd's all-pairs shortest path (part 3)
| |
9/29/2011 | Elementary Graph Algorithms |
Breadth first traversal
Depth first traversal
DAG and Topological Sort
Testing for Bipartite
| |
9/29/2011 | Dynamic Programming example |
DP part 1
DP part 2
DP part 3
DP part 4
DP part 5
| |
9/22/2011 | Perfect Matching (Gale-Shapley Algorithm) | | |
9/22/2011 | Graph Data Structures | | |
9/20/2011 | BST rotations
| BST rotations part 1
BST single rotation (part 2)
BST single rotation (part 3)
AVL double rotation AKA zig zag (part 4)
AVL double rotation (part 5)
AVL double rotation, code tracing (part 6)
zig zig double rotation (part 7) |
|
9/20/2011 | Splay Tree |
Splay tree (part 1)
Splay tree (part 2)
(part 2 has been fixed from previous dumb errors in the recording)
Splay tree (part 3) - just a recap of rotations
Splay tree (part 4)
|
|
9/20/2011 | Other trees |
kD tree, k=2 (part 1)
kD tree, k=2 (part 2)
kD tree, k=3
quad tree, explanation and example
quad tree, second example clearer than first example |
|
9/15/2011 | | Trace recursion: Fibonacci
Trace recursion: Print singly linked list
Obtain, then solve recurrence for mergesort |
9/8/2011 | Big Oh, Trees | |
|
9/6/2011 | Counting, a
Counting, b | |
|