Sieve of Eratosthenes (individual assignment)

1. Get started
2. Map-reduce warm up
3. Main task
4. Sieve of Eratosthenes
5. Capstone work
- 5.1. count-smaller-primes
- 5.2. twin-primes
6. Other info
7. How to test and submit your work
- 7.1. Testing your work
- 7.2. Submitting your work

This assignment is to be done individually. You can talk to other people in the class, me, and any of the course staff (graders, lab assistants, prefects) for ideas and to gain assistance. You can get direct help debugging your code from me and any of the course staff, and you're welcome to show us your code during debugging or other conversations. The code that you write should be your own, and you shouldn’t directly show or share your code with other students (although you may discuss general debugging strategies with others). See the course syllabus for more details or just ask me if I can clarify.

1 Get started

You'll download the folder with the starter code from the link below. Like for homeworks 1 and 2, unzip the folder and move it to where you'd like: the folder for the Docker container if you're using Docker, or COURSES if you're not. Then get started in VS Code (see Homework 1 if you get stuck).

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter code.

2 Map-reduce warm up

Before getting to the main task, you'll apply your knowledge of the map-reduce framework that we talked about this week. Using one or more of the functions map, fold-left, and fold-right, write a function sum-squared-values that gets the sum of the squares of all numbers in a list that are less than 5. For instance, (sum-squared-values '(2 3 19 1)) would return 14 (which is 2*2 + 3*3 + 1*1). Your function should not implement any recursion itself, but it must call at least one of map, fold-left, or fold-right.

Include the import for rnrs in your .scm file:

(use-modules (rnrs))

Note that you might see a warning when you run the tests of the form "WARNING: (guile-user): imported module (rnrs) overrides core binding `map'". You can ignore this warning.

3 Main task

Recall that a lazy list is a useful structure for representing a long or even infinite list. A lazy list is represented in Scheme with a cons cell, where the "car" contains a data item and the "cdr" contains a function which returns the rest of the lazy list. If the function returns #f, the list is empty. Write the following functions that create and manipulate lazy lists.

3.1 seq

(seq first last)

This function takes two integers and returns an integer lazy list containing the sequence of values first, first+1, ... , last. This is just a renaming of the function gen-lazy-list from a previous assignment, but I encourage you to write it from scratch to make sure you feel confident about what's going on.

3.2 inf-seq

(inf-seq first)

This function takes an integer and returns an integer lazy list containing the infinite sequence of values first,first+1, ....

3.3 first-n

(first-n lazy-list n)

This function takes a lazy list and an integer and returns an ordinary Scheme list containing the first n values in the lazy-list. If the lazy list contains fewer than n values, then all the values in the lazy list are returned. You may assume that n is an integer greater than or equal to 1. If the lazy list is empty, return an empty Scheme list.

3.4 nth

(nth lazy-list n)

This function takes a lazy list and an integer and returns the n-th value in the lazy-list (counting from 1). If the lazy-list contains fewer than n values, then #f is returned.

3.5 filter-multiples

(filter-multiples lazy-list n)

This function returns a new lazy list that has n and all integer multiples of n removed from lazy-list. For example, a non-lazy list version of filter-multiples would behave as follows:

(filter-multiples '(2 3 4 5 6) 2) ;; Returns (3 5)
(filter-multiples  '(3 4 5 6 7 8) 3) ;; Returns (4 5 7 8)

4 Sieve of Eratosthenes

A wide variety of techniques have been devised to compute prime numbers (numbers evenly divisible only by themselves and 1). One of the oldest techniques is the "Sieve of Eratosthenes." Here's how it works.

You start with the infinite list L = 2, 3, 4, 5, …. The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7, 9, …. The head of this list (3) is a prime. Moreover, if you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, …. Repeating the process, you repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples of the head value.

You are to write an function (primes) that computes a lazy list containing all prime numbers, starting at 2, using the Sieve of Eratosthenes. Here are some sample usages:

(first-n (primes) 10) ;; Returns  (2 3 5 7 11 13 17 19 23 29)
(nth (primes) 20) ;; Returns 71

(Possibly useless hint: Create a recursive function (sieve lazy-list) that "sieves" the first item from the rest, returning a new lazy list. It uses filter-multiples, but adds an additional recursive operation.)

5 Capstone work

Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.

5.1 count-smaller-primes

Create a function called count-smaller-primes that takes a single integer as a parameter, and counts the number of primes less than that number. For example:

(count-smaller-primes 11) ;; Returns 4

You should be using your lazy list of primes to do this, rather than some other technique that generates prime numbers.

5.2 twin-primes

Create a function called twin-primes that generates an infinite lazy list of all twin prime pairs, in order. Twin primes are two prime numbers that are only two apart from each other. For example:

(first-n (twin-primes) 5) ;; Returns ((3 . 5) (5 . 7) (11 . 13) (17 . 19) (29 . 31))

6 Other info

You may not use side-effects (e.g. set!). You may use helper functions.

7 How to test and submit your work

7.1 Testing your work

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here.

7.2 Submitting your work

You'll submit your work on Gradescope. First, create a CollaborationsAndSources.txt file in the same folder as your code. In that file, indicate in what ways (if any) you collaborated with other people on this assignment and . Indicate any people you talked about the assignment with besides me (Anna) and our prefect. Did you share strategies with anyone else? Talk about any annoying errors and get advice? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file. Give the names of people you talked with and some description of your interactions. If you used any resources outside of our course materials, that is also something to note in Collaborations.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly in CollaborationsAndSources.txt. Look back at the Scheme intro 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After making CollaborationsAndSources.txt and finishing the assignment, upload your files on Gradescope. Note that if you submit a zip, you should submit a zip of the files, not a zip of the folder that contains the files. If all tests fail on Gradescope but they're working on your machine, this is likely the problem.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a very small but possible chance that you have coded something highly unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

All M tests pass
Your sum-squared-values uses at least one of map, fold-left, and/or fold-right as an integral part of its logic.
A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs see Homework policies for more on this).
You have a CollaborationsAndSources.txt with the information described above.

You'll earn an E if:

All conditions above for an M are met.
All the E tests pass.
Your code is not significantly more complex than needed to accomplish the task.
You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file. You have two revisions to use at any point during the term if you earn an SP or M grade and would like to revise your code and have us change your grade.

Good luck, ask questions, and have fun!

Assignment originally designed by Dave Musicant - thanks for sharing!