# Discussion 13: Final Review disc13.pdf

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.

# 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!

## Recursion

### Q1: Paths List

(Adapted from Fall 2013) Fill in the blanks in the implementation of `paths`, which takes as input two positive integers `x` and `y`. It returns a list of paths, where each path is a list containing steps to reach `y` from `x` by repeated incrementing or doubling. For instance, we can reach 9 from 3 by incrementing to 4, doubling to 8, then incrementing again to 9, so one path is [3, 4, 8, 9].

Run in 61A Code

## Mutation

### Q2: 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

## Trees

### Q3: Widest Level

Write a function that takes a `Tree` object and returns the elements at the depth with the most elements.

In this problem, you may find it helpful to use the second optional argument to `sum`, which provides a starting value. All items in the sequence to be summed will be concatenated to the starting value. By default, start will default to 0, which allows you to sum a sequence of numbers. We provide an example of sum starting with a list, which allows you to concatenate items in a list.

Run in 61A Code

### Q4: 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.

Run in 61A Code

### Q5: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function for checking if something is an instance of an object. For example:

``````>>> isinstance([1, 2, 3], list)
True
True
False``````
Run in 61A Code

## Generators

### Q6: Repeated

Write a generator function that yields functions that are repeated applications of a one-argument function `f`. The first function yielded should apply `f` 0 times (the identity function), the second function yielded should apply `f` once, etc.

Run in 61A Code

## Scheme

### Q7: 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

## SQL

The following questions will refer to two tables:

• records: a table that stores information about the employees at a small company
• meetings: a table which records the divisional meetings at the company

records

Name Division Title Salary Supervisor
Ben Bitdiddle Computer Wizard 60000 Oliver Warbucks
Alyssa P Hacker Computer Programmer 40000 Ben Bitdiddle
Cy D Fect Computer Programmer 35000 Ben Bitdiddle
Lem E Tweakit Computer Technician 25000 Ben Bitdiddle
Louis Reasoner Computer Programmer Trainee 30000 Alyssa P Hacker
Oliver Warbucks Administration Big Wheel 150000 Oliver Warbucks
Eben Scrooge Accounting Chief Accountant 75000 Oliver Warbucks
Robert Cratchet Accounting Scrivener 18000 Eben Scrooge
... ... ... ... ...

meetings

Division Day Time
Accounting Monday 9am
Computer Wednesday 4pm
... ... ...

### Q8: Oliver Employee Meetings

Write a query that outputs the meeting days and times of all employees directly supervised by Oliver Warbucks.

Run in 61A Code

### Q9: Different Division

Write a query that outputs the names of employees whose supervisor is in a different division.

Run in 61A Code

### Q10: Num Meetings

Write a query that outputs the days of the week for which fewer than 5 employees have a meeting. You may assume no department has more than one meeting on a given day.

Run in 61A Code