2. Show that f(n) = n² + n is Q(n²) by applying the definition of Q-complexity from Chapter 3 of Cormen (reproduced below).

Definition: (g(n)) = { f(n) : there exists positive constants c₁, c₂, n₀ such that 0 c₁g(n) f(n) c₂g(n) , for n n₀ }. Prove that you can find a (c₁, c₂, n₀) triple that meets the criteria.

3. What is the worst-case asymptotic running time of the following method mthd, assuming that the parameter n is a positive integer? Assume doLogTimeWork() does O(lg n) work. Briefly explain your reasoning.

void mthd( int n ) {

for ( int i = 1; i

for ( int k = 1; k

doLogTimeWork();

}

}

}

4. We defined an anytime algorithm as one that can give its current best answer at any time, but can produce a better answer the more time it has.

Give one example of a practical situation in which an anytime algorithm would be appropriate. Justify your answer.

Give one example of a practical situation in which an anytime algorithm would be inappropriate. Justify your answer.

5. Consider a self-driving car as an example of an intelligent agent. I mean a fully autonomous car, which is capable of operating without any human intervention.

What is an example of a problem to which a self-driving car should seek an optimal solution?

What is an example of a problem to which a self-driving car should seek an approximately optimal solution?

What is an example of a problem to which a self-driving car may be satisfied with a probable solution?

S]: Prove by mathematical induction that for all positive integers n, i+1) n+1 First, show the base case for this induction. Then state and prove the inductive step