Q1. You are given an unsorted list containing integer values with duplicates. Describe a most efficient algorithm to remove all duplicates from this list. Derive the time complexity (Big O) for your algorithm.
Q2. Let A be an array of n distinct integers. Assume that the integers in A are sorted, i.e. A[i] < A[j], where 0 <= i < j < n. The algorithm count(x, y) returns the number of integers in A which are greater than x and less than y, where x < y. For example, if A = {5, 10, 33, 49, 66, 75, 82, 95, 100},then count(47, 85) returns 4.
Describe a most efficient algorithm to implement the algorithm for count(x, y). Derive the time complexity for your algorithm.
Q3. . The following array is to be sorted in ascending order. Use the QuickSort algorithm to rearrange the array. Clearly show the internal state of the array after each pass of the sorting process.
|
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
34
|
125
|
5
|
19
|
87
|
243
|
21
|
-3
|
117
|
36
|
Q4. Give a Big-Oh characterization, in terms of n, of the running firm of the following algorithm. A is an array of integer values. Explain your answer.
1) ()Algorithm Ex1(A) :
for i <- 2 to length[A] Key <- A[i]
j <= i-l
while j> 0 and A[ j]> key
A[j+1] <- A[j]
*- j-1 A[j+1] <- key
2) ()Algorithm Ex2(A, target) :
s <- 0
Left<-0
Right <-len(A)-1
while left
Mid <- (left+right)/2
if ( A[mid]=)
return true
else if (A[mid]>target) Right<-mid -1
else
Left< -mid+1
return false
Q5.Let T be a binary tree with n nodes (T may be realized with an array list or a linked structure). Give a linear algorithm that uses the methods of the binary tree interface to traverse the nodes of T in pre-order manner. Since operations associated with visiting each node is constant, the running time of the algorithm is O(n).
Q6. Insert the following values into an initially empty BST tree:
6 3 8 12 13 20 17 15 14
You must clearly show each step of the insertion and all actions needed to complete the insertion.
Q7. Use substitution method to show that the solution of T(n) = T(n/2)+1 is O(Ig n).
Q8. Let X[1::n] and Y [1::n] be two arrays, each containing n numbers already in sorted order.Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.