Exam 2 – Expanding Your Scheme Skills

Assigned

Friday, Mar 6, 2020

Due

Thursday, Mar 12, 2020 by 10:30pm

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 with your exam.

Exam 2

Assigned: Friday, 6 March 2020

Prologue Due: Sunday, 8 March 2020 by 10:30pm

Exam Due: Thursday, 12 March 2020 by 10:30pm

Cover Sheet Due: Friday, 13 March 2020 by the start of class

Epilogue Due: Friday, 13 March 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 exam2.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 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 on the next exam?

Problem 1: Determining List Contents

Topics: filter, predicates, lists, conditionals

Write and document (with 6P’s) a procedure (list-contains? lst type?) that takes in a list and a built-in Scheme predicate, and determines whether or not the list contains that type. For example,

> (list-contains? (list 1 2 3 4) number?)
#t
> (list-contains? (list "We" "love" "Scheme" #t) exact?)
#f

The predicates for which your solution must work are number?, exact?, inexact?, rational?, integer?, real?, string?, char?, boolean?, and list?.

Problem 2: Find a sublist

Topics: Recursion, Lists, Recursion with helpers

a. Write and document (with 4P’s) a recursive procedure remove-item that takes in a list and an element, and removes that element from the list. For example,

> (remove-item  (list 1 2 3 3) 2)
'(1 3 3)
> (remove-item  (list 1 2 3 3) 3)
'(1 2 3)
> (remove-item  (list 1 2 3 3) 4)
'(1 2 3 3)
> (remove-item  (list "D" "C" "B" "A") "C")
'("D" "B" "A")

Note: You may not use the built-in remove procedure in your solution.

b. Write and document (with 6P’s) a procedure sublist? that takes in two lists, and determines whether or not one list is contained within the other. For example,

> (sublist? (list 1 2 3 4) (list 1 2))
#t
> (sublist? (list 1 3) (list 1 2 3 4))
#t
> (sublist? (list 1 3 3) (list 1 2 3 4))
#f
> (sublist? (list "go" "above" "and" "beyond") (list "go" "above" "and" "beyond" "you" "will"))
#t
> (sublist? (list "go" "above" "and" "beyond") (list "no"))
#f
> (sublist? (list 2 1) (list 1 2 3 4))
#t

Note: You may use the built-in index-of in your solution.

Problem 3: WhatzItDo?

Topics: Let, Let, Recursion*

Sometimes students (and professors) come up with difficult-to-read solutions to simple problems, like this one below:

(define list-ref (lambda (char make-list) (let ([string 

(if (not (null? char)) (car char) null)])(cond [

(empty? string) null] [else (let* ([and 

(car string)][or  (cadr string)][not 

(caddr string)][predicate? (* 

and not)]) (sort (cons (

list or predicate?) 

(list-ref (cdr char) 

make-list))(lambda

(string char)(

make-list (cadr 

string) (cadr 

char))

)))]

)))

)

a. Clean up this procedure. You should reformat the code; rename the procedure, parameters, and variables; and simplify any unnecessarily complicated code.

b. Write 6P-style documentation for the code.

c. Explain how the code achieves its purpose.

Problem 4: Are the Elements in Order?

Topics: Recursion, Lists, Husk, Kernel, Error Handling

Write and document (with 6P’s) a predicate items-in-order? that takes a list lst and a string str-op as parameters, and checks if the all the elements of the list are maintaining the order according to the stated string str-op. Your procedure should only consider one from {strictly-increasing, increasing , strictly-decreasing, decreasing, equal} as valid entries for str-op and the list should contain numbers. Add proper statements to catch possible errors made by the end-user.

> (items-in-order? (list 333 223 123) "strictly-decreasing")

"The items are in order :)"

> (items-in-order? (list 333 223 223 123) "strictly-decreasing")

"The items are not in order :("

> (items-in-order? (list 333 223 223 123) "decreasing")

"The items are in order :)"

> (items-in-order? (list 123 123 123 123) "equal")

"The items are in order :)"

> (items-in-order? (list 123 123 123 123) "increasing")

"The items are in order :)"

> (items-in-order? (list 123 123 "123" 123) "increasing")

. . Some elements of the list are not numbers:  (123 123 "123" 123)

> (items-in-order? (list 123 123 "123" 123) >)

. . Some elements of the list are not numbers:  (123 123 "123" 123)

> (items-in-order? (list 123 123 123) >)

. . Insert a valid relational operator statement:  #<procedure:>>

Note: Be sure that your output is exactly as shown in the examples. This is required for your solution to pass our testing.

Problem 5: Highest HP Preconditions

Topics: verifying preconditions

You previously wrote a procedure (highest-hp lst) that takes a list of lists of Pokemon information and returns a list of lists of the five Pokemon with the highest HP from the list in a readable format. That procedure has many preconditions necessary for it to work and so now you will write a husk that verifies those preconditions before running the procedure.

The following kernel is provided in your exam starter code:

(define highest-hp-kernel
  (lambda (lst)
    (let ([higher-hp (lambda (poke1 poke2)
                       (> (list-ref poke1 5) (list-ref poke2 5)))]
          [nice-name (lambda (poke)
                       (list (cadr poke) (list-ref poke 5)))])
      (map nice-name (take (sort lst higher-hp) 5)))))

Write a procedure (without documentation), (highest-hp lst), that verifies the preconditions of highest-hp-kernel and then calls highest-hp-kernel. Your procedure should handle any possible input from the user and output an appropriate helpful and specific error message if the input violates a precondition.

Problem 6: Displaying Types

Topics: files, filtering, displaying data with histograms, tallying

In this problem, you will plot Pokemon types (primary and secondary).

Document and write a procedure, (types filename), that takes a string which is the path to a file with the format of the Pokemon statistics data set as input and produces a plot of the frequencies of the types of the Pokemon, treating Type 1 and Type 2 the same. Note that you should ignore "" when a Pokemon does not have a second type and therefore you should not have a large entry with the type name “” in your histogram.

Your plot should have appropriate labels for the x and y axes and an appropriate title. You should use the following to angle your x-axis labels so that they are readable since there are so many types.

(parameterize ([plot-x-tick-label-anchor  'top-left]
                 [plot-x-tick-label-angle   -40])
  (plot (YOUR PLOT CODE HERE)))

Copy the histogram that you produce with the data from Pokemon statistics data set into your exam file and include an appropriate citation for the source of the data (https://www.kaggle.com/abcsds/pokemon/data). We will also run your code to verify that it produces the same plot. Remember to remove your username from examples to preserve your anonymity.

Frequently Asked Questions

Are we allowed or required to use recursion?

Certain problems state that you must use recursion. In those cases it is required.

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.

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 may lose points, even if it is correct.

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.