000000.rkt, but replace 000000 with your generated random number. When you are finished with your exam, submit your exam on Pweb.
Assigned: Friday, 14 February 2020
Prologue Due: Sunday, 16 February 2020 by 10:30pm
Exam Due: Thursday, 20 February 2020 by 10:30pm
Cover Sheet Due: Friday, 21 February 2020 by the start of class
Epilogue Due: Friday, 21 February 2020 by 10:30pm
Please read the exam procedures page for policies, turn-in procedures, and grading details. If you have any questions about the exam, check the frequently asked questions at the bottom of the page and Piazza. We will generally spend some time in class every day on questions and answers while the exam is in progress.
While the exam is out, please check Piazza periodically to see if any errata have been reported.
Complete the exam using the
exam1.rkt starter source
code. Please rename this file to 000000.rkt, but replace
000000 with your generated random number.
The prologue for this examination will be via Pweb.
For each problem, please include a short note about something that will help you solve the problem. Mostly, we want to see some evidence that you’ve thought about the problem. You might note some similar procedures you’ve written or problems you’ve solved in the past (e.g., in a lab or on a homework assignment). You might note procedures that you expect to use. You might sketch an algorithm. You might pose a question to yourself. (We won’t necessarily read this in a timely fashion, so if you have questions for your instructor, you should ask by email or in person.)
If, when looking at a problem, you think you already know the answer, you can feel free to write something short like “solved” or “trivial”.
Which of those six problems do you expect to be the most difficult for you to solve? Why?
Conclude by answering the question What is an approach that you expect will help you be successful on this exam? For example, you might suggest that you will work thirty minutes on the exam each day, or work on the exam at 7pm each day, when your brain is most able to process information.
The epilogue for this examination will also be via Pweb.
What was the most difficult part of the exam?
What made that part difficult?
What are two things you can do to be more successful on the next exam?
Topics: Higher-Order Procedures, Creating Procedures, Documentation
In Cryptography, a Caesar cipher (also known as Shift cipher) is one of the simplest encryption techniques. In this technique, each letter in the plaintext is shifted a certain number of places down the alphabet. For example, a Caesar cipher with 10 shifts will change your message Game to Qkwo.
The algorithm is quite simple (You will find several articles explaining the process, like this one: https://en.wikipedia.org/wiki/Caesar_cipher). To keep the process even simpler, let’s just define the encryption process as the following:
new-character = old-character + shift-amount
If the characters are mapped to some numbers, then we can add the shift-amount to those numbers and map them to corresponding new characters. Recall that we learned a way to change characters into numbers in the reading on characters and strings in Scheme.
With all these clues, we are ready to implement a simple Caesar cipher procedure. Let’s write a procedure encrypt-a-char that takes a character as input and returns/encrypts a new character by shifting 2 positions.
> (encrypt-a-char #\t)
#\v
> (encrypt-a-char #\@)
#\B
> (encrypt-a-char #\6)
#\8
> (encrypt-a-char #\~)
#\u0080
> (encrypt-a-char #\*)
#\,
> (encrypt-a-char #\{)
#\}
> (encrypt-a-char #\L)
#\N
a. Write the 6P-style documentation for encrypt-a-char.
b. Implement encrypt-a-char using function composition. To avoid name overlap, you can call this encrypt-a-char-b. You may not use sectioning, lambda, or other procedures you define in implementing encrypt-a-char-b.
c. Implement encrypt-a-char using sectioning. To avoid name overlap, you can call this encrypt-a-char-c. You may not use lambda, or other procedures you define in implementing encrypt-a-char-c. You are allowed to use at most one composition to bind your procedures together.
d. Implement encrypt-a-char using lambda. To avoid name overlap, you can call this encrypt-a-char-d. You may not use sectioning, composition, or other procedures you define in implementing encrypt-a-char-d.
Topics: Writing Test suite, Writing Procedures, Documentation
Counting the frequency of the characters(or any data unit) is a common task in data science. For this part of the exam, you will be writing a procedure that does a similar task. Let’s think of a procedure count-frequency that takes two parameters (a string, str and a character, c) as input and returns the total frequency of c in the str.
> (count-frequency "csc-151" #\s)
1
> (count-frequency "csc-151" #\c)
2
> (count-frequency "csc-151" #\1)
2
> (count-frequency "csc-151" #\*)
0
> (count-frequency "csc-151-exam01" #\1)
3
a. Write 6P-style documentation for a procedure, count-frequency, that functions as described above.
b. Write a comprehensive test suite for count-frequency. Since you’ll need a procedure to test, start with this version.
(define count-frequency
(lambda (str chr)
(length (filter (section equal? <> chr) (string->list str)))))
Here is a test-suite to start with.
(define tests-count-frequency
(test-suite
"Tests of the count-frequency procedure"
(test-case
"short strings-unique-characters"
(check-equal? (count-frequency "str" #\s) 1))
(test-case
"short strings-repeated-characters"
(check-equal? (count-frequency "csc" #\c) 2))
(test-case
"longer strings"
(check-equal? (count-frequency "alphaalpha" #\a) 4))
))
Add two more test instances to each of the given test-cases and add one complete test-case (with three test instances).
Topics: filter, predicates, lists
In this problem we will compute the average length of strings in a list - but with a twist.
a. Write and document (with 6P’s) a procedure (string-starts-with? str char), which takes in a string and a character, and determines whether or not the string begins with that character. You can assume that all input strings will be lower-case. Here is an example of how your procedure should work:
> (string-starts-with? "hello" #\h)
#t
> (string-starts-with? "hello" #\j)
#f
b. Write and document (with 6P’s) a procedure (modified-average-length lst char) which takes in a list of strings, and a character. Your procedure should first remove any strings that begin with the given character, and then compute the average length of the remaining strings. You will likely find the procedure (string-length str) helpful (experiment with this procedure if it is unfamiliar to you).
> (define a-list-of-strings (list "fantastic" "day" "together" "scheme" "computer" "applesauce" "maybe"))
> (modified-average-length a-list-of-strings #\d)
7 2/3
> (modified-average-length a-list-of-strings #\a)
6 1/2
Topics: writing procedures, lists, strings
Suppose that the college keeps a list of all the courses offered, such as (list "CSC-151" "MAT-131" "SOC-111" "SPN-105"). In retrospect, the college wishes to include the semester information on each of the courses, such as “CSC-151-S20”.
a. Write and document (with 6P’s) a procedure (adjust-courses lst str) that takes in a list of strings and another string, str, and appends str to the end of every element in the list.
> (adjust-courses (list "CSC-151" "MAT-131" "SOC-111" "SPN-105") "-S20")
'("CSC-151-S20" "MAT-131-S20" "SOC-111-S20" "SPN-105-S20")
b. Write and document (with 6P’s) a procedure (adjust-courses-reverse lst num) that un-does the addition made in part a. For example, calling (adjust-courses-reverse lst 4) removes the last four characters from each of the strings in the list.
> (adjust-courses-reverse (list "CSC-151-S20" "MAT-131-S20" "SOC-111-S20" "SPN-105-S20") 4)
'("CSC-151" "MAT-131" "SOC-111" "SPN-105")
Topics: Tables, Sorting
Here is a list of Ice pokemon that you should copy into your definitions window. This data is from https://www.kaggle.com/abcsds/pokemon/data so you should cite it as well.
(define ice-pokemon
'((87 "Dewgong" "Water" "Ice" 475 90 70 80 70 95 70 1 "False")
(91 "Cloyster" "Water" "Ice" 525 50 95 180 85 45 70 1 "False")
(124 "Jynx" "Ice" "Psychic" 455 65 50 35 115 95 95 1 "False")
(131 "Lapras" "Water" "Ice" 535 130 85 80 85 95 60 1 "False")
(144 "Articuno" "Ice" "Flying" 580 90 85 100 95 125 85 1 "True")
(215 "Sneasel" "Dark" "Ice" 430 55 95 55 35 75 115 2 "False")
(220 "Swinub" "Ice" "Ground" 250 50 50 40 30 30 50 2 "False")
(221 "Piloswine" "Ice" "Ground" 450 100 100 80 60 60 50 2 "False")
(225 "Delibird" "Ice" "Flying" 330 45 55 45 65 45 75 2 "False")
(238 "Smoochum" "Ice" "Psychic" 305 45 30 15 85 65 65 2 "False")
(361 "Snorunt" "Ice" "" 300 50 50 50 50 50 50 3 "False")
(362 "Glalie" "Ice" "" 480 80 80 80 80 80 80 3 "False")
(362 "GlalieMega Glalie" "Ice" "" 580 80 120 80 120 80 100 3 "False")
(363 "Spheal" "Ice" "Water" 290 70 40 50 55 50 25 3 "False")
(364 "Sealeo" "Ice" "Water" 410 90 60 70 75 70 45 3 "False")
(365 "Walrein" "Ice" "Water" 530 110 80 90 95 90 65 3 "False")
(378 "Regice" "Ice" "" 580 80 50 100 100 200 50 3 "True")
(459 "Snover" "Grass" "Ice" 334 60 62 50 62 60 40 4 "False")
(460 "Abomasnow" "Grass" "Ice" 494 90 92 75 92 85 60 4 "False")
(460 "AbomasnowMega Abomasnow" "Grass" "Ice" 594 90 132 105 132 105 30 4 "False")
(461 "Weavile" "Dark" "Ice" 510 70 120 65 45 85 125 4 "False")
(471 "Glaceon" "Ice" "" 525 65 60 110 130 95 65 4 "False")
(473 "Mamoswine" "Ice" "Ground" 530 110 130 80 70 60 80 4 "False")
(478 "Froslass" "Ice" "Ghost" 480 70 80 70 80 70 110 4 "False")
(479 "RotomFrost Rotom" "Electric" "Ice" 520 50 65 107 105 107 86 4 "False")
(582 "Vanillite" "Ice" "" 305 36 50 50 65 60 44 5 "False")
(583 "Vanillish" "Ice" "" 395 51 65 65 80 75 59 5 "False")
(584 "Vanilluxe" "Ice" "" 535 71 95 85 110 95 79 5 "False")
(613 "Cubchoo" "Ice" "" 305 55 70 40 60 40 40 5 "False")
(614 "Beartic" "Ice" "" 485 95 110 80 70 80 50 5 "False")
(615 "Cryogonal" "Ice" "" 485 70 50 30 95 135 105 5 "False")
(646 "Kyurem" "Dragon" "Ice" 660 125 130 90 130 90 95 5 "True")
(646 "KyuremBlack Kyurem" "Dragon" "Ice" 700 125 170 100 120 90 95 5 "True")
(646 "KyuremWhite Kyurem" "Dragon" "Ice" 700 125 120 90 170 100 95 5 "True")
(698 "Amaura" "Rock" "Ice" 362 77 59 50 67 63 46 6 "False")
(699 "Aurorus" "Rock" "Ice" 521 123 77 72 99 92 58 6 "False")
(712 "Bergmite" "Ice" "" 304 55 69 85 32 35 28 6 "False")
(713 "Avalugg" "Ice" "" 514 95 117 184 44 46 28 6 "False")))
The columns of this dataset are:
# "Name" "Type 1" "Type 2" TotalStats HP Attack Defense Sp.Atk Sp.Def Speed Generation "Legendary"
Write and document a procedure highest-hp that takes as input a list of lists in the above format and finds the five Pokemon with the highest HP. The output should be in the form of a list of lists with ("PokemonName" HP) so that it is easier for humans to read.
Here is an example:
> (highest-hp ice-pokemon)
'(("Lapras" 130) ("Kyurem" 125) ("KyuremBlack Kyurem" 125) ("KyuremWhite Kyurem" 125) ("Aurorus" 123))
Topics: Reading data from files, Heterogeneous lists, Sorting
Download the Pokemon statistics data set which contains data on 800 Pokemon in the format:
#,Name,Type 1,Type 2,TotalStats,HP,Attack,Defense,Sp. Atk,Sp. Def,Speed,Generation,Legendary
Such as:
1,Bulbasaur,Grass,Poison,318,45,49,49,65,65,45,1,False
This data set comes from https://www.kaggle.com/abcsds/pokemon/data, so be sure to cite it.
Write and document a procedure most-common-primary-types that takes as input a string FILENAME (not a list!) that is the location of a file of the above format, and outputs the top five most common primary types (i.e. the entry in the Type 1 column) as a list of lists with the type as a string and the number of the type as a number.
Here is an example based on the main file:
> (most-common-primary-types "/home/username/Desktop/Pokemon.csv")
'(("Water" 112) ("Normal" 98) ("Grass" 70) ("Bug" 69) ("Psychic" 57))
To preserve your anonymity, remove your username from your examples!
Note that there is a header in the file and your procedure should remove it. Your procedure should work on any file with a header and the correct format.
We will post answers to questions of general interest on Piazza while the exam is in progress. Please check on Piazza before emailing questions!
lambda that looks like (define (proc params) body). Can I use that?(random 1000000). If you end up with a number less than six digits, add zeros to the left side of the number until you have six digits.; STUB on some of the procedures. What does that mean?Some of the problems on this exam are based on—and at times copied from—problems on previous exams for the course. Those exams were written by Charlie Curtsinger, Janet Davis, Rhys Price Jones, Titus Klinge, Samuel A. Rebelsky, John David Stone, Henry Walker, and Jerod Weinman. Many were written collaboratively, or were themselves based upon prior examinations, so precise credit is difficult, if not impossible.
Some problems on this exam were inspired by conversations with our students and by correct and incorrect student solutions on a variety of problems. We thank our students for that inspiration. Usually, a combination of questions or discussions inspired a problem, so it is difficult and inappropriate to credit individual students.