Fall 2008

Seminar in Computer Science

Listed in: Computer Science, as COSC-40


Lyle A. McGeoch (Section 01)


The topic for 2008 is Advanced Data Structures. A major focus of the seminar will be on data structures for dynamic graph problems. Dynamic graphs can be used to represent, for example, telecommunication or transportation networks that can change over time. Properly designed data structures can permit queries about the graph (such as checking connectivity and finding shortest paths) to be handled efficiently, without requiring excessive computation when the graph changes. A second focus will be on data structures supporting rapid handling of queries in massive data sets. Requisite: Computer Science 21. Fall semester. Professor L. McGeoch.

An Informal Overview

This course is, first and foremost, an opportunity to study and discuss advanced approaches to data structure design.  The two main topics that we'll consider are data structures for dynamic graph algorithms and for path-finding in massive graphs.  These areas are interesting in their own right, and the ideas that we will explore can be applied to many other kinds of problems.

This course will be a seminar and will not be lecture-oriented.  Students will read numerous research papers during the semester, will make presentations, and will have the opportunity to shape the direction of the course as the semester proceeds.  There is no textbook to buy.

Grades will be based on class participation and papers and/or projects.  The class is small enough that I will be able to work individually with each of you to set goals as we go through the semester.

Enrolled students will be able to access a variety of materials on the e-reserves page.  I will use the announcements page (and perhaps e-mail) to let you know when new items are available.

Questions?  Let me know.