General Information
This is the course website for the Comp150CO: Combinatorial Optimization
Spring 2012 with Anselm Blumer.

People:
Anselm Blumer
ablumer (at) cs dottufts dot edu
Halligan Hall, Room 214
Office Hours: TBA or by appointment.
Home page

Description and Objective:
Methods for solving discrete optimization problems: Linear and convex programming, duality, max flow, bipartite matching, branch and bound, approximation.

Prerequisites: COMP 160 and Linear Algebra (MATH 46 or 54)

Text:
Combinatorial Optimization: Algorithms and Complexity (Dover edition).
Christos H. Papadimitriou and Kenneth Steiglitz, Dover (1998)
ISBN: 0-486-40258-4

Topics covered by text:

Linear programming
Simplex algorithm
Duality
Max-Flow and shortest paths
Min-cost flow
Ellipsoid algorithm
Matching
Spanning trees
Matroids
Integer linear programming
Cutting-plane algorithms
NP-completeness
Approximation algorithms
Branch-and-bound
Dynamic programming
Local search

Communication:
Students are encouraged to communicate frequently with the instructor regarding any issues with the course. Students are encouraged to use email and office hours frequently. Any announcements regarding the course will be made via the course webpage or in class so be sure to check it frequently and be sure to get material for any class you miss.

Homework:
Homework will be assigned regularly in the course. While reading assignments will not be directly assigned it is important that students use the textbook to supplement their understanding of the material presented in the lecture. The majority of the assignments will be written assignments due on Thursdays at the beginning of class on the due date specified. This work can be handwritten with the assumption that these assignments are legible. (A student may be asked to type their assignments to improve legibility.)

Late Homework:
20% will be deducted for each weekday late.

Exams:
There will be no exams unless there are academic honesty problems on the homework.

Grade Calculation:
90% Homework
10% Class participation

Feedback:
Your thoughts and concerns on this course are important. You are encouraged to give feedback to the instructor and teaching fellow throughout the term. As always students will be asked to fill out a course evaluation at the end of the term.

Academic Misconduct:
Students should read the Tufts brochure on academic integrity located at: http://uss.tufts.edu/studentaffairs/publicationsandwebsites/AcademicIntegrity.pdf

A few highlights are presented to emphasize importance:

Absolute adherence to the code of conduct is demanded of the instructor, teaching fellow, and students. This means that no matter the circumstance any misconduct will be reported to Tufts University.

While students are encouraged to discuss course materials, no collaboration is allowed on homework. Specifically you may discuss assignments and projects verbally, but must write up or work on the computer alone. In addition any discussion should be documented. An example on the homework would be "Thanks to Ray for helping me understand Kolmogorov complexity." Another important example is citing a source, this could be "This information was adapted from www.boston.com"

While computers enable easy copying and collaboration both with other students and materials from the Internet, it is possible to use these same computers to detect plagiarism and collaboration.

If any student does not understand these terms or any outlined in The Academic Code of Conduct it is his/her responsibility to talk to the instructor or teaching fellow.