Discussion 12: More SQL, Final Review

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything.


You can refer back to Discussion 11 for an overview of SQL, including joins and aggregation.

(Adapted from Fall 2019) The scoring table has three columns, a player column of strings, a points column of integers, and a quarter column of integers. The players table has two columns, a name column of strings and a team column of strings. Complete the SQL statements below so that they would compute the correct result even if the rows in these tables were different than those shown.

Important: You may write anything in the blanks including keywords such as WHERE or ORDER BY. Use the following tables for the questions below:

    SELECT "Donald Stewart" AS player, 7 AS points, 1 AS quarter UNION
    SELECT "Christopher Brown Jr.", 7, 1 UNION
    SELECT "Ryan Sanborn", 3, 2 UNION
    SELECT "Greg Thomas", 3, 2 UNION
    SELECT "Cameron Scarlett", 7, 3 UNION
    SELECT "Nikko Remigio", 7, 4 UNION
    SELECT "Ryan Sanborn", 3, 4 UNION
    SELECT "Chase Garbers", 7, 4;

    SELECT "Ryan Sanborn" AS name, "Stanford" AS team UNION
    SELECT "Donald Stewart", "Stanford" UNION
    SELECT "Cameron Scarlett", "Stanford" UNION
    SELECT "Christopher Brown Jr.", "Cal" UNION
    SELECT "Greg Thomas", "Cal" UNION
    SELECT "Nikko Remigio", "Cal" UNION
    SELECT "Chase Garbers", "Cal";

Q1: Big Quarters

Write a SQL statement to select a one-column table of quarters in which more than 10 total points were scored.

Q2: Score

Write a SQL statement to select a two-column table where the first column is the team name and the second column is the total points scored by that team. Assume that no two players have the same name.

Final Review

The following worksheet is final review! It covers various topics that have been seen throughout the semester.

Your TA will not be able to get to all of the problems on this worksheet so feel free to work through the remaining problems on your own. Bring any questions you have to office hours or post them on piazza.

Good luck on the final and congratulations on making it to the last discussion of CS61A!


Q3: Maximum Subsequence

A subsequence of a number is a series of (not necessarily contiguous) digits of the number. For example, 12345 has subsequences that include 123, 234, 124, 245, etc. Your task is to get the maximum subsequence below a certain length.

Run in 61A Code


Q4: Reverse

Write a function that reverses the given list. Be sure to mutate the original list. This is practice, so don't use the built-in reverse function!

Run in 61A Code


Q5: The First Order...of Growth

What is the efficiency of rey?

def rey(finn):
    poe = 0
    while finn >= 2:
        poe += finn
        finn = finn / 2

What is the efficiency of mod_7?

def mod_7(n):
    if n % 7 == 0:
        return 0
        return 1 + mod_7(n - 1)


Q6: Level Mutation

As a reminder, the depth of a node is how far away the node is from the root. We define this as the number of edges between the root to the node. As there are no edges between the root and itself, the root has depth 0.

Given a tree t and a list of one-argument functions funcs, write a function that will mutate the labels of t using the function from funcs at the corresponding depth. For example, the label at the root node (with a depth of 0) will be mutated using the function at index 0, or funcs[0]. Assume all of the functions in funcs will be able to take in a label value and return a valid label value.

If t is a leaf and there are more than 1 functions in funcs, all of the remaining functions should be applied in order to the label of t. (See the doctests for an example.) If funcs is empty, the tree should remain unmodified.

Run in 61A Code

As an extra challenge, try implementing level_mutation_link, which has the same behavior as level_mutation except it will take in a Linked List of functions funcs (rather than a Python list of functions).

Run in 61A Code

Linked Lists

Write a function that takes in a Python list of linked lists and multiplies them element-wise. It should return a new linked list.

If not all of the Link objects are of equal length, return a linked list whose length is that of the shortest linked list given. You may assume the Link objects are shallow linked lists, and that lst_of_lnks contains at least one linked list.

Run in 61A Code


Q8: List Insert

Write a Scheme function that, when given an element, a list, and an index, inserts the element into the list at that index. You can assume that the index is in bounds for the list.

Run in 61A Code

Q9: Group by Non-Decreasing

Define a function nondecreaselist, which takes in a scheme list of numbers and outputs a list of lists, which overall has the same numbers in the same order, but grouped into lists that are non-decreasing.

For example, if the input is a stream containing elements

(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1)

the output should contain elements

((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))

Note: The skeleton code is just a suggestion; feel free to use your own structure if you prefer.

Run in 61A Code


Q10: Greetings

Let's say hello to our fellow bears! We've received messages from our new friends at Berkeley, and we want to determine whether or not these messages are greetings. In this problem, there are two types of greetings - salutations and valedictions. The first are messages that start with "hi", "hello", or "hey", where the first letter of these words can be either capitalized or lowercase. The second are messages that end with the word "bye" (capitalized or lowercase), followed by either an exclamation point, a period, or no punctuation. Write a regular expression that determines whether a given message is a greeting.

Run in 61A Code