Q1: Let Array A [1: 60] = 51, 52, …., 109, 110. How many element comparisons are performed by Algorithm BINARYSEARCH when searching for the following values of x?

(a) 20   (b) 57   (c) 150

Q2: (a)  Illustrate the operation of Algorithm SELECTIONSORT on the following array, showing the contents of the array after each outer-most iteration.

9

14

11

3

4

7

(b)  How many element comparisons are performed by the algorithm?

Q3: (a)  Illustrate the operation of Algorithm INSERTIONSORT on the following array, showing the contents of the array after each outer-most iteration.

9

14

11

3

4

7

(b)  How many element comparisons are performed by the algorithm?

Q4: (a)  Illustrate the operation of Algorithm BOTTOMUPSORT on the following array, showing the contents of the array after each outer-most iteration.

9

14

11

3

4

7

(b)  How many element comparisons are performed by the algorithm?

Q5: In your own words (not more than 50 words), explain how do the below algorithm sorts an array of n elements.

* the SELECTIONSORT

* the BOTTOMUPSORT

* the INSERTIONSORT