Princeton University Computer Science Dept.

Computer Science 528 Data Structures and Algorithms Robert Tarjan

Fall 1999

Overview

We will study recent results and open problems in data structures and graph algorithms. My goal is to provide students who might be interested in doing research in the area with a taste of cutting-edge techniques and problems. I will run the course seminar-style: we will read and discuss a set of representative papers. We will seek the most efficient possible algorithms for various combinatorial problems and the techniques underlying the design and analysis of these algorithms. Prerequisite: COS 423 or equivilent. Topics will include the following:

Amortized Efficiency: techniques and simple examples, including fast heaps.

Functional/Persistent data structures: double-ended queues with catenation,
finger search trees.

Kinetic Data Structues: kinetic heaps

Dynamic Graph Algorithms: connectivity, dynamic trees

Graph Algorithms: minimum spanning trees, planarity-testing

Miscellaneous Topics

Organization

Instructor: Robert Tarjan - 324 CS Building - 258-4797, ret@cs.princeton.edu
or (408) 222-6216, ret@intertrust.com

Administrative Assistant: Sandy Barbu, 323 COS Building, 258-4562, barbu@cs.princeton.edu

Class Meetings: T, Th 1:00-2:50, Room: 301 CS Building

We will meet once a week for 1 hour, 50 minutes. This is an amortized bound (~12 meetings during the semester); specific meeting days will be determined by my travel schedule. When I am in California, feel free to contact me there about class matters, using the phone number or email address above.

First three meetings: T 9/21, Th 9/23, T 9/28