Strfrimynstur tlvunarfri

Weekly note 13

This week we will finish with tree application (9.2) and then start on tree traversals (9.3). We will go on to various types of models for computation in Chapter 11. Among them grammars (11.1) and finite state machines (11.2 and 11.3).

Next week we will continue with finite state machines and regular expressions.

Below are 5 excercises that you are to solve and turn in to your section teacher before noon monday november 28th. Remember to mark your solutions with the number of your section and the name of the section teacher. Also below are few extra excercises that you can use to practice on and make sure that you have understood the material. Some of them will be solved in the sections if there is time.

Homework 12

    1. Construct a binary search tree from the words of the sentence "Fgur er hlin svo a mr hefir hn aldrei jafnfgur snst". Enter the words into the tree in the order in which they appear in the senctence.
    2. Show i) an inorder and ii) a preorder for the words in the tree from part a).

  1. Exercise 6 in section 9.2 on page 656 in the textbook.

  2. Exercise 12 in section 9.3 on page 673 in the textbook.

  3. Exercise 22 in section 9.3 on page 673 in the textbook.

  4. Exercise 4 c) and e) in section 11.1 on page 749 in the textbook.

Hand these exercices in before noon monday November 29th.

Also take a look at the following excercices:
From section 9.2:
1, 3, 7, 9.
From section 9.3:
7, 9, 23, 25, 29.
From section 11.1:
3, 5, 7, 11.

Remember that the above exercises are for you to practice on, and that you get the most out of them by trying to solve them yourselves (not by looking at someone else solving them!). The exercises in bold are more "interesting" than the others and it is more likely that they will be covered in the sections.

hh (hja), November 21st, 2005.