308-360 Assignment 1 Solution

Main Problems and Misconceptions

  1. If you are asked for a dynamic programming algorithm, then write a dynamic programming algorithm. Yours should be similar to those we examined in class, like longest increasing subsequence and grid walk. Remember that Dynamic Programming means that the optimal solution for some case is some combination of optimal solutions of cases already solved. If you are stuck, think of a 1-d or 2-d array that you are being asked to fill.
  2. Prove a dynamic programming algorithm's correctness. Ok, remember all that induction we looked at? If not, see tutorial 1. There was a reason for all that work... use an inductive proof to show the correctness of your algorithm.
  3. Given a problem like this: prove a holds if and only if b holds, you should know that your proof must show that a implies b and b implies a. One easy method of proving such implications is by contradiction. So, prove a implies b be letting a be true and b be false. Show that this creates a contradication, so if a is true then b must also be true. Do the same thing to show b implies a.
  4. Read the question. Make an algorithm or proof that solves the problem or statement in the question. A lot of students constructed algorithms and proofs that were related to the problem, but that didn't actually solve of prove the problem.

Question 1: Factorisation

 First, we develop a recursion. If n is a number and n = ab then f(n) = f(a) + f(b). All we need to do is find these two numbers a and b. One strategy would be to search for all numbers a < n and determine whether a divides n, putting b = n/a. How long would this take? If we check all of a=1,2,...,n then it takes O(n) time to find a and b. However we can assume that a <= b, in which case a <= n/a and a <= sqrt(n). This is what all we need to begin.

Memoized Algorithm

Let F be a 2 to n array of integers.

Factors(n)     //returns an integer.
1. if F[n] > 0 then return F[n]
2. else
3.     a = 2
4.     while a <= sqrt{n} do
5.         if n/a is an integer then
6.             return Factors(a) + Factors(n/a)
7.     return 1     //n is a prime

AllFactors(n)
1. Initialise F[i] = 0 for all i
2. for i = 2 to n do
3.     F[i] = Factors(i)

Loop Algorithm
Let F be a 2 to n array of integers.

Factors(n)     //Fill in the F array.
1. for i = 2 to n do
2.     a = 2
3.     prime = true
4.     while a <= sqrt{n} and prime == true do
5.         b = n/a
6.         if b is an integer then
7.             F[i] = F[a] + F[b]
8.             prime = false
9.         a++;
10.   end while
11.   if prime == true then
12.        F[i] = 1
13. end for

Formal Proof of Correctness (Memoized Algorithm)
Let P(n) denote the statement Factors(n) returns the number of factors in the prime factorisation of n, where n >= 2.

Induction Basis When n=2, Factors(n) returns 1, which is correct since 2 is a prime. Thus P(2) is true.

Induction step Suppose that P(k) is true for all k such that 2 <= k < n.

If n is a prime, then n/a is not an integer for all a such that 2 <= a <= sqrt{n}. Hence line 6. will not be called, and the algorithm returns 1 in line 7.

If n is not a prime then there is a <= sqrt{n} such that n/a is an integer. In this case, the number of factors in the prime factorisation of n will equal the number of factors of a plus the number of factors of n/a. By the induction hypothesis, these are correctly computed by Factors(a) and Factors(n/a), and the correct value of F(n) will be returned in line 6.\\

Time Complexity Analysis (Memoized Algorithm)
Each time Factors(i) is called for a new i, there are at most \sqrt{i} iterations for the loop in lines 4--6. Each subsequent call takes constant time. Thus the total time taken by the algorithm is O(n \sqrt{n}). [Note - there is probably a tighter bound on this!!!]

Question 2: Biconnected Components
 See the pdf or ps solution at the class site.

Question 3: Bellman-Ford Algorithm and Arbitrage
 See the pdf or ps solution at the class site.

| tutorial index | kaleigh work |