Question 1 is due on 19 October 2004 by email before start of lecture.
Questions 2,3,4,5 are due by noon Friday 22 October.
CSE 591 Assignment Three
-
Write a brief description of your individual project topic. The
description must include
- a working title;
- a statement of the problem you are investigating;
- a statement of objectives for what you are trying to do;
- a (three or four sentence long) progress report.
-
Using your program from Assignment 2 for all-terminal reliability of
L(n,m) as a starting point, compute the coefficients P_i, N_j and
H_k in the following equal forms of the reliability polynomial:
- sum(P_i p^i : 0 <= i <= m)
- sum(N_i p^i (1-p)^{m-i} : 0 <= i <= m)
- p^{n-1} * sum(H_i (1-p)^i : 0 <= i <= m-n+1)
Compute the coefficients in EACH form for L(n,m) with
n = 3...7 and all possible values of m.
-
Prove that the coefficients P_i from question (2) alternate in sign
(i.e. if P_i > 0 then P_{i-1} <= 0 and P_{i+1} <= 0).
-
Suppose that you have an oracle to compute all-terminal reliability of an
input graph G in time which is linear in the size of G. How can you
determine the number of spanning subgraphs of H which have
exactly two connected components, in time which is polynomial in the
size of H?
-
Prove the best upper bound that you can on the magnitude of P_i as a
function of n and m (do this for all possible values of i).
For the programming, choose any language you like. Do not spend a lot of
time on bells and whistles -- your main task is to get a basic easy-to-use
program that you can do some simple tests on.
Email me if you have tried
to figure out what to do, but have questions that you need
answered.