Quiz 5 Study Guide
You are responsible for all material covered through the end of Week 10.
Python concepts
In addition to all concepts from Quiz 4, you should understand the following:
-
Searching: linear search, binary search
-
Sorting: bubble sort, selection sort
-
Analysis of algorithms, and run times:
-
\(\log N\) — logarithmic (binary search)
-
\(N\) — linear (linear search)
-
\(N^2\) — quadratic (bubble/selection sort)
-
You should be able to:
-
trace the execution of linear and binary search
-
trace the execution of selection sort and bubble sort
-
compare different runtime analyses for algorithms
Practice problems
-
For each iteration of the loop in
binarySearch(x, lst)
, show the index values forlow
,high
, andmid
, and the value stored at locationmid
. What will be returned by this function call?x = 67 lst = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99] index 0 1 2 3 4 5 6 7 8 9 10 low | high | mid | lst[mid] - - - - - - - - - - - - - | | | | | | | | | | | |
-
For each iteration of the loop in
binarySearch(y, lst)
, 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 lst = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99] index 0 1 2 3 4 5 6 7 8 9 10 low | high | mid | lst[mid] - - - - - - - - - - - - - - | | | | | | | | | | | |
-
Binary search is much faster than linear search, so why don’t we use it for every search problem?
-
Which algorithm requires time directly proportional to the size of the input list?
-
linear search
-
binary search
-
selection sort
-
-
Consider a pair of nested loops in a function:
def loops(N): for i in range(N): for j in range(N): print("hello")
In terms of the parameter \(N\), how many times will the function print "hello"? That is, is the run time logarithmic, linear, quadratic, or something else?
-
Show how the list
L=[17,4,19,3,11,8]
would be changed after selection sort does its first 3 swaps. -
What would the output of the following code be?
def mystery(lst, idx): modded = False if lst[idx] % 2 == 0: lst[idx] = lst[idx] + 1 modded = True return modded def main(): L = [2, 3, 4, 5, 6] k = 2 ans = mystery(L, k) print(L) print("Answer: %s" % (ans)) main()
Draw the stack diagram to show the contents of the stack just before returning from
mystery
. What is the output of the program?