2.2 Interval correctness proof

Question 1

Steps to prove correctness

Answer 1

1. Express mathematically (and prove this)
2. Using mathematical definition prove correct set
3. Using mathematical definition prove maximum set

Question 2

What is the mathematical definition for the greedy internal algorithm

Answer 2

Input R

Question 3

How to prove that the mathematical definition for interval scheduling is equal to the psuedo-code

Answer 3

Question 4

How to prove the mathematical defintion for interval scheduling outputs a compatible set

Answer 4

Question 5

How to prove the mathematical defintion for interval scheduling outputs a maximum set (greedy stays ahead method)

Answer 5

Question 6

Steps for greedy stays ahead arguments

Answer 6

Question 7

What is the premise of greedy stays ahead arguments

Answer 7

This proof works by showing that, according to some measure, the greedy algorithm always is at least as far ahead as the optimal solution during each iteration of the algorithm. Once you have established this, you can then use this fact to show that the greedy algorithm must be optimal.

Question 8

What is the premise for exchange arguments

Answer 8

They work by showing that you can iteratively transform any optimal solution into the solution produced by the greedy algorithm without changing the cost of the optimal solution, thereby proving that the greedy solution is optimal.

Question 9

What are the steps for exchange arguments (greedy algorithms)

Answer 9

Question 10

How does the exchange proof work for interval scheduling

Answer 10