Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Robert Tarjan

Spring 2004

General Information

Problem Sets and Handouts

Course Summary

Administrative Information

Lectures: MW 11:00-12:20, Room: 104 Large Auditorium

Precept: Mondays 8:00 - 9:00PM, Room: 105 Small Auditorium

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

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

Undergraduate Coordinator: Tina McCoy - 410 CS Building - Phone: 258-1746 - Email:

Teaching Assistants:

Paul Chang (Office Hours: Fridays 2-3pm), 001A CS, Ext 8-6862,

Shengyu Zhang (Office Hours: Tuesdays 3-4pm), 103C CS, Ext 8-0419,

Problem Sets
Problem Set 1(no collaboration)
Problem Set 2
Problem Set 3
Problem Set 4
Problem Set 5

Course Information
Material Covered in COS 226
Tentitive Schedule
Algorithms, Complexity & Combinatories
Amortized Computational Complexity
Complexity of Combinatorial Algorithms
Planar Point
Simulating Queues
Binary Search Trees
Splay Trees Handout
How Long to Process Sequence..?
Shortest Path Problem
Thin Heaps
Priority Search Trees
Doubly Ordered Trees
Disjoint set union 1
Disjoint set union 2
Disjoint set union cont.
Graphs, Search, Components
Class Notes ...
March 1st Handout
Minimum Spanning Tree Problem
Path Based ..
March 10th Handout
A Randomized Linear..
Maximum Network Flow
Planar Graphs
April 5th Handout
April 7th Handout
Sketchy Notes
April 12th Handout
Coping with NP Completeness
The Planar Hamiltonian...
Planar Graphic four coloring..
Deques Handout on April 26
Quest for Efficeint Boolean..
Digital Computing...
Malik Lecture
Minimum Cost Network Flow