Applied Algorithms and Structures

Question one

True or false with explanations,

a. The class NP contains some problems that can be solved in polynomial time.

This is true because it has been observed that NP is the class of decision problems with the property that their “yes” instances can be proofed in polynomial time.

b. All of the problems in NP can be solved in worst-case exponential time.

False because it can only solve nearly all but not all of them to solve

c. There are problems that can be reduced to the Hamiltonian circuit problem and for which we have polynomial-time algorithms.

False because there is polynomial-time algorithm has been discovered for an NP-Complete problem.

d. There are problems that the Hamiltonian circuit problem can be reduced to and for which we have polynomial-time algorithms.

True because there are polynomial-time algorithm discovered for an NP-Complete problem

Question two

An asymptotic bound for each of the following (including explanation):

a. T(n) = 3T(n/3) + lg(n)

T (n) = 3T (n/3) + logn.

Let g (n) = T (n)/n.

Then n*g (n) = 3*(n/3)*g (n/3) + logn.

Thus

g (n) = g(n/3) + log n.

This gives g (n) = Sum log n + log n/3 + log n/9 +…

= Θ (Sum 1/logn + 1/ (logn -1) + 1/(log n – 2) + …)

= Θ (Integral 1/x between 1 and logn) = Θ (log log n).

Thus T (n) = n*g (n) = Θ (n*log logn.)

b. T(n) = 3T(n/6) + n

From,

T(n) = n + 3T(6/2)

= n +3(n/6) + 4(n/4) + … + 2i−1) + 2k

[taking i = k & use base case]

= n(1 + k)

= n(1 + log n)

c. T(n) = 9T(n/4) + n

The answer is O(n2) applying case 3 of master theorem.

d. T(n) = 4T(n/2) + n2

We make the use of master theorem algorithms, in the following form; T (n) = aT(n/b) + f(n).

For this assignment, a = 4, b = 2, and f (n) = n2. We make comparison of f (n) with nlogba = nlog24

Thus f (n) = n2 = Θ (n2),

Thus making T (n) = Θ (nlogba log n) = Θ (n2log n).

Question three

a. Writing down a recurrence that counts the number of times the comparison in line 1 is performed on an array of length n.

For single element: T(1) = 1

For N elements: T(N) = 2T(N/2) + N

Two MergeSort calls with N/2 elements, and the Merge takes O(N).

This is a recurrence equation. Solution of this gives T(N) as a function of N, which gives us a big-Oh function.

Consider N=2k.

T(2k) = 2T(2(k-1)) + 2k …. (1)

T(2(k-1)) = 2T(2(k-2)) + 2(k-1) …. (2)

T(2(k-2)) = 2T(2(k-3) ) + 2(k-2) …. (3) ….

T(2) = 2T(20) + 21 …. (k)

b. Writing down the asymptotic version of the running time.

Running time is a function of n

f(n) Î Q(n) such that

2n2 + 3n + 1 = 2n2 + f(n)

Question four

Given the following recurrence relation, where n and k are greater than 0

/0 if n c : =

—————————————

a->b |

|——————————–

< | < | > >

= | =

Question five

A dynamic programming algorithm for solving the Activity Selection problem from chapter 16 fills an n by n table c so that c[1,n] contains the maximal number of schedulable activities. Only the entries for which i <= j are filled. Assuming the table is oriented with row 1 at the top, to compute a value for entry c [i,j], the algorithm must access the i-1 entries to the left of and the j-1 entries below c[i,j].

a. The number of times entry c [i,j] is accessed in terms of i, j, and n.

int i, j, k;

for (i = 0; i < N; ++i)

{

for (j = 0; j < N; ++j)

{

C[i][j] = 0;

for (k = 0; k < N; ++k)

C[i][j] += A[i][k] * B[k][j];}}

b. The Theta-notation for the total number of accesses over all entries

for (ii = 0; ii < N; ii += ib)

{for (kk = 0; kk < N; kk += kb)

for (j=0; j < N; j += 2)

for (i = ii; i < ii + ib; i += 2 )

YummytreeJune 4, 2015 / 10:28 pmI was wondering if these are the correct answers because I wasn’t expecting code for the last question and for Q1 part C and D are the answers swithced?