Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Robert Tarjan

Spring 2004

Directory
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: ret@cs.princeton.edu

Secretary:Mitra Kelly - 323 CS Building - Phone: 258-4562 - Email: mkelly@cs.princeton.edu

Undergraduate Coordinator: Tina McCoy - 410 CS Building - Phone: 258-1746 - Email: tmmccoy@cs.princeton.edu

Teaching Assistants:

Paul Chang (Office Hours: Fridays 2-3pm), 001A CS, Ext 8-6862, pmchang@princeton.edu

Shengyu Zhang (Office Hours: Tuesdays 3-4pm), 103C CS, Ext 8-0419, szhang@cs.princeton.edu

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

Handouts
Course Information
Material Covered in COS 226
Tentitive Schedule
Algorithms, Complexity & Combinatories
Amortized Computational Complexity
Complexity of Combinatorial Algorithms
Planar Point
Amortize
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 ..
Dyntrees
March 10th Handout
A Randomized Linear..
Maximum Network Flow
Planar Graphs
CUT
Dominators
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