算法代写: EECS 340 Algorithms Homework 4

EECS 340 Algorithms 2018 Spring Semester

Homework 4

This assignment covers graph algorithms.

1. Warm-up: BFS Given the graph:

AB

CDE

FG

(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)

(1, 0)

(2, 0)

(0, 1)

(1, 1)

(2, 1)

(0, 2)

(1, 2)

(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 graphhas 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 SortThe 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 ApocalypseThe 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:

HWH

HZZ

HWH

then the state of the labyrinth at one minute is:

HWZ ZZZ HWZ

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

3