This is a solo, Gradescope assignment—you will submit an individual submission of one written text file and one Racket file on Gradescope.
Change log
I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here:
Updated Problem 4 is-sorted? to reference another Racket function and include examples.
Updated Problem 7 to reference another Racket function.
Setup
As with Assignment 0, I suggest you complete this assignment in DrRacket. For this assignment, your Racket file should start with #lang racket.
Create 2 files:
1.README.txt (or README.md) for your written answers. 2.a1.rkt for your Racket code.
For the Racket problems, you should write Racket solutions using primarily the operators and functions we have seen so far in class. Do not use Racket library functions that accomplish the full task, even if they exist.
Problem 1: Pondering side effects
Answer the following questions in your README text or Markdown file.
In class, we described a side effect as “a behavior other than producing a value”.
Written 1.1: Write 3 individual Python (or Java) functions that exhibit different side effects. Use comments to label and explain each side effect.
Written 1.2: Do you think variable declaration in Racket is a side effect? Why or why not? (Note: your explanation here matters more than the yes/no answer.)
Problem 2: Is that a value?
Answer the following question in your README text or Markdown file.
Does Racket allow lists to contain expressions that are not values? Provide 2 example Racket expressions and their results from the interactions window to justify your answer (explain each example).
The following problems should all be completed in a1.rkt.
Problem 3: repeat-element
Write a function, repeat-element, that repeats every element in a list twice.
For example:
> (repeat-element (list123))
'(112233)
Problem 4: is-sorted?
Write a function, is-sorted?, that checks whether a list is sorted. is-sorted? should return true if the list is a sorted list of strings or a sorted list of numbers, but false if the elements are not in order or if the list contains heterogenous datatypes.
Beyond what we saw in class, you may find the following Racket functions useful:
string?, number?: check whether a value is a string or a number, respectively.
Write a function, (contains-multiple? m ns), that takes an integer m and a list of integers ns and returns true if m evenly divides at least one element in the list; and otherwise false.
Beyond what we saw in class, you may find the following Racket functions useful:
modulo : documentation (can be used to check divisibility)
Write a function, (all-contain-multiple? m nss), that takes an integer m and a list of lists of integers nss and returns true if all lists of integers that are elements in nss contain at least one integer that is a multiple of m; and otherwise false. You should use your prior function as a helper function.
If you are surprised by the result of (all-contain-multiple? 3 null), consider that in general, "all" statements over an empty set (also known as universal quantification) are, by definition, true.
Problem 7: mergesort
Implement a function that sorts a list of numbers using the merge sort algorithm. Define helper functions as appropriate.
As a reminder, the high-level algorithm for merge sort is:
Consider the empty or single-element list sorted.
For lists longer than 2, divide the list (roughly) in half. Recursively sort each half.
merge the two sorted halves into a single list in a linear pass, making sure to keep the elements sorted.
For this problem, you can reference the CS230 materials, but please avoid looking at other implementations of mergesort.
You should not use any library sorting functions, however, you may find the following Racket functions useful:
Assignment 1
This is a solo, Gradescope assignment—you will submit an individual submission of one written text file and one Racket file on Gradescope.
Change log
I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here:
is-sorted?to reference another Racket function and include examples.Setup
As with Assignment 0, I suggest you complete this assignment in DrRacket. For this assignment, your Racket file should start with
#lang racket.Create 2 files:
1.
README.txt(orREADME.md) for your written answers.2.
a1.rktfor your Racket code.For the Racket problems, you should write Racket solutions using primarily the operators and functions we have seen so far in class. Do not use Racket library functions that accomplish the full task, even if they exist.
Problem 1: Pondering side effects
Answer the following questions in your
READMEtext or Markdown file.In class, we described a side effect as “a behavior other than producing a value”.
Written 1.1: Write 3 individual Python (or Java) functions that exhibit different side effects. Use comments to label and explain each side effect.
Written 1.2: Do you think variable declaration in Racket is a side effect? Why or why not? (Note: your explanation here matters more than the yes/no answer.)
Problem 2: Is that a value?
Answer the following question in your
READMEtext or Markdown file.Does Racket allow lists to contain expressions that are not values? Provide 2 example Racket expressions and their results from the interactions window to justify your answer (explain each example).
The following problems should all be completed in
a1.rkt.Problem 3:
repeat-elementWrite a function,
repeat-element, that repeats every element in a list twice.For example:
> (repeat-element (list 1 2 3)) '(1 1 2 2 3 3)Problem 4:
is-sorted?Write a function,
is-sorted?, that checks whether a list is sorted.is-sorted?should return true if the list is a sorted list of strings or a sorted list of numbers, but false if the elements are not in order or if the list contains heterogenous datatypes.Beyond what we saw in class, you may find the following Racket functions useful:
string?,number?: check whether a value is a string or a number, respectively.string<?,string<=?: documentationFor example:
> (is-sorted? (list 1 2 2 3)) #t > (is-sorted? (list "a" "c")) #t > (is-sorted? (list "c" "a")) #f > (is-sorted? (list "a" "2")) #fProblem 5:
contains-multiple?Write a function,
(contains-multiple? m ns), that takes an integermand a list of integersnsand returns true ifmevenly divides at least one element in the list; and otherwise false.Beyond what we saw in class, you may find the following Racket functions useful:
modulo: documentation (can be used to check divisibility)For example:
> (contains-multiple? 5 (list 8 10 14)) #t > (contains-multiple? 3 (list 8 10 14)) #f > (contains-multiple? 5 null) #fProblem 6:
all-contain-multiple?Write a function,
(all-contain-multiple? m nss), that takes an integermand a list of lists of integersnssand returns true if all lists of integers that are elements in nss contain at least one integer that is a multiple ofm; and otherwise false. You should use your prior function as a helper function.For example:
> (all-contain-multiple? 5 (list (list 17 10 2) (list 25) (list 3 7 5))) #t > (all-contain-multiple? 3 (list (list 17 10 2) (list 25) (list 3 7 5))) #f > (all-contain-multiple? 3 null) #tIf you are surprised by the result of
(all-contain-multiple? 3 null), consider that in general, "all" statements over an empty set (also known as universal quantification) are, by definition, true.Problem 7:
mergesortImplement a function that sorts a list of numbers using the merge sort algorithm. Define helper functions as appropriate.
As a reminder, the high-level algorithm for merge sort is:
mergethe two sorted halves into a single list in a linear pass, making sure to keep the elements sorted.For this problem, you can reference the CS230 materials, but please avoid looking at other implementations of
mergesort.You should not use any library sorting functions, however, you may find the following Racket functions useful:
length: documentationfloor: documentationtake: documentationdrop: documentationGrading
In your README, also report:
Written: Roughly how long did this assignment take you (in hours)?
This assignment is worth 100 points, broken down by:
Submission
Submit the following 2 files on Gradescope:
a1.rktREADME.txt(orREADME.md)Attribution
Some exercises adapted from previous CS251 versions by Ben Wood and Carolyn Anderson.