This page will provide general course information and access to various documents concerning CSC373. Weekly announcements for the course will be posted on this web site. The required text is "Algorithm Design" by Jon Kleinberg and Eva Tardos. The text "Introduction to Algorithms" (second edition) by Corman, Leiserson, Rivest and Stein is an additional good reference. Further course information is contained in the brief course syllabus that will also be handed out during the first lecture. Please note that this course has three lectures/week (MWF 10-11) and one tutorial/week (Thursday 2-3).
Students are encouraged to check the undergrad bulletin board which contains announcements such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines.
Please send any comments or questions to the instructor:
Term test 3 has been graded and can be picked up at my office. Once again (as in term test 2), the average grade is low due to the question on NP completeness. This material will be on the final exam so please make study this topic. I will be in most of Wed (not 11-12) and all day Thursday and Friday. Grades to date have been posted on CDF. If there is any garde not properly recorded please bring the relevant piece of work to me (either at my office or before the final exam).
I have provided solutions below for three of the questions on problem set 3. I have posted term test 3 and solutions for that test. There will no longer by any scheduled office hours. However, I am as always willing to meet by appointment or speak to you whenever I am free. I will be at the office until the final exam but my schedule is now different because of other obligations.
I have posted my lecture slides for lectures 1,3,4,5,7-20,22-32 (Yuli Ye gave lecture 2 and Justin Ward gave lecture 6 and Lecture 21 was devoted to answering question regarding problem set 2.) These slides serve only as a very rough outline of what I was discussing in class and should not be viewed as a substitute for the text or for attending lectures and tutorials. I have posted a latex presentation of the 1-1/e approximation for the randomized rounding of the Max-Sat IP/LP.
The text reading assignments thus far (in more or less the order we followed) : Chapter 1 (for motivation), Chapters 2 and 3 (just to recall some basic notation and concepts, and chapter 4 with the exception of sections 4.6 and 4.9. Chapter 6 with the exception of section 6.10. Chapter 7; 7.1-7.3, 7.5, 7.6, 7.10-7.12. Due to time contraints we will probably not be discussing circulations (sec 7.7) and the relevant applications in 7.8 and 7.9. But I still suggest looking at the definition of the circulation problem. In chapter 8, the relevant material is in sections 8.1-8.4, 8.8-8.10. Chapter 12; 12.4,12.5 and 12.6 was briefly discussed in tutorial. Chapter 11; 11.6 and 11.7. Chapter 13; 13.3, 13.4 and 13.9
The following grading scheme will be used for this course: 3 assignments (worth 5% each), 3 term tests (closely related to the assignments and worth 15% each) and a final 3 hour exam worth 40%. As will be discussed in class, every (sub) problem in any assignment or test will be worth some multiple of 5 points. You will receive 1/5 points for any (sub) problem for which you state "I do not know how to answer this question". You will receive .5/5 if you leave a question blank. If instead you submit irrelevant or erroneous answers you will lose the 1/5 points. That is, you will receive some credit for knowing what you don't know. You can also receive some additional credit for partial work that is clearly "on the right track". Even if the assignments are worth only 5% each, you are still obliged to submit your own work. In our first lecture, I will give a pragmatic definition for distiguishing between genuine learning together and plagarism. If you have any questions please see the instructor immediately! Any cases of plagarism will be reported to the Faculty.
IMPORTANT NOTE: I allow one page (double-sided) handwritten notes as an aid in all my tests and exams.
Slides from lectures will be posted here.
Problem Sets, Tests and Other Handouts will be posted here.
You may also find it helpful to look at the problem sets and other handouts for the most recent versions of CSC373 and CSC375 that I have taught. However, note that this year, CSC373 will also include some complexity theory (i.e. NP completeness).
I am providing links here to Professor Allan Jepson's lecture notes and demos used in his Fall 2010 CSC373 class. Many of these documents are password protected. I will provide the password during the first week of lectures.