If there are fewer than 3 people in your group, merge your group with another group in the room. If your group has 6 or more students, you're welcome to split into two sub-groups and then sync up at the end. If you want two separate Pensieve documents for the two sub-groups, just have one sub-group add 1000 to their group number.

Switch to Pensieve:

• Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number as the room number (which was in the email that assigned you to this discussion). As long as you all enter the same number (any number), you'll all be using a shared document.

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.

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

Getting Started

Everybody say your name and your birthday and then tell the group about your favorite birthday party you've attended (either for your birthday or someone else's).

Pro tip: Groups tend not to ask for help unless they've been stuck for a looooooong time. Try asking for help sooner. We're pretty helpful! You might learn something.

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) + ')'

Drawing time: Pick a way for your group to draw diagrams. Paper, a whiteboard, or a tablet, are all fine. If you don't have anything like that, ask another group in the room if they have extra paper.

Q1: Strange Loop

In lab, there was a Link object with a cycle that represented an infinite repeating list of 1's.

>>> ones = Link(1)
>>> ones.rest = ones
>>> [ones.first, ones.rest.first, ones.rest.rest.first, ones.rest.rest.rest.first]
[1, 1, 1, 1]
>>> ones.rest is ones
True

Implement strange_loop, which takes no arguments and returns a Link object s for which s.rest.first.rest is s.

Draw a picture of the linked list you want to create, then write code to create it.

Q2: Sum Two Ways

Implement both sum_rec and sum_iter. Each one takes a linked list of numbers s and a non-negative integer k and returns the sum of the first k elements of s. If there are fewer than k elements in s, all of them are summed. If k is 0 or s is empty, the sum is 0.

Use recursion to implement sum_rec. Don't use recursion to implement sum_iter; use a while loop instead.

To get started on the recursive implementation, consider the example a = Link(1, Link(6, Link(8))), and the call sum_rec(a, 2). Write down the recursive call to sum_rec that would help compute sum_rec(a, 2). Then, write down what that recursive call should return. Discuss how this return value is useful in computing the return value of sum_rec(a, 2).

Discussion time: When adding up numbers, the intermediate sums depend on the order. (1 + 3) + 5 and 1 + (3 + 5) both equal 9, but the first one makes 4 along the way while the second makes 8 along the way. For the same linked list s and length k, will sum_rec and sum_iter both make the same intermediate sums along the way?

For a summation, the order of additions doesn't affect the result, but for other operations this ordering matters. For example, (2 ** 3) ** 5 is much smaller than 2 ** (3 ** 5).

Q3: Overlap

Implement overlap, which takes two linked lists of numbers called s and t that are sorted in increasing order and have no repeated elements within each list. It returns the count of how many numbers appear in both lists.

This can be done in linear time in the combined length of s and t by always advancing forward in the linked list whose first element is smallest until both first elements are equal (add one to the count and advance both) or one list is empty (time to return). Here's a lecture video clip about this (but the video uses Python lists instead of linked lists).

Take a vote to decide whether to use recursion or iteration. Either way works (and the solutions are about the same complexity/difficulty). (If you finish quickly, implement it the other way too!)

    if s is Link.empty or t is Link.empty:
        return 0
    if s.first == t.first:
        return __________________
    elif s.first < t.first:
        return __________________
    elif s.first > t.first:
        return __________________

    k = 0
    while s is not Link.empty and t is not Link.empty:
        if s.first == t.first:
            __________________
        elif s.first < t.first:
            __________________
        elif s.first > t.first:
            __________________
    return k

Extra Fun

Some of you have requested additional practice with generators. Wouldn't it be fun to use a generator for a linked list problem?!

Q4: Iterate in Order

Implement iterate_in_order, which takes two linked lists of numbers called s and t that are sorted in increasing order and have no repeated elements within each list. It returns a generator that iterates over all items in s and t in non-decreasing order.

Extra Challenging Extra Fun

This last question is similar in complexity to an A+ question on an exam. Feel free to skip it, but it's a fun one, so try it if you have time.

Q5: Decimal Expansion

Definition. The decimal expansion of a fraction n/d with n < d is an infinite sequence of digits starting with the 0 before the decimal point and followed by digits that represent the tenths, hundredths, and thousands place (and so on) of the number n/d. E.g., the decimal expansion of 2/3 is a zero followed by an infinite sequence of 6's: 0.6666666....

Implement divide, which takes positive integers n and d with n < d. It returns a linked list with a cycle containing the digits of the infinite decimal expansion of n/d. The provided display function prints the first k digits after the decimal point.

For example, 1/22 would be represented as x below:

>>> 1/22
0.045454545454545456
>>> x = Link(0, Link(0, Link(4, Link(5))))
>>> x.rest.rest.rest.rest = x.rest.rest
>>> display(x, 20)
0.04545454545454545454...

>>> q, r = 10 * n // d, 10 * n % d
>>> tail.rest = Link(q)
>>> tail = tail.rest
>>> n = r