{- * Uppsala University - 2017 Fall * Program Design and Data Structures, 1DL201 * Exam 2014-12-16, attempted solutions * Copyright 2017 Henrik Alfken(Schulze) -} {- 1. Which of the following is a correct (well-typed) Haskell expression? (A) 1 ++ 2 (B) True + 1 (C) not 0 (D) length "foo" (E) "foo" && "bar" Answer: (D). length "foo" == 3 -} {- 2. What is the type of head [0<1, 0==1, 0>1] ? (A) The expression is not type-correct. (B) () (C) [Integer] (D) Integer (E) Bool Answer: (E). -} {- 3. What is the value of head [0<1, 0==1, 0>1] ? (A) [0] (B) () (C) The expression throws an exception. (D) 0 (E) True Answer: (E). -} {- 4. Which of the following is a correct Haskell expression that is equivalent to 3 > 2 || 3 < 1 `div` 0 ? (A) if 3 > 2 then True else 3 < 1 `div` 0 (B) if 3 < 1 `div` 0 then 3 > 2 else False (C) if 3 > 2 then 3 < 1 `div` 0 (D) if 3 > 2 || 3 < 1 `div` 0 then True (E) if 3 > 2 then 3 < 1 `div` 0 else False Answer: (A). The others do not even compile! -} {- 5. Which of the following expressions does not have the same value as the other four? (A) ['a','b','c'] (B) "a"++"b"++"c" (C) ["abc"] (D) ['a'..'c'] (E) 'a':'b':'c':[] Answer: (C) is the only one of type . -} {- 6. What is the value of the following expression? let x = 1 f y = let x = y+1 in x+y y = f x in x+y (A) 1 (B) 2 (C) 3 (D) 4 (E) 5 -- Rewrite the function to make it less confusing to read: let x = 1; f j = let k=j+1 in k+j; y = f x in x+y Answer: (D) 4; the result = x+y = 1 + f 1 = 1 + k+j, where j=1 and k=j+1. -} {- 7. Consider the following function: -} f07 x = let y = 10 `div` x in if x == 0 then x else y {- What is the value of f07 0 ? (A) The expression throws an exception. (B) 1 (C) 10 (D) Infinity (E) 0 Answer: (E). Because Haskell uses lazy evaluation, <10 `div` 0> is never evaluated. -} {- 8. Consider the following function: -} f08 (True, 1) = 1 f08 (True, _) = 2 f08 (_, 1) = 3 f08 (False, _) = 4 {- f08 (False, 1) = 5 The last line MUST be commented away, or else when compiling you get: PKD-2014-12-16.hs:80:1: warning: [-Woverlapping-patterns] Pattern match is redundant In an equation for ‘f08’: f08 (False, 1) = ... | 80 | f08 (False, 1) = 5 | ^^^^^^^^^^^^^^^^^^ -} {- What is the value of f08 (False, 0) ? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5 Answer: (D) - or rather: none of these since the code does not even compile! -} {- 9. Which of the following expressions is equivalent to [1,3..7] ? (A) [1,3,5,7] (B) [1,2,3,4,5,6,7] (C) [1,4,7] (D) [] (E) [1,3,4,5,6,7] Answer: (A). -} {- 10. Recall the mergesort algorithm. To ensure that the output list is a sorted permutation of the input list, it is important that the splitting function ... (A) returns two lists that together contain the same elements as the input list. (B) returns two sorted lists. (C) splits the input list into elements below the pivot, and elements above the pivot. (D) returns two lists of equal length. (E) runs in Θ(n). Answer: (A). -} -- I believe we have NOT talked about the issues raised in questions 11-12. {- 11. Which of the following best describes the purpose of data descriptions in the 8 step design process? (A) To informally describe the input and output of functions. (B) To give examples of the data used in a program. (C) To describe how the data in the program relates to the real world concepts it models and give constraints on the validity of the data. (D) To give examples of valid and invalid data for the program. (E) To provide a description of the relationship between data used in programs and the functions that operate on that data. Answer: (C) ? - If you say so. -} {- 12. What of the following is NOT an accurate description of the goal of stepwise refinement? (A) To help break a large problem into smaller problems. (B) To solve a problem by introducing other functions to help solve the problem. (C) To break a function into details which are refined in successive steps until the whole program is fully defined. (D) To refine the steps of an algorithm into lines of code. (E) To refine a highly abstract representation of some required program gradually through a sequence of intermediate representations to yield a final program in some chosen programming language. Answer: (D). "Top-down design - in which design begins by specifying complex pieces and then dividing them into successively smaller pieces" "A top-down approach (also known as stepwise design) is essentially the breaking down of a system to gain insight into the sub-systems that make it up." https://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Data_Representation_and_Practical_Exercise/Problem_Solving/Top-down_design_and_Step-wise_refinement -} {- 13. Which of the following post-conditions is best for the given code? -} rempos :: [Integer] -> [Integer] rempos [] = [] rempos (a:as) | a >= 0 = a : rempos as rempos (_:as) | otherwise = rempos as {- (A) The length of the result is greater than or equal to zero. (B) The input list traversed recursively to remove all negative numbers. (C) A list of integers with negative elements removed. (D) The input list with negative elements removed. (E) The input list with just positive elements remaining. Answer: (D). -} {- 14. Which of the following is a variant for the function rempos from the previous question? (A) the length of the input list (B) [] (C) as (D) a:as (E) 1 Answer: (A). -} {- 15. Let f(n) = 4n^3 + 99n^2 + 3. Which of the following is NOT correct? (A) f(n) = O(n^2) (B) f(n) = Θ(n^3) (C) f(n) = O(n^4) (D) f(n) = Ω(n^2) (E) f(n) = Ω(n^3) Answer: (A). n^3 is NOT bounded from above by n^2. n^3 growths faster than n^2. -} {- 16. What is the most precise closed form for the following recurrence? T(1) = 1 T(n) = T(n − 1) + n^2 if n > 1 (A) T(n) = O(n) (B) T(n) = O(n^4) (C) T(n) = Ω(n^2) (D) T(n) = Θ(n^2) (E) T(n) = Θ(n^3) Answer: (E). See below! Substitution method: T(0) = 1 T(1) = 1 + 1^2 T(2) = (1 + 1^2) + 2^2 T(3) = ((1 + 1^2) + 2^2) + 3^2 T(4) = (((1 + 1^2) + 2^2) + 3^2) + 4^2 ... T(k) = 1 + 1^2 + 2^2 + 3^2 + 4^2 + ... + k^2 ... T(n) = 1 + 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 ... https://brilliant.org/wiki/sum-of-n-n2-or-n3/ T(n) = (1/3)n^3 + (1/2)n^2 + (1/6)n + 1 □ Expansion method: T(n) = T(n−1) + n^2 = (T(n−2) + (n-1)^2) + n^2 = ((T(n−3) + (n-2)^2) + (n-1)^2) + n^2 = (((T(n−4) + (n-3)^2) + (n-2)^2) + (n-1)^2) + n^2 = T(n-4) + (n-3)^2 + (n-2)^2 + (n-1)^2 + n^2 ... = T(n-k) + (n-k+1)^2 + ... + (n-3)^2 + (n-2)^2 + (n-1)^2 + n^2 ... Let k=n: = T(n-n) + (n-n+1)^2 + ... + (n-3)^2 + (n-2)^2 + (n-1)^2 + n^2 = T(0) + 1^2 + ... + (n-3)^2 + (n-2)^2 + (n-1)^2 + n^2 = T(0) + 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 = 1 + 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 = (1/3)n^3 + (1/2)n^2 + (1/6)n + 1 □ Same answer with both methods! Isn't that nice? (:-) -} {- 17. Use the Master Theorem to find a closed form for the following recurrence: T(n) = 2T(n/2) + n·log n The closed form is: (A) Θ(n) (B) Θ(n·(log n)^2) (C) Θ(n·log n) (D) Θ(n^2) (E) The Master Theorem does not apply. Answer: (B). See page 1! a = b = 2, so logb a = 1. Hence case 2 applies with c = k = 1. -} {- 18. Which answer is the recurrence representing the run-time cost of the following function? -} f18 :: Integer -> Integer f18 n | n <= 1 = 1 f18 n = f18 (n - n `div` 2) + f18 (n - n `div` 2) {- (A) T(n) = Θ(1) if n ≤ 1 T(n) = 2T(n) otherwise (B) T(n) = Θ(1) if n ≤ 1 T(n) = 2T(n − 1) + Θ(1) if n > 1 (C) T(n) = Θ(1) if n ≤ 1 T(n) = 2T(n/2) + Θ(1) otherwise (D) T(n) = Θ(1) if n ≤ 1 T(n) = T(n − 1/2n) + Θ(1) otherwise (E) T(n) = Θ(1) if n ≤ 0 T(n) = 2T(n/2) otherwise Answer: (C). The argument is (approximately) halved on every recursive call. Hence, T(n/2) should be on the right side. But in E, the cost for addition is missing. -} {- 19. What is the type of the following function? -} dup [] = [] dup (x:xs) = x:x:dup xs {- (A) [a] -> [b] (B) [a] -> [a] (C) (a,b) -> (a,a,b) (D) [a] -> [[a]] (E) [a] Answer: (B). In GHCi, run :t dup -} {- 20. Suppose you want to write a function increment_even :: [Integer] -> [Integer] that returns its input list with all odd numbers removed, and all even numbers incremented by 1 . For instance, increment_even [1,2,5,7,8] == [3,9] . Which of the following function definitions can you not use? -} -- (A) increment_evenA xs = [ x+1 | x <- xs, even x ] -- (B) increment_evenB [] = [] increment_evenB (x:xs) | even x = (x+1) : increment_evenB xs increment_evenB (_:xs) = increment_evenB xs -- (C) increment_evenC = map (+1) . filter even -- (D) {- increment_evenD xs = map ((+1) . filter even) xs -} -- (E) increment_evenE xs = map (+1) (filter even xs) {- Answer: (D). It makes no sense and does not compile. -}