Computer Science 161.01

Homework 11

 Due Wednesday, April 17th at 9:30AM

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”, “Jackson”,

                       “Lewis”, “Stevens”, “Young”);

 

a)      Assume desiredName = “Davis”.

 

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 SortingAlgorithms.

Practice also using my Sorting Demo web sites:

SelectionSortDemo.htm   BubbleSort.htm   InsertionSort.htm

 

THEN…DO PROBLEMS 33 through 38 on page 238.