CS21B: Quiz 5 Study Guide

You should be able to define and explain the following terms:

• Running time of an algorithm
  • Big-O notation (also known as "order notation")
• Searching
  • Linear search, including its input requirements, the details of the algorithm, and its worst-case running time
  • Binary search, including its input requirements, the details of the algorithm, and its worst-case running time
• Sorting
  • Bubble sort, including the details of the algorithm and its worst-case running time
  • Selection sort, including the details of the algorithm and its worst-case running time
• Recursion vs Iteration

Practice problems:

1. True/False 1-5 on page 460
2. Multiple choice problems 1-4 on page 461
3. Discussion questions 1-2 on page 462
4. What are the minimum and maximum possible number of steps linear search will need to find a value in a list of 64 items?
5. What are the minimum and maximum possible number of steps binary search will need to find a value in a list of 64 items?
6. Show the low, high, and mid values for each step of a binary search for the value 7 in this list:

   [2, 4, 5, 10, 14, 18, 22, 31]
   

7. Suppose you were going to sort the following list using selection sort. Show how the list would be changed after one iteration through selection sort. Explain in your own words the key idea of selection sort.

   [12, 3, 7, 1, 8, 2, 5, 4, 10, 9]
   

8. Suppose you were going to sort the same list above using bubble sort. Show how the list would be changed after one interstion through bubble sort. Explain in your own words the key idea of bubble sort.
9. Write an iterative function sumEvenIter(n) that returns the sum of the even numbers between 2 and n inclusive. For example, sumEvenIter(8) would return 2+4+6+8 which is 20.
10. Write a recursive function sumEvenRecur(n) that returns the sum of the even numbers between 2 and n inclusive.
11. Write an interative function countIter(ls, item) that returns a count of how many times the given item appears in the given list. For example, countIter([5, 1, 2, 5, 4, 5], 5) would return 3 since the number 5 appears three times in the list.
12. Write a recursive function countRecur(ls, item) that returns a count of how many times the given item appears in the given list.

Home Page