60-100 Final Exam Fall 2005 December 21St

60-100 SAMPLE SOUTIONSFinalExam December 13th 2012

Toldo Room 200 7pm to 10:00 pm

Answer ALL Questions SHOW ALL WORK to obtain full marks. Put a box around your answer. Answer in ink, if you want to review your paper after it has been marked.

1) Write a Miranda program p1 which takes a list of lists of numbers as input and which returns the product of the sum_of_the_squares of the numbers in the lists. You must use foldr, map and composition (.) in your answer. The following is an example use of p1:

p1 [[3,2],[4,5],[3,3,2]] => 11,726

note that 11,726 = (9+4)*(16+25)*(9+9+4)

p1 = foldr (*) 1 . map (foldr (+) 0). map (map sq)
sq n = n* n / 10 marks
p1 n = (foldr (*) 1 . map (foldr (+) 0). map (map sq)) n
sq n = n* n / 10 marks
p1 = foldr (*) 1 . map (foldr (+) 0). mapsq
sq n = n* n / 9 marks
p1 n = (foldr (*) 1 . map (foldr (+) 0). map sq) n
sq n = n* n / 9 marks
p1 = foldr (*) 1 .foldr (+) 0. map (map sq)
sq n = n* n / 9 marks
p1 = foldr (*) 1 .foldr (+) 0. map sq
sq n = n* n / 8 marks
p1 = foldr (*) 1. Map op
where op [] = 0
op (x:xs) = sq x + op xs / 10
^2 in place of sq is OK
anything else – give to Dr Frost

2) What is the result of evaluating the following list comprehension(show all of your calculation to obtain part marks):

[(x,y)|x<-[3..5];y <- [z^3 |z <- [2..3]]; x^2 < (y + 15)]

[(3,8),(3,27),(4,8),(4,27),(5,27)] / 10 marks
(3,8),(3,27),(4,8),(4,27),(5,27) / 9 marks
anything else – give to Dr Frost

3) What is the type of the program p2 defined as follows:

p2 x [] z = x, if [x] = z

= p2 5 [‘a’] (z --[z!0]), otherwise

p2:: num -> [char] ->[num] -> num / 10 marks
p2:: num -> [char] ->[*] -> * / 9 marks
p2:: num -> [*] ->[num] -> num / 9
marks
p2:: * -> [char] ->[num] -> * / 9 marks
p2:: * -> [char] ->[*] -> * / 9 marks
Anything else – give to Dr Frost

4) Write a Miranda program to implement the following relational algebraic operator:

project_second_and_third_of_3

project_second_and_third_of_three r
= mkset [(b,c) | (a,b,c) <- r] / 10 marks
project_second_and_third_of_three r
= [(b,c) | (a,b,c) <- r] / 9
marks
project_second_and_third_of_three
= mkset [(b,c) | (a,b,c) <- r] / 9
marks
project_second_and_third_of_three r
= mkset [(a,b) | (a,b,c) <- r] / 9
marks
project_second_and_third_of_three
= [(b,c) | (a,b,c) <- r] / 8
marks
Anything else – give to Dr Frost

5) Use RECURSION to write a Miranda program p3 which takes anon-empty list of numbers and which returns a pair containing the smallest number in the list and the largest number in the list. For example:

p3 [3,6,12,4,2] => (2,12)

P3 [x] = (x,x)
P3 (x:xs) = (x,b), if x < a
= (a,x), if x > b
= (a,b), otherwise / 10 marks
p3 [x] = (x,x)
p3 (x:xs) = (x ,snd(p3 xs)), if x < fst (p3 xs)
= (fst (p3 xs), x), if x > snd (p3 xs)
= (fst (p3 xs),snd(p3 xs)), otherwise / 10 marks
p3’s = (small s, big s)
small [x] = x
small (x:xs) = x, if x < small xs
= small xs, otherwise
big [x] = x
big (x:xs) = x, if x > big xs
= big xs, otherwise / 10 marks
Missing base case – dect 2

6) Consider the following grammar G =

(terminals = {0, 1, n, m}, non-terminals = {expr, b, bs, char, chars},

start-symbol = expr, rules = {expr::= char | chars bsexpr

chars::= char | char chars

bs ::= b | bsbs

char ::= n | m

b ::= 0 | 1

Draw a syntax tree for the following expression: nm00m

7) Write down an attribute grammar for the following language:

Example expression Value

2534 3.5

4826 5

37532 4

That is, the value of the expression is the sum of the digits divided by the number of digits.

G =
(terms = { 0, 1, .., 9},
start_symbol = expr,
non_terms = {expr, digs, dig},
rules =
{expr ::= digs
VAL of expr = SUM of digs/NUM of digs
digs ::= dig
SUM of digs = VAL of dig
NUM of digs = 1
| dig digs’
SUM of digs = VAL of dig + SUM of digs’
NUM of digs = 1 + NUM of digs’
dig ::= 0
VAL of dig = 0 (or VAL 0)
| 1
VAL of dig = 1 (or VAL 1)
etc. / 10:
6 for grammar,
4 for attribute rules
As above but with different (but consistent identifiers, e.g. nums instead of digs, etc. / 10:
6 for grammar,
4 for attribute rules
Same as above but digs’ dig in place of dig digs’ / 10
Same as above but missing ’ / 9
Any other answer – give to Dr Frost

8) Use structural induction on the length of the input list to show that the length of the output is greater than the length of the input. That is, show that

#(p8 t)(#t), for p8 defined as follows:

p8 [ ] = [3]

p8 (x:xs) = x : (p8 xs)

Prove #(p8 t) > #t for all lists t
Base case t = []
#(p8 []) > #[]
#([3]) > #[] from the definition of p8
1 > 0 from the meaning of #
True – base case proven
Inductive Step
Assume #(p8 k) > #k for some arbitrary list k
Show #(p8 (a:k)) > #(a:k)
How
#(p8 (a:k)) > #(a:k)
#(p8 (a:k)) > 1 + #k from (#)
#(a:(p8 k)) > 1 + #k from definition of p8
1 + #(p8 k) > 1 + #k from knowledge of #, and (:)
^ ^
|______>_____| by the assumption
Therefore lhs > rhs (because a + b > a + c, if b > c)
Proven / 10
3 for base case
2 for structure of inductive step
5 for inductive step calculation
Same as above but missing statement because a + b > a + c, if b > c / 10
anything else – give to Dr Frost

9) Calculate and illustrate on a graph, the complexity of the following program with respect to the first input number m. (You MUST trace the program for a few example inputs and analyze the trace in order to obtain full marks).

p9 [y] = [y]

p9 (x:xs) = (3:xs)++ p9 xs

Example Trace
p9 [1,2,3,4,5,6]
=> 3:[2,3,4,5,6] ++ p9 [2,3,4,5,6]
|
|
3:[3,4,5,6] ++ p9 [3,4,5,6]
|
|
3:[4,5,6] ++ p9 [4,5,6]
etc.
Therefore
a)If the length of the input is n, then there are n - 1 levels in the computation as one element is removed from the list on each recursive call until the list is of length 1.
b)The work on the first level is proportional to n + 1 because the ++ operator depends on the length of the leftmost list.
The work on the next level is proportional to n
The work on the next level is proportional to n - 1
etc. until the last call when the work is 2 units
c)Therefore the average work on levels is proportional to n/2.
d)Therefore the total work is proportional to n^2
e)Therefore, the complexity is O(n^2)
|
|
|
| *
^ | O(n^2)
time |
| *
|
| *
|*______
Length of input n > / 10:
1 for trace
3 for correct analysis of trace
2 for correct O(n^2)
4 for graph with correct axes and shape of curve for the complexity calculated (even if complexity is wrong)
Any other answer – give to Dr Frost

10) a) (5 marks) Use a truth table to determine if the following is satisfiable, universally valid or unsatisfiable. Note that ~ is the negation operator, is “and”, and \/ is “or”:

(~a & b) -> (~b -> (a \/ b))

b) (5 marks)Use a truth table to determine if the formula (~a -> ~b) is a logical consequence of the set of formulas{(b -> a), (~b \/ ~a)}Explain why the formula is or is not a logical consequence by marking the table.

a b | (b -> a) (~b \/ ~a) | | ~a -> ~b
T T | T F | | T
T F | T T | √ | T √
F T | F T | | F
F F | T T | √ | T √
(~a -> ~b) is a logical consequence of the set of formulas {(b -> a), (~b \/ ~a)} because it is True in all (the two) cases where both (b -> a) and (~b \/ ~a) are both True. / 10
3 for table
1 for correct answer
1 for explanation
anything else – give to Dr. Frost