Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein;
Selected papers.
.
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.
.
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, studying the book, working exercises and doing the experimental studies. Don't expect to learn the material simply by sitting in class and listening to the lecture.
Recorded Lectures. I plan to use Tuesdays to answer questions and have the class work through problems together. To make time for these activities, I will be recording the lectures for these days and making them available on the web site. You are expected to view the recorded lectures BEFORE CLASS each Tuesday and come with questions. You may want to get together with a few classmates and watch the lecture together, so that as questions occur to you, you can pause the recording and talk about it. The recordings are provided as PowerPoint slide shows. If you don't have Power Point on your computer, you can download a free viewer for Power Point slideshows from the Microsoft web site. Links to recorded lectures can be found in the table towards the bottom of this page (links are labeled "rec").
Quizes. Every second Tuesday, there will be a short quiz covering material from the previous two week period. In particular, quizes may include a question from that day's recorded lecture. The first quiz will be on 1/26.
Experimental Studies. You will be asked to do six experimental studies over the course of the semester. These require some programming, but the amount of new code you will need to write for each assignment is typically fairly small (1-4 pages). Implementations of most of the data structures and algorithms we'll be using are available on the web site for your use. These implementations are in C++ and have been compiled and tested with the Gnu C++ compiler (g++) in the cygwin environment under Windows XP. You can also expect them to work in a Unix or Linux environment, although you may have to make some minor adjustments to get them to compile.
Late Policy. Assignments are due in class on the assigned date. Solutions will be posted on the web site that evening. 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 homework 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.
Academic Integrity Policy. Experimental studies must be done independently of other students. First violations of this policy will result in negative credit of 100% for the assignment, for ALL students involved. This does not mean that you may not study together. In fact, group study directed to helping each other gain a better understanding of the material is encouraged and you should feel free to work together on the exercises. However, all students must work independently on the experimental studies and all must turn in their own work, and only their own work.
On-line Communication. Most information about the course can be obtained electronically. In addition to this web site, there is a google group which you can access using a web browser at the url (www.groups.google.com/group/cse-542?hl=en&lnk=gcimv). I strongly recommend that you use the news group to post questions you may have about lecture material, exercises and experimental studies. 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. You will find a first assignment on the group. It is due by noon on Sunday, January 24, so don't delay.
Course Notes. You will note that the lecture notes for the course are posted in the left-hand margin. Feel print them out and use them for taking notes.
Examinations. There will be two in-class exams given during the semester. The dates for these are 2/18 and 4/1. Please reserve these dates on your calendar, now! There will also be a final exam which will be given on May 12 from 3:30 to 5:30.
| Date | Lecture Notes | Reading Assignment |
| 1-19-2010 | Introduction to CSE 542 (exercises) | T 1-19, CLRS2 525-552, CLRS3 587-615 |
| 1-21-2010 | Minimum Spanning Trees and d-Heaps (ex) | T 75-77, 33-38, CLRS2 561-567, 570-573, 127-135, CLRS3 624-631, 634-636, 151-159 |
| 1-26-2010 | Shortest Paths (rec, ex) | T 85-91, CLRS2 580-599, CLRS3 643-663 |
| 1-28-2010 | More Shortest Paths (ex) | T 91-95, CLRS2 629-640, 693-705 |
| 2-2-2010 | Maximum Flows in Graphs (rec, ex) | T 97-101, CLRS2 643-663, CLRS3 708-731 |
| 2-4-2010 | Maximum Flows - Augmenting by Capacity (ex) | T 97-101, CLRS2 643-663, 708-731 |
| 2-9-2010 | Minimum Cost Flows (rec, ex) | T 108-111 |
| 2-11-2010 | Matchings in Bipartite Graphs (ex) | T 113-115, CLRS2 664-668, CLRS3 732-736 |
| Date | Lecture Notes | Reading Assignment |
| 2-23-2010 | Kruskal's MST Algorithm and the Partition Data Structure (rec, ex) | T 74-75, 23-24, CLRS2 567-570, 498-509, CLRS3 631-633, 561-573 |
| 2-25-2010 | Analysis of Partition Data Structure (ex) | Maintaining a Partition |
| 3-2-2010 | Computing Nearest Common Ancestors (rec, ex) | Applications of Path Compression, pages 690-695,697-698 |
| 3-4-2010 | Round Robin MST Algorithm and Leftist Heaps (ex) | T 77-82, 38-43 |
| 3-16-2010 | Fibonacci Heaps (rec, ex) | CLRS2 476-495, CLRS3 505-526 |
| 3-18-2010 | Dinic's Max Flow Algorithm (ex) | T 102-104 |
| 3-23-2010 | Dinic's Algorithm with Dynamic Trees (rec, ex) | T 107-108 |
| 3-25-2010 | Open | - |
| Date | Lecture Notes | Reading Assignment |
| 4-6-2010 | Binary Search Trees (ex) | T 45-51, CLRS2 253-264, CLRS3 286-298 |
| 4-8-2010 | Self- Adjusting Search Trees (ex) | 52-56 |
| 4-13-2010 | Dynamic Trees and Path Sets (ex) | T 59-64 |
| 4-15-2010 | Fast Implementation of Dynamic Trees (ex) | T 64-70 |
| 4-20-2010 | Open | - |
| 4-22-2010 | Preflow Push Method for Max Flows (ex) | TBA |
| 4-27-2010 | Scaling Algorithm for Min Cost Flows (ex) | TBA |
| 4-29-2010 | Edmonds Maximum Matching Algorithm (ex) | T 115-123 |
