{- * Uppsala University - 2017 Fall * Program Design and Data Structures, 1DL201 * Exam 2016-03-17, attempted solutions * Copyright 2018 Henrik Alfken(Schulze) * Inspired by: competition with Madde. -} {- Question 1: Suppose you want to write a physics simulation, where objects move through space. Each object has a speed, given by a value of type Double. Speeds are measured either in meters per second (m/s) or in kilometers per hour (km/h). Which of the following type declarations could you use to make sure that speeds measured in m/s are not confused with speeds measured in km/h? A type Speed = Double B type SpeedMs = Double; type SpeedKmh = Double C data Speed = Ms | Kmh D data Speed = Speed Double E data Speed = Ms Double | Kmh Double Answer: E. See the lecture slides '15-16-Inductive-Data-Types.pdf', page 30, Geometric Shapes: A type that models circles (of a given radius), squares (of a given side length) and triangles (of three given side lengths): -- INVARIANT: all Doubles are positive data Shape = Circle Double | Square Double | Triangle Double Double Double -} {- Question 2: In what order would a post-order traversal process the values in the following binary tree? a / \ b c / \ \ d e f (In the tree above, all edges are directed downwards.) A abdecf B abcdef C dbeacf D debfca E fedcba Answer: D. See the lecture slides '15-16-Inductive-Data-Types.pdf', page 59, traversals: A traversal of a data structure is a way of processing each element in the data structure exactly once. For binary trees, we distinguish: · Pre-order traversal: process the root value, then traverse the left subtree, then traverse the right subtree · In-order traversal: traverse the left subtree, then process the root value, then traverse the right subtree · Post-order traversal: traverse the left subtree, then traverse the right subtree, then process the root value Apply the rule for post-order on the above tree: · The left subtree of node a is bde, of which the left subtree of b is d, and the right subtree of b is e. Hence the post-order of the bde subtree is deb. · The right subtree of node a is cf, of which the left subtree of c is empty, and the right subtree of c is f. Hence the post-order of the cf subtree is fc. · The post-order of the whole tree is the post-order of the left subtree followed by the post-order of the right subtree - and finally node a. Putting it together: debfca. -} {- Question 3: 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 (f03) compute? -} {- EXAMPLES: f03 t == 5 -} f03 (Node a ts) = 1 + fs03 ts -- where {- EXAMPLES: fs03 [t] == 5 -} fs03 [] = 0 fs03 (t:ts) = f03 t + fs03 ts {- A The sum of all values in a tree. B The number of nodes in a tree. C The height of a tree. D A post-order list of all values in a tree. E A pre-order list of all values in a tree. Answer: B. See the lecture slides '15-16-Inductive-Data-Types.pdf', pp 48-65. On each occurrence of another node in the tree, line 72 = adds one (1) to a call to the helper function fs03, which in turn calls f03 on the next tree and adds the result to a recursive call of fs03 on the remaining sibling trees. Putting it all together it means that the function f03 counts the number of nodes in the compound tree (starting at the root). -} {- Remark: replacing the digit <1> in with an would produce the sum of all values in the tree. -} {- EXAMPLES: sum03 t == 30 -} sum03 (Node a ts) = a + sumAux03 ts -- where {- EXAMPLES: sumAux03 [t] == 30 -} sumAux03 [] = 0 sumAux03 (t:ts) = sum03 t + sumAux03 ts {- Question 4: The (worst-case) complexity of inserting an item into a binary search tree with n nodes is A O(2^n) B O(n) C O(1) D O(n^2) E O(log n) Answer: B. See the lecture slides '17-Binary-Search-Trees.pdf', pp 1-25. On page 21 it says: "the complexity of inserting into and searching in binary search trees is O(n) in the worst case". -} {- Question 5: Suppose the following numbers are inserted, in the given order, into an initially empty red-black tree. (Grey=red.) 29 62 78 10 14 99 31 68 What is the resulting red-black tree? https://i.imgur.com/QJZMfhq.png A B C D E None of these. Answer: A. 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 then rebalance the tree. 4. Color the root node black. While rebalancing, apply the rules given on pages 9-14. -} {- Question 6: How many nodes does a binomial tree of rank r have? A r B [lg r] + 1 C (r) D 2^r E 1 (k) Answer: D. See the lecture slides '19-Binomial-Heaps.pdf', page 8: "There are 2^r nodes in the tree." -} {- Question 7: Which of the following is a distinguishing feature of abstract data types? (distinguishing: characteristic of one thing or person, so serving to identify it; distinctive.) A Pattern matching. B Hidden implementation details. C More efficient than other kinds of data types. D Polymorphism. E Different constructors representing different kinds of data. Answer: B. See the lecture slides '20-Abstract-Datatypes.pdf', page 9: "An abstract datatype is an encapsulation mechanism. In general it is composed of several components: ... · An implementation hidden from the client of the data type. ... Data abstraction: a clear separation between the abstract properties of a data type (public) and the concrete details of its implementation (private). " -} {- Question 8: What is the result of merging the following two binomial heaps? https://i.imgur.com/zJPfZwZ.png For definition, see the lecture slides '19-Binomial-Heaps.pdf', page 10. Each binomial heap is a collection of binomial trees such that · each tree satisfies the min-heap property (the minimum key in the root); and · the trees have strictly increasing ranks. In this case, the following two heaps are to be merged: 73 25 64 10 | - and - / | 82 30 86 | 69 Solution. Start by merging the two zero-ranked trees containing 64 and 73. Since 64 < 73, we get the following binomial tree as a result: 64 | 73 which added with the tree containing 25-82 becomes: 25 / | 64 82 (since 25 < 64) | 73 Finally, adding the two trees with 4 elements each becomes: _ 10 _/ / | 25 30 86 / | | 64 82 69 (since 10 < 25) | 73 which is the same heap as the one depicted in answer D. A B C D E None of these. Answer: D. See the lecture slides '19-Binomial-Heaps.pdf', pp 9-13. About merging binomial heaps, also see: https://brilliant.org/wiki/binomial-heap/#binomial-trees https://brilliant.org/wiki/binomial-heap/#binomial-heaps and then scroll down to "Merging Binomial Heaps". This is a 'brilliant' explanation on how to merge two heaps. :P -} {- Question 9: Which of the following best describes the concept of overloading? A Two or more functions with the same name but different definitions. B Two or more functions with different definitions. C Two or more functions with the same definition. D Computationally-intensive functions that overload the CPU. E Polymorphic functions. Answer: A. See the lecture slides '20-Abstract-Datatypes.pdf', pp 44-78. Page 56: "Overloading allows code to use the same name for functions of different type and different implementations." (Not sure why E cannot be considered a correct answer? Page 56 of the slides: "Overloading is a kind of polymorphism called ad hoc polymorphism.") -} {- Question 10: Which of the following, when executed from within a Haskell program, is NOT a side-effect? A Writing 'one does not simply walk into Mordor' to the screen. B Halting the program with an error. C Playing Soundgarden’s 'Spoonman' through the speakers. D Recursively calculating the number of times the phrase 'there is evil there that does not sleep' occurs in a string. E Reading Tolkien’s 'The Lord of the Rings' from a text file. Answer: D. See the lecture slides '22-Imperative-Programming-I.pdf', pp 1-11. On page 6 it says: "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." In this case, given that the recursive calculation of a phrase is done on a given string (which is therfore always the same) will always return the same number. (Provided it is implemented correctly.) -} {- Question 11: Consider the type class Mirror which has a function mirror :: t -> t whose intention is to produce some kind of mirror image of a data structure. -} class Mirror t where mirror :: t -> t instance Mirror () where mirror () = () instance Mirror Bool where mirror = not instance Mirror Int where mirror n = -n instance (Mirror a, Mirror b) => Mirror (a,b) where mirror (a,b) = (mirror a, mirror b) data BTree a b = Leaf a | Branch b (BTree a b) (BTree a b) deriving (Eq,Show) {- EXAMPLES: mirror () == () (mirror 5::Int) == (-5) mirror $ Leaf (5::Int) == Leaf (-5) mirror $ Branch (True,()) (Leaf [(1::Int),2,3]) (Branch (False,()) (Leaf [3,4,5]) (Leaf [5,6,7])) == Branch (False,()) (Branch (True,()) (Leaf [-7,-6,-5]) (Leaf [-5,-4,-3])) (Leaf [-3,-2,-1]) -} instance (Mirror a, Mirror b) => Mirror (BTree a b) where mirror (Leaf a) = Leaf (mirror a) mirror (Branch b l r) = Branch (mirror b) (mirror r) (mirror l) instance Mirror a => Mirror [a] where mirror = reverse . map mirror {- Given the test case mirror $ Branch (True,()) (Leaf [1,2,3]) (Branch (False,()) (Leaf [3,4,5]) (Leaf [5,6,7])) = Branch (False,()) (Branch (True,()) (Leaf [-7,-6,-5]) (Leaf [-5,-4,-3])) (Leaf [-3,-2,-1]) which of the following is the most reasonable implementation of mirror for BTree? A mirror (Leaf a) = mirror (Leaf a) mirror (Branch b l r) = Branch (mirror b) (mirror r) (mirror l) B mirror (Leaf a) = Leaf (mirror a) mirror (Branch b l r) = Branch (mirror b) (mirror r) (mirror l) C mirror (Leaf a) = Leaf (mirror a) mirror (Branch b l r) = Branch b (mirror l) (mirror r) D mirror (Leaf a) = Leaf a mirror (Branch b l r) = Branch b (mirror l) (mirror r) E mirror (Leaf a) = Leaf (mirror a) mirror (Branch b l r) = Branch b (mirror r) (mirror l) Answer: B. In A, is an infinite loop (no variant!) so it never terminates. For the remaining suggestions, look at the test case! In D, violates SHOULD be <(Leaf [-3,-2,-1])> In E, violates that SHOULD become In C, violates that in the mirror the _left_ subtree SHOULD become <(mirror r)>. (It also has the same violation as in E.) To conclude, B is the only the answer that is in accordance with the given test case. -} {- Question 12: Which of the following is true about native/truly mutable arrays (the ones in Data.Array.IO) in Haskell? A O(1)-time read, O(1)-time write. B O(logn)-time read, O(1)-time write. C O(logn)-time read, O(logn)-time write. D O(1)-time read, O(logn)-time write. E O(1)-time read, O(n)-time write. Answer: A. See the lecture slides '24-Imperative-Programming-III.pdf', pp 3-9, notably p 4: "Element i of array is at address a + i — accessible in THETA(1) time." In this case, 'accessible' should be interpreted to mean both _read_access and _write_access. -} {- Question 13: Consider the following code: -} {- main SIDE EFFECTS: ??? -} main = do putStrLn $ "13" let x = putStrLn "10" y <- putStr "12" x putStrLn "11" return y -- let z = 42 -- return z {- What is the output (not the result) of evaluating main in ghci? A 13 1210 11 12 B 13 12 10 11 C 13 10 12 11 D 13 1210 11 E 13 10 1211 12 Answer: D. See the lecture slides '22-Imperative-Programming-I.pdf', pp 13-46. Note that is not evaluated immediately, which means that the side effect is postponed as well. And since does not output a line break, <10> comes immediately after and on the same line as <12>: 13 1210 11 -} {- Question 14: Assume that a stack contains the entries (top) 12 15 12 16 12 17 (bottom). Which stack is the result of performing the following operations pop, pop, push 12, pop, pop, push 12 ? A 12 15 12 12 B 12 17 12 12 C 12 12 12 15 D 12 12 12 12 E 12 16 12 17 Answer: E. 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) 12 15 12 16 12 17 (bottom) pop (top) 15 12 16 12 17 (bottom) pop (top) 12 16 12 17 (bottom) push 12 (top) 12 12 16 12 17 (bottom) pop (top) 12 16 12 17 (bottom) pop (top) 16 12 17 (bottom) push 12 (top) 12 16 12 17 (bottom) -} {- Question 15: Given a hashtable with 7 slots that contain, respectively, chains of length 1, 2, 0, 0, 3, 1, 0. That is, slot 0 contains a chain of length 1, slot 1 contains a chain of length 2, slot 3 is empty, etc. Keys are numbers and the hash function is hash(key) = key mod 7. What is the length of the longest chain after inserting the numbers 12, 16, 34, 7, 15, 21, 22, assuming that none of these keys already appear in the table? A 3 B 4 C 5 D 6 E 7 Answer: B. See the lecture slides '24-Imperative-Programming-III.pdf', pp 10-24. As in the previous exercise, just insert each number one at a time and write what the hash table looks like, remembering that that hash table is indexed starting with zero: 1, 2, 0, 0, 3, 1, 0 12 = 7 + 5 1, 2, 0, 0, 3, 2, 0 16 = 2·7 + 2 1, 2, 1, 0, 3, 2, 0 34 = 4·7 + 6 1, 2, 1, 0, 3, 2, 1 7 = 7 + 0 2, 2, 1, 0, 3, 2, 1 15 = 2·7 + 1 2, 3, 1, 0, 3, 2, 1 21 = 3·7 + 0 3, 3, 1, 0, 3, 2, 1 22 = 3·7 + 1 3, 4, 1, 0, 3, 2, 1 We see that the longest chain is for numbers ending with 2, and that the length is 4. -} {- Question 16: Consider the following hash table of 11 cells, where ⊥ denotes that a cell was never used. 0 1 2 3 4 5 6 7 8 9 10 33 23 57 35 70 ⊥ 6 ⊥ 19 ⊥ 54 Assume that the hash function is h(k) = k mod 11, that open addressing with linear probing function f(i) = i is used as the conflict resolution method, and that duplicates are allowed. Firstly, 35 is deleted from the hash table. In which cell of the resulting table will 89 be placed? A Nowhere B 3 C 5 D 9 E 10 Answer: B. 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 and m = 11. After the deletion of 35 = 3·11 + 2, the hash table will look as: 0 1 2 3 4 5 6 7 8 9 10 33 23 57 ∆ 70 ⊥ 6 ⊥ 19 ⊥ 54 Next, 89 = 8·11 + 1 collides with 23 for i=0, and with 57 for i=1, but t[3] = ∆ for i=2, so: 0 1 2 3 4 5 6 7 8 9 10 33 23 57 89 70 ⊥ 6 ⊥ 19 ⊥ 54 which shows that 89 is inserted in slot 3. -} {- Question 17: Consider the following graph: https://i.imgur.com/SogvXTn.png Which of the following is a valid adjacency list representation of the graph? A B C D E Answer: E. See the lecture slides '25-26-Graph-Algorithms.pdf', pp 3-18, notably page 17. Note that D gives an edge list and not an adjacency list. Similarly, answers A and B give adjacency matrices and not _lists_. Answer C would have been a valid adjacency list IF the graph had been UNdirected. On each line in answer E, the source node is to the left of the vertical bar, while the valid destination nodes are to the right of it. (You may note, for example, that from node 4 the graph does not allow you to go anywhere, so the list of destinations is empty.) -} {- Question 18: Consider the graph from the previous question. Which of the following is a valid depth-first search ordering—that is, the order in which nodes are visited when performing a depth-first search? A 154326 B 156342 C 324561 D 623451 E 635214 Answer: C. 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. In general, a depth-first search traversal is NOT unique, so there is no way of finding _the_one_and_only_ DFS-ordering. So let us instead try them out one at a time. A 154326 15 starts OK, but the next node SHOULD have been 6 which it is not. B 156342 1563 starts OK, but the next node SHOULD have been 2 which it is not. C 324561 DFS-visit 3: colour 3 gray DFS-visit 2: colour 2 gray DFS-visit 4: colour 4 gray and then black Colour 2 black DFS-visit 5: colour 5 gray DFS-visit 6: colour 6 gray and then black (because we have already been at node 3 so it is no longer white) Colour 5 black Colour 3 black At this point we have visited all nodes and painted them black except for node 1 which is still white. Note that we could not reach node 1 when starting from node 3, so we need to restart: - Restart - DFS-visit 1: colour 1 gray and then black (because neither node 4 nor node 5 are white any more.) At this point we can confirm that 324561 is indeed a DFS-ordering, and we could stop here. D 623451 6 starts OK, but the next node SHOULD have been 3 which it is not. E 635214 6352 starts OK, but the next node SHOULD have been 4 which it is not. -} {- Question 19: Consider the following graph: https://i.imgur.com/Qi7bqtz.png Which of the following is a valid topological sort of this graph? A 123456 B 654321 C 243615 D 516342 E 613245 Answer: E. 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 6 must come before all the other nodes. Otherwise there is now way to reach node 6. From this we can rule out all answers except B and E. · node 3 must come before node 2. Both B and E fulfill this requirement. · node 2 must come before node 4. Only E fulfills this requirement. -- · 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. -- 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 | BadWordException | ConquerByZorroException 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 cleanSentence :: String -> Bool cleanSentence s = and $ (map clean) (words s) where clean s = not (s `elem` ["flip", "jeez", "crumbs"]) censor :: String -> Exceptional String censor s = if cleanSentence s then return s else throw BadWordException duplicate :: Int -> String -> Exceptional String duplicate n s | n < 0 = throw ConquerByZorroException duplicate n s | otherwise = return $ concat $ replicate n s {- EXAMPLES: prog 2 (-1) "ingen smuts här" == Left ConquerByZorroException -} prog :: Int -> Int -> String -> Exceptional String prog a b s = do e <- a /// b f <- censor s duplicate e f {- Under what conditions on inputs a, b, and s does function result in a ? A Whenever a is negative and s contains no bad words. B Whenever b is not zero, a `div` b is negative, and s contains no bad words. C Whenever b is not zero, a `mod` b is negative, and s contains no bad words. D Whenever neither a nor b is zero, at most one of a or b is negative, and s contains no bad words. E Whenever neither a nor b is zero, at most one of a or b is negative, and s is not empty and contains no bad words. Answer: B. See the lecture slides '23-Imperative-Programming-II.pdf', pp 3-16. Note the definition of the function Exceptional a> on page 9. For the function to result in a , it is necessary that (1) does NOT produce a (2) does NOT produce a (3) DOES produce a For (1) to hold, it is necessary that b ≠ 0. For (2) to hold, it is necessary that s contains no bad words. For (3) to hold, it is necessary that (a `div` b) < 0. See the lines 598, 600, 579, and 589. To conclude, it is necessary that b ≠ 0, (a `div` b) < 0, and that s contains no bad words. -}