Q74: Interval Scheduling: Another greedy approach

This question is in continuation of previous question of interval scheduling. Please visit Q7 & Q8 before attempting this question.

Question #74: In another greedy approach, consider the following rule for selecting requests to produce optimal set in interval scheduling problem:

For all requests, find the number of other requests which conflict with it. Then, choose the request with least number of conflicts. Then, eliminate the conflicting requests, and again from the remaining requests, choose the one with least number of conflicts & so on.

Options:

1. The above algorithm produces optimal set always as it is able to select maximum requests since requests with more conflicts can be avoided.
2. This algorithm only fails when all requests conflict with equal number of other requests, but such an example cannot be constructed.
3. This algorithm may not produce optimal set in every case, and counter examples can be constructed.
4. This algorithm doesn’t work as greedy algorithms are unsuccessful in solving problems like this.

Solution: Below is the counter example of the above proposed algorithm:

Here 4 is the optimal number of requests that can be scheduled, but they have maximum conflicts. Hence, the correct answer is 3rd one.

Q19: Evaluate postfix expression

Algorithm for evaluating postfix expressions:

Input: Postfix string

Output: Result of the expression

• Scan the Postfix string from left to right.
• Initialize an empty stack.
• A) If the scanned character is an operand, add it to the stack.
• B) If the scanned character is an operator, there will be at least two operands in the stack, otherwise report error. Pop 2 symbols from top of the stack (assuming operator is not unary) and apply the operator onto them. Push the result back.
• Repeat A) and B) until all characters are scanned.
• After all characters are scanned, we will have only one element in the stack. Return topStack.

Question #19: What will be the top of the stack after above algorithm has scanned till second ‘*’ in the postfix string: 123*4112+*+4–+ ?

Options:

1. *
2. 6
3. 5
4. 3

Solution:

Following will be the steps of the algorithm (comma indicates the position till the algorithm has scanned):

1, 23*4112+*+4–+

12, 3*4112+*+4–+

123, *4112+*+4–+

123*, 4112+*+4–+ => 16, 4112+*+4–+

164, 112+*+4–+

1641, 12+*+4–+

16411, 2+*+4–+

164112, +*+4–+

164112+, *+4–+ => 16413, *+4–+

16413*, +4–+ => 1643, +4–+

Hence, the correct answer is option 4.

Q8: Interval Scheduling: An alternative approach

This question is in continuation of previous question of interval scheduling. Please visit Question #7 before attempting this question.

Question #8: Consider a different greedy approach to solve the same problem of finding a subset of maximum size of non-overlapping intervals. This greedy algorithm selects shorter requests first and adds it to the solution if it doesn’t overlap with the existing jobs. The algorithm finally stops until we reach the highest interval job. Which of the following option is correct?

Options:

1. This algorithm produces optimal set as more number of shorter requests can be covered in a given time as compared to longer ones.
2. This algorithm will produce optimal set only if a good mix of shorter and longer requests exists.
3. This algorithm doesn’t produce optimal set in cases when all requests have same size.
4. We can design some counter examples to prove that this algorithm doesn’t work in all cases, even if requests have varying size.

Solution:

Consider the following counter example.

The above mentioned algorithm selects 1 smaller request instead of 2 bigger ones. Hence, this algorithm is not optimal.

Q7: Interval Scheduling Problem

There’s a set of n requests, where each request i represents an interval of time starting and finishing time. A subset of these requests is compatible, if there is no overlap, as only one request can be handled at a given time. The goal is to select a subset of maximum size for scheduling. For example, the figure below has a total of 11 requests and a maximum of 4 requests from it can be scheduled without any conflicts.

Question #7: Consider a greedy solution to the above described interval scheduling problem:

At any time, select the job which is going to start the earliest. Eliminate all the conflicting jobs, and of the remaining ones, again select the job which is going to start the earliest & so on.

Options:

1. This algorithm produces the optimal set in the above example only.
2. This algorithm produces the optimal set always because it is the most intuitive way to solve the problem.
3. This algorithm will produce optimal set always because it always chooses the first job and then next best possible choice, hence it always selects the maximum number of jobs.
4. This algorithm may not produce optimal set in every case.

Solution: Consider the following example where this algorithm fails.

Since we have at least one counter-example, this algorithm is not optimal. Hence, the correct answer is option 4.