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.