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.
- Exercise 38 in section 8.3 on page 565 in the textbook.
- [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.
- Exercise 36 in section 8.5 on page 590 in the textbook. What about a Hamilton path?
- Exercise 16 in the supplementary exercises for Chapter 8 on page 626 in the textbook.
- 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) hi.is, November 14th, 2005.