CS2223 Algorithms
Homework 2 - D Term 2015

Due Date: Friday, April 3rd 2015 at 1:50 pm
See course policy regarding late homework submissions

Homework Instructions:

• Read Chapters 2 and 3 and Sections 4.1-4.3 of the textbook in detail.
• See useful resources posted on the course lecture notes.
• This is an individual homework. No collaboration is allowed.
• Remember to show your work and explain your answers. Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.
• Python Code vs. Pseudocode: Each question will explicitly state whether the deliverable is pseudocode or a Python program that the TAs will run to give you a grade.
• Programming Language: If a question asks you to write a program, then use the Python language.
• HW Submission: The submission of Homework 2 must be done electronically through the blackboard site for CS2223 available from myWPI. Login to myWPI, go to CS2223 under "My Courses", then go to "Assignments", and submit your homework under "HW2". All programs plus your report (.doc or .pdf) should be zipped into a single file. Submit that single .zip file.
• See the course webpage for the late homework submission policy.

Homework Problems:

1. (15 points) Problem 1.

   1. (7 points) In homework 1, you determined that n log₂(n) grows slower than n² - 324. Use the basic definition of Big-Omega to prove that: n² - 324 is Ω(n log₂(n)). Show your work.

   2. (8 points) In homework 1, you determined that log₂(n) grows slower than 12 √ n . Use the limit rule theorem to prove that: log₂(n) = O( √ n ). Show your work.

   ---

2. (25 points) Problem 2. Let f, g, h, and k be functions. Assume that for each n ≥ 0, these functions output a positive value. That is, f(n) > 0 for all n ≥ 0, and the same property holds for g, h, and k.

   1. (10 points) Prove using the basic definition of Big-O the following property:

      If f(n) = O(g(n)) and h(n) = O(k(n)) then f(n) + h(n) = O(g(n) + k(n)).

   2. (10 points) Prove using the basic definition of Big-O the following property:

      If f(n) = O(g(n)) and h(n) = O(k(n)) then f(n) * h(n) = O(g(n) * k(n)).

   3. (5 points) What is wrong with the following "proof" of the true fact below? Explain your answer.

      True Fact: If f(n) = O(g(n)) then f(n) = O(a*g(n)) for any constant a > 0.
      Incorrect Proof: If f(n) = O(g(n)) then lim n→∞[f(n)/g(n)] = 0. Thus, lim n→∞[f(n)/a g(n)] = 0. Hence, f(n) = O(a*g(n)). Q.E.D.

   ---

3. (25 points) Problem 3. Consider the following problem: Given an 2-dimensional matrix A of size (n x n), where each cell (or entry) in the matrix contains an integer value, return:

   • 1, if the matrix is a triangular matrix (either upper triangular, or lower triangular, but not both).
   • 0, otherwise.

   1. (10 points) Design an algorithm to solve this problem. Write your algorithm using pseudo-code.

   2. (5 points) Prove that your algorithmm is correct. That is, that for any input it always produces the correct output.

   3. Analyze the time complexity of your algorithm using worst-case analysis, following the steps below.
      1. (02 points) State what the size of the input is and what variable you will use to denote it.
      2. (03 points) To the right of each instruction in your pseudo-code, state what the cost of performing the instruction is, how many times the instruction is repeated as a function of the input size, and the total cost of executing that instruction over all iterations. Be precise.
         [As an example, see Solutions to Quiz1 CS2223 B term 2005. Problem II.]
      3. (05 points) Combine these costs to obtain the total runtime function T(n) of your program.

   ---

4. (20 points) Problem 4. Consider the recurrence: T(n) = 5T(n/3) + n².
   1. (10 points) Use the master theorem to find a function g(n) such that T(n) = O(g(n)). Explain your answer.
   2. (10 points) Use the recursion-tree method to show again that T(n) = O(g(n)), where g(n) is the function you found above. [Note: Choose a convenient base case if you need one. If not, ignore this comment.]

   ---

5. (15 points) Problem 5.

   Consider "Euclid's" algorithm to calculate the gcd of two integers. For positive integers m, n: gcd(m,n) = largest positive integer that divides both m and n evenly (that is, without a remainder).

      function Euclid(m, n) {
         while (m > 0) {
            temp = m
            m = n mod m
            n = temp
         }
         return n
      }
   

   1. (5 points) Run the algorithm by hand with input n = 24 and m = 32. Show your work.
   2. (10 points) Argue that this algorithm is an example of a "divide-and-conquer", or more precisely a "reduce-and-conquer", strategy.

   ---

6. (10 points) Bonus Problem . In this problem you will compare two different algorithms to calculate the n-th Fibonacci number. As you know,

   Fib(0) = 0
   Fib(1) = 1
   Fib(2) = 1
   ...
   Fib(n) = Fib(n-2) + Fib(n-1) for all n > 1.
   

   Here are the first few Fib(n) values: 0, 1, 1, 2, 3, 5 8, 13, 21, ... The following are two alternative algorithms for computing Fib(n):

   • Recursive version:
     This is a straightforward implementation of the definition:

        function Fibrec(n) {
           if (n < 2) return n
           else return (Fibrec(n-1) + Fibrec(n-2))
        }
     

   • Iterative version: The other algorithm uses an iterative approach. We analyzed the time complexity of this algorithm in class.

        function Fibiter(n) {
           if (n<2) return n
           else {
              temp1 = 1
              temp2 = 0
              while (n>1) {
                 sum = temp1 + temp2
                 temp2 = temp1
                 temp1 = sum
                 n = n-1
              }
           }
           return sum
        }
     

   Here is what you need to do for this problem:
   1. (5 points) Implement these two algorithms in Python.
   2. Time the execution of each of these two problems by adding two new functions:

         function TimeFibrec(n) {
            include a Python instruction here to start the clock
            k = Fibrec(n)
            include a Python instruction here to stopt the clock
            include a Python instruction here to print n and the time 
               taken to calculate Fibrec(n)
         }
      

         function TimeFibiter(n) {
            include a Python instruction here to start the clock
            k = Fibiter(n)
            include a Python instruction here to stopt the clock
            include a Python instruction here to print n and the time 
               taken to calculate Fibiter(n)
         }
      

      Submit your full Python code as part of your HW submission.
   3. (5 points) Include in your written report the time taken to calculate Fibrec(n) for as many n's (0, 1, 2, 3, 4, ...) as you can such that the largest execution time reported is around 3 minutes. Do the same for Fibiter(n), so that you could compare the times reported for Fibiter(n) and by Fibrec(n) for the same n. For Fibiter(n), you don't need to report the running time for every number n (it will be very large).