- #1

evinda

Gold Member

MHB

- 3,836

- 0

I want to choose if the following sentences are true or false and justify the reason for the choice.

- Polynomial: good, exponential: bad.
- Radix Sort works correctly if we use any right sorting algorithm to sort each digit.
- Given an array $A[1 \dots n]$ from integers, the time that [m] CountingSort [/m] requires is polynomial in relation to the input size $n$.
- Given an array $A[1 \dots n]$ from integers, the time that [m] HeapSort [/m] requires is polynomial in relation to the input size $n$.
- For a Dynamic Programming algorithm, the calculation of all the values with bottom-up is asymptotically faster than the use of recursion and memoization.
- The time of a dynamic algorithm is always $O(P)$ where $P$ is the number of subproblems.
- Each problem that belongs to [m]ΝΡ[/m] is solved in exponential time.

- This sentence is true. But how could we explain why it is actually like that? (Thinking)
- False. We can only use a sorting algorithm, if it is stable.
- Right. The [m] CountingSort [/m] is a linear algorithm.
- False. [m] HeapSort [/m] requires $O(n \log n)$ time.
- False. The calculation of all the values with bottom-up is asymptotically the same as if we use recursion and memoization.

Do I have to explain why the above four properties hold further? If so, what could we add? - How could we deterine if this is true or not?
- The [m] NP [/m] problems cannot be solved in polynomial time, right? But do we know that all these problems are solved in exponential time?