In addition to the concepts below, you should also know the
concepts that were tested on all of the previous quizzes:
You should be able to define and explain the following terms:
- Analysis of algorithms (number of steps, O(N) vs O(logN) vs O(N*N), etc)
- Sorting: selection, bubble, and insertion sort
- Swapping two values in a list
- Recursion and iteration
- 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:
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]
- Which algorithm requires time directly proportional to the size of the input?
- linear search
- binary search
- merge sort
- 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 two versions of each of the following functions...one version using
iteration and one using recursion:
- sum all values in a given list of integers
- return True if a list is sorted/in order, False if not
- count/return how many times a given value (v) is found in a list (L)
- find the largest number in a list
- Draw a stack diagram for the following program. Show what the
stack would look like at it's largest point.
n = 5
ans = factorial(n)
if x == 0:
return x * factorial(x-1)