Solution Manual: 2017

Friday, 25 August 2017

Chapter 3 Exercise 3.1-3, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-3 Explain why the statement, “The running time of algorithm A is at \[O(n^2)\]

O (n^{2})

,” is meaningless.

Solution: Let us assume the running time of the algorithm is T(n). Now, by definition, O-notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying $$T(n) \ge O(n^2)$$ means growth of T(n) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.

For example, $$f(n) = 0$$ is $$O(n^2)$$ for all n. So, $$T(n) \ge f(n)$$ doesn’t tell us anything new as all running times are non-negative.

Chapter 3 Exercise 3.1-2, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-2 Show that for any real constants

a

and

b

, where
$$b > 0 , (n + a)^b =\Theta(n^b)$$

Solution:
To prove this, we have to show that there exists constants $$c_1, c_2, n_0 > 0$$ such that $$0 \le c_1 n^b \le (n + a)^b \le c_2 n^b$$ for all $$n \ge n_0$$
Note that, $$n + a \le 2n ,$$ when $$|a| \le n$$ Also note, $$n + a \ge \frac 1 2 n ,$$ when $$|a| \le \frac n 2$$
Therefore, when $$n \ge 2 \vert a \vert ,$$ $$0 \le \frac n 2 \le n + a \le 2n$$
As b>0, we can raise all the terms of the previous inequality to the power of b without breaking the inequality:
$$\begin {align}
0 \le (\frac n 2)^b & \le (n + a)^b \le (2n)^b \\
\Rightarrow 0 \le \frac 1 {2^b}n^b & \le (n + a)^b \le 2^bn^b
\end {align}$$
So,$$(n + a)^b = \Theta(n^b)$$ because there exists $$c_1 = 1/{2^b},c_2 = 2^b , $$ and $$n_0 = 2 \vert a \vert$$

Thursday, 8 June 2017

Chapter 3 Exercise 3.1-1, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-1 Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ-notation, prove that max(f(n),g(n))=Θ(f(n)+g(n)).

Solution:

To prove this, we have to show that there exists constants $$c_1, c_2, n_0 > 0$$ such that $$0 \le c_1 (f(n) + g(n)) \le \max(f(n), g(n)) \le c_2 (f(n) + g(n))$$ for all $$n \ge n_0$$. As the functions are asymptotically non-negative, we can assume that for some $$n_0 > 0, f(n) \ge 0$$ and $$g(n) \ge 0$$.

n \geq n_{0}

So Far
$$n \ge n_0$$ , $$f(n) + g(n) \ge \max(f(n), g(n))$$
Also note that,
$$f(n) \le \max(f(n), g(n))$$
and $$g(n) \le \max(f(n), g(n)) \\
\therefore f(n) + g(n) \le 2 \max(f(n), g(n)) \\
\Rightarrow \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n))$$
Therefore, we can combine the above two inequalities as follows:
$$0 \le \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n)) \le (f(n) + g(n)) \text { for } n \ge n_0$$
So, $$\max(f(n), g(n)) = \Theta(f(n) + g(n))$$ because there exists $$c_1 = \frac 1 2$$ and $$c_2 = 1$$

Thursday, 25 May 2017

Chapter 2 4 Problem, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2-4 Inversions

Let

A [1 . . n]

be an array of

n

distinct numbers. If

i < j

and

A [i] > A [j]

, then the pair

(i, j)

is called an inversion of

A

List the five inversions of the array $⟨ 2, 3, 8, 6, 1 ⟩$ .
What array with elements from the set $1, 2, \dots, n$ has the most inversions? How many does it have?
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $Θ (n \lg n)$ worst-case time. (Hint: Modify merge sort.)

1. List of Inversions
Inversions in the given array are: (1, 5), (2, 5), (3, 4), (3, 5), and (4, 5). (Note: Inversions are specified by indices of the array, not by values.)

2. Array With Most Inversions
The array with elements from the set

1, 2, \dots, n

with the most inversions will have the elements in reverse sorted order, i.e.

⟨ n, n - 1, \dots, 2, 1 ⟩

.

As the array has

n

unique elements in reverse sorted order, for every unique pair of

(i, j)

, there will be an inversion. So, total number of inversion = number of ways to choose 2 distinct integer from the set

1, 2, \dots, n

(\binom{n}{2})

\frac{n (n - 1)}{2}

.

3. Relationship With Insertion Sort
If we take look at the pseudocode for insertion sort with the definition of inversions in mind, we will realize that the more the number of inversions in an array, the more times the inner while loop will run. The reason being more inversions means most of the array is reverse sorted, i.e. more swaps to perform in the while loop.
So, the higher the number of inversions in an array, the longer insertion sort will take to sort the array.

4. Algorithm to Calculate Inversions
Although a hint to modify merge sort is already given, without that also we should think of divide-and-conquer algorithms whenever we see running time of

Θ (\lg n)

.

As was done in merge sort, we need to recursively divide the array into halfs and count number of inversions in the sub-arrays. This will result in

\lg n

steps and

Θ (n)

operations in each step to count the inversions. All in all a

Θ (n \lg n)

algorithm.

def merge(items, p, q, r):
    L = items[p:q+1]
    R = items[q+1:r+1]
    i = j = 0
    k = p
    inversions = 0
    while i < len(L) and j < len(R):
        if(L[i] < R[j]):
            items[k] = L[i]
            i += 1
        else:
            items[k] = R[j]
            j += 1
            inversions += (len(L) - i)
        k += 1
    if(j == len(R)):
        items[k:r+1] = L[i:]
    return inversions



def mergesort(items, p, r):
    inversions = 0
    if(p < r):
        q = (p+r)/2
        inversions += mergesort(items, p, q)
        inversions += mergesort(items, q+1, r)
        inversions += merge(items, p, q, r)
    return inversions


items = [4,3,2,1,17]
inversions = mergesort(items, 0, len(items)-1)
print items,inversions

Chapter 2 3 Problem, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2-3 Correctness of Horner’s rule

The following code fragment implements Horner’s rule for evaluating a polynomial
$$ \begin {align} P(x) & = \sum _{k = 0}^n a_k x^k \\ & = a_0 + x(a_1 + x(a_2 +· · · + x(a_{n − 1} + xa_n) · · ·)) \end {align} $$

given the coefficients a 0 ; a 1 ; : : : ; a n and a value for x:

y = 0
for i = n downto 0
 y = a_i + x * y

In terms of Θ-notation, what is the asymptotic running time of this code fragment for Horner’s rule?
Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule?
Consider the following loop invariant:. At the start of each iteration of the for loop of lines 2-3, $y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k}$ Interpret a summation with no terms as equaling 0. Your proof should follow the structure of the loop invariant proof presented in this chapter and should show that, at termination, $y = \sum_{k = 0}^{n} a_{k} x^{k}$ .
Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients $a_{0}, a_{1}, . . ., a_{n}$ .

Solution:

1. Asymptotic Running Time

From the pseudocode of Horner’s Rule, the algorithm runs in a loop for all the elements, i.e. it runs at

Θ (n)

time.

2. Comparison with Naive Algorithm

Pseudocode for NAIVE-POLY-EVAL(A, x), where

A

is the array of length

n + 1

consisting of the coefficients

a_{0}, a_{1}, . . ., a_{n}

y = 0
for i = 1 to A.length
    m = 1
    for j = 1 to i - 1
        m = m * x
    y = y + A[i] * m

The above algorithm runs with for inside another for loop

j

multiplications to evaluate

a_{j} x^{j}

and $(n - 1)$ additions in total to evaluate a polynomial. Hence, it does

\sum_{j = 0}^{n} j = n (n + 1) / 2

multiplications and

(n - 1)

additions. Therefore, the algorithm runs at

Θ (n^{2})

time.
This algorithm is obviously worse than Horner’s rule which runs at linear time.

3. Loop Invariant for the While Loop

Initialization: At the start of the first iteration, we have

i = n

. So,

\begin{aligned} y & = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k} \\ = \sum_{k = 0}^{n - (n + 1)} a_{k + n + 1} x^{k} \\ = \sum_{k = 0}^{- 1} a_{k + n + 1} x^{k} \\ = 0 \end{aligned}

As the sum is zero, the loop invariant holds after the first loop.
Maintenance: From the loop invariant, for any arbitrary

0 <= i < n

, at the start of the

i

-th iteration of the while loop of lines 3–5,

y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k}

Now, after the

i

-th iteration,

\begin{aligned} y^{'} & = a_{i} + x \cdot y \\ = a_{i} + x \cdot \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k} \\ = a_{i} x^{0} + \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k + 1} \\ = \sum_{k = - 1}^{n - (i + 1)} a_{k + i + 1} x^{k + 1} \\ = \sum_{k^{'} = 0}^{n - (i + 1)} a_{k^{'} + i} x^{k^{'}} \\ = \sum_{k^{'} = 0}^{n - (i^{'} + 1)} a_{k^{'} + i^{'} + 1} x^{k^{'}} \end{aligned}

So, the loop invariant also holds after the loop.
We make two assumption:

$k^{'} = k + 1$ : This is valid as $k$ is nothing but the summation parameter.
$i^{'} = i - 1$ : This holds as this is precisely the operation done in line 5.

Termination: When the loop terminates, we have

i = - 1

. So,

\begin{aligned} y & = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k} \\ = \sum_{k = 0}^{n - (- 1 + 1)} a_{k - 1 + 1} x^{k} \\ = \sum_{k = 0}^{n} a_{k} x^{k} \end{aligned}

This is precisely what we wanted to calculate.

4. Correctness Argument
When Horner’s rule terminates it successfully evaluates the polynomial as it intended to. This means the algorithm is correct.

Solution Manual

Pages