Design and Analysis of Algorithms
Homework 1
Put each of the problems on a separate sheet of paper, and make sure your name is on
each sheet. To hand them in, staple them together and bring them to the class on due date.
Please make sure to express your algorithms in pseudo-code when directed (see the course
textbook for the proper pseudo-code style), and always provide justi cation for your answer
when asked to give the running time of an algorithm. Be brief and concise, and draw pictures
where appropriate.
Problem 1.
a) Show that if f(n) is O(g(n)) and d(n) is O(h(n)), then f(n) d(n) is O(g(n) h(n)).
b) Show that 3(n + 1)5 + 2n3 logn is O(n5).
c) Algorithm A executes 10n2 logn operations, while algorithm B executes n3 operations.
Determine the minimum integer value n0 such that A executes fewer operations than
B for n n0.
Problem 2.
a) What does the following algorithm do? Analyze its worst-case running time, and express
it using \Big-Oh" notation.
Algorithm Foo (a, n):
Input: two integers, a and n
Output: ?
k 0
b 1
while k 0 do
if k mod 2 = 0 then
k k=2
c c c
else
k k 1
b b c
return b
Problem 3.
a) Describe the output of the following series of stack operations on a single, initially empty
stack:
push(5), push(3), pop(), push(2), push(8), pop(), push(9), push(1), pop(), push(7),
push(6), pop(), pop(), push(4), pop(), pop().
b) Describe the output of the following series of queue operations on a single, initially empty
queue:
enqueue(5), enqueue(3), dequeue(), enqueue(2), enqueue(8), dequeue(), enqueue(9),
enqueue(1), dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(), enqueue(4),
dequeue(), dequeue().
c) Describe in pseudo-code a linear-time algorithm for creating a copy stack S0 of a stack S.
As the result, you must end up with two identical stacks S0 and S. To access the stack,
you are only allowed to use the methods of stack ADT.
d) Describe how to implement two stacks using one array. The total number of elements in
both stacks is limited by the array length; all stack operations should run in O(1) time.
Problem 4. In year 2069 the eleventh hovercraft of the class MARK III came o the
assembly lines of the Boeing Company’s (misnamed) rotorcraft division. This hovercraft was
called \Nebuchadnezzar." Unfortunately, the core libraries of Nebuchadnezzar were corrupted
during installation, so the only uncorrupted data structure left was a simple stack. Boeing
software engineers set out to reimplement all the other data structures in terms of stacks,
and they started out with queues.
a) The following are parts of their original implementation of a queue using two stacks
(in stack and out stack). Analyze the worst-case running times of its enqueue and
dequeue methods and express them using \Big-Oh" notation.
Algorithm enqueue(o)
in stack.push(o)
Algorithm dequeue()
2
while (! in stack.isEmpty()) do
out stack.push(in stack.pop())
if (out stack.isEmpty()) then
throw a QueueEmptyException
return obj out stack.pop()
while (! out stack.isEmpty()) do
in stack.push(out stack.pop())
return return obj;
b) Sometime in the early twenty- rst century a war erupted between the humans and the
machines, which humans lost. 120 years after its creation, the hovercraft Nebuchadnez-
zar ended up in the hands of the human resistance leader and hacker extraordinaire,
Morpheus. Always on the run, the rebels needed much faster software to escape the
machines, so Morpheus and his crew set out to optimize Neb’s code. Thus a new
implementation of a queue (still using two stacks) was born:
Algorithm enqueue(o)
in stack.push(o)
Algorithm dequeue()
if (out stack.isEmpty()) then
while (! in stack.isEmpty()) do
out stack.push(in stack.pop())
if (out stack.isEmpty()) then
throw a QueueEmptyException
return out stack.pop()
What is the worst-case complexity of performing a series of 2n enqueue and n dequeue
operations in an unspeci ed order? Express this using \Big-Oh" notation.
Problem 5. A program Thunk written by a graduate student uses an implementation
of the sequence ADT as its main component. It performs atRank, insertAtRank and
remove operations in some unspeci ed order. It is known that Thunk performs n24 atRank
operations, n insertAtRank operations, and n2 remove operations. Which implementation
of the sequence ADT should the student use in the interest of e ciency: the array-based one
or the one that uses a doubly-linked list? Explain.