Performance and Test, Spring 2007 : Episode 4.1
Subject: Graphs, Graph Traversals
Note: We are reading the second volume of the book (part 5) from now on.
Text : RS 17.0 pp. 3—7, RS 17.2 (read until you can understand Program 17.2 p. 19 and Program 17.3 p.20. The rest can be skipped). RS 17.3—17.4 pp. 25—35, Table 17.1 p. 40 (skim the section around if you need to interpret the table), RS 18.0—18.3 pp.81—97 (in 18.3 focus on the properties). Study 18.5 briefly to realize what kind of applications DFS has. RS 18.7 pp. 121—130. [50pp, 5h]
Prerequisites: sorting, asymptotic complexity, basic data structures (lists, arrays), hash tables, basic graph theory (read RS 17.1 if you lack a bit of graph theory).
Comment: There are three main units in this lecture: graph representation (adjacency matrix vs adjacency list), depth first graph traversals (DFS) and breadth first graph traversals. Try to keep track of these important concepts among the multitude of technicalities and diversions in the book.
Reading carefully this week, will help you directly in making a better project!
Following exercises are easy and good for initial self-study (not exam level):
RS exercise 17.17 p. 30, 17.27 p. 35
RS exercise 18.50, 18.51 p. 130
Some of the following exercises will be discussed at the exercise session:
RS Exercise 17.21 p.30. Is such an optimization possible for directed graphs? For weighted undirected graphs?
RS Exercise 17.25 p.31. Clique is defined on page 13, RS vol.2 (top of the page)
RS Exercise 18.23 p. 110.
RS Exercise 18.31 p. 112.
RS Exercise 18.56 p. 130.
The solutions to one of the following exercises should be handed in to the course pigeon hole, before Wednesday, March 7, 13:30 [expected time 2h]
Exercise 17.22 p.30 in RS
Exercise 17.30 with 17.31 p.35 (treated as one exercise, hand in together)
|
|
|
|
Last updated Feb 16, 2007 22:30Henrik Reif Andersen, Andrzej Wąsowski |