1. General Information2. Texts2.1. Required Texts:3. Course Description and Goals4. Course Assessment5. Course Grades6. Academic Integrity and Classroom Demeanor7. Classroom and Learning Accommodations8. Tentative ScheduleLinear and Combinatorial Optimization1MA/STA 515, Section 001, Fall 20081. General InformationDr. Benjamin BraunCourse Webpage: http://www.ms.uky.edu/%7ebraunEmail: [email protected]: 257-68103:00-3:50 PM, MWF, CB 347Office Location/Hours: 831 POT, 2:00-2:50PM Monday and Friday2. Texts2.1. Required Texts: A First Course in Combinatorial Optimization, by Jon Lee. CambridgeUniversity Press, 2004.Linear Programming Notes, by Carl Lee. Available from the course website.3. Course Description and GoalsThe best way to teach real mathematics, I believe, is to start deeper down, with the elementaryideas of number and space. . . . in fact, arithmetic, algebra, and geometry can never beoutgrown. . . by maintaining ties between these disciplines, it is possible to present a more unifiedview of mathematics, yet at the same time to include more spice and variety.Numbers and GeometryJohn StillwellFinding optimal solutions to mathematical models is a classical problem; even first-year calculusstudents solve problems involving local and global maximization and minimization! Linear pro-gramming is the study of finding maximal and minimal solutions to systems constrained by linearequalities and inequalities. Problems of this type arise in many disciplines, including mathematics,statistics, chemistry, computer science, economics, and others. Combinatorial optimization prob-lems arise when we seek to find maximal and minimal solutions to some model over a finite object,typically one with combinatorial structure. The interplay of linear programming and combinatorialoptimization leads to beautiful mathematics and rich applications.We will discuss the following sections from the course texts:• C. Lee, Linear Programming Notes• J. Lee, Chapter 0, Linear Programming• J. Lee, Chapter 1, Matroids• J. Lee, Chapter 2, Minimum-Weight Dipaths• J. Lee, Chapter 3, Matroid Intersection• J. Lee, Chapter 4, Matching• J. Lee, Chapter 5, Flows and Cuts• Additional Topics, as time permitsMy goal as an instructor in this course is to nurture your innate desire to discover and understandmathematical truths. My goal for you, the student, is to achieve profound understanding of linearand combinatorial optimization2. By this, I mean that you will:1I reserve the right to change or amend this syllabus at any time for any reason.2The following description is adapted from the work of Liping Ma, as described in her book Knowing and TeachingElementary Mathematics; see page 122 in particular.1(1) make connections among relevant mathematical concepts and procedures, from simple andsuperficial connections between individual pieces of knowledge to complicated and under-lying connections among linear algebra, combinatorics, polyhedral geometry, and relatedareas;(2) approach problems from multiple perspectives, providing explanations of the varying per-spectives and comparing their advantages and disadvantages;(3) be aware of simple but powerful basic mathematical concepts and principles such as theroles and purposes of linearity, maximality, etc.; and(4) relate ideas and techniques from linear and combinatorial optimization to previous mathe-matical study.In short, you will know how to solve problems in linear and combinatorial optimization, know whyyour solutions work, and understand how they are related to the mathematical world and beyond.4. Course Assessment• You must be present and engaged in class discussion each day. If you need to miss class forsome reason, please notify me ahead of time.• There will be regular homework assignments. These will be graded and returned to you.WARNING: No late work will be accepted.• While searching the library or internet for solutions is not allowed, you may work on home-work problems with your classmates (mathematics is a social endeavor). For each homeworkproblem, list the people you worked with. You must write up your own answers to all thequestions; do not let cooperation degenerate into one person solving the problem and otherpeople copying their answers. The act of copying a written answer from another studentand submitting it as your own will be considered cheating and will be dealt with accordingto the procedures referenced in Section 6.• There will be two in-class exams and a cumulative final.5. Course GradesGraduate Students: Your total grade will be determined by your homework and exams. Thegrading scale will be no stricter than the usual A>89.9, B>79.9, C>69.9, D>59.9, E otherwise,weighted as follows:• Homework: 30%• In-Class Exams: 20% each• Final Exam: 30%Undergraduate Students: Your total grade will be determined by your homework and exams.The grading scale will be no stricter than A>84.9, B>74.9, C>64.9, D>54.9, E otherwise, weightedas follows:• Homework: 30%• In-Class Exams: 20% each• Final Exam: 30%6. Academic Integrity and Classroom DemeanorAll students are expected to follow the academic integrity standards as explained in the UniversitySenate Rules, particularly Chapter 6, found at:http://www.uky.edu/USC/New/SenateRulesMain.htmTurn off all cell phones, pagers, etc. prior to entering the classroom. You are not to use yourcell phones, pagers, or other electronic devices during class. An attitude of respect forand civility towards other students in the class and the instructor is expected at all times.7. Classroom and Learning AccommodationsAny student with a disability who is taking this course and needs classroom or exam accommoda-tions should contact the Disability Resource Center, 257-2754, room 2 Alumni Gym, [email protected]. Tentative ScheduleIn the following, “Notes” refers to the notes by Carl Lee and “Opt” refers to the optimizationbook by Jon Lee. Thus, a reference to Notes, 7.3 means section 7.3 in Carl Lee’s Notes.IMPORTANT COMMENT: The Notes by Carl Lee are a more detailed presentation of thematerial in Chapter 0 of Jon Lee’s book. You are expected to look through Chapter 0 and familiarizeyourself with both presentations. This will help you when we switch to using Jon Lee’s bookexclusively.• Wed, Aug 27: Course Introduction and Notes, 8.1 – Matrices• Fri, Aug 29: Notes, 8.2 and 8.3 – Matrix Algebra, Graphs and Digraphs• Mon, Sept 1: LABOR DAY HOLIDAY, No class• Wed, Sept 3: