CS 4349 — Advanced Algorithm Design and Analysis, Homework 2

Download PDF

Question 1 - We prove the following using the Master Method

a

We must now prove regularity

Thus, T(n) =

b

, so T(n) is

c

We must now prove regularity

Thus, T(n) is

d

We must now prove regularity

Thus, T(n) =

Question 2

a

No. . Recall that .

Now let us proceed by contradiction. Assume there is constants such that for all and .

Rearranging, we get

but this is clearly false.

b

No. 2.0000000001 > 2. This means that

We can show this through contradiction. Assume there is constants such that for all and .

This implies that for all .

Rearranging, we get that

However, this cannot be true for n > 1, thus a contradiction is derived.

Question 3

a

Input: A vector of length called

Output: A boolean answering the proposition (i.e if A is sorted)

b

Input: The input size is . In practice, every integer is allocated the same number of bits (usually for the positive part), and thus in implementation, is

c

Output: The output size is 1 (1 bit valued at either 1 or 0 representing either T or F)

d

e

Input: A vector of length called . We will assume

Output: A boolean answering the proposition (i.e if the even indices of A are sorted in increasing order)

Question 4

a

Input: Two digit integers which are a power of 2, which we denote and

b

Output:

c

If n=1, the running time is , as we must repeatedly add to find the product. Since this operation is performed once for each digit in , each digit is added to itself

d

Divide each integer into two halves :

Each part of these has length

e

Before combining, let us make some observations. Similarly,

We will write this as

We can compute each of these three terms separately. (Conquer)

f

Combining can also simply be seen as the addition of these three terms can be done through addition. We will assume addition is , as each digit must be added.

g

We now find an asymptotic solution to this recurrence using the master theorem. Recall that the master theorem solves recurrences of the form

with and

Let , which in this case

The first case of the master theorem applies, so this method of multiplication is

Note: This is the Karatsuba algorithm for multiplication. While this faster asymptotic time complexity, this is considered a “Galactic” algorithm, where the constant factor of performing the algorithm practice dominate the asymptotically larger term of the algorithm.

Question 5

a

Assume that for . We must show that

.

for some Thus,

b

Assume that for . We must show that .

for some Thus,