Due by 11:59pm on Wednesday, April 30

Instructions

Download hw11.zip. Inside the archive, you will find two files called hw11.py and hw11.sql, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.

End of Semester Feedback and Course Evaluations

Please fill out the two surveys listed below:

• Data C88C end-of-semester survey
• UC Berkeley course evaluations

If 65% or more students (325 out of 500 students) complete both surveys by Friday 5/9 at 11:59 PM, then everyone will receive 1 point of extra credit! If this goal is not met, nobody will receive the extra point.

If 75% or more students (375 out of 500 students) complete both surveys by Friday 5/9 at 11:59 PM, then everyone will receive 1 additional point of extra credit (max amount of EC will be 2 points).

Required Questions

Q1: I Heard You Liked Functions...

Define a function cycle that takes in three functions f1, f2, and f3, as arguments. cycle will return another function g that should take in an integer argument n and return another function h. That final function h should take in an argument x and cycle through applying f1, f2, and f3 to x, depending on what n was. Here's what the final function h should do to x for a few values of n:

• n = 0, return x
• n = 1, apply f1 to x, or return f1(x)
• n = 2, apply f1 to x and then f2 to the result of that, or return f2(f1(x))
• n = 3, apply f1 to x, f2 to the result of applying f1, and then f3 to the result of applying f2, or f3(f2(f1(x)))
• n = 4, start the cycle again applying f1, then f2, then f3, then f1 again, or f1(f3(f2(f1(x))))
• And so forth.

Hint: most of the work goes inside the most nested function.

Hint: How can you utilize the % operator to achieve the cyclic behavior? Try computing n % 3 for all integers n from 0 to 12. What pattern do you notice?

def cycle(f1, f2, f3):
    """Returns a function that is itself a higher-order function.

    >>> def add1(x):
    ...     return x + 1
    >>> def times2(x):
    ...     return x * 2
    >>> def add3(x):
    ...     return x + 3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q cycle
Copy
✂️

Q2: Making Onions

Write a function make_onion that takes in two one-argument functions, f and g. It returns a function that takes in three arguments: x, y, and limit. The returned function returns True if it is possible to reach y from x using up to limit calls to f and g, and False otherwise.

For example, if f adds 1 and g doubles, then it is possible to reach 25 from 5 in four calls: f(g(g(f(5)))).

def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit):
        if limit < 0:
            return ____
        elif x == y:
            return ____
        else:
            return can_reach(____, ____, limit - 1) or can_reach(____, ____, limit - 1)
    return can_reach

Use Ok to test your code:

python3 ok -q make_onion
Copy
✂️

Survey Data

In a past semester of this course, we asked the students to take a survey. In this lab, we will interact with the results of the survey by using SQL queries to see if we can find interesting trends in the data. Data scientists often use languages like SQL to do Exploratory Data Analysis (EDA).

First, take a look at data.sql and examine the table defined in it. Note its structure.

You will only be working with the students table in this file.

The students table is the main results of the survey. Each column represents a different question from the survey, except for the first column, which is the time of when the result was submitted. This time is a unique identifier for each of the rows in the table.

You will write all of your solutions in the starter file hw11.sql provided. As with other labs, you can test your solutions with OK. In addition, you can use either of the following commands:

python3 sqlite_shell.py < hw11.sql
python3 sqlite_shell.py --init hw11.sql

Q3: Matchmaker, Matchmaker

Did you take this course with the hope of finding a new group of friends? Well you're in luck! With all this data in hand, it's easy for us to find your perfect match. If two students want the same pet and have the same taste in music, they are clearly meant to be friends! In order to provide some more information for the potential pair to converse about, let's include the favorite colors of the two individuals as well!

In order to match up students, you will have to do a join on the students table with itself. When you do a join, SQLite will match every single row with every single other row, so make sure you do not match anyone with themselves, or match any given pair twice!

Important Note: When pairing the first and second person, make sure that the first person responded first (i.e. they have an earlier time). This is to ensure your output matches our tests.

Hint: When joining table names where column names are the same, use dot notation to distinguish which columns are from which table: [table_name].[column name]. This sometimes may get verbose, so it’s stylistically better to give tables an alias using the AS keyword. The syntax for this is as follows:

SELECT <[alias1].[column1], [alias2].[column2]...>
    FROM <[table1] AS [alias1], [table2] AS [alias2]...> ...

Write a SQL query to create a table that has 4 columns:

• The shared preferred pet of the pair
• The shared favorite song of the pair
• The favorite color of the first person
• The favorite color of the second person

CREATE TABLE matchmaker AS
  SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";

Use Ok to test your code:

python3 ok -q matchmaker
Copy
✂️

Q4: The Smallest Unique Positive Integer

Write an SQL query to create a table with the columns time and smallest which contains the timestamp for each submission that made a unique guess for the smallest unique positive integer - that is, only one person put that number for their guess of the smallest unique integer. Also include their guess in the output (this is the value in the smallest column).

Hint: Think about what attribute you need to GROUP BY. Which groups do we want to keep after this? We can filter this out using a HAVING clause.

You should not compute this in your final answer, but if you're curious, the submission with the timestamp corresponding to the minimum value of smallest in this table is the timestamp of the submission with the smallest unique positive integer!

CREATE TABLE smallest_int_having AS
  SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";

Use Ok to test your code:

python3 ok -q smallest-int-having
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.