Computer Science 161
Homework 11
Due Wednesday April 19th
at 1:30PM
Read pp. 213-235 covering Algorithms
1. 10 points On a separate sheet of paper, draw a tree structure that represents the binary search on a list of 31 entries.
2. 8 points
Determine exactly (as a fraction) the average number of
comparisons required for binary search on a list of 31 entries. Show your work on a separate sheet.
3. 8 points
Complete the tables below as you track the values of first, last and mid the
following list of names.
list = new Array(“Adams”,
“Baker”, “Davis”, “
“Lewis”, “Stevens”,
“Young”);
a)
Assume
desiredName = “
first last__mid
0
6 3 list[mid]>desiredName,so set last to
mid-1
in 2nd row
b)
Assume
desiredName = “Lee”.
first last__mid
0
6 3
4. 24 points Read pp. 223-229 covering 3 Basic Sorting Algorithms.
Practice also using my Sorting Demo web sites: SelectionSortDemo.htm BubbleSort.htm InsertionSort.htm
Then complete the following exercises:
a)
The following array has undergone 2 passes
of the Selection Sort algorithm.
Show the array again after one more pass:
6 9 | 76 39 55
46 20 39 13 24
b) The
effect of the first insertion by the Insertion Sort algorithm is shown below.
Show the array again after each of the next 2 insertions:
73 | 14 21 22 75 39 11 61 48 43 (initial array)
14 73 | 21 22 75 39 11 61 48 43 (array after 1 insertion)
c)
The following array has undergone 2 passes
of the Bubble Sort algorithm.
Show
the array again after one more pass:
86 88 88 98 24 36 84 75 54 18
18 | 86 88 88 98 24 36 84 75 54
18 24 |86 88 88 98 36 54 84 75