CMSC  435  Algorithm Analysis & Design

 

Review Material for the Second Exam

 

Algorithms covered in class

  1. Exact-fit Knapsack problem
  2. 0-1 Knapsack problem
  3. Matrix-chain multiplication
  4. Longest Common Subsequence
  5. Best Matching Problem
  6. Floyd-Warshall (All pairs shortest distance) **
  7. The Fractional Knapsack problem
  8. Various Sorting Algorithms
  9. Divide and Conquer Recurrence relations

 

1.      Solve the following recurrence relations:

 

  a)  T(n) = 3 T(n/2) + n2

 

  b)  T(n) = 5 T(n/4) + n lg(n)

 

  c)  T(n) = 8 T(n/2) + 4n3

 

2.      Let T(n) = the number of moves to move a Tower of n disks from the source peg to the target peg.  Write the recurrence relation for T(n) based upon the recursive Towers of Hanoi algorithm.

 

3.      Let T(n) = the number of multiplications that have to be performed, worst case, in the following algorithm.  Write the recurrence relation for T(n), and find its big-Q asymptotic bound.

 

double  exp(double x, int n) {

    if (n < 0)

            return 1.0/exp(x, -n);

    else  {

if (n == 0)

      return 1;

if (n == 1)

      return x;

if (n % 2 == 1)

      return  x * exp (x, n-1);

else {

      double temp = exp(x, n/2);

      return temp * temp;

}

                }

            }

 

4.      Given the alternative description of the partition function in quicksort shown below, write the algorithm for a function     partition based upon this description.

 

 

5.      Given the following strategy for bubble sort, draw the picture of how the array appears at some intermediate stage in the execution of the algorithm, state the invariants (truths about each of the segments) and the starting and stopping      conditions in terms of the picture that you have drawn, and from this description write the algorithm.  Bubble sort strategy:  Start at the beginning of the untested portion of the list (array) and compare each element with its immediate successor.  If that element is greater than its successor, swap the two and continue traversing the list and performing comparisons and swaps until you reach the last element in the untested portion of the list.  Adjust the boundary between the tested and untested portion of the list, and continue this process until the untested portion of the list is empty, or until you make a complete traversal of the untested segment with no swaps.

 

6.      Write an O(n) algorithm that, given an array A consisting of a sorted subarray of size m followed by a sorted subarray of size n, merges them into A using an extra array of size min{m,n}.

 

7.      Given a list of items with their sizes and multiplicities (number of the item available), determine if an exact-fit solution exists for a given knapsack, and if so, give an algorithm for retrieving the elements of such a solution.

 

8.      Given a list of items with their sizes, values, and multiplicities, find the maximum value one could place in the knapsack without exceeding its capacity.

 

9.      Given a list of items with their sizes and values, write a dynamic programming algorithm that maximizes the value of the contents placed in the knapsack.  The total size of the objects placed in the knapsack need not exactly fill the capacity of the knapsack, but must not exceed this capacity.  (Assume all sizes and values are integral.)

 

10.  Given two strings X and Y and the weights dx = dy = 2, ax[i],y[j] = 0 if x[i] = y[j], and ax[i],y[j] = 1 if one each of x[i], y[j] are A and C, or one each are T and G, and ax[i],y[j] = 3 if one each of x[i], y[j] are A and T or one each are C and G, and ax[i],y[j] = 4 if one each of x[i], y[j] are A and G or one each of C and T.  Let X = ACCGTACTTCG, and Y = TACCGACTCCG.  Construct a table and determine the best match.

 

11.  Write a dynamic programming algorithm to determine the best factorization of a for the matrix chain A1A2A3A4A5 with dimensions p = <3,10, 50, 100, 10, 25>.  Construct a table and determine the factorization and minimum number of mults.