CSE 542. Advanced Data Structures and Algorithms

Spring 2013

Course description (from the catalog)

This course is concerned with the design and analysis of efficient algorithms, focusing principally on algorithms for combinatorial optimization problems. A key element of the course is the role of data structures in algorithm design and the use of amortized complexity analysis to determine how data structures affect performance. The course is organized around a set of core problems and algorithms, including classical network optimization algorithms, as well as newer and more efficient algorithms. This core is supplemented by algorithms selected from the recent technical literature. Prerequisites: CSE 241. Credit: 3 units.

Administrivia

Class Preparation. For each class, there is a reading assignment and a set of review questions that address a portion of the material covered in that class. You are expected to do the reading assignments before coming to class and to turn in your answers to the review questions at the start of class, when one person will be asked to explain their answer to each question. Review questions will be checked to verify that you have made a reasonable effort to understand the material, but will not be graded in detail, or returned.

Labs. The class includes a series of laboratory exercises designed to help you get a deeper understanding of the various data structures and algorithms we will be covering. The labs require some programming, but the amount of new code you will need to write for each assignment is usually fairly small (1-4 pages). Implementations of many of the data structures and algorithms we'll be using will be provided to you, through a private subversion repository. The provided code is written in C++ and has been compiled and tested with the Gnu C++ compiler (g++) under MacOS and Linux. You can also expect them to work under cygwin on a Windows PC, although you may have to make some minor adjustments to get them to compile. You will typically be asked to implement at least some portion of an algorithm or data structure, and you will be asked to measure some aspect of its performance. There will also typically be some analysis, comparing the measured performance to the worst-case analytical bounds. Specific assignments can be found in the detailed class schedule below.

Quizes. Every second Tuesday, there will be a short quiz. The first will be on January 22. Each quiz will address material covered since the previous quiz or exam. Quizes will be given at the beginning of class, so don't be late. There will be no makeup quizes, but your low quiz score will be dropped from your course grade.

Examinations. There will be three exams given during the semster. The first two will be in class on February 14 and March 28. The final exam will be May 8, 3:30-5:30. THERE WILL BE NO ALTERNATE TIMES FOR ANY OF THE EXAMS - IT IS UP TO YOU TO ARRANGE YOUR OTHER ACTIVITIES TO AVOID CONFLICTS.

Lecture Notes. Bound, paper copies of the lecture notes are available in the bookstore. These are printed with space provided for adding your own notes. You are strongly encouraged to purchase a copy, and use it for taking notes during class. Links to online copies are also provided in the detailed schedule below.

Reading Assignments. Reading assignments in the two text books (Tarjan and Cormen, et. al) appear in the detailed course schedule below. It is strongly recommended that you read over this material before class each day, then study it in more detail after class. The Tarjan book is not a typical text, and requires careful attention to detail. Don't let its conciseness fool you. He packs a great deal of meaning into every sentence and you need to think hard about what he is saying, in order to really understand it. The CLRS text is an easier read, but covers only a portion of the material in the course. In addition to these texts, there are notes that explain the material covered in the first few slides of each lecture. This is the material addressed by the review questions.

Practice Problems. Each section of the lecture notes concludes with a set of exercises. The most important single thing you can do to master the material in this course is to work through these problems. Solutions are provided for most questions, but you should make a serious effort to solve them on your own, rather than just look at the solutions.

Working with Others Students. You are encouraged to work with other students in study groups, so that you can help each other master the course material. However, all work that is to be handed in must be done individually. This includes answers to review questions and labs. You may discuss general approaches with your fellow students, and the TAs will provide hints and general guidance. However, you are expected to turn in your own work and only your own work. You should not share your solutions with other students. Sharing of source code, measurement results or any other written material is expressly forbidden. Any group of students found to have collaborated inappropriately on an assignment will have the full value of the assignment subtracted from the grades of all students involved. Repeat offenses will not be treated so leniently.

Late Policy. Assignments are due in class on the assigned date. Late assignments will not be accepted, not even for partial credit. No exceptions. If you are not going to be in class, you may turn in your assignment early by giving it to me in person, or by putting it in my box in the CSE office after having it initialed by one of the CSE department staff, with the date and time. Please use this procedure only in exceptional circumstances.

Expectations. This course covers a great deal of material and you will need to devote substantial time and effort to mastering it. You should plan to spend an average of eight to twelve hours per week outside of class, preparing for class, doing the assigned readings, working exercises and doing the labs. Don't expect to master the material simply by sitting in class and listening to the lecture.

On-line Communication. Most information about the course can be obtained electronically. In addition to this web site, there is a discussion group setup on Piazza. All registered students should receive an invitation email to join the group. If you have not received such an email, let me know and I will make sure you do. I strongly recommend that you use the discussion group to post questions you may have about lecture material, exercises and labs. The TAs and I will use it to answer questions and to provide guidance and occasional hints. It will also be used to post clarifications and corrections and to make general announcements, so you should monitor it regularly. You are also encouraged to respond to posts from other students. The more you all use the group, the more useful it will be for everyone.

Course Lectures and Assignments

The course material is organized into three parts. The first part will provide an introduction to each of the main problems we will be studying over the course of the semester. In the second part and third parts, we will study additional data structures and algorithms, going into selected topics in greater depth. In the reading assignments listed below, JSTx stands for my online notes, T stands for the Tarjan text, CLRS2 stands for the second edition of Cormen Leiserson, Rivest and Stein and CLRS3 stands for the third edition of CLRS. Readings from CLRS are used for material that is not covered in Tarjan. I have not had the bookstore order CLRS for this class, as I expect most of you already own a copy (if not, you should). Much of the material covered by Tarjan is also covered in CLRS. Some of you may find it useful to read this material in addition to the assigned readings in Tarjan.

First Half

Date Lecture Notes Reading Review Questions Other
1/15 Introduction to CSE 542 T 1-19 - -
1/17 Minimum Spanning Trees and d-Heaps JST2, T 75-77, 33-38 .doc, .pdf -
1/22 Shortest Paths JST3, T 85-91 .doc, .pdf Quiz 1
1/24 Fibonacci Heaps JST4, CLRS2 476-495, CLRS3 505-526 .doc, .pdf -
1/29 Maximum Flows in Graphs JST5, T 97-101 .doc, .pdf Lab 1, Solution,
1/31 Minimum Cost Flows JST6, T 108-111 .doc, .pdf -
2/5 All Pairs Shortest Paths and Faster Min Cost Flows JST7, T 94-95 .doc, .pdf Quiz 2
2/7 Matchings in Bipartite Graphs JST8, T 113-115 .doc, .pdf -
2/12 Review session - - -

Second Half

Date Lecture Notes Reading Review Questions Other
2/19 Kruskal's MST Algorithm and the Partition Data Structure JST9, T 74-75, 23-24, JST10 1-5 .doc, .pdf Lab 2, Solution,
2/21 Analysis of Partition Data Structure JST10 6-13 .doc, .pdf -
2/26 Applications of Matching JST13 .doc, .pdf Quiz 3
2/28 Round Robin MST Algorithm and Leftist Heaps JST11, T 77-82, 38-43 .doc, .pdf -
3/5 Edmonds Maximum Matching Algorithm JST12, T 115-123 .doc, .pdf Lab 3, Solution,
3/7 Linear Programming and Network Optimization JST14, CLRS2 770-790, 804-811 .doc, .pdf -
3/19 Weighted Matching in General Graphs - Part 1 JST15 .doc, .pdf Quiz 4
3/21 Weighted Matching in General Graphs - Part 2 JST16 .doc, .pdf -
3/26 Review Session, Practice Questions - - -

Third Half

Date Lecture Notes Reading Review Questions Other
4/2 Dinic's Max Flow Algorithm JST17,T 102-104 .doc, .pdf Lab 4, Solution,
4/4 Preflow Push Method for Max Flows JST18, CLRS2 669-691, CLRS3 736-759 .doc, .pdf -
4/9 Dinic's Algorithm with Dynamic Trees JST19, T 107-108 .doc, .pdf Quiz 5
4/11 Binary Search Trees JST20, T 45-53 .doc, .pdf -
4/16 Self-Adjusting Binary Search Trees JST21, T 53-56 .doc, .pdf
4/18 Dynamic Trees and Path Sets JST22, T 59-64 .doc, .pdf -
4/23 Fast Implementation of Dynamic Trees JST23, T 64-70 .doc, .pdf Quiz 6
4/25 Review Session - - -
5/2 - - - Lab 5, Solution,

Corrections to Tarjan book