Discussion 12: Final Review

• disc12.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 Ed.

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

Linked Lists

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
>>> isinstance(Link(1), Link)
True
>>> isinstance(Link(1, Link(2)), list)
False

Run in 61A Code

Generators

Q6: Yield, Fibonacci!

Implement fibs, a generator function that takes a one-argument pure function f and yields all Fibonacci numbers x for which f(x) returns a true value. The Fibonacci numbers begin with 0 and then 1. Each subsequent Fibonacci number is the sum of the previous two. Yield the Fibonacci numbers in order.

Run in 61A Code

Q7: Powers

Implement powers, a generator function which takes positive integers n and k. It yields all integers m that are both powers of k and whose digits appear in order in n.

Assume the following functions are defined:

• is_power(base, s) - is_power takes in a positive integer base and a non-negative integer s and returns True if there is some number n where pow(base, n) = s
• curry2 - curry2 = lambda f: lambda x: lambda y: f(x, y)

Hint: filter(func, seq) returns an iterator that yields all the values x in seq where func(x) is truthy.

Run in 61A Code

Scheme

Q8: 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

After you finish your Thanksgiving dinner, you realize that you still need to buy gifts for all your loved ones over the holidays. However, you also want to spend as little money as possible (you're not cheap, just looking for a great sale!).

This question utilizes the following tables:

products

inventory

stores

Q9: Price Check

Let's start off by surveying our options. Using the products table, write a query that creates a table average_prices that lists categories and the average price of items in the category (using MSRP as the price).

You should get the following output:

computer|109.0
games|350.0
phone|90.0

Run in 61A Code

Q10: The Price is Right

Now, you want to figure out which stores sell each item in products for the lowest price. Write a SQL query that uses the inventory table to create a table lowest_prices that lists items, the stores that sells that item for the lowest price, and the price that the store sells that item for.

You should expect the following output:

Hallmart|GameStation|298.98
Targive|QBox|390.98
Targive|iBook|110.99
RestBuy|kBook|94.99
Hallmart|qPhone|85.99
Hallmart|rPhone|69.99
RestBuy|uPhone|89.99
RestBuy|wBook|114.29

Run in 61A Code

Q11: Bang for your Buck

You want to make a shopping list by choosing the item that is the best deal possible for every category. For example, for the "phone" category, the uPhone is the best deal because the MSRP price of a uPhone divided by its ratings yields the lowest cost. That means that uPhones cost the lowest money per rating point out of all of the phones. Note that the item with the lowest MSRP price may not necessarily be the best deal.

Write a query to create a table shopping_list that lists the items that you want to buy from each category.

After you've figured out which item you want to buy for each category, add another column that lists the store that sells that item for the lowest price.

You should expect the following output:
GameStation|Hallmart
uPhone|RestBuy
wBook|RestBuy

Run in 61A Code

Q12: Driving the Cyber Highways

Using the Mbs (megabits) column from the stores table, write a query to calculate the total amount of bandwidth needed to get everything in your shopping list.

Run in 61A Code

Regex

Q13: Party Planner

You are the CEO of SchemeCorp, a company you founded after learning Scheme in CS61A. You want to plan a social for everyone who works at your company, but only your colleagues who live in Berkeley can help plan the party. You want to add all employees located in Berkeley (based on their phone number) to a party-planning group chat. Given a string representing a list of employee phone numbers for SchemeCorp, write a regular expression that matches all valid phone numbers of employees in the 314 or 510 Berkeley area codes.

In addition, a few of your colleagues are visiting from Los Angeles (area code 310) and Montreal (area code 514) and would like to help. Your regular expression should match their phone numbers as well.

Valid phone numbers can be formatted in two ways. Some employees entered their phone numbers with parentheses around the area code (for example, (786)-375-6454), while some omitted the area code (for example, 786-375-6454). A few employees also entered their phone numbers incorrectly, with either greater than or fewer than 10 digits. These phone numbers are not valid and should not be included in the group chat.

Run in 61A Code

Interpreters

Q14: Call Count

Modify the Scheme interpreter so that it keeps track of the number of times each procedure is called inside the evaluator. You will also add the primitive call-count that takes a procedure as its argument and returns the number of times the procedure has been called since the evaluator was started. This feature should work for both primitive and compound procedures.

For example:

scm> (define (foo x)
(* 2 (+ 1 (* 2 x))))
scm> (call-count foo)
0
scm> (call-count *)
0
scm> (foo 2)
10
scm> (call-count foo)
1
scm> (foo 10)
42
scm> (call-count foo)
2
scm> (call-count *)
4
scm> (call-count (lambda (x) x))
0

Your job is to modify the interpreter to make this work. We have provided several possibly relevant functions on the following page.

Run in 61A Code