Attendance

Your TA will come around during discussion to check you in.

If you miss discussion for a good reason (such as sickness or a scheduling conflict), email cs61a@berkeley.edu within one week to receive attendance credit.

Higher Order Functions

Q1: Match Maker

Implement match_k, which takes in an integer k and returns a function that takes in a variable x and returns True if all the digits in x that are k apart are the same.

For example, match_k(2) returns a one argument function that takes in x and checks if digits that are 2 away in x are the same.

match_k(2)(1010) has the value of x = 1010 and digits 1, 0, 1, 0 going from left to right. 1 == 1 and 0 == 0, so the match_k(2)(1010) results in True.

match_k(2)(2010) has the value of x = 2010 and digits 2, 0, 1, 0 going from left to right. 2 != 1 and 0 == 0, so the match_k(2)(2010) results in False.

Important: You may not use strings or indexing for this problem.

Tip: Floor dividing by powers of 10 gets rid of the rightmost digits.

Trees

Q2: In-order Traversal

Write a function that returns a generator that generates an "in-order" traversal, in which we yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.

Iterators

Q3: Repeated

Implement repeated, which takes in an iterator t and an integer k greater than 1. It returns the first value in t that appears k times in a row.

Important: Call next on t only the minimum number of times required. Assume that there is an element of t repeated at least k times in a row.

Hint: If you are receiving a StopIteration exception, your repeated function is calling next too many times.

Object-Oriented Programming

Q4: Person

Modify the following Person class to add a repeat method, which repeats the last thing said. See the doctests for an example of its use.

Linked Lists

Q5: Every Other

Implement every_other, which takes a linked list s. It mutates s such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True

If s contains fewer than two elements, s remains unchanged. Do not return anything! every_other should mutate the original list.

Scheme

Q6: Switch

Define the macro switch, which takes in an expression expr and a list of pairs called cases where the first element of the pair is some number and the second element is a single expression. switch will evaluate the expression contained in cases that corresponds to the number that expr evaluates to.

scm> (switch (+ 1 1) ((1 (print 'a))
                      (2 (print 'b))
                      (3 (print 'c))))
b

You may assume that the value expr evaluates to is always a number and is always the first element of one of the pairs in cases. You can also assume that the first value of each pair in cases is a number and the second expression does not contain the symbol val.

Use equal? to check if two numbers are equal.

(begin
     (define val (+ 1 1))
     (cond ((equal? val 1) (print 'a))
           ((equal? val 2) (print 'b))
           ((equal? val 3) (print 'c))))

SQL

Q7: Raises

This last question refers to the following salaries table:

salaries

Write a query that outputs the names of the top 3 employees with the largest salary raises from 2022 to 2023 along with their corresponding salary raises, ordered from largest to smallest raise.