UNIT 6

TOPICS TO BE COVERED IN THIS UNIT:

1. Searching - Linear and binary search methods
2. Bubble sort
3. Selection sort
4. Insertion sort
5. Quick sort
6. Merge sort

Tutorial-1

1. Write algorithm for binary search using recursive function..


2. The concept of order (Big O) is important because
   1. it can be used to decide the best algorithm that solves a given
      problem.
   2. It determines the minimum size of a problem that can be solved
      in a given system, in a given amount of time
   3. It is the lower bound of the growth rate of the algorithm
   4. It is the average bound of the growth rate of the algorithm


3. The average time complexity of insertion sort is
   1. O(n2)
   2. O(n)
   3. O(1)
   4. O(log n)


4. If n=16, then the value of O(n log n) is
   1. 16
   2. 32
   3. 64
   4. 128


5. Which of the following sorting algorithms does not have a worst case running time complexity of O(n2)?
   1. Insertion sort
   2. Merge sort
   3. Quick sort
   4. Bubble sort


6. What are the advantages in insertion sort than bubble sort.


7. There are 3 different algorithms A1,A2,A3 to solve a given problem with the
   order log(n), log(log(n)) ,n*log(n) respectively. Which is the best algorithm?
   1. A1
   2. A2
   3. A3


8. The way a card game player arranges his cards as he picks them up one by one , is an example of
   1. bubble sort
   2. selection sort
   3. insertion sort
   4. merge sort

Tutorial-2

1. Which of the following sorting methods will be the best if number of swapping done, is the only measure of efficiency?
   1. bubble sort
   2. insertion sort
   3. selection sort
   4. heap sort


2. Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?
   1. Heap sort
   2. Quick sort
   3. Insertion sort
   4. Selection sort


3. As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be
   1. bubble sort
   2. insertion sort
   3. selection sort
   4. heap sort


4. Sorting is not useful for
   1. report generation
   2. minimizing the storage needed
   3. making searching easier and efficient
   4. responding to queries easily


5. Trace the arrangement of elements in the end of each pass while using bubble-sort for the below list
   5 6 2 9 1 4


6. Trace the arrangement of elements in the end of each pass while using insertion sort for the below list
   22 13 17 15 19 8


7. A machine needs a minimum of 100 sec. to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
   1. 50.2 sec
   2. 6.7 sec
   3. 72.7 sec.
   4. 11.2 sec


8. A machine took 200 sec to sort 200 names, using bubble sort.
   In 800 sec. it can approximately sort _ _ _ _ _ _ _ _ _ names
   1. 400
   2. 800
   3. 750
   4. 1600

Beginner problems

1. What do you mean by sorting? Mention the different types of sorting.


2. Explain linear search with a good example.


3. What is the time complexity of binary search?


4. Trace out all passes and steps by hand to sort the following list in bubble sort
   5 2 1 8 7


5. Write algorithm for performing selection sort.


6. Write a program to sort elements of an array using Insertion sort.

Intermediate problems

1. Formulate recursive algorithm for binary search with its timing analysis.
2. Write a program to explain selection sort. Which type of technique does it belong?
3. Compare the advantage and disadvantage of bubble, insertion and selection sort.
4. Sort the following numbers using selection sort and give the required steps.
   96,31,27,42,34,76,61,10,4
(a) Distinguish between linear and binary search methods. (b) Write an algorithm for non-recursive binary search method.
5. Write an algorithm for two-way merge sort. Analyze its time complexity.
6. Derive the time complexity of merge sort.
7. (a) Explain Quick sort with algorithm. (b) Analyze the worst case performance of Quick sort and compare with Selection sort.

Advanced problems

1. Write a program to sort the elements whose worst case is O (n2) and average case is
   O (n log n).
2. Write an algorithm for routine merge(x, lb1, ub1, ub2) that assumes that x [lb1] through
   x [ub1] and x[ub1 + 1] through x[ub2] are sorted and merges the two into x[lb1]
   through x[ub2].
3. Trace through the steps by hand to sort the following list in Quick sort.
   28 7 39 3 63 13 61 17 50 21
4. Write in detail about the following: (a) Selection sort (b) Merge Sort.


5. Suppose that the list contains the integers 3 7 13 17 28 50 21 39 61 63 in this order.
   Trace through the steps of binary search to determine what comparisons of keys are done
   in searching.
   To locate 17 To locate 16


6. Write about Sorting Efficiency, and explain O - notation Analysis.

This Page Is Designed By Rakesh