CS 4625 Spring 2001
Assignment 3

Handed out: Thurs, Feb 27
Due: Thurs,  March 29
Total Marks: [110]
 

Exercise 1 [20]:  Matrix multiplication

1. What is the optimal way to compute A₁A₂A₃A₄A₅A₆, where the dimensions of the matrices are: A₁: 10x20, A₂: 20x1, A₃: 1x40, A₄: 40x5, A₅: 5x30, A₆: 30x15.
2. Show that none of the following greedy algorithms for chained matrix multiplication work. At each step:
1. Compute the cheapest multiplication
2. Compute the most expensive multiplication
3. Compute the multiplication between the two matrices M_i and M_i+1, such that the number of columns in M_i is minimized (breaking ties by one of the rules above).


Hint : use a proof by counterexample.

Exercise 2 [50]:   Closest pair of points

1.  N points are placed in a unit square. Show that the distance between the closest pair is O(N^-1/2)
2.   Argue that for the closest-points algorithm, the average number of points in the strip is O(N^1/2).
3. Practice question[30]: write the program to implement the closest-pair algorithm. Compare the runing time of this program to a program using the trivial way to solve the same problem.

Exercise 3 [20]: The one-dimensional circle packing problem

You have N circles of radii r₁,r₂,...,r_N. These circles are packed in a box such that each circle is tangent to the bottom of the box, and are arranged in the original order. The problem is to find the width of the minimized-sized box. The figure below shows an example with circles of radii 2,1,2 respectively. The minimum-sized box has width 4 + 4 x 2^1/2.

Exercise 4 [20]:  Dynamic Programming

One form of the knapsack problem is as follows: we are given a set of integers A=a₁,a₂,...,a_N and an integer K. Is there a subset of A whose sum is exactly K?

1. Give an algorithm that solves the knapsack problem in O(NK) time.
2. Why does this not show that P=NP ?

Hand_In of coding question:

  1/ create a directory named "assign3"

 2/ move all files required by the assignment to the directory "assign3" i.e :

         If you are submiting a single file :

              program3.cpp

         If you are submiting more than one file :

              README (file expalaining the compilation and execution of your program including the
              format of input and other details)
              headers (.h)
              implementations (.cc , .cpp...etc)
              the Makefile :

                  should be named "makefile"

              the generated executable should be named : "assign3"

              you can give any name to your source files. The marker will only have to execute  "make" to
              compile your program and "assign1" to execute it.

3/  tar your directory

        tar cf assign3.tar assign3

4/ compress the result with gzip

        gzip assign3.tar

5/ The result will be a file named :

      assign3.tar.gz

6/ Execute the following script :

     /home/4625/assignments/a3_4625_submit

7/ Check(read the message) mentioning that the script has found your file

8/ Ignore the error message about uuencode !

9/ The marker will send you an e-mail confirming the reception
   of your files.