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.

Linked Lists

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.

Linked List

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.

    >>> lst = link(1, link(2, link(3, link(4))))
    >>> len_link(lst)
    4
    >>> len_link(empty)
    0
    """
"*** YOUR CODE HERE ***"
if lst == empty: return 0 return 1 + len_link(rest(lst))

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
    >>> lst1 = link(1, link(2, link(3, link(4))))
    >>> sum_linked_list(lst1, square)
    30
    >>> lst2 = link(3, link(5, link(4, link(10))))
    >>> sum_linked_list(lst2, double)
    44
    """
"*** YOUR CODE HERE ***"
if lst == empty: return 0 return fn(first(lst)) + sum_linked_list(rest(lst), fn) # Iterative Solution def sum_linked_list(lst, fn): 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.

    >>> my_list = link(1, link(2, link(3, link(4, empty))))
    >>> print_link(map(lambda x: x * x, my_list))
    1 4 9 16
    >>> pokemon = link('bulbasaur', link('charmander', link('squirtle', empty)))
    >>> print_link(map(print, pokemon))
    bulbasaur
    charmander
    squirtle
    None None None
    """
"*** YOUR CODE HERE ***"
if lst == empty: return empty else: return link(fn(first(lst)), map(fn, rest(lst)))

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.

    >>> lst = link(1, link(2, link(3)))
    >>> new = insert(lst, 9001, 1)
    >>> print_link(new)
    1 9001 2 3
    """
"*** YOUR CODE HERE ***"
if lst == empty: return link(item, empty) elif index == 0: return link(item, lst) else: return link(first(lst), insert(rest(lst), item, index-1))

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.

    >>> x = link(3, link(4, link(6, link(6))))
    >>> print_link(x)
    3 4 6 6
    >>> has_prefix(x, empty)
    True
    >>> has_prefix(x, link(3))
    True
    >>> has_prefix(x, link(4))
    False
    >>> has_prefix(x, link(3, link(4)))
    True
    >>> has_prefix(x, link(3, link(3)))
    False
    >>> has_prefix(x, x)
    True
    >>> has_prefix(link(2), link(2, link(3)))
    False
    """
"*** YOUR CODE HERE ***"
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
    >>> aca = link('A', link('C', link('A')))
    >>> x = link('G', link('A', link('T', link('T', aca))))
    >>> print_link(x)
    G A T T A C A
    >>> has_sublist(x, empty)
    True
    >>> has_sublist(x, link(2, link(3)))
    False
    >>> has_sublist(x, link('G', link('T')))
    False
    >>> has_sublist(x, link('A', link('T', link('T'))))
    True
    >>> has_sublist(link(1, link(2, link(3))), link(2))
    True
    >>> has_sublist(x, link('A', x))
    False
    """
"*** YOUR CODE HERE ***"
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.

    >>> dna = link('C', link('A', link('T')))
    >>> dna = link('C', link('A', link('T', link('G', dna))))
    >>> print_link(dna)
    C A T G C A T
    >>> has_61A_gene(dna)
    False
    >>> end = link('T', link('C', link('A', link('T', link('G')))))
    >>> dna = link('G', link('T', link('A', link('C', link('A', end)))))
    >>> print_link(dna)
    G T A C A T C A T G
    >>> has_61A_gene(dna)
    True
    >>> has_61A_gene(end)
    False
    """
"*** YOUR CODE HERE ***"
cat = link('C', link('A', link('T'))) catcat = link('C', link('A', link('T', cat))) 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.

    >>> denominations = link(50, link(25, link(10, link(5, link(1)))))
    >>> print_link(denominations)
    50 25 10 5 1
    >>> count_change(7, denominations)
    2
    >>> count_change(100, denominations)
    292
    >>> denominations = link(16, link(8, link(4, link(2, link(1)))))
    >>> print_link(denominations)
    16 8 4 2 1
    >>> count_change(7, denominations)
    6
    >>> count_change(10, denominations)
    14
    >>> count_change(20, denominations)
    60
    """
"*** YOUR CODE HERE ***"
if amount < 0 or denominations == empty: return 0 elif amount == 0: return 1 using_coin = count_change(amount - first(denominations), denominations) not_using_coin = count_change(amount, rest(denominations)) return using_coin + not_using_coin