Announcements:
- December 13: The grades for Homework 5 have been posted.
- December 12:
The final exam is tomorrow from 7:00pm to 10:00pm in DCL 1310 (the
regular lecture hall. You can bring TWO US-letter double-sided
cheat sheets; otherwise, the exam is closed-everything, as usual.
There are seven questions, of which your lowest score is dropped. The
exam is cumulative, with roughly uniform coverage over the entire
course. The questions will be about as hard as the midterms.
The exam covers prerequisite material, course material for which lecture notes are available, and nothing else. In particular, the exam will not include questions about sparse dynamic programming, Lempel-Ziv and Burrows-Wheeler compression, randomizeed incremenetal Voronoi diagrams, max-weight matchings, maximum matchings in general graphs, or linear programming algorithms (see below).
- December 8:
- Homework 6 solutions are available. Some of these are very rough; caveat lector!
- Lecture
notes on the simplex algorithm
are available.
(I'll add some pictures later tonight and repost them.)Since I didn't do that, the final exam will not cover LP algorithms.
- December 5:
- Homework 6 is available. As promised, these are only practice problems; do not turn in solutions.
- Lecture notes on linear programming are aavailable. There will be one more set of notes for Tuesday's lecture.
- Midterm 2 grades are now posted. Sorry for the delay.
- December 1: Homework 5 solutions are available.
- November 29: Homework 3 and Homework 4 grades are now posted.
- November 28:
- Welcome back!
- Lecture notes on max-flow algorithms are available. There will be no lecture notes on weighted matchings and matchings in general graphs, but curious readers can find Sariel's notes here and here.
- Homework 6 will be released on Thursday and will not be graded. It will contain practice problems, mostly on linear programming, to help prepare for the final exam.
- I will be distributing course evaluation ("ICES") forms near the end of class on Tuesday, December 6. This anonymous feedback is extremely important to me, to future 473 students, and to the department as a whole. The department is instituting several major policy changes to help improve the quality of our teaching; your feedback is absolutely crucial to this effort. All on-campus students, including students who have already dropped the class are strongly encouraged to fill out these forms, especially the first two multiple-choice questions (on the front) and the narrative questions (on the back). Bring a #2 pencil; the scanners will reject any forms filled out in ink.
- I also want feedback from the I2CS students. In the past, OIR has provided an electronic feedback form equivalent to ICES, but I don't know if that option is available this semester. If all else fails, you can aways use ratemyprofessor or myprofessorsucks.
- November 14:
- Lecture notes on graph representations, minimum spanning trees, single-source and all-pairs shortest paths, and the max-flow/min-cut theorem are available.
- You can pick up your graded Midterm 2 from Jeff's office. The mean was 24.02, with a standard deviation of 7.7.
- November 8: Homework 5 is due Thursday, November 17.
- November 2: Solutions for Midterm 2 are available.
- October 30:
Midterm 2 be held on Tuesday, November 1, from 7:00pm to 8:30pm, in
114
Transportation.
- Like the previous midterm, you can bring a one-page (double-sided) cheat sheet, a pen, your brain, and your sense of humor, but nothing else.
- Most of the exam will focus on approximation algorithms and randomized algorithms, but there will be at least one question on earlier material. [Hint: Which question did most people leave blank on Midterm 1?]
- You are not responsible for any material covered in lectures for which there are no notes.
- Don't forget the I Don't Know rule!
- October 29: Homework 3 solutions, Homework 4 solutions, and hashing notes are available.
- October 27: Lecture notes on Chernoff bounds and randomized min-cut are available.
- October 19: Lecture notes on nuts and bolts and treaps and skip lists are available.
- October 15: Homework 2 grades are now available.
- October 14:
- Homework 4 is due Thursday, October 27.
- For this and all future homework, we are making a couple of policy changes to encourage collaboration between on-campus and off-campus students. Homework teams that include at least one I2CS student and at least one on-campus student automatically get 3 points of extra credit; mixed teams can contain up to four members instead of the usual three. On-campus students are strongly encouraged to include I2CS students in their study groups—and vice versa—via the course newsgroup, email, instant messaging, or phone.
- Today is the last day to drop the course via Banner.
- October 10: Lecture notes on approximation algorithms are (finally!) available.
- October 4:
- Homework 0 and homework 1 grades are now posted. If you did not choose an alias, your entry will contain a blank alias. If that is the case, consider choosing one in order to view your grades online.
- Midterm 1 grades are now posted.
- Midterm 1 has been graded (except for some I2CS students). The mean score was 24.64 (out of 40), with a standard deviation of 7.1. You can pick up your graded midterms in the TA office during TA office hours.
- Jeff will be out of town tomorrow, so his Wednesday office hours are cancelled. He will hold extra office hours next Monday from 2 to 3 instead.
- October 3: Homework 3 is due October 18 (not October 13 as originally planned).
- September 30: Midterm 1 questions and solutions are available.
- September 26: Homework 2 solutions are available.
- September 24: Homework 1 solutions are available.
- September 22: Midterm 1 will be held Tuesday, September 27, from 7:00 to 8:30, in rooms 135 and 153 of the Mechanical Engineering Building. The exam is closed-book, closed-notes, and closed-web; aside from your cheat cheet (one double-sided 8.5"×11" sheet of paper), the only thing you should bring is something to write with. There will be no lecture on Tuesday.
- September 21:
- Lecture notes for dynamic programming (except for sparse LCS) and greedy algorithms are available.
- Two clarifications for Homework 2:
- The time bound we asked for in Problem 6(a) is unreasonable; ignore it. Just describe the fastest recursive algorithm you can.
- In problem 3, you can assume that George has positive weirdness. For extra credit, solve the problem without that assumption.
- September 14:
- Homework 2 is due Thursday, September 22 at midnight. Start early!
- More information about
Nadiria and its Dream Dollars
- September 12:
- Recursion lecture notes (now with the .pdf suffix!)
- LaTeX source for Homework 0 solutions is available.
- September 6: Homework 0 solutions are available.
- September 2: Homework 1 is due Tuesday, September 13 at midnight (11:59:59pm CDT).
- September 1:
- Notes for the first three lectures are available.
- Homework 1 and solutions for homework 0 will be posted tomorrow at the latest.
- August 26:
- The first lecture video is now available.
- Missing source files for HW0: handout.sty, martian.eps
- How to solve recurrences! [pdf]
- Reminder: Jeff will be out of town all next week. Erin is giving the next two lectures.
- August 25: Homework Zero is due Thursday, September 1 at 12:30 CDT. Here are the LaTeX source files: hw0.tex, jeffe.sty, dieroll.eps, rollmazes.eps. More information about rolling die mazes (problem 3) can be found here and here.