CS 4349 — Advanced Algorithm Design and Analysis, Homework 2
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,