#
Homework 8

*Due at 11:59:59 pm on Thursday, 4/13/2023.*

## Instructions

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

**Submission:** When you are done, submit with `python3 ok --submit`

. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org.

**Readings:** This homework relies on following references:

Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.

For example, let's say that we have the function `get_x`

which is
defined as follows:

```
def get_x(x):
return x
```

`get_x`

has one expression in it. That one expression takes the same
amount of time to run, no matter what x is, or more importantly, how
large x gets. This is called constant time, or O(1).

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

```
def foo(n):
i = 1
sum = 0
while i <= n:
sum = sum + i
i = i + 1
return sum
```

This loop has two statements in it `sum = sum + i`

and `i = i + 1.`

Each statement is a constant time operation, since the amount of time each statement takes does not depend on the input to the function `n`

.
In C88C, we are not concerned with how long primitive functions such as addition,
multiplication, and variable assignment take to run. Rather we are
concerned with *how many more times a loop is
executed* or *how many more recursive calls* occur as
the input increases. In this example, we execute the loop `n`

times, and
for each iteration, we only execute constant time operations, so we get
an order of growth of O(*n*).

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

O(n)

```
def bar(n):
i = 1
a = 1
b = 0
while i <= n:
temp = a
a = a + b
b = temp
i = i + 1
return a
```

O(n^2)

```
def bar(n):
sum = 0
a, b = 0, 0
while a < n:
while b < n:
sum += (a*b)
b += 1
b = 0
a += 1
return sum
```

## Efficiency

There is nothing to submit for this part. But doing these problems will be good practice. The solutions are given right below the question and to see them you must highlight them.

For each question find the asymptotic runtime in big theta notation.

### Question 1

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

Answer: O(

*n*

^{2})).

### Question 2

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

Answer: O(log(

*n*)).

## Inheritance

### Question 3: Errors

It is often said that nothing in life is certain but death and taxes. For a programmer or data scientist, however, nothing is certain but encountering errors.

In Python, there are two primary types of errors, both of which you are likely familiar with: syntax errors and exceptions. Syntax errors occur when the proper structure of the language is not followed, while exceptions are errors that occur during the execution of a program. These include errors such as ZeroDivisionError, TypeError, NameError, and many more!

Under the hood, these errors are based in the concepts of object orientation, and all exceptions are class objects. If you're interested in more detailed explanations of the structure of exceptions as well as how to create your own, check out this article from the Python documentation! In the meantime, we'll implement our own version of an `Error`

class

Complete the `Error`

, `SyntaxError`

, and `ZeroDivisionError`

classes such that
they create the correct messages when called.

- The
`SyntaxError`

and`ZeroDivisionError`

classes inherit from the`Error`

class and add functionality that is unique to those particular errors. Their code is partially implemented for you. - The
`add_code`

method adds a new helpful message to your error, while the`write`

method should print the output that you see when an error is raised. Do not worry if that code already is already defined; for this problem, it is safe to overwrite it. - You can access the parent class methods using the super() function

```
class Error:
"""
>>> err1 = Error(12, "error.py")
>>> err1.write()
error.py:12
"""
def __init__(self, line, file):
"*** YOUR CODE HERE ***"
def format(self):
return self.file + ':' + str(self.line)
def write(self):
print(self.format())
class SyntaxError(Error):
"""
>>> err1 = SyntaxError(17, "lab10.py")
>>> err1.write()
lab10.py:17 SyntaxError : Invalid syntax
>>> err1.add_code(4, "EOL while scanning string literal")
>>> err2 = SyntaxError(18, "lab10.py", 4)
>>> err2.write()
lab10.py:18 SyntaxError : EOL while scanning string literal
"""
type = 'SyntaxError'
msgs = {0 : "Invalid syntax", 1: "Unmatched parentheses", 2: "Incorrect indentation", 3: "missing colon"}
def __init__(self, line, file, code=0):
"*** YOUR CODE HERE ***"
def format(self):
"*** YOUR CODE HERE ***"
def add_code(self, code, msg):
"*** YOUR CODE HERE ***"
class ZeroDivisionError(Error):
"""
>>> err1 = ZeroDivisionError(273, "lab10.py")
>>> err1.write()
lab10.py:273 ZeroDivisionError : division by zero
"""
type = 'ZeroDivisionError'
def __init__(self, line, file, message='division by zero'):
"*** YOUR CODE HERE ***"
def format(self):
end = self.type + ' : ' + self.message
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q Error`

Use OK to test your code:

`python3 ok -q SyntaxError`

Use OK to test your code:

`python3 ok -q ZeroDivisionError`

## Linked Lists

A linked list is either an empty linked list (`Link.empty`

) **or** a first value
and the rest of the linked list.

```
class Link:
"""
>>> s = Link(1, Link(2, Link(3)))
>>> s
Link(1, Link(2, Link(3)))
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), rest_str)
```

To check if a `Link`

is empty, compare it against the class attribute
`Link.empty`

. For example, the below function prints out whether or not the link it is handed is empty:

```
def test_empty(link):
if link is Link.empty:
print('This linked list is empty!')
else:
print('This linked list is not empty!')
```

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (

`first`

) and a reference to another linked list (`rest`

) which contains the rest of the values in the list.

### Question 4: Link to List

Write a function `link_to_list`

that converts a given `Link`

to a
Python list.

```
def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> link_to_list(Link(88))
[88]
>>> link_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q link_to_list`

### Question 5: Every Other

Implement `every_other`

, which takes a linked list `s`

. It mutates `s`

such
that all of the odd-indexed elements (using 0-based indexing) are removed from
the list. For example:

```
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s
Link('a', Link('c'))
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True
```

If `s`

contains fewer than two elements, `s`

remains unchanged.

Do not return anything!

`every_other`

should mutate the original list.

```
def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s) # removes 2, 4
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length) # removes 3
>>> odd_length
Link(5, Link(1))
>>> two_items = Link(6, Link(7))
>>> every_other(two_items) # removes 7
>>> two_items
Link(6)
>>> singleton = Link(4)
>>> every_other(singleton) # doesn't remove anything
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q every_other`

### Question 6: Deep Map

Implement `deep_map`

, which takes a function `f`

and a `link`

. It returns a
*new* linked list with the same structure as `link`

, but with `f`

applied to any
element within `link`

or any `Link`

instance contained in `link`

.

The `deep_map`

function should recursively apply `fn`

to each of that
`Link`

's elements rather than to that `Link`

itself.

*Hint*: You may find the built-in `isinstance`

function useful.

```
def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.
>>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
>>> print_link(s)
<1 <2 3> 4>
>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
>>> print_link(s) # unchanged
<1 <2 3> 4>
>>> t = Link(s, Link(Link(Link(5))))
>>> print_link(t)
<<1 <2 3> 4> <<5>>>
>>> print_link(deep_map(lambda x: 2 * x, t))
<<2 <4 6> 8> <<10>>>
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q deep_map`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`