COMP 150CO - Spring 2012

**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.