1 .In a selectionsort of n elements, how many times is the swap function called
in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log
n
D. n^2
Solution: B.
n-1
2 .Selectionsort and quicksort both fall into the same category
of sorting algorithms. What is this category?
* A. O(n log n) sorts
*
B. Divide-and-conquer sorts
* C. Interchange sorts
* D. Average time is
quadratic.
Solution: C.Interchange
sorts reason:Selection sort is not O(n log n) and not a Divide-conquer sort too
and Average time of quicksort is not quadratic.
3 . Suppose that a selectionsort of 100 items has
completed 42 iterations of the main loop. How many items are now guaranteed to
be in their final spot (never to be moved again)?
* A. 21
* B. 41
*
C. 42
* D. 43
Solution: C. 42
4 .Suppose we are
sorting an array of ten integers using a some quadratic sorting algorithm. After
four iterations of the algorithm's main loop, the array elements are ordered as
shown here:
1 2 3 4 5 0 6 7 8 9
Which statement is correct? (Note:
Our selection sort picks largest items first.)
* A. The algorithm might
be either selection sort or insertion sort.
* B. The algorithm might be
selectionsort, but could not be insertionsort.
* C. The algorithm might be
insertionsort, but could not be selectionsort.
* D. The algorithm is neither
selectionsort nor insertionsort.
Solution: C. The algorithm might be insertion
sort, but could not be selection sort.
5 .Suppose we are sorting an array
of eight integers using a some quadratic sorting algorithm. After four
iterations of the algorithm's main loop, the array elements are ordered as shown
here:
2 4 5 7 8 1 3 6
Which statement is correct? (Note: Our
selectionsort picks largest items first.)
* A. The algorithm might be
either selectionsort or insertionsort.
* B. The algorithm might be
selectionsort, but it is not insertionsort.
* C. The algorithm is not
selectionsort, but it might be insertionsort.
* D. The algorithm is neither
selectionsort nor insertionsort.
Solution: C. The algorithm is not
selectionsort, but it might be insertionsort.
6 .When is insertionsort a
good choice for sorting an array?
* A. Each component of the array
requires a large amount of memory.
* B. Each component of the array requires
a small amount of memory.
* C. The array has only a few items out of
place.
* D. The processor speed is fast.
Solution: C. The array has only a few items out
of place.
7 What is the worst-case time for mergesort to sort an array of
n elements?
* A. O(log n)
* B. O(n)
* C. O(n log n)
* D.
O(n^2)
Solution : C. O(n log
n)
8 What is the worst-case time for quicksort to sort an array of n
elements?
* A. O(log n)
* B. O(n)
* C. O(n log n)
* D.
O(n^2)
Solution: D.
O(n^2)
9 .Mergesort makes two recursive calls. Which statement is true
after these recursive calls finish, but before the merge step?
* A. The
array elements form a heap.
* B. Elements in each half of the array are
sorted amongst themselves.
* C. Elements in the first half of the array are
less than or equal to elements in the second half of the array.
* D. None of
the above.
Solution: B. Elements
in each half of the array are sorted amongst themselves.
10 .Suppose we
are sorting an array of eight integers using quicksort, and we have just
finished the first partitioning with the array looking like this:
2 5 1 7
9 12 11 10
Which statement is correct?
* A. The pivot could be
either the 7 or the 9.
* B. The pivot could be the 7, but it is not the
9.
* C. The pivot is not the 7, but it could be the 9.
* D. Neither the 7
nor the 9 is the pivot.
Solution:
A. The pivot could be either the 7 or the 9.
11 .What is the worst-case
time for heapsort to sort an array of n elements?
* A. O(log n)
* B.
O(n)
* C. O(n log n)
* D. O(n^2)
Solution: C. O(n log n)
12.Suppose you
are given a sorted list of N elements followed by f(N) randomly ordered
elements.How would you sort the entire list if
* A. f(N)=O(1)
* B.
f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire
list still to be sortable in O(N) time?
Solution:
A. f(N)=O(1) In this case
insertion sort would be the best ,giving the time complexity of O(N)
B.
f(N)=O(log N) Merge sort is the best option with a time complexity of
O(N)
C.f(N)=O(N^1/2) Merge sort is the best option with a time complexity
of O(N)
D.complexity = f(N)log f(N) + N +f(N)
Clearly f(N) is O(N) for
the complexity to be of O(N)
Now O(N) is an over estimate on the upper
bound of f(N) ,which is quite clear from the first term in the above
expression.
Now let f(N) is of the form k.N^(1/p ).Then with some
simplification we get
f(N)log(f(N)) is O(N ^(2/p)) and now to restrict
the whole expression to O(N)
we need to restrict p to p >= 2
But
f(N)is O(N^(1/p)) which means f(N) can at most be of size N^1/2
.
13.Prove that any algorithm that find an element X in a sorted list of
N elements requires Omega(log N) comparisons.
Solution:The search essentially becomes a
search for X in a binary decision tree and this requires Omega(log N)
comparisons.
14.Prove that sorting N elements with integer keys in the
range 1 < style="font-weight: bold;">Solution: Putting the elements
in to their corresponding buckets is of O(N).Then iteration of the buckets and
printing the corresponding keys as many times as their frequency is of
O(M+N).Hence the total complexity.
15.Suppose you have an array of N
elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm
to sort the array.
Solution:Use
bucket sort with 2 buckets.
16.Prove that any comparison based algorithm
to sort 4 elements requires at least 3 comparisons and at the max
comparisons
Solution:The binary
decision tree has maximum distance of 3 and a maximum distance of 5 ,from the
root to the leaf.As each edge corresponds to a comparison,we need minimum of 3
and maximum of 5 comparisons to sort 4 elements.
17. In how many ways can
2 sorted arrays of combined size N be merged?
Solution:Still up for
debate.Any answers? :)
18.Show that binary insertion may reasonably be
expected to be an O(n log n) sort.
Solution:Binary insertion sort employs
binary search to find the right place to insert new elements, and therefore
performs ceil (log(n!)) comparisons in the worst case, which is Θ(n log n). The
algorithm as a whole still takes Θ(n2) time on average due to the series of
swaps required for each insertion, and since it always uses binary search, the
best case is no longer Ω(n) but Ω(n log n).
19.You are given two sets
of numbers Xi and Yj , where i and j run from 1 to N.
Devise an algorithm to
find the M largest values of Xi −Yj . This algorithm should
not be quadratic
in N, though it is permitted to be quadratic in M.
You should regard N as
being of the order of 20,000 and M as being of the order
of 1,000.
Solution:Use an order-statistic algorithm to
find the Mth largest number in X,partition around that number and sort the M
largest numbers.Repeat this for Y but sorting the M smallest numbers.This can be
done in O(N+M log(M))Now with each of these sub-arrays having M elements,find
the difference between each element of X and Y.We have M difference elements for
each Xi in sorted order and in total M^2 differences.Use merge sort repeatedly
to merge these portions .This is of complexity M^2.Hence the
procedure.
20.If 1024 numbers are drawn randomly in the range 0–127 and
sorted by binary
insertion, about how many compares would you
expect?
Solution:We have 3 comparisons
coming in to the picture ab, a=b.The overall number of comparisons won't change
and it is still of the O(N log N). strictly speaking log(N!)
comparisons.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment