Discussion 12: Final Review
Reminder: Use Discord for voice chat with the course staff. Write to @discuss
in the #discuss-queue
channel on Discord at any time, and a member of the course staff will join your group's voice channel.
Pick someone in your group to join Discord. It's fine if multiple people join, but one is enough.
Now switch to Pensieve:
- Everyone: Go to discuss.pensieve.co and log in with your @berkeley.edu email, then enter your group number. (Your group number is the number of your Discord channel.)
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.
Post in the #help
channel on Discord if you have trouble.
Pro tip: Any of you can type a question into your group's Discord channel's text chat with the @discuss
tag, and a member of the course staff will respond.
Getting Started
If you have only 1 or 2 people in your group, you can join the other group in the room with you.
Ice breaker: Everybody say your name and the non-CS/EECS course that you're most excited about taking next semester.
Lists
The two most common mutation operations for lists are item assignment and the append
method.
>>> s = [1, 3, 4]>>> t = s # A second name for the same list>>> t[0] = 2 # this changes the first element of the list to 2, affecting both s and t>>> s[2, 3, 4]>>> s.append(5) # this adds 5 to the end of the list, affecting both s and t>>> t[2, 3, 4, 5]
There are many other list mutation methods:
append(elem)
: Addelem
to the end of the list. ReturnNone
.extend(s)
: Add all elements of iterables
to the end of the list. ReturnNone
.insert(i, elem)
: Insertelem
at indexi
. Ifi
is greater than or equal to the length of the list, thenelem
is inserted at the end. This does not replace any existing elements, but only adds the new elementelem
. ReturnNone
.remove(elem)
: Remove the first occurrence ofelem
in list. ReturnNone
. Errors ifelem
is not in the list.pop(i)
: Remove and return the element at indexi
.pop()
: Remove and return the last element.
Q1: Word Rope
Definition: A rope in Python is a list containing only one-letter strings except for the last element, which may either be a one-letter string or a rope.
Implement word_rope
, a Python function that takes a non-empty string s
containing only letters and spaces that does not start or end with a space. It returns a rope containing the letters of s
in which each word is in a separate list.
Important: You may not use slicing or the split
, find
, or index
methods of a string. Solve the problem using list operations.
Reminder: s[-1]
evaluates to the last element of a sequence s
.
Run in 61A Code
In this implementation, result
is a rope and word
is a list within that rope which is still being constructed. When x
is a space, add an empty list to the end of word
and assign word
to this empty list. Otherwise, add x
to the end of word
.
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 lists
.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) + '>'
Q2: 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.
Run in 61A Code
There are three cases:
- If
rest
is empty, return a one-element list containing justfirst
. - If
rest.first
is in the linear sublist that starts withfirst
, then build a list that containsfirst
, andrest.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
.
Scheme
Q3: Increasing Rope
Definition: A rope in Scheme is a non-empty list containing only numbers except for the last element, which may either be a number or a rope.
Implement up
, a Scheme procedure that takes a positive integer n
. It returns a rope containing the digits of n
that is the shortest rope in which each pair of adjacent numbers in the same list are in increasing order.
Reminder: the quotient
procedure performs floor division, like //
in Python. The remainder
procedure is like %
in Python.
Run in 61A Code
Compare first
to (car result)
to decide whether to cons
the value first
onto the result
or whether to form a new list that contains first
and result
as elements.
To correctly call helper
from within up
, build a rope that only contains the last digit of n
: (remainder n 10)
.
SQL
A SELECT
statement describes an output table based on input rows. To write one:
- Describe the input rows using
FROM
andWHERE
clauses. - Group those rows and determine which groups should appear as output rows using
GROUP BY
andHAVING
clauses. - Format and order the output rows and columns using
SELECT
andORDER BY
clauses.
SELECT
(Step 3) FROM
(Step 1) WHERE
(Step 1) GROUP BY
(Step 2) HAVING
(Step 2) ORDER BY
(Step 3);
Step 1 may involve joining tables (using commas) to form input rows that consist of two or more rows from existing tables.
The WHERE
, GROUP BY
, HAVING
, and ORDER BY
clauses are optional.
Q4: A Secret Message
A substitution cipher replaces each word with another word in a table in order to encrypt a message. To decode an encrypted message, replace each word x
with its corresponding y
in a code table.
Write a select statement to decode the original
message It's The End using the code
table.
Run in 61A Code
Join the original
and code
tables and make sure that the joined roles have the same word
and x
.
What happens now? Write another select statement to decode this encrypted message using the same code
table.
Run in 61A Code
Join original
with code AS a
and code AS b
to create six-column rows like: 2|The|The|Happens|Happens|Go
, The Go at the end is part of the decoded message.
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 discussion room and time should be available during RRR week if you want to use it.
Document the Occasion
Please all fill out the attendance form (one submission per person per week).
Important: Please help put the furniture in the room back where you found it before you leave. Thanks!