Late Penalty: 5% per working day, cutting o date October 31
Submit your work electronically through Wattle. The total mark is 50. Note that the
mark you received from each question is proportional to the quality of your solution.
Question 1 (25 points).
A complete graph is an undirected graph G = (V;E) with an edge between each pair
of nodes. An induced subgraph G[A] = (A;(A A)\E) of a graph G is a subgraph
induced by the nodes in set A with A V .
Given a 10 10 square in a 2-D plane with its four corner coordinates are: (0;0)
- the most left bottom coordinate, (0;10) - the most left top coordinate, (10;10) - the
most top right coordinate, and (10;0) the most right bottom coordinate. We randomly
choose n nodes within this square. Let node vi have a coordinate (xi;yi), where the
values of both xi 0 and yi 0 are randomly drawn from an interval [0,10], where xi
and yi are random real numbers uniformly distributed between 0 and 10.
Let V =fvi j 1 i ng be the set of a complete graph K(V ) = (V;E), the weight
(or cost) assigned to each edge (vi;vj) 2E is the Euclidean distance between nodes vi
and vj, i.e., w(vi;vj) = p(xi xj)2 + (yi yj)2. We term such a complete graph in this
square area as a randomly generated complete graph.
Let L(n) be the sum of edge weights in a minimum spanning tree (MST) of a ran-
domly generated complete graph K(V ) with n =jVj nodes. Your tasks are to
(i) Calculate the average L(n), which is the cost sum of p MST costs divided by p
where p randomly generated complete graphs need to be constructed and p 20,
using Prim’s algorithms when n = 200;400;800;1;600, respectively (10 points).
(ii) Observe the changing trend of the value of L(n) with the growth of n, and explain
why this happens. (2 points)
(iii) The actual running time of Prim’s algorithm when n = 200;400;800;1;600, re-
spectively (don’t include the graph generation time). (2 points)
(iv) Let K(V ) be a randomly generated complete graph, let Ui be a subset of V with
a fraction size of set V , i.e., Ui V i = 1;2;3. Assume that the nodes in Ui
are randomly drawn from set V , and the size of Ui is de ned as jU1j = d3jVj4 e,
jU2j=djVj2 e, andjU3j=djVj4 e. Let K(Ui) be an induced subgraph of K(V ) by the
nodes in Ui ( V ), which is a complete graph too, where K(Ui) = (Ui;(Ui Ui)\E).
(a) Compute the ratio of the sum of the edge weights of the MST of K(Ui) to the
sum of the edge weights of the MST of K(V ) for all i with 1 i 3 when
n = 200, 400, 800, and 1,600 (6 points)
(b) What is the upper bound on the ratios obtained in Part (a)? (1 point)
(c) Show the theoretical upper bound on the ratio. (Hint: Make use of triangle
inequality of edge weights, 4 points)
More precisely, write code using one language such as C, C++, Java, or Python program
that does this: For each size n = 200;400;800;1;600, generate at least p = 20 randomly
generated complete graphs with n nodes and determine the sum of the weights of the
edges in minimum spanning trees of the graphs as well as the running times of Prim’s
algorithms. Notice that the graph generation time will not be taken into account. In your
report, print out
(i) The average L(n) of the sum of edge weights of 20 MSTs for each n by Prim’s
algorithms
(ii) Explain the changing trend of the value of L(n) with the growth of n
(iii) The average running time of Prim’s algorithm for nding MSTs in the 20 graphs
for each n
(iv) Compute the ratio of the MST of an induced subgraph K(Ui) of a randomly
generated complete graph K(V ), where the nodes in Ui are randomly drawn from
V for all i with 1 i 3. Observe the upper bound on these ratios, and show
this bound theoretically.
Your program should have the following properties.
1. Do not read any input. Write one line of output for each n, and at most 5 extra
lines of explanatory output.
2. Store the graph as a symmetric matrix.
3. The minimum priority queue will be employed in the implementation of Prim’s
algorithm, and you may implement the minimum priority queue by yourself or
make use of it from your program language lib if it does exist there.
4. To measure the running time of an algorithm, refer to a timing procedure in the
exercise of the 1st lab.
5. (a) If you use C, write the program as a single le mst.c which will compile on
Linux with the command
gcc -o mst mst.c -lm
(\-lm" selects the maths library; you might not need it). Use real random
numbers (type double) generated using the library function rand() whose
use is illustrated as follows.
/* This program generates 10 random double numbers in (0,10).
* Note that rand() returns an integer in the range [0,RAND_MAX],
* so you need performing some conversion to double and scaling.*/
#include
#include
int
main(int argc, char *argv[])
{
double x;
int i;
for (i = 0; i 1, where
1 ij n and 1 j k. (7 points for COMP3600 and 5 points for
COMP6466)
Give an e cient algorithm to print out the sequence if it does exist. (3 points)
Analyze the running time of your algorithm. (2 points)
Question 3 (13 points for COMP3600 and 10 points for COMP6466)
You are given a n n checkerboard and a checker. A square of the checkerboard is
speci ed by (x;y) with 1 x;y n. You are initially located at some square (a;1) at
some row a and column 1 with 1 a n. At each step, you can move from square
(x;y) to square (x0;y0), where jx x0j 1 and y0 = y + 1 with 1 x0;y0 n. For
each move, you will receive a payment of f(x;y;x0 x) dollars where f is a pre-de ned
function for all 1 x n, 1 y n, and jx x0j 1.
Devise an e cient algorithm for maximizing the sum of dollars collected for all
the moves from your initial location (a;1) to your nal location (b;n), you need
to determine the values of both a and b with 1 a n and 1 b n. In other
words, you need to nd your movement path starting from your initial location
(a;1) to your nal location (b;n) such that the sum of payments you collected
along the path is maximized. You can either make use of natural language to
describe your algorithm, or use pseudo-code to describe your algorithm with brief
explanations. (10 points for COMP3600 and 7 points for COMP6466)
Analyze the running time of your algorithm. (3 points)
Question 4 (5 points for COMP6466 only)
Given a set of m machines M1;M2;:::;Mm and a set of n jobs, each job j has a
processing time tj with 1 j n. We seek to assign each job to one of the m machines
so that the work loads placed on all machines are as \balanced" as possible.
Let A(i) denote the set of jobs assigned to machine Mi. Under this assignment,
machine Mi needs to work for a total time of Ti = Pj2A(i) tj, which is the load at
machine Mi. We seek to minimize a quantity known as the makespan, i.e., the maximum
load among all machines T = maxfTi j 1 i mg is minimized.
The following sort-based heuristic can provide an approximate solution to the prob-
lem.
Sort Balance(tj)
1 for i 1 to m do
2 Ti 0;
3 A(i) ;;
4 endfor;
5 Sort jobs in decreasing order of processing time tj, assuming that t1 t2 ::: tn;
6 for j 1 to n do
7 Let Mi be a machine that achieves the minimum load so far,
i.e., Ti = minfTk j 1 k mg;
8 Assign job j to machine Mi;
9 A(i) A(i)[fjg;
5
10 Ti Ti + tj;
11 endfor
Show the approximation ratio of algorithm Sort Balance is 3/2. (Hint: If there are
more than m jobs, then T 2tm+1, where T is the optimal makespan, (5 points))
Bonus Question (5 points)
Warning: the following question is designed for people who are capable of doing some
extra research-related work. Only if you have nished all basic questions correctly and
are willing to challenge yourself, you can proceed the question.
BQ.1: We say a graph is k-edge connected if the removal of any k0 edges from the graph
with k0 < k and k 2, the resulting graph is still connected. Given a d-edge connected,
weighted undirected graph G = (V;E) with n = jVj nodes and m = jEj edges, we say
that d 1 edges e1 2 E, e2 2 E, :::;ed 1 2 E are most vulnerable if their removals
will result in the maximum increase on the weighted sum of the edges in a minimum
spanning tree of graph G0 = (V;En[d 1i=1feig) with d 2.
Devise an O(nd)-time algorithm to identify these d 1 most vulnerable edges e1;e2;:::;ed 1
in G, assuming that d 2 is a constant integer. (A graph is 2-edge connected if it is
still connected after the removal of any edge from it.) (5 points)