Homework 6: Scheme, Scheme Lists
Due by 11:59pm on Wednesday, July 31
Instructions
Download hw06.zip. Inside the archive, you will find a file called
hw06.scm, 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.
Readings: You might find the following references useful:
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.
The 61A Scheme interpreter is included in each Scheme assignment. To start it,
type python3 scheme
in a terminal. To load a Scheme file called f.scm
, type python3 scheme -i f.scm
. To exit the Scheme interpreter, type
(exit)
.
Scheme Editor
All Scheme assignments include a web-based editor that makes it easy to run ok
tests and visualize environments. Type python3 editor
in a terminal, and the
editor will open in a browser window (at http://127.0.0.1:31415/
). Whatever
changes you make here will also save to the original file on your computer!
To stop running the editor and return to the command line, type Ctrl-C
in the
terminal where you started the editor.
The Run
button loads the current assignment's .scm
file and opens a Scheme
interpreter, allowing you to try evaluating different Scheme expressions.
The Test
button runs all ok tests for the assignment. Click View Case
for a
failed test, then click Debug
to step through its evaluation.
Recommended VS Code Extensions
If you choose to use VS Code as your text editor (instead of the web-based editor), install the vscode-scheme extension so that parentheses are highlighted.
Before:
After:
In addition, the 61a-bot (installation instructions) VS Code extension is available for Scheme homeworks. The bot is also integrated into ok
.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Scheme
Q1: Pow
Implement a procedure pow
that raises a base
to the power of a nonnegative integer exp
. The number of recursive pow
calls should grow logarithmically with respect to exp
, rather than linearly. For example, (pow 2 32)
should result in 5 recursive pow
calls rather than 32 recursive pow
calls.
Hint:
- x2y = (xy)2
- x2y+1 = x(xy)2
For example, 216 = (28)2 and 217 = 2 * (28)2.
You may use the built-in predicates
even?
andodd?
. Also, thesquare
procedure is defined for you.Scheme doesn't have
while
orfor
statements, so use recursion to solve this problem.
(define (square n) (* n n))
(define (pow base exp)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q pow
Q2: Repeatedly Cube
Implement repeatedly-cube
, which receives a number x
and cubes it n
times.
Here are some examples of how repeatedly-cube
should behave:
scm> (repeatedly-cube 100 1) ; 1 cubed 100 times is still 1
1
scm> (repeatedly-cube 2 2) ; (2^3)^3
512
scm> (repeatedly-cube 3 2) ; ((2^3)^3)^3
134217728
For information on
let
, see the Scheme spec.
(define (repeatedly-cube n x)
(if (zero? n)
x
(let
(_________________)
(* y y y))))
Use Ok to test your code:
python3 ok -q repeatedly-cube
Q3: Cadr
Define the procedure cadr
, which returns the second element of a list. Also define caddr
, which returns the third element of a list.
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
'YOUR-CODE-HERE
)
(define (caddr s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q cadr-caddr
Scheme Lists
Q4: Ascending
Implement a procedure called ascending?
, which takes a list of numbers s
and
returns True
if the numbers are in non-descending order, and False
otherwise.
A list of numbers is non-descending if each element after the first is greater than or equal to the previous element. For example...
(1 2 3 3 4)
is non-descending.(1 2 3 3 2)
is not.
Hint: The built-in
null?
procedure returns whether its argument isnil
.
Note: The question mark in
ascending?
is just part of the procedure name and has no special meaning in terms of Scheme syntax. It is a common practice in Scheme to name procedures with a question mark at the end if it returns a boolean value.
(define (ascending? s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q ascending -u
python3 ok -q ascending
Q5: My Filter
Write a procedure my-filter
, which takes a predicate pred
and a list s
, and
returns a new list containing only elements of the list that satisfy the
predicate. The output should contain the elements in the same order that they
appeared in the original list.
Note: Make sure that you are not just calling the built-in filter
function in Scheme - we are asking you to re-implement this!
(define (my-filter pred s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Q6: No Repeats
Implement no-repeats
, which takes a list of numbers s
. It returns a list
that has all of the unique elements of s
in the order that they first appear,
but no repeats.
For example, (no-repeats (list 5 4 5 4 2 2))
evaluates to (5 4 2)
.
Hint: You may find it helpful to use
filter
with alambda
procedure to filter out repeats. To test if two numbersa
andb
are not equal, use(not (= a b))
.
(define (no-repeats s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q no_repeats
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.
Extra Credit (1 pt)
During Office Hours and Project Parties, the staff will prioritize helping students with required questions. We will not be offering help with this question unless the queue is empty.
Q7: Longest Increasing Subsequence
Write the procedure longest-increasing-subsequence
, which takes in a list lst
and returns the
longest subsequence in which all the terms are increasing.
Note: the elements do not have to appear consecutively in the original list. For example, the longest increasing subsequence of
(1 2 3 4 9 3 4 1 10 5)
is (1 2 3 4 9 10)
. Assume that the longest increasing subsequence is unique.
Hint: The built-in procedures
length
(documentation) andfilter
(documentation) might be helpful to solving this problem.
; helper function
; returns the values of lst that are bigger than x
; e.g., (larger-values 3 '(1 2 3 4 5 1 2 3 4 5)) --> (4 5 4 5)
(define (larger-values x lst)
'YOUR-CODE-HERE)
(define (longest-increasing-subsequence lst)
; the following skeleton is optional, remove if you like
(if (null? lst)
nil
(begin
(define first (car lst))
(define rest (cdr lst))
(define large-values-rest
'YOUR-CODE-HERE)
(define with-first
'YOUR-CODE-HERE)
(define without-first
'YOUR-CODE-HERE)
(if 'YOUR-CONDITION-HERE
with-first
without-first))))
Use Ok to test your code:
python3 ok -q longest-increasing-subsequence
Exam Practice
The following are some Scheme List exam problems from previous semesters that you may find useful as additional exam practice. These questions have no submission component; feel free to attempt them if you'd like some practice!