Jimma University

Jimma Institute of Technology

Design and Analysis of Algorithms

For
Computer Science
Prepared by
Demeke Endalie
Course description
The course focuses on algorithm design and analysis. Design techniques such as divide-and-conquer,
dynamic programming, and greedy algorithms are covered, as are graph algorithms such as elementary
graph algorithms, breadth-first search (BFS), depth-first search (DFS), strongly-connected components,
minimum spanning tree, and shortest paths.
Objectives
By the end of this course, students will be able to:
➢ Perform algorithm analysis using the different techniques;
➢ Demonstrate the use of algorithm design techniques; and
➢ Describe the basics of computational complexity
➢ Apply advanced searching and sorting algorithms
➢ Develop, and reason about the correctness and performance of algorithms, in particular
for string
➢ Searching and graph manipulation
 Chapter one
Introduction and Elementary Data Structures

What is an algorithm? An algorithm is a set of instructions for completing a task. A computer algorithm
is a set of steps to accomplish or complete a detailed task for a computer to run. The following are some
of the characteristics of an algorithm or points to consider while developing an algorithm to solve a
given problem.
✓ It is necessary to accept input.
✓ Must provide some output (yes/no, value, etc.)
✓ Clarity - each instruction is precise and unambiguous.
✓ Finiteness - the algorithm stops after a finite number of steps.
✓ Effectiveness – Every instruction must be basic, i.e., simple.

What do we expect from an algorithm?

We expect the following points from any algorithm defined or developed to solve a problem.
a. Correctness
Correct: Algorithms must produce the right outcome. Produce an incorrect answer: Even if it fails to
give accurate results all the time still, there is a control on how often it gives the wrong result.
Approximation algorithm: Although an exact solution cannot be found, a near-optimal solution can
be found. (This is used in the optimization problem.)
b. Less resource usage
The algorithm should use as few resources as possible (in terms of time and space). Time is regarded as
the primary measure of efficiency. We are also concerned with how much computer memory the
respective algorithm uses. However, time is the most commonly dealt with resource. And the actual
running time is determined by several factors, including the computer's speed, the language in which
the algorithm is implemented, the compiler/interpreter, the programmers' skill, and so on. As a result,
the primary resource usage can be divided into 1. Memory (space) 2. Time
Time is taken by an algorithm
✓ Apostoriori Analysis is implementing an algorithm in a machine and then calculating the time
it takes the system to execute the program successfully.
✓ Performance evaluation, also known as Apriori Analysis, is carried out before implementing an
algorithm in a system. This can be done as follows:
a. The algorithm's execution time will be represented as a function of the input size. If 'n' is the
size of the input, f(n) is how long it takes.
b. The rate at which the function characterizes running time grows with input size (rate of
running time growth). The algorithm with the lowest rate of running time growth is
considered.
1.1. Growth of Functions (Asymptotic notations)
We want to be able to characterize algorithms based on their efficiency when we study them. Rather
than the exact running time, we are usually interested in the order of growth of an algorithm's running
time. This is known as symptomatic running time. Asymptotic notation is a technique for categorizing
functions based on their growth rate. Asymptotic notations are mathematical tools used to represent
algorithms' time complexity in asymptotic analysis. Big-O Notation (O-notation), Omega Notation (Ω
-notation), and Theta Notation (Θ-notation) are the three most common asymptotic notations.
 a. Big-O Notation
Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the
worst-case complexity of an algorithm. If f(n) describes the running time of an algorithm, f(n) is O(g(n))
if there exists a positive constant C and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. It returns a given
input's highest possible output value (big-O). The execution time is an upper bound on the algorithm’s
time complexity.

Mathematical representation of Big-O notation: O(g(n)) = {f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}
b. Big-Ω notation
Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the
best-case complexity of an algorithm. The execution time is a lower bound on the algorithm’s time
complexity. It is defined as the condition that allows an algorithm to complete statement execution in
the shortest amount of time. Let g and f be the function from the set of natural numbers to itself. The
function f is said to be Ω(g) if thereis a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n)
for all n ≥ n0.

Mathematical Representation of Omega notation: Ω(g(n)) = {f(n): there exist positive constants c and
n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}
c. Theta notation
Theta notation encloses the function from above and below. Since it represents the upper and the lower
bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an
algorithm. Let g and f be the function from the set of natural numbers to itself. The function f is said to
be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n)
for all n ≥ n0.
Mathematical representation of theta notation can be expressed as Θ (g(n)) = {f(n): there exist positive
constants c1, c2, and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0} Note: Θ(g) is a set
1.2. Review of Elementary Data Structures
a. Heaps
A heap is a complete binary tree, and the binary tree is a tree in which the node can have utmost two
children. The (binary) heap data structure is an array object we can view as a nearly complete binary
tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all
levels except possibly the lowest, which is filled from the left up to a point. The root of the tree is A [1],
and given the index i of a node, we can easily compute the indices of its parent, left child, and right
child:
✓ PARENT (i) => return [i/2]
✓ LEFT (i) => return 2i
✓ RIGHT (i) => return 2i+ 1

The LEFT procedure can compute 2i in one instruction by simply shifting the binary representation
of i left by a one-bit position. Similarly, the RIGHT procedure can quickly calculate 2i + 1 by shifting
the binary representation of i left by a one-bit position and then adding a 1 as the low-order bit. The
PARENT procedure can compute [i/2] by shifting i right one-bit position. Good implementations
of heapsort often implement these procedures as "macros" or "inline" procedures. There are two
kinds of binary heaps: max-heaps and min-heaps.
1. In a max-heap, the max-heap property is that for every node i other than the root, A [PARENT
(i)] >= A[i], that is, the value of a node is at most the value of its parent. Thus, the largest element
in a max-heap is stored at the root, and the subtree rooted at a node contains values no larger
than that contained at the node itself.
2. A min-heap is organized oppositely; the min-heap property is that for every node i other than
the root, A [PARENT (i) <=A[i], the smallest element in a min-heap is at the root.
Properties Heap
✓ The height of a node in a heap is the number of edges on the longest simple downward path
from the node to a leaf and
✓ The height of the heap is the height of its root.
 ✓ The height of a heap of n elements which is based on a complete binary tree is O (log n).
Maintaining the heap property
MAX-HEAPIFY is an important subroutine for manipulating max-heaps. The algorithm for
MAX_HEAPIFY is shown as follows:

At each step, the largest of the elements A[i], A[LEFT(i)], and A[RIGHT(i)] is determined, and its index
is stored in the largest. If A[i] is the largest, then the subtree rooted at node i is already a max-heap and
the procedure terminates. Otherwise, one of the two children has the largest element, and A[i ] is
swapped with A[largest], which causes node i and its children to satisfy the max-heap property. The
node indexed by largest, however, now has the original value A[i], and thus the subtree rooted at largest
might violate the max-heap property. Consequently, we call MAX-HEAPIFY recursively on that
subtree. Example {16, 4, 10, 14, 7, 9, 3, 2, 8};
Building a heap
✓ We can use the procedure MAX-HEAPIFY in a bottom-up.
✓ Build-max-heap goes through nodes other than the leaf node by running MAX-HEAPIFY.
Algorithm to build the heap
We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node varies
with the node’s height in the tree, and the heights of most nodes are small. Our tighter analysis relies on
the properties that an n-element heap has height [log n] and at most [n/2h+1] nodes of any height h. The
total cost of BUILD-MAX-HEAP as being bounded is T (n) =O (n).
b. Hashing
Hashing is converting a string of characters into a fixed-length value or key representing the original
string. Because it is faster to find an item using the shortest hashed key than the original value, hashing
is used to index and retrieve items in a database. It's also used in a lot of encryption algorithms. A hash
code is created using a key, which is a unique value. Hashing is a technique in which a given key field
value is converted into the address of the record's storage location using the same operation.
Hash Table
It is a collection of items that are stored in such a way as to make it easy to find them later. Each position
in the hash table is called a slot, can hold an item, and is named by an integer value starting at 0. The
mapping between an item and a slot where the item belongs in a hash table is called a Hash Function.
A hash function accepts a key and returns its hash coding or value. Assume we have a set of integers
54, 26, 93, 17, 77, and 31. Our first hash function required to be as "remainder method" simply takes
the item and divides it by table size, returning remainder as its hash value i.e. h item = item % (size of
the table)
1. Let us say the size of the table = 11, then
2. 54 % 11 = 10 26 % 11 = 4 93 % 11 = 5
3. 17 % 11 = 6 77 % 11 = 0 31 % 11 = 9
 key Value
54 10
26 4
93 5
17 6
77 0
31 9

Now, when we need to search for any element, we just need to divide it by the table size and get the
hash value. So, we get the O (1) search time. Now taking one more element, 44, when we apply the hash
function on 44, we get (44 % 11 = 0), But the 0 hash value already has an element 77. This problem is
called Collision. Collision: According to the Hash Function, two or more items must be in the same slot.
This is said to be called Collision.

Figure: using a hash function h to map keys to hash-table slots. Because keys K2 and k5 map to the
same slot, they collide.
a. Hashing with Chaining
In Hashing with Chaining, the element in S is stored in Hash table T [0...m-1] of size m, where m is
somewhat larger than n, the size of S. The hash table is said to have m slots. Associated with the hashing
scheme is a hash function h, which is mapping from U to {0...m-1}. Each key k ∈S is stored in location
T [h (k)], and we say that k is hashed into slot h (k). If more than one key in S hashed into the same slot,
we have a collision. In such a case, all keys that hash into the same slot are placed in a linked list
associated with that slot; this linked list is called the chain at the slot. A hash table’s load factor is
defined as ∝=n/m; it represents the average number of keys per slot. We typically operate in the range
m=θ(n), so ∝ is usually a constant generally ∝<1.

Collision Resolution by Chaining:

Collision Resolution by Chaining
In chaining, we place all the elements that hash to the same slot into the same linked list, as fig shows
that Slot j contains a pointer to the head of the list of all stored elements that hash to j; if there are no
such elements, slot j contains NIL.

Analysis of Hashing with Chaining

Given a hash table T with m slots that stores n elements, we define the load factors α for T as n/m, which
is the average number of elements stored in a chain. The worst-case running time for searching is thus
θ(n) plus the time to compute the hash function- no better than if we used one linked list for all the
elements. Clearly, hash tables are not used for their worst-case performance. The average hashing
performance depends on how well the hash function h distributes the set of keys to be stored among the
m slots.
Hashing with Open Addressing
In Open Addressing, all elements are stored in the hash table itself. Each table entry consists of a
component of the dynamic set or NIL. When searching for an item, we consistently examine table slots
until we find the desired object or have determined that the element is not in the table. Thus, the load
factor α can never exceed 1 in open addressing. The advantage of open addressing is that it avoids
Pointer. In this, we compute the sequence of slots to be examined. The extra memory freed by not
sharing pointers provides the hash table with more slots for the same amount of memory, potentially
yielding fewer collisions and faster retrieval. The process of examining the location in the hash table is
called Probing. The HASH-INSERT procedure takes as input a hash table T and a key k

HASH-INSERT (T, k)
 1. i ← 0
2. repeat j ← h (k, i)
3. if T [j] = NIL
4. then T [j] ← k
5. return j
6. else ← i= i +1
7. until i=m
8. error "hash table overflow"
The procedure HASH-SEARCH takes as input a hash table T and a key k, returning j if it finds that slot
j contains key k or NIL if key k is not present in table T.

HASH-SEARCH.T (k)
1. i ← 0
2. repeat j ← h (k, i)
3. if T [j] =j
4. then return j
5. i ← i+1
6. until T [j] = NIL or i=m
7. return NIL

Advantages of hash table

✓ If U (Universe of keys) is large, storing a table T of size [U] may be impossible.
✓ Set k of keys may be small relative to U, so space allocated for T will waste.
So, Hash Table requires less storage. Indirect addressing element with key k is stored in slot k with
hashing it is stored in h (k) where h is a hash fn and hash (k) is the value of key k. Hash fn required
array range.
Application of Hash Tables
Some applications of Hash Tables are:
✓ Database System: Specifically, those that are required efficient random access. Usually, database
systems try to develop between two types of access methods: sequential and random. Hash Table
is an integral part of efficient random access because they provide a way to locate data constantly.
✓ Symbol Tables: The tables utilized by compilers to maintain data about symbols from a program.
Compilers access information about symbols frequently. Therefore, it is essential that symbol
tables be implemented very efficiently.
✓ Data Dictionaries: Data Structure that supports adding, deleting, and searching for data. Although
the operation of hash tables and a data dictionary are similar, other Data Structures may be used
to implement data dictionaries.
✓ Associative Arrays: Associative Arrays consist of data arranged so that one array's nth elements
correspond to another's nth element. Associative Arrays are helpful for indexing a logical data
grouping by several key fields.

c. Set operation
Union of Sets: Union of Sets A and B are defined to be the set of all those elements which belong to A
or B or both and is denoted by A∪B. A∪B = {x: x ∈ A or x ∈ B}
Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}
A∪B = {1, 2, 3, 4, 5, 6}.

2. Divide and conquer

2.1. The General Method of Divide and Conquer

Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design takes a dispute on a
huge input, breaks the input into minor pieces, decides the problem on each of the small pieces, and then
merges the piecewise solutions into a global solution. This mechanism of solving the problem is called
the Divide & Conquer Strategy. Divide and Conquer algorithm consists of a dispute using the following
three steps.

a) Divide the original problem into a set of subproblems.

b) Conquer: Solve every subproblem individually, recursively.
c) Combine: Put together the solutions of the subproblems to get the solution to the whole problem.

Control Abstraction of Divide and Conquer A control abstraction is a procedure whose control flow is
clear but whose primary operations are specified by other procedures whose precise meanings are
undefined. The control abstraction for the divide and conquer technique is DANDC(P), where P is the
problem to be solved.

DANDC (P) {
if SMALL (P), then return S (p);
else {divide p into smaller instances p1, p2, …. Pk, k  1;
apply DANDC to each of these sub-problems;
return (COMBINE (DANDC (p1), DANDC (p2)., DANDC (pk));}}

SMALL (P) is a Boolean-valued function that determines whether the input size is small enough to
compute the answer without splitting. If this is so, function ‘S’ is invoked otherwise, the problem ‘p’ is
into small sub-problems. These sub-problems p1, p2, . . ., pk are solved by recursive application of
DANDC.

2.2. Binary Search

If we have ‘n’ records that have been ordered by keys, so that x1 < x2 < … < xn. When we are given an
element ‘x’, binary search is used to find the corresponding element from the list. If ‘x’ is present, we
must determine a value ‘j’ such that a[j] = x (successful search). If ‘x’ is not in the list, then j is to be set
to zero (unsuccessful search). In Binary search, we jump into the middle of the file, finding key a[mid],
and compare ‘x’ with a[mid]. If x = a[mid], the desired record has been found. If x < a[mid], then ‘x’
must be in that portion of the file that precedes a[mid], if there is one at all. Similarly, if a[mid] < x, then
a further search is only necessary for that part of the file which follows a[mid].
If we use a recursive procedure of finding the middle key a[mid] of the un-searched portion of a file,
then every unsuccessful comparison of ‘x’ with a[mid] will eliminate roughly half the un-searched
portion from consideration. Since the array size is roughly halved often each comparison between ‘x’
and a[mid], and since an array of length ‘n’ can be halved only about log2n times before reaching a
trivial length, the worst-case complexity of Binary search is about log2n.
Algorithm
BinarySearch (a, n, x)
// array a (1: n) of elements in increasing order, n 0,
// determine whether ‘x’ is present, and if so, set j such that x = a(j)
// else return j
{
low =1; high =n;
while (low <= high)
{
mid = (low + high)/2;
if (x < a [mid]) then high=mid – 1;
else if (x > a [mid]) then low= mid + 1
else return mid;}
return 0;}
low and high are integer variables such that each time through the loop, either ‘x’ is found, low is
increased by at least one, or high is decreased by at least one. Thus, we have two sequences of integers
approaching each other, and eventually, low will become greater than high, causing termination in a
finite number of steps if ‘x’ is not present.
Example: Let us illustrate binary search on the following 9 elements:
Index 1 2 3 4 5 6 7 8 9
Element -15 -6 0 7 9 23 54 60 100
Search for x=100
iteration low high mid Comparison of
a[mid] with x
1 1 9 5 100>9
2 6 9 7 100>54
3 8 9 8 100>60
4 9 9 9 100=100 element
found at index 9

2.3. Finding Maximum and Minimum

A natural approach is to try a divide-and-conquer algorithm. Split the list into two sub-lists of equal
size. (Assume that the initial list size is a power of two.) Find the maxima and minima of the sub-lists.
Two more comparisons then suffice to find the maximum and minimum of the list. Hence, if T(n) is the
number of comparisons, then T(n) = 2T(n/2) + 2. (The 2T(n/2) term comes from conquering the two
problems into which we divide the original; the 2 term comes from combining these solutions.) Also,
clearly, T (2) = 1. By induction, we find T(n) = (3n/2) −2, for n a power of 2.
✓ Let P = (n, a [i]……, a [j]) denote an arbitrary instance of the problem.
✓ Here ‘n’ is the no. of elements in the list (a [i]…., a[j]) and we are interested in finding the
maximum and minimum of the list.
✓ If the list has more than 2 elements, P has to be divided into smaller instances.
 ✓ For example, we might divide ‘P’ into the 2 instances, P1=([n/2], a [1] ……..., a[n/2]) & P2= (
n-[n/2], a[[n/2]+1],….., a[n]) After having divided ‘P’ into 2 smaller sub-problems, we can solve
them by recursively invoking the same divide-and-conquer algorithm.
Algorithm

Example
Time Complexity
If T(n) represents this no., then the resulting recurrence relations are
T (n)=T([n/2] +T[n/2] +2 n>2
1 n=2
1 n=1
When ‘n’ is a power of 2, n=2k for some positive integer ‘k’, then
T (n) = 2T(n/2) +2
= 2(2T(n/4) +2) +2
= 4T(n/4) +4+2
*
*
= 2k-1 T (2) + Σ 1 ≤ I ≤ k-1 ≤ 2i
= 2k-1+ 2k - 2
T(n) = (3n/2) – 2
Note that (3n/2) - 2 is the best-average and worst-case no. of comparisons when ‘n’ is a power of 2.
2.4. Merge Sort
It is one of the well-known divide-and-conquer algorithms. This is a simple and very efficient algorithm
for sorting a list of numbers. We are given a sequence of n numbers, which we will assume is stored in
an array A [1...n]. The objective is to output a permutation of this sequence, sorted in increasing order.
This is normally done by permuting the elements within array A. How can we apply divide-and-conquer
to sorting? Here are the major elements of the Merge Sort algorithm.
✓ Divide: Split A down the middle into two sub-sequences, each of size roughly n/2.
✓ Conquer: Sort each subsequence (by calling MergeSort recursively on each)
✓ Combine: Merge the two sorted sub-sequences into a single sorted list.
The dividing process ends when we split the sub-sequences into a single item. A sequence of length
is trivially sorted. The key operation where all the work is done is by combined module, which
merges two sorted lists into a single sorted list. It turns out that the merging process is quite easy to
implement. The following figure gives a high-level view of the algorithm. The “divide” phase is
shown on the left. It works top-down splitting up the list into smaller sub-lists. The “conquer and
combine” phases are shown on the right. They work bottom-up, merging sorted lists into larger
sorted lists.
Designing the Merge Sort algorithm top-down. We’ll assume that the procedure that merges two
sorted lists is available to us. We’ll implement it later because the algorithm is called recursively on
sub-lists. in addition to passing in the array itself, we will pass in two indices, which indicate the
first and last indices of the subarray that we are to sort. The call MergeSort (A, p, r) will sort the
sub-array A [ p..r ] and return the sorted result in the same subarray. Here is the overview. If r = p,
then this means that there is only one element to sort, and we may return immediately. Otherwise
(if p < r) there are at least two elements, and we will invoke the divide-and-conquer. We find the
index q, midway between p and r, namely q = (p + r ) / 2 (rounded down to the nearest integer).
Then we split the array into subarrays A [ p..q ] and A [ q+ 1 ..r ] . Call Merge Sort recursively to
sort each subarray. Finally, we invoke a procedure (which we have yet to write) that merges these
two subarrays into a single sorted array.
Algorithm

MergeSort(array A, int p, int r) {

if(p < r) { // we have at least 2 items
q = (p + r)/2
MergeSort (A, p, q) // sort A[p..q]
MergeSort (A, q+1, r) // sort A[q+1..r]
Merge (A, p, q, r) // merge everything together
}

Merging: All left is to describe the procedure that merges two sorted lists. Merge (A, p, q, r) assumes
that the left subarray, A [ p..q ], and the right subarray, A [ q + 1 ..r ], have already been sorted. We
merge these two subarrays by copying the elements to a temporary working array called B. For
convenience; we assume that array B has the same index range A, B [ p..r ]. We have to indices i
and j, that point to the current elements of each subarray. We move the smaller element into the next
position of B (indicated by index k) and then increment the corresponding index (either i or j). When
we run out of elements in one array, we copy the other into B. Finally, we copy the entire contents
of B back into A.
Algorithm
Merge (array A, int p, int q, int r) { // merges A[p..q] with
A[q+1..r] array B[p..r]
i=k=p //initialize pointers
j = q+1
while (i <= q and j <= r) { // while both subarrays are nonempty
if (A[i] <= A[j]) B[k++] = A[i++] // copy from left subarray
else B[k++] = A[j++] // copy from right subarray
 }
while (i <= q) B[k++] = A[i++] // copy any leftover to B
while (j <= r) B[k++] = A[j++]
for i = p to r do A[i] = B[i] // copy B back to A
}

Analysis: What remains is to analyze the running time of MergeSort. First let us consider the
running time of the procedure Merge (A, p, q, r). Let n = r − p + 1 denote the total length of both
the left and right subarrays. What is the running time of Merge as a function of n? The algorithm
contains four loops (none nested in the other). It is easy to see that each loop can be executed at
most n times. (If you are a bit more careful you can actually see that all the while-loops
together can only be executed n times in total, because each execution copies one new element to
the array B, and B only has space for n elements.) Thus the running time to Merge n items is Θ (
n ) . Let us write this without the asymptotic notation, simply as n. (We’ll see later why we do
this.
How do we describe the running time of the entire MergeSort algorithm? We will do this through a
recurrence, that is, a function defined recursively in terms of itself. To avoid circularity, the
recurrence for a given value of n is defined in terms of strictly smaller values than n. Finally, a
recurrence has some basis values (e.g., for n = 1), which are defined explicitly.
Let’s see how to apply this to MergeSort. Let T (n) denote the worst-case running time of MergeSort
on an array of length n. For concreteness, we could count whatever we like: the number of lines
of pseudocode, number of comparisons, and number of array accesses since these will only differ
by a constant factor. Since all of the real work is done in the Merge procedure, we will count the
total time spent in the Merge procedure.
First, observe that if we call MergeSort with a list containing a single element, then the running time
is a constant. Since we ignore constant factors, we can just write T (n ) =1. When we call MergeSort
with a list of length n >1, e.g., Merge (A, p, r), where r − p +1 = n, the algorithm first computes q =
(p + r) / 2. The subarray A [ p..q ], which contains q − p + 1 element You can verify that is of size
n/ 2. Thus, the remaining subarray A [ q +1 ...r] has n/ 2 elements in it. How long does it take to sort
the left subarray? We do not know this, but because n/ 2< n for n >1, we can express this as T
(n/ 2). Similarly, we can express the time that it takes to sort the right subarray as T (n/ 2). Finally,
merging both sorted lists take n time, by the comments made above. In conclusion e have T (n) =1
if n = 1, 2T (n/ 2) + n otherwise.
 2.5. Quick Sort
The characteristics of the quick sort are
✓ Worst-case running time: O (n2)
✓ Expected running time: O (n log n)
✓ Sort in place
Description of quick sort
Quick sort follows a divide-and-conquer algorithmic designing paradigm. It uses three sub-steps
to sort a subarray A [p…r]. The three steps used in the quick sort or divide-and-conquer paradigm
in general are:
I. Divide: Partition A [p to r] in two subarrays of A [p to q-1] and A [q+1 to r] where A[p to
q-1] are less than A[q] and A[q] less than all elements of A[q+1 to r]
II. Conquer: Sort the two subarrays A [p to q-1] and A [q+1 to r] by recursive call quicksort
III. Combine: Combine the sorted subarrays.
Perform the divide step by a procedure PARTITION, which returns the index q that marks the
position separating the subarrays.

To sort an entire array A, the initial call is QUICKSORT (A, 1, length [A]).
Partition (A, p, r)
1 x ← A[p]
2 i←p-1
3 j←r+1
4 while TRUE
5 do repeat j ← j - 1
6 until A[j] ≤ x
7 repeat i ← i + 1
8 until A[i] ≥ x
9 if i < j
10 then exchange A[i] ↔ A[j]
11 else return j

Given an array of n elements (e.g., integers):

If array only contains one element, return
Else
◦ Pick one element to use as pivot.

18
 ◦ Partition elements into two sub-arrays:
◦ Elements less than or equal to pivot
◦ Elements greater than pivot
◦ Quicksort two sub-arrays
◦ Return results
Example
We are given array of n integers to sort:

Step 1: There are a number of ways to pick the pivot element. In this example, we will use the
first element in the array:

Step2: partitioning the array

Given a pivot, partition the elements of the array such that the resulting array consists of:
1. One sub-array that contains elements >= pivot
2. Another sub-array that contains elements < pivot
The sub-arrays are stored in the original data array. Partitioning loops through, swapping elements
below/above pivot.

1. While data[i] <= data[pivot]

++i

19
Since 10 is less than or equal to 40 increment i and get i=3

Now the value of data [3] is not less than or equal to data [pivot], then we go to the second rule
i.e., While data[j] > data [pivot]
--j

Now i is less than j and data[i] is greater than data [pivot] and data[j] is less than data [pivot] then
we swap data[i] and data[j].

Gives us

20
Then if the value of j is greater than i then go the first step

Since data[i] is greater than data [pivot] go to the second rule

At this time the value of i<j and data[i] >data[pivot] and data[j]<data[pivot]
Swap value of data[i] with data[j]

21
Go to the first condition and data[i]< data[pivot]
i++

data[i]>data[pivot] then go to the second condition

Continue until data[j] <data [pivot]

at this point i<j is false then

Swap data[j] and data[pivot_index]

22
Then the data 40 get its correct position which means all the elements to the left of it is less than
or equal to it and the element to the right of 40 are all grater that it.
Then the partition result

Exercise
Do the same operation to
7 20 10 30 40
Left sub-array

50 60 80 90
Right sub-array
Finally, you need combine every elements of the array without any operation.
Performance of Quick sort
The running time of Quicksort depends on the partitioning of the subarrays:
✓ If the subarrays are balanced, then Quicksort can run as fast as merge sort.
✓ If they are unbalanced, then Quicksort can run as slowly as insertion sort.
Worst case
Occurs when the subarrays are completely unbalanced. Have 0 elements in one subarray and n -
1 elements in the other subarray. Get the recurrence
T(n) = T (n - 1) + T (0) + Θ (n)
= T (n - 1) + Θ (n)

23
= O (n2).
Same running time as insertion sort. In fact, the worst-case running time occurs when Quicksort
takes a sorted array as input, but insertion sort runs in O (n) time in this case.
Best case
Occurs when the subarrays are completely balanced every time.
Each subarray has ≤ n/2 elements.
Get the recurrence
T (n) = 2T (n/2) + Θ (n)
= O(n logn).
Randomized version of quicksort
➢ Selecting the pivot point using some randomize technique which is called as random
sampling.
➢ The change over the partition and quicksort is small.
➢ In the new partition procedure, we perform swapping before partitioning
Algorithm

2.6. Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based
algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted
part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost element,
and that element becomes a part of the sorted array. This process continues moving unsorted array

24
boundary by one element to the right. This algorithm is unsuitable for large data sets as its average
and worst-case complexity is Ο(n2), where n is the number of items.
Algorithm

selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < current minimum
set element as new minimum
swap minimum with the first unsorted position
end selectionSort

Example: illustrate how selection sort sorts the array

18 10 7 20 2

25
Time complexity
✓ Best Case Complexity - It occurs when no sorting is required, i.e., the array is already
sorted. The best-case time complexity of the selection sort is O(n2).
✓ Average Case Complexity - It occurs when the array elements are in jumbled order that is
not properly ascending or descending. The average case time complexity of the selection
sort is O(n2).

26
 ✓ Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of the selection
sort is O(n2).

3. Greedy algorithms
3.1. Introduction to greedy algorithms
The greedy method is one of the strategies like Divide and conquers used to solve problems. This
method is used for solving optimization problems. An optimization problem is a problem that
demands either maximum or minimum results.
The Greedy method is the most straightforward approach. It is not an algorithm, but it is a
technique. The main function of this approach is that the decision is taken based on the currently
available information. This technique determines the feasible solution that may or may not be
optimal. The feasible solution is a subset that satisfies the given criteria. The optimal solution is
the solution that is the best and the most favorable in the subset. In the case of feasible, if more
than one solution satisfies the given criteria then those solutions will be considered feasible,
whereas the optimal solution is the best solution among all the solutions.
The components that can be used in the greedy algorithm are:
✓ Candidate set: A solution that is created from the set is known as a candidate set.
✓ Selection function: This function chooses the candidate or subset that can be added to the
solution.
✓ Feasibility function: A function that is used to determine whether the candidate or subset
can be used to contribute to the solution or not.
✓ Objective function: A function assigns the value to the solution or the partial solution.
✓ Solution function: This function is used to intimate whether the complete function has been
reached or not.
Applications of Greedy Algorithm
✓ It is used in finding the shortest path.
✓ It is used to find the minimum spanning tree using Prim’s or Kruskal’s algorithms.
✓ It is used in job sequencing with a deadline.
✓ This algorithm is also used to solve the fractional knapsack problem.
The general control of greedy algorithm is shown as follows
Algorithm Greedy (a, n){ // a(1 : n) contains the ‘n’ inputs
solution = ; // initialize the solution to empty
For (i=1 to n) {
x = select (a);
if feasible (solution, x)
then solution= Union (Solution, x); }
return solution; }
Procedure Greedy describes how a greedy-based algorithm will look once a particular problem is
chosen and the functions selected, feasible, and union is properly implemented. The function select
selects an input from ‘a’ removes it, and assigns its value to ‘x.’ Feasible is a Boolean valued

27
function, which determines if ‘x’ can be included into the solution vector. The function Union
combines ‘x’ with solution and updates the objective function
3.2. Minimum Cost Spanning Tree
A spanning tree for a connected graph is a tree whose vertex set is the same as the vertex set of the
given graph, and whose edge set is a subset of the edge set of the given graph. i.e., any connected
graph will have a spanning tree. Weight of a spanning tree w (T) is the sum of weights of all edges
in T. The Minimum spanning tree (MST) is a spanning tree with the smallest possible weight.
If we consider a weighted graph, all the spanning trees generated from the graph have different
weights. The weight of the spanning tree is the sum of the weights of its edges. The spanning tree
with minimum weight is called the minimum spanning tree (MST). A greedy method to obtain the
minimum spanning tree would construct the tree edge by edge, where each edge is chosen to
account for some optimization criterion. An obvious criterion would be to choose an edge that
adds a minimum weight to the total weight of the edges selected so far. Let G = (V, E) be the
graph, with V being the set of vertices and E being the set of edges, and |V|= n. G′= (V, E′) is a
subgraph of G in which all the vertices of graph G are connected with the fewest number of edges.
The smallest number of edges required to correct all of a graph's vertices is G in n - 1. The spanning
tree is very important in the design of efficient algorithms. There are two ways in which this
criterion can be achieved.
➢ The set of edges selected so far always forms a tree, and the next edge to be added is such
that not only it adds a minimum weight, but also forms a tree with the previous edges; it
can be shown that the algorithm results in a minimum cost tree; this algorithm is called
Prim’s algorithm.
➢ The edges are considered in nondecreasing order of weight; the set T of edges at each stage
is such that it is possible to complete T into a tree; thus, T may not be a tree at all steps of
the algorithm; this also results in a minimum cost tree; this algorithm is called Kruskal’s
algorithm.
Prim’s algorithm
This algorithm starts with a tree with only one edge, the minimum weight edge. The edges (j, q)
are added one by one such that node j is already included, node q is not included and weight wt (j,
q) is the minimum amongst all the edges (x, y) for which x is in the tree and y is not. To execute
this algorithm efficiently, we have a node index near(j) associated with each node j that is not yet
included in the tree. If a node is included in the tree, near(j) = 0. The node near(j) is selected into
the tree such that wt (j, near(j)) is the minimum amongst all possible choices for near(j).
Steps for finding MST using Prim's Algorithm:
1. Create MST set that keeps track of vertices already included in MST.
2. Assign key values to all vertices in the input graph. Initialize all key values as INFINITE
(∞). Assign key values like 0 for the first vertex so that it is picked first.
3. While MST set doesn't include all vertices.
1. Pick vertex u, which is not MST set and has minimum key value. Include 'u' in MST
set.

28
 2. Update the key value of all adjacent vertices of u. To update, iterate through all
adjacent vertices. For every adjacent vertex v, if the weight of edge u.v is less than
the previous key value of v, update the key value as a weight of u.v.

MST-PRIM (G, w, r)
1. for each u ∈ V [G]
2. do key [u] ← ∞
3. π [u] ← NIL
4. key [r] ← 0
5. Q ← V [G]
6. While Q? ∅
7. do u ← EXTRACT - MIN (Q)
8. for each v ∈ Adj [u]
9. do if v ∈ Q and w (u, v) < key [v]
10. then π [v] ← u
11. key [v] ← w (u, v)

Example: Now, let's see the working of prim's algorithm using an example. It will be easier to
understand the prim's algorithm using an example.

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.
Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two edges
from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among the edges,
the edge BD has the minimum weight. So, add it to the MST.

29
Step 3 - Now, again, choose the edge with the minimum weight among all the other edges. In this
case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of C, i.e.,
E and A. So, select the edge DE and add it to the MST.

Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create a cycle
in the graph. So, choose the edge CA and add it to the MST.

So, the graph produced in step 5 is the minimum spanning tree of the given graph. The cost of the
MST is 4 + 2 + 1 + 3 = 10 units.
The complexity of Prim's algorithm

30
The running time of the prim's algorithm depends upon using the data structure for the graph and
the ordering of edges.
The data structure used for the minimum edge weight Time Complexity
Adjacency matrix, linear searching O(|V|2)
Adjacency list and binary heap O (|E| log |V|)
Adjacency list and Fibonacci heap O (|E|+ |V| log |V|)
Prim's algorithm can be simply implemented by using the adjacency matrix or adjacency list graph
representation, and adding the edge with the minimum weight requires the linearly searching of an
array of weights. It requires O(|V|2) running time. It can be improved further by using the
implementation of a heap to find the minimum weight edges in the inner loop of the algorithm.
Kruskal’s Algorithm
This algorithm starts with a list of edges sorted in nondecreasing order of weights. It
repeatedly adds the smallest edge to the spanning tree that does not create a cycle. Initially,
each vertex is in its own tree in the forest. Then, the algorithm considers each edge ordered
by increasing weights. If the edge (u, v) connects two different trees, then (u, v) is added to
the set of edges of the MST, and two trees connected by an edge (u, v) are merged into a
single tree. If an edge (u, v) connects two vertices in the same tree, then edge (u, v) is discarded.
Kruskal’s algorithm for finding the MST is presented as follows. It starts with an empty set A and
selects at every stage the shortest edge that has not been chosen or rejected regardless of where
this edge is situated in the graph.
The operations and disjoint sets used for Kruskal’s algorithm are as follows:
✓ Make_set(v): create a new set whose only member is pointed to v.
✓ Find_set(v): returns a pointer to the set containing v.
✓ Union (u, v): unites the dynamic sets that contain u and v into a new set that is union of
these two sets.
Kruskal's algorithm

Now, let's see the working of Kruskal's algorithm using an example. It will be easier to understand
Kruskal's algorithm using an example. Suppose a weighted graph is -

31
The weight of the edges of the above graph is given in the below table.

Now, sort the edges given above in the ascending order of their weights.

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

32
Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle, so
discard it.
Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.
Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard
it. So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal's
algorithm is AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10. The number of edges in the above tree
equals the number of vertices minus 1. So, the algorithm stops here.
The time complexity of Kruskal’s Algorithm
Kruskal’s algorithm first creates n trees from n vertices which are done in O(n) time. Then, a heap
is created in O(n) time using the happify procedure. The least-weight edge is at the root of the
heap. Hence, the edges are deleted one by one from the heap and either added to the MST or
discarded if it forms a cycle. This deletion process requires O(nlog2n). Hence, the time complexity
of Kruskal’s algorithm is O(nlog2n).
3.3. Shortest Paths
Let us consider the graph G = (V, E), a weighting function w(e) for the edges in E, and a
source node v0. The problem is to determine the shortest path from v0 to all the remaining
nodes of G. The solution to this problem is suggested by E.W. Dijkstra and the algorithm is
popularly known as Dijkstra’s algorithm.
Dijkstra’s algorithm is one of the greedy algorithms for solving a single source shortest path
problem and provides the shortest path from a particular source vertex to all other vertices of
a given graph. Characteristics of Dijkstra’s algorithm
✓ It can be applied on both directed and undirected graph
✓ It is applied on a weighted graph
✓ It is applied on a connected graph
✓ It cannot work for negative-weight edges
✓ It assigns distance zero for the source vertex
✓ It assigns a tentative distance for other distances.
This algorithm finds the shortest paths one by one. If we have already constructed i shortest
paths, then the next path to be constructed should be the next shortest path. Let S be the set of
vertices to which the shortest paths have already been generated. For z not in S, let dist[z] be
the length of the shortest path starting from v0, going through only those vertices that are in S
and ending at z. Let u be the vertex in S to which the shortest path has already been found. If
dist[z] >dist[u] + w(u,z) then dist[z] is updated to dist[u] + w(u, z) and the predecessor of z is
set to u. Dijkstra’s algorithm is presented in Algorithm below.
Input: W[1...n][1..n] with W[i, j] = weight of edge (i, j); set W[i, j] =  if no edge

33
 Output: an array D[2...n] of distances of shortest paths to each node in [2..n]
Algorithm:
1. C = {2, 3…,n} // the set of remaining nodes
2. for i = 2 to n do D[i] = W [1, i] // initialize distance from node 1 to node I
3. repeat the following n – 2 times // determine the shortest distances
a. Select node v of set C that has the minimum value in array D
b. C = C – {v} // delete node v from set C
c. for each node w in C do
if (D[v] + W [v, w] < D[w]) then
D[w] = D[v] + W [v, w] // update D[w] if found shorter path to w

Time complexity is O(n2)

Example:

34
 3.4. Scheduling

4. Dynamic programming
4.1. Introduction to dynamic programming

Dynamic programming is a technique that breaks the problems into sub-problems and saves the
result for future purposes so that we do not need to compute the result again. The subproblems are
optimized to optimize the overall solution is known as the optimal substructure property. The main
use of dynamic programming is to solve optimization problems. Here, optimization problems
mean that when we are trying to find out the minimum or the maximum solution to a problem.
Dynamic programming guarantees finding the optimal solution to a problem if the solution exists.
The definition of dynamic programming says that it is a technique for solving a complex problem
by first breaking into a collection of simpler subproblems, solving each subproblem just once, and
then storing their solutions to avoid repetitive computations. The following are the steps that the
dynamic programming follows:
✓ It breaks down the complex problem into simpler subproblems.
✓ It finds the optimal solution to these sub-problems.
✓ It stores the results of subproblems (memorization). The process of storing the results of
subproblems is known as memorization.
✓ It reuses them so that the same sub-problem is calculated more than once.
✓ Finally, calculate the result of the complex problem.

35
The above five steps are the basic steps for dynamic programming. Dynamic programming is
applicable that has properties such as those problems that are having overlapping subproblems and
optimal substructures. Here, optimal substructure means that the solution of optimization problems
can be obtained by simply combining the optimal solution of all the subproblems. In the case of
dynamic programming, the space complexity would be increased as we are storing the intermediate
results, but the time complexity would be decreased.
Approaches of dynamic programming
Dynamic programming can be applied in two ways:
a. Top-down approach
b. Bottom-up approach
Top-down approach
The top-down approach follows the memorization technique, while the bottom-up approach
follows the tabulation method. Here memorization is equal to the sum of recursion and caching.
Recursion means calling the function itself while caching means storing the intermediate results.
Advantages
✓ It is very easy to understand and implement.
✓ It solves the subproblems only when it is required.
✓ It is easy to debug.
Disadvantages
✓ It uses the recursion technique that occupies more memory in the call stack. Sometimes
when the recursion is too deep, the stack overflow condition will occur.
✓ It occupies more memory which degrades the overall performance.
Bottom-up approach
The bottom-up approach is also one of the techniques which can be used to implement dynamic
programming. It uses the tabulation technique to implement the dynamic programming approach.
It solves the same kind of problems but it removes the recursion. If we remove the recursion, there
is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique,
we solve the problems and store the results in a matrix.
4.2. All-pairs Shortest Path - Floyd-Warshall Algorithm
The all-pair shortest path algorithm also known as the Floyd-Warshall algorithm is used to find
all-pair shortest path problems from a given weighted graph. As a result of this algorithm, it will
generate a matrix, which will represent the minimum distance from any node to all other nodes in
the graph.
Algorithm
Input − The cost matrix of the given Graph.
Output − Matrix to for shortest path between any vertex to any vertex.

36
 Begin
for k = 0 to n, do
for i= 0 to n, do
for j= 0 to n, do
if cost[i,k] + cost[k,j] < cost[i,j], then
cost[i,j] := cost[i,k] + cost[k,j]
done
done
done
display the current cost matrix
End

Example: Apply Floyd-Warshall algorithm for constructing the shortest path. Show that matrices
D(k) and π(k) computed by the Floyd-Warshall algorithm for the graph.

Solution:

37
Step (i) When k = 0

Step (ii) When k =1

38
Step (iii) When k = 2

Step (iv) When k = 3

39
Step (v) When k = 4

40
41
Step (vi) When k = 5

The strategy adopted by the Floyd-Warshall algorithm is Dynamic Programming. The running
time of the Floyd-Warshall algorithm is determined by the triply nested loops of lines. The
algorithm thus runs in time θ (n3).
4.3. 0/1 Knapsack
We are given n objects and a knapsack. Each object i has a positive weight wi and a positive value
Vi. The knapsack can carry a weight not exceeding W. Fill the knapsack so that the value of objects
in the knapsack is optimized. A solution to the knapsack problem can be obtained by making a
sequence of decisions on the variables x1, x2, . . .., xn. A decision on variable xi involves
determining which of the values 0 or 1 is to be assigned to it. The algorithm takes the following
inputs
✓ The maximum weight W
✓ The number of items n
✓ The two sequences v=<v1, v2…vn> and w=<w1, w2…., wn>

42
Algorithm
0/1Knapsack(v,w,n,W){
for w=0 to W do
c[0,w]=0
for i=1 to n do
c[i,0]=0
for w=1 to W do
if wi<=w then
if vi+c[i-1,w-wi]>c[i-1,w] then
c[i,w]= vi+c[i-1,w-wi]
else
c[i,w]=c[i-1,w]
else
c[i,w]=c[i-1,w]
}
Set of items to take can be deduced from the table starting from c[n,w] and tracing backwards
where the optimal values come frome. If c[i,w]=c[i-1,w], then item i is not part of the solution,
and we continue tracing with c[i-1,w]. Otherwise, item i is part of the solution, and we continue
tracing with c[i-1,w-W]
Example: let us illustrate how a knapsack is working using dynamic programming. Given
maximum capacity of the knapsack is W=8.
item Weighs Value
1 3 2
2 4 3
3 5 1
4 6 4
Solution
First, we need to create a matrix having row=n+1 and column=W+1 i.e.,
When i=1, wi=3, v1=2
w=1, check for wi<=w which is 3<=1 false then c[1,1]=c[0,1]=0
w=2, check for wi<=w which is 3<=2 false then c[1,2]=c[0,2]=0
w=3, check for wi<=w which is 3<=3 true then c[1,3]=max{2+c[0,0],c[[0,3]}=2
w=4, check for wi<=w, which is 3<=4 true then [1,4]=max{2+c[0,1],c[[0,4]}=2
w=5, check for wi<=w, which is 3<=5 true then [1,5]=max{2+c[0,2],c[[0,5]}=2
w=6, check for wi<=w, which is 3<=6 true then [1,6]=max{2+c[0,3],c[[0,6]}=2
w=7, check for wi<=w, which is 3<=7 true then [1,7]=max{2+c[0,4],c[[0,7]}=2
w=8, check for wi<=w, which is 3<=8 true then [1,8]=max{2+c[0,5],c[[0,8]}=2

43
when i=2, v2=3, w2=4
w=1, check for wi<=w which is 4<=1 false then c[2,1]=c[1,1]=0
w=2, check for wi<=w which is 4<=2 false then c[2,2]=c[1,2]=0
w=3, check for wi<=w which is 4<=3 false then c[2,3]=c[1,3]=2
w=4, check for wi<=w, which is 4<=4 true then [2,4]=max{3+c[1,0],c[1,4]}=3
w=5, check for wi<=w, which is 4<=5 true then [2,5]=max{3+c[1,1],c[1,5]}=3
w=6, check for wi<=w, which is 4<=6 true then [2,6]=max{3+c[1,2],c[1,6]}=3
w=7, check for wi<=w, which is 4<=7 true then [2,7]=max{3+c[1,3],c[1,7]}=5
w=8, check for wi<=w, which is 4<=8 true then [2,8]=max{3+c[1,4],c[1,8]}=5
when i=3, v3=1, w3=5
w=1, check for wi<=w which is 5<=1 false then c[3,1]=c[2,1]=0
w=2, check for wi<=w which is 5<=2 false then c[3,2]=c[2,2]=0
w=3, check for wi<=w which is 5<=3 false then c[3,3]=c[2,3]=2
w=4, check for wi<=w, which is 5<=4 false then [3,4]=c[2,4]=3
w=5, check for wi<=w, which is 5<=5 true then [3,5]=max{1+c[2,0],c[2,5]}=3
w=6, check for wi<=w, which is 5<=6 true then [3,6]=max{1+c[2,1],c[2,6]}=3
w=7, check for wi<=w, which is 5<=7 true then [3,7]=max{1+c[2,2],c[2,7]}=5
w=8, check for wi<=w, which is 5<=8 true then [3,8]=max{1+c[2,3],c[2,8]}=5
when i=4,v4=4, w4=6
w=1, check for wi<=w which is 6<=1 false then c[4,1]=c[3,1]=0
w=2, check for wi<=w which is 6<=2 false then c[4,2]=c[3,2]=0
w=3, check for wi<=w which is 6<=3 false then c[4,3]=c[3,3]=2
w=4, check for wi<=w, which is 6<=4 false then [4,4]=c[3,4]=2
w=5, check for wi<=w, which is 6<=5 false then [4,5]=c[3,5]=3
w=6, check for wi<=w, which is 6<=6 true then [4,6]=max{4+c[3,0],c[3,6]}=4
w=7, check for wi<=w, which is 6<=7 true then [4,7]=max{4+c[3,1],c[[3,7]}=5
w=8, check for wi<=w, which is 6<=8 true then [4,8] =max{4+c[3,2],c[3,8]}=5
i/w 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2 2 2
2 0 0 0 2 3 3 3 5 5

44
 3 0 0 0 2 3 3 3 5 5
4 0 0 0 2 3 3 4 5 5

Then, using the following algorithm, we'll decide which item goes in the knapsack.

i=n,j=w
while(i>0 && j>0){
if(c[i][j]==c[i-1][j]){
item i is not included
i--
}
else{
include item i
i--, j=j-wi
}
}

The solution is then {1,1,0,0} items 0ne and two are included, and the maximum benefit is 5,
which is v1+v2=2+3.
4.4. Depth First Search
Depth-first search is an algorithm for traversing or searching tree or graph data structures. The
algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a
graph) and explores as far as possible along each branch before backtracking. So, the basic idea is
to start from the root or any arbitrary node, mark the node, move to the adjacent unmarked node,
and continue this loop until there is no unmarked adjacent node. Then backtrack and check for
other unmarked nodes and traverse them. Finally, print the nodes in the path.
DFS (G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)

init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS (G, u)
}

Let's see how the Depth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.

45
We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its
adjacent vertices in the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already
been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

46
After we visit the last element, 3, it has no unvisited adjacent nodes, so we have completed the
Depth First Traversal of the graph. The time complexity of the DFS algorithm is represented in
the form of O (V + E), where V is the number of nodes and E is the number of edges.
5. Backtracking
5.1. Introduction to backtracking

Backtracking is one of the techniques that can be used to solve the problem. We can write the
algorithm using this strategy. It uses the Brute force search to solve the problem, and the brute
force search says that for the given problem, we try to make all the possible solutions and pick out
the best solution from all the desired solutions. This rule is also followed in dynamic programming,
but dynamic programming is used for solving optimization problems. In contrast, backtracking is
not used in solving optimization problems. Backtracking is used when we have multiple solutions
and we require all of those solutions.

The backtracking name itself suggests that we are going back and coming forward; if it satisfies
the condition, then return success, or else we go back again. It is used to solve a problem in which
a sequence of objects is chosen from a specified set so that the sequence satisfies some criteria.

When we have multiple choices, we make decisions from the available choices. In the following
cases, we need to use the backtracking algorithm:

✓ A piece of sufficient information is unavailable to make the best choice, so we use the
backtracking strategy to try out all the possible solutions.
✓ Each decision leads to a new set of choices. Then again, we backtrack to make new
decisions. In this case, we need to use the backtracking strategy.

Applications of Backtracking

✓ N-queen problem
✓ Sum of subset problem
✓ Graph coloring
✓ Hamilton cycle

5.2. 8 Queens Problem

N - Queens’s problem is to place n - queens in such a manner on an n x n chessboard that no queens

attack each other by being in the same row, column, or diagonal. Consider the problem of trying
to place 8 queens on a chess board such that no queen can attack another queen

47
Given an 8x8 chess board, you must place 8 queens on the board so that no two queens attack each
other. Print all possible matrices satisfying the conditions with positions with queens marked with
'1' and empty spaces with '0'. You must solve the 8 queens problem using backtracking.

✓ Note 1: A queen can move vertically, horizontally, and diagonally in any number of steps.
✓ Note 2: You can also go through the N-Queen Problem for the general approach to solving
this problem.
Example: One possible solution to the 8 queens problem using backtracking is shown below. In
the first row, the queen is at E8 square, so we have to ensure no queen is in column E and row 8
along its diagonals. Similarly, for the second row, the queen is on the B7 square. Thus, we have to
secure its horizontal, vertical, and diagonal squares. The same pattern is followed for the rest of
the queens.

Output
00001000
01000000
00010000
00000010
00100000
00000001
00000100

48
 10000000
Let's go through the steps below to understand how this algorithm of solving the 8 queens problem
using backtracking works:
✓ Step 1: Traverse all the rows in one column at a time and try to place the queen in that
position.
✓ Step 2: After coming to a new square in the left column, traverse to its left horizontal
direction to see if any queen is already placed in that row or not. If a queen is found, then
move to other rows to search for a possible position for the queen.
✓ Step 3: Like step 2, check the upper and lower left diagonals. We do not check the right side
because it's impossible to find a queen on that side of the board yet.
✓ Step 4: If the process succeeds, i.e., a queen is not found, mark the position as '1' and move
ahead.
✓ Step 5: Recursively uses the above-listed steps to reach the last column. Print the solution
matrix if a queen is successfully placed in the last column.
✓ Step 6: Backtrack to find other solutions after printing one possible solution.
Complexity Analysis
Time Complexity: O(N!), For the first column, we will have N choices, then for the next column,
we will have N-1 options, and so on. Therefore, the total time taken will be N*(N-1) *(N-2) ....,
which makes the time complexity to be O(N!).
Space Complexity: O(N), since we just maintain three linear arrays as extra storage space.

5.3. Graph coloring

Let G be a graph, and m be a given positive integer. We want to discover whether the nodes of G
can be colored so that no two adjacent nodes have the same color, yet only m colors are used. This
is termed the m-color ability decision problem. The m-color ability optimization problem asks for
the smallest integer m for which graph G can be colored. Given any map, if the regions are to be
colored so that no two adjacent regions have the same color, only four colors are needed. For many
years it was known that five colors were sufficient to color any map, but no map that required more
than four colors had ever been found. After several hundred years, this problem was solved by a
group of mathematicians with the help of a computer. They showed that in fact, four colors are
sufficient for planar graphs. The function m-coloring will begin by first assigning the graph to its
adjacency matrix, setting the array x [] to zero. The colors are represented by the integers 1, 2, . .
., m and the solutions are given by the n-tuple (x1, x2, . . ., xn), where xi is the color of node i. A
recursive backtracking algorithm for graph coloring is carried out by invoking the statement m-
coloring (1);

graphColoring(colors, colorList, vertex)

Input − Most possible colors, the list for which vertices are colored with which color, and the
starting vertex.
Output − True, when colors are assigned, otherwise false.
Begin
if all vertices are checked, then
return true

49
 for all colors col from available colors, do
if isValid(vertex, color, col), then
add col to the colorList for vertex
if graphColoring(colors, colorList, vertex+1) = true, then
return true
remove color for vertex
done
return false
End

isValid(vertex, colorList, col)

Input − Vertex, colorList to check, and color, which is trying to assign.
Output − True if the color assigning is valid, otherwise false.
Begin
for all vertices v of the graph, do
if there is an edge between v and i, and col = colorList[i], then
return false
done
return true
End

Example:

Color the graph given below with minimum number of colors by backtracking using state space
tree.

5.4. Hamiltonian Cycle

Let G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle (suggested by William
Hamilton) is a round-trip path along n edges of G that visits every vertex once and returns to its
starting position. In other vertices of G are visited in the order v1, v2, . . . . . , vn+1, then the edges
50
(vi, vi+1) are in E, 1 < i < n, and the vi are distinct expect for v1 and vn+1, which are equal. The
graph G1 contains the Hamiltonian cycle 1, 2, 8, 7, 6, 5, 4, 3, 1. The graph G2 contains no
Hamiltonian cycle.

The backtracking solution vector (x1, . . .. xn) is defined so that xi represents the ith visited vertex
of the proposed cycle. If k = 1, then x1 can be any of the n vertices. To avoid printing the same
cycle n times, we require that x1 = 1. If 1 < k < n, then xk can be any vertex v that is distinct from
x1, x2, . . ., xk–1 and v is connected by an edge to kx-1. The vertex xn can only be one remaining
vertex and it must be connected to both xn-1 and x1. Using NextValue algorithm we can
particularize the recursive backtracking schema to find all Hamiltonian cycles. This algorithm is
started by first initializing the adjacency matrix G [1: n, 1: n], then setting x [2: n] to zero and x
[1] to 1, and then executing Hamiltonian (2). The traveling salesperson problem using dynamic
programming asked for a tour that has minimum cost. This tour is a Hamiltonian cycle. For the
simple case of a graph all of whose edge costs are identical, Hamiltonian will find a minimum-
cost tour if a tour exists.

Algorithm NextValue (k)

// x [1: k-1] is a path of k – 1 distinct vertex. If x[k] = 0, then no vertex has as yet been
// assigned to x [k]. After execution, x[k] is assigned to the next highest numbered vertex
// which does not already appear in x [1: k – 1] and is connected by an edge to x [k – 1].
// Otherwise, x [k] = 0. If k = n, then in addition x [k] is connected to x [1].
{
repeat
{
x [k]= (x [k] +1) mod (n+1); // Next vertex.
If (x [k] = 0) then return;
If (G [x [k – 1], x [k]] ≠0) then
{ // Is there an edge?
for j= 1 to k – 1 do if (x [j] = x [k]) then break;
// check for distinctness.
If (j = k) then // If true, then the vertex is distinct.
If ((k < n) or ((k = n) and G [x [n], x [1]] ≠ 0))
then return;
}
} until (false);
}

51
 Algorithm
Hamiltonian (k)
// This algorithm uses the recursive formulation of backtracking to find all theHamiltonian
// cycles of a graph. The graph is stored as an adjacency matrix G [1: n, 1: n]. All cycles begin
// at node 1.
{
repeat
{ // Generate values for x [k].
NextValue (k); //Assign a legal Next value to x [k].
if (x [k] = 0) then return;
if (k = n) then write (x [1: n]);
else Hamiltonian (k + 1)
} until (false);
}

Example: Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit using
the backtracking method.

Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our implicit
tree.

Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographical order (b, c, d).

Next, we select 'c' adjacent to 'b.'

52
Next, we select 'd' adjacent to 'c.'

Next, we select 'e' adjacent to 'd.'

Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already
visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from the
partial solution.

53
From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already been
checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent
to d is e, f from which e has already been checked, and adjacent to 'f' are d and e. If 'e' vertex is,
revisited we get a dead state. So again, we backtrack one step. Now, adjacent to c is 'e' and adjacent
to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.' Here, we get the Hamiltonian Cycle as
all the vertex other than the start vertex 'a' is visited only once. (a - b - c - e - f -d - a).

54
Here we have generated one Hamiltonian circuit, but another Hamiltonian circuit can also be
obtained by considering another vertex.

5.5. Knapsack Problems

In solving of knapsack problem using backtracking the method we mostly consider the profit but
in the case of dynamic programming we consider weights. Concept of backtracking: The idea of
backtracking is to construct solutions one component at a time and evaluate such partially
constructed solutions. This partially constructed solution can be developed further without
violating the problem constraints. It is convenient to implement this kind of processing by
constructing a tree of choices being made called the "State Space Tree". Its root represents an
initial state before the search for the solution begins. The nodes of the first level in the tree represent
the choices for the first component of a solution and the nodes of the second level represent the
choices for the second component and so on.

A node in the state space tree is promising if it corresponds to the partials constructed solution that
may lead to the complete solution otherwise the nodes are called non-promising. The leaves of the
tree represent either the non-promising dead end or the complete solution found by the algorithm.
The knapsack is nothing but a sack where in which we need to place the given items according to
the capacity of the knapsack. In the case of backtracking, we consider the profits but in dynamic
programming we consider weights. Algorithm:

Bound (CP, CW, K)

{
b=CP, c=CW;
for i=k+1 to n dp
{
c=c + w [i];
if (c<m) then
b= b + p[i];
else
return b+(1-(c-m)/w[i]) *p[i];

55
 return b;
}
}
Consider:
CP=Current Profit; CW=Current Weight; K= Index; m=Capacity of Knapsack;
Example:
Profits P1=10, P2=10, P3=12, P4=18.
Weights W1= 2, W2= 4, W3= 6, W4=9;
m=15;
n=4;
Tracing:
When, i=1 C=2; b=10;
When, i=2 w[2]=4 so, c=c + w[2] c= 2+4= 6 so c= 6 if 6<15 condition gets true so
b=10+10=20;
c=6;
b=20
When, i=3 w[3]=6 so, c=c + w[3] c= 6+6= 12 so c= 12 if 12<15 condition gets true so
b=20+12=32;
c=12;
b=32
When, i=4 w[4]=9 so, c=c + w[4] c= 12+9= 21 so c= 21 if 21<15 condition gets FALSE so
b+(1-(c-m)/w[i])*p[i] is 32+(1-(21-15)/9)*18=38
c=21;
b=38;
Here we got the maximum profit as 38.
To obtain this maximum capacity we need to consider Item 4 first then Item 2 then Item 1 which
is 18+10+10 = 38.

5.6. Traveling Salesman Problems

The traveling salesman’s problems abide by a salesman and a set of cities. The salesman has to
visit every one of the cities starting from a certain one (e.g., the hometown) and return to the same
city. The challenge of the problem is that the traveling salesman needs to minimize the total length

56
of the trip. Suppose the cities are x1 x2.... xn where cost cij denotes the cost of traveling from city
xi to xj. The traveling salesperson’s problem is to find a route starting and ending at x1 that will
take all cities with the minimum cost. Let A be an array of n cities and let 1 6 ℓ 6 n be a parameter.
Let lengthSoFar be the length of the path A [1], A [2], . . ., A[ℓ] and let minCost > 0 be another
parameter. We want to compute min (minCost, L), where L is the minimum length of a tour visiting
all cities in A [1...n] under the condition that the tour starts by visiting the cities from A [1...ℓ] in
the given order. Algorithm

TSP Backtrack (A, ℓ, lengthSoFar , minCost)

n ← length[A] // number of elements in the array A
if ℓ = n
then minCost ← min (minCost, lengthSoFar + distance[A[n], A [1]])
else for i ← ℓ + 1 to n
do Swap A [ℓ + 1] and A[i] // select A[i] as the next city
newLength ← lengthSoFar + distance[A[ℓ], A [ℓ + 1]]
if newLength > minCost // this will never be a better solution
then skip // prune
else minCost ←
min (minCost, TSP Backtrack (A, ℓ + 1, newLength, minCost))
Swap A [ℓ + 1] and A[i] // undo the selection
return minCost

6. Probabilistic Algorithms
6.1. Introduction to Probabilistic Algorithms
Build algorithms using a ‘random’ element so as gain improved performance. In some cases,
improved performance is very dramatic, moving from intractable to tractable. Often however, there
is some loss in the reliability of results: either no result at all may be produced, or an incorrect
result may be returned, or, for numerical results, an approximate answer may be produced. Because
of the random element, different runs may produce different results and therefore the reliability of
results may be improved with multiple runs.
Classification of probabilistic algorithms
There is a variety of behaviors associated with probabilistic algorithms:
✓ Algorithms always return a result, but the result may not always be correct. We attempt to
minimize the probability of an incorrect result, and using the random element, multiple
runs of the algorithm will reduce the probability of incorrect results. These are sometimes
called Monte Carlo algorithms. Terminology has not been fixed and varies with the author.
✓ Algorithms that never return an incorrect result, but may not produce results at all on some
runs. Again, we wish to minimize the probability of no result, and, because of the random
element, multiple runs will reduce the probability of no result.
✓ Algorithms which always return a result and the correct result, but where a random element
increases the efficiency, by avoiding or reducing the probability of worst-case behavior.

57
 Useful for algorithms that have a poor worst-case behavior but a good average-case
behavior. These are sometimes called Sherwood algorithms, cf. Robin Hood!
✓ Numerical approximation algorithms. Here the random element allows us to get
approximate numerical results, often much faster than direct methods, and multiple runs
will provide an increasing approximation.
Random numbers
The random element required by probabilistic algorithms is provided by a random number
generator. Random number generators have been devised to generate sequences of numbers that
behave as though they were random, in that they pass various ‘tests of randomness. Such sequences
are sometimes called ‘pseudo-random’. A variety of methods have been proposed. These all
generate numbers in a specific range and require an initial element, called the seed, to begin the
generation. Each number in the sequence is computed from its predecessor.
These methods have several disadvantages: Because numbers are generated from predecessors, if
a number re-occurs, then the sequence cycles repeatedly. It is intended that different choices
generate different pseudo-random sequences, but if a choice coincides with an entry in any
sequence it will generate the remainder of this sequence. The analysis of the randomness and
reliability of these pseudo-random sequences is, in general, very difficult.
Example: Middle squares method
Consider 4-digit numbers. Repeat the following: Square the number and take the middle 4 digits
of the square. For example, beginning with 1234, the square is 1522756. Take 5227 as the next
entry, the square is 27321529. The next number is 3215. The sequence is 1234, 5227, 3215, 3362,
3030, 1809, 2728, ...
This is not a reliable method: for some seeds, it will repeat itself fairly quickly, and the selection
of numbers may not be very uniform in the interval. Zeros tend to propagate.
6.2. Parallel Algorithms
A parallel algorithm is an algorithm that can execute several instructions simultaneously on
different processing devices and then combine all the individual outputs to produce the final result.
Parallel Algorithm is the problem divided into sub-problems and is executed in parallel to get
individual outputs. Later on, these individual outputs are combined together to get the final desired
output. It is not easy to divide a large problem into sub-problems. Sub-problems may have data
dependency among them. Therefore, the processors have to communicate with each other to solve
the problem. It has been found that the time needed by the processors in communicating with each
other is more than the actual processing time. So, while designing a parallel algorithm, proper CPU
utilization should be considered to get an efficient algorithm.
Run time complexity
Analysis of an algorithm helps us determine whether the algorithm is useful or not. Generally, an
algorithm is analyzed based on its execution time (Time Complexity) and the amount of space
(Space Complexity) it requires. Since we have sophisticated memory devices available at a
reasonable cost, storage space is no longer an issue. Hence, space complexity is not given so much
of importance. Parallel algorithms are designed to improve the computation speed of a computer.
For analyzing a Parallel Algorithm, we normally consider the following parameters:

58
 ✓ Time complexity (Execution Time),
✓ Total number of processors used, and
✓ Total cost.

59