Computer Science

EX3_1 due 11:50pm, 3/16(Fri)

· Download this instruction word file. Fill in your answers and covert into pdf. Upload to both Canvas and Turnitin by the due date.

· Among the top tabs, go to FilePrint. Choose “Microsoft PDF” as the printer and print. This saves the file as a pdf file.

· You may insert one or more figures. See the item “How to insert a figure” on Canvas for how.

1. (5pts) Show by induction on |V| that |E|=|V|-1 for any tree T=(V, E).

(Write your answer directly here. Provide a complete proof.)

2. (9pts) The following is the proposition we used in EX2_22 and its proof.

Proposition: Let G=(V,E) be an edge-weighted graph, and T be any minimum spanning tree of G. The algorithm MST(G) can return T with some allowed choices of the next minimum edge e.

Proof: It suffices to show the following invariant for every given non-negative integer m .

Invariant: There exists an edge set calc T that can be constructed by MST(G) so that m=|calc|.

We show by induction on m. The base case m=0 is clearly true; T includes calc when calc is an empty set. Assume true for m and prove true for m+1.

Let:

· calc be a subset of T that is constructed MST(G) so that |calc|=m,

· be the set of edges, each of which grows a connected component in calc, and

· where is the weight function on G.

It further suffices to prove that:

(A) there exists an edge in the tree T such that

The statement (A) is true otherwise _______________(B)______________. The algorithm MST(G) can choose such an edge e as the next choice. Therefore, calc can be constructed by MST(G), whose size is m+1. This completes the induction step.

Answer the three questions.

a. Explain why the invariant for all m |V|-1 is sufficient to prove the proposition. Write your answer in at least 3 and less than 15 lines.

b. Explain why the statement (A) is sufficient to prove the induction step. Write your answer in at least 3 and less than 15 lines.

c. Fill in the blank (B) justifying the answer.

Answer for (B): (write your answer as a part of the proof, in one or two lines)

Justification: (Explain why it’s correct in at least 3 and less than 15 lines.)

3. (6 pts) Prove that select(A[1 to n], k) given in vLec3_1 runs in linear time, by solving the running time recurrence seen in the last activity.