'Fast' exponential and Pseudo polynomial algorithms

Question 1

What do we mean by a fast exponential?

Answer 1

Where instead of 2^n runtime, we get a base less than 2. For example, 1.5^n

Question 2

Why is it more important to develop fast algorithms over getting faster hardware?

Answer 2

As due to the nature of exponentials, even hardware that is 20x faster will be faced with the same problem as slower hardware.

A better algorithm on a slower computer will almost certainly have less runtime than a more naïve algorithm on a faster machine.

Question 3

What are some design paradigms we have that can be used to develop faster algorithms?

Answer 3

• Greedy algorithms
• Divide and Conquer
• Dynamic Programming

Question 4

What is the dynamic programming paradigm?

Answer 4

Where we build a solution from the bottom up, using a table to store intermediate results

Question 5

What is the definition of a pseudo polynomial time algorithm?

Answer 5

An algorithm is said to have pseudo polynomial runtime if its runtime is polynomial in the length of the input and the numbers appearing in the input

Question 6

What is a pseudo polynomial (PP) time algorithm for the Knapsack problem?

Answer 6

An algorithm that uses a dynamic approach.

However this is only PP if the max weight and weights of the inputs are polynomial