Discussion 11: Final Review

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Now switch to Pensieve:

  • Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Getting Started

Everybody say your name and the non-Data/CS course that you're most excited about taking next semester.

Linked Lists

A linked list is a Link object or Link.empty.

You can mutate a Link object s in two ways:

  • Change the first element with s.first = ...
  • Change the rest of the elements with s.rest = ...

You can make a new Link object by calling Link:

  • Link(4) makes a linked list of length 1 containing 4.
  • Link(4, s) makes a linked list that starts with 4 followed by the elements of linked list s. 
class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    <3 4 5>
    """
    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:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

Q1: Linear Sublists

Definition: A sublist of linked list s is a linked list of some of the elements of s in order. For example, <3 6 2 5 1 7> has sublists <3 2 1> and <6 2 7> but not <5 6 7>.

Definition: A linear sublist of a linked list of numbers s is a sublist in which the difference between adjacent numbers is always the same. For example <2 4 6 8> is a linear sublist of <1 2 3 4 6 9 1 8 5> because the difference between each pair of adjacent elements is 2.

Implement linear which takes a linked list of numbers s (either a Link instance or Link.empty). It returns the longest linear sublist of s. If two linear sublists are tied for the longest, return either one.

Your Answer
Run in 61A Code
Solution 
def linear(s):
    """Return the longest linear sublist of a linked list s.

    >>> s = Link(9, Link(4, Link(6, Link(7, Link(8, Link(10))))))
    >>> linear(s)
    Link(4, Link(6, Link(8, Link(10))))
    >>> linear(Link(4, Link(5, s)))
    Link(4, Link(5, Link(6, Link(7, Link(8)))))
    >>> linear(Link(4, Link(5, Link(4, Link(7, Link(3, Link(2, Link(8))))))))
    Link(5, Link(4, Link(3, Link(2))))
    """
    def complete(first, rest):
        "The longest linear sublist of Link(first, rest) with difference d."
        if rest is Link.empty:
            return Link(first, rest)
        elif rest.first - first == d:
            return Link(first, complete(rest.first, rest.rest))
        else:
            return complete(first, rest.rest)
    if s is Link.empty:
        return s
    longest = Link(s.first) # The longest linear sublist found so far
    while s is not Link.empty:
        t = s.rest
        while t is not Link.empty:
            d = t.first - s.first
            candidate = Link(s.first, complete(t.first, t.rest))
            if length(candidate) > length(longest):
                longest = candidate
            t = t.rest
        s = s.rest
    return longest

def length(s):
    if s is Link.empty:
        return 0
    else:
        return 1 + length(s.rest)
There are three cases:
  • If rest is empty, return a one-element list containing just first.
  • If rest.first is in the linear sublist that starts with first, then build a list that contains first, and rest.first.
  • Otherwise, complete(first, rest.rest).
This while loop is creating a candidate linear sublist for every two possible starting values: s.first and t.first. The rest of the linear sublist must be in t.rest.

Document the Occasion

Please all fill out the attendance form (one submission per person per week).

Scheduling time: This is the last discussion, but you could schedule a meeting with your group next week to study for the exam. Your regular lab room and time should be available during RRR week if you want to use it.