{- * Uppsala University - 2017 Fall * Program Design and Data Structures, 1DL201 * Exam 2017-03-16, attempted solutions * Copyright 2018 Henrik Alfken(Schulze) * Inspired by: competition with Madde. -} {- Question 1: Define a datatype (and any helper types you might need) to represent a ticket. A ticket may be: • a train ticket from a city to a city—either first or second class; or • a bus ticket from a city to a city; or • a flight ticket from a city to a city—either business class, super economy, or economy. Cities are represented as strings. Which of the following definitions would you use? A type City = String type Economy = SuperEcon | Econ data TClass = First | Second data FClass = Business | Economy data Ticket = Train City City TClass | Bus City City | Flight City City FClass B type City = String data Ticket = Train City City First | Second | Bus City City | Flight City City Business | SuperEcon | Econ C type City = String data TClass = int data FClass = String data Ticket = Train City City TClass | Bus City City | Flight City City FClass D -} type City = String data TClass = First | Second data FClass = Business | SuperEcon | Econ data Ticket = Train City City TClass | Bus City City | Flight City City FClass {- E type City = String type TClass = First | Second type FClass = Business | SuperEcon | Econ data Ticket = Train City City TClass | Bus City City | Flight City City FClass Answer: D. In A, does not compile. :13:26: error: parse error on input ‘|’ In B, does not compile. :14:33: error: Not in scope: type constructor or class ‘First’ In C, does not compile. :19:17: error: Not a data constructor: ‘int’ In E, does not compile. :21:23: error: parse error on input ‘|’ See further the lecture slides '15-16-Inductive-Data-Types.pdf', notably pp 8-30. -} {- Question 2: Consider the type of general trees, defined as -} data Tree a = Node a [Tree a] deriving (Eq,Show) toInt :: Integral a => a -> Int toInt x = fromIntegral x t = Node (toInt 3) [Node 5 [], Node 2 [Node 13 []], Node 7 []] {- What does the following function (f02) compute? -} {- EXAMPLES: f02 (Node 11 [t]) == [5,13,2,7,3,11] -} f02 :: Tree Int -> [Int] f02 (Node a ts) = f02s ts ++ [a] -- where {- EXAMPLES: f02s [Node 11 [t]] == [5,13,2,7,3,11] -} f02s [] = [] f02s (t:ts) = f02 t ++ f02s ts {- Hint: what does the following function (pre) compute? -} {- EXAMPLES: pre (Node 11 [t]) == [11,3,5,2,13,7] -} pre :: Tree Int -> [Int] pre (Node a ts) = a:preChildren ts -- where {- EXAMPLES: preChildren [Node 11 [t]] == [11,3,5,2,13,7] -} preChildren [] = [] preChildren (t:ts) = pre t ++ preChildren ts {- A The sum of all values in a tree. B A post-order list of all values in a tree. C The number of nodes in a tree. D A pre-order list of all values in a tree. E The height of a tree. Answer: B. See further the lecture slides '15-16-Inductive-Data-Types.pdf', pp 59-60. -} {- Question 3: Which of the following trees is a binary search tree? A 2 / \ 4 5 ... B _ 9 _ / \ 4 _ 11 / \ \ 2 7 14 / \ / 5 8 15 C _ 8 _ / \ 4 11 / \ \ 2 7 15 / \ / 5 9 14 D 2 / \ 4 11 ... E None of these. Answer: E. - A and D are obviously not BSTs. In B, 15 is on the wrong side of 14. In C, 9 is on the wrong side of 8. If in B, 14 and 15 would switch places; and if in C, 8 and 9 would switch places - then they would both become BSTs. (And in fact, the same BST.) See further the lecture slides '17-Binary-Search-Trees.pdf', pp 10-15. Note the invariant given on page 13: "In any node (Node l x r), x is larger than all the labels of nodes in l and smaller than all the labels of nodes in r." -} {- Question 4: The (worst-case) complexity of searching in a red-black tree with n nodes is A O(n) B O(log n) C O(2^n) D O(n^2) E O(1) Answer: B. See the lecture slides '18-Red-Black-Trees.pdf', p 7. -} {- Question 5: Suppose the following numbers are inserted, in the given order, into an initially empty red-black tree. (Grey=red.) 71 28 81 64 21 76 99 63 What is the resulting red-black tree? https://i.imgur.com/WkVfpjm.png A B C D E None of these. Answer: C. See the lecture slides '18-Red-Black-Trees.pdf', pp 7-17. Start with the algorithm on page 7: 1. Perform a standard binary-search-tree insertion. 2. Color the new node red. 3. If there is a red node with a red parent --> rebalance the tree. 4. Color the root node black. While rebalancing, apply the rules given on pages 9-14. -} {- Question 6: Assume there exists a function sales :: Int -> Int that gives the weekly sales from a shop, where weeks are numbered in sequence 1, 2, .... What does the function foo06 below compute? -} sales :: Int -> Int sales 1 = 7 sales 5 = 3 sales _ = 42 {- EXAMPLES: foo06 5 == [2,3,4] -} foo06 n = mW n (sales n) [] where mW n max weeks | n < 1 = weeks | sales n > max = mW (n-1) (sales n) [n] | sales n == max = mW (n-1) max (n:weeks) | sales n < max = mW (n-1) max weeks {- A The week number with the largest sales in the period 1, ..., n. B The list of week numbers with the largest sales in the period 1, ..., n. C The list of week numbers in the period 1, ..., n with sales larger than max. D The list of week numbers with sales in the interval [n, max]. E The week number in the period 1, ..., n with sales larger than max. Answer: B. is just an accumulator (variable) whose vaue is (originally) set by the call the value of then changes according to what happens in the recursive call. In other words, the value of is not given as such, and therefore it does not make any sense to relate the answer to the value of as is done in the answers C,D,E. The only two remaining possibilities are A and B. But the line <| sales n == max = mW (n-1) max (n:weeks)> says that if more than one week has the largest sales, then a list of all such weeks shall be returned. -} {- Question 7: A heap is a data structure that is commonly used to implement A hash tables. B priority queues. C graphs. D search trees. E stacks. Answer: B. See the lecture slides '19-Binomial-Heaps.pdf', p 2: "A heap can be used to implement a priority queue". -} {- Question 8: Consider the following binomial heap. https://i.imgur.com/zIKXzgk.png After its minimum element is extracted, what is the resulting heap? A B C D E None of these. Answer: D. See the lecture slides '19-Binomial-Heaps.pdf', pp 9-13. Note the definition on page 10: "A _binomial_heap_ is a list of binomial trees such that each tree satisfies the min-heap property (hence the root of each tree contains its minimum key); and the trees have strictly increasing ranks." A consequence is that the number of elements determines what tree sizes should be in the binomial heap. In our example one element is removed from the original heap of 13 elements. Thus, 12 elements remain. The decimal number 12 is written 1100 as a binary number. The binary number 1100 tells us there are 0 trees of rank 0 (containing 2^0 elements), 0 trees of rank 1, 1 tree of rank 2 , and 1 tree of rank 3 (containing 2^3 elements). In other words, there will be one tree containing four elements and another tree containing eight elements. This rules out answers A and B. Answer C still has the element 1 which was supposed to be extracted. Answer D has the two correct trees containing the right elements and is therefore the correct answer. -} {- Question 9: Which of the following is a disadvantage of Abstract Data Types (ADTs)? A Abstract properties of a data type are separated from implementation details. B New operations have to be expressed in terms of existing operations. C An ADT is a collection of multiple data types. D Implementation details are hidden. E The implementation of an ADT depends on the specific data representation. Answer: B. See the lecture slides '20-Abstract-Datatypes.pdf', p 10. "Cons. Cannot add new operations, unless they are phrased in terms of existing ones." -} {- Question 10: Consider the following function bar10: -} {- EXAMPLES: bar10 [0,1,2,3,4] == [0,0,1,2,3,4] bar10 ["f00","bAR","f00Bar"] == ["f00","f00","bAR","f00Bar"] -} bar10 :: [a] -> [a] bar10 (x:xs) = x:x:xs {- Which of the following statements is correct? A bar10 is a polymorphic function because it accepts lists of any type. B bar10 returns the first element of a list. C bar10 is both an overloading and a polymorphic function. D bar10 overloads the identity function. E bar10 is a polymorphic function because it always performs the same operation. Answer: A. returns the argument list with the first element duplicated in the beginning of the list. It is true that it is a polymorphic function (since it accepts lists of any type). 'Overloading' refers to reusing a name of a function when the "same" functionality is defined for different data types. For example, the (infix) operation (+) may be defined for both integers and floats. See the lecture slides '06-Local-Declarations-Patterns-Overloading.pdf', pp 14-18. Answer E is not related to what it means that a function is polymorphic. See further the lecture slides '13-Polymorphism-Higher-Order-Functions.pdf', pp 6-7. The identity function mentioned in D is given on page 7. -} {- Question 11: Which of the following operations necessarily entails side effects in Haskell? A Wrapping a value in the Maybe type using the Just constructor. B Counting the number of files in the directory where the program is currently being run. C Inserting line numbers after each newline in a string. D Calculating the sum of the elements of a list. E Calling any function that uses monads. Answer: B. Counting the number of files in the directory where the program is currently being run. The result of such a function depends on how many files there are in the current directory. In general, this will NOT give the same result every time the function is called and hence by definition, the function is impure. See the lecture slides '02-Introduction-FP-and-Haskell.pdf', p 34. See the lecture slides '22-Imperative-Programming-I.pdf', p 6: "An expression is called pure if it has no side effects (such as I/O) and given the same argument value(s) _always_evaluates_to_the_same_result_." See the lecture slides '22-Imperative-Programming-I.pdf', p 11 - examples. -} {- Question 12: The function readFile :: FilePath -> IO String reads the contents of a file. Which of the following statements is correct? A readFile is referentially transparent, because it is always returns the same result. B readFile is not referentially transparent, because it may give different results for the same argument. C readFile is referentially transparent, because it is always clear what type the argument has. D readFile is not referentially transparent, because different arguments may give different results. E readFile is not referentially transparent, because no function in the IO monad is referentially transparent. Answer: B. See the lecture slides '22-Imperative-Programming-I.pdf', pp 8-9. This question is closely related to whether there are side effects: "An expression is said to be referentially transparent if it can be replaced with its value without changing the behaviour of a program. In other words, yielding a program that has the same output on the same input". https://stackoverflow.com/questions/41096040/why-wrap-an-io-result-in-io-monad/41096524#41096208 -} {- Question 13: Which of the following is not true for arrays (the ones in Data.Array.IO that you have seen in the lectures)? A Any element of an array can be written in O(1) time. B Arrays can only be used inside the IO monad. C The size of an array grows and shrinks as elements are added or removed. D The elements of an array are all adjacent in memory. E Any element of an array can be read in O(1) time. Answer: C. See the lecture slides '24-Imperative-Programming-III.pdf', pp 3-9, notably p 4: "An array is a continuous chunk of memory. Address of array is position of first location a. Element i of array is at address a + i — accessible in Θ(1) time." - The memory spaced reserved for an array is fixed. The only way to make it shrink or grow is to create a completely new array. -} {- Question 14: Consider the following code: -} {- foobar14 SIDE EFFECTS: ??? -} foobar14 :: IO Int foobar14 = do putStr "A" x <- putStr "B" let y = putStr "C" return x y putStrLn "D" return 42 {- What is the output (not the result) when evaluating foobar14? A AD B ABCD42 C ABCD D ABCBCD E ACBD Answer: C. See the lecture slides '22-Imperative-Programming-I.pdf', pp 13-46. In fact, the exact output when calling is: ABCD 42 But why? - Well, the side effects of the first three lines in the do-clause are to output ABC on the screen. has no side effect and therefore does not output anything. The same is true for the fifth line . The last side effect of is to output D. The function finally returns 42 which is then output on the screen. But this last output of 42 is output on the screen by ghci, and is not part of _evaluating_ . -} {- Question 15: Assume that a stack contains the entries (top) 1 2 3 4 5 6 (bottom). What is the content of the stack if we perform the following operations? push 2, pop, pop, push 1, top, push 1, pop A 2 1 1 1 2 3 4 5 6 B 2 3 4 5 6 C 1 2 3 4 5 6 D 1 1 2 3 4 5 6 E 2 1 1 2 3 4 5 6 Answer: C. See the lecture slides '20-Abstract-Datatypes.pdf', p 31. Just do each operation one at a time and write what the stack looks like: (top) 1 2 3 4 5 6 (bottom) push 2 (top) 2 1 2 3 4 5 6 (bottom) pop (top) 1 2 3 4 5 6 (bottom) pop (top) 2 3 4 5 6 (bottom) push 1 (top) 1 2 3 4 5 6 (bottom) top (top) 1 2 3 4 5 6 (bottom) -- The stack is unchanged. push 1 (top) 1 1 2 3 4 5 6 (bottom) pop (top) 1 2 3 4 5 6 (bottom) -} {- Question 16: Consider a hash table with 20 slots that uses chaining to resolve conflicts. What is the maximal possible chain length (worst case) of a single slot when the load factor is 3.2? A 16 B 3.2 C 32 D 64 E None of the above; the load factor can never be larger than 1. Answer: D. See the lecture slides '24-Imperative-Programming-III.pdf', pp 15 & 23. The definition is given in '24-Imperative-Programming-III.pdf', page 23: The load factor of a hash table with m slots and n elements is α = n/m The maximal possible chain length of a single slot happens when ALL the elements have been inserted in the very same slot. 20 slots and a load factor of 3.2 means that there are 20 x 3.2 = 64 elements. When collision resolution is done by chaining, the number of elements in a hash table is not limited by the number of slots as is the case for (linear) probing. Thus, nothing prevents the load factor from being larger than 1. -} {- Question 17: Assume you have a hash table of 10 slots using open addressing. The hash function of the table is h(k,i) = (k + f(i)) mod m where m = 10 is the number of slots of the hash table, and i is the probe number. Probing is linear: f(i) = i Insert the following elements 113,19,155,16,129,43 and then remove the element 155. If we now search for 33, how many times do we have to probe before we know for sure that this element is not in the table? Answer with the largest tried value of i. A 0 B 1 C 2 D 3 E 4 Answer: E. See the lecture slides '24-Imperative-Programming-III.pdf', pp 16-21, notably pp 19-21. The number k represents the element to be inserted, where h(k,i) = (h'(k) + f(i)) mod m is the (calculated) slot in the hash table for where to put element k, given the hash function h'(k) and the probing number i. In this case, h'(k) = k. After the first four insertions, the hash table t is: 0 1 2 3 4 5 6 7 8 9 ⊥ ⊥ ⊥ 113 ⊥ 155 16 ⊥ ⊥ 19 Next, 129 collides with 19 for i = 0, but t[0] = ⊥ for i = 1, so: 0 1 2 3 4 5 6 7 8 9 129 ⊥ ⊥ 113 ⊥ 155 16 ⊥ ⊥ 19 Finally, 43 collides with 113 for i = 0, but t[4] = ⊥ for i = 1, so: 0 1 2 3 4 5 6 7 8 9 129 ⊥ ⊥ 113 43 155 16 ⊥ ⊥ 19 Delete 155 from t using h'(k) = k mod 10. If we would set t[5] = ⊥, then search for a probed number could fail. Hence: 0 1 2 3 4 5 6 7 8 9 129 ⊥ ⊥ 113 43 ∆ 16 ⊥ ⊥ 19 Now search for 33. How many times do we have to probe before we know for sure that this element is not in the table? We try with i=0 which gives us 113≠33. For i=1 we get 43≠33. Finally, for i=2 we get ∆ but we STILL cannot conclude that 33 is not in the hash table. The reason is that - given what the hash table currently looks like - in both slots 5 and 6 there COULD have been numbers ending with a 3, of which the '3-number' in slot 5 has been removed. Hence, to be completely certain that 33 is not in the table we have to keep searching until we reach a ⊥. This happens at slot 7 with i=4. -} {- Question 18: In what order would a depth-first search, starting at the root, visit the nodes in the following binary tree? a / \ b c / \ \ d e f (In the tree above, all edges are directed downwards.) A abdecf B abecfd C abcedf D abcdef E acbfed Answer: A. See the lecture slides '25-26-Graph-Algorithms.pdf', pp 51-70. The algorithm is on page 53: DFS(G) 1. Paint all nodes white. 2. For each node v in G: if v is (still) white, DFS-Visit(G,v). Each subsequent call to DFS-Visit in line 2 is called a restart. DFS-Visit(G,v) 1. Colour v gray. 2. For each node u adjacent to v: if u is white, DFS-Visit(G,u). 3. Colour v black — this node is finished. Solution. DFS-visit a: colour a gray DFS-visit b: colour b gray DFS-visit d: colour d gray and then black DFS-visit e: colour e gray and then black Colour b black DFS-visit c: colour c gray DFS-visit f: colour f gray and then black Colour c black Colour a black The depth-first visit order is the order in which the nodes were coloured gray: abdecf Side marks: · abedcf, acfbde and acfbed are also possible depth-first visit orderings. · answers D=abcdef and E=acbfed are valid breadth-first visit orderings. -} {- Question 19: Consider the binary tree from the previous question. Which of the following is NOT a valid topological sort? A abcfed B acfbed C abdecf D abdefc E acbfed Answer: D. See the lecture slides '25-26-Graph-Algorithms.pdf', pp 19-33. The definition is on page 20: A topological sort is a linear ordering of all the nodes of a directed acyclic graph (DAG). If there is a path from node n_i to node n_j , then n_i appears before n_j in the ordering. Solution. From the definition we can conclude that: · node a must come before all the other nodes. · node b must come before both d and e. · node c must come before node f. In answer D, f comes before c which violates the topological sort. All other answers adhere to the three rules above. -} {- Question 20: Consider the following code that uses exceptions, where Exceptional a> and Exceptional a> are used to report good and bad values, respectively. -} data Exception = DivideByZeroException deriving (Eq,Show) type Exceptional a = Either Exception a throw :: Exception -> Exceptional a -- '23-Imperative-Programming-II.pdf', page 9. throw x = Left x (///) :: Int -> Int -> Exceptional Int _ /// 0 = throw DivideByZeroException a /// b = return (a `div` b) {- EXAMPLES: foo20 0 2 1 == Left DivideByZeroException -} foo20 :: Int -> Int -> Int -> Exceptional Int foo20 a b c = do e <- a /// b c /// e {- EXAMPLES: bar20 0 2 1 == 1 -} bar20 :: Int -> Int -> Int -> Int bar20 a b c = handler c (foo20 a b c) -- where {- EXAMPLES: handler 1 (Left DivideByZeroException) == 1 -} handler :: Int -> Exceptional Int -> Int handler d exc = case exc of Right y -> if y < 0 then -1 else y Left _ -> d {- What is the result of calling bar20 0 2 1? A 2 B 0 C 1 D -1 E DivideByZeroException Answer: C. See the lecture slides '23-Imperative-Programming-II.pdf', pp 3-16. Note the definition of the function Exceptional a> on page 9! bar20 0 2 1 --> handler 1 (foo20 0 2 1) (foo20 0 2 1) --> e <- 0 /// 2 --> (0 `div` 2) --> 0 1 /// e --> (1 `div` 0) --> throw DivideByZeroException --> Left DivideByZeroException handler 1 (Left DivideByZeroException) --> 1 In short, bar20 0 2 1 --> handler 1 (foo20 0 2 1) --> handler 1 (Left DivideByZeroException) --> 1 -} -- https://www.schoolofhaskell.com/school/starting-with-haskell/basics-of-haskell/10_Error_Handling