Home   Current Courses   Video/Audio Library     Course Archive   Papers Archive   Beyond the Box   CV   Service My Keeper Shelf Cultural References in Class

COSC 511 Design and Analysis of Algorithms FALL 2011


Textbook: Kleinberg and Tardos, Algorithm Design, Addison Wesley, ISBN:0321295358

1. Lecture notes, Recordings, and InLabs

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 halfsecond 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
 
2. Assignments (Homework) 3. Projects 4. Quizzes and Tests 5. General 6. Resources


Last changed: