Exam Questions

Question 1

How can array top be found, (an element whose neighbor(s) are smaller?

Answer 1

FindTop(array)
Check array borders.
Check the middle element if it is the top.
If not check the half for the greatest neighbor to the middle element.

Question 2

How can you show that a problem is in NP?

Answer 2

Show we can verify problem correctness in P. (polynomial time)

Question 3

How can you prove that a dynamic programming algorithm is correct?

Answer 3

Since you have an optimal way of describing a correct solution for index j and given for 0, this holds by induction. OPT(j).

Question 4

What are the steps for an exchange argument?

Answer 4

1. Assume a Greedy Solution and Another Optimal Solution: Start by considering the solution generated by the greedy algorithm and another arbitrary optimal solution.
2. Find a Difference: Identify a point where the greedy solution differs from the assumed optimal solution.
3. Exchange to Improve: Show that this difference can be “exchanged” or modified in the optimal solution without losing optimality, thereby making the optimal solution more similar to the greedy solution.
4. Iterate the Process: Continue exchanging elements until the arbitrary solution looks exactly like the greedy one, proving that the greedy solution is also optimal.