COMP225 Tutorial Exercises for week 4

  1. Consider the following log of an interactive session of the Animal game discussed in lectures. 
    No file 'animalData' found: starting from scratch.

Is it animal, vegetable or mineral? (animal,vegetable,mineral,save,quit) animal
What is it? a horse
It's a horse, eh? Now that's settled, let's try again.

Is it animal, vegetable or mineral? (animal,vegetable,mineral,save,quit) animal
Is it a horse? (yes,no) no
What is it then? a cow
Give me a 'yes' question for a cow: does it have horns?
Ok; let me have another go.

Is it animal, vegetable or mineral? (animal,vegetable,mineral,save,quit) animal
does it have horns? (yes,no) yes
Is it a cow? (yes,no) no
What is it then? a goat
Give me a 'yes' question for a goat: does it have a beard?
Ok; let me have another go.

Is it animal, vegetable or mineral? (animal,vegetable,mineral,save,quit) animal
does it have horns? (yes,no) no
Is it a horse? (yes,no) no
What is it then? a rabbit
Give me a 'yes' question for a rabbit: does it eat lettuce?
Ok; let me have another go.

    (a)* Sketch the corresponding animal tree at this point in the game.

    (b)* Now suppose we think of a cat, which does not have horns, and does not eat lettuce. Sketch the resulting tree after adding a node for a cat, and a "yes" question of your choice.

    (c)* Write down the correct serialised file if the game is now saved. Remember to use the correct indenting and tagging.

  2. What is the worst-case complexity of the algorithm which rebalances a binary search tree, using the restore function discussed in lectures?
  3. Consider now the algorithm for computing the optimal winnings discussed in lectures. Sketch the LookUp table if the players play the game with the line of money V={2,4, 8, 2, 1, 2}.
  4. Adapt the optimal winnings algorithm to compute Player 1's optimal strategy.
  5. Trace the algorithm for finding the maximal contiguous subsequence sum discussed in lectures for A={1,2,-1,-1, 6, 2,-1, 3}.
Answers to all of the above starred questions should be handed in to your tutor at your scheduled tutorial in Week 4.

All enquiries to Annabelle McIver