Introduction to Algorithms
Lecture 1
Text Books
• Coreman, Rivest, Lisserson, : “Introduction to
Algorithms", PHI.
• Horowitz & Sahani, "Fundamental of
Computer Algorithm", Galgotia.
All of Computer Science Is the Study of
Algorithms
Asymptotic Performance of an
Algorithm
• In this course, we care most about asymptotic
performance
How does the algorithm behave as the problem
size gets very large?
o Running time
o Memory/storage requirements
o Bandwidth/power requirements/logic gates/etc.
An asymptote of a curve is a line such that the distance
between the curve and the line approaches zero as one or
both of the x or y coordinates tends to infinity.
Asymptotic Notation
• By now you should have an intuitive feel for
asymptotic (big-O) notation:
What does O(n) running time mean? O(n2)?
O(n lg n)?
How does asymptotic running time relate to
asymptotic memory usage?
• Our first task is to define this notation more
formally and completely (which we will do in
next class)
Analysis of Algorithms
• Analysis is performed with respect to a computational
model
• We will usually use a generic uniprocessor random-
access machine (RAM)
All memory equally expensive to access
No concurrent operations
All reasonable instructions take unit time
o Except, of course, function calls
Constant word size
o Unless we are explicitly manipulating bits
Input Size
• Time and space complexity
This is generally a function of the input size
o E.g., sorting, multiplication
How we characterize input size depends:
o Sorting: number of input items
o Multiplication: total number of bits
o Graph algorithms: number of nodes & edges
o Etc
Running Time
• Number of primitive steps that are executed
Except for time of executing a function call most
statements roughly require the same amount of
time
oy=m*x+b
o c = 5 / 9 * (t - 32 )
o z = f(x) + g(y)
• We can be more exact if need be
Analysis
• Worst case
Provides an upper bound on running time
An absolute guarantee
• Average case
Provides the expected running time
Very useful, but treat with care: what is “average”?
o Random (equally likely) inputs
o Real-life inputs
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
InsertionSort(A) {
for i = 2 to length[A] {
key = A[i]
j = i - 1
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 10 40 20 i = j = key =
A[j] = A[j+1] =
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 10 40 20 i=2 j=1 key = 10
A[j] = 30 A[j+1] = 10
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 i=2 j=1 key = 10
A[j] = 30 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 i=2 j=1 key = 10
A[j] = 30 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 i=2 j=0 key = 10
A[j] = A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 i=2 j=0 key = 10
A[j] = A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=2 j=0 key = 10
A[j] = A[j+1] = 10
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=0 key = 10
A[j] = A[j+1] = 10
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=0 key = 40
A[j] = A[j+1] = 10
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=0 key = 40
A[j] = A[j+1] = 10
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=2 key = 40
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=2 key = 40
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=3 j=2 key = 40
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=4 j=2 key = 40
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=4 j=3 key = 20
A[j] = 40 A[j+1] = 20
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 i=4 j=3 key = 20
A[j] = 40 A[j+1] = 20
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 i=4 j=3 key = 20
A[j] = 40 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 i=4 j=3 key = 20
A[j] = 40 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 i=4 j=3 key = 20
A[j] = 40 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 40
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 i=4 j=2 key = 20
A[j] = 30 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 i=4 j=1 key = 20
A[j] = 10 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 i=4 j=1 key = 20
A[j] = 10 A[j+1] = 30
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 20 30 40 i=4 j=1 key = 20
A[j] = 10 A[j+1] = 20
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
10 20 30 40 i=4 j=1 key = 20
A[j] = 10 A[j+1] = 20
1 2 3 4
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
} Done!
Insertion Sort
InsertionSort(A, n) { What is the precondition
for i = 2 to n { for this loop?
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
Insertion Sort
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
} How many times will
} this loop execute?
Insertion Sort
Statement Effort
InsertionSort(A) {
for i = 2 to length[A] { c1n
key = A[i] c2(n-1)
j = i - 1; c3(n-1)
while (j > 0) and (A[j] > key) { c4T
A[j+1] = A[j] c5(T-(n-1))
j = j - 1 c6(T-(n-1))
} 0
A[j+1] = key c7(n-1)
} 0
}
T = t2 + t3 + … + tn where ti is number of while expression evaluations for the i th for loop iteration
Analyzing Insertion Sort
• T(n) = c1n + c2(n-1) + c3(n-1) + c4T + c5(T - (n-1)) + c6(T - (n-1)) + c7(n-1)
= c8T + c9n + c10
• What can T be?
Best case -- inner loop body never executed
o ti = 1 T(n) is a linear function
Worst case -- inner loop body executed for all previous
elements
o ti = i T(n) is a quadratic function
Average case
o ti = i/2 T(n) is a quadratic function
Order of Growth
• Ignore constants & lower order terms since it
is the high order term that dominates as input
size grows longer.
• We say running time of insertion sort is O(n 2)
The largest size n of a problem that can be solved in time t,
assuming that the algorithm to solve the problem takes f(n)
microseconds.
Correct algorithms
• An algorithm is correct if:
– for any correct input data:
• it stops and
• it produces correct output.
– Correct input data: satisfies precondition (restrictions on input
data)
– Correct output data: satisfies postcondition (result)
• Example: Binary Search
– Input : a:array of integer; x:integer;
– Output : found:boolean;
– Precondition: a is sorted in ascending order
– Postcondition: found is true if x is in a, and found is false
otherwise
Proving correctness of an Algorithm
• This is easy to prove for simple sequential
algorithms
• This can be complicated to prove for repetitive
algorithms (containing loops)
use techniques based on loop invariants and induction
Example – a sequential algorithm
Swap1(x,y): Proof: the list of actions
aux := x applied to the
x := y precondition imply the
y := aux postcondition
1. Precondition:
x = a and y = b
Precondition:
2. aux := x => aux = a
x = a and y = b
3. x : = y => x = b
Postcondition:
4. y := aux => y = a
x = b and y = a
5. x = b and y = a is
the Postcondition
Example – a repetitive algorithm
Algorithm Sum_of_N_numbers
Proof: the list of actions
applied to the
Input: a, an array of N numbers
precondition imply
Output: s, the sum of the N numbers the postcondition
in a
BUT: we cannot
s:=0; enumerate all the
k:=0; actions in case of a
While (k<N) do repetitive algorithm !
k:=k+1; We use techniques
s:=s+a[k]; based on loop
end invariants and
induction
Loop invariants
• A loop invariant is a logical predicate such that: if it
is satisfied before entering any single iteration of the
loop then it is also satisfied after the iteration
• In other words, a loop invariant is a property of a
program loop that is true before (and after) each
iteration
Example: Loop invariant for Sum of
n numbers
Algorithm Sum_of_N_numbers
Input: a, an array of N numbers
Output: s, the sum of the N numbers in a
s:=0; Loop invariant = induction
k:=0; hypothesis: At step k, S holds the
While (k<N) do
k:=k+1; sum of the first k numbers
s:=s+a[k];
end
Using loop invariants in proofs
• We must show the following 3 things about a
loop invariant:
1. Initialization: It is true prior to the first iteration of
the loop.
2. Maintenance: If it is true before an iteration of the
loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the
invariant gives us a useful property that helps show
that the algorithm is correct.
Example: Proving the correctness
of the Sum algorithm (1)
• Induction hypothesis: S= sum of the first k
numbers
1. Initialization: The hypothesis is true at the
beginning of the loop:
Before the first iteration: k=0, S=0. The first 0 numbers have
sum zero (there are no numbers) => hypothesis true
before entering the loop
Example: Proving the correctness
of the Sum algorithm (2)
• Induction hypothesis: S= sum of the first k
numbers
2. Maintenance: If hypothesis is true before step k, then it
will be true before step k+1 (immediately after step k is
finished)
We assume that it is true at beginning of step k: “S is the sum of
the first k numbers”
We have to prove that after executing step k, at the beginning of
step k+1: “S is the sum of the first k+1 numbers”
We calculate the value of S at the end of this step
K:=k+1, s:=s+a[k+1] => s is the sum of the first k+1 numbers
Example: Proving the correctness
of the Sum algorithm (3)
• Induction hypothesis: S= sum of the first k
numbers
3. Termination: When the loop terminates, the
hypothesis implies the correctness of the algorithm
The loop terminates when k=n=> s= sum of first k=n
numbers => postcondition of algorithm, DONE
Loop invariants and induction
• Proving loop invariants is similar to
mathematical induction:
showing that the invariant holds before the first
iteration corresponds to the base case, and
showing that the invariant holds from iteration to
iteration corresponds to the inductive step.
Correctness of algorithms
• Induction can be used for proving the
correctness of repetitive algorithms:
Iterative algorithms:
o Loop invariants
Induction hypothesis = loop invariant = relationships between
the variables during loop execution
Recursive algorithms
o Direct induction
Hypothesis = a recursive call itself ; often a case for applying
strong induction
Example: Correctness proof for
Decimal to Binary Conversion
Algorithm Decimal_to_Binary
Input: n, a positive integer
Output: b, an array of bits, the bin repr. of n,
starting with the least significant bits
t:=n; It is a repetitive (iterative)
k:=0; algorithm, thus we use loop
While (t>0) do invariants and proof by induction
k:=k+1;
b[k]:=t mod 2;
t:=t div 2;
end
Example: Loop invariant for
Decimal to Binary Conversion
Algorithm Decimal_to_Binary
Input: n, a positive integer
Output: b, an array of bits, the bin repr. of n
t:=n; At step k, b holds the k least
k:=0;
significant bits of n, and the value
While (t>0) do
k:=k+1; of t, when shifted by k,
b[k]:=t mod 2; corresponds to the rest of the bits
t:=t div 2; 1 2 3 k
end
b
20 21 22 2k-1
Example: Loop invariant for
Decimal to Binary Conversion
Algorithm Decimal_to_Binary
Input: n, a positive integer
Output: b, an array of bits, the bin repr. of n
t:=n; Loop invariant: If m is the
k:=0; integer represented by array
While (t>0) do
k:=k+1; b[1..k], then n=t*2k+m
b[k]:=t mod 2;
t:=t div 2; 1 2 3 k
end
b
20 21 22 2k-1
Example: Proving the correctness
of the conversion algorithm
• Induction hypothesis=Loop Invariant: If m is the
integer represented by array b[1..k], then n=t*2^k+m
• To prove the correctness of the algorithm, we have
to prove the 3 conditions:
1. Initialization: The hypothesis is true at the beginning of
the loop
2. Maintenance: If hypothesis is true for step k, then it will
be true for step k+1
3. Termination: When the loop terminates, the hypothesis
implies the correctness of the algorithm
Example: Proving the correctness
of the conversion algorithm (1)
• Induction hypothesis: If m is the integer represented
by array b[1..k], then n=t*2^k+m
1. The hypothesis is true at the beginning of the loop:
k=0, t=n, m=0(array is empty)
n=n*2^0+0
Example: Proving the correctness
of the conversion algorithm (2)
• Induction hypothesis: If m is the integer represented by
array b[1..k], then n=t*2^k+m
2. If hypothesis is true for step k, then it will be true for
step k+1
At the start of step k: assume that n=t*2^k+m, calculate the
values at the end of this step
If t=even then: t mod 2==0, m unchanged, t=t / 2, k=k+1=> (t /
2) * 2 ^ (k+1) + m = t*2^k+m=n
If t=odd then: t mod 2 ==1, b[k+1] is set to 1, m=m+2^k , t=(t-
1)/2, k=k+1 => (t-1)/2*2^(k+1)+m+2^k=t*2^k+m=n
Example: Proving the correctness
of the conversion algorithm (3)
• Induction hypothesis: If m is the integer represented
by array b[1..k], then n=t*2^k+m
3. When the loop terminates, the hypothesis implies
the correctness of the algorithm
The loop terminates when t=0 => n=0*2^k+m=m
n==m, proved
Proof of Correctness for Recursive
Algorithms
• In order to prove recursive algorithms, we have to:
1. Prove the partial correctness (the fact that the program
behaves correctly)
o we assume that all recursive calls with arguments that satisfy the
preconditions behave as described by the specification, and use
it to show that the algorithm behaves as specified
2. Prove that the program terminates
o any chain of recursive calls eventually ends and all loops, if any,
terminate after some finite number of iterations.
Example - Merge Sort
MERGE-SORT(A,p,r) p q r
if p < r
q= (p+r)/2
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)
Precondition:
Array A has at least 1 element between indexes p and r
(p<=r)
Postcondition:
The elements between indexes p and r are sorted
Example - Merge Sort
• MERGE-SORT calls a MERGE (A,p,q,r)
function MERGE(A,p,q,r) to
merge the sorted subarrays of Precondition: A is an
A into a single sorted one array and p, q, and r
• The proof of MERGE (which are indices into the
is an iterative function) can be array such that p <= q
done separately, using loop < r. The subarrays
A[p.. q] and A[q +1..
invariants r] are sorted
• We assume here that MERGE Postcondition: The
has been proved to fulfill its subarray A[p..r] is
postconditions (can do it as a sorted
distinct exercise)
Correctness proof for Merge-Sort
• Number of elements to be sorted: n=r-p+1
• Base Case: n = 1
A contains a single element (which is trivially “sorted”)
• Inductive Hypothesis:
Assume that MergeSort correctly sorts n=1, 2, ..., k elements
• Inductive Step:
Show that MergeSort correctly sorts n = k + 1 elements.
First recursive call n1=q-p+1=(k+1)/2<=k => subarray A[p .. q] is
sorted
Second recursive call n2=r-q=(k+1)/2<=k => subarray A[q+1 .. r] is
sorted
A, p q, r fulfill now the precondition of Merge
The postcondition of Merge guarantees that the array A[p .. r] is sorted
=> postconsition of MergeSort
Correctness proof for Merge-Sort
• Termination:
To argue termination, we have to find a quantity that decreases with
every recursive call: the length of the part of A considered by a call to
MergeSort
For the base case, we have a one-element array. the algorithm
terminates in this case without making additional recursive calls.
Correctness proofs
for recursive algorithms
RECURSIVE(n) is
if (n=small_value)
return ct
else
RECURSIVE(n1) n1, n2, … nr are some
… values smaller than n but
RECURSIVE(nr) bigger than small_value
some_code
• Base Case: Prove that RECURSIVE works for n = small_value
• Inductive Hypothesis:
Assume that RECURSIVE works correctly for n=small_value, ..., k
• Inductive Step:
Show that RECURSIVE works correctly for n = k + 1
Do it Yourself
Proving correctness of an algorithm
(Read the article Loop invariants and
correctness of insertion sort on page 17 )
Up Next
• Asymptotic Notations
