Description
Practicing Chapter 3 and 4
1. (5 Points) Chapter 3: Topological Order Consider the directed acyclic graph G in the figure
below. How many topological orderings does it have? Explain how you get computed it. List
the topological order.
a
b
d
c
e
f
2. (25 Points) Chapter 4: Scheduling
You have n distinct jobs, labeled J1, J2, …, Jn, which can be performed completely independently of one another. Each job consists of two stages: first it needs to be preprocessed on a
supercomputer, and then it needs to be finished on one of a local PCs. Let’s say that job Ji
needs pi seconds of time on the supercomputer, followed by fi seconds of time on a PC.
There are at least n PCs available on the premises, the finishing of the jobs can be performed
fully in parallel–all the jobs can be processed at the same time. However, the supercomputer
can only work on a single job at a time, so the system managers need to work out an order
in which to feed the jobs to the supercomputer. As soon as the first job in order is done on
the supercomputer, it can be handed off to a PC for finishing; at that point in time a second
job can be fed to the supercomputer; when the second job is done on the supercomputer, it
can proceed to a PC regardless of whether or not the first job is done (since the PCs work in
parallel); and so on.
(a) (10 Points) Design a schedule for the ordering of the jobs for the supercomputer that
minimize thecompletion time of the schedule. The definition of the completion time
of the schedule is the earliest time at which all jobs will have finished processing on the
PCs.
(b) (5 Points) What is the running time of your algorithm?
(c) (10 Points) Prove that the schedule that you designed is optimal.
Hint: 1- Think of an order of the jobs with some rational explained and try to find a counter
example until you find a good order. 2- You can use the exchange of argument to prove the
optimality the same way that we did in for minimizing the max. lateness problem.
1
3. (35 Points) Chapter 4 – Trees on Graphs (Midterm, Fall 2011).
Consider the undirected graph shown in the following figure. It consists of six nodes A,B,C,D,E,F
and nine edges with the shown edge costs.
A C E 6 5
1
2 3 4
4
5
F
2 3 4
B
5
D F 2 4
(a) (10 Points) Run Dijkstra’s algorithm to find the shortest paths from node A to all other
nodes. (Show the final answer and briefly describe the intermediate steps.)
(b) (10 Points) Run an algorithm of your choice (e.g., Kruskal, Prim, Reverse-Delete) and
find a minimum spanning tree. (Show the final answer and briefly describe how you got
there.)
(c) (10 Points) Is the minimum spanning tree of this graph unique? Justify your answer,
i.e., if the answer is yes, provide a proof; if the answer is no, provide a counter-example
and explain why this is the case.
(d) (5 Points) Consider the average distance from A to all other nodes, first by following
edges on the shortest path tree (a), let’s call it davg
SPT ; and then following edges on the
minimum spanning tree found in (b), let’s call it davg
MST . Which one is greater, davg
SPT or
davg
MST ? Does the same answer hold for any graph G = (V, E) and node A ∈ V , or is it
specific to this example?
4. (20 points) Chapter 4 – (Midterm, Fall 2019).
Consider the undirected graph below.
(a) (10 Points) Use an algorithm of your choice to find a Minimum Spanning Tree (MST)
for this graph. Show the final answer (draw the tree and write down its cost) and briefly
describe how you got the answer (which algorithm you used and some intermediate
steps).
(b) (10 Points) Is the MST for this graph unique? Justify your answer, i.e., if the answer is
yes, provide a proof; if the answer is no, provide a second MST as a counter-example.
2
5. (15 Points) Combinatorial Structure of Spanning Trees: Let G be a connected graph,
and T and T ′ two different spanning trees of G. We say that T and T ′ are neighbors if T
contains exactly one edge that is not in T ′
, and T ′ contains exactly one edge that is not in
T .
Now, from any graph G, we can build a (large) graph H as follows. The nodes of H are
the spanning trees of G, and there is an edge between two nodes of H if the corresponding
spanning trees are neighbors.
Is it true that, for any connected graph G, the resulting graph H is connected? Give a proof
that H is always connected, or provide an example (with explanation) of a connected graph
G for which H is not connected.
3
