CS 6131

Advanced Algorithm Design and Analysis

MSc in Computer Science

Chapter 1: Introduction
Dr. Atef MASMOUDI
Associate Professor
College of Computer Science
amasmoudi@kku.edu.sa

Chapter 1 – pages : 1-35

Algorithms Illuminated: Part 1: The Basics
Part I – pages : 24-84
Introduction to algorithms 1
 What we will cover
• An overview of algorithms and their place in modern computing systems.

• Define what an algorithm is and lists some examples.

• Examining the sorting algorithms and introducing many standard design techniques

and analysis tools.

• You will learn by doing, not just by listening.

2
 Let’s start with the first algorithms
Sorting a sequence of n numbers
• Insertion Sort
– Suppose that you need to sort a sequence of numbers into monotonically
increasing order.
Formal definition:
– Input: A sequence of n numbers <a1, a2, …,an>
Output: A permutation (reordering) <a’1, a’2, …,a’n> of the input sequence
such that a’1<=a’2<= …<=a’n.
Pseudocode*
INSERTION-SORT(A, n)
1 for i = 2 to n
2 key = A[i]
3 // Insert A[i] into the sorted subarray A[1 : i – 1].
4 j=i–1
5 while j > 0 and A[j] > key
6 A[j + 1] = A[j]
7 j=j–1
8 A[j + 1] = key
*PseudoCode, Introduction to algorithms, page 46 3
 Insertion Sort
• Example

Figure 2.2, Introduction to algorithms, page 47 4

 Loop invariants and correctness
• Loop invariants help us understand why an algorithm is
correct.
• When using a loop invariant, you need to show three
things:
– Initialization: It is true prior to the first iteration of the
loop.
– Maintenance: If it is true before an iteration of the
loop, it remains true before the next iteration.
– Termination: The loop terminates, and when it
terminates, the invariant gives us a useful property that
helps show that the algorithm is correct.
5
 Loop invariants and correctness (cont.)
• Let’s see how these properties hold for insertion sort.

• Loop invariant: At the start of each iteration of the for loop, the subarray A[1 : i–1] consists
of the elements originally in A[1 : i– 1], but in sorted order.
• Initialization: Before the first loop iteration, when i = 2. The subarray A[1 : i – 1] consists of just the
single element A[1], which is in fact the original element in A[1]. Trivially, this subarray is sorted,.

• Maintenance: The body of the for loop works by moving the values in A[i – 1], A[i – 2], A[i – 3], and so
on by one position to the right until it finds the proper position for A[i] (lines 4–7), at which point it
inserts the value of A[i] (line 8). The subarray A[1 : i] then consists of the elements originally in A[1 : i],
but in sorted order. Incrementing i for the next iteration of the for loop then preserves the loop
invariant.

• Termination: The loop variable i starts at 2 and increases by 1 in each iteration. Once i’s value exceeds
n in line 1, the loop terminates. That is, the loop terminates once i equals n + 1. Substituting n + 1 for i
in the wording of the loop invariant yields that the subarray A[1 : n] consists of the elements originally
in A[1 : n], but in sorted order. Hence, the algorithm is correct.
6
 Exercises
• 1- Using Figure 2.2 as a model, illustrate the operation of
INSERTIONSORT on an array initially containing the sequence 〈31,
41, 59, 26, 41,58〉.
• 2- Consider the following procedure SUM-ARRAY. It computes the
sum of the n numbers in array A[1 : n]. State a loop invariant for
this procedure, and use its initialization, maintenance, and
termination properties to show that the SUM-ARRAY procedure
returns the sum of the numbers in A[1 : n].
SUM-ARRAY(A, n)
1s=0
2 for i = 1 to n
3 s = s + A[i]
4 return s

7
 Exercises (cont.)
• 3- Consider the searching problem:
Input: A sequence of n numbers 〈a1, a2, … , an〉 stored in array A[1 : n] and a
value x.
Output: An index i such that x equals A[i] or the special value NIL if x does not
appear in A.
Write pseudocode for linear search, which scans through the array from
beginning to end, looking for x. Using a loop invariant, prove that your
algorithm is correct. Make sure that your loop invariant fulfills the three
necessary properties.
• 4- Consider the problem of adding two n-bit binary integers a and b, stored in
two n-element arrays A[0 : n – 1] and B[0 : n – 1], where each element is either
0 or 1, = ∑ ∗ 2 , and = ∑ ∗ 2 . The sum c = a + b of the
two integers should be stored in binary form in an (n + 1)-element array C [0 :
n], where = ∑ ∗ 2 . Write a procedure ADD-BINARY-INTEGERS that
takes as input arrays A and B, along with the length n, and returns array C
holding the sum. Using a loop invariant, prove that your algorithm is correct.
Make sure that your loop invariant fulfills the three necessary properties.
8
 Analyzing algorithms
• Analyzing an algorithm has come to mean predicting the resources that the
algorithm requires.
• You might consider resources such as memory, communication bandwidth, or
energy consumption.
• More important is to measure computational time. If you analyze several
candidate algorithms for a problem, you can identify the most efficient one.
• We assume a generic one-processor, random-access machine (RAM) model of
computation as the implementation technology, with the understanding that
algorithms are implemented as computer programs.
• In the RAM model, instructions execute one after another, with no concurrent
operations.
• The RAM model assumes that it takes a constant amount of time to do any of these:
– initialize a value
– increment a value
– perform an addition/subtraction
– perform a comparison and react accordingly
– return a value
– find the length of a list
– access a list element 9
 Analysis of insertion sort
• How long does the INSERTION-SORT procedure take?
• One way is to run the procedure on your computer and time how long it takes to run.
• In that case, you’d first have to implement it in a real programming language, since you
cannot run a pseudocode directly.
• What would such a timing test tell you?
• You would find out how long insertion sort takes to run on your particular computer,
on that particular input, under the particular implementation that you created, with
the particular compiler or interpreter that you run, with the particular
libraries that you linked in, and with the particular background tasks that were running
on your computer concurrently with your timing test
• If you run insertion sort again on your computer with the same input, you might
even get a different timing result.

We need a way to predict, given a new input, how long insertion sort will take.

10
 Analysis of insertion sort (cont.)
• Instead of timing a run, or even several runs, of insertion sort, we can determine how
long it takes by analyzing the algorithm itself.
• We’ll examine how many times it executes each line of pseudocode and how
long each line of pseudocode takes to run.
• We’ll first come up with a precise but complicated formula for the running time.
• Then, we’ll consider the important part of the formula using a convenient notation
that can help us compare the running times of different algorithms for the same
problem.

• How do we analyze insertion sort?

• Describe the running time of a program as a function of the size of its input.

• Let’s assume that a constant amount of time is required to execute each line of our
pseudocode. One line might take more or less time than another line, but we’ll assume
that each execution of the kth line takes ck time, where ck is a constant.
11
 Analysis of insertion sort (cont.)
• The running time of the algorithm is the sum of running times for each statement
executed.
• A statement that takes ck steps to execute and executes m times contributes ckm to the
total running time.
• The running time of an algorithm on an input of size n is usually denoted by
T (n). To compute T(n), the running time of INSERTION-SORT on an input of n values, we
sum the products of the cost and times columns.
let ti denote the number of times the while loop test in line 5 is executed for that value of i.

INSERTION-SORT(A, n) Cost Times

1 for i = 2 to n C1 n
2 key = A[i] C2 n-1
3 // Insert A[i] into the sorted subarray A[1 : i – 1]. 0 n-1
4 j=i–1 C4 n-1
5 while j > 0 and A[j] > key C5 ∑
6 A[j + 1] = A[j] C6 ∑ ( −1)
7 j=j–1 C7 ∑ ( − 1)
8 A[j + 1] = key C8 n-1

12
 Analysis of insertion sort (cont.)

• Even for inputs of a given size, an algorithm’s running time may depend on which input of
that size is given.
• For example, in INSERTION-SORT, the best case occurs when the array is already sorted.
• In this case, each time that line 5 executes, the value of key is already greater than or
equal to all values in A[1 : i – 1], so that the while loop of lines 5–7 always exits upon the
first test in line 5. Therefore, we have that ti = 1 for i = 2, 3, … , n, and the best-case
running time is given by

We can express this running time as an + b for constants a and b that depend on the
statement costs ck (where a = c1 + c2 + c4 + c5 + c8 and b = c2 + c4 + c5 + c8).
The running time is thus a linear function of n.
13
 Analysis of insertion sort (cont.)
• The worst case arises when the array is in reverse sorted order.
• The procedure must compare each element A[i] with each element in the entire sorted
subarray A[1 : i – 1], and so ti = i for i = 2, 3, … , n

The running time of INSERTION-SORT in the worst-case is

We can express this worst-case
running time as an2 + bn + c for
constants a, b, and c that again
depend on the statement costs
ck.
The running time is thus a
quadratic function of n.

14
 The worst-case analysis
• We’ll usually concentrate on finding only the worst-case running time, that is, the longest
running time for any input of size n.
Why? Here are three reasons:
– The worst-case running time of an algorithm gives an upper bound on the running
time for any input. If you know it, then you have a guarantee that the algorithm never
takes any longer.
– For some algorithms, the worst case occurs fairly often. In some applications,
searches for absent information may be frequent.
– The “average case” is often roughly as bad as the worst case.
• We usually consider one algorithm to be more efficient than another if its worst-case
running time has a lower order of growth.
• A “fast algorithm” is an algorithm whose worst-case running time grows slowly with the
input size.

But, what does “order of growth” mean?

15
 Order of growth
• The “order of growth” will be defined precisely in next chapter,
here I will give you an introduction.
• In order to ease our analysis of the INSERTION-SORT procedure,
we used some simplifying abstractions.
• We consider only the leading term of a formula (e.g., an2), since
the lower-order terms are relatively insignificant for large values
of n.
• We also ignore the leading term’s constant coefficient, since
constant factors are less significant than the rate of growth in
determining computational efficiency for large inputs.
• For insertion sort’s worst-case running time, when we ignore the
lower-order terms and the leading term’s constant coefficient,
only the factor of n2 from the leading term remains. That factor,
n2, is by far the most important part of the running time.
16
 Designing algorithms
• The insertion sort has quadratic running time, meaning that the
number of operations performed on arrays of length n scales with
n2, the square of the input size.
Can we do better?
• We’ll use divide-and-conquer to design a sorting algorithm whose
worst-case running time is much less than that of insertion sort.
• By using the divide-and-conquer paradigm, the MergeSort
algorithm improves dramatically over the insertion sorting
algorithm.
• The algorithms, that follow the divide-and-conquer method, break
the problem into several subproblems that are similar to the
original problem but smaller in size, solve the subproblems
recursively, and then combine these solutions to create a solution
to the original problem.
17
 The divide and conquer paradigm
• In the divide-and-conquer method,
– if the problem is small enough—the base case— you just
solve it directly without recursing.
– Otherwise—the recursive case—you perform three
characteristic steps:
• Divide the problem into one or more subproblems that
are smaller instances of the same problem.
• Conquer the subproblems by solving them recursively.
• Combine the subproblem solutions to form a solution
to the original problem.

18
 The Merge-Sort algorithm
• The merge sort algorithm closely follows the divide-and-
conquer method.
• In each step, it sorts a subarray A[p : r], starting with the entire
array A[1 : n] and recursing down to smaller and smaller
subarrays.
• Here is how merge sort operates:
– Divide the subarray A[p : r] to be sorted into two adjacent subarrays,
each of half the size. To do so, compute the midpoint q of A[p : r] and
divide A[p : r] into subarrays A[p : q] and A[q + 1 : r].
– Conquer by sorting each of the two subarrays A[p : q] and A[q + 1 : r]
recursively using merge sort.
– Combine by merging the two sorted subarrays A[p : q] and A[q + 1 : r]
back into A[p : r], producing the sorted answer.
• The key operation of the merge sort algorithm occurs in the “combine” step, which
merges two adjacent, sorted subarrays. The merge operation is performed by the
auxiliary procedure MERGE(A, p,q, r)

19
 The Merge-Sort algorithm (cont.)

Figure 1.3, Algorithms Illuminated: Part 1: The Basics, page 15

20
 The Merge-Sort algorithm
The Merge procedure
• MERGE(A, p, q, r)
1 nL = q – p + 1 // length of A[p : q]
2 nR = r – q // length of A[q + 1 : r]
3 let L[0 : nL – 1] and R[0 : nR – 1] be new arrays
4 for i = 0 to nL – 1 // copy A[p : q] into L[0 : nL – 1]
5 L[i] = A[p + i]
6 for j = 0 to nR – 1 // copy A[q + 1 : r] into R[0 : nR – 1]
7 R[j] = A[q + j + 1]
8 i = 0 // i indexes the smallest remaining element in L
9 j = 0 // j indexes the smallest remaining element in R
10k = p // k indexes the location in A to fill
11// As long as each of the arrays L and R contains an unmerged element,
//copy the smallest unmerged element back into A[p : r].
12while i < nL and j < nR
13 if L[i] ≤ R[j]
14 A[k] = L[i]
15 i = i + 1
16 else A[k] = R[j]
17 j = j + 1
18 k = k + 1
21
 The Merge-Sort procedure
• 19// Having gone through one of L and R entirely, copy the
//remainder of the other to the end of A[p : r].
20while i < nL
21 A[k] = L[i]
22 i = i + 1
23 k = k + 1
24while j < nR
25 A[k] = R[j]
26 j = j + 1
27 k = k + 1

MERGE-SORT(A, p, r)
1 if p ≥ r // zero or one element?
2 return
3q = ⌊(p + r)/2⌋ // midpoint of A[p : r]
4 MERGE-SORT(A, p, q) // recursively sort A[p : q]
5 MERGE-SORT(A, q + 1, r) // recursively sort A[q + 1 : r]
6 // Merge A[p : q] and A[q + 1 : r] into A[p : r].
7 MERGE(A, p, q, r)

22
 Example

Figure 2.4, Introduction to algorithms, page 72

23
 Running Time of The Merge procedure
• What is the number of operations performed by a
single invocation of the Merge subroutine when called
on two sorted arrays of length n/2 each?
• By inspecting the code of the Merge subroutine, we can
easily find that the for and while loops are executed in a
total of n times.
• Each iteration of each loop performs comparisons,
assignments, increments and other operations that take
a constant amount of time.
• The running time of the Merge procedure is thus a
linear function of n.

24
Running Time of The Merge-SORT procedure
• The running times of simpler sorting algorithms, like SelectionSort,
InsertionSort, and BubbleSort, depend quadratically on the input size n,
meaning that the number of operations required scales as a constant times n2.
• A recursive divide-and-conquer approach results in a faster sorting algorithm
than more straightforward methods. HOW?
• For simplicity, we assume that the input array length n is a power of 2.
• We will draw a recursion tree to write out all the work done by a recursive
algorithm in a tree structure, with nodes of the tree corresponding to
recursive calls, and the children of a node corresponding to the recursive calls
made by that node.
• The recursion tree will help us to identify two things: the number of distinct
subproblems at a given recursion level j, and the length of the input to each of these
subproblems.

25
Running Time of The Merge-SORT procedure (cont.)

Figure 1.5, Algorithms Illuminated: Part 1: The Basics, page 22

26
 Running Time of The Merge-SORT procedure (cont.)
Quizzes
• Quiz1
• Fill in the blanks in the following statement:
at each level j = 0, 1, 2, . . . of the recursion tree, there are [blank] subproblems, each
operating on a subarray of length [blank].
a) 2j and 2j, respectively
b) n/ 2j and n/ 2j, respectively
c) 2j and n/ 2j, respectively
d) n/ 2j and 2j, respectively
• Quiz2
• How many levels does this recursion tree have, as a function of the length n of the
input array?
a) A constant number (independent of n)
b) log2 n
c)
d) n

27
 Running Time of The Merge-SORT procedure (cont.)

• Now, we can express the total work done by level-j recursive calls as:

• We can conclude that the operations performed across all the recursive calls at the jth
recursion level take an amount of time which is a linear function of n.
• The recursion tree has log2(n) + 1 levels (levels 0 through log2(n), inclusive).
• The total number of operations performed across all levels of the recursion tree is:

• When we consider only the leading term of a formula c ∗ nlog , and we also ignore
the leading term’s constant coefficient c, The running time of the Merge-SORT
procedure as a function of n is .

28