Exam 2: Expanding your Scheme skills

Assigned: Wednesday, 28 February 2018

Prologue Due: Friday, 2 March 2018 by 10:30pm

Exam Due: Tuesday, 6 March 2018 by 10:30pm

Cover Sheet Due: Wednesday, 7 March 2018 by the start of class

Epilogue Due: Wednesday, 7 March 2018 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 Q&A at the bottom of this page. 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 back periodically to see if we have reported any new errata.

Complete the exam using the exam02.rkt starter source code. Please rename this file to 000000.rkt, but replace 000000 with your generated random number.

Prologue

The prologue for this examination will be via email, which you should send to your instructor. Your message should be titled CSC 151.01: Exam 2 Prologue (your name).

1. 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”.

2. Which of those problems do you expect to be the most difficult for you to solve? Why?

3. 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.

Epilogue

The epilogue for this examination will also be via email, which you should send to your instructor. Your message should be titled CSC 151.01: Exam 2 Epilogue (your name). Include answers to the following questions.

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?

Problem 1: Even numbers between

Topics: lists, iota, documentation, precondition testing

Generating a list of all numbers between 0 and n with (iota n) has been handy in a variety of algorithms. Consider a similar procedure (evens-between lower upper), that creates a list of all the even integers between lower and upper, inclusive. For example,

> (evens-between 0 10)
'(0 2 4 6 8 10)
> (evens-between 3 7.5)
'(4 6)
> (evens-between -2 5)
'(-2 0 2 4)
> (evens-between 1.0 5)
Error: The lower bound is not exact.

a. Document evens-between.

b. Implement the kernel of this procedure. That is, write a procedure (evens-between-kernel lower upper), that produces a list of the values between lower and upper. Your procedure should not build an intermediate list that is significantly longer than the result list. (A factor of two or three is acceptable. Much more than that is not acceptable.)

c. Implement the husk of this procedure. That is, write a procedure that checks all of the preconditions of evens-between and reports an appropriate error for each one.

Problem 2: Testing evens-between

Topics: testing

Write a comprehensive test suite for evens-between.

Here’s the start of a test suite.

(define tests-evens-between
  (let ([check-error
         (lambda (proc)
           (check-exn (conjoin exn:fail? (negate exn:fail:contract?))
                      proc))])
    (test-suite
     "Tests of the evens-between procedure"
     (test-case
      "Lower and upper are both even"
      (check-equal? (evens-between 0 10)
                    '(0 2 4 6 8 10)))
     (test-case
      "Preconditions are not met"
      (check-error (lambda () (evens-between "a" "b")))))))

Note: You should also verify that evens-between issues appropriate errors using the check-error procedure provided in the above test-evens-between suite. Note that your tests need to have an extra (lambda () ...) wrapping your test so that the error is not thrown before check-error is called.

Problem 3: Identifying unique column elements

Topics: compound data, documentation

Let us return once again to one of our favorite dataset examples: a list of courses. We are now storing the list of courses as a CSV file, grinco-2018S.csv.

(define grinco-2018S (read-csv-file "grinco-2018S.csv"))

> (take-random grinco-2018S 12)
'((81338 "ALS" 100 2 "Italian I" "Moisan, Claire" 5 8 2.0)
  (81349 "ALS" 101 4 "Brazilian Portuguese II" "Moisan, Claire" 2 8 2.0)
  (80686 "ART" 246 1 "Digital Media" "Kaufman, Andrew" -1 15 4.0)
  (79907 "BIO" 334 1 "Plant Physiology w/lab" "DeRidder, Benjamin" 0 12 4.0)
  (81282 "CHM" 499 3 "MAP: Redox Ligand Coord Synth" "Kamunde-Devonish, Maisha" 0 1 4.0)
  (81234 "LIN" 397 2 "IP: Chld Sntx&Nonwrd Use&Cmp" "Kelty-Stephen, Emma" 0 1 4.0)
  (80015 "MAT" 220 1 "Differential Equations" "French, Christopher P." 1 28 4.0)
  (80662 "MAT" 295 2 "ST: Intro to Data Science" "Jonkman, Jeffrey" 0 15 4.0)
  (80204 "MUS" 120 24 "Perf: Flute" "Anderson, Claudia" 30 34 1.0)
  (80979 "MUS" 221 44 "Perf: Adv Voice" "Neher, Lisa R" 20 20 2.0)
  (80287 "MUS" 221 46 "Perf: Adv Oboe" "Wohlenhaus, Jennifer" 20 20 2.0)
  (80343 "PHE" 100 24 "Beginning Swimming" "Hurley, Erin D" 9 12 0.5))

As you may have noticed, the values in some columns are duplicated. For example, we see multiple entries for "MAT" in column 1 and for "Moisan, Claire" in column 5. It is sometimes useful to extract the list of unique values in a column.

Write, but do not document, a procedure, (extract-unique table column), that makes a list of the unique values in a column. You need not present those values in any particular order.

> (define departments (extract-unique grinco-2018S 1))
> (take departments 5)
'("ALS" "AMS" "ANT" "ARB" "ARH")
> (length departments)
54
> (drop departments (- (length departments) 5))
'("SST" "TEC" "THD" "THS" "WRT")

> (define sections (extract-unique grinco-2018S 3))
> sections
'(1 2 4 5 7 8 10 3 6 9 11 14 17 19 20 12 13 15 16 18 21 23 24 25 26 27 28 35 38 39 40 41 42 43 44 45 46 48 49 99 32 "36A" "36B" "36C" 55 56 22)

> (define faculty (extract-unique grinco-2018S 5))
> (take faculty 5)
'("Moisan, Claire" "Scott, Kesho" "Gibel Mevorach, Katya S" "Quinsaat, Sharon" "Purcell, Sarah J")
> (length faculty)
258
> (drop faculty (+ -5 (length faculty)))
'("Thomas, Justin M" "Miller, Claudia E" "Rudolph, William K" "Wohlwend, Helyn A" "Price, Taylor")

> (extract-unique (filter (lambda (entry)
                            (equal? (cadr entry) "CSC"))
                          grinco-2018S)
                  5)
'("Rebelsky, Samuel" "Klinge, Titus" "Walker, Henry M" "Vostinar, Anya" "Osera, Peter-Michael Santos" "Curtsinger, Charles Miskimen" "Weinman, Jerod")

Problem 4: Describing files

Topics: conditionals, files

Write, but do not document, a procedure, (describe-file fname), that takes the name of a text file as input and prints a simple description of the file according to the following policies.

• If the file contains no characters, you should return the string "empty".
• If the file contains fewer than 1000 words, the description should begin with the phrase "a short file".
• If the file contains at least 1000 words but fewer than 10,000, the description should begin with the phrase "a medium-length file".
• If the file contains at least 10,000 words but fewer than 100,000, the description should begin with the phrase "a large file".
• If the file contains at least 100,000 words, the description should begin with the phrase "a very large file".
• If the average line length is less than twenty characters, the description should include the phrase "containing mostly short lines".
• If at least 1/3 of the words in the file are under five characters, the description should include the phrase "with many short words".
• If at least 1/3 of the words in the file are over eight characters, the description should include the phrase "with many long words".
• If any of conditions above are not met, the description should not include the corresponding phrase.

For example,

> (describe-file "/home/rebelsky/share/files/long-short.txt")
"a short file with many short words with many long words"
> (describe-file "/home/rebelsky/share/files/pg1260.txt")
"a very large file with many short words"
> (describe-file "/home/rebelsky/share/files/five-syllables.txt")
"a short file containing mostly short lines with many long words"
> (describe-file "/home/rebelsky/share/files/empty.txt")
"empty"

Problem 5: Visualizing speech information

Topics: data visualization, strings, compound data

Suppose that we have a table of speeches, each entry of which represents one speech and contains two strings, which correspond to the speaker name and the words that they said.

(define some-speeches
  (list (list "Joe" "My name is Joe")
        (list "Jane" "I heard that Abraham Lincoln once said that ...")
        (list "Joe" "My name is still Joe")
        (list "Jae" "I am not inclined to speak at length, nor on matters ...")
        (list "Joe" "It's still Joe")
        (list "Jo" "I am often mistaken for another person. Let me explain ...")
        (list "Joe" "I'm not Jo")
        ...))

a. Write, but do not document, a procedure, (visualize-speeches speeches) that takes a list of that form as input and makes a scatterplot in which the x-axis represents the number of words in a speech and the y-axis represents the average word length in the speech.

You may choose to treat words as “anything separated by spaces”, and therefore get the words by splitting the speech at the space character.

b. Of course, our scatterplot would be much more useful if we could identify the speakers. Write, but do not document, a procedure, (visualize-speeches-prime speeches speakers colors), that behaves much like visualize-speeches except that it also takes a list of speakers and a list of colors of the same length. You should use the ith color for the points that correspond to the ith speaker name. If a speaker does not appear in the list of speakers, you should use a black point.

c. It is not clear that scatterplots are the best way to visualize this information. Write, but do not document, a procedure, (speech-histogram speeches), that creates a histogram of the ratio of speech length to average word length. Your histogram should have one bar per speech and have the speaker name under the bar.

Problem 6: Whatzitdo?

Topics: sectioning, filters, documentation, local bindings

Sometimes students (and professors) use unhelpful variable names and procedure names such as helper. For example, consider the following procedure.

(define helper1
  (let ([helper1 (o positive? string-length)]
        [helper2 (o car string->list)])
    (let ([helper3 #\A]
          [helper4 #\M])
      (let* ([helper3 (section char-ci<=? helper3 <> helper4)]
             [helper4 (o helper3 helper2)])
        (section filter (conjoin helper1 helper4) <>)))))

a. Rename the procedure and the locally bound variables so that they will make sense to the reader.

b. Clean up the code so that it is easier to read.

c. Write 6P-style documentation for the procedure.

d. Explain how the code achieves its purpose.

Questions and answers

We will post answers to questions of general interest here while the exam is in progress. Please check here before emailing questions!

Initial questions and answers

Are we allowed to talk to others about general issues from the first few weeks of class, such as the syntax of section?

No. We’ve had too many problems with “slippery slope” issues.

Questions should go to the instructors.

What is a general question?

A question that is about the exam in general, not a particular problem.

Do all the sections have the same exam?

Yes.

Can we still invoke the “There’s more to life” clause if we spend more than five hours on the exam?

Yes. However, we really do recommend that you stop at five hours unless you are very close to finishing. It’s not worth your time or stress to spend more effort on the exam. It is, however, worth your time to come talk to us, and perhaps to get a mentor or more help (not on this exam, but on the class). There’s likely some concept you’re missing, and we can help figure that out.

What do you mean by “implement?”

Write a procedure or procedures that accomplish the given task.

Do we have to make our code concise?

You should strive for readable and correct code. If you can make it concise, that’s a plus, but concision is secondary to readability and correctness. Long or muddled code is likely to lose points, even if it is correct.

Much of your sample 6P-style documentation has incomplete sentences. Can we follow that model? That is, can we use incomplete sentences in our 6P-style documentation?

Yes, you can use incomplete sentences in 6P-style documentation.

You tell us to start the exam early, but then you add corrections and questions and answers. Isn’t that contradictory? Aren’t we better off waiting until you’ve answered the questions and corrected any errors?

We think you’re better able to get your questions answered early if you start early. Later questions will generally receive a response of “See the notes on the exam.”

How do we know what our random number is?

You should have received instructions on how to generate your random number on the day the exam was distributed. If you don’t have a number, ask your professor for one before submitting your exam.

To show we’ve tested the code informally, would you just like us to just post the inputs we used to test the procedure? If so, how should we list those?

Copy and paste the interactions pane into the appropriate place in the definitions pane. Put a #| before the pasted material. put a |# after the pasted material.

Should we cite our partner from a past lab or assignment if we use code from a past lab or assignment?

You should cite both yourself and your partner, although you should do so as anonymously as possible. For example “Ideas taken from the solution to problem 7 on assignment 2 written by student 641321 and partner.”

If we write a broken procedure and replace it later, should we keep the previous one?

Yes! This will help us give you partial credit if your final procedure isn’t quite right. But make sure to comment out the old one using #| and |# or semicolons. You might also add a note or two as to what you were trying to do.

Do I need to document helper procedures?

You must document helpers using the 4Ps.

Can I use procedures that we have not covered in class?

Probably not. Ask about individual procedures if you’re not sure.

Can I use list-ref? I’d swear we’ve used it, but I can’t find where.

You may certainly use list-ref.

I discovered a way to define procedures without using lambda that looks like (define (proc params) body). Can I use that?

No.

Is extra credit available on this exam?

No explicit extra credit is available. However, we may find that you’ve come up with such wonderful answers that we cannot help but give you
extra credit. (Don’t laugh. It happens almost every time.)

DrRacket crashed and ate my exam. What do I do?

Send your instructor the exam file and any backups that DrRacket seems to have made. (Those tend to have a similar file name, but with pound signs or tildes added at the front or back.)

How do I know when you’ve added a new question or answer?

We try to add a date stamp to the questions and answers.

Should we cite readings from the CSC 151 website? If so, how much information should we give.

Yes. The title and URL should suffice.

Can I use some other websites (different from ours websites) to solve problems in the exam?

As the exam policies page states, “This examination is open book, open notes, open mind, open computer, open Web.” Note that it also states “ If you find ideas in a book or on the Web, be sure to cite them appropriately.”

Do we have to cite the exam itself?

No.

How do I generate a random six digit number?

(random 1000000)

How do I submit my exam?

Name it 012345.rkt (substituting your random number)

Send it to your instructor, not the grader, as an attachment in an email message entitled “CSC 151 Exam 1” (or something similar)

Some of the problems are based on a recent homework assignment. Should I cite my work on that assignment?

If you refer to your work on that assignment, you should cite it.

How do I cite my work on an assignment?

Something like “Student 123456 and partner. Homework Assignment 3. CSC 151.. 6 February 2018.”

I see the comment ; STUB on some of the procedures. What does that mean?

We use the term “STUB” for a procedure that gives some default value, rather than the correct one. Stub procedures are useful when you need the procedure to exist during development, but have not yet had time to implement it.

Why don’t we get extra credit for errors in the Q&A, errata, or code?

We hope to get those answers out quickly and, in doing so, we may make the occasional mistake.

How many examples are enough for each procedure?

You should have at least three or four examples for each procedure.

Time logs

What should I record for “Elapsed” in the time log?

The difference between the time you finished and started the entry. (E.g., 30 min.)

What should I record for “Activity” in the time log?

What you spent the time on. For example, you might have been writing test cases, or failed solutions, or ….

Can you provide a sample?

Sure.

; Time Log:
;   Date        Start   Finish  Elapsed Activity
;   2018-02-08  18:00   18:20   20 min  Wrote four tests
;   2018-02-08  20:30   21:00   30 min  Three non-working versions
;                                       (marked as a, b, and c below).
;                                       Decided to sleep on it.
;   2018-02-09  08:00   08:10   10 min  Woke up with an idea.  Coded it.
;                                       it seems to work
;   2018-02-09  19:00   19:10   10 min  A few more tests just to make
;                                       sure.  Done!

What should I do if I see others collaborating inappropriately on the exam?

Ideally, you would report the issue to one of us and we would deal with it. Minimally, you should refuse to sign the second half of the academic honesty statement.

New general questions

Questions on problem 1

It appears that the lower bound must be exact and the upper bound can be inexact. Is that the intent? [2018-02-28 6:00 p.m.]

Yes.

Questions on problem 5

Can you please give a sample call to visualize-speeches-prime? [2018-03-02, 5:20 p.m.]

Sure

(visualize-speeches-prime some-speeches
                          (list "Joe" "Jane" "Jae")
                          (list "Red" "Blue" "Purple"))

Errata

Please check back periodically in case we find any new issues.

• The exam contains various grammatical errors. (+1, JB)
• The URL for the dataset on problem 3 was broken. (+1, RZ)
• “If any of the problem above is not met” should probably be “If any of the problems above are not met”. (+1, OM)
• The exam starter file and the problem description had inconsistent names for the parameters. (+1 TK section, AI; +0 SR section)

Citations

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.