*(Guest post by Shivam Kumar)*

The class started with the recap of the various techniques we have learnt so far to design algorithms. Like greedy strategy reduces the exponential runtime to polynomial runtime, and divide and conquer strategy reduces larger polynomial runtime to smaller polynomial runtime ( ex. to .

Then the professor started talking about a new algorithm design technique called Dynamic Programming. Dynamic programming is similar to Divide and Conquer since both use recursion but Dynamic programming uses different kind of recursion. In other words, dynamic programming is smarter about solving recursive sub problems.

End of Semester Blues

If we use greedy strategy on this then we choose jobs , and and the total value will be *[whereas the schedule that maximizes the value is picking to get a value of . –Atri]*

Formal Definition of the problem:

- Input: jobs, th job which stand for start time, finish time, and value respectively.
- Output: A schedule where for , and are not conflicting.
- Goal: max .

If forall , then it’s the interval scheduling problem.

*Assume:* All jobs are sorted by the finish time, i.e., . This will be sorted in time.

“*Previous non-conflicting jobs*” ( )

- = largest such that does not conflict with . (I.e. )
- if no such exists

*Ex:* compute values in linear time.

*Optimal Schedule* for will be denoted by and its value by .

**Properties of :**

*Case 1:*

*Question*: What can you say about jobs wrt ?

*Answer:* None of them will be in by the definition of .

**Claim 1:** If , then .

If does not conflict with then will also not conflict.

Recall : jobs are sorted by finish time. This implies that for all , does not conflict with . This is because .

*Proof of Claim 1:* If not, let such that value of $\mathcal {O}’ >$ value of . Let . Now, note that

- is a valid schedule
- Value of value of .

Contradiction the fact that is optimal.

*
Case 2:* does not belong to .

**Claim 2:** If , then .

*Proof idea:* As does not belong to implies that needs to schedule .

For the more **general case**, let and consider the problem on jobs . Then by the same argument as we used to prove Claims 1 and 2, we have:

- If , then , i.e. .
- If , then , i.e. .

Thus, we have shown that

.

## Leave a Reply