Lab 4: Lists and Linked Lists

Due at 11:59pm on 02/22/2016.

Starter Files

Download lab04.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-6 in lab04.py and submit through OK.
  • Questions 7, 8 and 9 are extremely useful practice with lists and linked lists. They are not mandatory, but can be very helpful in understanding both concepts. They can be found in the lab04_extra.py file.
  • Questions 10, 11, and 12 are extra practice. They can also be found in the lab04_extra.py file. It is recommended that you complete these problems on your own time.

Lists

Question 1: How to get Seven?

In each of following, what does the list indexing look like to get the number 7? Ex. x = [7], answer would be x[0]. You can use the interpreter or Python tutor to experiment with your answers.

Use OK to test your knowledge with the following "How to get Seven?" questions:

python3 ok -q sevens -u
>>> x = [1, 3, [5, 7], 9]

______
x[2][1]

>>> x = [[7]]

______
x[0][0]

>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]

______
x[1][1][1][1][1][1][0]

Question 2: If This Not That

Define if_this_not_that, which takes a list of integers i_list, and an integer this, and for each element in i_list if the element is larger than this then print the element, otherwise print that.

def if_this_not_that(i_list, this):
    """Define a function which takes a list of integers `i_list` and an integer
    `this`. For each element in `i_list`, print the element if it is larger
    than `this`; otherwise, print the word "that".

    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
    that
    that
    that
    4
    5
    """

    "*** YOUR CODE HERE ***"

    for elem in i_list:
        if elem <= this:
            print("that")
        else:
            print(elem)

# List comprehension version
def if_this_not_that(i_list, this):
    [print(i) if i > this else print('that') for i in i_list]

Use OK to test your code:

python3 ok -q if_this_not_that

List Comprehension

List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

>>> [i**2 for i in [1, 2, 3, 4] if i%2 == 0]
[4, 16]

is equivalent to

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst += [i**2]
>>> lst
[4, 16]

The general syntax for a list comprehension is

[<expression> for <element> in <sequence> if <conditional>]

The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."

Note: The if clause in a list comprehension is optional.

Question 3: WWPP: Lists?

What would Python print? Try to figure it out before you type it into the interpreter!

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q lists -u
>>> [x*x for x in range(5)]

______
[0, 1, 4, 9, 16]

>>> [n for n in range(10) if n % 2 == 0]

______
[0, 2, 4, 6, 8]

>>> ones = [1 for i in ["hi", "bye", "you"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]

______
[1, 1, 1, '6', '3', '8', '4']

>>> [i+5 for i in [n for n in range(1,4)]]

______
[6, 7, 8]

Question 4: Coordinates

Implement a function coords that takes a function fn, a sequence seq, and a lower and upper bound on the output of the function. coords then returns a list of coordinate pairs (lists) such that:

  • Each (x, y) pair is represented as [x, fn(x)]
  • The x-coordinates are elements in the sequence
  • The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)

See the doctest for examples.

Note: your answer can only be one line long. You should make use of list comprehensions!

def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """

    "*** YOUR CODE HERE ***"
    return ______

    return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

Use OK to test your code:

python3 ok -q coords

Linked Lists (same as rList)

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

Note: 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 5: Link to List

Write a function link_to_list that takes a linked list and converts it to a Python list.

Hint: To check if a linked list is empty, you can use lst == empty. Also, you can combine two Python lists using +.

def link_to_list(linked_lst):
    """Return a list that contains the values inside of linked_lst

    >>> link_to_list(empty)
    []
    >>> lst1 = link(1, link(2, link(3, empty)))
    >>> link_to_list(lst1)
    [1, 2, 3]
    """

    "*** YOUR CODE HERE ***"

    if linked_lst == empty:
        return []
    else:
        return [first(linked_lst)] + link_to_list(rest(linked_lst))

# Iterative version
def link_to_list_iterative(linked_lst):
    """
    >>> link_to_list_iterative(empty)
    []
    >>> lst1 = link(1, link(2, link(3, empty)))
    >>> link_to_list_iterative(lst1)
    [1, 2, 3]
    """
    new_lst = []
    while linked_lst != empty:
        new_lst += [first(linked_lst)]
        linked_lst = rest(linked_lst)
    return new_lst

Use OK to test your code:

python3 ok -q link_to_list

Question 6: Insert-end

Write a function that returns a new linked list that is the same as lst with elem added at the end.

def insert_at_end(lst, elem):
    """Return a linked list that is the same as lst with elem added
    at the end.

    >>> lst1 = insert_at_end(empty, 1)
    >>> print_link(lst1)
    1
    >>> lst2 = insert_at_end(lst1, 2)
    >>> print_link(lst2)
    1 2
    >>> lst3 = insert_at_end(lst2, 3)
    >>> print_link(lst3)
    1 2 3
    """

    "*** YOUR CODE HERE ***"

    if lst == empty:
        return link(elem, empty)
    else:
        return link(first(lst), insert_at_end(rest(lst), elem))

Use OK to test your code:

python3 ok -q insert_at_end

Questions in this section are not required for submission. However, they are very good practice for learning these topics.

Question 7: Reverse (iteratively)

Write a function reverse_iter that takes a list and returns a new list that is the reverse of the original. Use iteration! Do not use lst[::-1] or lst.reverse()!

def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """

    "*** YOUR CODE HERE ***"

    new, i = [], 0
    while i < len(lst):
        new = [lst[i]] + new
        i += 1
    return new

Use OK to test your code:

python3 ok -q reverse_iter

Question 8: List to Link

It would be convenient if we had a way to convert from lists to linked lists. Write a function list_to_link that does exactly that.

Hint: It is much easier to write this recursively, but if you are writing the function iteratively, it might be helpful to reverse the list first.

def list_to_link(lst):
    """Converts a list to a linked list.

    >>> lst = [1, 2, 3, 4]
    >>> r = list_to_link(lst)
    >>> first(r)
    1
    >>> first(rest(rest(r)))
    3
    >>> r = list_to_link([])
    >>> r is empty
    True
    """

    "*** YOUR CODE HERE ***"

    if not lst:
        return empty
    return link(lst[0], list_to_link(lst[1:]))

Use OK to test your code:

python3 ok -q list_to_link

Question 9: 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 CATCAT. 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.

Hint: Use the has_prefix function you just defined!

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).

Extra Questions

We deleted the extra questions because they are the same as homework 3. They were flatten, merge, and interleave.