Data Structures for Computer Scientists
Text Processing: Lecture 2
Dr. Franc Brglez, Computer Science, NCSU
11 April 2005
(click here for the course home page)
(Textbook: Data Structures and Algorithms in Java, 3rd Edition)
(Package that made these slides possible: Prosper)
CSC316-001 – Data Structures for Computer Scientists: Text Processing: Lecture 2 – p.1/2
Lecture Outline
greeedy methods
0-1 knapsack problem (exam)
fractional knapsack problem
text compression problem (exam)
task scheduling problem
CSC316-001 – Data Structures for Computer Scientists: Text Processing: Lecture 2 – p.2/2
© 2004 Goodrich, Tamassia Greedy Method and Compression 2
The Greedy Method
Technique (§ 11.4.2)
The greedy method is a general algorithm
design paradigm, built on the following
elements:
configurations: different choices, collections, or
values to find
objective function: a score assigned to
configurations, which we want to either maximize or
minimize
It works best when applied to problems with the
greedy-choice property:
a globally-optimal solution can always be found by a
series of local improvements from a starting
configuration.
The 0/1 knapsack problem
Given a knapsack and a set of n items of some weight and
profit, choose a subset that does not exceed the maximum
weight of W and maximizes the cumulative profit function.
Let wi, pi be the weight and profit, and xi the decision variable
associated with associated with the i-th item. Here, xi = 1 if
item is placed into the knapsack, and xi = 0 otherwise.
The objective (profit) function to be maximized is
Pn
i=1 pixi, subject to Pn
i=1 wixi W
Here, the runtime of ’brute-force’ method is O(2n), prohibitive
as n gets large.
We need to consider ‘greedy solutions strategies’ that may or
may not always lead to a ’globally optimum solutions’.
. – p.1/5
9/21/2008
1
Chapter 2: Algorithm Analysis
• What is an algorithm?
• What to analyze?
• How to estimate the time required for a program?
• How to reduce the running time of a program from
days or years to fractions of a second?
2
• An algorithm is any computational procedure that takes some
value as input and produces some value as output.
• An algorithm is a tool for solving a well-specified
computational problem.
• Example – sorting problem
– Input: A sequence of n numbers:
– Output: A permutation (reordering)
sequence, such that a1’ ≤ a2’ ≤ … ≤ an’.
• Lots of sorting algorithmswill be examined in this course.
What is an algorithm?
3
• Correctness
– An algorithm is said to be correct if for every input
instance, it halts with the correct output.
• Efficiency
– Computers may be fast, but not infinitely fast!
– Memory may be cheap, but not free!
– Computing time and memory space are two
important resources.
Correctness and Efficiency
4
2.1: Mathematical Background
• 4 Definitions:
( ) ( ) 0
(1) ( ) ( ( )) , . .
T N cf N when N n
T N O f N if c n R s t o
£ ³
= $ Î
0 ( ) ( )
(2) ( ) ( ( )) , . .
T N cg N when N n
T N g N if c n R s t o
³ ³
= W $ Î
( ) ( ( )) ( ) ( ( ))
(3) ( ) ( ( ))
T N O N andT N N
T N N iff
h h
h
= =W
=Q
( ) ( ( )) ( ) ( ( ))
(4) ( ) ( ( ))
T N O N and T N N
T N o N if
r r
r
= ¹ W
=
5
2.1: Mathematical Background
• Physical meaning of the definitions and
objectives.
• Example:
(1) N3 = O(N4 )
(2) N4 = W(N3 )
(3) 2N4 = Q(N4 )
(4) N3 = o(N4 )
6
2.1: Mathematical Background
Function Name
c
logN
log2N
N
NlogN
N2
N3
2N
Constant
Logarithmic
Log-squared
Linear
Quadratic
Cubic
Exponential
Typical Growth Rates
9/21/2008
2
7
2.1: Mathematical Background
• Rule 1
( ) ( ) ( ) ( ( ) ( ))
( ) ( ) ( ) max( ( ( )), ( ( )))
( ) ( ( )) ( ) ( ( )),
1 2
1 2
1 2
b T N T N O f N g N
a T N T N O f N O g N
If T N O f N and T N O g N then
´ = ´
+ =
= =
• Examples:
if T1(N) = O(N2) and T2(N)= O(N) then
(a) T1(N) + T2(N) = O(N2)
(b) T1(N)*T2(N) = O(N3)
8
2.1: Mathematical Background
• Rule 2
( ) ( )
( ) is a polynomial of degree k, then
T N Nk
If T N
= Q
• Rule 3
This tells that logarithms grow very slowly
logkN = O(N) for any constant k.
9
2.1: Mathematical Background
• Using L’Hopital’s rule to evaluate:
( )
( )
lim
g N
f N
N®¥
(1) lim = 0; ⇒ f (N) = o(g(N)).
(2) lim = c ¹ 0; ⇒ f (N) = Q(g(N)).
(3) lim = ¥; ⇒ g(N) = o( f (N)).
(4) limoscillates; ⇒no relation.
10
2.1: Mathematical Background
• Example:
= = = ¥
= =
®¥ ®¥ ®¥ 1
lim lim
( )
( )
lim
( ) , ( )
2
3
3 2
N
N
N
g N
f N
f N N g N N
N N N
= ¥
=
=
®¥
®¥
2
6N
lim
2N
3N
lim
N
2
N
11
2.2:Running Time Calculations
• Ways to estimate the running time
• Rule 1: for loops
for (i=0;i
k++
• Rule 2: Nested for loops
for (i=0; i
for (j=0; j
k++
O(N)
O(N2)
12
2.2:Running Time Calculations
• Rule 3: Consecutive Statements
for (i=0;i
k++
for (i=0; i
for (j=0; j
k++
O(N)
O(N2)
9/21/2008
3
13
2.2:Running Time Calculations
• Rule 4: Condition Statement
if (condition)
S1
else
S2
14
2.2. Examples
Sum=0
for (j=0;j
Sum++;
O(N)
15
2.2. Examples
Sum=0
for (j=0;j
for (k=0;k
Sum++;
O(N2)
16
2.2. Examples
Sum=0
for (j=0;j
for (k=0;k
Sum++;
O(N3)
17
2.2. Examples
Sum=0
for (j=0;j
for (k=0;k
Sum++;
O(N2)
18
2.2. Examples
Sum=0
for (j=0;j
for (k=0;k
for (m=0; m
Sum++;
O(N5)
9/21/2008
4
19
2.2. Examples
Sum=0
for (j=0;j
for (k=0;k
if (k%j == 0)
for (m=0; m
Sum++;
O(N4)
20
2.2:Running Time Calculations
• Analysis of factorial
int fact(int n)
{ if (n<=1)
return 1;
else
return (n*fact(n-1));
}
O(N)
21
2.2:Running Time Calculations
• Analysis of Fibonacci number
int Fib (int N)
{
if (N<=1)
return 1;
else
return ( Fib(N-1) + Fib(N-2) );
}
O((5/3)N)
2.3: Example: Max Subsequence
Sum Problem(MSSP)
• Given N (possibly negative) integers A1, A2,
…, AN, find the maximum value of
j
k
k i
A
= Σ
0 0, 1... MSS = if all Ak £ where k = N
• For convenience, assume that
2.3:Example-MSSP
• Example: input -2, 11, -4, 13, -5, -2
• the answer is 20 (A2 through A4)
• 4 possible solutions
2.3:MSSP: Solution1
• Exhaustively tries all possibilities
Running Time:
O(N3)
• int MaxSubSumSol1(const int A[], int N)
{ int ThisSum, MaxSum, i, j, k;
MaxSum = 0;
for (i=0; i
for ( j=i; j
{ ThisSum = 0;
for (k=i; k
ThisSum += A[k];
if (ThisSum > MaxSum) MaxSum = ThisSum;
}
return MaxSum;
}
9/21/2008
5
2.3:MSSP: Solution 2
• Eliminate the last for loop in solution 1
Running Time:
O(N2)
int MaxSubSumSol2(const int A[], int N)
{ int ThisSum, MaxSum, i, j, k;
MaxSum = 0;
for (i=0; i
{ ThisSum = 0;
for ( j=i; j
{ ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
2.3:MSSP: Solution 3
• “divide-and-conquer” strategy
static int MaxSubSum(const int A[], int Left, int Right)
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBoarderSum, MaxRightBoardSum;
int LeftBoarderSum, RightBoardSum;
int center, i;
if ( Left = = Right) /*Base Case*/
if (A[Left] > 0) return A[Left];
else return (0);
Center = (Left + right)/2;
MaxLeftSum = MaxSubSum(A, Left, Center);
MaxRightSum=MaxSubSum(A, Center +1, Right);
MaxLeftBoardSum = 0; LeftBoardSum = 0;
2.3:MSSP: Solution 3
for (i= Center; i>= Left; i--)
{ LeftBoarderSum += A[i];
if (LeftBoarderSum > MaxLeftBoarderSum)
MaxLeftBoarderSum = LeftBoarderSum;
}
for (i= Center+1; i>= Right; i++)
{ RightBoarderSum += A[i];
if (RightBoarderSum>MaxRightBoarderSum)
MaxRightBoarderSum = RightBoarderSum;
}
return Max3(MaxLeftSum, MaxRightSum,
MaxLeftBoarderSum+MaxLeftBoarderSum);
}
int MaxSubSumSol3(const int A[], int N)
{ return (MaxSubSum(A, 0, N-1); }
Running
Time:
O(NlogN)
2.3:MSSP: Solution 4
• int MaxSubSumSol4(const int A[], int N)
{ int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for ( j=0; j
{ ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
Running
Time:
O(N)
29
2.3:MSSP: Running Times
(in second)
Algorithm 1 2 3 4
Time O(N3) O(N2) O(NlogN) O(N)
Input Size N=10
N=100
N=1,000
N=10,000
N=100,000
0.00103
0.47015
448.77
NA
NA
0.00045
0.01112
1.12330
111.13
NA
0.00066
0.00486
0.05843
0.68631
8.01113
0.00034
0.00063
0.00333
0.03042
0.29832
30
2.3:MSSP: Running Times
(in second)
9/21/2008
6
31
2.3:MSSP: Running Times
(in second)
32
2.3:Binary Search
• Analysis of Binary Search
while (low <= high)
{ mid = (low + high) / 2;
if (x == a [mid])
return (mid);
else if (x < a [mid])
high = mid - 1;
else
low = mid + 1;
}
O(logN)
33
2.4 Check Your Analysis
• Check with actual running time
• Compute T(N)/f(N) for a range of N
34
2.4 Check Your Analysis
N CPU time T/N2 T/N3 T/N2logN
100
200
300
400
500
022
056
118
207
318
0.002200
0.001400
0.001311
0.001294
0.001272
0.00000220
0.00000700
0.00000430
0.00000324
0.00000254
0.0004777
0.0002642
0.0002299
0.0002159
0.0002047
600
1000
466
1362
0.001294
0.001362
0.00000217
0.00000132
0.0002024
0.0001972
1500
2000
4000
3240
5949
25720
0.001440
0.001482
0.001608
0.00000096
0.00000074
0.00000040
0.0001969
0.0001947
0.0001938
3.1 Abstract Data Types
3.1.1 Modularity
· A logical unit to do a specific job.
· Advantages:
§ Easier to debug
§ Easier for several people to work on a modular program simultaneously
§ Place certain dependencies in only one routine, making changes easier
3.1.2 Abstract data type (ADT)
· a set of operations
· mathematical abstractions
· not mention how the set of operations is implemented in an ADT's definition.
· Basic idea
§ The implementation of the operations is written once in the program, and any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate function.
§ If for some reason implementation details need to be changed, it should be easy to do so by merely changing the routines that perform the ADT operations.
3.2 The List ADT
· Operations:
§ PrintList
§ MakeEmpty
§ Find
§ Insert
§ Delete
§ FindKth
3.2.1 Simple Array Implementation of Lists
· require a high estimate of maximum size of list (waste space)
· Processing time
§ PrintList and Find: in linear time
§ FindKth: takes constant time
§ Insertion and deletion: slow, worst case is O(N)
· Simple arrays are generally not used to implement lists because:
§ Slow in insertions and deletions
§ List size must be known in advance
3.2.2 Linked Lists
Fig. 3.1
· consists of a series of structures, which is not necessarily adjacent in memory.
· Each structure contains the element and a pointer to a structure containing its successor.
Fig. 3.2
· Processing time
§ PrintList(L), Find(L, key): only pass a pointer to the first element in the list and then traverse the list. (linear time)
§ FindKth: not as efficient as an array implementation, takes O(i) time.
§ Delete: in one pointer change. (Fig. 3.3 )
§ Insert: require a malloc call and two pointer maneuvers. (Fig. 3.4 )
3.2.3 Programming Details
· Problems associated with deletions
§ Deleting from the front of the list changes the start of the list; careless coding will lose the list.
§ Require keeping track of the cell before the one that to be deleted.
· Header
§ A sentinel code
Fig. 3.5
· FindPrevious
§ It will return the predeccessor of the cell to be deleted.
Fig. 3.6 - 3. 13
· Short-circuited operation
§ Line 2 in Fig. 3.10
§ If the first half of the and is false, the result is automatically false and the second half is not executed.
· Insertion (Fig. 3.13)
§ Insert the new element after the position implied by P.
§ Insertion of the new element before the element currently in position P requires knowledge of the element before position P.
· The list is passed to the Insert and IsLast routines, even though it is never used because:
§ Another implementation might need this formation
§ Not passing the list would defeat the idea of using ADTs.
· Processing time
§ All routines (except Find and FindPrevious) take O(1) time because in all cases only a fixed number of instructions are performed.
§ Find, FindPrevious: the running time is O(N) in the worse case, because the entire list might need to be traversed if the element either is not found or is last in the list.
3.2.4 Common Errors
· Failure to initialize the variable
· Illegal indirection
(Therefore, whenever you do an indirection, you must make sure that the pointer is not NULL.)
· When and when not to use malloc to get a new cell.
· Free memory of the deleted cell
· Incorrect way to delete a list
Fig. 3.14
Fig. 3.15
(A temporary variable may be needed to set to the cell to be disposed of, because after the pointer moves are finished, you may not have a reference to it.)
· malloc(sizeof(PtrToNode)) is legal, but it doesn't allocate enough space for a structure. It allocates space only for a pointer.
3.2.5 Doubly Linked Lists
Fig. 3.16
· It is convenient to traverse lists backward.
· It requires extra links. Thus, require more space and double the cost of insertion.
· It simplifies deletion, because no longer have to refer to a key by using a pointer to the previous cell.
3.2.6 Circularly Linked Lists
Fig. 3.17
3.2.7 Examples
3.2.7.1 The Polynomial ADT
·
Define an abstract data type for single-variable polynomials (with nonnegative exponents) by using a list.
 |
Define an abstract data type for single-variable polynomials (with nonnegative exponents) by using a list.
· Implemented by a simple array
§ If most of the coefficients Aj are nonzero, a simple array can be used to store them.
Fig. 3.18 - Fig. 3.21
§ The running time of the multiplication routine is proportional to the product of the degree of the two input polynomials.
§ This is adequate for dense polynomials, where most of the terms are present.
· Implemented by a singly linked list
Fig. 3.22 - Fig. 3.23
§ Each term in the polynomial is contained in one cell, and the cells are sorted in decreasing order of exponents.
3.2.7.2 Radix Sort
· Bucket sort
§ Sort N integers in the range 1 to M (or 0 to M-1)
§ Algorithm:
(1) Initialize an array called Count, of size M, to zero.
(2) When Ai is read, increment (by 1) Count[Ai].
(3) After all the input is read, scan the Count array, printing out a representation of the sorted list.
§ This algorithm takes O(M+N)
· Radix sort is a generalization of bucket sort.
· It uses several passes of bucket sort.
· Algorithm
§ Perform bucket sort by the least significant "digit" first.
§ Then the next least significant digit and so on.
· More than one number could fall into the same bucket and these numbers could be different, so we keep them in a list.
Fig. 3.24,-3.26
· Failure would occur if two numbers came out of the same bucket in the wrong order. But the previous passes ensure that when several numbers enter a bucket, they enter in sorted order.
· The running time is O(P(N + B)).
· This algorithm would have the overhead of maintaining linked lists.
3.2.7.3 Multilists
· Example: 40,000 students and 2,500 courses needs to be able to generate the following two types of reports:
§ List the registration for each class.
§ List the classes that each student is registered for.
· Implemented by a 2-dimensional array
§ Such as array would have 100 million entries.
§ If the average students registers for about 3 courses, only 120,000 of these entries (or about 0.1%) would actually have meaningful data.
· Implemented by multilists
§ A list for each class containing the students in the class.
§ A list for each student containing the classes the student is registered for.
§ Combine these two lists into one.
§ All lists use a header and are circular.
Fig. 2.27
· Using a circular list saves space but does so at the expense of time.
· Each of the (nonheader) cells could have pointers directly back to the student and class header. This would double the space requirement but would simplify and speed the implementation.
3.2.8 Cursor Implementation of Linked Lists
· To simulate the following two important features of a pointer implementation of linked lists:
(1) The data are stored in a collection of structures. Each structure contains data and a pointer to the next structure.
(2) A new structure can be obtained from the system's global memory by a call to malloc and released by a call to free.
· To simulate feature 1:
To have a global array of structures. For any cell in the array, its array index can be used in placed of an address.
· To simulate feature 2:
To keep a freelist of cells that are not in any list.
Fig. 3.28 - Fig. 3.36
· The interface for the cursor implementation is identical to the pointer implementation.
· The implementation is transparent to the user.
· If relatively few Finds are performed, the cursor implementation could be significant faster because of the lack of memory routines.
3.3 The Stack ADT
3.3.1 Stack Model
· A stack is a list with the restriction that insertions and deletions can be performed in only one position.
· Fundamental operations:
§ Pop
§ Top
§ Push
· Last in, first out (LIFO)
Fig. 3.37-3.38
3.3.2 Implementation of Stacks
3.3.2.1 Linked List Implementation
Fig. 3.39 - Fig. 3.44
· Use a singly linked list.
· The front of the list serves as the top of the stack.
· All the operations take constant time, because nowhere in any of the routines is there even a reference to the size of the stack (except for emptiness).
· Drawback
§ Calls to malloc and free are expensive
· Some of this can be avoided by using a second stack to hold the cells dropped from the first stack. When new cells are needed, the second stack is checked first.
3.3.2.2 Array Implementation of Stacks
· Need to declare an array size ahead of time.
· Associated with each stack is TopOfStack, which is -1 for an empty stack.
· To push
(1) Increment TopOfStack by 1.
(2) Set Stack[TopOfStack] = X
· To Pop
(1) Set return value to Stack[TopOfStack]
(2) Decrement TopOfStack by 1.
· These operations are performed in very fast constant time.
Fig. 3.45-3.53
3.3.3 Applications
3.3.3.1 Balancing Symbols
· To check that every right brace, bracket, and parentheses must correspond to its left counterpart.
· Algorithm
(1) Make an empty stack.
(2) Read characters until end of file.
i. If the character is an opening symbol, push it onto the stack.
ii. If it is a closing symbol, then if the stack is empty, report an error.
iii. Otherwise, pop the stack.
If the symbol popped is not the corresponding opening symbol, then report an error.
(3) At end of file, if the stack is not empty, report an error.
3.3.3.2 Postfix Expressions
· Postfix (reverse Polish) expression evaluation:
§ When a number is seen, it is pushed onto the stack.
§ When an operator is seen, the operator is applied to the 2 numbers that are popped from the stack. The result is pushed onto the stack.
· Example: To evaluate 6 5 2 3 + 8 * + 3 + *
· No need to know any precedence rules in postfix expression evaluation.
· The time to evaluate a postfix expression is O(N), because processing each element in the input consists of stack operations and thus takes constant time.
3.3.3.3 Infix to Postfix Conversion
· Algorithm
(1) Initialize a stack to empty.
(2) Read a symbol
(3) If read the end of input, pop the stack until it is empty, write symbols onto the output.
(4) If it is an operand, place onto the output.
(5) If it is an operator, push onto the stack.
(5.1) If it is a right parenthesis, then pop the stack, write symbols, until a left parenthesis is encountered.
(5.2) If it is any other symbol ('+', '*', '(' ), pop entries from the stack until an entry of lower priority is found. When the popping is done, push the operator onto the stack.
(6) Goto step (2).
Notes:
§ We never remove '(' from the stack except when processing a ')'.
§ '+' has lowest priority and '(' highest.
· Example: To convert a + b * c + (d * e + f) * g
· This conversion requires only O(N) time and works in one pass through the input.
3.3.3.4 Function Calls
· Activation record (stack frame): information saved during function call.
· Tail recursion
Fig. 3.54
§ Refer to a recursive call at the last line.
§ An example of a bad use of recursion.
· Activation records are typically large because of all the information they contain, so the program in Fig. 3.54 is likely to run out of stack space if the list is very long.
· In languages and systems that do not check for stack overflow, your program will crash without an explicit explanation. In these systems, strange things may happen when your stack gets too big, because your stack will run into part of your program.
· Tail recursion can be mechanically eliminated by changing the recursive call to a goto preceded by one assignment per function argument.
Fig. 3.55
· Although nonrecursive programs are certainly generally faster than equivalent recursive programs, the speed advantage rarely justifies the lack of clarity that results from removing the recursion.
3.4 The Queue ADT
· Insertion is done at one end, whereas deletion is performed at the other end.
3.4.1 Queue Model
Fig. 3.56
· Basic operations:
§ Enqueue
§ Dequeue
3.4.2 Array Implementation of Queues
· Front, Rear: represent the ends of the queue.
· Size: to keep track of the number of elements that are actually in the queue.
· To Enqueue an element X:
(1) Increment Size and Rear.
(2) Set Queue[Rear] = X.
· To Dequeue an element:
(1) Set the return value to Queue[Front].
(2) Decrement Size.
(3) Increment Front.
· Circular array implementation
§ If increment either Rear or Front causes it to go past the array, the value is reset to the first position in the array.
§ To check the queue for emptiness, because a Dequeue when the queue is empty will return an undefined value.
§ If we do not use an entry to keep track of size, we can rely on the base case that when the queue is empty, Rear = Front - 1.
Fig. 3.57 - Fig. 3.60
3.4.3 Applications of Queues
· Print jobs
· Computer networks
· Operating systems
· Real-life waiting lines
Lecture #7:
0.0.1 Greedy Methods:(Chapter 16)
We now take up the concept of the greedy paradigm. We will consider several
illustrative examples.
• Making Change
Suppose we have the following coins: Dollar(100 cents), Quarter(25 cents),
Dime(10 cents), Nickel(5 cents), and penny(1 cent). When we to pay some
one an amount (say $2.89=289 cents), we do this with little thinking in a
way that in some cases uses the smallest number of coins. [Assume that
we have sufficient quantities of each denomination). And the way we do it
is known as the greedy method. We use 2 dollar coins, three quarters,
one dime, and four pennies. If there was a half-dollar (=50 cents) coin,
there are two possibilities — the greedy one is 2 dollar coins, one half-dollar
coin, one quarter, one dime, and four pennies. So at each step, we use
the largest denomination as many times as possible without going over
the total. The decision made at each step is never revoked. These are
some of the characteristics of greedy methods. It does not provide the
correct solution to every problem! For example, convince yourself
that when the available coins are: {50,25,20,10,5,1), this method does not
always work.
But it is useful in some instances. In some cases, there may be more than
one way to solve using greedy ideas. Some may work while others may
not.
• Activity Selection Problem (Chapter 16.2)
Suppose we have a set S = {1, 2, ..., n} of n activities that wish to use a
common resource. Activity i needs the resource in the time interval [si, fi) with
fi > si. Two activities i and j are said to be compatible if their intervals do not
overlap — that is if either si ≥ fj or sj ≥ fi. The activity selection problem is to
select the largest set of mutually compatible activities. Here is the pesuodcode
from the book: s and f are arrays. Assume that the activities are numbered so
that f1 ≤ f2 ≤ ... ≤ fn.
GREEDY-ACTIVITY-SELECTOR(s, f)
n ←− length(s)
A ←− {1}
j ←− 1
for i = 2 to n
do if si ≥ fj
1
then A ←− A ∪ {i}
j ←− i
return A
I will call the above Algorithm II.
Proof of Algorithm I (not the above algorithm!)
Clearly the set A returned by the Algorithm I is "feasible" — meaning that
the intervals corresponding to activities in A do not overlap. What remains to
be shown is that among such sets A has the largest size (such sets are called
"optimal"). It is the proof of this that we do now.
1. We need to show that 1 should belong to some optimal set.
Proof: Suppose 1 does not belong to any optimal set. Let S be some
optimal set (the existence of such a set is not in question since there are
only finitely many feasible sets). Let k = min[j : j ∈ S]. This is under
the numbering as per an ordering that satisfies f1 ≤ f2 ≤ ... ≤ fn. Then
sj ≥ fk ≥ f1 for all j ∈ S − {k}. Moreover, there is no overlap in the
intervals corresponding to activities in S−{k}. Thus S′ = S−{k}+{1} is
also feasible and |S′| = |S| and hence S′ is also optimal. This contradicts
the supposition that 1 doe snot belong to any optimal set.
2. Since 1 is a subset of some optimal set, eliminating any activity whose
interval overlaps with 1 does not exclude such optimal sets. Activity i = 1
does not overlap with 1 implies that
si ≥ f1 or
s1 ≥ fi
Since we know that fi ≥ f1 it follows that fi ≥ s1. Hence i = 1does not
conflict with 1 implies that si ≥ f1 and hence this step of the algorithm
is correct.
3. Let T represent the set of activities which does not include activity 1 or
any activity whose interval overlaps with that of 1. No activity in T can
conflict with 1. Thus, an optimal set S that includes 1 has the property
(by induction hypothesis) that S − {1} is optimal for T. And the above
algorithm applied to T clearly produces S − {1}. Hence the Algorithm
I "works". Now show that Algorithm II produces the same outcome as
Algorithm I.
{23}’ Alternate Proof of Algorithm II: Step 1 is the same. Now suppose that
the algorithm correctly produces A of some step — meaning that this A is
a subset of some optimal set. Then excluding any activity that conflicts
with any activity in A will not exclude such optimal sets. It is easy to
verify that an activity (that has not already been excluded) i /∈ A conflicts
with some activity in A iff si < fj where j is the last activity added to A.
Thus the algorithm’s next addtion is also correct by reasoning similar to
that in step 1.
2
• Huffman Codes (Chapter 16.3)
HUFFMAN(C)
1. n ← |C|
2. Q ← C
3. for i ← 1 to n − 1
4. do allocate a new node z
5. left[z] ← x ←EXTRACT-MIN(Q)
6. right[z] ← y ←EXTRACT-MIN(Q)
7. f[z] ← f[x] + f[y]
8. INSERT(Q, z)
9. return EXTRACT-MIN(Q)
• Minimum/Maximum Spanning Tree Problem
• Dijkstra’s Algorithm in Shortest Paths
The discussion of the last two problems also comes under the category Graph
Algorithms.
• Several Scheduling Problems
Example 1 A single server (such as a processor, a cashier in a bank, etc.)
has n customers to serve. The service time required by each customer is known
in advance: customer i will require ti time units (1 ≤ i ≤ n ). We want to
minimize the average time a customer spends in the system.
Since the number of customers is fixed, this is equivalent to minimizing the
total time spent by all customers. So we want to minimize n
i=1 Ci where
Ci is the time at which customer i completes service. Suppose n = 3 and
t1 = 3; t2 = 10; t3 = 5 the table below summarizes the values for all the ways in
which we could render the service:
Order n
i=1 Ci
1, 2, 3 34
1, 3, 2 29 Optimal
2, 3, 1 43
2, 1, 3 41
3, 1, 2 31
3, 2, 1 38
Let P = p1p2...pn be a permutation of {1, 2, ..., n} and let si = tpi . If
customers are served in the order corresponding to P,
n
i=1
Ci = s1 + (s1 + s2) + ... + (s1 + ...sn)
=
n
k=1
(n − k + 1)sk
3
This is minimized by the permutation that has s1 ≤ s2 ≤ ... ≤ sn. This
corresponds to the greedy strategy of processing the customer with the least
time required first.
Example 2 We have n jobs to execute, each one of which takes a unit time to
process. At any time instant we can do only one job. Doing job i earns a profit
pi. The deadline for job i is di.
Suppose n = 4; p = [50, 10, 15, 30]; d = [2, 1, 2, 1]. It should be clear that we
can process no more than two jobs by their respective deadlines. The set of
feasible sequences are:
Sequence Profit
1 50
2 10
3 15
4 30
1, 3 65
2, 1 60
2, 3 25
3, 1 65
4, 1 80 optimal
4, 3 45
A set of jobs is feasible if there is a sequence that is feasible for this set. The
greedy method chooses jobs in decreasing order of their profits. If the inclusion
of the next job does not affect feasibility, we do so. Else we do not include the
last job that was considered. We need to show that this algorithm provides an
optimal solution. We also need to consider the implementation that is most
efficient. Some results given below help in this.
Lemma 3 Let S be a set of jobs. Suppose that the jobs are numbered so that
d1 ≤ d2 ≤ d3 ≤ .... (This is known as the Earliest Due Date order — EDD for
short). The set S is feasible if and only if the sequence {1, 2, ..., } is feasible.
Proof. The ”if” part is clear. To show that ”only if” part we use proof by
contradiction. Suppose that the sequence {1, 2, ..., } is NOT feasible. Let the
first job in the sequence that misses its deadline be job r. This means that the
deadline for job r, dr ≤ r − 1. Since our sequence is EDD, the first r jobs all
have deadlines ≤ (r − 1). However, these jobs are scheduled, at least one will
not meet its deadline. Hence there is no feasible sequence for this set and hence
for S.
This is good news — since we don’t have to check all the permutations of this
set to check feasibility.
Theorem 4 The greedy algorithms solves the problem.
4
Proof. Suppose the greedy algorithms chooses the set I of jobs and suppose
the set J is optimal. We want to show that the two have same profit and
hence I is also optimal. Suppose that corresponding sequences are SJ and SI
respectively. These two sequences may have gaps — time slots where there are
no jobs. By rearranging these sequences, we can get sequences S′j and S′
I in
which the jobs common to the sets J and I are scheduled in the same time slots
as shown below:
p y q x r
r s t p u v q w
x y p r q
u s t p r v q w
SI
SJ
S'I
S'J
These sequences are still feasible since both the previous ones were. This
performs at most one exchange for each job that is common to the two sets. If the
new sequences are not the same we may have one of the following possibilities:
• There is a job a in S′
I opposite a gap in S′
J : This means that a /∈ J. But
J ∪ {a} is also feasible because we can put a in this gap and this would
be more profitable than J˙ But this can not happen since J is optimal.
• There is a job b in S′
J opposite a gap in S′
I : This means that b /∈ I. But
I ∪ {b} is also feasible because we can put b in this gap. This implies
that the greedy algorithm would have included the job b as well. This is
impossible since b was not included in the greedy schedule.
The only remaining possibility is that some job b is scheduled in S′
I opposite
some job a in S′
J . In this case b /∈ S′
J and a /∈ S′
I . There are three
cases to consider:
1. pa > pb: One could substitute a by b in J and we would get a higher
profit — contradiction to optimality of J.
2. pb > pa: The greedy algorithm would have selected b before selecting
a — contradicting the outcome of greedy method.
5
3. pa = pb: In this case the values are the same
Hence, both schedules have equal values jobs in each time slot and
hence the total values are equal. Hence I is also optimal.
The following lemma helps in faster implementation of the greedy algorithm.
Lemma 5 A set J of n jobs is feasible if and only if we can construct a feasible
sequence as follows: Start with an empty schedule with n time slots. For each
job i ∈ J, schedule i at time slot t, where t is the largest integer such that
1 ≤ t ≤ min[n, di] and time slot t is free.
In other words, schedule the next job as late as possible without violating its
deadline. If a job can not be scheduled before its deadline under this algorithm,
then there is no feasible sequence for the set J.
Proof. The ”if” is obvious. For the ”only if” part: Since there are only n
jobs in all, no job needs to be scheduled later than time slot n. Thus, we can
reset the deadlines to min[n, di] for job i. When we try to add a job, there is
always a ”gap”. Suppose we are unable to add a job whose deadline is d. This
happens because all slots form t = 1 to t = r (where r = min[n, d]) are taken
by previous jobs. Let s > r be the smallest integer such that time slot t = s is
free. Thus the schedule built up so far includes s − 1 jobs whose deadlines are
earlier than s, no job with deadline s, and possibly others with deadlines later
than s. The job we are trying to add also has a deadline less than s. Thus, J
includes at least s jobs with deadlines less than or equal to s −1. Whatever be
the schedule, at least one of these will be late.
This lemma suggests that we should take up the jobs in decreasing order of
their profit values and schedule each job one by one to positions in a sequence
of length n. For any position t define nt = max{k ≤ t :position k is free}. We
want the next job i to be assigned to position nt if t = min[n, di]. We need
some other data structures to do this right. We will take this up later when we
do minimum spanning trees in Graph algorithms.
Example 6 We have n jobs to execute. We can do only one job at any time
instant . Job i requires a duration ti. The deadline for job i is di. We want to
maximize the number of jobs done on or before their deadlines.
Let the jobs be ordered in EDD order — numbered so that d1 ≤ d2 ≤ d3 ≤ ....
≤ dn. Define sets Ik = {1, 2, ..., k} with this numbering of jobs. If In is feasible,
then it, clearly, is the solution. If not, let k1 be the minimum k for which Ik is
not feasible. At least one of these jobs can not be included in the final solution.
The most promising candidate is again found by the greedy method: it is the
job k2 in the set Ik for which tk2 is the largest. Job k2 is removed from the list
and we repeat this process.
Proof. Suppose the optimal solution has the set J of jobs and let k2 ∈ I =
J ∩ Ik. So our algorithm removed job k2 but the optimal solution has included
that job. Clearly, I = Ik since this set of jobs is not feasible and hence any
6
set that properly contains this set can not be feasible as well. Let l ∈ Ik\I.
Consider the set J′ = J ∪ {l}\{k2}. Since tl ≤ tk2 , the set J′ is also feasible.
• A Loading Problem
Example 7 Consider a train that travels from point 1 to point n with intermediate
stops at points 2, 3, ..., (n − 1). We have pi,j packages that need to be
delivered from point i to point j where 1 ≤ i < j ≤ n. Packages have the
same size. The maximum number at any point in the train must not exceed its
capacity C. We want to deliver as many packages as possible.
For example, the following table gives data for n = 6 with C = 8:
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 2 2 2
2 4 1 2 2
3 4 4 1
4 2 2
5 3
6
We use the greedy idea twice in the solution of this problem. We describe
the algorithm informally. At point 1 load packages in increasing order of their
destination till capacity is reached. When the train arrives at point 2, (conceptually)
unload and reload according to the same principle as above. If some
packages that were picked up at point 1 get left at point 2, do not load them at
point 1 in the first place! Here is the evolution of the algorithm for this example:
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 2
2
3
4
5
6
After Loading at Point 1
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3
4
5
6
After Loading at Point 2
7
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
4
4 3
After Loading at Point 3
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3 4 3
4 2 2
5
6
After Loading at Point 4
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3 4 3
4 2 2
5 3
6
After Loading at Point 5
I will leave the proof to you as an exercise.
• Two Machine Scheduling Problem (S. Johnson)
Example 8 Consider the following scheduling problem: We have two machines
A and B (they perform different operations) and a set {1, 2, ..., n} of n jobs. All
jobs are processed by machine A first and then by machine B. Job i requires
a duration Ai on machine A and Bi on machine B. We wish to minimize the
time required to process all jobs and the corresponding schedule. S.M. Johnson
gave a greedy algorithms to solve this problem.
• Johnson Algorithm:
Partition the jobs into two sets S1 = {i : Ai < Bi} and S2 = {i : Ai ≥ Bi}.
Schedule the jobs in S1 first in increasing order of their Ai values and then
the jobs in S2 in decreasing order of their Bi values. Note that this can
8
also be viewed as looking for the smallest of all durations and if this is an
A type schedule the job first and if it is a B type schedule the job last. In
this sense, this is a greedy method. The effort is Θ(n lg n). To prove that
this produces an optimal schedule, we use proof by contradiction.
Proof. Suppose this algorithm does not work for some problem instance.
Let the optimal schedule for this be S. Since the algorithm does not work, there
are two consecutive jobs say j followed by i in S such that one of the following
conditions holds:
1. j ∈ S2 and i ∈ S1
2. j ∈ S1; i ∈ S1 and Aj > Ai
3. j ∈ S2; i ∈ S2 and Bj < Bi
It suffices to show that in any of these cases, if we exchange the positions
of these jobs, we get a schedule that is at least as good as S. By repeated
applications of these exchanges we get a schedule that would be obtained by the
algorithm. This would be a contradiction to the statement that the algorithm
does not work. See below:
S
a1 a2
S'
a1 a2
j i
j i
i j
i j
b1 b2
b1
b'2
α
γ
β
δ
It suffices to show that b′
2 ≤ b2 to show that the schedule S′ is at least as
good as schedule S. Please note that the jobs after i in S can start at the same
time or earlier on machine B in S′ in this case. Let the job before j in S be k
9
and the job after i be m.
α = max[b1, (Aj + a1)]
β = max[a2, (Bj + α)]
b2 = Bi + β
= Bi + max[a2,Bj + max[b1, (Aj + a1)]]
= Bi + max[a2,Bj + b1,Bj + Aj + a1]
max[a1 + Aj + Ai + Bi,Bj + Bi + b1,Bj + Bi + Aj + a1]
γ = max[b1, (Ai + a1)]
δ = max[a2, (Bi + γ)]
b′
2 = Bj + δ
= Bj + max[a2,Bi + max[b1, (Ai + a1)]]
= Bj + max[a2,Bi + b1,Bi + Ai + a1]
= max[a1 + Aj + Ai + Bj ,Bi + Bj + b1,Bi + Bj + Ai + a1]
The middle terms in b2 and b′
2 are the same. Now we consider each of our
cases above:
1. First term in b2 = a1 +Aj +Ai +Bi ≥ Bi +Bj +Ai +a = Third term in
b′
2 because j ∈ S2 =⇒ Aj ≥ Bj
Third term in b2 = Bj + Bi + Aj + a1 ≥ a1 + Aj + Ai + Bj = First term
in b′
2 because i ∈ S1 =⇒ Ai < Bi.
Hence b2 ≥ b′
2 in this case.
2. Third term in b2 = Bj + Bi + Aj + a1 > Bi + Bj + Ai + a = Third term
in b′
2 because Aj > Ai
Third term in b2 = Bj + Bi + Aj + a1 > a1 + Aj + Ai + Bj = First term
in b′
2 because Ai < Bi since i ∈ S1
Hence b2 ≥ b′
2 in this case.
3. First term in b2 = a1 +Aj +Ai +Bi ≥ Bi +Bj +Ai +a = Third term in
b′
2 because j ∈ S2 =⇒ Aj ≥ Bj
First term in b2 = a1 + Aj + Ai + Bi > a1 + Aj + Ai + Bj = First term
in b′
2 because Bj < Bi
Hence b2 ≥ b′
2 in this case.
By a similar argument, we can also show that if there are two possible
schedules that could be obtained by the algorithm, they are equally good.
This completes the proof that the algorithm works.
We will revisit greedy algorithms when we discuss graph algorithms.
10
Lecture #7:
0.0.1 Greedy Methods:(Chapter 16)
We now take up the concept of the greedy paradigm. We will consider several
illustrative examples.
• Making Change
Suppose we have the following coins: Dollar(100 cents), Quarter(25 cents),
Dime(10 cents), Nickel(5 cents), and penny(1 cent). When we to pay some
one an amount (say $2.89=289 cents), we do this with little thinking in a
way that in some cases uses the smallest number of coins. [Assume that
we have sufficient quantities of each denomination). And the way we do it
is known as the greedy method. We use 2 dollar coins, three quarters,
one dime, and four pennies. If there was a half-dollar (=50 cents) coin,
there are two possibilities — the greedy one is 2 dollar coins, one half-dollar
coin, one quarter, one dime, and four pennies. So at each step, we use
the largest denomination as many times as possible without going over
the total. The decision made at each step is never revoked. These are
some of the characteristics of greedy methods. It does not provide the
correct solution to every problem! For example, convince yourself
that when the available coins are: {50,25,20,10,5,1), this method does not
always work.
But it is useful in some instances. In some cases, there may be more than
one way to solve using greedy ideas. Some may work while others may
not.
• Activity Selection Problem (Chapter 16.2)
Suppose we have a set S = {1, 2, ..., n} of n activities that wish to use a
common resource. Activity i needs the resource in the time interval [si, fi) with
fi > si. Two activities i and j are said to be compatible if their intervals do not
overlap — that is if either si ≥ fj or sj ≥ fi. The activity selection problem is to
select the largest set of mutually compatible activities. Here is the pesuodcode
from the book: s and f are arrays. Assume that the activities are numbered so
that f1 ≤ f2 ≤ ... ≤ fn.
GREEDY-ACTIVITY-SELECTOR(s, f)
n ←− length(s)
A ←− {1}
j ←− 1
for i = 2 to n
do if si ≥ fj
1
then A ←− A ∪ {i}
j ←− i
return A
I will call the above Algorithm II.
Proof of Algorithm I (not the above algorithm!)
Clearly the set A returned by the Algorithm I is "feasible" — meaning that
the intervals corresponding to activities in A do not overlap. What remains to
be shown is that among such sets A has the largest size (such sets are called
"optimal"). It is the proof of this that we do now.
1. We need to show that 1 should belong to some optimal set.
Proof: Suppose 1 does not belong to any optimal set. Let S be some
optimal set (the existence of such a set is not in question since there are
only finitely many feasible sets). Let k = min[j : j ∈ S]. This is under
the numbering as per an ordering that satisfies f1 ≤ f2 ≤ ... ≤ fn. Then
sj ≥ fk ≥ f1 for all j ∈ S − {k}. Moreover, there is no overlap in the
intervals corresponding to activities in S−{k}. Thus S′ = S−{k}+{1} is
also feasible and |S′| = |S| and hence S′ is also optimal. This contradicts
the supposition that 1 doe snot belong to any optimal set.
2. Since 1 is a subset of some optimal set, eliminating any activity whose
interval overlaps with 1 does not exclude such optimal sets. Activity i = 1
does not overlap with 1 implies that
si ≥ f1 or
s1 ≥ fi
Since we know that fi ≥ f1 it follows that fi ≥ s1. Hence i = 1does not
conflict with 1 implies that si ≥ f1 and hence this step of the algorithm
is correct.
3. Let T represent the set of activities which does not include activity 1 or
any activity whose interval overlaps with that of 1. No activity in T can
conflict with 1. Thus, an optimal set S that includes 1 has the property
(by induction hypothesis) that S − {1} is optimal for T. And the above
algorithm applied to T clearly produces S − {1}. Hence the Algorithm
I "works". Now show that Algorithm II produces the same outcome as
Algorithm I.
{23}’ Alternate Proof of Algorithm II: Step 1 is the same. Now suppose that
the algorithm correctly produces A of some step — meaning that this A is
a subset of some optimal set. Then excluding any activity that conflicts
with any activity in A will not exclude such optimal sets. It is easy to
verify that an activity (that has not already been excluded) i /∈ A conflicts
with some activity in A iff si < fj where j is the last activity added to A.
Thus the algorithm’s next addtion is also correct by reasoning similar to
that in step 1.
2
• Huffman Codes (Chapter 16.3)
HUFFMAN(C)
1. n ← |C|
2. Q ← C
3. for i ← 1 to n − 1
4. do allocate a new node z
5. left[z] ← x ←EXTRACT-MIN(Q)
6. right[z] ← y ←EXTRACT-MIN(Q)
7. f[z] ← f[x] + f[y]
8. INSERT(Q, z)
9. return EXTRACT-MIN(Q)
• Minimum/Maximum Spanning Tree Problem
• Dijkstra’s Algorithm in Shortest Paths
The discussion of the last two problems also comes under the category Graph
Algorithms.
• Several Scheduling Problems
Example 1 A single server (such as a processor, a cashier in a bank, etc.)
has n customers to serve. The service time required by each customer is known
in advance: customer i will require ti time units (1 ≤ i ≤ n ). We want to
minimize the average time a customer spends in the system.
Since the number of customers is fixed, this is equivalent to minimizing the
total time spent by all customers. So we want to minimize n
i=1 Ci where
Ci is the time at which customer i completes service. Suppose n = 3 and
t1 = 3; t2 = 10; t3 = 5 the table below summarizes the values for all the ways in
which we could render the service:
Order n
i=1 Ci
1, 2, 3 34
1, 3, 2 29 Optimal
2, 3, 1 43
2, 1, 3 41
3, 1, 2 31
3, 2, 1 38
Let P = p1p2...pn be a permutation of {1, 2, ..., n} and let si = tpi . If
customers are served in the order corresponding to P,
n
i=1
Ci = s1 + (s1 + s2) + ... + (s1 + ...sn)
=
n
k=1
(n − k + 1)sk
3
This is minimized by the permutation that has s1 ≤ s2 ≤ ... ≤ sn. This
corresponds to the greedy strategy of processing the customer with the least
time required first.
Example 2 We have n jobs to execute, each one of which takes a unit time to
process. At any time instant we can do only one job. Doing job i earns a profit
pi. The deadline for job i is di.
Suppose n = 4; p = [50, 10, 15, 30]; d = [2, 1, 2, 1]. It should be clear that we
can process no more than two jobs by their respective deadlines. The set of
feasible sequences are:
Sequence Profit
1 50
2 10
3 15
4 30
1, 3 65
2, 1 60
2, 3 25
3, 1 65
4, 1 80 optimal
4, 3 45
A set of jobs is feasible if there is a sequence that is feasible for this set. The
greedy method chooses jobs in decreasing order of their profits. If the inclusion
of the next job does not affect feasibility, we do so. Else we do not include the
last job that was considered. We need to show that this algorithm provides an
optimal solution. We also need to consider the implementation that is most
efficient. Some results given below help in this.
Lemma 3 Let S be a set of jobs. Suppose that the jobs are numbered so that
d1 ≤ d2 ≤ d3 ≤ .... (This is known as the Earliest Due Date order — EDD for
short). The set S is feasible if and only if the sequence {1, 2, ..., } is feasible.
Proof. The ”if” part is clear. To show that ”only if” part we use proof by
contradiction. Suppose that the sequence {1, 2, ..., } is NOT feasible. Let the
first job in the sequence that misses its deadline be job r. This means that the
deadline for job r, dr ≤ r − 1. Since our sequence is EDD, the first r jobs all
have deadlines ≤ (r − 1). However, these jobs are scheduled, at least one will
not meet its deadline. Hence there is no feasible sequence for this set and hence
for S.
This is good news — since we don’t have to check all the permutations of this
set to check feasibility.
Theorem 4 The greedy algorithms solves the problem.
4
Proof. Suppose the greedy algorithms chooses the set I of jobs and suppose
the set J is optimal. We want to show that the two have same profit and
hence I is also optimal. Suppose that corresponding sequences are SJ and SI
respectively. These two sequences may have gaps — time slots where there are
no jobs. By rearranging these sequences, we can get sequences S′j and S′
I in
which the jobs common to the sets J and I are scheduled in the same time slots
as shown below:
p y q x r
r s t p u v q w
x y p r q
u s t p r v q w
SI
SJ
S'I
S'J
These sequences are still feasible since both the previous ones were. This
performs at most one exchange for each job that is common to the two sets. If the
new sequences are not the same we may have one of the following possibilities:
• There is a job a in S′
I opposite a gap in S′
J : This means that a /∈ J. But
J ∪ {a} is also feasible because we can put a in this gap and this would
be more profitable than J˙ But this can not happen since J is optimal.
• There is a job b in S′
J opposite a gap in S′
I : This means that b /∈ I. But
I ∪ {b} is also feasible because we can put b in this gap. This implies
that the greedy algorithm would have included the job b as well. This is
impossible since b was not included in the greedy schedule.
The only remaining possibility is that some job b is scheduled in S′
I opposite
some job a in S′
J . In this case b /∈ S′
J and a /∈ S′
I . There are three
cases to consider:
1. pa > pb: One could substitute a by b in J and we would get a higher
profit — contradiction to optimality of J.
2. pb > pa: The greedy algorithm would have selected b before selecting
a — contradicting the outcome of greedy method.
5
3. pa = pb: In this case the values are the same
Hence, both schedules have equal values jobs in each time slot and
hence the total values are equal. Hence I is also optimal.
The following lemma helps in faster implementation of the greedy algorithm.
Lemma 5 A set J of n jobs is feasible if and only if we can construct a feasible
sequence as follows: Start with an empty schedule with n time slots. For each
job i ∈ J, schedule i at time slot t, where t is the largest integer such that
1 ≤ t ≤ min[n, di] and time slot t is free.
In other words, schedule the next job as late as possible without violating its
deadline. If a job can not be scheduled before its deadline under this algorithm,
then there is no feasible sequence for the set J.
Proof. The ”if” is obvious. For the ”only if” part: Since there are only n
jobs in all, no job needs to be scheduled later than time slot n. Thus, we can
reset the deadlines to min[n, di] for job i. When we try to add a job, there is
always a ”gap”. Suppose we are unable to add a job whose deadline is d. This
happens because all slots form t = 1 to t = r (where r = min[n, d]) are taken
by previous jobs. Let s > r be the smallest integer such that time slot t = s is
free. Thus the schedule built up so far includes s − 1 jobs whose deadlines are
earlier than s, no job with deadline s, and possibly others with deadlines later
than s. The job we are trying to add also has a deadline less than s. Thus, J
includes at least s jobs with deadlines less than or equal to s −1. Whatever be
the schedule, at least one of these will be late.
This lemma suggests that we should take up the jobs in decreasing order of
their profit values and schedule each job one by one to positions in a sequence
of length n. For any position t define nt = max{k ≤ t :position k is free}. We
want the next job i to be assigned to position nt if t = min[n, di]. We need
some other data structures to do this right. We will take this up later when we
do minimum spanning trees in Graph algorithms.
Example 6 We have n jobs to execute. We can do only one job at any time
instant . Job i requires a duration ti. The deadline for job i is di. We want to
maximize the number of jobs done on or before their deadlines.
Let the jobs be ordered in EDD order — numbered so that d1 ≤ d2 ≤ d3 ≤ ....
≤ dn. Define sets Ik = {1, 2, ..., k} with this numbering of jobs. If In is feasible,
then it, clearly, is the solution. If not, let k1 be the minimum k for which Ik is
not feasible. At least one of these jobs can not be included in the final solution.
The most promising candidate is again found by the greedy method: it is the
job k2 in the set Ik for which tk2 is the largest. Job k2 is removed from the list
and we repeat this process.
Proof. Suppose the optimal solution has the set J of jobs and let k2 ∈ I =
J ∩ Ik. So our algorithm removed job k2 but the optimal solution has included
that job. Clearly, I = Ik since this set of jobs is not feasible and hence any
6
set that properly contains this set can not be feasible as well. Let l ∈ Ik\I.
Consider the set J′ = J ∪ {l}\{k2}. Since tl ≤ tk2 , the set J′ is also feasible.
• A Loading Problem
Example 7 Consider a train that travels from point 1 to point n with intermediate
stops at points 2, 3, ..., (n − 1). We have pi,j packages that need to be
delivered from point i to point j where 1 ≤ i < j ≤ n. Packages have the
same size. The maximum number at any point in the train must not exceed its
capacity C. We want to deliver as many packages as possible.
For example, the following table gives data for n = 6 with C = 8:
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 2 2 2
2 4 1 2 2
3 4 4 1
4 2 2
5 3
6
We use the greedy idea twice in the solution of this problem. We describe
the algorithm informally. At point 1 load packages in increasing order of their
destination till capacity is reached. When the train arrives at point 2, (conceptually)
unload and reload according to the same principle as above. If some
packages that were picked up at point 1 get left at point 2, do not load them at
point 1 in the first place! Here is the evolution of the algorithm for this example:
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 2
2
3
4
5
6
After Loading at Point 1
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3
4
5
6
After Loading at Point 2
7
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
4
4 3
After Loading at Point 3
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3 4 3
4 2 2
5
6
After Loading at Point 4
TO →
FROM↓ 1 2 3 4 5 6
1 3 3 1
2 4
3 4 3
4 2 2
5 3
6
After Loading at Point 5
I will leave the proof to you as an exercise.
• Two Machine Scheduling Problem (S. Johnson)
Example 8 Consider the following scheduling problem: We have two machines
A and B (they perform different operations) and a set {1, 2, ..., n} of n jobs. All
jobs are processed by machine A first and then by machine B. Job i requires
a duration Ai on machine A and Bi on machine B. We wish to minimize the
time required to process all jobs and the corresponding schedule. S.M. Johnson
gave a greedy algorithms to solve this problem.
• Johnson Algorithm:
Partition the jobs into two sets S1 = {i : Ai < Bi} and S2 = {i : Ai ≥ Bi}.
Schedule the jobs in S1 first in increasing order of their Ai values and then
the jobs in S2 in decreasing order of their Bi values. Note that this can
8
also be viewed as looking for the smallest of all durations and if this is an
A type schedule the job first and if it is a B type schedule the job last. In
this sense, this is a greedy method. The effort is Θ(n lg n). To prove that
this produces an optimal schedule, we use proof by contradiction.
Proof. Suppose this algorithm does not work for some problem instance.
Let the optimal schedule for this be S. Since the algorithm does not work, there
are two consecutive jobs say j followed by i in S such that one of the following
conditions holds:
1. j ∈ S2 and i ∈ S1
2. j ∈ S1; i ∈ S1 and Aj > Ai
3. j ∈ S2; i ∈ S2 and Bj < Bi
It suffices to show that in any of these cases, if we exchange the positions
of these jobs, we get a schedule that is at least as good as S. By repeated
applications of these exchanges we get a schedule that would be obtained by the
algorithm. This would be a contradiction to the statement that the algorithm
does not work. See below:
S
a1 a2
S'
a1 a2
j i
j i
i j
i j
b1 b2
b1
b'2
α
γ
β
δ
It suffices to show that b′
2 ≤ b2 to show that the schedule S′ is at least as
good as schedule S. Please note that the jobs after i in S can start at the same
time or earlier on machine B in S′ in this case. Let the job before j in S be k
9
and the job after i be m.
α = max[b1, (Aj + a1)]
β = max[a2, (Bj + α)]
b2 = Bi + β
= Bi + max[a2,Bj + max[b1, (Aj + a1)]]
= Bi + max[a2,Bj + b1,Bj + Aj + a1]
max[a1 + Aj + Ai + Bi,Bj + Bi + b1,Bj + Bi + Aj + a1]
γ = max[b1, (Ai + a1)]
δ = max[a2, (Bi + γ)]
b′
2 = Bj + δ
= Bj + max[a2,Bi + max[b1, (Ai + a1)]]
= Bj + max[a2,Bi + b1,Bi + Ai + a1]
= max[a1 + Aj + Ai + Bj ,Bi + Bj + b1,Bi + Bj + Ai + a1]
The middle terms in b2 and b′
2 are the same. Now we consider each of our
cases above:
1. First term in b2 = a1 +Aj +Ai +Bi ≥ Bi +Bj +Ai +a = Third term in
b′
2 because j ∈ S2 =⇒ Aj ≥ Bj
Third term in b2 = Bj + Bi + Aj + a1 ≥ a1 + Aj + Ai + Bj = First term
in b′
2 because i ∈ S1 =⇒ Ai < Bi.
Hence b2 ≥ b′
2 in this case.
2. Third term in b2 = Bj + Bi + Aj + a1 > Bi + Bj + Ai + a = Third term
in b′
2 because Aj > Ai
Third term in b2 = Bj + Bi + Aj + a1 > a1 + Aj + Ai + Bj = First term
in b′
2 because Ai < Bi since i ∈ S1
Hence b2 ≥ b′
2 in this case.
3. First term in b2 = a1 +Aj +Ai +Bi ≥ Bi +Bj +Ai +a = Third term in
b′
2 because j ∈ S2 =⇒ Aj ≥ Bj
First term in b2 = a1 + Aj + Ai + Bi > a1 + Aj + Ai + Bj = First term
in b′
2 because Bj < Bi
Hence b2 ≥ b′
2 in this case.
By a similar argument, we can also show that if there are two possible
schedules that could be obtained by the algorithm, they are equally good.
This completes the proof that the algorithm works.
We will revisit greedy algorithms when we discuss graph algorithms.
10
