PROBLEMS
Fig. 3.3
Fig. 7.29
Table 3.44(f)
These review problems are meant as a study guide, to direct your
questions and preparation, not as a comprehensive overview of the
course. They may or may not be more painful than real test questions.
They DO NOT reflect the style or format of the final exam in any way.
Studying this document does not mean that you have covered and studied
all the material required in full, or that you have seen the full
range of topics possible on the exam.
Seeing a problem here also does not necessarily mean that it could
appear on the final, it just means that it is a good practice
problem for the final. Do not panic if you see some new functions.
YOU SHOULD NOT try to complete this entire review document - just
focus on concepts that you need extra practice with. If you are able
to answer the problems, you will be better-prepared for a final exam
question.
YOU SHOULD review the following:
o The HtDP text
o lecture slides
o homeworks from this semester
o homeworks from previous semesters
o Labs from this semester
o practice tests from both this and previous semesters
in order to gain a complete overview of the course content.
Note that some topics covered in previous semesters may not have been
covered this semester, and vice versa.
In addition to these problems, it would greatly benefit you to know
the Data Analyses and Templates for complex data, covered in the
Design Recipe Guide. These are very helpful for:
o knowing what you're doing when given some complex data
o saving yourself time on a tougher problem
o knowing what to do when you don't know how to start a problem
o partial credit if your solution isn't perfect
INSTRUCTIONS:
-------------
1. Find a scary set of questions
2. Read all about that topic in the materials above
3. THEN try to answer the questions
4. Discuss your solution(s) with others
SOLUTIONS
---------
An official solutions page will not be posted, therefore your
best bet is to discuss the problems with other students, TAs, and post
& discuss your solutions on the newsgroups. Be patient with TAs who
may have extremely busy finals week schedules (due to grading etc).
This review sheet is an excellent collaboration exercise - use it to
your advantage.
Good luck!
PROBLEMS
NOTES: USE DR. SCHEME'S "PRETTY BIG MODE" FOR ALL QUESTIONS
* Stars indicate challenging/optional problems
CS VOCAB
1. (a) What is atomic data?
(b) What is complex data?
(c) What is a function?
(d) How is a procedure different from a function?
(HINT: What is a side-effect?)
(e) What is a program? How is a program different from
functions or procedures?
(f) What is an algorithm?
(h) What is abstraction? (very important!)
(i) What is scope?
(j) What is syntax?
(k) What are semantics?
RECURSION/ITERATION VOCAB
2. (a) What are three requirements of a recursive algorithm?
1. ___________________________
2. ___________________________
3. ___________________________
(b) What is iteration? How is it different from recursion?
(c) What do the following types of recursion mean:
o tail
o generative
o structural
o augmenting
o mutual
(d) Which of these types contradict each other? How and why?
(e) Which types complement each other (i.e. which types may be used
together, or may appear in one function? For instance, is it
possible to have a tail-recursive and mutually recursive
function? What about a generative and structural recursive function?)
SCHEME VOCAB
3. (a) What does the word cond stand for? Why?
(b) What does the word cons stand for? Why?
(c) What is the significance of the lambda symbol? *
HINT: You know it as the all-too-familiar Dr. Scheme logo.
SCHEME SYNTAX
4. (a) What character delimits comments in Scheme?
(b) Is it required to have two of these before a comment?
(c) What character delimits a symbol in Scheme?
(d) What character delimits a string in Scheme?
(e) What are three ways of writing a list in Scheme?
(f) What is a shorthand for writing vectors in Scheme? *
(g) What is a shorthand for writing booleans in Scheme? *
(h) What is the difference between how you write let and
local definitions?
5. What is the difference between:
(a) (define something ...)
and: (define (something ...) ...)
(b) (define 'pi 3.14),
(define pi 3.14)
and: (define "pi" 3.14)
(c) Without typing anything into Dr. Scheme, take a wild guess at
which of the three definitions in (b) will execute correctly.
(NOTE: Read Chapter 5 in the textbook if you got it wrong.)
TESTS
6. Given the following problem on a homework:
Write a function that calculates whether a given year between 1
and 2000 is a leap year. A leap year is any year divisible by
4. Years divisible by 100 are not leap years unless they
are divisible by 400. Return false if you are given a number
outside the valid range.
WAIT - do not write the code for this! That's not what this
question is about.
Suppose you were a TA, writing an autograder to test student's
submitted solutions to this problem. Think about the various tests
you would need to check the students' code:
(a) How many categories of input are there? (That is, give the
optimum number of test cases you would need to test all the
possible input this function should/shouldn't handle.) *
(b) Now list the examples/tests you would use to thoroughly
test the solutions, and which category (from above) they
belong to.
HINT: Think about valid/invalid ranges, boundary conditions,
all types of leap and non-leap years. Even so, if you are
coming up with more than 10 test cases, you are duplicating
a lot of categories - try to be economic, but cover everything.
7. Given the same problem as above:
(a) Write the solution using a cond statement.
(b) Write the solution using ONLY boolean logic and/or/not.
NO cond is allowed!
NOTE: You may use the built-in remainder function to test
divisibility. You should also use your test cases from above to
check your code thoroughly.
STRUCTURES
8. Given the following completely bizarre structure definitions:
(define-struct can-can (can can-can cancun))
(define a-can-can (make-can-can 'can 'can 'can))
(a) Try your very best to list the following items created by that
bizzarre define-struct command:
(i) the constructor
(ii) the selectors
(iii) the predicate
(b) Show how to extract all three 'can symbols from the defined
a-can-can constant. Use three separate one-line commands,
ON PAPER, before testing your code in Dr. Scheme.
(c) Show how to use the predicate to return a true value,
then show how it could return a false value. Use any
example you can create.
NESTED STRUCTURES
9. Given the following structures:
(define-struct point (x y z))
(define-struct cube (p1 p2 p3 p4 p5 p6 p7 p8))
(define my-cube (make-cube ... ... ...))
where each "p" inside the cube is actually a
point structure,
Write the following ON PAPER, before testing them in Dr. Scheme:
(a) show how to extract p3 from my-cube, in one line of Scheme code
(b) show how to extract the x-coordinate of p7 from my-cube, also
with only one line of Scheme code - assuming that p7 is a
point structure
HINT: This is easy to get backwards, so test your solutions!
CONTRACTS
10. Carefully write a Contract for each of the following: (Know that
some are much trickier than they look - if you are not sure, then
ask someone to check your solutions!)
(a) sqr: returns the square of a number
(b) symbol=?: compares two symbols for equality
(c) string?: checks if an unknown piece of data is a string
(d) posn-x: extracts the x-coordinate of a posn
(e) BST-search: checks if a string exists inside a BST of
strings (i.e. whether it is found or not).
(f) length: counts the number of items in a list
(g) append: attaches two lists of Scheme data end-to-end
(h) map: applies a function to each item in a list
(i) filter: applies a predicate to each item in a list, then
removes all items for which the predicate is false
returning a list of ONLY the items for which the
predicate is true. (CORRECTED)
(j) vector-set!: changes a specified index in the vector
(k) display: displays any item to the screen
(l) collect-garbage: runs the Scheme garbage collector
try it: (collect-garbage)
(m) flipflop: takes a list which contains lists of numbers,
returns a vector, containing vectors of numbers
(n) squish: takes two vectors of any two types
of data, and a function (which consumes an item
from each vector and produces a number,
squish only returns a number
(o) d/dx: takes a function f(x) (which takes in a number
and returns a number) and returns its derivative
f'(x), which is also a function that takes a
number and returns a number (don't worry about the
Calculus, just read the problem carefully)
(p) ;; weirdness: _____ _____ _____ _____ --> _____ *
;; This function may take in other functions! Read carefully:
(define (weirdness A B C D)
(local [
;; A constant ...
(define current-limit (* 3 D))
]
(cond [(empty? C) empty]
[(B (first C) current-limit)
(cons (A (first C))
(weirdness A B (rest C) current-limit) )]
[else (weirdness A B (rest C) D)] )))
HINTS: o You may need to run these or research them to figure out
the precise Contract - many are built into Dr. Scheme.
o Remember to be as general as possible, but at the same time
specific where only specific data types will work.
o Remember to use the "new" notations, including functions
as parameters, listof, vectorof, BSTof, etc..
LISTS
11. Given the following list:
(define mylist (cons 1 (cons 2 (cons 3 empty))))
Show how to extract each of the following from mylist,
using only combinations of first & rest,
in ONE line of code per part:
(a) extract the 1
(b) extract everything after the 1
(c) extract the 2
(d) extract everything after the 2
(e) extract the 3
(f) extract the empty at the end of the list
Again - you must extract the values *from* the given list, one
line of code per part. For example, to answer part (f) I could
simply write:
empty
but that empty *does not come from the list*. It is wrong.
NOTE: Do you see why recursion is perfect for automating this process?
If not, try doing this for (list 1 2 3 4 5); it gets tedious... ;)
12. Trace the following code ON PAPER, showing each step: *
(yes, the final result spells something...)
(append (reverse (cons (first '(S C H E M E))
(rest (rest '(A B C))) ))
(map add1
(first (list (reverse (list 0 1 2 0))
(reverse (list 0 1 2 1))) ))
(list (first (rest '("Russian" "is" 'so 'confusing)) ))
(filter string? '(This question is "craaazy!" man!)) )
MAJOR HINT: Think like math - the innermost parentheses get
evaluated first, then the result will replace the
original expression.
13. Given a list of numbers, such as:
(list 1 2 3 4 5)
write a function that will cube each number in the list, to
produce:
(list 1 8 27 64 125)
You must use the following variations: (each of them should simply
take in the user's list, and nothing else)
(a) Write it using augmenting recursion and one or more
local helper functions. Name the main function
cube-aug.
(b) Write it using tail recursion and one or more local
helper functions. NONE of the functions you write can
be augmenting recursive at any point! Name the main
function cube-tail.
HINT: Telltale signs of augmenting recursion - if you
are applying some operation *to* a recursive call, then
that operation will have to wait outside the recursive
call, until that recursion is finished. This will
build a stack of waiting operations: augmenting.
Instead, move the operation *into* the recursive
call, applying it to the extra parameter/accumulator.
Then the operation is done *before* the recursive
call, so nothing is left building up ouside of it.
On most finals if you use ANY augmentation
in your solution to a tail recursive problem,
your solution will not receive any credit.
(c) Write it using a do loop, and one or more local helper
functions. You may not use recursion at any point!
name the main function cube-loop.
(d) Write it WITHOUT a local helper, using only the
built-in functions map and lambda. Name
this variation cube-map.
HINT: There is no built-in cube function for numbers;
perhaps one of your helper functions could abstract this
operation?
14. Write the Scheme code for filter and map.
Some examples of how the built-in map & filter behave:
(map sqr '(1 2 3 4 5)) --> '(1 4 9 16 25)
(map (lambda (x) (+ x 5)) '(10 10 10)) --> '(15 15 15)
(filter (lambda (x) (symbol=? x 'a))
'(a b c a b c a b c a b c)) --> '(a a a a)
HINT: Take a look at the Contracts and descriptions for these two
functions, in the CONTRACTS problem above. Also, the HtDP
text has a description of both (although they give an
incorect Contract in the chart!).
15. Write a function that will find the smallest odd number in
a list of any data.
(smallest-odd '(a b c
-4 -2 0 1 2 3
"HEY" THIS IS "tricky")) --> 1
If the list is empty, or contains no odd numbers, you may return
zero.
Write this using any technique you like (try tail recursion or
a loop). Be sure to also write out a Contract.
HINT: You will need to make sure you are looking at a number,
before you try to check if it is odd or not. There is a
number? predicate in Scheme that will help you.
BOXES & POINTERS
16. Given the boxes & pointers diagram shown in Figure 3.3:
Fig. 3.3
Fig. 7.29
Table 3.44(f)