MA/STA 515 — LINEAR AND COMBINATORIAL OPTIMIZATIONMWF 12–12:50 — CB347COURSE WEBPAGE: www.ms.uky.edu/~lee/ma515fa09/ma515fa09.htmlINSTRUCTOR: Carl Lee, 967 POT, 257-1405, [email protected], www.ms.uky.edu/~leeOFFICE HOURS: MWF 11:00–11:50 and by appointment, since I realize that some ofyou will be unable to come at these times. Also, I may need to schedule some additionalformal times for the class to meet, since there are some class days when I will be out of town.TEXT: Jon Lee, A First Course in Combinatorial Optimization, Cambridge, 2004. I willalso prepare some course notes.TOPICS:1. Chapter 0: Polytopes and Linear Programming2. Chapter 1: Matroids and the Greedy Algorithm3. Chapter 2: Minimum-Weight Dipaths4. Chapter 3: Matroid Intersection5. Chapter 4: Matching6. Chapter 5: Flows and Cuts7. Various miscellaneous topics as time permitsGRADING:Homework: 50%Exams: 30%Final: 20%HOMEWORK: Usually collected weekly, but some problems may be collected more fre-quently. From time to time I will give additional homework assignments for the graduatestudents enrolled in the course that will not be required of the undergraduate students.Problems are assigned to be solved. Searching the textbooks or the library for solutions isnot permitted. On regular assignments you may discuss the problems with other currentclass members and with me. However, when it comes time for you to write up the solutions,I expect you to do this on your own. If you receive assistance from someone else, include awritten acknowledgment. Such an acknowledgment is a professional courtesy and will notaffect your grade.EXAMS: There will be two or three exams (tentative dates: September 18, October 16,and November 20) and a final exam (December 18, 10:30 am). One or more of these may betake-home exams.IMPORTANT DATES:August 25 — Tuesday — Last day a student may officially drop a course or cancel registra-tion with the University Registrar for a full refund of fees.September 1 — Tuesday — Last day to add a class for the 2009 Fall Semester.September 1 — Tuesday — Last day to officially withdraw from the University or reducecourse load and receive an 80 percent refund.September 7 — Monday — Labor Day - Academic Holiday.September 16 — Wednesday — Last day to drop a course without it appearing on the stu-dent’s transcript.September 23 — Wednesday — Last day to officially withdraw from the University or reducecourse load and receive a 50 percent refund.October 19 — Monday — Midterm of 2009 Fall Semester.November 6 — Friday — Last day to withdraw from the University or reduce course load.Students can withdraw or reduce course load after this date only for urgent non-academicreasons.November 25–28 — Wednesday through Saturday — Thanksgiving — Academic Holidays.December 18 — Friday— Final Exam, 10:30 am.CHEATING AND PLAGIARISM: Cheating and plagiarism are not worth it, and theyare damaging to your self-integrity, so don’t do it. Here is the website with information onUniversity policies: