Exercises: Lists, Binary Search, and Procedures

Let nums ← [4, 9, 1, 7]. Remember that AP list positions start at 1.

1. a) What is nums[2]?

1. b) What is LENGTH(nums)?

1. c) What is LENGTH(nums) after APPEND(nums, 5)?

list ← [10, 20, 30]

INSERT(list, 2, 15)

REMOVE(list, 1)

What is the final content of list? Show the list after each step.

Binary search requires something about the data. Which of these lists could be searched directly with binary search? Explain.

1. i) [2, 5, 8, 11]

ii) [9, 3, 7, 1]

iii) ["ant", "bee", "cat"]

Use binary search to look for 26 in this sorted list. At each step, check the item at position ⌊(low + high) / 2⌋, where positions start at 1.

[3, 8, 12, 17, 21, 26, 30, 35, 41]

1. a) List, in order, the values that are checked.

1. b) How many items were checked in total? How does this compare with a sequential search for the same value?

PROCEDURE countAbove(list, limit)

{

  count ← 0

  FOR EACH item IN list

  {

    IF (item > limit)

    {

      count ← count + 1

    }

  }

  RETURN(count)

}

1. a) What does countAbove([72, 85, 90, 64, 88], 80) return?

1. b) What does countAbove([72, 85, 90, 64, 88], 90) return?

1. c) Describe in one sentence what the procedure does.

PROCEDURE mystery(a, b)

{

  IF (a > b)

  {

    RETURN(a)

  }

  ELSE

  {

    RETURN(b)

  }

}

1. a) Evaluate mystery(4, 9).

1. b) Evaluate mystery(mystery(3, 8), 5).

1. c) What does the procedure do? Identify the parameters and the return value.

A school's sorted list has 1,000,000 student names.

1. a) In the worst case, about how many items does a sequential search check? About how many does binary search check? (Hint: $2^{20} = 1{,}048{,}576$.)

1. b) Suppose the list is not sorted and you only need to search it once. Is it better to sort it first and use binary search, or to use sequential search? Justify your answer.

1. c) Suppose instead the list will be searched thousands of times each day. Which approach is better, and why?

PROCEDURE average(list)

{

  total ← 0

  FOR EACH x IN list

  {

    total ← total + x

  }

  RETURN(total / LENGTH(list))

}

1. a) Trace average([80, 90, 70, 100]). What is returned?

1. b) What goes wrong if the list is empty? Rewrite the procedure so that it returns 0 for an empty list.

1. c) Explain how procedural abstraction helps a teacher who uses this procedure in many parts of a gradebook program.