Job sequencing with dead line

Job sequencing with dead line is yet another greedy approach.

Given a set of jobs with their profits and deadlines, the idea is to find the subset of jobs that will produce maximum profit.

Let us take an example to easily understand how it works. Assume each job takes one unit time for execution.

Consider 4 jobs, with profits 100,10,15,27 respectively and deadline 2,1,2,1 respectively.

Job	1	2	3	4
Profit	100	10	15	27
Deadline	2	1	2	1

job 2 or 4 if taken should be completed in unit time 1. so only one can be taken among them. let us take job 4 as it gives more profit. Now in the unit time 2 we have to take job 1 as it gives more profit.Therefore we can take the best sequence as Maximum deadline in the given set is 2. so within 2 units of time we should identify the jobs if taken,will produce the maximum profit. In 2 units of time only 2 jobs can be completed. So which two jobs?

0               1               2        <-- Time

Job 4

Job 1

Consider one more example for the same problem.

Job	1	2	3	4	5
Profit	20	15	10	5	1
Deadline	2	2	1	3	3

So within 3 units of time we can complete 3 jobs. The best sequence will be

0               1               2                3    <-- Time

Job 1

Job 2

Job 4

and the profit will be 45. If more number of jobs are given then it may be a good idea to arrange the jobs in non increasing order of their profits and then identify the sequence.

Fractional Knapsack

Greedy approach is to try all possible combinations in a sequence to find a optimal solution.

You can imagine the knapsack problem like

"a thief having a bag which can hold up to a certain weight W. He found some N items in a house with each having some value V and weight W. So in order to gain maximum value by accumulating items up to the maximum weight he can carry in his bag, he should identify which item should be taken in which quantity"

Here he can go for a greedy approach by trying all possible sequences. we say this as fractional knapsack because any item can be taken in fractional quantity instead of taking as a whole.

The below example shows how such problems can be solved.

consider maximum weight  of the sack is w=15. There are 5 items (n=5). The weights of the 5 items are 12,1,2,1,4 respectively. Their values are 4,2,2,1,10 respectively. The maximum profit that can be obtained is?

Answer : The idea is to calculate the profit/weight value for each item

Item	1	2	3	4	5
Weight	12	1	2	1	4
Value (profit)	4	2	2	1	10
Profit/weight	0.3	2	1	1	2.5

Now sort according to the profit/weight values in descending order.

this gives

Item	5	2	3	4	1
weight	4	1	2	1	12
P/w	2.5	2	1	1	0.3

This tell us we will get maximum profit if we add items to the sack in the above order until we reach the maximum weight

So now we take each item in the above sorted order until the weight is 15(Maximum)

This goes like this

                    item 5 + item 2 + item 3 + item 4 

weight ->      4       +    1     +    2     +    1     = 8

still we can accumulate a weight of 15-8 = 7. so from last item in the list i.e item 1 we cannot add the whole item as it weighs 12. so,we will take a fraction that weighs 7.

item 1 actual weight is 12. we take 0.58 fractional part of item 1 that weights as 7

so the profit we get will be 0.58 * 4 

  

Therefore, the total profit we get is

10+2+2+1+0.58*4 = 17.32

The maximum profit that can be achieved is 17.32.

To sum up, the idea here is to find the profit by wight ratio that helps in finding how much profit we will get for that weight. so we will add a unit quantity of items until we reach maximum weight or nearer to maximum weight, so that the last item we add will be taken in fraction upto which we can accommodate in the bag.

Dont be wondered after seeing a book dedicated for knapsack solutions. You can find it here

Best,Worst and average case comparisions for Sorting algorithms

Below table gives a quick idea of running times, number of comparisions and swaps in various sorting algorithms. For insertion sort rather than swaps they can be considered as moves. Will update the table with linked list, stack and queue operation details.

Algorithm	Best	Worst	Average	Comparisons		Swaps
				Min	Max	Min	Max
Bubble	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	n(n-)/2
Selection	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	(n-1)
Insertion	Ω(n)	Θ(n2)	Ο(n2)	n(n-)/2	(n-1)	0	n(n-)/2
Quick	Θ(nlogn)	Θ(nlogn)	Ο(n2)
Merge		Θ(nlogn)