A linked list has exactly n nodes. The elements in these nodes are
selected from the set {0, 1,...,
n}. There are no duplicates in the list. Design an O(n)
worst case time algorithm to find which one of the elements from the above
set is missing in the given linked list.
2.
Write a procedure that will reverse a linked list while traversing it only
once. At the conclusion, each node should point to the node that was previously
its predecessor: the head should point to the node that was formerly at
the end, and the node that was formerly first should have a null link.
3.
How would one implement a queue if the elements that are to be placed on
the queue are arbitrary length strings? How long does it take to enqueue
a string?
4.
Let A be an array of size n, containing positive or negative
integers, with A[1]
< A[2] <...< A[n]. Design an efficient algorithm
(should be more efficient than O(n)) to find an isuch
that A[i] = i provided such an i exists. What
is the worst case computational complexity of your algorithm ?
5.
Consider an array of size n. Sketch an O(n) algorithm
to shift all items in the array k places cyclically counterclockwise.
You are allowed to use only one extra location to implement swapping of
items.
6.
In some operating systems, the least recently used (LRU) algorithm
is used for page replacement. The implementation of such an algorithm will
involve the following operations on a collection of nodes.
use a node.
replace the LRU node by a new node.
Suggest a good data structure for implementing such a collection of nodes.
7.
A queue Q contains the items a_{1},
a_{2},..., a_{n}, in that order with a_{1}
at the front and a_{n} at the back. It is required to transfer
these items on to a stack S (initially empty) so that a_{1}
is at the top of the stack and the order of all other items is preserved.
Using enqueue and dequeue operations for the queue and push and pop operations
for the stack, outline an efficient O(n) algorithm to accomplish
the above task, using only a constant amount of additional storage.
8.
A queue is set up in a circular array C[0..n
- 1] with front and rear defined as usual. Assume that n
- 1 locations in the array are available for storing the elements (with
the other element being used to detect full/empty condition). Derive a
formula for the number of elements in the queue in terms of rear,
front, and n.
9.
Let p_{1}p_{2}...p_{n}
be a stack-realizable permutation of 12...n.
Show that there do not exist indices i < j < k
such that p_{j} < p_{k}
< p_{i}.
10.
Write recursive algorithms for the following problems:
(a)
Compute the number of combinations of n objects taken m at
a time.
(b)
Reverse a linked list.
(c)
Reverse an array.
(d)
Binary search on an array of size n.
(e)
Compute gcd of two numbers n and m.
11.
Consider the following recursive definition:
g(i, j) =
i
(j = 1)
(2.1)
g(i, j) =
j
(i = 1)
(2.2)
g(i, j) =
g(i - 1, j) + g(i,
j - 1)
else
(2.3)
Design an O(mn) iterative algorithm to compute g(m,
n) where m and n are positive integers.
12.
Consider polynomials of the form:
p(x) = c_{1}x^{e1}
+ c_{2}x^{e2}...c_{1}x^{en};
where e_{1}
> e_{2}...> e_{n}
0. Such polynomials can be represented by a linked lists in which each
cell has 3 fields: one for the coefficient, one for the exponent, and one
pointing to the next cell. Write procedures for
(a)
differentiating,
(b)
integrating,
(c)
adding,
(d)
multiplying
such polynomials. What is the running time of these procedures as a function
of the number of terms in the polynomials?
13.
Suppose the numbers 1, 2, 3, 4, 5 and 6 arrive in an input stream in that
order. Which of the following sequences can be realized as the output of
(1) stack, and (2) double ended queue?