- analysis of algorithms/big-O notation (
*O*(*n*) vs*O*(*l**o**g*(*n*)) vs*O*(*n***n*)) - sorting: bubble vs selection sort
- swapping two values in a list
- recursion
- base case

- recursive call

- recursion on numbers, strings, and lists

- compare different runtime analyses for algorithms
- design a recursive function
- draw the call stack for a recursive function

- How many
*steps*are required for each of the following?

```
#############################################
for i in range(N):
for j in range(N):
print("%d %d" % (i,j))
#############################################
while N > 1:
print(N)
N = N/2
#############################################
for i in range(N):
for j in range(10):
print(i, j)
#############################################
```

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

Write an expression for the asymptotic runtime of `oneLoop`

, in terms of the length *n* of the list `L`

.

- Show how the following list would be changed after selection sort does its first 3 swaps:

For concreteness, here is some Python code for selection sort:

```
def findLargest(ls, top):
large = 0
for i in range(top+1):#want to include top too
if ls[large] < ls[i]:
large=i
return large
def selectionSort(ls):
N = len(ls)
top = N-1
while top>0:
j = findLargest(ls, top)
swap(ls, j, top)
top = top-1
```

`[15, 99, 4, 30, 3, 82, 7, 42]`

- Show how the following list would be changed after bubble sort does one iteration of the outer loop.

`[17, 4, 19, 3, 11, 8]`

Which algorithm requires time directly proportional to the size of the input list?

- linear search
- binary search
- bubble sort
- selection sort

Write a recursive function

`longestInList(L)`

that returns the longest string in`L`

, a list of strings. You can assume that`L`

has at least one string.Then, draw the stack as it would look at its

*largest*(i.e, the deepest part of the recursion when it hits a base case), when the function is called on the list`['awesome', 'recursive', 'code']`

. pdf of solutionWrite a recursive function

`countdown(n)`

which simulates a countdown to a rocket launch. If you call`blastoff(4)`

you should see the following output:

```
4...
3...
2...
1...
BLASTOFF!
```

This function is only called for its side-effects (printing), and not its return value.

Write a recursive function

`recBinary(x,L)`

which implements a*recursive*version of binary search for item`x`

in list`L`

. It should return`True`

if`x`

is in`L`

, and`False`

otherwise.For additional recursive function problems, try problems on this page.