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
  app-admin/addpatches

It makes good sense to read the data from the file outside Find-Dep and let this function work on some kind of graph representation. Beware that due to some technical obscurities of Linux package management (or package management in general) there may be circular dependencies in the graph. You algorithm should detect them "on-the-fly". In such situation it is sufficient to stop the algorithm, producing the error message. What is the asymptotic complexity of your solution?

Assignment 9.2

Modify the function from the previous exercise so that it also accepts an array containing names of packages already installed in the system. The new Find-Dep-Realistic function should return only the names of packages not yet installed, and do it as efficiently as you can. What is the asymptotic complexity of your solution?

Note: you do not have to either know or use Linux to solve the above exercises.

DISCLAIMER/ADVERT : Beware that the data in dependecies.txt has been simplified for you and does not reflect dependencies as precisely as in Linux distributions. In reality dependencies are much more complex, some of them need to be satisfied when the package is compiled, some when the package is running. Also there are alternative dependencies (any package of given class can be installed to satisfy them), and requirements up to the specific version number and package. Finally some dependencies are conditional, depending on how the package is configured, what hardware are you running and what is already available on the system. All these lead to much more interesting algorithmic problems. At ITU these kind of algorithms are actively studied in the VeCoS group. Feel free to contact Andrzej if your are interested in writing a 4-week project or a master's thesis in a related topic.