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 terms and concepts:

Searching: linear vs binary search
Analysis of algorithms (number of steps)
Big-O notation (O(N) vs O(logN), etc)
Sorting: selection, bubble, and insertion sort
swapping two values in a list
complexity (big O, number of steps) of searching and sorting algorithms
string comparisons ("alice" < "zelda")
list of lists

Practice problems:

True/False questions:
- Linear search requires a number of steps proportional to the size of the list being searched (T/F)
- The python in operator performs a binary search (T/F)
- Binary search is an NlogN algorithm (T/F)
- The number of times N can be divided by 2 (before reaching 1) is log base-two of N (T/F)
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?

#############################################
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
#############################################

Show the index values for low, high, and mid for each step in searching the list L for the value x using binary search.

x = 99
L = [-20, -12, -4, 1, 7, 44, 45, 46, 58, 67, 99, 145]     low   mid   high
       0    1   2  3  4   5   6   7   8   9  10   11      ----------------

Show how the following list would be changed after selection sort does its first 3 swaps:
```
[15, 99, 4, 30, 3, 82, 7, 42]
```
Consider the following function, oneLoop, which is similar to the inner loop from bubble sort:
```
def oneLoop(ls):
  print "in oneLoop"
  for j in range(len(ls)-1):
    if ls[j] > ls[j+1]:
      tmp = ls[j+1]
      ls[j+1] = ls[j]
      ls[j] = tmp
```
(1) Given the list ls = [17, 4, 19, 3, 11, 8], what is ls after one call to oneLoop(ls)?
(2) Given the following main function, trace through its execution showing all program output and drawing the stack right before the call to function oneLoop returns:
```
def main( ):                    
  print "in main"
  my_list = [6, 8, 19, 3, 7]
  print my_list
  oneLoop(my_list)
  print my_list 
```
Which algorithm requires time directly proportional to the size of the input?
1. linear search
2. binary search
3. merge sort
4. selection sort
Write a sort function (any sort) that takes in a list and sorts it in place. Show what a call to your sort function would look like from main.
Write a function to return the index of the smallest item in a given list.