CSC373 Home Page (Fall 2005)

Announcements for week of December 19. I am in my office Monday, Deecember 19 until at least 2PM and I will also be in Tuesday AM. Graded assignments (including problem set 4) and term tests can be picked up at my office. Regrading requests will be considered as usual (i.e. with an explanation of what you consider to be improperly graded). I am posting term grades to insure that there has not been any mistakes in recording of the grades. If you observe an incorrectly recorded grade please bring the appropriate assignment/test to the final exam. Note that as agreed upon I have scaled term test 1 so that its average will be the average of term tests 2 and 3 (that is 67.3) and then will take the maximum of the highest two term test grades.

I have been asked about the format of the final exam. As in the term tests, you are allowed one (and only one) sheet (both sides is fine) of handwritten notes. No calculators are allowed (nor are they needed). The questions will cover all topics in the course. The questions will be similar to questions on problem sets and term tests but (obviously) will not be identical to those question. It will be important to understand the concepts.

I have a short pdf handout on the MAX3SAT problem as discussed in class and in the text. The handout now has an example of the method of conditional expectations.

As announced in class, I proposed a new grading scheme which would be used if there were no objections. Namely, the 40% of the grade determined by term tests will now be calculated by assigning 20% to each of your best two tests. I was asked to scale the grades for test 1 so that a "decent" grade in test 1 might still be useful. Again, assuming there are no objections, I will scale the grades for term test 1 so that the average grade for test 1 will equal the average of the average grades for term tests 2 and 3.

I have been asked for suggestions of more examples to look at. Here is a link to the Fall 2004 CSC373 course . For those who would like more information on linear programming, here is a chapter (in pdf) of a forthcoming text book by Dasgupta, Papadimitriou and Vazirani. The publisher of the text would appreciate any feedback on the material which you can forward through me.

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. Another comparable text is ``Algorithmics: Theory and Practice" by Brassard and Bratley. Some further course information is contained in the brief course syllabus that was handed out during the first lecture. Students are encouraged to check the undergrad announcements (UGA) website which contains announcements about things such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines. Please send any comments or questions to the instructor:

The following grading scheme will be used for this course: 4 assignments (worth 5% each), 3 term tests (closely related to the assignments and worth 15% , 12.5%, 12.5%) 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 (or when allowed, work in pairs). 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. Here is some further information on how not to cheat .
Tentative schedule for assignments and term tests: Assignments are due at the start of the class on the indicated date. We will answer questions about the assignments as soon as the assignments are submitted and hence I will not accept late assignments.
  • Assignments: September 29 (please note that there was a typo on the hard copy that was handed out during the first class), October 14 (NOTE change of date to Friday), November 4 (NOTE change of date to Friday), December 2 (NOTE change of date by one week).
  • Term Tests: October 19, November 9, December 7 (NOTE change of date by one week).
    • Here are the free
  • lecture notes
    • that have been used previously in CSC364 and CSC366.

    Problem Sets, Tests and Other Handouts will be posted here.
  • Problem set 1 in ps format
  • Problem set 1 in pdf format
  • The obvious interval covering algorithm in ps format
  • The obvious interval covering algorithm in pdf format
  • Problem set 2 in ps format
  • Problem set 2 in pdf format
  • Problem set 3 in ps format
  • Problem set 3 in pdf format
  • Problem set 4 in ps format
  • Problem set 4 in pdf format