MA/STA 515 — LINEAR AND COMBINATORIAL OPTIMIZATIONMWF 2:00–2:50 — CB347COURSE WEBPAGE: www.ms.uky.edu/~lee/ma515fa06/ma515fa06.htmlINSTRUCTOR: Carl Lee, 967 POT, 257-1405, [email protected], www.ms.uky.edu/~leeOFFICE HOURS: MWF 1:00–1: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. I also expect to ask students to present solutions on the board at various times, andfor some problems to be typed in LATEX. From time to time I will give additional homeworkassignments for the graduate students enrolled in the course that will not be required of theundergraduate students. Problems are assigned to be solved. Searching the textbooks or thelibrary for solutions is not permitted. On regular assignments you may discuss the problemswith other current class members and with me. However, when it comes time for you towrite up the solutions, I expect you to do this on your own. If you receive assistance fromsomeone else, include a written acknowledgment. Such an acknowledgment is a professionalcourtesy and will not affect your grade.EXAMS: There will be two or three exams (tentative dates: September 20, October 18,and November 15) and a final exam (December 11).IMPORTANT DATES:Wednesday, August 23, First day of classesTuesday, August 29, Last day to add a classMonday, September 4, Labor Day holiday—no classWednesday, September 13, Last day to drop a class without a gradeFriday, October 6, October break—no classSaturday–Sunday, October 7–8, Tentative math graduate “cease-fire” weekendFriday, October 20, Last day to withdraw from a classThursday–Friday, November 23–24, Thanksgiving holiday—no classFriday, December 8, Last day of classesMonday, December 11, 1:00 p.m., Final exam.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: