CS424 – Design and

Analysis of Algorithms
Week #1-2
About the course
 Course material

 Textbook:
Introduction to Algorithms
by Cormen et al.

 Lecture slides

05/19/25 18:14 2
Why take this course?
 Very basic (especially for CS and SE/CE) and intellectually enlightening
course

 Get to know some common computational problems and their existing

solutions

 Get familiar with algorithm design techniques

(that will help you come up with algorithms on your own)

 Get familiar with algorithm analysis techniques

(that will help you analyze algorithms to pick the most suitable algorithm)

 Computers are not infinitely fast and memory is finite

 Get familiar with typical problems and learn the bounds of power of
algorithms (undecidability and NP-completeness)

05/19/25 18:14 3
Tentative Outline
 Introduction
 Asymptotic Notation Dynamic programming
 Divide and Conquer Greedy algorithms
Paradigm Graph algorithms
 Recurrences Undecidability
 Solving Recurrences NP-Completeness
 Quicksort Practical Evaluation of
 Sorting in linear time Algorithms
 Binary search trees
 Red-Black trees

05/19/25 18:14 4
 INTRODUCTION

05/19/25 18:14 5
What is an algorithm?
Sequence of trivial
steps

 An algorithm is a well-defined computational

procedure that takes a value as input, and
produces a value as output, as a solution to a
computational problem.

input output
Algorithm

05/19/25 18:14 6
 The statement of the problem defines what is
the relationship between the input and the
output.

 The algorithm defines a specific

computational procedure that explains how
this relationship will be realized.

05/19/25 18:14 7
An example computational
problem…
 Given a function

f : {1,2,..., n}  
find a bijection
g : {1,2,..., n}  {1,2,..., n}
such that
i  {1,2,..., n  1} : f ( g (i ))  f ( g (i  1))
 This is nothing but a very formal definition of
the sorting problem
(the problem as described above asks for an algorithm that sorts the input numbers
in nondecreasing order)

05/19/25 18:14 8
An example computational
problem…
 The problem definition is not always given as formal
as in the previous example:

Input : A sequence of n numbers a1 , a2 ,  , an

Output : A permutation a '1 , a '2 ,  , a 'n of the input

sequence such that a '1 a '2  a 'n

05/19/25 18:14 9
Sorting example
 Given a sequence of numbers as input such as
[ 15, 42, 17, 34, 3, 17 ]
 The output should be
[ 3, 15, 17, 17, 34, 42 ]

 Note that, the output for this input is in accordance

with the problem definition, i.e. it conforms with the
“what should be done” definition given in the problem
statement .

 “How it should be done” depends on the algorithm.

05/19/25 18:14 10
An instance of a problem
 An instance of a problem consists of all the
inputs that satisfy the constraints that are
imposed by the problem definition.
 “Sort [15, 42, 17, 34, 3, 17] in nondecreasing
order” is an instance of the sorting problem.
 “Sort [23, 33, 4, 1, 27] in nondecreasing order” is
another instance of the sorting problem.

 The input is a sequence of numbers (not a sequence of animals, not

a set of sequences of numbers).

05/19/25 18:14 11
Not the sorting problem
again !!!
 Sorting is a fundamental operation in many
disciplines and it is used as a part of other
algorithms.
 A lot of research has been made on the
sorting problem.
 A lot of algorithms have been developed.
 It is a very simple and interesting problem to
explain basic ideas of algorithm design and
analysis techniques.
05/19/25 18:14 12
Correctness of algorithms
 An algorithm is correct if for every instance
of the problem, it halts (terminates) and it
produces the correct answer.
 Otherwise (i.e. if there are some instances for which
the algorithm does not halt, or it produces an
incorrect answer), it is called an incorrect algorithm.

 Surprisingly, incorrect algorithms are

occasionally used in practice…

05/19/25 18:14 13
Insertion sort
 Basic idea: Given a nondecreasing sequence
[a1, a2, …, an] and a number k
the sequence
[a1, a2, … ai, k, ai+1,…, an]
is a nondecreasing sequence if ai ≤ k ≤ ai+1
 For example:
[a1, a2, a3, a4, a5] k

[10, 12, 22, 34, 35] 19

the result is: [10,12,19,22,34,35]

05/19/25 18:14 14
Insertion sort
 How can we use this idea to sort a sequence of
numbers?
 Suppose we are given: [ 3, 1, 7, 2 ]

[3] [1,3] [1,3,7] [1,2,3,7]

 Start with a single element sequence
(by definition, it is already a sorted sequence)
 Insert each element one-by-one into already sorted
sequence.
 It is like sorting a hand of a card game (e.g. bridge)

05/19/25 18:14 15
An Implementation for
Insertion sort Considers each element
Searches for the
Insertion-Sort(A) { one-by-one. Note that, the
correctisplace
first element to insert
assumed to
for (j=2; j≤n; j=j+1) { form thetheinitial
next sorted
element.
num = A[j]; sequence.
i = j-1;
// find the correct place for num
while (i>0 and A[i]>num) { If it sees that num is
A[i+1] = A[i]; smaller than A[i], it
shifts A[i] one position
i=i-1; to the right
}
A[i+1] = num;
When the correct
} place is found, it will
} be already empty

05/19/25 18:14 16
Is Insertion sort the solution for
the sorting problem?
 Insertion sort is only a solution for the sorting
problem.
 “But we’ve just proved that it works correctly
for all the input sequences. Why do we need
other algorithms to solve the sorting
problem?”
 There may be other algorithms better than
Insertion sort…

05/19/25 18:14 17
What does a “better
algorithm” mean?
 A better algorithm uses less resources than the

other algorithms.
 Then, just show us the best algorithm known.
We will only be using the best algorithm.
- Time (*)
- Space (i.e. memory)
 Not that simple. Using
- Money less resource depends on
- Area
 The number of input elements
- Bandwidth
 The characteristics of the input
- Energy
- etc.
 The resource we are interested in
 So, the definition of “best” changes

05/19/25 18:14 18
Selecting the best algorithm
 Selecting the best algorithm, first of all, requires to
have multiple algorithms for the solution of the same
problem. We will mainly use the RAM (random
access machine) model, where the
 The resource on which our selection
algorithms will be
are implemented made
as single
should be known. threaded computer programs .
 And, we must analyze the model,
In RAM available algorithms
statements to
are executed
understand how much oneofbythe
one,type of resource we
sequentially.

are interested these algorithms use.

 We must have a specific model of implementation
for the analysis.

05/19/25 18:14 19
Analysis of Insertion sort

 Time taken by Insertion sort depends on

 The number of elements to be sorted
10 elements vs. 1000 elements
 The nature of the input
almost sorted, reverse sorted, etc.
 In general, the time taken by an algorithm
grows with the size of the input.
 Therefore, we describe the running time of an
algorithm as a function of the input size.
05/19/25 18:14 20
Definition of the input size
 It depends on the problem and sometimes on the
algorithm.
 For sorting problem, it is natural to pick the number of
elements as the size of the input. For some sorting
algorithms, the range of the numbers to be sorted may
also be used as the size of the input.
 For some problems, a single measure is not sufficient to
describe the size of the input.
 For example, for a graph algorithm, the size of the graph is
better described with the number of nodes and the number
of edges given together.

05/19/25 18:14 21
Definition of the running
time
 We can use a 1990 PC AT computer or a

contemporary supercomputer to execute an

implementation of the algorithm.
 A good programmer can implement the algorithm
directly using assembly code, or a beginner
programmer can implement it using a high level
language and compile it using the worst compiler
(which has no optimization).

 So, the running time of a given algorithm seems

to depend on certain conditions.

05/19/25 18:14 22
Definition of the running
time
 Our notion of “running time” should be an
abstract notion that is as independent as
possible from such concerns.

 Let us try to compute the running time

InsertionSort, by assigning some unknown
but fixed running times for each line of code
in the algorithm.

05/19/25 18:14 23
Running time of insertion
cost times executed
sort
Insertion-Sort(A) {
for (j=2; j≤n; j=j+1) { c n 1
num = A[j]; c2 n-1
i = j-1; c3 n-1
// find the correct place for num

n
c4 kj
while (i>0 and A[i]>num) { j 2


n
A[i+1] = A[i]; c5 j 2
(k j  1)
i=i-1;

n
c6 (k j  1)
j 2
}
A[i+1] = num; c7 n-1
}
}

n: the number of elements in the array A

kj: the number of times the “while” loop condition is checked for that specific j value

05/19/25 18:14 24
Running time of insertion
sort
 The total running time can be calculated as:
T (n) c1n  c2 (n  1)  c3 (n  1)  c4  j 2 k j  c5  j 2 (k j  1)  c6  j 2 (k j  1)  c7 (n  1)
n n n

 With a little bit of calculation:

T (n) a1n  a2  j 2 k j  a3
n

05/19/25 18:14 25
Running time of insertion sort
(best case)
 Recall that kj is the number of times that the
“while loop” condition is checked to find the
correct place of a number
 Under the best scenario, it will never iterate
for all j, hence kj =1 for all j
 This corresponds to the case where the input
is already sorted
 In this case n
T (n) a1n  a2  j 2 k j  a3 a1n  a2  j 2 1  a3 (a1  a2 )n  a3  a2
n

05/19/25 18:14 26
Running time of insertion sort
(worst case)
 Under the worst scenario, the while loop will
iterate the maximum amount of time possible
 Therefore, kj = j for all j
T (n) a1n  a2  j 2 k j  a3
n

a1n  a2  j 2 j  a3
n

 n(n  1) 
a1n  a2   1  a3
 2 
b1n 2  b2 n  b3

05/19/25 18:14 27
Running time of insertion sort
(average case)
 On the average, the while loop will iterate half
of the maximum possible number of times
 Therefore, kj = j/2 for all j
T (n) a1n  a2  j 2 k j  a3
n

j
a1n  a2  j 2  a3
n

2
a  n(n  1) 
a1n  2   1  a3
2 2 
d1n 2  d 2 n  d 3

05/19/25 18:14 28
Running time of insertion
sort
 Best case: T (n) (a1  a2 )n  a3  a2
Linear function of n

2
 Average case: T (n) b1n  b2 n  b3
Quadratic function of n

2
 Worst case: T ( n ) d1 n  d 2n  d3
Quadratic function of n

05/19/25 18:14 29
Which running time we
should use?
 In order to compare the running time of
algorithms, usually the “worst case running
time” is used, because
 It gives an upper bound (it cannot go worse)
 Murphy’s law (the worst case happens)
 Average case is usually the same as the worst
case.

05/19/25 18:14 30
Asymptotic Analysis

 Note that, in the running time analysis of the

insertion sort algorithm, we ignored the actual
cost of steps by abstracting them with
constants : ci

 We will go one step further, and show that

these constants are not actually very
important in practice, especially when we
consider large input sizes.

05/19/25 18:14 31
Asymptotic Analysis
 Suppose we have two algorithms for sorting
A1 and A2
 Let the exact running time of them be
T1 (n) 2n 3 and T2 (n) 50n 2
 Assume A1 is executed on a fast machine
(109 instructions per second)
 Assume A2 is executed on a slow machine
(106 instructions per second)
 Assume we will be sorting 105 numbers
05/19/25 18:14 32
Asymptotic Analysis
T1 (n) 2n 3 and T2 (n) 50n 2
 A1 on the fast computer will need
210  instructions
5 3
6
9
2.10 2 million seconds
10 instructions/sec
A2 will run four times faster
 A2 on the slow computer will need
  5 2
50 10 instructions 4
50.10 0.5 million seconds
6
10 instructions/sec

05/19/25 18:14 33
Asymptotic Analysis

 In real life, most of the time we will be

interested in the performance of the
algorithms on large inputs.

 Therefore, even if the coefficients of the exact

running time are small, it is the growth rate of
the function (highest order term) that
determines the performance of the algorithms
as the input size gets bigger.
05/19/25 18:14 34
Asymptotic Analysis


Look at growth of T(n) as n → ∞
 Θ-notation:
 Ignore lower order terms
 Ignore leading constants
Leading
 For example: constant

T (n) d1n 2  d 2 n  d 3
Lower order
T (n) n 2  terms

05/19/25 18:14 35
Asymptotic Analysis
time

n0 input size

05/19/25 18:14 36
Algorithm Design Techniques
 In general, there is no recipe for coming up with an
algorithm for a given problem.

 However, there are some algorithms design

techniques that can be used to classify the
algorithms.

 Insertion sort uses so called “incremental approach”

Having sorted A[1..j-1], insert a new element A[j],
forming a new, larger sorted sequence A[1..j]

05/19/25 18:14 37
Divide and Conquer
 Another such design approach is
Divide and Conquer

 We will examine another algorithm for the sorting

problem that follows divide and conquer approach

 Divide and conquer algorithms are recursive in their

nature.

 It is relatively easy to analyze their running time

05/19/25 18:14 38
Three steps of divide and
conquer
1. Divide: The problem is divided into several
smaller subproblems
2. Conquer: The subproblems are attacked
recursively by the
For example, dividesame
the algorithm. When
the size ofsequence
given the subproblem
of gets
Combine sorted small
subsequences
numbers into smaller together to form the sorted form
enough, the problemof is
sequences. the solved in a
original sequence.
straightforward manner.
3. Combine:
As long asThe solutions
we have to element
more than one the subproblems
to
combined to
sort, keep form
dividing.the
Whensolution of the original
we have a single
element to sort, it is already a sorted sequence.
problem.
05/19/25 18:14 39
Merge Sort
 Basic idea: Given two sorted sequences
[a1,a2,…,an] and [b1,b2,…bm]
these two sequences can be merged into a
single sorted sequence efficiently.
 For example:
[1,5,7] and [2,3,6]

[1] [1,2] [1,2,3] [1,2,3,5] [1,2,3,5,6] [1,2,3,5,6,7]

Can be performed in Θ(n) time.

05/19/25 18:14 40
Divide and conquer structure of
the merge sort
1. Divide: Divide the n-element sequence to be
sorted into two subsequences of n/2 elements
each.

2. Conquer: Sort the subsequences recursively using

merge sort (note that the recursion will bottom out
when we have single element lists).

3. Combine: Merge the sorted subsequences using

the merge operation explained before.

05/19/25 18:14 41
Execution of the merge sort
3 8 4 1
divide

3 8 4 1
divide

recursion bottoms out 3 8 4 1

merge

3 8 1 4
merge
1 3 4 8

05/19/25 18:14 42
Execution of the merge sort
3 8 4

3 8 4
Works even when the number
of items is not an exact power
of two 3 8 4

3 8 4

3 4 8

05/19/25 18:14 43
 A Merge Sort
Implementation
Lowest index of the subsequence Highest index of the subsequence

Merge-Sort(A,p,r) {
If there are at least two numbers, we still need to
1. if (p < r) { divide. Otherwise do nothing…

2. q = floor((p+r)/2); divide the list into 2

3. Merge-Sort(A,p,q); recursively sort using
Merge-Sort
4. Merge-Sort(A,q+1,r);
5. Merge(A,p,q,r);
combine the solutions
}
}
05/19/25 18:14 44
Analysis of Divide and Conquer
Algorithms
 If an algorithm is recursive, its running time
can often be described by a recurrence
equation or recurrence.

 A recurrence is a function that is defined

recursively.

05/19/25 18:14 45
Analysis of Divide and Conquer
Algorithms
 A recurrence for running time T(n) of a divide and
conquer algorithm is based on the three steps of the
design approach:
 Suppose at each step the problem of size n is divided into
a subproblems each of size n/b. Furthermore suppose
dividing takes D(n) time.

 When the problem size is small enough (say smaller than a

constant c), we will apply a straightforward technique to
solve the problem in constant amount of time, denoted by
Θ(1).

 Suppose combining the solutions takes C(n) time.

05/19/25 18:14 46
Analysis of Divide and Conquer
Algorithms
 The recurrence for a divide and conquer
algorithm will then be:

(1) if n  c
T (n) 
aT (n / b)  D(n)  C (n) otherwise
if the problem is small
enough,
time we
number spend
required
size a solve
ofof each
to
work required
workforrequired for
constant amount
subproblems
each of dividing
subproblem
subproblem combining
into the solution
recursive definition of the function
time to solve it subproblemsof the subproblems

05/19/25 18:14 47
Analysis of Merge Sort
 Note that the pseudo code for Merge-Sort works
correctly when the number of elements is not even.

 However, we will assume that the number of

elements is a power of 2 for the analysis purposes.

 We will later see that, this assumption does not

actually make a difference.

05/19/25 18:14 48
 Merge-Sort(A,p,r) {
Analysis of Merge Sort 1. if (p<r) {
Merge-Sort(A,p,r) { 2. q =
floor((p+r)/2);
1. if (p<r) {
Merge-
2. Divide: q The divide step just computes the
 =
3.
Sort(A,p,q);
floor((p+r)/2);
middle of the array, hence 4. it takes a constant
Merge-
3. Merge-
amount of
Sort(A,p,q); time → D(n) = Θ(1)
Sort(A,q+1,r);
5. Merge(A,p,q,r);
 Conquer:
4.
Need
Merge- to solve recursively two
Sort(A,q+1,r); }
Merge-Sort(A,p,r) {
5.
subproblems, each of 1.which
Merge(A,p,q,r); } has size n/2.
if (p<r) {
Hence}this step takes 2.2T(n/2) time. q =
} floor((p+r)/2);
Combine: As we have 3.seen earlier, Merge-
merging
two sorted sequences with n elements takes
Sort(A,p,q);
linear time → C(n) = Θ(n) 4. Merge-
Sort(A,q+1,r);
5. Merge(A,p,q,r);
05/19/25 18:14 49
}
Analysis of Merge Sort

 Therefore, the running time of Merge-Sort is

(1) if n  c
T (n) 
aT (n / b)  D(n)  C (n) otherwise
(1) if n 1

2T (n / 2)  (1)  (n) otherwise
(1) if n 1

2T (n / 2)  (n) otherwise
(n log 2 n)

05/19/25 18:14 50
Comparison of Insertion and
Merge Sort
 Insertion Sort : Θ(n2)
 Merge Sort: Θ(n log2 n)
 Merge Sort is asymptotically more efficient
than Insertion Sort.
 Does this mean we should never use
Insertion Sort?
 No. Note that we omitted the constant
coefficients…

05/19/25 18:14 51
Comparison of Insertion and
Merge Sort
time Insertion Sort

Merge Sort

n0 input size
 Due to constant coefficients, Insertion Sort may still be
preferable for small input sizes.
 Also, Insertion Sort has a good performance on almost
sorted inputs

05/19/25 18:14 52