# Introduction to Algorithms and Data Structures, Fall 2004, Episode 9

## Lecture, October 25

Subject : Graph representations. Breadth-first search. Depth-first search. Topological sort.

Text : CLRS 22.1–22.4; 23.1–23.2 (Prim's algorithm is optional).

Prerequisites : Directed and undirected graphs. Paths and cycles.

Comments : You should aim for a good understanding of the ideas, mechanics and details of both Breadth-first Search and Depth-first Search algorithms as well as the reasons why they lead to the desired results.

Time : Monday, October 25, 9:00–12:00 (3×45min), Room 2A12

Tutorial : 13:00–16:00 (3×45min), Room 2A12

## Assignments

• CLRS exercises 22.1-1 (M), 22.1-3, 22.1-5, 22.1-6, pp 530
• CLRS exercises 22.2-1 (M), 22.2-3, 22.2-4, 22.2-5, 22.2-7 (D), pp 538-539
• CLRS exercises 22.3-1 (H), 22.3-2, 22.3-3 pp 547
• CLRS exercises 22.4-1 (M), 22.4-3, 22.4-5 pp 551-552
• What happens if, in TopologicalSort, we arrange the vertices in the order of increasing discovery time rather than in the order of decreasing finishing time? Do we necessarily get a correct solution to the topological sorting problem?

The mandatory assignments should be handed in no later than November 5 at 13.00.

## Programming Assignments

### Assignment 9.1

The file dependencies.txt contains package dependencies extracted from some distribution of Linux operating system. Each line in the file contains information about a single dependency: two package names separated by a colon. Each package name consists of a prefix, a slash and the actual name. For example the first line states app-admin/addpatches:sys-devel/patch meaning that the package called "app-admin/addpatches" depends on the package "sys-devel/patch", so "sys-devel/patch" should be installed before "app-admin/addpatches".

Implement a function Find-Dep which for a given package name S returns a sequence of transitive dependencies of S in the order they should be installed to get S to run on your bare-bones system. For example a call Find-Dep("app-admin/addpatches") should print something like:

sys-libs/glibc
sys-devel/patch