Comp 251: Assignment 4

Instructor: Jérôme Waldispühl

Due on April 8th at 11h

• Your solution must be returned electronically on MyCourse.
• Written answers and programming questions must be returned in separate submission folders on MyCourse.
• The only format accepted for written answers are PDF or text files (e.g. .txtor.rtf). PDF files must open on SOCS computers. Any additional files (e.g. images) must be in- cluded in the PDF.
• Do not submit a compressed files (e.g. zip files). Upload instead each PDF or text file individually.
• The solution of programming questions must be written in java. Submit the Java source file only (i.e..java). Your program should compile and execute of SOCS computers in a terminal. Java files that do not compile or execute properly on SOCS computer will not be graded.
• To some extent, collaborations are allowed. These collaborations should not go as far as sharing code or giving away the answer. You must indicate on your assignments the names of the persons with who you collaborated or discussed your assignments (including members of the course staff). If you did not collaborate with anyone, you write “No collaborators” at the beginning of your document. If asked, you should be able to orally explain your solution to a member of the course staff.
• Unless specified, all answers must be justified.
• When applicable, your pseudo-code should be commented and indented.
• The clarity and presentation of your answers is part of the grading. Be neat!
• Violation of all rules above may result in penalties or even absence of grading (Please, refer to the course webpage for a full description of the policy).
• Partial answers will receive credits.
• The course staff will answer questions about the assignment during office hours or in the online forum athttps://osqa.cs.mcgill.ca/. We urge you to ask your questions as early as possible. We cannot guarantee that questions asked less than 24h before the submission deadline will be answered in time.

1. (50 points) We want to compare the naive and Karatsuba divide-and-conquer methods to mul-

tiply two integersxandy. Download the java filemultiply.javafrom the course web page. Here, your task is to implement a recursive version of these algorithms in the methods

1

naive(int size, int x, int y)andkaratsuba(int size, int x, int
y), and to use them to compare the efficiency of each algorithm (i.e. number of arithmetic op-
erations). The variablesizeis the size of the integersxandy, and is defined as the number
of bits used to encode them (Note: we assume thatxandyhave the same size).
Each method (i.e.naiveandkaratsuba) will return an integer arrayresultthat 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 sizem(i.e. cost is 3 ·m), in addition of the num-
ber of operations executed by each recursive call to the function. By contrast, the Karatsuba
algorithm requires 6 arithmetic operations of sizemon 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 naive
method, and the third number the cost of the Karatsuba method.

2. (25 points) We remind the master method for determining the asymptotical behaviour of a recursive function.

Theorem 1 (Master method) Leta≥ 1 andb≥ 1 be two constants, andf(n)a function.
∀n∈N+we defineT(n)as:

T(n) =aT

(n
b

)

+f(n),wherenbis interpreted asbnbcordnbe.

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

1. Iff(n) =O(nlogba−)with > 0 , thenT(n) = Θ(nlogba).
2. Iff(n) = Θ(nlogba·logpn), thenT(n) = Θ(nlogbalogp+1n).
3. Iff(n) = Ω(nlogba+)with > 0 , anda·f

(n
b

)

≤ cf(n),∀n > n 0 withc < 1 and
n 0 > 0. ThenT(n) = Θ(f(n)).

When possible, apply the master theorem to find the asymptotic behaviour ofT(n)from the
following recurrences. Show your work and justify your answer for each recurrence.
(a) (5 points) T(n) = 25·T(n 5 ) +n
(b) (5 points) T(n) = 2·T(n 3 ) +n·log(n)
(c) (5 points) T(n) =T(^34 n) + 1
(d) (5 points) T(n) = 7·T(n 3 ) +n^3
(e) (5 points) T(n) =T(n/2) +n(2−cosn)

COMP 251 - HW4 Page 2 of 3 Winter 2017

3. (25 points) LetTAandTBbe two function returning the running time of algorithmsAandB, defined by the recusionsTA(n) = 7TA(n 2 ) +n^2 andTB(n) =αTB(n 4 ) +n^2. Find the largest integer value ofαfor which algorithm B is asymptotically faster than A.

COMP 251 - HW4 Page 3 of 3 Winter 2017