Homework 2.  Due Aug 21

Reading: Chapter 9.3 (all exercises in the section, and all problems
on the chapter), EL (Electronic lesson) "Discrete Optimization", "Dynamic
Programming: Knapsack"

1.  Problem 9-2 of CLRS

2.  Exercise 9.3-1 of CLRS.

3.  Exercises 2 and 4 from EL: Discrete Optimization.

4.  Consider the problem of determining whether a string $A[1..m]$ is
    a substring of another string $B[1..n]$, i.e. whether there exists
    an integer $d$ such that $A[i]=B[i+d]$ for all $1\le i \le m$.

    (a) Give an algorithm from specification for this problem.

    (b) Consider the following divide-and-conquer strategy for solving
    the problem: 

    DandC(A,B){
      m = length(A)
      n = length(B)
      if n < 2m then return brute(A,B)
      if DandC(A,B[1..n/2]) or DandC(A, B[n/2+1..n]) then return true
      Else
        ...
    }

    Complete the algorithm given above -- state what is needed in
    place of "...".  Analyze the time required by the resulting
    algorithm.  Dont worry if the time is not better than what you get
    in part (a) -- divide and conquer isnt always fast!

5.  Exercise 9.3-8, CLRS.  Show that by doing one comparison, half of
    either the array X or the array Y can be ruled out.  (No, this
    doesnt require you to know the median finding algorithm.  The idea
    is somewhat similar to binary search.)