Reference no: EM131455221

Q1. We want to compare the naive and Karatsuba divide-and-conquer methods to multiply two integers x and y. Download the java file multiply.java from the course web page. Here, your task is to implement a recursive version of these algorithms in the methods naïve (int size, int x, int y) and karatsuba(int size, int x, int y), and to use them to compare the efficiency of each algorithm (i.e. number of arithmetic operations). The variable size is the size of the integers x and y, and is defined as the number of bits used to encode them (Note: we assume that x and y have the same size).

Each method (i.e. naive and karatsuba) will return an integer array result that stores the value of the multiplication in the first entry of the array (i.e. result[0]), and the cost of this computation in the second entry (i.e. result[1]). We define the cost as the number of brute force arithmetic operations of the (addition, subtraction, or multiplication) executed by the algorithm multiplied by the size (in bits) of the integers involved in this operation (Note: We ignore the multiplication by powers of 2 which can be executed using a bit shift. Of course, this is a crude approximation).

In particular, for the base case (i.e. when the size of the integers is 1 bit), this cost will be 1 (brute force multiplication of two integers of size 1). In the induction case, the naive method executes 3 arithmetic operations of integer of size m (i.e. cost is 3 m), in addition of the number of operations executed by each recursive call to the function. By contrast, the Karatsuba algorithm requires 6 arithmetic operations of size m on the top of the cost of the recursion. The output of your program will print a list of numbers such that, the first number of each row is the size of the integers that have been multiplied, the second number is the cost of the naïve method, and the third number the cost of the Karatsuba method.

Q2. We remind the master method for determining the asymptotical behaviour of a recursive function.

Theorem 1 (Master method) Let a ≥ 1 and b ≥ 1 be two constants, and f(n) a function. ∀n ∈ N⁺ we define T(n) as:

T(n) = aT(n/b) + f(n), where n/b is interpreted as ⌊n/b⌋ or ⌈n/b⌉.

Then, we can find asymptotical bounds for T(n) such that:

1. If f(n) = O(n^{log_b a-∈}) with ∈ > 0, then T(n) = Θ(n^{log_b a}).

2. If f(n) = Θ(n^{log_b a} · log^pn), then T(n) = Θ(n^{log_b a} log^p+1n).

3. If f(n) = Ω(n^{log_b a+∈}) with ∈ > 0, and a · f(n/b) ≤ cf(n), ∀n > n₀ with c < 1 and n₀ > 0. Then T(n) = Θ(f(n)).

When possible, apply the master theorem to find the asymptotic behaviour of T(n) from the following recurrences. Show your work and justify your answer for each recurrence.

(a) T(n) = 25 · T(n/5) + n

(b) T(n) = 2 · T(n/3) + n ·  log(n)

(c) T(n) = T(3n/4) + 1

(d) T(n) = 7 · T(n/3) + n³

(e) T(n) = T(n/2) + n(2 - cos n)

Q3. Let T_A and T_B be two function returning the running time of algorithms A and B, defined by the recusions T_A(n) = 7T_A(n/2) + n² and TB(n) = αT_B(n/4) + n². Find the largest integer value of α for which algorithm B is asymptotically faster than A.

Attachment:- Assignment Files.rar