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
"""
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]]
"""
return ______
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]``````

Use OK to test your code:

``python3 ok -q coords``

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

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

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

[]
[1, 2, 3]
"""
return []
else:

# Iterative version
"""
[]
[1, 2, 3]
"""
new_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)
1
>>> lst2 = insert_at_end(lst1, 2)
1 2
>>> lst3 = insert_at_end(lst2, 3)
1 2 3
"""
if lst == empty:
else:

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

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]
>>> first(r)
1
>>> first(rest(rest(r)))
3
>>> r is empty
True
"""
if not lst:
return empty

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.

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

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
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
"""
``python3 ok -q has_61A_gene``