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.
Assignment 3, due in class Friday November 30. 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
(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
(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
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.