Quiz 5 Study Guide
You are responsible for all material covered through the end of Week 10 (Sorting).
In addition to all concepts from Quiz 4, you should understand the following:
Python concepts

Analysis of algorithms, and run times:

\$\log N\$ — logarithmic (e.g. binary search)

\$N\$ — linear (e.g. linear search)

\$N^2\$ — quadratic (e.g. selection sort)


Searching: linear vs binary search

Sorting: bubble vs selection sort

Swapping two values in a list
You should be able to

compare different runtime analyses for algorithms

trace the execution of different searching and sorting algorithms
Practice problems

NOTE: There are additional searchspecific questions in the
searchWorksheet.txt
file in your week 10 class notes directory.
Which algorithm requires time directly proportional to the size of the input list?

linear search

binary search

bubble sort

selection sort


What would the output of the following code be?
for i in range(2): for j in range(3): print("i:%d j:%d" % (i,j))

Consider a similar pair of nested loops in a function:
def loops(N): for i in range(N): for j in range(N): print("i:%d j:%d" % (i,j))
In terms of the parameter \$N\$, how many times will this function print given, i.e., is the run time, logarithmic, linear, quadratic, or something else?

Consider the following function,
oneLoop(L)
, which is similar to the inner loop from bubble sort:def oneLoop(L): for j in range(len(L)1): if L[j] > L[j+1]: tmp = L[j+1] L[j+1] = L[j] L[j] = tmp
Suppose we run
oneLoop
on the listL=[17,4,19,3,11,8]
. What are the new contents ofL
? 
Show how the list
L=[17,4,19,3,11,8]
would be changed after selection sort does its first 3 swaps: 
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 O(N) algorithm (T/F)

The number of times N can be divided by 2 before reaching 1 is the log (base 2) of N (T/F)


How many steps would it take to do binary search on a list of size 1 million, when the item you are searching for is NOT in the list?

Binary search is much faster than linear search, so why don’t we use it for every search problem?

For each iteration of the loop in
binarySearch(x, L)
, show the index values forlow
,high
, andmid
, and the value stored at locationmid
. What will be returned by this function call?x = 67 L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99] 0 1 2 3 4 5 6 7 8 9 10 low  high  mid  L[mid]                         

For each iteration of the loop in
binarySearch(y, L)
, show the index values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?y = 4 L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99] 0 1 2 3 4 5 6 7 8 9 10 low  high  mid  L[mid]                          
