parallel computing NC

[nonevent99]

I don't seem many practice problems on II.E.2: Parallel Computing. Here's one (below). Does anybody have more practice problems on this subject or distributed computing?

I don't understand the answer to this question, and I hope somebody else will:

The NC problem class consists of problems that
can be solved by a parallel algorithm with polynomially
many processors in time proportional to a
fixed power of the log of their input size. Which of
the following problems is most likely not in class
NC?

a. Sorting a list of records on a particular key.

b. Searching an unordered list for the record
with the largest key.

c. Weighted average computation.

d. Finding the greatest common divisor of two
integers.

(Source: http://www.cis.temple.edu/~ingargio/...ncurrency.html)

[wood]

I didn't quite understood the question. What does the question mean by "power of the log of their input size" ?

Is it: if I have an input size n = 32, the parallel algorithm should run in (log N)^X = 5^X ?? I'm lost on the English interpretation.

[AlbaLed]

"fixed power of the log of their input"

say input is n, then we're looking for something like (log(n))^c where c is a constant

AlbaLed

[AlbaLed]

"fixed power of the log of their input"

say input is n, then we're looking for something like (log(n))^c where c is a constant

AlbaLed