Week 9

Question 1

What is the million dollar question?

Answer 1

Record some of the most difficult problems with which mathematicians were grappling at the turn of the second millennium
To elevate in the consciousness of the general public the fact that in mathematics, the frontier is still open and abounds in important unsolved problems
To emphasize the importance of working towards a solution of the deepest, most difficult problems, and to recognize achievement in mathematics of historical magnitude.

Question 2

What is problem 3: P vs NP

Answer 2

If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question.

Question 3

NP-complete vs NP-hard

Answer 3

NP: problems that are slow to solve but fast to check.
NP-Complete: problems in NP for which a fast solution to any
one could give a fast solution to any other.
NP-Hard: problems at least as hard as NP problems — all NP
problems can be reduced (in polynomial time) to them.

Question 4

Does P = NP?

Answer 4

Nobody knows, the possibilities are P != NP or P == NP.
Can we find algorithms in P for problems in NP?

Question 5

Why wont running code on a parallel computer make it quicker?

Answer 5

One must think of a parallel algorithm, and implement that algorithm on a parallel computer.

Question 6

Inherently sequential problems on a parallel machine

Answer 6

It is generally believed that there are inherently sequential
problems that do not admit any significant speed up on a
parallel machine, but so far no problem has been proved
inherently sequential.

Question 7

Whats the asymptotic complexity of insertion sort?

Answer 7

O(n^2)

Question 8

What is the asymptotic complexity of quick sort?

Answer 8

O(nlogn)
P as it is an upper bound of O(n^2)

Question 9

Why does P != NP in parallel

Answer 9

Parallel processors take care of a nondeterministic choice, each processor runs a different ‘guess’
This doesnt make P == NP because an arbitrary size would require an arbitrary number of processors.

Question 10

What is the PRAM model?

Answer 10

Parallel RAM
Combines the synchronous computation model of the ILLIAC-IV with the hierarchical memory model of the connection machine.

Question 11

What does a PRAM consist of?

Answer 11

An unbounded number of processors
An unbounded global memory
A finite program.

Each processor has
A unique processor id
A program counter
An unbounded local memory
A flag indicating whether the processor is active or inactive