Assignment 1, due in class Friday September 14.

- Design an algorithm to perform multiplication using the "elementary school" method; describe the algorithm using pseudocode (similar to the description of the algorithm given in class).
- Give the worst case analysis of the time required to multiply a*b using your algorithm assuming a uniform cost RAM model of computation.
- Repeat the previous question assuming a log cost RAM model of computation.

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

- 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.
- CCPS p8 1.2
- CCPS p18 2.5
- CCPS p34 2.21 [NOTE TEXT CORRECTION: delete (k,4) from L_j]
- CCPS p36 2.36
- 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 ]

- 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. - 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.
- 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/xmapleEach 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.