#
Lab 12: Final Review (Optional)

*Due at 11:59:59 pm on 5/10/2024.*

## Starter Files

Download lab12.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

**This lab assignment is OPTIONAL**. This means it does not count toward your final grade, and completing it will NOT earn you any extra credit. It is intended to help with studying for the final exam. Note that the topics listed in this lab are NOT comprehensive of the scope of the final.

You do not have to submit to Gradescope, although there is an assignment with the autograder if you want to check your work.

Solutions are available here.

## Control

### Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

```
def second_max(lst):
"""
Return the second highest number in a list of positive integers.
>>> second_max([3, 2, 1, 0])
2
>>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
6
>>> second_max([1, 5, 5, 5, 1])
5
>>> second_max([5, 6, 6, 7, 1])
6
>>> second_max([5, 6, 7, 7, 1])
7
"""
"*** YOUR CODE HERE ***"
highest = 0
second_highest = 0
for num in lst:
if num >= highest:
second_highest = highest
highest = num
elif num < highest and num > second_highest:
second_highest = num
return second_highest
```

Use OK to test your code:

`python3 ok -q second_max`

## Higher Order Functions

### Question 2: Count van Count

Consider the following implementations of `count_factors`

and `count_primes`

:

```
def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count
def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count
def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and n
```

The implementations look quite similar! Generalize this logic by writing a
function `count_cond`

, which takes in a two-argument predicate function ```
mystery_function(n,
i)
```

. `count_cond`

returns a count of all the numbers from 1 to `n`

that satisfy
`mystery_function`

.

Note: A predicate function is a function that returns a boolean (`True`

or `False`

).

```
def count_cond(mystery_function, n):
"""
>>> def divisible(n, i):
... return n % i == 0
>>> count_cond(divisible, 2) # 1, 2
2
>>> count_cond(divisible, 4) # 1, 2, 4
3
>>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
6
>>> def is_prime(n, i):
... return count_cond(divisible, i) == 2
>>> count_cond(is_prime, 2) # 2
1
>>> count_cond(is_prime, 3) # 2, 3
2
>>> count_cond(is_prime, 4) # 2, 3
2
>>> count_cond(is_prime, 5) # 2, 3, 5
3
>>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
"*** YOUR CODE HERE ***"
i, count = 1, 0
while i <= n:
if mystery_function(n, i):
count += 1
i += 1
return count
```

Use OK to test your code:

`python3 ok -q count_cond`

## Lists and Dictionaries

### Question 3: Deep-Len

A list that contains one or more lists as elements is called a *deep*
list. For example, `[1, [2, 3], 4]`

is a deep list.

Write a function `deep_len`

that takes a list and returns its deep
length. See the doctests for the function's behavior.

*Hint*: you can check if something is a list by using the built-in
`type`

function. For example,

```
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
```

```
def deep_len(lst):
"""Returns the deep length of the list.
>>> deep_len([1, 2, 3]) # normal list
3
>>> x = [1, [2, 3], 4] # deep list
>>> deep_len(x)
4
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> deep_len(x)
6
"""
"*** YOUR CODE HERE ***"
if not lst:
return 0
elif type(lst[0]) == list:
return deep_len(lst[0]) + deep_len(lst[1:])
else:
return 1 + deep_len(lst[1:])
```

Use OK to test your code:

`python3 ok -q deep_len`

### Question 4: Counter

Implement the function `counter`

which takes in a string of words `message`

, and returns a
dictionary where each key is a word in the message, and each value is the number
of times that word is present in the original string.

```
def counter(message):
""" Returns a dictionary of each word in message mapped
to the number of times it appears in the input string.
>>> x = counter('to be or not to be')
>>> x['to']
2
>>> x['be']
2
>>> x['not']
1
>>> y = counter('run forrest run')
>>> y['run']
2
>>> y['forrest']
1
"""
word_list = message.split()
"*** YOUR CODE HERE ***"
result_dict = {}
for word in word_list:
if word in result_dict:
result_dict[word] += 1
else:
result_dict[word] = 1
return result_dict
```

Use OK to test your code:

`python3 ok -q counter`

## Recursion

### Question 5: Knapsack

You're are a thief, and your job is to pick among `n`

items that are of
different weights and values. You have a knapsack that supports `c`

pounds, and
you want to pick some subset of the items so that you maximize the value you've
stolen.

Define `knapsack`

, which takes a list `weights`

, list `values`

and a capacity
`c`

, and returns that max value. You may assume that item 0 weighs
`weights[0]`

pounds, and is worth `values[0]`

; item 1 weighs `weights[1]`

pounds, and is worth `values[1]`

; etc.

```
def knapsack(weights, values, c):
"""
>>> w = [2, 6, 3, 3]
>>> v = [1, 5, 3, 3]
>>> knapsack(w, v, 6)
6
"""
"*** YOUR CODE HERE ***"
if weights == []:
return 0
else:
first_weight, rest_weights = weights[0], weights[1:]
first_value, rest_values = values[0], values[1:]
with_first = first_value + knapsack(rest_weights, rest_values, c - first_weight)
without_first = knapsack(rest_weights, rest_values, c)
if first_weight <= c:
return max(with_first, without_first)
return without_first
```

Use OK to test your code:

`python3 ok -q knapsack`

### Question 6: repeated, repeated

In Homework 2 you encountered the `repeated`

function, which takes
arguments `f`

and `n`

and returns a function equivalent to the nth
repeated application of `f`

. This time, we want to write `repeated`

recursively. You'll want to use `compose1`

, given below for your
convenience:

```
def compose1(f, g):
""""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
```

```
def repeated(f, n):
"""
>>> f = lambda x: x + 1
>>> g = repeated(f, 1)
>>> g(5)
6
>>> h = repeated(f, 3)
>>> h(5)
8
>>> f2 = lambda x: x * 2
>>> g2 = repeated(f2, 3)
>>> g2(3)
24
"""
"*** YOUR CODE HERE ***"
if n == 0:
return lambda x: x # Identity
return compose1(f, repeated(f, n - 1))
```

Use OK to test your code:

`python3 ok -q repeated`

## OOP and Inheritance

### Question 7: Mint

Complete the `Mint`

and `Coin`

classes so that the coins created by a mint have
the correct year and worth.

- Each
`Mint`

instance has a`year`

stamp. The`update`

method sets the`year`

stamp to the`current_year`

class attribute of the`Mint`

class. - The
`create`

method takes a subclass of`Coin`

and returns an instance of that class stamped with the`mint`

's year (which may be different from`Mint.current_year`

if it has not been updated.) Hint: Check out the`create_animal`

method in this demo. - A
`Coin`

's`worth`

method returns the`cents`

value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the`current_year`

class attribute of the`Mint`

class.

```
class Mint:
"""A mint creates coins by stamping on years.
The update method sets the mint's stamp to Mint.current_year.
>>> mint = Mint()
>>> mint.year
2020
>>> dime = mint.create(Dime)
>>> dime.year
2020
>>> Mint.current_year = 2100 # Time passes
>>> nickel = mint.create(Nickel)
>>> nickel.year # The mint has not updated its stamp yet
2020
>>> nickel.worth() # 5 cents + (80 - 50 years)
35
>>> mint.update() # The mint's year is updated to 2100
>>> Mint.current_year = 2175 # More time passes
>>> mint.create(Dime).worth() # 10 cents + (75 - 50 years)
35
>>> Mint().create(Dime).worth() # A new mint has the current year
10
>>> dime.worth() # 10 cents + (155 - 50 years). 155 is because this dime instance has year 2020
115
>>> Dime.cents = 20 # Upgrade all dimes!
>>> dime.worth() # 20 cents + (155 - 50 years)
125
>>> m = Mint()
>>> n = m.create(Nickel)
>>> n.worth()
5
>>> n.year = 2015
>>> n.worth() # 5 cents + (160 - 50 years). 160 is from 2175 - 2015
115
"""
current_year = 2020
def __init__(self):
self.update()
def create(self, coin):
"*** YOUR CODE HERE ***"
return coin(self.year)
def update(self):
"*** YOUR CODE HERE ***"
self.year = Mint.current_year
class Coin:
cents = 0 # Default value of 0. This value will be overridden in subclasses.
def __init__(self, year):
self.year = year
def worth(self):
"The worth is a coin's face value + 1 cent for each year over age 50."
"*** YOUR CODE HERE ***"
return self.cents + max(0, Mint.current_year - self.year - 50)
class Nickel(Coin):
cents = 5
class Dime(Coin):
cents = 10
```

Use OK to test your code:

`python3 ok -q Mint`

## Linked Lists

### Question 8: Insert

Implement a function `insert`

that takes a `Link`

, a `value`

, and an
`index`

, and inserts the `value`

into the `Link`

at the given `index`

.
You can assume the linked list already has at least one element. Do not
return anything — `insert`

should mutate the linked list.

Note: If the index is out of bounds, you can raise an`IndexError`

with:`raise IndexError`

```
def insert(link, value, index):
"""Insert a value into a Link at the given index.
>>> link = Link(1, Link(2, Link(3)))
>>> print_link(link)
<1 2 3>
>>> insert(link, 9001, 0)
>>> print_link(link)
<9001 1 2 3>
>>> insert(link, 100, 2)
>>> print_link(link)
<9001 1 100 2 3>
>>> insert(link, 4, 5)
IndexError
"""
"*** YOUR CODE HERE ***"
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
elif link.rest is Link.empty:
raise IndexError
else:
insert(link.rest, value, index - 1)
# iterative solution
def insert(link, value, index):
while index > 0 and link.rest is not Link.empty:
link = link.rest
index -= 1
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
else:
raise IndexError
```

Use OK to test your code:

`python3 ok -q insert`

## Trees

### Question 9: Path

Write a function `path`

that returns the path from the root of the tree to the given value `target`

as a list if it exists and `[]`

if it does not. You can assume all values are unique.

```
def path(t, target):
"""
>>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
>>> path(t, 2)
[9, 7, 2]
>>> path(t, 5)
[9, 5]
>>> path(t, 8)
[]
"""
"*** YOUR CODE HERE ***"
if t.value == target:
return [target]
elif t.is_leaf():
return []
else:
for b in t.branches:
rest = path(b, target)
if rest:
return [t.value] + rest
return []
```

Use OK to test your code:

`python3 ok -q path`

## Iterators and Generators

### Question 10: Str

Write an iterator that takes a string as input and outputs the letters in order when iterated over.

```
class Str:
def __init__(self, str):
self.str = str
def __iter__(self):
return iter(self.str)
```

That works (why?), but just kidding.

```
class Str:
"""
>>> hey_iter = Str('hey')
>>> for char in hey_iter:
... print(char)
h
e
y
>>> list(hey_iter)
[]
"""
def __init__(self, str):
"*** YOUR CODE HERE ***"
self.str = str
self.i = -1
def __iter__(self):
"*** YOUR CODE HERE ***"
return self
def __next__(self):
"*** YOUR CODE HERE ***"
self.i += 1
if self.i >= len(self.str):
raise StopIteration
return self.str[self.i]
```

Use OK to test your code:

`python3 ok -q Str`

### Question 11: Generate permutations

Given a list of unique elements, a *permutation* of the list is a
reordering of the elements. For example, `[2, 1, 3]`

, `[1, 3, 2]`

, and
`[3, 2, 1]`

are all permutations of the list `[1, 2, 3]`

.

Implement `generate_perms`

, a generator function which takes in a `lst`

and
yields all the unique permutations of `lst`

one at a time (see doctest for examples).

```
def generate_perms(lst):
"""
Generates the permutations of lst one by one.
>>> perms = generate_perms([1, 2, 3])
>>> hasattr(perms, '__next__')
True
>>> p = list(perms)
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
if lst == []:
"*** YOUR CODE HERE ***"
yield [] else:
for perm in generate_perms(lst[1:]):
for i in range(len(lst)):
"*** YOUR CODE HERE ***"
yield perm[:i] + [lst[0]] + perm[i:]
```

Use OK to test your code:

`python3 ok -q generate_perms`

Feel free to replace the `for`

loops with list comprehensions
if you would rather use that.

## Efficiency

There is no code to submit for this part.

### Question 12

What is the asymptotic run time of the baz function?```
def baz(n):
i = 1
sum = 0
while i <= n:
sum += bam(i)
i += 1
return sum
def bam(n):
i = 1
sum = 0
while i <= n:
sum += i
i += 1
return sum
```

Highlight the text on the line below this line to see the solution:

Answer: O(*n*^{2})).

### Question 13

What is the asymptotic run time of the bonk function?

```
def bonk(n):
sum = 0
while n >= 2:
sum += n
n = n / 2
return sum
```

Highlight the text on the line below this line to see the solution:

Answer: O(log(*n*)).

## Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

`lab12.py`