CS21: Quiz 5 Study Guide

In addition to the concepts below, you should also know the concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4. Many of the earlier concepts -- especially functions -- are fundamental to what we've been studying recently.

You should understand the following topics:

Lists of lists
Searching: linear vs binary
Sorting: selection, bubble, insertion
Analysis of algorithms (number of steps)
Big-O notation (O(N) vs O(logN), etc)

Practice problems:

True/False questions:
- In the worst case, Linear search requires a number of steps proportional to the size of the list being searched (True/False)
- The python in operator performs a binary search (True/False)
- Binary search is an NlogN algorithm (True/False)
- The number of times N can be divided by 2 is log base-two of N (True/False)
- Binary search is always faster than Linear search (True/False)
Approximately how many iterations will binary search need to find a value in a list of 1 million items?
Place these algorithm classes in order from best to worst: N, logN, N*N, NlogN
What is log(1024,2) in python? What about log(2048,2)?

How many steps are required for each of the following? Assume that n is a postive integer.

#-------------------------------------------
for i in range(n):
  for j in range(n):
    print i, j
#-------------------------------------------
while n > 1:
  print n
  n = n/2
#-------------------------------------------
for i in range(n):
  for j in range(10):
    print i, j
#-------------------------------------------
i = 0
while i < n:
  print i
  i = i + 1
#-------------------------------------------
while n > 0
  print n
#-------------------------------------------

Show the index values for low, high, and mid for each step in searching the list L for the value x using binary search. The indices for L are shown above the list.
```
     0   1   2   3   4   5   6   7   8
L = [10, 17, 44, 45, 46, 58, 67, 99, 122]
x = 99
```

If you are running selectionSort on the following list, L:

L = [9, 35, 18, 200, 0, 6, 43, 21]

Which of the following represents L after 3 iterations of the outer loop in the algorithm:

A. [0, 6, 9, 18, 21, 35, 43, 200]
B. [0, 6, 9, 200, 18, 35, 43, 21]
C. [0, 9, 35, 18, 200, 6, 43, 21]
D. [0, 6, 9, 35, 200, 18, 43, 21]

If you are running insertionSort on the following list, L:
```
L = [22, 41, 56, 7, 79, 75, 89]
```
Which value in the list would be the first one to be swapped?
What would it be swapped with?
If you are running bubbleSort on the following list, L:
```
L = [22, 41, 56, 7, 79, 75, 89]
```
Show how the list would change after completing one iteration of the outer loop of the algorithm.

Given the following assignment:

   ls = [[1, "dog"], [3, "fish"], [2, "cat"]]

What are the value and type of the following expressions:

  (1) len(ls)
  (2) ls[1]
  (3) ls[1][1]
  (4) ls[1][0] < ls[2][0]
  (5) ls[2][1] + ls[1][1]