Stærðfræðimynstur í tölvunarfræði

Weekly note 12

This week we will finish covering graphs and start on trees. We will look at various properties of trees (9.1), their applications (9.2), and how you can traverse all the nodes of a tree (9.3).

Next week we will look at models of computation from Chapter 11.

Below are 5 excercises that you are to solve and turn in to your section teacher before noon monday november 21st. 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.

Skiladæmi 11

  1. Exercise 38 in section 8.3 on page 565 in the textbook.

  2. [Exam 2004] You are given the graph below:
    In how many ways can the vertices be marked with the letters a, b, c, d, and e such that the graphs are isometric, but not the same graph? In other words, how many different labelled graphs are isomorphic with the graph above? Explain how you calculate the number.

  3. Exercise 36 in section 8.5 on page 590 in the textbook. What about a Hamilton path?

  4. Exercise 16 in the supplementary exercises for Chapter 8 on page 626 in the textbook.

  5. Exercise 18 in section 9.1 on page 643 in the textbook.

Hand these exercices in before noon monday november 21st.

Also take a look at the following excercices:
From section 8.4:
5, 9, 25, 31, 35.
From section 8.5:
3, 7, 11, 33, 45.
From section 9.1:
3, 11, 17, 27.

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 14th, 2005.