Design and Analysis of Algorithms

Announcements

• November 20
  Exam 2 grades posted. Sudheer evaluated problems 1, 5 and 6. Yuheng evaluated rest of the problems. Max: 94, Average: 66, Min: 29. If you want to talk to sudheer regarding the problems he evaluated, you can meet him at 10:00 AM in pearson 145 on 30th November.
• November 19
  Assignment 6 is posted.
• November 11
  
  • Assignment 5 grades and solutions posted. Yuheng evaluated all 4 problems.
  • There will be no class on Friday (11/13). However, David will be available during the class period to answer any questions students may have about that evening's exam or anything else about the course.
• November 9
  Exam 2 from Fall 2008 is posted. This exam covers the same material as this semester's Exam 2.
• November 5
  
  • Here's a link to an excellent recent review article on the status of the P versus NP problem.
  • The room for exam 2 is now reserved. It will be 1352 Gilman, as originally announced.
• November 4
  Exam 2 will be held on Friday November 13 from 7 to 9 PM. The location is yet to be determined, although we will try to reserve room 1352 Gilman (the same one as for the first exam).
• October 30
  Assignment 4 grades and solutions posted. Sudheer evaluated all 4 problems. If your exam 1 or previous assignment points were changed during your meeting with TA's, please verify that the grade sheet reflects those changes.
• October 28
  Exam 2 (on NP-completeness) will be held on the week of November 9. The three possible dates are November 11, 12, or 13; the time would be 7-9 PM. Please email David as soon as possible if you have any concerns about any of these dates. The actual date and time of the exam will be announced by the middle of next week.
• October 25
  Assignment 5 is posted.
• October 22
  Yuheng's Office hours for next week October 29 will be cancelled.
• October 16
  Exam 1 grades posted. Sudheer graded problems 4, 5 and 6. Yuheng graded the other three problems. Following are some statistics for the test.
  • Min: 33
  • Max: 85
  • Average: 65.64
  • Std. Deviation: 12.38
• October 11
  Assignment 4 is posted.
• October 9
  
  • Sample solutions to Exam 1 are available by request. Please report any errors to David.
  • Homework 3 grades posted. You can collect your answer sheets in David's office between 11 AM and 11:50 AM today. You can also collect them during Yuheng Long's office hours in Pearson 145 today. Sudheer graded problems 1 and 5. Yuheng Long graded the other two problems.
  • There is no class today, but David will be in his office during the class period to answer questions about the course.
• October 7
  
  • Solutions posted for problems 1,5 and 6 of assignment 3
  • Solutions posted for problems 2,3 and 4 of assignment 3
  • Office hours of Yuheng Long for October 8 have been moved to October 9 from 3:00 to 4:00 pm. Notice that it is effective for this week only.
• October 6
  A corrected version of the slides on the fundamental theorem of linear programming, weak duality, and strong duality has been posted. Please contact David if you find any errors in these notes.
• October 1
  Exam 1 will be held on Friday October 9 from 7 to 9 PM in room 1352 Gilman. Note that this is not our regular classroom (although it is nearby), since we need extra space to allow for alternate seating.
• September 28
  In problem 5b of assignment 3, you may assume that the output of the linear inequality feasibility problem includes a setting of the variables that simultaneously satisfies each of the inequalities, if such a setting exists.
• September 27
  
  • Solutions posted for problems 1, 2 and 5 of Assignment 2.
  • Some students are unable to take exam 1 on either October 7 or 8. One remaining possibility is Friday October 9 from 7 to 9 PM. Please contact David if this time does not work for you. In any event, we will have a definite schedule for the exam by the end of this week.
  • The class notes posted on 9/24 have been updated with the addition of some slides on the geometry of linear programming.
  • Notes on the fundamental theorem of linear programming, weak duality, and strong duality have been posted.
• September 25
  
  • Solutions posted for problems 3,4 and 6 of Assignment 2.
  • Assignment 2 grades posted. Problems 1 and 2 evaluated by Yuheng Long. Problems 3 and 6 evaluated by Sudheer.
• September 24
  Some class notes on linear programming are posted.
• September 23
  Office hours of Yuheng Long for September 24 have been changed. His office hour for September 24 is 8:40 to 9:40 am. Notice that it is effective for this week only.
• September 23
  
  • Some students have mentioned that they wil be unavailable at the proposed exam date. An alternative is to hold the test on Wednesday October 7 from 7 to 9 PM. Please contact David if this time does not work for you.
  • Exam 1 from Fall 2008 is posted. This exam covers the same material as this semester's Exam 1.
• September 22
  Exam 1 (on network flows and linear programing) is tentatively scheduled for 7-9 PM on Thursday October 8. Note that this is subject to change depending on students' constraints and room availability. Please email David if you have any concerns about this date and time.
• September 21
  Assignment 3 is posted.
• September 20
  Our main references for linear programming will be the following.
  • Chapter 29 of Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.
  • Chapter 7 of Algorithms, by Dasgupta, Papadimitriou, and Vazirani.
  Several other excellent references for linear (and integer) programming are available. Among these, the following two are especially accessible:
  • V. Chvátal. Linear Programming. W.H. Freeman, 1983.
  • R. Vanderbei. Linear Programming: Foundations and Extensions (3rd ed.). Springer, 2008.
• September 16
  As mentioned in class, there is an error in the statement of problem 1b of Assignment 2. The question should refer to the values of the flows, not the flows themselves. A corrected version has been posted.
• September 11
  
  • Office hours of Yuheng Long and Sudheer Vakati changed. Changed timings posted on the course homepage.
  • Solutions to Assignment 1 posted. Solutions are password protected. David will give you the username and password in the class today.
  • Assignment 1 grades posted. Problems 1 and 2 evaluated by Yuheng Long. Problems 4 and 5 evaluated by Sudheer.
• September 7
  Assignment 2 is posted.
• September 1
  Yuheng Long's office hours this semester will be Thursdays, from 9:30 to 11:30 a.m., in 145 Pearson.
• August 24
  
  • Welcome to CS 511! Please consult this page regularly for updates on this course, including homework, solutions, exam information, as well as supplementary reading material.
  • Assignment 1 is posted.