Reference no: EM132598322

Question 1. Explain how to modify Prim's algorithm so that it finds connected compo- nents of an undirected graph without edge weights.

Question 2. Use the symbols ⊂ and = (and no ⊆ ) to order the sets below. No justification is needed.

?((2^{lg n})²) ?(2^{((lg n)2)}) ?(2^lg(n2)) ?(2^{ln n}) ?(n²).

Response:

?( ) ?( ) ?( ) ?( ) ?( ).

Question 3. Let ti : i = 0, 1, . . . , 9 be a set of tasks to execute, each needing a unit of time. The task ti must be completed by the time di in order to bring a profit of gi, both given in the table below.

	t0	t1	t2	t3	t4	t5	t6	t7	t8	t9
g	20	15	43	2	5	15	16	10	30	7
d	3	4	2	2	4	3	7	4	3	9

What is the order of execution of these tasks that maximizes the total profit and what is the profit if you use what we called the "fast algorithm" (i.e. "student algorithm")?

Ordre:

Gain:

Question 4. Let T = {c1, . . . , cn} be a set of keys; you may assume that they are given in an array, also called T , in the obvious way: T [i] = ci. Give an algorithme that finds the two smallest keys in fewer than n + lg n comparisons. Prove, or at least justify, your claims.