Princeton University
Computer Science Department

Computer Science 528
Data Structures and Graph Algorithms

Robert Tarjan

Fall 2005

Directory
General Information: Check Here for Announcements

Problem Sets and Handouts

Course Summary

Administrative Information

Lectures: MW 1100-1220, Room: 401

Professor: Robert Tarjan - 324 CS Building - 258-4797 ret@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly@cs.princeton.edu

Teaching Assistants: None for this course

Problem Sets

Handouts
Melding Priority Queues
Np is as Easy as Detecting Unique Solutions
Sodoku Puzzle
Disjoint Set Union
Union-Find with Constant Time Deletions
Amortized Computational Complexity
Applications of Path Compression on Balanced Trees
A Fast Algorithm for Finding Dominators in a Flowgraph
Self-Adjusting Binary Search Trees
Dynamic Trees
The Soft Heap..
A Simpler Minimum...
A Randomized Linear-Time...
An Optimal Minimum...
A Minimum Spanning....
Union-Find....
Beyond the flow decomposition barrier
New Maximum Flow..
Mathematical Engineering....
A New Approach....
Linear-Time Triangulation....
Triangulating a Simple Polygon....
Computational Geometry Column 42....
An..Time Algorithm for Triangulating
Optimal Search In Planar..
Planar Point..
Making Data..
Simplified Linear
A Simple and fast
A Fast Las Vegas..
Efficient Planarity..
PQ Tree..
Testing for the Consecutive..
Design of Data Structure for Mergeable Trees