Assignment 1, due in class Friday September 14.

Assignment 2, due in class Friday October 12. GROUP SIZE 1 or 2.

  1. Implement a program which finds an MST and the weight of some Hamiltonian tour for the Canada graph. You do not need to hand in the source code, but keep it available in case I need to see it later. Hand in a very brief description of the particular algorithm you implemented, and its asymptotic running time, *and* the actual running time when it found the MST.
  2. CCPS p8 1.2
  3. CCPS p18 2.5
  4. CCPS p34 2.21 [NOTE TEXT CORRECTION: delete (k,4) from L_j]
  5. CCPS p36 2.36
  6. solve the following problem via the simplex method; show each dictionary
    max cx   s.t. Ax <= b, x >= 0 where
       c= [3  1]  A =[  1   -1 ]  b = [ -1 ]
                     [ -1   -1 ]      [ -3 ]
    	         [  2    1 ]      [  4 ]
Assignment 3, due in class Friday November 30. GROUP SIZE 1 or 2.
  1. Call a graph zippy if, for every induced subgraph with at least two vertices, either the subgraph or its complement is disconnected.
    (a) Draw all (non-isomorhic, unlabelled) non-zippy graphs with at most 5 vertices.
    (b) Prove that zippy graphs are perfect.
    (c) Describe (in detailed pseudo-code) a polynomial time algorithm to find the clique-size of a zippy graph.
    (d) Analyze the running time of your algorithm.
  2. Let G be a weighted graph whose weights satisfy the triangle inequality, and suppose that (x,y,z) is a shortest distance x-z path. Let G- be the weighted graph obtained from G by removing y, and adding an edge (xz) whose weight is the same as the x-z distance in G. Let T- be a minimum weight Hamiltonian tour of G-, and suppose that T- includes the edge (x,z). Let T be the tour obtained from T- by replacing the edge (x,z) with the path (x,y,z). Prove or disprove: T is a minimum weight Hamiltonian tour of G.
  3. Construct a small tsp example to illustrate the ideas of the DFJ paper.
    (a) Pick a weighted graph on a small number of vertices. The weights should be non-negative, but do not have to satisfy the triangle inequality. The graph does not have to be complete.
    (b) Formulate the tsp on your graph as an IP.
    (c) Formulate an initial LP relaxation of the IP.
    (d) Find an optimal solution x* to the LP (and if possible, give a proof that x* is LP-optimal); x* should NOT be an optimal tour.
    (e) Find a cutting plane which separates x* from the feasible integer solutions.
    Note: there is a version of maple, which has an LP solver, on tees, in directory /usr/local/maple/bin/xmaple

    Each assignment *must* include an acknowledgement statement.
    Each group must write up their assignment with *no* assistance from anyone outside the group. Discussion of problems with other people before writing up of solutions has begun *is* permitted, but any such discussions *must* be cited when listing collaborations. Copying of all or part of another group's writeup constitutes plagiarism.