IMPORTANT NOTE: I allow one page (double-sided) handwritten notes as an aid in all my tests and exams.
Announcements for week of May 8. I have graded the final exams and have computed final grades. I will be submitting these grades to the Department Office which then gets sent to the Faculty office. The grades are not official untl approved by the Department and Faculty. If you email me, I will send your complete set of grades including your unofficial final grade for the course. I want to correct an incorrect statement I think I made regarding Max2SAT (or MaxSat). Namely, I may have said that this problem was #P complete but in fact it is "just" NP-hard and given our current beliefs cannot be #P complete. #P problems essentially count the number of certificates and in general this number is exponential in the length of the input. Even if P = NP, there is no reason to believe we could exactly compute the output of a #P complete problem in polynomial time. But it is easy to see that if P = NP we could polynomial time compute the maximum number of satisfiable clauses. As I mentioned in class there is a known hardness of approximation (approximately .95) result known for Max2SAT and 7/8 for Max3SAT.
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.
This page provides general course information and access to
various documents concerning CSC375.
Lectures are held Mondays and Wednesday at 2 PM and the tutorials
take place Fridays at 2 PM. The first lecture is Monday,
January 9 and the first tutorial is Friday, January 11.
Weekly announcements for the course
will be posted on this web site. As the required text,
we will use the lecture notes
"Algorithm Design"
by Jon Kleinberg and Eva Tardos (which are being developed into
a textbook) and the lecture notes are available at the bookstore.
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.
More information is contained in the
brief course syllabus
.
Please send any comments or questions to the instructor:
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.
Problem Sets, Tests and Other Handouts will be posted here.