Recursion
def func(n):
print(n)
if n == 1:
return
else:
func(n - 1)
print(func(3))
Output?
3
2
1
countdown recursively
64 25 12 22 11
First pass of a selection sort?
11 25 12 22 64
For binary search, the "worst case scenario" (when the algorithm takes the most number of steps) is when an element is ______?
Not in the list!
Philosophy I
classes = [ “CS1”, “Calculus”, “Chemistry”, “English"]
schedule = open( 'file.txt' , “w” )
for x in classes:
schedule.write(x+”\n”)
schedule.close()
CS1
Calculus
Chemistry
English
def func( s ) :
if len(s) <= 1 :
return s
else:
return s[-1] + func( s[:-1])
print(func("1034"))
Output?
4301; this is the algorithm to reverse a string recursively
3rd pass of an insertion sort?
23 || 1 10 5 2
1 23 || 10 5 2
1 10 23 || 5 2 <--- 3rd pass
|| separates out sorted sublist
x = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Using binary search, how many comparisons
does it take to find 23 in the list?
3
First mid is 16, then 56, then 23!
OR 1 pass
if you do midpoint + 1 instead of midpoint -1....
file.txt:
Welcome to
your last discussion
good luck
on
the exam!
---------------------------
jeopardy = open( ’file.txt’ , “r” )
c = 0
for x in jeopardy:
c = c + 1
print (c)
jeopardy.close()
What is the output? As in, what is "c"?
5; it's a line count.
def func(x):
if x == 1:
return 1
else:
return (x * func(x-1))
result = func(3)
print(result)
Ouput?
6; this is the factorial recursion algorithm!
original array: 1 10 23 -2
-2 10 23 1
-2 1 23 10
-2 1 10 23
What type of sort is this?
Selection sort
def linearSearch_v1 (L , element ) :
for i in range (0, len(L)):
if L[i] == element :
return True
elif _______ :
return False
return False
Linear search returns true if the target element is equal to array at index i. What is the "else if" case where the linear search would return False?
L[i] > element
def func(A):
B = []
for x in range(len(A)):
B = B+ A[x]
return B
C = func([[3,8,9],[1,9,7], [7,2]])
print(C)What is the output?
[3,8,9,1,9,7, 7,2]; this is the iterative method of flattening a 2D list.
def func(x):
print(x)
if (x == 1):
return 5
return func(x-1) + x
print(func(6))
Output?
25
adds 6+5+4+3+2+5
8 5 7 1 9 3
1 5 7 8 9 3
_ _ _ _ _ _
1 3 5 8 9 7
1 3 5 7 9 8
1 3 5 7 8 9
Fill in the missing pass!
1 3 7 8 9 5
def binarySearchIterative(search_list,number):
if len(search_list) < 1:
return False
low = 0
high = len(search_list)-1
if search_list[low] == number or search_list[high] == number:
return True
while low < (high - 1):
midpoint = (low+high)//2
if num_list[midpoint] == number:
return True
elif num_list[midpoint] < number:
____ = midpoint
else:
_____ = midpoint
return False
Assume search_list is sorted; what are the two missing blanks of the algorithm?
low
high
gym.txt:
Susan / 11:00a / Yoga / Rm313
Bob / 8:00a / Spin / Rm202
Alex / 3:00p / Cardio / Rm105
-------------------------------------
file = open('gym.txt','r')
x = file.readlines()
y = [[a.lstrip().rstrip() for a in b.split("/")] for b in x]
print(y[2][2])
What's the output?
Cardio
def printSomething(n):
if (n < 1):
return
for i in range(0, n):
print("*", end = " ")
print("\n", end = "")
printSomething(n - 1)
printSomething(5)
What is the output: EXACT answer only!
*****
****
***
**
*
program to recursively print triangle
def insertionSort (L) :
for i in range(1, len(L)):
val = L[i]
j = i – 1
while (j >= 0) and (L[j] > val):
L[___] = L[j]
j = j – 1
L[___] = val
return L
Fill in the blanks of the insertion sort algorithm.
def binarySearchRecursive(search_list, item):
if len(search_list) == 0:
return False
else:
midpoint = len(search_list)//2
if search_list[midpoint]==item:
return True
else:
if item<search_list[midpoint]:
return binarySearchRecursive(______,item)
else:
return binarySearchRecursive(______,item)
Assume search_list is sorted; what are the missing blanks of the algorithm?
search_list[:midpoint]
search_list[midpoint+1:]
x = [[6, 5, 2], [9, 0, 1], [3, 7, 8]]
a = 0
for i in range(3):
a = a + x[i][i]
b = 0
for j in range(3):
b = b + x[3-j-1][j]
print(a+b)
19.
a = 14, b = 5. a is the descending diagonal sum and b is the ascending diagonal sum.