[Solved] CIS575-Assignment 3

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

1.3 n2 2n nn npn 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 f₁ f₂ f₁₂ of the functions such that f₁ O(f₂), f₂ O(f₃), f₁₁ O(f₁₂). For each i, you should write f_i f_i+1 if f_i (f_i+1), but f_i < f_i+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 queues 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 queues largest

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 )

(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