Homework 5

Due Wednesday, February 25

1. (a) A partial order on a set $S$ is a relation $R$ on $S$ such that $R$ is (i) irreflexive (i.e., $s \not R s$ for all $s \in S$) and (ii) transitive (i.e., if $s R t$ and $t R u$, then $s R u$ for all $s, t, u \in S$). Given such a partial order $R$ on a set $S$, let $G = (V, E)$ be a directed graph defined by $V = S$ and $E = \{ (s, t) : s R t \mbox{ for } s, t \in S \}$. Prove that $G$ is a directed acyclic graph.

   (b) For a set $S = \{ a, b, c \}$, let ${\cal P}(S)$ be the power set of $S$, the set of all eight subsets of $S$. The proper-subset relation $\subset$ on ${\cal P}(S)$ then defines a partial order on ${\cal P}(S)$. Draw a directed acyclic graph $G = (V, E)$ induced by $\subset$ on ${\cal P}(S)$; that is, $G = (V, E)$ is defined by $V = {\cal P}(S)$ and $E = \{ (A, B) : A \subset B \mbox{ for } A, B \in {\cal P}(S) \}$. Then give a topological ordering of $G$. How many different topological orderings does $G$ have?

2. Another important approach to find topological orderings of directed acyclic graphs uses depth-first search. For a directed graph $G = (V, E)$ of $n$ nodes and $m$ edges, modify depth-first search to determine whether or not $G$ is acyclic and, if so, find a topological ordering of $G$ in $O(n + m)$ time. Give a complete algorithm, including depth-first search, and carefully prove its correctness and analyze its runtime.

3. The major requirements for the computer science major at a college is comprised from a set of required courses, some of them having prerequisites. As usual, a prerequisite for a course $c$ is a course $c'$ that must be completed before taking $c$—formally specified by a pair $(c', c)$. A course may have no or any number of prerequistes. For a set of $n$ courses and $m$ pairs of prerequisites, design an $O(n + m)$-time algorithm to determine the minimum number of semesters required to complete the major requirements, assuming that (i) all courses are offered each semester, and (ii) a student may take any number of courses each semester.

CPSC 320 home page