Due at 11:59pm on 07/09/2015.

## Starter Files

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

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be graded.

• To receive credit for this lab, you must complete Questions 1, 2, 3, and 4 in lab06.py and submit through OK.
• Questions 5 and 6 are extra practice. They can be found in the lab06_extra.py file. It is recommended that you complete these problems on your own time.

Python has many built-in types of sequences: lists, ranges, and strings, to name a few. In this lab, we instead construct our own type of sequence called a linked list. A linked list is a simple type of sequence that is comprised of multiple links that are connected. Each `link` is a pair where the `first` element is an item in the linked list, and the `second` element is another `link`.

• Constructors:

• `link(first, rest)`: Construct a linked list with `first` element and the next link `rest`.
• `empty`: The empty linked list.
• Selectors

• `first(s)`: Returns the first element in the given linked list `s`.
• `rest(s)`: Returns the rest of the linked list `s`.
• Other

• `is_link(s)`: Returns `True` if `s` is a linked list.
• `print_link(s)`: Prints out the linked list `s`.

We can construct the Linked list shown above by using the constructors. The `first` element of this Linked list is 12 while the `rest` is another Linked list that contains 99 and 37:

``````>>> x = link(12, link(99, link(37)))
>>> first(x)
12
>>> first(rest(x))
99
>>> first(rest(rest(x)))
37``````

Notice that we can just use `link(37)` instead `link(37, empty)`. This is because the second argument of the `link` constructor has a default argument of `empty`.

### Question 1: Length

Implement the `len_link(lst)` function, which calculates the length of a linked list.

``````def len_link(lst):
"""Returns the length of the link.

4
0
"""
if lst == empty:
return 0

Use OK to test your code:

``python3 ok -q len_link``

### Question 2: Sum

Write a function that takes in a linked list `lst` and a function `fn` which is applied to each number in `lst` and returns the sum.

``````def sum_linked_list(lst, fn):
""" Applies a function FN to each number in LST and returns the sum
of the resulting values

>>> square = lambda x: x * x
>>> double = lambda y: 2 * y
30
44
"""
if lst == empty:
return 0

# Iterative Solution
sum = 0
while lst != empty:
sum += fn(first(lst))
lst = rest(lst)
return sum``````

Use OK to test your code:

``python3 ok -q sum_linked_list``

### Question 3: Map

Write `map`, which takes a one argument function and a linked list as arguments, and returns a linked list of the results produced by applying the procedure to each element in the list.

``````def map(fn, lst):
"""Returns a list of the results produced by applying f to each
element in lst.

>>> print_link(map(lambda x: x * x, my_list))
1 4 9 16
bulbasaur
charmander
squirtle
None None None
"""
if lst == empty:
return empty
else:

Use OK to test your code:

``python3 ok -q map``

### Question 4: Insert

Implement the `insert` function that inserts an item at a specific index in the linked list. If the index is greater than the current length, you should insert the item at the end of the list.

Hint: This will be much easier to implement using recursion, rather than using iteration!

Note: We are not actually inserting the item into the original linked list. Instead, we are creating a copy of the original linked list, but with the provided item added at the specified index. The original linked list stays the same.

``````def insert(lst, item, index):
""" Returns a link matching lst but with the given item inserted at the
specified index. If the index is greater than the current length, the item
is appended to the end of the list.

>>> new = insert(lst, 9001, 1)
1 9001 2 3
"""
if lst == empty:
elif index == 0:
else:

Use OK to test your code:

``python3 ok -q insert``

## Extra Questions

The following questions are for extra practice — they can be found in the the lab06_extra.py file. It is recommended that you complete these problems on your own time.

### Question 5: DNA Sequence Matching

The mad scientist John Harvey Hilfinger has discovered a gene that compels people to enroll in CS 61A. You may be afflicted!

A DNA sequence is represented as a linked list of elements `A`, `G`, `C` or `T`. This discovered gene has sequence `C A T C A T`. Write a function `has_61A_gene` that takes a DNA sequence and returns whether it contains the 61A gene as a sub-sequence.

First, write a function `has_prefix` that takes two linked lists, `s` and `prefix`, and returns whether `s` starts with the elements of `prefix`. Note that `prefix` may be larger than `s`, in which case the function should return `False`.

``````def has_prefix(s, prefix):
"""Returns whether prefix appears at the beginning of linked list s.

3 4 6 6
>>> has_prefix(x, empty)
True
True
False
True
False
>>> has_prefix(x, x)
True
False
"""
if prefix == empty:
return True
elif s == empty:
return False
else:
return first(s) == first(prefix) and has_prefix(rest(s), rest(prefix))``````

Use OK to test your code:

``python3 ok -q has_prefix``

Next, write a function `has_sublist` that takes two linked lists, `s` and `sublist`, and returns whether the elements of `sublist` appear in order anywhere within `s`.

``````def has_sublist(s, sublist):
"""Returns whether sublist appears somewhere within linked list s.

>>> has_sublist(empty, empty)
True
G A T T A C A
>>> has_sublist(x, empty)
True
False
False
True
True
False
"""
if has_prefix(s, sublist):
return True
elif s == empty:
return False
else:
return has_sublist(rest(s), sublist)``````

Use OK to test your code:

``python3 ok -q has_sublist``

Finally, write `has_61A_gene` to detect `C A T C A T` within a linked list `dna` sequence.

``````def has_61A_gene(dna):
"""Returns whether linked list dna contains the CATCAT gene.

C A T G C A T
>>> has_61A_gene(dna)
False
G T A C A T C A T G
>>> has_61A_gene(dna)
True
>>> has_61A_gene(end)
False
"""
return has_sublist(dna, catcat)``````

Use OK to test your code:

``python3 ok -q has_61A_gene``

Note: Subsequence matching is a problem of importance in computational biology. CS 176 goes into more detail on this topic, including methods that handle errors in the DNA (because DNA sequencing is not 100% correct).

### Question 6: Count Change (with Linked Lists!)

A set of coins makes change for `n` if the sum of the values of the coins is `n`. For example, if you have 1-cent, 2-cent and 4-cent coins, the following sets make change for `7`:

• 7 1-cent coins
• 5 1-cent, 1 2-cent coins
• 3 1-cent, 2 2-cent coins
• 3 1-cent, 1 4-cent coins
• 1 1-cent, 3 2-cent coins
• 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for `7`. Write a function `count_change` that takes a positive integer `n` and a linked list of the coin denominations and returns the number of ways to make change for `n` using these coins:

``````def count_change(amount, denominations):
"""Returns the number of ways to make change for amount.

50 25 10 5 1
>>> count_change(7, denominations)
2
>>> count_change(100, denominations)
292
16 8 4 2 1
>>> count_change(7, denominations)
6
>>> count_change(10, denominations)
14
>>> count_change(20, denominations)
60
"""