CS 477 Exam 1

What is true?
Np-complete problems

show up all the time

For today's computers, which of the following statement is true?

Many computational problems have no efficient solution methods even today

What is true about NP-complete problems

It is easy to check the answer but hard to find it

Which of the following problems can be solved by a greedy algorithm?

Minimum Spanning Tree

Approximation algorithm

gives an answer that is within a factor of optimal

To show Big-Oh using the original definition (no limits)

one has to exhibit a C and an n_0 that makes a certain inequality true.

What does f(n) O(g(n)) mean?

It means f grows more slowly than g or they could have the same order.

For f(n) (g(n)) :

the limit f(n)/g(n) goes to a constant not zero not infinity

What do we do with the characteristic polynomial?

We find the roots.

If a recurrence has a history number of three, how many initial values are needed?

t_0, t_1, t_2

What is the "inhomogeneous part" of a recurrence.

It is the function that remains when all terms that have a t are moved to the left side.

Assertion: Insertion has run time O(n) for input which is already sorted. 

This is not a contradiction. Because the lower bounds speaks to the worst case of an algorithm, and sorted input is not the worst case for insertion sort.

How many comparisons are necessary and sufficient to sort 4 keys?

5

The worst-case run time of quicksort is:

O(n^2)