CS473G - Graduate Algorithms - Spring 2007

Tue Thu 11:00-12:15, 106 Lincoln Hall

Instructor:
Jeff Erickson (jeffe+473@cs.uiuc.edu), 3304 Siebel Center
Tentative office hours: Monday 11-12, Wednesday 3-4
Administrative assistant: Elaine Wilson, 3229 Siebel Center

Teaching assistant:
Kevin Milans (milans@uiuc.edu)
Office hours: Monday 4-5 and Thursday 4-5

All office hours will be held in the open area outside 3303 Siebel Center.

— Administrivia — Course policies — Lectures — Grades (via Compass) — Old notes, homeworks, and exams —

Announcements

May 3: The Final exam is this Saturday, May5, from 1:30 to 4:30 in 106 Lincoln. The final will cover prerequisite material, NP-completeness, recursion and dynamic programming, greedy algorithms, approximation algorithms, randomized algorithms, and flows/cuts/matchings. There will be no questions on matroids or linear programming. There will be slightly more emphasis on randomized algorithms and flows/cuts/matchings, which weren't covered on the two midterms. The exam will have seven questions; each student's lowest score will be dropped. Each student may bring two double-sided 8.5"×11" `cheat sheets'. Lots of old exams are available; you can also find lots of practice problems in this semester's lecture notes and head-banging sessions.

April 28:
Homework 5 solutions are now available.

April 10:
Midterm 2 has been graded, and grades have been entered into Compass. Here is a complete list of all the scores (out of 40 points):
12 14 17.5 18 19.5 20.5 20.5 21 21.5 22 22 22.5 27 29 29 29.5 29.5 33 34.5 35 35 35 36 37 37 38.5 40
You can pick up your exam at Jeff's or Kevin's office hours.

April 5:
Homework 5 is due Thursday, April 19.
April 4:
Solutions for Midterm 2 are available.
April 3:
Today's headbanging session is also canceled due to Midterm 2.
March 30: April 2:
Homework 4 solutions are available.
March 28:
  • Midterm 2 will be held Tuesday, April 3, from 7:00pm to 9:00pm in 114 Transportation. There will be no regular lecture on Tuesday morning. The exam will emphasize dynamic programming, greedy algorithms (but not matroids), approximation algorithms, and perhaps one easy question on randomized algorithms, but earlier course material is also fair game. Each student may bring one double-sided 8.5"×11" `cheat sheet'. Lots of old exams are available; you can also find lots of practice problems in this semester's lecture notes.
  • Several updated lecture notes on randomized algorithms are available.
March 15:
Homework 3 solutions are now available.
March 12:
Homework 4 is due March 29 (Thursday after spring break).
February 27:
February 27:
  • Midterm 1 has been graded. Grades will be entered into Compass later this afternoon. Here is a complete list of all the scores (out of 40 points):
    7 8 8.5 10.5 11 11.5 13.5 15 15 16.5 16.5 17 20 20.5 20.5 21 21 21.5 23 24.5 25 25.5 26.5 30 32 33 37 39 40
    You can pick up your exam at Jeff's or Kevin's office hours.
  • Starting next Tuesday, March 6, we will hold problem-solving (aka "head banging") sessions every Tuesday from 5pm to 6pm in 3405 Siebel Center.
February 23:
February 20:
Midterm 1 will be held Thursday, February 22, from 7:00pm to 8:30 pm in 114 Transportation. There will be no regular lecture on Thursday morning. The exam will cover prerequisite material, NP-hardness, recursion, and dynamic programming. Each student may bring one double-sided 8.5"×11" `cheat sheet' with anything written, printed, xeroxed, engraved, or whatever. Otherwise, the exam will be closed-everything; no electronic devices or microscopes allowed. The exam will have five questions, the lowest of which will be dropped. Lots of old exams are available; you can also find lots of practice problems in this semester's lecture notes.
February 12:
Class is cancelled tomorrow (February 13).
Jeff is sick and we're expecting six twelve inches of snow. Please pass this message to your fellow students!
February 9:
Homework 1 solutions are now available.
February 6:
  • Homework 2 is now available. Solutions are due Tuesday, February 20. As Jeff mentioned in class, one of the problems requires FFTs to get the requested time bound.
  • Elaine Wilson's office number is 3229 Siebel Center, not 3329. Sorry for the confusion! You can submit your HW1 solutions there any time tomorrow (February 7).
February 5:
Homework 0 solutions are now available.
January 31:
A brief introduction to complex variables is now available. Please read it before Thursday's lecture on Fast Fourier Transforms. It is particularly important to understand exercises 3 and 5.
January 23:
  • Homework 1 is now available: (pdf, source). Solutions are due Feburary 6 in 3329 Siebel Center. Groups of up to three students can submit a single common solution.
  • Jeff will be out of town January 26 through February 2. Kevin will give the lectures that week.
January 22:
  • A few students have noticed that we gave two different deadlines for HW0. So as not to penalize students for our mistake, we will honor the later deadline. Homework Zero is due Tuesday, January 30, at the beginning of class. Sorry for the confusion! Homework 1 will still be released tomorrow (January 23) and will be due in two weeks (February 6).
  • Starting on Thursday, January 24 Tuesday, Jaunary 23, lectures will be held in 106 Lincoln Hall. Sorry the new room is so far across campus; that's all that Facilities could give us. The registration cap for the class has been lifted, so everyone on the waiting list should now be able to register. The online registration deadline is Monday, January 29.
January 17:
My office hours on Thursday, January 18 are rescheduled for 2-3 PM; regular office hours are still scheduled as above. --Kevin
January 15:
  • Hello and welcome! The course web site is still under heavy construction.

  • Homeork Zero is due in class at 11:00am Tuesday, January 23 January 30. (This will be the only homework due in class.) LaTeX source code for the homework is available, if you'd like a template for your solutions. You may also find Jeff's notes on solving recurrences helpful.

  • If you are interested in registering for 473G, even though the class is full, please come to class during the first week to add your name to the waiting list. Students who register late are still expected to turn in Homework Zero.

Administrivia

Newsgroup: class.cs473 on the news server news.cs.uiuc.edu
Please read the newsgroup at least once a day. You must sign up for access if you have not already done so.

Audience:
This section of CS 473 is intended for graduate students in computer science and related areas, including students in the 5-year CS master's program. This is the only section of 473 that will satisfy graduate core requirements in computer science. Mathematically/algorithmically mature undergraduates are also welcome to register, but you need my permission first.

Prerequisites:
Students are assumed to have an undergraduate degree in computer science or a related field, such as electrical/computer engineering or mathematics. Students are also assumed to have mastered the material taught in CS 173, CS 225, and CS 273 (discrete mathematics, basic algorithms and data structures). Please note that "mastery" is not the same as "exposure" or even "a good grade". Hence, Homework Zero. Programming experience is helpful; a strong mathematics background is even more helpful.

Coursework:
Grades will be based on 6-8 homeworks (30% total, lowest score dropped), two midterms (20% each) and a final exam (20%). There will be many opportunities for extra credit, which will be applied after the curve.

Credit:
This course is offered in two sections, one worth 3 hours of credit, the other worth 4 hours of credit. There is absolutely no difference between these sections. The split is entirely an artifact of instutional inertia. Students in both sections will meet at the same time, will cover the same course material, will be given the same homework and exams, and will be graded on the same curve. You might as well sign up for 4 hours of credit.

Reading material:
There is no required textbook. Instead, Lecture notes will be posted to the course web site as the semester progresses. For almost every topic we will cover, both Jeff Erickson and Sariel Har-Peled have lecture notes online from previous semesters. For students who prefer an actual dead-tree book as an additional reference, we recommend any of the following:
  • Algorithm Design by Jon Kleinberg and Éva Tardos (Addison-Wesley, 2005). This is the 'official' recommended textbook; copies are available in all campus bookstores.
  • Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 2006).
  • Introduction to Algorithms by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press/McGraw-Hill, 2001). The first edition is also fine.
If there is sufficient demand, hard copies of Jeff's lecture notes might be made available at a local copy shop.

Course materials: