EECS 340 Algorithms
2018 Spring Semester
Homework 4Homework 4
Due on March 28, 2018, 12:45pm
This assignment covers graph algorithms.
1. Warm-up: BFS
Given the graph:
A B
C D E
F G
(a) Draw the shortest path tree found by a BFS. (?)
(b) Annotate the tree in part (a) with the order vertices are visited in your BFS. (?)
(c) List the cross-edges of the BFS. (?)
2. Warm-up : Topological Sorting
(a) Find four distinct topological orderings of the nodes in the following directed
acyclic graph, presented here as a 3× 3 grid. (?)
(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)
1
(b) Describe how to generalize your orderings to the case of a graph with the same
connectivity pattern on an n× n grid. (? ?)
3. A Unicycle Problem
Prove that a cycle exists in an undirected graph if and only if a BFS of that graph
has a cross-edge. (? ?)
Your proof may use the following facts from graph theory:
• There exists a unique path between any two vertices of a tree.
• Adding any edge to a tree creates a unique cycle.
4. A Bicycle Problem
Solve C-13.15 in the text. You may assume that the graph is connected. (? ?)
5. Maximal Independent Set 1 An independent set I of an undirected graph G = (V,E)
is a subset I ⊆ V such that if u, v ∈ I , then (u, v) /∈ E. A maximal independent set M
is an independent set which cannot have any vertices added to it without losing the
independent set property. Describe an efficient algorithm to compute the maximal
independent set of any such G. (? ?)
6. Application: Procrastinator’s Sort
The year is 430BC. Socrastes The Philosopher has a collection of important ethical
questions to ponder over. Some of these questions have dependencies, i.e: ”Is it eth-
ical to consume meat?” should be answered before the question ”What should I eat
for lunch?” is resolved. Socrastes may only consider one question at a time, but nev-
ertheless, Socrastes is a masterful philosopher: whenever Socrastes begins thinking
about a question, Socrastes is guaranteed to answer it in a few days. Socrastes will
always respect the dependencies between questions in choosing which questions to
think about. However, whenever Socrastes has a choice between two questions 2 to
ponder, Socrastes will always choose the less important question to think about. 3
Suppose that Socrastes ranks the importance of questions on an integer scale from 1
to 10. If the number of questions is n and the number of dependencies is m, describe
an algorithm which returns a possible order that Socrastes might think about the
questions in O(n+m) time. (? ? ?)
7. Application: Zombie Apocalypse
The year is 2050AD. CWRU’s HvZ got a little out of hand this year, primarily due to
one BME student’s discovery of a zombifying virus. Luckily, Babs has constructed
an elaborate labyrinth 4 where all students are currently in hiding. Suppose that the
labyrinth is represented by an m × n matrix of values in {H,Z,W}, where H , Z,
1Reproduced from A-13.3, only with 100% fewer lawyers involved.
2To reiterate, for Socrastes to have a choice beween two or more questions, the questions must have no
remaining prerequisites for Socrastes to handle.
3This fatal flaw is widely regarded by philosophers to have set back the field several thousand years.
4Known as KSL
2
and W correspond to humans, zombies, and walls, respectively. Each minute, all
zombies infect all humans which are directly adjacent to them in the labyrinth, e.g,
if the state of the labyrinth at zero minutes is:
H W H
H Z Z
H W H
then the state of the labyrinth at one minute is:
H W Z
Z Z Z
H W Z
Describe an algorithm to determine how long (in minutes) it will take for all humans
in Babs’ labyrinth to become zombies. Assume that no human is safe. (? ? ?)
8. The following is for EECS 454 students only. Read Section 17.3 in the textbook and
then solve the following problems:
(a) R-17.2
(b) C-17.7
(c) C-17.8
Submission
Hand in your paper in-class by the beginning of class on the due date. Always check
Canvas for updates and corrections.
3