Performance and Test, Spring 2008 : Episode 7.1

Spring 2008

Description

Schedule

Resources

Lecture: Wednesday, February 20, 9:00-11:00, room 3A14

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!

Exercises, Friday, Feb 22, 13:00—16:00 (room 3A52)

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.

Last updated Feb 22, 2008 11:20 Dan Witzner Hansen, Kristian Støvring