midterm2.dvi
Second Midterm Examination
CSCI 2041: Advanced Programming Principles
Fall 2021
Fill in these blanks before you start to work on the examination.
Name:
UMN Email Address:
UMN ID Number:
Lab Section:
This examination must be done individually. It is “open notes,” so you are allowed to use
anything represented on paper to help you answer questions, including class notes, lab
assignments, program listings, and Xeroxed pages. However, you are not allowed to use
your textbook, or any other published books. You are also not allowed to use electronic
devices. You will have 50 minutes to complete the examination.
The examination is worth 35 points. There are three questions, some with multiple
parts. Make sure you have seen all the questions before you start to write. Write your
answers directly on the pages of this examination. Please use a pencil, so you can erase if
you make mistakes. Your grade for this examination will be determined only by what you
write and draw here. You may use “helper” functions if you need them.
1
1. (10 points.) A list is rotated when its first element is removed and placed after its
last element. For example, [1 ; 2 ; 3] rotated is [2 ; 3 ; 1]. Similarly, [2 ; 3 ; 1]
rotated is [3 ; 1 ; 2], and [3 ; 1 ; 2] rotated is [1 ; 2 ; 3].
Write an OCaml function called rotate that has two parameters: a continuation and
a nonempty list. The function rotate must call its continuation on all possible rotations
of its list. For example, the call rotate etc [1 ; 2 ; 3] must call etc on exactly the
following lists, in this order.
[1 ; 2 ; 3]
[2 ; 3 ; 1]
[3 ; 1 ; 2]
For full credit, your function rotate must work correctly on any nonempty list, not just
the one shown in the example. It must also generate only one rotated list at a time. Hints:
The function List.length l returns the number of elements in a list l. The expression
l @ r returns a new list, made by appending the lists l and r.
2
2. (10 points.) Suppose that a binary tree is defined by the following OCaml type. Each
node in the tree has an identifying tag and two subtrees.
type ‘tag tree = Empty | Node of ‘tag * ‘tag tree * ‘tag tree ;;
A node is an external node if both its subtrees are empty. Write an OCaml function called
externals that takes a binary tree of type ‘tag tree as its only argument. It must return
the number of external nodes in the tree.
3
3. The Park-Miller algorithm generates a series of pseudo-random integers. It works like
this. Let n0 be an integer called the seed. The seed is the first term in the series, where
1 ≤ n0 ≤ 2
31
− 2. Starting from the seed, later terms n1, n2, n3 … are produced by the
following equation.
nk+1 = (7
5
nk) mod (2
31
− 1)
The following let’s bind names to the constants used in the Park-Miller algorithm.
let sevenToTheFifth = 16807 ;;
let twoToTheThirtyFirstMinusOne = 2147483647 ;;
let twoToTheThirtyFirstMinusTwo = 2147483646 ;;
3a. (10 points.) Define a function makeRandom n0 that takes the seed n0 as its argument. If
the seed is out of range, then makeRandom raises an exception called ParkMillerException.
Otherwise, makeRandom returns a new function with no parameters. Each time the new
function is called, it returns the next term in the Park-Miller series whose seed is n0. The
first time the new function is called, it returns n1. The second time, it returns n2. The
third time, it returns n3, etc.
3b. (5 points.) What is the type of the function makeRandom?
4