Solo Assignment B
-
Clarifications shown in magenta.
-
Dueish: Thu Mar 04 (followed by a 7-day grace period)
-
Notes:
-
This is a solo assignment. You must complete all parts of this assignment entirely on your own without help from any other person and without consulting any resources other than course materials or Racket documentation. You may ask Lyn for clarification, but not for help.
-
You can do all problems on this assignment based on material you learned for PS2. Be sure to study the solutions to PS2 before doing this assignment.
-
This assignment has 48 solo points.
-
-
How to Start Solo Assignment B
Follow the instructions in the GDoc CS251-S21-T3 Pset Submission Instructions for creating your SOLO-B Google Doc. Put all written answers and a copy of all code into this SOLO-B GDoc.
-
Submission:
-
For all parts of all problems, include all answers (including the small-step derivation and all Racket code) in your SOLO-B GDoc. Please format your big/small-step derivation in Problem 1 and your Racket function definitions in Problem 2 so that they’re easy to read. Format all derivations and code using a fixed-width font (Courier New or Consolas). You use a small font size if that helps.
-
For Problem 1 (Alternative If Semantics), include your explanation and your small-step derivation in your GDoc.
-
For Problem 1 (Recursive Numeric Function), include your small-step derivation for part a and your answers to parts b and c in your GDoc.
-
For Problem 3 (Recursive List Functions) + Be sure that all function definitions in
yourAccountName-solo-b-functions.rkt
also appear in your Google Doc (so that I can comment on them) + Drop a copy of youryourAccountName-solo-b-functions.rkt
in your~/cs251/drop/solo-b
drop folder on cs.wellesley.edu.
-
1. Alternative If Semantics (5 points)
The small-step reduction rules for if
expressions in Racket are
(if V_test E_then E_else) ⇒ E_then
, ifV_test
is a value that is not#f
[if nonfalse](if #f E_then E_else) ⇒ E_else
[if false]
Lois Reasoner thinks that the reduction of if
expressions should be changed to:
(if V_test V_then V_else) ⇒ V_then
, ifV_test
is a value that is not#f
[if nonfalse Lois](if #f V_then V_else) ⇒ V_else
[if false Lois]
These differ from the actual rules by requiring that all three subexpressions E_test
, E_then
, and E_false
of (if E_test E_then E_false)
are first evaluated to values before the if
expression can be simplified.
Explain that Lois’s alternative semantics for if
are a bad idea. In particular, consider the sum-between
function from PS2:
(define sum-between
(lambda (lo hi)
(if (> lo hi)
0
(+ lo (sum-between (+ lo 1) hi)))))
Use Lois’s semantics for if
in a small-step semantics derivation for the evaluation of (sum-between 2 3)
to explain what happens. Use λ_sb
as an abbreviation for the lambda
expression that sum-between
names. You needn’t show every step, but at the very least should show lines in which the redex is λ_sb
applied to two values.
2. Recursive Numeric Function (10 points)
This problem involves the following recursive Racket function g
:
(define g
(lambda (n)
(if (<= n 2)
n
(+ n
(g (thirdish n))
(g (half n))))))
where thirdish
and half
are defined as
(define thirdish
(λ (int) (* (remainder int 3) (quotient int 3))))
(define half
(λ (int) (quotient int 2)))
half
returns the integer quotient of a number by 2 (e.g. (half 10)
and (half 11)
are both 5) and thirdish
returns the product of the integer quotient of the number by 3 and its remainder by three. For example:
> (map (λ (n) (cons n (thirdish n))) (range 12))
'((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 1) (5 . 2) (6 . 0) (7 . 2) (8 . 4) (9 . 0) (10 . 3) (11 . 6))
-
(8 points) Use small-step semantics to derive the evaluation of
(g 11)
. To keep the size of your derivation manageable, use the same conventions used in small-step derivations in PS2 Problem 1 Sum Fun. In particular:-
Use the notation λ_g as an abbreviation for the
lambda
expression(lambda (n) (if (<= n 2) n (+ n (g (thirdish n)) (g (half n)))))
-
Use ⇒* to show only the steps of the derivation in which the redex is a call to λ_g.
-
Use curly braces to show the redex in each line of your derivation.
-
Be careful not to perform any reductions to the right of the current focus. For example, when showing steps in the reduction of
(+ E1 E2)
,E1
must be completely evaluated to a valueV1
before any reduction steps are performed onE2
. -
Treat
half
andthirdish
as black boxes: do not show any redexes involving calls to these functions, only the results of such calls.
Additionally, you must explicitly show every reduction involving a
+
redex. -
-
(1 point) How many times is
g
called in the evaluation of(g 11)
? (Be sure to include the initial call(g 11)
as well as all base case calls, such as(g 0)
,(g 1)
, and(g 2)
.) -
(1 point) What is the maximum stack depth (measured in terms of maximum number of nested
+
operations) in the evaluation of(g 11)
?
3. Recursive List Functions (33 points)
In this problem you will define three recursive functions on lists. Some ground rules:
- Define all of your functions in a new file named
yourAccountName-solo-b-functions.rkt
that you create in Dr. Racket. -
You should use explicit recursion on lists in all of your definitions.
- Unlike in PS2 Problem 4, you are not required to explicitly show the Divide/Conquer/Glue steps for the list recursive functions you defined. Nevertheless, your solutions are required to use the Divide/Conquer/Glue strategy, and you are strongly encouraged to use these steps as part of thinking about the problems and developing your solutions.
- You should not use any higher-order list operations (e.g.,
map
,filter
,foldr
,foldl
,iterate
, orgenlist
) in this problem. - The only built-in Racket list operators you may use in your definitions are:
null
,null?
,cons
,list
,append
,first
,second
,third
, andrest
. (You may also use any Racket math or logic operators, such as+
,max
,equal?
, etc.) - You should not use other Racket list operators, including
reverse
,list-ref
,take
,drop
, etc. - You should use Racket’s
let
construct to avoid evaluating an expensive expression more than once. -
In this problem, you should define and use the following
map-cons
helper function:(define (map-cons x yss) (if (null? yss) null (cons (cons x (first yss)) (map-cons x (rest yss)))))
You may use this
map-cons
helper function in any part of this problem where you find it useful. - Other than the above
map-cons
function, you should not use any other helper functions in this problem except for the one helper function specified in 1dweighted-suffixes
.
-
(4 points) Define a recursive function
my-remove
that takes two arguments (a value and a list of values) and returns a new list containing all values in the list in their original order except for any valuesequal?
to the specified value. For example:> (my-remove 5 '(5 6 5 7 6 8 5 6 7 5)) '(6 7 6 8 6 7) > (my-remove 6 '(5 6 5 7 6 8 5 6 7 5)) '(5 5 7 8 5 7 5) > (my-remove 7 '(5 6 5 7 6 8 5 6 7 5)) '(5 6 5 6 8 5 6 5) > (my-remove 8 '(5 6 5 7 6 8 5 6 7 5)) '(5 6 5 7 6 5 6 7 5) > (my-remove 9 '(5 6 5 7 6 8 5 6 7 5)) '(5 6 5 7 6 8 5 6 7 5) > (my-remove '(1 2) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)) '(1 2 (1 2 3) 3 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6) > (my-remove '(1 2 3) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)) '(1 (1 2) 2 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6) > (my-remove '((1 2) (1 2) (1 2)) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 6) > (my-remove 5 '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) ((1 2) (1 2) (1 2)) 6) > (my-remove '(0 1) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)
-
(5 points) Define a recursive function
remove-dups
that takes one argument (a list of values) and returns a new list containing all values in the list in their original order except that all occurrences of a valueequal?
to the first occurrence have been removed.Other Requirements:
-
As with all parts of this problem, you must use the Divide/Conquer/Glue strategy in your solution. In particular, you must call
remove-dups
directly on therest
of the input list and not on any other list. -
You should use
my-remove
in your definition, but not Racket’smember
or any othermember
-like functions. -
Other than
my-remove
, andnull?
/cons
/first
/rest
. you may not use any helper functions in your definition.> (remove-dups '(5 6 5 7 6 8 5 6 7 5)) '(5 6 7 8) > (remove-dups '(1 2 3 4)) '(1 2 3 4) > (remove-dups '(1 (1 2) 2 (1 2 3) 3 (1 2) 1 (0 1 2) 2 ((1 2) (1 2) (1 2)) 1 (1 2 3) 2 (1 2) 3 (0 1) 4)) '(1 (1 2) 2 (1 2 3) 3 (0 1 2) ((1 2) (1 2) (1 2)) (0 1) 4)
-
-
(4 points) A length-n prefix of a list is a list containing its first n elements in the same relative order. For example:
- The length-0 prefix of
'(5 8 4)
is'()
- The length-1 prefix of
'(5 8 4)
is'(5)
- The length-2 prefix of
'(5 8 4)
is'(5 8)
- The length-3 prefix of
'(5 8 4)
is'(5 8 4)
Define a function
prefixes
that takes a list as its single argument and returns a list of all of its prefixes ordered from shortest to longest. For example:> (prefixes '(5 8 4)) '(() (5) (5 8) (5 8 4)) > (prefixes '(2 5 8 4)) '(() (2) (2 5) (2 5 8) (2 5 8 4)) > (prefixes '(7 2 5 8 4)) '(() (7) (7 2) (7 2 5) (7 2 5 8) (7 2 5 8 4)) > (prefixes (range 0 11)) '(() (0) (0 1) (0 1 2) (0 1 2 3) (0 1 2 3 4) (0 1 2 3 4 5) (0 1 2 3 4 5 6) (0 1 2 3 4 5 6 7) (0 1 2 3 4 5 6 7 8) (0 1 2 3 4 5 6 7 8 9) (0 1 2 3 4 5 6 7 8 9 10))
- The length-0 prefix of
-
(7 points) Define a function
sum-max-squaresEvens
that takes a list of integers its single argument and returns a triple (i.e., a three-element list) whose three elements are (1) the sum of the numbers in the list; (2) the maximum of the numbers in the list and (3) a list of the squares of all the even numbers in the list (maintaining relative order).> (sum-max-squaresEvens '(9 2 8 5 4 7 1 6 3)) '(45 9.0 (4 64 16 36)) > (sum-max-squaresEvens '(2 8 5 4 7 1 6 3)) '(36 8.0 (4 64 16 36)) > (sum-max-squaresEvens '(8 5 4 7 1 6 3)) '(34 8.0 (64 16 36)) > (sum-max-squaresEvens '(5 4 7 1 6 3)) '(26 7.0 (16 36)) > (sum-max-squaresEvens '(-9 2 -8 5 4 -7 1 -6 3)) '(-15 5.0 (4 64 16 36)) > (sum-max-squaresEvens '(-6 -3 -10 -5 -8)) '(-32 -3.0 (36 100 64)) > (sum-max-squaresEvens (append (range 1 101 7) (range 201 0 -2))) '(10951 201.0 (64 484 1296 2500 4096 6084 8464))
Notes:
-
Your
sum-max-squaresEvens
function should make a single pass over the input list to produce the output triple. I.e., you should not have separate recursions for calculating each of the three parts. -
Depending on how you determine the maximum, the result might display as a floating point number (as in
9.0
) or as an integer (as in9
).
-
-
(6 points) skippers
Note: The examples in this problem use lists of symbols rather than list of strings or characters because they are easier to read. A Racket symbol is a literal values (i.e., it evaluates to itself) that is written as a single quote mark followed by a sequence of characters, where the allowed characters are similar to those in Racket identifiers. E.g. examples of symbols are
'a
,'CS251
and'Hi*!?
. When symbols are in a list, they are not quoted. So the printed representation of(list 'a 'CS251 'Hi*!?)
is'(a CS251 Hi*!?)
.Define a skipper of a list L to be a list formed by (possibly) skipping some of the elements in the list, leaving the “kept” elements in the same relative order.
For example, if L is the list
'(b o a t)
, then:'(b o a t)
is the single 4-element skipper of L;'(o a t)
,'(b a t)
,'(b o t)
,'(b o a)
are the the 3-element skippers of L that result from removing one element of'(b o a t)
;'(a t)
,'(o t)
,'(o a)
,'(b t)
,'(b a)
,'(b o)
are the the 2-element skippers of L that result from removing two elements of'(b o a t)
;'(b)
,'(o)
,'(a)
,'(t)
are the the 1-element skippers of L that result from removing three elements of'(b o a t)
;'()
is the the single 0-element skipper of L that results from removing all four elements of'(b o a t)
;
Define a recursive function skippers that returns all of the skippers of a given list in the order suggested by the following examples:
> (skippers '()) '(()) > (skippers '(t)) '((t) ()) > (skippers '(a t)) ; Result has been manually reformatted to highlight the relationship between ; (skippers '(a t)) and (skippers '(t)) '((a t) (a) (t) ()) > (skippers '(o a t)) ; Result has been manually reformatted to highlight the relationship between ; (skippers '(o a t)) and (skippers '(a t)) '((o a t) (o a) (o t) (o) (a t) (a) (t) ()) > (skippers '(b o a t)) ; Result has been manually reformatted to highlight the relationship between ; (skippers '(b o a t)) and (skippers '(o a t)) '((b o a t) (b o a) (b o t) (b o) (b a t) (b a) (b t) (b) (o a t) (o a) (o t) (o) (a t) (a) (t) ())
-
(7 points) A length-n suffix of a list is a list containing its last n elements in the same relative order. For example:
- The length-0 suffix of
'(5 8 4)
is'()
- The length-1 suffix of
'(5 8 4)
is'(4)
- The length-2 suffix of
'(5 8 4)
is'(8 4)
- The length-3 suffix of
'(5 8 4)
is'(5 8 4)
Based on this definition, imagine a function
suffixes
that takes a list as its single argument and returns a list of all of its suffixes ordered from longest to shortest. For example:> (suffixes '(5 8 4)) '((5 8 4) (8 4) (4) ()) > (suffixes '(2 5 8 4)) '((2 5 8 4) (5 8 4) (8 4) (4) ()) > (suffixes '(7 2 5 8 4)) '((7 2 5 8 4) (2 5 8 4) (5 8 4) (8 4) (4) ()) > (suffixes (range 1 11)) '((1 2 3 4 5 6 7 8 9 10) (2 3 4 5 6 7 8 9 10) (3 4 5 6 7 8 9 10) (4 5 6 7 8 9 10) (5 6 7 8 9 10) (6 7 8 9 10) (7 8 9 10) (8 9 10) (9 10) (10) ())
In this problem, you are not asked to define
suffixes
, but are instead asked to define a related function namedweighted-suffixes
, which is assumed to take a list of numbers. The result ofweighted-suffixes
is a list similar to that returned bysuffixes
except that each nonempty sublist in the result ofweighted-suffixes
is the result of scaling all numbers in the corresponding nonempty sublist in the result ofsuffixes
by its first element. (The empty sublist insuffixes
yields the empty sublist inweighted-suffixes
).For example,
(weighted-suffixes '(7 2 5 8 4))
returns'((49 14 35 56 28) (4 10 16 8) (25 40 20) (64 32) (16) ())
because:(49 14 35 56 28)
is the result of scaling(7 2 5 8 4)
by7
(4 10 16 8)
is the result of scaling(2 5 8 4)
by2
(25 40 20)
is the result of scaling(5 8 4)
by5
(64 32)
is the result of scaling(8 4)
by8
(16)
is the result of scaling(4)
by4
()
is the sublist in the result ofweighted-suffixes
that corresponds to the sublist()
in the result ofsuffixes
Here are more examples of
weighted-suffixes
, the last two of which illustrate negative numbers:> (weighted-suffixes (range 3 8)) '((9 12 15 18 21) (16 20 24 28) (25 30 35) (36 42) (49) ()) > (weighted-suffixes (range 1 11)) '((1 2 3 4 5 6 7 8 9 10) (4 6 8 10 12 14 16 18 20) (9 12 15 18 21 24 27 30) (16 20 24 28 32 36 40) (25 30 35 40 45 50) (36 42 48 54 60) (49 56 63 70) (64 72 80) (81 90) (100) ()) > (weighted-suffixes '(-2 6 1 -3 -8 4 7 -5)) '((4 -12 -2 6 16 -8 -14 10) (36 6 -18 -48 24 42 -30) (1 -3 -8 4 7 -5) (9 24 -12 -21 15) (64 -32 -56 40) (16 28 -20) (49 -35) (25) ()) > (weighted-suffixes (range -3 4)) '((9 6 3 0 -3 -6 -9) (4 2 0 -2 -4 -6) (1 0 -1 -2 -3) (0 0 0 0) (1 2 3) (4 6) (9) ())
Notes:
-
Recall that you cannot use the higher-order
map
function here. So, in this problem, in addition toweighted-suffixes
, you will need to define a recursive list helper function that implements the mapping pattern to scale all elements in a list of numbers by a given scaling factor. -
You should not define
suffixes
helper function in this problem.
- The length-0 suffix of