Second Midterm Examination
CSCI 2041: Advanced Programming Principles Fall 2021
Fill in these blanks before you start to work on the examination.
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. (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. (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. 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 ≤ 231 − 2. Starting from the seed, later terms n1, n2, n3 … are produced by the following equation.
nk+1 = (75nk) mod (231 − 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?