1.Which type of proof technique is most representative of a "greedy stays ahead" argument?

Select one:

a. Proof by contradiction

b. Proof by induction

c. Resolution theorem proving

d. Probabilistically-checkable proofs

2.

Suppose there are 20 intervals in the interval scheduling problem; some intervals overlap with other intervals. Construct a graph G with 20 nodes, each node corresponds to an interval, and there is an edge between two intervals if the two intervals overlap. Suppose there is a set of 10 intervals you can pick such that none of them overlap with each other. Which of the following is always a true statement about G?

Select one:

a. G has an independent set of size 10.

b. G is connected.

c. G has a cycle of length 10.

d. G is disconnected.

3.

Suppose an instance of the interval partitioning problem has intervals with si=i and fi=i+5+(1/log(n)+1)fori=1 to n. Then the depth of this set is:

Select one:

a. (nn)

b. (n)

c. (logn)

d. (1)