Computer Science Department

Stay tuned to this section of the web page for assignments and announcements. Check it before coming to class for notices, such as class cancellations, homework extensions, etc.

• Solutions to final exam problems
• 5/13: Review session 12:30-1:45 in USC 310B.
• Exercises on transitive orientation
• Homework 4 (modified 6/4 to give more hints)
• Wednesday 5/14: Final exam, 3:40-5:40 in the usual room.
• Tuesday 5/6: Derive the modular decomposition on your own (continued).
• Thursday 5/1: Derive the modular decomposition on your own. Handout.. For solutions to these questions click here.
• Tuesday 4/29: Transitive orientation and perfection of comparability graphs.
• Midterm 2 solutions
• Thursday 4/24: Midterm2.
• Tuesday 4/22: More on partially ordered sets and comparability graphs; review for second midterm.
• Thursday 4/17: Discussion of Homework 3 problems
• Homework 3, due 4/17
• Nissa Ossheim's proof that chordal graphs are perfect, using the strong perfect graph theorem.
• Tuesday 4/15: Readings: an introductory reference on partially ordered sets from K. P. Bogart, Introductory Combinatorics, Pitman, 1986; two sections handed out 4/10 from a chapter on comparability graphs in Golumbic's text.
• Thursday 4/10: Continue on triangulated graph.
• Tuesday 4/8: Handout on triangulated graphs (from M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.) Explanation of terminology and study guide.
• Thursday 4/3: Introduction to perfect graphs and coloring algorithms on interval graphs and their complements.
• Tuesday 4/1: Finish on Tarjan's bound for max flow on arbitrary graphs, using linking/cutting trees.
• Tuesday 3/25 and Thursday 3/27: Ben Joeris covered Dinic's algorithm and special cases of flow networks. (I was out of town due to research obligations.)
• Tuesday 3/18 and Thursday 3/20: Spring Break.
• Thursday 3/13: Midterm 1. Click here for solutions.
• Tuesday 3/11: Homework 2 solutions and review for midterm 1.
• Finished Thursday 3/6: Network flow and Edmonds-Karp (Chapter 26 through 26.3).
• Finished Tuesday, 3/4: dynamic (linking-and-cutting) trees. For 3/6, read Cormen, Chapter 26 through Section 26.3 (network flow).
• We will have the first midterm on Thursday, March 13. Focus your attention not just on the data structures and algorithms that we have studied, but the principles of design and analysis that they illustrate.
• Homework 2, due Tuesday, March 11
• Completed Thursday, 2/21: Sections 6.1-6.3 of the handout from 2/12 on the point-location problem. (Source: M. de Berg, et. al., Computation Geometry: Algorithms and Applications, Springer, 1997.)
• Completed Tuesday 2/14: Review of Homework 1 solutions; review of randomized search trees, introduction to splay trees, Section 4.3 of Tarjan.
• Homework 1, due 2/14
• Completed Tuesday 2/12: Section 13.4 of handout on randomized search trees (expected number of rotations for deletion).
• Completed Thursday 2/7: 13.1-13.3 of handout on randomized search trees (expected depth of a node). (Source: D.C. Kozen, The Design and Analysis of Algorithms, Springer, 1992.)

Instructor: Ross McConnell

• E-mail:
• Phone: (970) 491-7524     Fax: (970) 491-2466
• Office: University Services Center (USC) 240
• Office Hours: to be determined

Textbooks:

• The required texts for this course are Data Structures and Network Algorithms by R. E. Tarjan, 1980, and Introduction to Algorithms by T. H. Cormen et. al., 2001. There will be handouts from a variety of other sources.

Prerequisites:

• C.S. 520, or permission of the instructor.

Many people think of data structures as an undergraduate topic. However, there are many beautiful data structures that are skipped in undergraduate courses, because few undergraduate students have the background to understand them.

Some of these data structures consist of a large number of nodes that perform an elaborate ballet, constantly establishing and dropping connections between each other as the structure is queried. The behavior of some of them more closely resembles that of a living brain than that of a traditional data structure, and they give rise to the fastest algorithms known for many fundamental problems in computer science.

The course covers a variety of examples, and gives case studies in their application to real-world problems. Of greatest significance is not so much the particular data structures that we study, but the very general principles of algorithm design that they illustrate.

An official prerequisite is a graduate algorithms course, such as our CS 520. However, of greater interest is reasonable comfort with the assumed background and skills. This includes the math background, which is outlined in Chapters 1 through 4 of the Cormen book, and experience at how to apply it to algorithm design, which is illustrated in many subsequent chapters. In recent weeks, I have also given waivers to students who have have picked this up in non-traditional ways. Make an appointment with me during the first week if you have questions about your background or waivers.

Of equal importance is an esthetic appreciation of the subject, which generates many problems and puzzles that look hard at first, but that are astonishingly easy once you hit on the right insight. Much of the course is about tricks for coming up with these insights.

• Preliminaries: Tarjan, Chapter 1; Cormen, Chapter 3; Review Cormen chapters 1, 2 and sections 4.2, 4.3.
• Priority queues.
  • Cormen, Chapter 19 (binomial heaps)
  • Tarjan, Chapter 3 (leftist heaps)
  • Handout from 2/5 on treaps, from D. Kozen, The Design and Analysis of Algorithms
  • Tarjan, Chapter 4 (splay trees)
  • Handout from 2/12 on the point-location problem from deBerg, et. al. Computational Geometry
  • Dynamic (linking-and-cutting) trees: Chapter 5 in Tarjan.
  • More on network flow: Cormen, Chapter 26 through Section 26.3; Chapter 8 in Tarjan.
  • Perfect graphs and chordal graphs: handout, ``Triangulated Graphs'' from M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs
  • Handout: sections 1 and 2 of ``Comparability Graphs,'' from Golumbic.

Homeworks	25 %.
Midterm 1	25 %
Midterm 2	25 %
Final	25 %

Homeworks are not accepted late, since I often hand out or discuss solutions when they are due. To compensate for this, I will drop your lowest homework grade as a "freebie" for when you have an unexpected conflict, illness, or emergency.

Much of the class is built around discussion. Please attend class regularly and to be prepared to discuss the readings. I will hand out written exercises to bolster your skills and enhance your understanding of the readings. Start on them early so that we can discuss them in class.