CIS575-Assignment 3 Solved

1.      Below are 12 functions of n (recall that lg (ln) denotes the binary (natural) logarithm):

                               1.3      n2      2n       n√n      np√n           nlg(n)nln(n)(1.001)n             nn      n!        nlg(n)2n+7

n

Arrange these functions in non-decreasing order of growth; that is, find an arrangement f1 ≤ f2 ≤ ... ≤ f12 of the functions such that f1 ∈ O(f2), f2 ∈ O(f3), ...f11 ∈ O(f12). For each i, you should write fi ≡ fi+1 if fi ∈ Θ(fi+1), but fi < fi+1 otherwise. You do not need to argue for your answers.

2.      In this exercise we shall employ two data structures:

• a queue, with three operations:

–    IsEmpty?() which returns true iff (if and only if) the queue is empty.

–    InsertLast(x) which inserts x at the end of the queue.

–    RemoveFirst() which returns the queue’s first element (which is removed from the queue).

• a priority queue, with three operations:

–    IsEmpty?() which returns true iff the priority queue is empty.

–    Insert(x) which inserts x into the priority queue.

–    RemoveMax() which returns (and removes) the priority queue’s largest element.

The program below takes as input a queue Q and then sorts it (in reverse order), using a priority queue P which we assume is initially empty.

Sort(Q) while not Q.IsEmpty?() x ← Q.RemoveFirst()

P.Insert(x) while not P.IsEmpty?()

x ← P.RemoveMax()

Q.InsertLast(x) return Q

We shall assume that each operation on queues executes in time Θ(1), i.e., constant time (this can be accomplished by a pointer implementation). We shall also assume that priority queues are implemented such that IsEmpty? executes in time Θ(1), whereas Insert and RemoveMax executes in time Θ(lgk) where k is the current size of the priority queue (this can be accomplished by a “heap” implementation, as we shall see later in this course).

Let T(n) be the (worst-case) running time of Sort, given a queue with n elements.

1.   Express T(n) as the sum of two summations (each of the form ). You do not need to argue

for your answer.

2.    Use (1) to find a function f, as simple as possible, such that the T(n) ∈ Θ(f(n)). You should justify your answer, for example by referring to Theorem 3.28 in Howell.

3.      Estimate the running times, in terms of n, of the following three programs. You should give tight bounds, of the form Θ(f(n)) with f as simplified as possible. Justify your answers; this will involve expressing each running time as a sum. (You can assume that arithmetic operations take time in Θ(1), no matter the size of the operands. Recall that the scope of language constructs is determined by indentation, so in (c), k ← k ∗ 2 is part of the while loop but not of the for loop.)

(a)                                                              (b)                                                           (c)

         z ← 0                                                       z ← 0                                                       z ← 0

          for k ← 1 to n ∗ n                                  for k ← 1 to n ∗ n                                 k ← 1

               q ← 1                                                      q ← 1                                                 while k < n

               while q ≤ k                                            s ← k ∗ k                                                  for q ← 1 to k

                     q ← q + 1                                          while q ≤ s                                                   z ← z + 1

                      z ← z + 1                                                q ← q ∗ 2                                           k ← k ∗ 2

z ← z + 1