Exam 4 – Advanced Scheming

Assigned

Friday, May 8, 2020

Due

Friday, May 15, 2020 by 05:00pm

Collaboration

You may not receive help from any person other than the instructor for this exam. See the exam procedures for a detailed description of the resources you can and cannot use.

Submitting

Rename the starter code file to 000000.rkt, but replace 000000 with your generated random number. Submit this file on Pweb when you are finished.

Exam 4

Assigned: Friday, 8 May 2020

Prologue Due: Sunday, 10 May 2020 by 10:30pm

Exam Due: Friday, 15 May 2020 by 05:00pm

Cover Sheet Due: Friday, 15 May 2020 by 05:00pm

Epilogue Due: Friday, 15 May 2020 by 05:00pm

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 and Piazza.

While the exam is out, please check back periodically to see if we have reported any new errata.

Complete the exam using the exam4.rkt starter source code.

Prologue

The prologue for this examination will be via Pweb.

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 six 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 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 in a CSC-161 exam? If you don’t plan to take CSC-161, what have you learned that will help you to be successful in another discipline?

Problem 1: Testing Sorts

Topics: Sorting, Testing

Write a comprehensive test suite for a sorting procedure (my-sort lst may-precede?). You should name your test suite test-my-sort. Your test suite should work for any of the sorting algorithms that we have seen that use the specified signature.

To receive full credit, your test suite must have at least nine test cases that cover distinct categories of input. Each test case must be labeled with a descriptive name, and have at least three checks that fit that description.

Problem 2: Line of File

Topics: File Recursion, Strings, Error Handling

Write and document a file recursive procedure (line-num filename num) that returns the num^th line in the file or raises an error if the file does not have enough lines where the error specifically says “The file only has num lines”. You need to match that error message exactly where num should be the number of lines in the file.

For example, for this file, you would see:

> (define file "/home/username/Desktop/example_grades.csv")
> (line-num file 0)
"Name,Potions,DADA,Muggle Studies"
> (line-num file 2)
"Hermione Granger,Outstanding,Outstanding,Outstanding"
> (line-num file 5)
. . The file only has 4 lines
> (line-num file 4)
. . The file only has 4 lines

You may not use file->lines or any of the other file-> procedures. You may only use read, read-line, read-char, and peek-char to retrieve data from the input port.

Problem 3: Arithmetic Sequence Generator

Topics: List Recursion, Testing Preconditions

An arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. If the initial term of a sequence is a, and the common difference of successive sequences is d, then the n^th term of the sequence is a + (n - 1) * d. For example, 1, 3, 5, 7, 9 is an arithmetic sequence of 5 numbers where the initial term is 1, and the difference between each consecutive terms is 2.

Define and document a procedure (series-generator a d n) that generates a list of n terms of the following arithmetic sequence: a, a + d, a + 2d, ..., (a + (n-1) * d)

Your procedure must also verify all preconditions and catch any possible errors in the user input.

> (series-generator 1 2 5)
'(1 3 5 7 9)
> (series-generator 0 5 5)
'(0 5 10 15 20)
> (series-generator 0 -5 5)
'(0 -5 -10 -15 -20)
> (series-generator 0.5 5 5)
'(0.5 5.5 10.5 15.5 20.5)
> (series-generator 0.5 5 0)
'()

Problem 4: Using Binary Search

Topics: binary search

Below is a group of students. For each we have a first name, last name, id, major, and class year. The students are sorted by first name.

(define simulated-students
  (vector
   (list "Annie"     "Edison"   1336804 "General Science"   2019) ;  0
   (list "Bob"       "Smith"    1170605 "Mathematics"       2020) ;  1
   (list "Cally"     "Griffin"  1512121 "Literature"        2017) ;  2
   (list "Charlotte" "Davis"    1304091 "Independent"       2018) ;  3
   (list "Dee"       "Reynolds" 1472662 "Undeclared"        2021) ;  4
   (list "Dwight"    "Schrute"  1546921 "German Studies"    2018) ;  5
   (list "Eddie"     "Huang"    1320727 "Music"             2019) ;  6
   (list "Ezra"      "Smith"    1260057 "Chinese"           2018) ;  7
   (list "George"    "Bluth"    1668280 "Economics"         2020) ;  8
   (list "Heather"   "Jones"    1046860 "Classics"          2021) ;  9
   (list "Ira"       "Jackson"  1070103 "Political Science" 2022) ; 10
   (list "Ivan"      "Ivanoff"  2987612 "French"            2017) ; 11
   (list "Jason"     "Mendoza"  1488985 "Dance"             2019) ; 12
   (list "Karla"     "Hill"     1821167 "Psychology"        2018) ; 13
   (list "Leon"      "Black"    1399810 "GWSS"              2019) ; 14
   (list "Liz"       "Lemon"    1168059 "Theatre"           2020) ; 15
   (list "Ned"       "Chang"    1177023 "Russian"           2018) ; 16
   (list "Otto"      "White"    1908656 "Chinese"           2019) ; 17
   (list "Paula"     "Hall"     1218704 "Computer Science"  2018) ; 18
   (list "Raymond"   "Holt"     1679081 "Classics"          2018) ; 19
   (list "Ron"       "Swanson"  1658200 "History"           2020) ; 20
   (list "Selina"    "Meyer"    1085519 "Political Science" 2018) ; 21
   (list "Ted"       "Tedly"    1480618 "GWSS"              2019) ; 22
   (list "Tiger"     "King"     1818181 "Biology"           2022) ; 23
   (list "Urkle"     "Andersen" 1681805 "Anthropology"      2018) ; 24
   (list "Violet"    "Teal"     1493989 "Economics"         2019) ; 25
   (list "Xerxes"    "Homer"    1547425 "Economics"         2019) ; 26
   (list "Yvonne"    "Stein"    1748611 "Sociology"         2018) ; 27
   (list "Zed"       "Rebel"    1540899 "Computer Science"  2017) ; 28
   ))

Suppose we are looking for Titus. The binary search algorithm starts with a lower bound of 0 and an upper bound of 28. The midpoint is 14. The key of element 14 is Leon, so we recurse on the right half. Finish the table below to show the steps binary search goes through in finding (or not finding) Titus.

; lower   upper   middle  middle-elt  conclusion 
; 0       28      14      Leon        too small
;
;
;
;

Note: There may or may not be enough rows in the table. You need to determine the actual number of steps that binary search takes.

Problem 5: Vector to String

Topics: vectors, recursion

Write and document (using 6P’s) a recursive procedure vector->string which takes in a vector of characters and returns a string of the characters concatenated together.

> (vector->string (vector #\a #\b #\c))
"abc"
> (vector->string (vector))
""
> (vector->string (vector #\a))
"a"
> (vector->string (vector #\z #\y #\x #\w #\v #\u))
"zyxwvu"

Note: You may not convert the vector into a list, or use any list procedures. Further, you may not create a new vector. The point of this problem is to use recursion.

Frequently Asked Questions

Do we need to document locally-defined procedures?

No.

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.

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.

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

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

Yes. The title and URL should suffice.

Can I use other websites as a reference for 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). 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.

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.02. 6 September 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. You should remove these comments as you replace stub procedures with real implementations.

How exhaustive do our postconditions need to be when writing 6P-style documentation?

Your postconditions are not a test suite, but they should capture all of the procedure’s behavior. You do not need to give specific input/output examples, but describe what is true about the output as much as you can in a few concise lines.

Are there any requirements for informal tests?

Sort of. They should be good tests, though they need not be exhaustive. Your informal tests only count if they are different from the examples on the exam.

Do we need to show examples of running our helper procedures?

No, but you should be checking them carefully. You don’t need to include these examples in your exam.

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.