Example solutions to TDDC32 exam 09-03-17
		=========================================

1)
 a) Divide the main problem into smaller subproblems. Solve the subproblems
    separately (but: cf 1c). Combine the subsolutions into a solution for
    the whole problem.

 b) The design isn't completed in one try. Start with a rough sketch. Rethink
    the decisions over and over again. Add new ideas, change bad ones.

 c) Old designs, both parts already designed in the same project and parts from
    old projects, could be used again - to reduce the work.

 d) In a good design there should be strong/many relations between the parts in
    an object/a class and weaker/fewer relations between (objetcs of) different
    classes. This facilitates 1c.

2)
  Interfaces: Animal, Predator, Prey, Wild, Domestic.
  Classes: Mammal, Bird, Fox, Rabbit, Eagle, Hen, Leg.

  <----  =  inheritance
  <****  =  implementation
  .....  =  other relations

  All classes except Predator should look like 

  +-----+
  |Class|
  +-----+
  +-----+
  +-----+

  but here I'm saving some space.
    
                             +---------+
     +**********************>| Animal  |<----------------------+
     *     +****************>+---------+<-----------------+    |
     *     *                 ^        ^                   |    |
     *     *                 |        |                   |    |
     *     *        +---------+       +----+              |    |
     *     *        |Predator +.......+Prey|              |    |
     *     *        +---------+       +----+              |    |
     *     *        |preys    |       ^   ^               |    |
     *     *        |favourite|       *   *               |    |
     *     *        +---------+       *   *               |    |
     *     *        +---------+       *   *               |    |
     *     *          ^    ^          *   *               |    |
     *     *          *    *  *********   *               |    |
     *     *          *    +---+          *               |    |
     *     * ,--------+----|Fox|**********+*************. |    |
     *     * V        *    +---+          *             V |    |
     *    +------+    *                   *            +----+  |
.....+..<>|Mammal|    *                   *            |Wild|  |
.    *    +------+    *                   *            +----+  |
.    *       ^        *         +------+  *             ^ ^    |
.    *       `--------+---------|Rabbit|**+*************' |    |
.    *                *         +------+  *               |    |
.    *           +-----+                  *               |    |
.    *   ,-------|Eagle|******************+***************'    |
.    *   V       +-----+                  *                    |
.    +----+                               *             +--------+
. .<>|Bird|                               *             |Domestic|
. .  +----+                               *             +--------+
. .      ^                              +---+            ^
. .      `------------------------------|Hen|************'
.4.2                                    +---+
+---+
|Leg|
+---+

3)
 a)  4   =>     6     =>         __6__       =>     __6__
               / \              /     \            /     \
              4   9            4      10          4      10
                              / \    /  \        / \    /  \
                             3   5  9    11     3   5  8    11
                                                      / \
                                                     7   9

 b) A Fibonacci tree is an AVL tree with greatest height for a given number of
    nodes. It is used in computing the complexity of AVL tree operations.

4)
 a)  4  =>   6  =>  9   =>  11  =>   5      =>  3
            /      /        /       / \          \
           4      6        9       4   9          4
                 /        /           / \          \
                4        6           6   11         5
                        /                            \
                       4                              9
                                                     / \
                                                    6   11

 b) It's better when the same value, or a small set of values, is accessed very
    often. It's better because that/those element(s) is/are kapt at or near the
    root of the tree.

5)
 a) Every node has at least a children. Exception: The root has at least 2
    children.
    Every node has at most b children.
    2 <= a <= [b/2], where [x] means x rounded up to nearest integer.

 b)       +-+-+
          |2|5|
          +-+-+
         /  |  \
      +-+ +-+-+ +-+-+
      |1| |3|4| |6|7|
      +-+ +-+-+ +-+-+

6)
 e) The hash function may return the same array index for two different
    elements, That problem is solved by a-d.

 a) Every position in the array contains a (pointer to a) linked list.
    All elements for which the hash function returns the same index are
    inserted into the linked list for that position.

 b) If there already is an element in the indexed (i) array position
    consecutive indices (i+1, i+2, i+3, ...) are tested until a free position 
    is found.

 c) If there already is an element in the indexed (i) array position the
    indices i+1, i+4, i+9, ... (square increments) are tested until a free
    positions is found.

 d) If there already is an element in the indexed (i) array position the
    indices i+j, i+2j, i+3j, ... (where j=h'(x), x is the element to insert, and
    h' is a second hash function) are tested until a free position is found.

7)
 a) (See slide copies on course web.)

 b)
  i  - Searching for an element in a sorted array is as efficient as searching
       in a skip list.
       When inserting an element into an array all the higher elements must be
       moved in the array.

  ii - Searching  for an element in a linked list must start from the beginning
       and look at every element until the correct position is found.
       Inserting - when correct plac is found - is as easy as in a skip list.