{-
 * Uppsala University - 2017 Fall
 * Program Design and Data Structures, 1DL201
 * Exam 2016-12-20, attempted solutions
 * Copyright 2017 Henrik Alfken(Schulze)
 * Inspired by: competition with Madde.
-}

{- split ls
  PRE:  True -- Q 03
  POST: a pair (xs,ys) such that xs++ys is a permutation of ls -- Q 04
  EXAMPLES:
    split [1,2,3,4]
      == ([1,3],[2,4]) -- Q 01
    split [3,4]
      == ([3],[4])
  COMMENT:  split is NOT a higher-order function. -- Q 06
-}
-- split :: [a] -> ([a],[a]) -- Q 02
-- VARIANT: length ls -- Q 05
split (x:y:ls) = let (xs,ys) = split ls in (x:xs, y:ys)
split ls = (ls, [])

{- Question 1: What is the value of split [1,2,3,4] ?
  A [(1,2),(3,4)]   B ([1,2],[3,4])   C ([1,3],[2,4])   D 10    E [1,3]
Answer: C.
-}

{- Question 2: What is the type (?TYPE?) of split?
  A [a] -> [(a,b)]  B [a] -> (a,b)  C [a] -> ([a],[b])  D [a] -> ([a],[a])  E [a] -> (a,[b])
Answer: D.  -- In GHCi, type :t split
-}

{- Question 3: What is the most appropriate precondition (?PRE?) for split ls?
  A True    B ls is a list    C length ls ≥ 2   D ls is non-empty   E False
Answer: A.
-}

{- Question 4: What is the most appropriate postcondition (?POST?) for split ls?
  A a pair (xs,ys) such that xs++ys is a permutation of ls
  B a list of all pairs in ls   C True    D (ls, [])    E (x:xs, y:ys)
Answer: A.
-}

{- Question 5: Which of the following is a variant (?VARIANT?) for the function split?
  A length ls ≥ 2   B ½·(length ls)   C 0   D length ls   E x + y + length ls
Answer: D.
-}

{- Question 6: Which of the following statements is false?
  A split is a polymorphic function.      B split is a higher-order function.
  C split is a recursive function.        D split terminates for all valid arguments.
  E The definition of split is type-correct.
Answer: B.
-}


{- Question 7: Consider this alternative definition of split,
  where the order of the two equations has been swapped:
  split ls = (ls, [])
  split (x:y:ls) = let (xs,ys) = split ls in (x:xs, y:ys)
Which of the following statements is correct for this definition of split?
  A If split ls returns the pair (xs,ys), then xs++ys is equal to ls.
  B Evaluating split ls does not terminate.
  C This definition is not type-correct.
  D This definition of split is equivalent to the definition given earlier
    (i.e., the two functions behave exactly the same).
  E If split ls returns the pair (xs,ys), then xs and ys have the same length.
Answer: A.
-}
{- splitQ07 ls
  PRE:  -
  POST: a pair (ls,[]) such that ls++[] is ls -- Q 07
  EXAMPLES:
    splitQ07 [1,2,3,4] -- Q 07
      == ([1,2,3,4],[])
-}
splitQ07 ls = (ls, [])


{- Question 8: Consider the function  f x = div 0 x + div x 0
Evaluating f 42 will result in ...
  A Infinity            B a syntax error.       C a type error.       D none of these.
  E a run-time error.
Answer: E a run-time error. (Due to 'div x 0'.)
-}
{- fQ08 x
  EXAMPLES:
    fQ08 42
      *** Exception: divide by zero -- Q 08
-}
fQ08 x = div 0 x + div x 0


{- Question 9: Which of the following values does NOT match the pattern (_, [2,x]) ?
  A (1, [2])    B (1, [2,2])    C ([1,2], [2,3])    D ((1,2), [2,3])    E (1, [2,3])
Answer: A - the second tuple element, [2], is a list containing only one element.
  A
    (_, [2,x]) = (1, [2])       -- ?
    x
*** Exception: <interactive>:14:5-25: Irrefutable pattern failed for pattern (_, [2, x]) --> A!
  B
    (_, [2,x]) = (1, [2,2])     -- ?
    x   -- x == 2
  C
    (_, [2,x]) = ([1,2], [2,3]) -- ?
    x   -- x == 3
  D
    (_, [2,x]) = ((1,2), [2,3]) -- ?
    x   -- x == 3
  E
    (_, [2,x]) = (1, [2,3])     -- ?
    x   -- x == 3
-}


{- Question 10: Consider the function   f x = let f x = x+1 in f (f x)
What is the value of let x=0 in f x ?
  A 0   B 2   C 4   D 1   E None of these.
-}
{- fQ10 x
  EXAMPLES:
    let x=0 in fQ10 x
      == 2
    fQ10 0
      == 2
-}
-- Rewrite the function to make it less confusing to read:
fQ10 x = let g y = y+1 in g (g x)
-- Answer: B.


{- Question 11: Which of the following statements is FALSE?
Both Quicksort and Mergesort ...
  A are divide-and-conquer algorithms.
  B can sort lists of arbitrary length.
  C split the problem into two subproblems of similar size.
  D can sort lists containing positive as well as negative integers.
  E are recursive algorithms.
-}
-- The answer is supposed to be C, which is somewhat ridiculous, since Quicksort
-- also splits the problem into two subproblems of 'similar' size, AS LONG AS the
-- pivot element is well chosen. (Which it always will be if the indata is random.)


{- Question 12: Which of the following expressions is NOT equivalent to the other four?
  A (/) 2   B (2/)    C \x -> 2 / x   D (/2)    E \x -> (/) 2 x
  (NOTE: backslash \ is supposed to be read as LAMBDA.)
  Looking at B, C, E, it shoud be clear that the function is (2/x), NOT (x/2).
  So the question follows: which of the five denotes (x/2)? Try with x=1:
  In GHCi, what is   D (/2) 1 ?  - Well, try it out and you will see it is 0.5.
  { You can verify that (for x=1) the result of all the others is 2.0:
  A (/) 2 1    B (2/) 1    C (\x -> 2 / x) 1    E (\x -> (/) 2 x) 1   }
-}


{- Question 13: Let f(n) = 3n^2 + 4n + 5. Which of the following does NOT hold?
  A f(n) = Ω(n^3)
  B f(n) = Ω(n^2)
  C f(n) = O(n^3)
  D f(n) = O(n^2)
  E f(n) = Θ(n^2)
Answer: A, f(n) is not bounded below by n^3; n^3 'grows faster' than n^2.
-}


{- Question 14: What is the closed form of the following recurrence?
  T(0) = 4
  T(n) = T(n − 1) + 2n + 3 if n > 0
  A T(n) = (n + 3)^2
  B T(n) =  n^2
  C T(n) = (n + 2)^2
  D T(n) = (n + 1)^2
  E T(n) = n·log(n^2)
Answer: C, see below!

Substitution method:
  T(0) = 4
  T(1) = 4 + 2·1 + 3
  T(2) = (4 + 2·1 + 3) + 2·2 + 3
  T(3) = ((4 + 2·1 + 3) + 2·2 + 3) + 2·3 + 3
  T(4) = (((4 + 2·1 + 3) + 2·2 + 3) + 2·3 + 3) + 2·4 + 3
  ...
  T(k) = 4 + 2·(1+2+3+4+...+k) + k·3
  ...
  T(n) = 4 + 2·(1+2+3+4+...+n) + 3n = 4 + n·(n+1) + 3n = n^2 + 4n + 4         □

Expansion method:
  T(n) = T(n−1) + 2n + 3
       = (T(n-2) + 2·(n-1) + 3) + 2n + 3
       = ((T(n-3) + 2·(n-2) + 3) + 2·(n-1) + 3) + 2n + 3
       = (((T(n-4) + 2·(n-3) + 3) + 2·(n-2) + 3) + 2·(n-1) + 3) + 2n + 3
       = T(n-4) + 2·(n-3) + 3 + 2·(n-2) + 3 + 2·(n-1) + 3 + 2n + 3
  ...
       = T(n-k) + 2·(n-k+1) + 3 + ... + 2·(n-2) + 3 + 2·(n-1) + 3 + 2n + 3
  ... Let k=n:
       = T(n-n) + 2·(n-n+1) + 3 + ... + 2·(n-2) + 3 + 2·(n-1) + 3 + 2n + 3
       = T(0) + 2·(1) + 3 + ... + 2·(n-2) + 3 + 2·(n-1) + 3 + 2n + 3
       = T(0) + 2·(1+2+3+4+...+(n-2)+(n-1)+n) + n·3
       = 4 + n·(1+n) + 3n = n^2 + 4n + 4                                         □
Same answer with both methods! Isn't that nice? (:-)
Expanding answer C:       (n+2)^2 = n^2 + 4n + 4                                 □
-}

{- Question 15: Which of the following statements is FALSE?
  A If f(x) = Θ(g(x)) then f(x) = O(g(x))
  B f(x) = Θ(f(x)), for all f
  C If f(x) = Θ(g(x)) then g(x) = Θ(f(x))
  D If f(x) = O(g(x)) then f(x) = Θ(g(x))
  E If f(x) = O(g(x)) then g(x) = Ω(f(x))
Answer: D. It suffices to find a counter example, like f(x)=x and g(x)=x^2.
Then clearly f(x) = O(g(x)). - But it is clear (?) that f(x) != Θ(g(x))          □
-}


{- Question 16: Use the Master Theorem to find a closed form for the following recurrence:
T(n) = 4T(n/2) + n^2
The closed form is:
  A T(n) = Θ((n^4)/2 + n^2)
  B T(n) = Θ(n^2 log n)
  C T(n) = Θ(n^2)
  D T(n) = Θ(n log log n)
  E The Master Theorem does not apply.
Normally B would be the right answer (case 2 on page 1), but this year it is E. (:-)
-}


{- Question 17: Which answer is the recurrence best describing the run-time cost of
the following Haskell function?
  foo :: [a] -> Integer
  foo [] = 0
  foo [x] = 1
  foo (x:y:xs) = length (x:xs) + foo xs
Assume n is the length of the argument list.
  A T(n) = Θ(1)                 if n ≤ 1
    T(n) = T(n/2) + Θ(n + 1)    if n > 1

  B T(n) = Θ(1)                 if n ≤ 1
    T(n) = 2T(n − 2) + 2Θ(n)    if n > 1

  C T(n) = Θ(1)                 if n ≤ 1
    T(n) = 2T(n − 1) + Θ(n)     if n > 1

  D T(n) = Θ(1)                 if n ≤ 1
    T(n) = T(n − 1) + Θ(n − 2)  if n > 1

  E T(n) = Θ(1)                 if n ≤ 1
    T(n) = T(n − 2) + Θ(n)      if n > 1

Answer:
  T(n) = t0                       if n ≤ 1
  T(n) = t_cons·(n-1) + T(n-2)    if n > 1  -- Argument list is shortened by 2 per recursion
Or:
  T(n) = Θ(1)                     if n ≤ 1
  T(n) = T(n-2) + Θ(n-1)          if n > 1
And since Θ(n-1) = Θ(n), E is the correct answer.
-}


-- I believe we have NOT talked about the issues raised in questions 18-20.


{- Question 18: To implement a complex program, one can use one of three techniques: top-down 
design, bottom-up design or dodging. Which of the following is NOT true for top-down design?
  A Does not break the flow of programming the algorithm.
  B Uses existing functions to build new functionality and solve a larger project.
  C Relies on building new, simple functions with clearly defined purposes.
  D Divides the problem into simpler sub-problems.
  E Starts with an overall view of the entire algorithm.
Answer: B.

See the lecture slides '27-28-Design.pdf', pp 17, 18, 63-83. Page 17:
    "Cheating (Top-down design) - break function into smaller functions — larger function
    relies on smaller functions. Implement smaller functions _after_ larger function."
  Page 18:
    "Cheating (Top-down design) - reduce complexity to implementable chunks"
  Definition on page 74:
    "Determine how the problem should be divided into easier sub-problems
    that can be solved by helper functions.
      · Write function specifications for helper functions.
      · Write algorithms (e.g., in pseudocode).
        These may use additional helper functions.
      · Use helper functions to implement current function.
    Repeat the process for helper functions."
  Nice quotations on page 75:
    "Cheating is a concrete way of doing top-down design."
    "Maybe bluffing is a better name than cheating
      — you are pretending to have something that isn’t there."
-}


{- Question 19: In the 8 Step Design Process, how does data description contribute
to the overall design of the project?
  A Data representation guides the process of dividing the large problem into
    smaller sub-problems that are easier to solve.
  B Data description is very important for large projects, but the programmer can
    implement small programs without reasoning about data representation.
  C Reasoning about data representation helps the programmer to outline the
    implementation based on inputs and expected outputs.
  D Data representation should provide concrete examples of input data, borderline
    cases, valid and invalid inputs.
  E Data representation adds a level of abstraction, helping to separate general
    ideas from specific implementation decisions.
Answer: C.

  The answer in A sounds more like top-down design.
  Does the answer in B make any sense?
  The answer in D sounds more like function examples.
  Answer E? Exactly the opposite — that data representation makes the problem more concrete?
See the lecture slides '27-28-Design.pdf', pp 17, 18, 26-33. Page 17:
    "Data Description - understand the data: number, boolean, string, image, ..."
  Page 18:
    "Data Description - shape of data will drive implementation"
  Page 27:
    "Data representation: Determine what data structures are needed to represent
     the data that the program should work on (the ‘real world data’.)"
    "Every datatype definition comments explaining:
      · Representation Convention description of how the data type represents
        the ‘real world data’
      · Representation Invariant requirements on elements
        of the datatype that the code preserves at all times"
-}


{- Question 20: Why are tracing and debugging not enabled by default in every program execution?
  A Because it slows down execution.
  B Because the programmer can track the errors by reasoning only.
  C Because either tracing or debugging is required, but not both.
  D Because tracing and debugging cannot be enabled simultaneously.
  E Because it would disturb programmers that will maintain the code in the future.
Answer: A.

See the lecture slides '21-Debugging-and-Testing.pdf'. Tracing on pp 13-23. Debugging on pp 32-52.
  Not sure that this answer is spelled out explicitly in the lecture slides?
  But the statements on page 38 might be of help:
    "A debugger allows you to set points in your program (called breakpoints) where execution
     will stop." Obviously, you don't want a program to stop _every_ time you execute it.
  In fact, tracing is sometimes enabled by default in every program execution. In procduction
  code, writing 'traces' an event log file is a standard technique for doing this. Page 15:
    "Eventlog tracing — performance profiling system. These functions emit extra events into
     the eventlog. In combination with eventlog profiling tools, these functions can be used
     for monitoring execution and investigating performance problems."
("We will not be using eventlog tracing or consider performance. Considered in detail in IOOPM.")
-}