Princeton University
|
Computer Science 521
|
|
Professor: Robert Tarjan - 324 CS Building - 258-4797
ret@cs.princeton.edu Also: prof.tarjan@gmail.com
Graduate Coordinator:
Melissa Lawson - 310 CS Building - 258-5387
mml@cs.princeton.edu
Course Secretary: Mitra Kelly -323 CS Building - 258-4562 mkelly@cs.princeton.edu
Related courses at other institutions:
Advanced Algorithms, MIT: Advanced Algorithms 6.854 Course WebsiteUseful Information
Advanced Data Structures, MIT: Advanced Data Structures 6.851 Course Website
Advanced Algorithms, CMU: Advanced Algorithms 15-859(E) Course Website
Algorithms in the Real World, CMU: Algorithms in the "Real World" Course Website
Assignments
Problem Set 1: Due Wed Sept. 30 for full credit, no collaboration
Wed Oct. 7 for credit, collaboration allowed
Problem Set 2: Due Wed Oct. 19 Collaboration Allowed on 1 and 2, not on 3 (Note new Due Date)
Problem Set 2 Clarification
Problem Set 3: Due Wed Oct. 28th
Problem Set 4: Due Wed Dec 2nd
Final Project: Due Dates are as follows- Project Proposal, a 1/2-1 page summary of your topic, due on Monday, Dec. 14 Completed project, due on Dean's Date, Tuesday, January 12
Problem Set 5: Due Wed Dec 16th
Lecture Topics and Related Materials
| Date |
Topic |
Readings |
|
| Monday 9/21 |
Balanced Binary Search Trees | Rank-Balanced Trees
Link
|
|
| Wednesday 9/23 |
Deletion Without Rebalancing? and Other Questions | ||
| Monday 9/28 |
Unequal access in search trees; fingers, bias, caching, self-adjustment | For material on splay trees, see COS 423 Spring 2009 2/11 lecture
Link |
|
| Wednesday 9/30 |
Heaps (Priority Queues) | Monday 10/4 |
Pairing Heaps and Rank-Pairing Heaps | The Pairing Heap: A New Form of Self-Adjusting Heap
link
|
| Wednesday 10/07 |
Directed Graphs: Cycle Detection, Topological Ordering, and Strong Components | Path-based depth-first search for strong and biconnected components
link |
|
| Monday 10/12 |
Incremental Cycle Detection | A New Approach to Incremental Cycle Detection link |
Wednesday 10/14 |
Incremental Cycle Detection/Dynamic Connected Components | Poly Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Bioconnectivity link |
Monday 10/19 |
Dynamic Connected Components | Monday 10/26 |
Minimum Spanning Trees in Linear Time | Notes On Minimum Spanning Trees link
|
Wednesday 10/28 |
Verification of Minimum Spanning Trees | A Simpler Minimum Spanning Tree Verification Algorithm link
|
| Monday 11/09 |
Hashing | Cuckoo Hasing link
| |
| Wednesday 11/11 |
Hashing II | Efficient Hashing with Lookups in two Memory Accesses Link
| |
| Monday 11/16 |
Network Routing | Universal Schemes for Parallel Communication link | |
| Wednesday 11/18 |
Network Routing II | Notes on Routing in Regular Networks Link | |
| Monday 11/23 |
Analysis of Randomized Routing | Chernoff Bounds Lecture 10 Link
| |
| Wednesday 11/25 |
Graph Matching | An n5/2 Algorithm for maximum Matchings in Bipartite Graphs Link | |
| Monday 11/30 |
Nonbipartite Matching, Vertex Covers, Linear Programming | Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching Link
| |
| Wednesday 12/2 |
Shortest Paths | Scaling Algorithms for the Shortest Paths Problem Link | |
| Monday 12/7 |
The Assignment Problem and the Maximum Flow Problem | Faster Scaling Algorithms for Network Problems Link
| |