Preliminary Examination 1

March 7, 2002

You have 90 minutes to complete this exam. There are 89 total points on the exam. Points for each problem are given below; points are distributed evenly among problem subparts unless otherwise stated. Make sure you have all 9 pages of the exam.

This is a closed-book exam: you may not use notes, book, calculators, computers, etc. Please do all work and write all answers on the exam papers. If you are running low on space, write on the back of the exam sheets and be sure to write (OVER) on the front side. If you finish in the last ten minutes of the exam, please remain seated quietly as a courtesy to your fellow students.

It is to your advantage to show your work—we will award partial credit for incorrect solutions that are headed in the right direction. If you feel rushed, try to write a brief statement that captures key ideas relevant to the solution of the problem.

NetID:

Problem |
Points |
Score |

1 | 15 | |

2 | 15 | |

3 | 20 | |

4 | 28 | |

5 | 11 | |

Total |
89 |

**a)** Briefly explain the difference between an SML (also called **algebraic**)
datatype and an *abstract* datatype.

**b)** Why is unit testing needed even if integration testing succeeds?
Explain briefly.

**c)** Explain briefly how hash tables implement the set membership operation
in O(1) time.

2. Zardoz (15 pts, a–e)

A **value** is an expression that does not need further evaluation; if
typed to the SML prompt, exactly the same thing is reported as a result. For
example, it may be a integer constant, a `fn`

expression, a tuple of
values, or a datatype constructor applied to a value. Complete each of the
following **let**-expressions by giving a *value *that can replace
"`???`

" and cause the whole thing to evaluate to the
integer 42.

**a)**

let fun zardoz(x: string*string): int = case Int.fromString((#2 x)^(#1 x)) of NONE => 41 | SOME n => n*2 in zardoz("1",???) end

**b)**

let fun zardoz (x:string, (y:(int*int) option, z: int)):int = case y of SOME (7,x) => x*z-1 | SOME (x,z) => x*z | NONE => size(x)*z+1 in zardoz(???) end

**c)**

let datatype sa = Done of int | Function of sa->int fun zardoz(f:sa):int = case f of Done(n) => n | Function(g) => g(f) in zardoz(Function(???)) end

DataMiners Inc is designing an application to track stock portfolios and
needs code to analyze a history of stock prices and find the maximum profit that
could have been obtained by buying and selling at just the right moments. The
stock price history is stored as a list of reals ordered in time; the maximum
profit is the largest value *y*`-`*x
*where *x*, *y*
are integers in the list and *y* occurs in
the list *after* *x*. For example, for
the list `[4,6,7,2]`

the maximum profit would be 7`-`4=3.
Note that it would not be 7`-`2=5 because 7 does not occur after 2 in
the list. The maximum profit can even be negative if the stock price always
declines in value throughout the history.

The programmers at DataMiners have written the following analysis code; they
have hired you to figure out whether it works and analyze its performance.

```
fun maxDiff_x(data: int list, x: int, currentMax: int) =
foldl (fn(y,max) => Int.max(y-x,max)) currentMax data
```

fun mpLoop (data: int list, currentMax:int) : int = case data of [] => currentMax | x::xs => mpLoop(xs, maxDiff_x (xs, x, currentMax)) fun maxProfit (data: int list) : int option = case data of x::y::xs => SOME (mpLoop (data, y-x)) | _ => NONE

**a)** Give a specification of the function `maxDiff_x`

.

**b)** Give a specification of the function `mpLoop`

.

**c)** Give a tight asymptotic bound on the running time of `maxDiff_x`

(no justification needed).

**
d)** Derive a recurrence relation for the worst-case running time of

`mpLoop`

as a function of the length of the list `data`

.

**e)** Use your recurrence relation to determine the worst-case time bound
for this code. Justify this bound by using the recurrence relation.

The following is a simplified version of the SML signature for strings, with only some operations specified fully:

signature STRING = sig (* A string is a finite sequence of characters. For example, the * string "abd" is the characters #"a", #"b", #"d" in sequence. *) type string (* size(s) is the number of characters in the string. *) val size : string -> int (* sub(s, i) is the character in the string at index i, * where indices start at zero in the usual manner. *) val sub : (string * int) -> char (* ^ is ordinary string concatenation *) val ^ : (string * string) -> string (* implode(lst) is the string containing the characters in lst * in the same order as in lst, e.g. implode[#"a",#"b"] is "ab" * and implode nil is the empty string "". *) val implode : char list -> string (* explode is the inverse of implode *) val explode : string -> char list ... end

**a) (2 pts) **Explain briefly what is wrong with the specification for
the function `sub`

and give a corrected specification.

While the default SML implementation of this signature is adequate for a
broad range of applications, there are cases where a different implementation is
better. For example, if the program is doing a lot of string concatenations (^),
the standard `String`

implementation may not be fast enough because
it does string concatenation in time O(*n*)
in the length of the string. An alternate implementation of strings looks like
the following:

structure Rope :> STRING = struct datatype string = Empty | Single of char | Concat of string * string * int (* Abstraction function: * Empty represents the empty string * Single(c) represents the single-character string containing c * Concat(s1,s2,n) represents the concatenation of * s1 with s2, i.e., s1^s2. * Representation invariant: ??? *) fun size(s) = case s of Empty => 0 | Single(c) => 1 | Concat(s1,s2,n) => n fun op^(s1, s2) = Concat(s1, s2, size(s1) + size(s2)) fun sub(s, i:int) = case s of Empty => raise Subscript | Single(c) => if i = 0 then c else raise Subscript | Concat(s1,s2,n) => let val n1 = size(s1) in if i < n1 then sub(s1,i) else sub(s2, ???) end fun implode(cl) = let fun implode_n(cl: char list, n: int): string = case cl of nil => Empty | c::nil => Single(c) | c::cl' => Concat(Single(c), implode_n(cl', n-1), n) in implode_n(cl, List.length(cl)) end fun explode(s) = ??? end

In the rest of this problem, the type name `string`

refers to the
type `Rope.string`

.

**b)** **(4 pts)** The representation invariant is conspicuously
missing from the `Rope`

implementation. Give a representation
invariant. Hint: consider what rep invariant is needed in order to make the size
function correct.

**c) (3 pts) **Given `string`

values `s1`

and `s2`

of length at most *n*, what is the asymptotic
worst-case performance of the concatenation expression `s1^s2`

as a
function of *n*? Justify in one sentence.

**d) (4 pts)** The sub function has three question marks in place of an
expression of type `int`

. What expression should replace the `???`

to make `sub`

work correctly?

**e)** **(3 pts)** In this implementation, the same string can be represented in many different
ways. Suppose we consider one string representation better than another based on
the worst-case running time of a call to `sub`

. Describe two
different representations of the same string where one representation is much
better than the other.

**f)** **(5 pts)** Given a `string`

of length *n*,
what is the asymptotic worst-case performance of `sub`

as a function
of *n*, supposing that the representation
does not include any `Empty`

nodes? Justify in 1-2 sentences.

**g)** **(7 pts)** Give code that implements `explode`

(your
implementation need not be asymptotically efficient).

**h)** **(EXTRA CREDIT: 2 pts -- save till you are done with everything
else!) ** Give a better implementation of `implode`

that improves the worst-case asymptotic efficiency of `sub`

on strings
that it creates.

5. Fun with folding (11 pts, a–c)

Recall the definition of `foldl`

:

fun foldl (f: ('a*'b) -> 'b) (base:'b) (x:'a list):'b = case x of nil => base | hd::tl => foldl f (f (hd,base)) tl

For each of the following tasks, show how `foldl`

can be used to
reimplement the function in 1–2 lines of *functional* code, without using
`case`

, `hd`

, `tl`

, or `nth`

. Your
version should always produce the same result as the reference code. In your code, include the full type signature for the function provided as the argument `f`

and remember to check your code to make sure that that function returns the type
it needs to.

**a)** **(5 pts)** Given a list of integers, find the sum of all
elements prior to the first 0. Reference code to be rewritten:

fun SumPriorZero(a: int list) = case a of 0::t => 0 | h::t => h + SumPriorZero(t) | nil => 0

**b) (6 pts)** Return a list containing every *n*^{th}
element in a list. Reference code:

fun everyNth(l:'a list, n:int):'a list = let fun iter(l:'a list, counter:int):'a list = case (l,counter) of ([],_) => [] |(x::xs,1) => x::(iter(xs,n)) |(x::xs,c) => iter(xs,c-1) in iter(l,n) end