Princeton University
Computer Science Department

Computer Science 528
Data Structures and Graph Algorithms

Robert Tarjan

Fall 2003

General Information

Check Here for Messages

Problem Sets and Handouts

Course Summary

Administrative Information

Lectures: MW 1100-1220, Room: FC007

Professor: Robert Tarjan - 324 CS Building - 258-4797

Secretary: Mitra Kelly - 323 CS Building - 258-4562

Problem Sets
Problem Set 1
Problem Set 2
Problem Set 3
Problem Set 4

Notes on Catenable Deques
Notes on Redundant Binary Number
Notes on Sorting by Two Stacks in Parallel
Open Problem sequence generation
Testing for the Consecutive
Two Streamlined Depth-First
Stop Minding Your P's and Q's
Notes on PQ-tree Reduction
Pure Versus Impure LISP
Implementation of PQ-tree
Notes on the Boyer-Myrvold Planary-Testing Algorithm
Maximum Network Flow
A New Approach to the Maximum-Flow Problem
Beyond the Flow Decomposition Barrier
Network Flow and Testing Graph Connectivity
Augmenting Paths
Final Project
Self-Adjusting Binary Search Trees
Dynamic Trees
Fibonacci Heaps and Their Uses
Scaling Algorithms for the Shortest Paths Problems
A Practical Shortest Path Algorithm..
The Minimum Spanning Tree Problem
A Randomized Linear-Time Algorithm
Efficient Algorithm For Funding...
A Fast Algorithm For Finding Dominators in a Flowchart
Applications of Path Compression on Balanced Trees
A Simpler Minimum Spanning Tree..
The Soft Heap
A Minimum Spanning Tree:Inverse-Ackerman
Poly-logarithmic deterministic...
Faster Kinetic Heaps...
Dynamic Planar Convex Hull