Mizan-Tepi University

School of Computing and Informatics

Department of Computer Science
Module

Analysis of Algorithm

Prepared by:
Mr. Getahun Tadesse
Mr. Bikila Abebe

September 6, 2022

Mizan-Tepi University
 1. Module Description

This module aims to equip the learners with the skills to design, analysis, compare and implement
a range of important and commonly used algorithms across a number of problem domains. Over
view of the basic data structures; design techniques: divide-and-conquer, dynamic programming,
greedy algorithms, and graph algorithms: Elementary graph algorithms, Breadth-first search
(BFS), Depth-first search (DFS), Strongly- connected components, Minimum spanning tree, and
shortest paths are included in details.

2. Course Goals or Learning Outcomes:

By the end of this module, students will be able to do the following

» 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
3. Syllabus
Chapter One: - Introduction and elementary data structures
Chapter Two: - Divide – and – conquer
Chapter Three: - Greedy Model
Chapter Four: - Dynamic Programming and traversal techniques
Chapter Five: - Back Tracking

[i]
 Table of Contents
List of Figures ................................................................................................................................ iv
Chapter One .................................................................................................................................... 1
1. Introduction and Elementary Data structures .......................................................................... 1
1.1 Order Notation.................................................................................................................. 1
1.2 Analysis of algorithm ....................................................................................................... 3
1.3 Review of elementary data structures ............................................................................ 10
1.4 Heap and Heap Sort........................................................................................................ 13
1.5 Hashing........................................................................................................................... 17
1.6 Sets Representation ........................................................................................................ 20
1.7 UNION, FIND operation................................................................................................ 21
Chapter One Review Questions ................................................................................................ 24
Chapter -Two ................................................................................................................................ 25
2. Divide – and – conquer .......................................................................................................... 25
2.1 General Method .............................................................................................................. 25
2.2 Binary Search ................................................................................................................. 26
2.3 Finding Maximum and Minimum .................................................................................. 28
2.4 Merge Sort ...................................................................................................................... 30
2.4.1 Analysis of Merge Sort ........................................................................................... 35
2.5 Quick sort ....................................................................................................................... 37
2.6 Selection Sort ................................................................................................................. 41
Chapter two Review Questions ................................................................................................. 42
Chapter Three................................................................................................................................ 43
3. Greedy Model ........................................................................................................................ 43
3.1 Overview of Greedy Model............................................................................................ 43
3.2 Job sequencing with deadlines ....................................................................................... 44
3.3 Optimal merge pattern .................................................................................................... 48
3.4 Minimum spanning trees ................................................................................................ 52
3.5 Single Source Shortest Pattern ....................................................................................... 59
Chapter three Review Questions ............................................................................................... 64
Chapter Four ................................................................................................................................. 66

[ii]
4. Dynamic Programming and Traversal techniques................................................................. 66
4.1 Multistage graphs, all pairs shortest pattern ................................................................... 68
4.2 Optimal binary search trees ............................................................................................ 69
4.3 0/1 Knapsack .................................................................................................................. 72
4.4 Reliability design............................................................................................................ 74
4.5 Travelling salesman problem ......................................................................................... 76
4.6 Game trees ...................................................................................................................... 77
4.7 Disconnected components .............................................................................................. 78
4.8 Depth first search ........................................................................................................... 78
Chapter four Review Questions ................................................................................................ 80
Chapter Five .................................................................................................................................. 81
5. Back Tracking........................................................................................................................ 81
5.1 The Queens Problem ...................................................................................................... 81
5.1.1 8 queen problem ............................................................................................................. 82
5.2 Graph coloring and Hamiltonian cycles ......................................................................... 83
5.2.1 Graph coloring................................................................................................................ 84
5.2.2 Hamiltonian cycles ......................................................................................................... 85
5.3 Knapsack problems ........................................................................................................ 86
5.4 0/1 Knapsack problems .................................................................................................. 87
5.4.1 Interpreting the solution .......................................................................................... 88
5.5 Travelling sales person problems (TSP) ........................................................................ 90
Chapter five Review Questions ................................................................................................. 92
References ..................................................................................................................................... 93

[iii]
 List of Figures

Figure 1:1 Growth Rate of six function .......................................................................................... 9

Figure 1:2: Data Structure classification....................................................................................... 11
Figure 1:3: (a) The initial configuration, by exchanging A [2] with A [4], node 4 is fixed up, and
the recursive call MAX-HEAPIFY (A, 9) .................................................................................... 16
Figure 2:1 Divide and Conquer problems ..................................................................................... 25
Figure 2:2 Tree for Merge sort...................................................................................................... 34
Figure 2:3 Tree Calls of Merge sort .............................................................................................. 34
Figure 2:4 Calls of Merge Sort function ....................................................................................... 35
Figure 2:5 Steps for Selection Sort ............................................................................................... 42
Figure 3:1 Examples of Greedy Models ....................................................................................... 44
Figure 3:2 Minimum Spanning Tree............................................................................................. 52
Figure 3:3 Minimum Spanning Tree for Prim's Algorithm .......................................................... 54
Figure 3:4 Examples for Kruskal Algorithm ................................................................................ 58
Figure 4:1: Binary search trees with 5 keys .................................................................................. 70
Figure 4:2 Devices connected in series ....................................................................................... 74
Figure 4:3 Multiple Devices Connected in Parallel in each stage ................................................ 74
Figure 5:1 Graph Coloring ............................................................................................................ 84
Figure 5:2 Graph and its Hamiltonian Circle ................................................................................ 85

[iv]
 Chapter One

1. Introduction and Elementary Data structures

1.1 Order Notation

The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t
depend on machine specific constants, and doesn’t require algorithms to be implemented and time
taken by programs to be compared. Asymptotic notations are mathematical tools to represent time
complexity of algorithms for asymptotic analysis[1]. The following five asymptotic notations are
mostly used to represent time complexity of algorithms.

Big-Oh Notation- Let f(n) and g(n) be functions mapping nonnegative integers to real numbers.
A function f(n) = O(g(n)), if there is some positive constant c > 0 and a non-negative integer no ≥
1 such that

f(n) ≤ c.g(n) for all n ≥ no

➢ Big-O expresses an upper bound on the growth rate of a function, for sufficiently large
values of n

➢ An upper bound is the best algorithmic solution that has been found for a problem (“what
is the best thing that we know we can do?”)

➢ In simple words, f(n) = O(g(n)) means that the growth rate of f(n) is less than or equal to
g(n). The statement f(n) = O(g(n)) states only that c.g(n) is un upper bound on the value of
f(n) for all n, n ≥ n0

Big-Oh theorems

➢ Theorem 1: If k is a constant, then k is O (1)

Example: f(n) = 2100 = O (1)
➢ Theorem 2: If f(n) is a polynomial of degree k, then
f(n) = O (nk)
o If f(n) = a0+ a1n + a2n2 + … + aknk, where ai and k are constants, then f(n) is in O (nk)
o Polynomial’s growth rate is determined by the leading term
[1]
 o Example: f(n) = 7n4 + 3n2 + 5n + 1000 is O (n4)

Theorem 4 (Transitivity): If T(n) is O(f(n)) and f(n) is O(g(n)), then T(n) is O(g(n)).

Theorem 5: If T(n) is in O(f(n)) and g(n) is in O(h(n)), then T(n) + g(n) is in O(T(n) + g(n))

Theorem 6: If T(n) is in O(f(n)) and g(n) is in O(h(n)), then T(n).g(n) is in O(T(n).g(n))

✓ product of upper bounds is upper bound for the product

Theorem 7: If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n) + f2(n) = O(max(g1(n), g2(n))

Big-Omega () Notation

Definition:

➢ Let f(n) and g(n) be functions mapping nonnegative integers to real numbers.
➢ A function f(n) = (g(n)), if there is some positive constant c > 0 and a negative integer no ≥
1 such that
f(n) ≥ c.g(n) for all n ≥ no
➢ The statement f(n) = (g(n)) states only that c.g(n) is a lower bound on the value of f(n) for
all n, n ≥ n0. In simple terms, f(n) = (g(n)) means that the growth rate of f(n) is greater than
or equal to g(n)

Big-Omega- Example

➢ Show that the function T(n) = 5n2 – 64n + 256 = Ω(n2)

o We need to show that for non-negative integer n0 and a constant c > 0, T(n) ≥ c.n2 for
all integers n ≥ n0
o we have that for c=1 and n0 = 0, T(n) ≥ cn2 for all integers n ≥ n0
o What if c = 2 and n0 = 16?
o Show if f(n) = 10n2 + 4n + 2 and g(n) = n2, then f(n) = Ω(n2)

Theta () Notation

➢ Let f(n) and g(n) be functions mapping nonnegative integers to real numbers.

[2]
➢ A function f(n) = (g(n)), if there exist some positive constant c1 and c2 and a negative
integer constant no ≥ 1 such that c1.g(n) ≤ f(n) ≤ c2.g(n) for all n ≥ n0
➢ The Theta notation is used when the function f can be bounded both from above and below
by the same function. When we write f(n) = (g(n)), we mean that f lies between c1 times the
function g and c2 times the function g except possibly when n is smaller than n0.
➢ Another way to view the θ-notation is that the function:
o f(n) = θ(n) if and only if
o f(n) = Ο(g(n)) and f(n) = Ω(g(n))

Little-o Notation

➢ Big-Oh notation may or may not be asymptotically tight, for example: 2n2 = O (n2), O(n3)
➢ f(n)=o(g(n)) means for all c>0 there exists some k>0 such that f(n)<c.g(n) for all n>=k.
➢ Informally, f(n)=o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches
infinity.
Example: f (n) =3n+4 is o(n2)
o In simple terms, f(n) has less growth rate compared to g(n).
o g(n)= 2n2 g(n) =o(n3), O(n2), g(n) is not o(n2).

Little-Omega (notation)

➢ Little-omega (ω) notation is to big-omega (ω) notation as little-o notation is to Big-Oh

notation.
➢ We use ω notation to denote a lower bound that is not asymptotically tight.
Formal Definition: f(n)= ω (g(n)) if there exists a constant n0>0 such that 0<= c. g(n)<f(n) for all
n>=k.
Example:

o 2n2= ω (n) but it’s not ω(n2).

1.2 Analysis of algorithm

The analysis of an algorithm provides background information that gives us a general idea of how
long an algorithm will take for a given problem set. For each algorithm considered, we will come
up with an estimate of how long it will take to solve a problem that has a set of N input values. So,
for example, we might determine how many comparisons a sorting algorithm does to put a list of

[3]
N values into ascending order, or we might determine how many arithmetic operations it takes to
multiply two matrices of size N × N. There are a number of algorithms that will solve a problem.
Studying the analysis of algorithms gives us the tools to choose between algorithms. For example,
consider the following two algorithms to find the largest of four values:

If you examine these two algorithms, you will see that each one will do exactly three comparisons
to find the answer. Even though the first is easier for us to read and understand, they are both of
the same level of complexity for a computer to execute. In terms of time, these two algorithms are
the same, but in terms of space, the first needs more because of the temporary variable called
largest. This extra space is not significant if we are comparing numbers or characters, but it may
be with other types of data. In many modern programming languages, we can define comparison
operators for large and complex objects or records. For those cases, the amount of space needed
for the temporary variable could be quite significant. When we are interested in the efficiency of
algorithms, we will primarily be concerned with time issues, but when space may be an issue, it
will also be discussed [2].

[4]
The purpose of determining these values is to then use them to compare how efficiently two
different algorithms solve a problem. For this reason, we will never compare a sorting algorithm
with a matrix multiplication algorithm, but rather we will compare two different sorting algorithms
to each other.

An equally valid way to analyze an algorithm, and the one we will use, is to consider the algorithm
as it is written in a higher-level language. This language can be Pascal, C, C++, Java, or a general
pseudocode.

Input classes

Input plays an important role in analyzing algorithms because it is the input that determines what
the path of execution through an algorithm will be. For example, if we are interested in finding
the largest value in a list of N numbers, we can use the following algorithm:

We can see that if the list is in decreasing order, there will only be one assignment done before
the loop starts. If the list is in increasing order, however, there will be N assignments (one before
the loop starts and N -1 inside the loop). Our analysis must consider more than one possible set
of input, because if we only look at one set of input, it may be the set that is solved the fastest (or
slowest). This will give us a false impression of the algorithm. Instead, we consider all types of
input sets.

The number of possible inputs can get very large as N increases. For instance, if we are interested
in a list of 10 distinct numbers, there are 3,628,800 different orderings of these 10 numbers. It
would be impossible to look at all of these different possibilities. We instead break these possible
lists into classes based on what the algorithm is going to do. For the above algorithm, the
breakdown could be based on where the largest value is stored and would result in 10 different
classes. For a different algorithm, for example, one that finds the largest and smallest values, our
breakdown could be based on where the largest and smallest are stored and would result in 90

[5]
 different classes. Once we have identified the classes, we can look at how an algorithm would
behave on one input from each of the classes. If the classes are properly chosen, all input sets in
the class will have the same number of operations, and all of the classes are likely to have different
results.

Time Complexity

Time complexity of an algorithm is the amount of time it needs to execute the program and get the
intended result, or it determines the approximate number of operations required to solve a problem
of size n.
Space Complexity

Most of what we will be discussing is going to be how efficient various algorithms are in terms of
time, but some forms of analysis could be done based on how much space an algorithm needs to
complete its task. This space complexity analysis was critical in the early days of computing when
storage space on a computer (both internal and external) was limited.

When considering space complexity, algorithms are divided into those that need extra space to do
their work and those that work in place. It was not unusual for programmers to choose an algorithm
that was slower just because it worked in place, because there was not enough extra memory for a
faster algorithm.

Computer memory was at a premium, so another form of space analysis would examine all of the
data being stored to see if there were more efficient ways to store it. For example, suppose we are
storing a real number that has only one place of precision after the decimal point and ranges
between -10 and +10. If we store this as a real number, most computers will use between 4 and 8
bytes of memory, but if we first multiply the value by 10, we can then store this as an integer
between -100 and +100. This needs only 1 byte, a savings of 3 to 7 bytes. A program that stores
1000 of these values can save 3000 to 7000 bytes. When you consider that computers as recently
as the early 1980s might have only had 65,536 bytes of memory, these savings are significant [2].

Cases to Consider

Choosing what input to consider when analyzing an algorithm can have a significant impact on
how an algorithm will perform. If the input list is already sorted, some sorting algorithms will

[6]
perform very well, but other sorting algorithms may perform very poorly. The opposite may be
true if the list is randomly arranged instead of sorted. Because of this, we will not consider just
one input set when we analyze an algorithm. In fact, we will actually look for those input sets that
allow an algorithm to perform the most quickly and the most slowly. We will also consider an
overall average performance of the algorithm as well.

Best Case

As its name indicates, the best case for an algorithm is the input that requires the algorithm to take
the shortest time. This input is the combination of values that causes the algorithm to do the least
amount of work. If we are looking at a searching algorithm, the best case would be if the value we
are searching for (commonly called the target or key) was the value stored in the first location that
the search algorithm would check.

This would then require only one comparison no matter how complex the algorithm is. Notice that
for searching through a list of values, no matter how large, the best case will result in a constant
time of 1. Because the best case for an algorithm will usually be a very small and frequently
constant value, we will not do a best-case analysis very frequently.

Worst case

Worst case is an important analysis because it gives us an idea of the most time an algorithm will
ever take. Worst-case analysis requires that we identify the input values that cause an algorithm to
do the most work. For searching algorithms, the worst case is one where the value is in the last
place we check or is not in the list. This could involve comparing the key to each list value for a
total of N comparisons. The worst case gives us an upper bound on how slowly parts of our
programs may work based on our algorithm choices.

Average Case

Average-case analysis is the toughest to do because there are a lot of details involved. The basic
process begins by determining the number of different groups into which all possible input sets
can be divided. The second step is to determine the probability that the input will come from each
of these groups. The third step is to determine how long the algorithm will run for each of these
groups. All of the input in each group should take the same amount of time, and if they do not, the

[7]
group must be split into two separate groups. When all of this has been done, the average case time
is given by the following formula.

𝐴(𝑛) = ∑𝑚
𝑖=1(𝑃𝑖 ∗ 𝑡𝑖 ) ------------------------------------------------------------(Equation 1)

where n is the size of the input, m is the number of groups, pi is the probability that the input will
be from group i, and ti is the time that the algorithm takes for input from group i.

In some cases, we will consider that each of the input groups has equal probabilities. In other
words, if there are five input groups, the chance the input will be in group 1 is the same as the
chance for group 2, and so on. This would mean hat for these five groups all probabilities would
be 0.2. We could calculate the average case by the above formula, or we could note that the
following simplified formula is equivalent in the case where all groups are equally probable:

1
𝐴(𝑛) = ∑𝑚
𝑖=1 𝑡𝑖 -------------------------------------------------------------------- (Equation 2)
𝑚

Rates of Growth

In analysis of algorithms, it is not important to know exactly how many operations an algorithm
does. Of greater concern is the rate of increase in operations for an algorithm to solve a problem
as the size of the problem increases. This is referred to as the rate of growth of the algorithm. What
happens with small sets of input data is not as interesting as what happens when the data set gets
large. Therefore, the growth rate for an algorithm is the rate at which the cost of the algorithm
grows as the size of its input grows. The following figure shows a graph for six equations, each
meant to describe the running time for a particular program or algorithm. A variety of growth rates
that are representative of typical algorithms are shown.

[8]
Figure 1:1 Growth Rate of six function
As you can see from the figure, the difference between an algorithm whose running time has
cost T(n)=10n and another with cost T(n)=2n2 becomes tremendous as n grows. For n>5, the
algorithm with running time T(n)=2n2 is already much slower. This is despite the fact that 10n has
a greater constant factor than 2n2. Comparing the two curves marked 20n and 2n2 shows that
changing the constant factor for one of the equations only shifts the point at which the two curves
cross. For n>10, the algorithm with cost T(n)=2n2 is slower than the algorithm with
cost T(n)=20n. This graph also shows that the equation T(n)=5nlogn grows somewhat more
quickly than both T(n)=10n and T(n)=20n, but not nearly so quickly as the equation T(n)=2n2. For
constants a,b>1,na grows faster than either logbn or lognb. Finally, algorithms with
cost T(n)=2n or T(n)=n! are prohibitively expensive for even modest values of n. Note that for
constants a, b≥1, an grows faster than nb.

Order-of-Magnitude Analysis

The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t
depend on machine specific constants, and doesn’t require algorithms to be implemented and time
taken by programs to be compared. Asymptotic notations are mathematical tools to represent time
complexity of algorithms for asymptotic analysis. The following five asymptotic notations are
mostly used to represent time complexity of algorithms.
[9]
1.3 Review of elementary data structures

Data Structure can be defined as the group of data elements which provides an efficient way of
storing and organizing data in the computer so that it can be used efficiently. Some examples of
Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in
almost every aspect of Computer Science. Data Structures are the main part of many computer
science algorithms as they enable the programmers to handle the data in an efficient way. It plays
a vital role in enhancing the performance of a software or a program as the main function of the
software is to store and retrieve the user's data as fast as possible [3].

Need of Data Structures

As applications are getting complexed and amount of data is increasing day by day, there may
arise the following problems:

Processor speed: To handle very large amount of data, high speed processing is required, but as
the data is growing day by day to the billions of files per entity, processor may fail to deal with
that much amount of data.

Data Search: Consider an inventory size of 106 items in a store, if our application needs to search
for a particular item, it needs to traverse 106 items every time, results in slowing down the search
process.

Multiple requests: If thousands of users are searching the data simultaneously on a web server,
then there are the chances that a very large server can be failed during that process.

In order to solve the above problems, data structures are used. Data is organized to form a data
structure in such a way that all items are not required to be searched and required data can be
searched instantly.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures. For example:
suppose, we have some data and we need to perform the search for a particular record. In that
case, if we organize our data in an array, we will have to search sequentially element by element.

[10]
 hence, using array may not be very efficient here. There are better data structures which can
make the search process efficient like ordered array, binary search tree or hash tables.

Reusability: Data structures are reusable, i.e. once we have implemented a particular data
structure, we can use it at any other place. Implementation of data structures can be compiled into
libraries which can be used by different clients.

Abstraction: Data structure is specified by the ADT which provides a level of abstraction. The
client program uses the data structure through interface only, without getting into the
implementation details.

Data Structure Classification

Figure 1:2: Data Structure classification

Linear Data Structures: A data structure is called linear if all of its elements are arranged in the
linear order. In linear data structures, the elements are stored in non-hierarchical way where each
element has the successors and predecessors except the first and last element.

[11]
Linked List: Linked list is a linear data structure which is used to maintain a list in the memory.
It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node of
the list contains a pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.
A stack is an abstract data type (ADT), can be implemented in most of the programming languages.
It is named as stack because it behaves like a real-world stack, for example: - piles of plates or
deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and
deleted only at the other end called front. It is an abstract data structure, similar to stack. Queue is
opened at both end therefore it follows First-In-First-Out (FIFO) methodology for storing the data
items.

Nonlinear Data Structures: This data structure does not form a sequence i.e. each item or element
is connected with two or more other items in a non-linear arrangement. The data elements are not
arranged in sequential structure.

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements
known as nodes. The bottommost nodes in the hierarchy are called leaf node while the topmost
node is called root node. Each node contains pointers to point adjacent nodes. Tree data structure
is based on the parent-child relationship among the nodes. Each node in the tree can have more
than one child except the leaf nodes whereas each node can have at most one parent except the
root node.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented
by vertices) connected by the links known as edges. A graph is different from tree in the sense that
a graph can have cycle while the tree cannot have the one.

Operations on data structure

Traversing: Every data structure contains the set of data elements. Traversing the data structure
means visiting each element of the data structure in order to perform some specific operation like
searching or sorting.

[12]
Example: If we need to calculate the average of the marks obtained by a student in 6 different
subjects, we need to traverse the complete array of marks and calculate the total sum, then we will
divide that sum by the number of subjects i.e. 6, in order to find the average.

Insertion: Insertion can be defined as the process of adding the elements to the data structure at
any location. If the size of data structure is n then we can only insert n-1 data elements into it.

Deletion: The process of removing an element from the data structure is called Deletion. We can
delete an element from the data structure at any random location. If we try to delete an element
from an empty data structure then underflow occurs.

Searching: The process of finding the location of an element within the data structure is called
Searching. There are two algorithms to perform searching, Linear Search and Binary Search. We
will discuss each one of them later in this tutorial.

Sorting: The process of arranging the data structure in a specific order is known as Sorting. There
are many algorithms that can be used to perform sorting, for example, insertion sort, selection sort,
bubble sort, etc.

Merging: When two lists List A and List B of size M and N respectively, of similar type of
elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is
called merging.

1.4 Heap and Heap Sort

The (binary) heap data structure is an array object that we can view as a nearly complete binary
tree. Each node of the tree corresponds to an element of the array [4]. 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:

[13]
 o PARENT (i) => return [i/2]
o LEFT (i) => return 2i
o RIGHT (i) => return 2i+ 1

On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the
binary representation of i left by one bit position.

Similarly, the RIGHT procedure can quickly compute 2i + 1 by shifting the binary representation
of i left by one bit position and then adding in 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 [4].

➢ 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.
➢ A min-heap is organized in the opposite way; 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
➢ 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.
➢ Height of a heap of n elements which is based on a complete binary tree is O (log n).

[14]
Construction of Heap

➢ A heap can be constructed by inserting new elements one by one into an initially empty heap
into the left-most open spot in the array
➢ If the newly inserted element is greater than (in the case of max heap) its parent then swap their
position recursively so that the newly inserted element rises to its appropriate place and
preserves the heap order
➢ A node has the heap property if the value in the node is as large as or larger than the values in
its children

➢ All leaf nodes automatically have the heap property

➢ A binary tree is a heap if all nodes in it have the heap property

Maintaining the heap property

MAX-HEAPIFY lets the value at A[i] "float down" in the max-heap so that the subtree rooted at
index i obeys the max-heap property.

MAX-HEAPIFY(A,i)

1. l<-LEFT(i)

2. r<-RIGHT(i)

3. if A[l] > A[i]

4. largest<-l

5. if A[r] > A[largest]

6. Largest<-r

[15]
7. if largest! = i

8. Then exchange A[i]<-->A[largest]

9. MAX-HEAPIFY (A, largest)

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 largest. If A[i] is 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.

Figure 1:3: (a) The initial configuration, by exchanging A [2] with A [4], node 4 is fixed up,
and the recursive call MAX-HEAPIFY (A, 9)

[16]
Figure 1:3: The action of MAX-HEAPIFY (A, 2), where heap-size = 10. (a) The initial
configuration, with A [2] at node i = 2 violating the max-heap property since it is not larger than
both children. The max-heap property is restored for node 2 in (b) by exchanging A [2] with A [4],
which destroys the max-heap property for node 4. The recursive call MAX-HEAPIFY (A,4). now
has i = 4. After swapping A [4] with A [9], as shown in (c), node 4 is fixed up, and the recursive
call MAX-HEAPIFY (A, 9) yields no further change to the data structure.

The running time of MAX-HEAPIFY by the recurrence can be described as

T (n) < = T (2n/3) + O (1)

The solution to this recurrence is T(n)=O (log n)

The HEAPSORT Algorithm

HEAPSORT(A)

1. BUILD MAX-HEAP(A)

2. for i=n to 2

3. exchange A[1] with A[i]

4. MAX-HEAPIFY(A,1)

Inplace algorithm

➢ Running Time: O(n log n)

➢ Complete Binary Tree

1.5 Hashing

Hashing is used to index and retrieve items in a database because it is faster to find the item using
the shortest hashed key than to find it using the original value. It is also used in many encryption
algorithm. A hash code is generated by using a key, which is a unique value. It is a technique in

[17]
which given key field value is converted into the address of storage location of the record by
applying the same operation on it [5].

Need of Hashing

Suppose we have 50 employees, and we have to give 4-digit key to each employee (as for security),
and we want after entering a key, direct user map to a particular position where data is stored. If
we give the location number according to 4 digits, we will have to reserve 0000 to 9999 addresses
because anybody can use anyone as a key. There is a lot of wastage. In order to solve this problem,
we use hashing which will produce a smaller value of the index of the hash table corresponding to
the key of the user.

Universal Hashing

Let H be a finite collection of hash functions that map a given universe U of keys into the range
{0, 1..... m-1}. Such a collection is said to be universal if for each pair of distinct keys k,l∈U, the
number of hash functions h∈ H for which h(k)= h(l) is at most |H|/m. In other words, with a hash
function randomly chosen from H, the chance of a collision between distinct keys k and l is no
more than the chance 1/m of a collision if h(k) and h(l)were randomly and independently chosen
from the set {0,1,...m-1}.

Rehashing

If any stage the hash table becomes nearly full, the running time for the operations of will start
taking too much time, insert operation may fail in such situation, the best possible solution is as
follows:

o Create a new hash table double in size.

o Scan the original hash table, compute new hash value and insert into the new hash table
o Free the memory occupied by the original hash table.

Example: Consider inserting the keys 10, 22, 31,4,15,28,17,88 and 59 into a hash table of length
m = 11 using open addressing with the primary hash function h' (k) = k mod m. Illustrate the result
of inserting these keys using linear probing, using quadratic probing with c1=1 and c2=3, and using
double hashing with h2(k) = 1 + (k mod (m-1)).

[18]
Solution: Using Linear Probing the final state of hash table would be

0 22
1 88
2 /
3 /
4 4
5 15
6 28
7 17
8 59
9 31
10 10

Using Quadratic Probing with c1=1, c2=3, the final state of hash table would be h (k, i) = (h' (k)
+c1*i+ c2 *i2) mod m where m=11 and h' (k) = k mod m.

0 22
1 88
2 /
3 17
4 4
5 /
6 28
7 59
8 15
9 31
10 10

Using Double Hashing, the final state of the hash table would be:

0 22

[19]
 1 /
2 59
3 17
4 4
5 15
6 28
7 88
8 /
9 31
10 10

1.6 Sets Representation

A set is a data structure that can store any number of unique values in any order you so wish. Set’s
are different from arrays in the sense that they only allow non-repeated, unique values within them.
A set is a well-defined collection of distinct objects, i.e. the nature of the object is the same, or in
other words the objects in a set may be anything: numbers, people, places, letters, etc [6].

These objects are called the elements or members of the set.

Notation:

A set is usually denoted by capital letters, i.e. A, B, C…, X, Y, Z…A, B, C,…, X,Y,Z,… etc.,
and the elements are denoted by small letters, i.e. a,b,c,…,x,y,z,…a,b,c,…,x,y,z,… etc.

If A is any set and aa is the element of set A, then we write a∈A, read as aa belongs to A. If A is
any set and a is not the element of set A, then we write a∉A, read as a does not belong to A.

Representation of Sets

Tabular Form- Listing all the elements of a set, separated by commas and enclosed within curly
brackets {}. Example: A= {1,2,3,4,5}, B = {2,4,6, ⋯,50}, C = {1,3,5,7,9, ⋯}

[20]
Descriptive Form: State in words the elements of the set
Example:
A= Set of first five natural numbers.
B= Set of positive even integers less than or equal to fifty.
C=Set of positive odd integers.

Set Builder Form: Writing in symbolic form the common characteristics shared by all the
elements of the set.

Examples: A={x:x∈N∧x⩽5} A={x:x∈N∧x⩽5} N = Natural numbers

A={x:x∈E∧0<y⩽50} A={x:x∈E∧0<y⩽50} E = Even numbers

A= {x: x∈O∧x>0} A={x:x∈O∧x>0} O = Odd numbers

1.7 UNION, FIND operation

UNION (x, y):

o Combines/merges two disjoint sets containing root x and root y into one set
o Replaces two sets, A and B with their union A U B

FIND(x):

➢ FIND () operation check if the two pairs, xi & xj are in the same group or not, before
merging them using UNION () operation.

Algorithms: Create, Union & Find operations

procedure CREATE(x)

parent(x) = -1 //some negative number

end

procedure UNION(x,y)

parent(x) = y

end

[21]
procedure FIND(x)

y=x

while parent(y) > 0 do

y = parent(y)

end while

return y

end
Improving UNION and FIND operations

➢ Analyze the total time required for performing the following operations:
UNION (1,2), UNION (2,3), …, UNION (n-1, n), and FIND (1), FIND (2), …, FIND(n)
➢ There is a need to enhance the efficiency of UNION and FIND operations. Notice that the
time to do a FIND operation on an element corresponds to its depth in the tree. Can we
improve the performance of UNION and FIND? Improve means decrease the height of the
trees. Hence our goal is to keep the trees as short as possible.
➢ Two heuristics for keeping the height of the disjoint trees short are UNION by rank and Path
Compression

UNION by rank: ensures that when we combine two trees, we try to keep the overall depth of
the resulting tree small.

o If x and y are roots of two distinct trees, this technique makes the root of the smaller tree
a child of the root of the larger tree.
o Union by rank avoids creation of degenerate trees

Path compression: collapses all nodes to point to root node.

o Is used during FIND operation so as to make each node on the find path point directly
to the root

[22]
UNION by rank

➢ Balances the height of a tree. The idea is that the rank of the root is associated with the
depth of the tree so as to keep the depth small. Weighting rule for UNION (x, y): If the
number of nodes in tree with root x is less than the number in tree with root y, then make
y the parent of x; otherwise, make x the parent of y.
procedure UNION(x,y)
z = parent(x) + parent(y)
if parent(x) > parent(y) then
parent(x) = y
parent(y) = z
else
parent(y) = x
parent(x) = z
end if
end UNION

Path Compression

➢ Reduces the complexity of FIND algorithm. This is done by collapsing nodes in a tree.
Collapsing rule: If x is a node on the path from y to its root and parent[y] ≠ root[y], then set
parent[x] to root[y]. The idea is that, once we perform a FIND on some element, we should
adjust its parent pointer so that it points directly to the root; that way, if we ever do another
FIND on it, we start out much closer to the root.
function FIND(x)
y=x
while parent(y) > 0 do
y = parent(y) //Find root
z=x
while z ≠ y do //collapse nodes from z to root y
t = parent(z)
parent(z) = y
z=t

[23]
 return y
end FIND

Chapter One Review Questions

1) Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of -
notation, prove that max f(n), g(n) =  (f (n) + g(n)).
2) Write an algorithm that takes in three distinct integers and determines the largest of the three.
What are the possible input classes that would have to be considered when analyzing this
algorithm?

3) f (n) = (3/2) n2 + (5/2) n – 3, Show that f (n) = O (n2)?

4) Let us take the list of 40,56,28,79,20,20,18,67 and 58. construct the max heap
5) Express the function n3/1000 - 100n2 - 100n + 3 in terms of  -notation

[24]
 Chapter -Two

2. Divide – and – conquer

2.1 General Method

Divide and conquer strategy is as follows: divide the problem instance into two or more smaller
instances of the same problem, solve the smaller instances recursively, and assemble the solutions
to form a solution of the original instance. The recursion stops when an instance is reached which
is too small to divide. When dividing the instance, one can either use whatever division comes
most easily to hand or invest time in making the division carefully so that the assembly is
simplified.

Divide and conquer algorithm consists of two parts: Divide: Divide the problem into a number of
sub problems. The sub problems are solved recursively. Conquer: The solution to the original
problem is then formed from the solutions to the sub problems (patching together the answers).
Traditionally, routines in which the text contains at least two recursive calls are called divide and
conquer algorithms, while routines whose text contains only one recursive call are not. Divide–
and–conquer is a very powerful use of recursion [7].

Figure 2:1 Divide and Conquer problems

[25]
Control Abstraction of Divide and Conquer

A control abstraction is a procedure whose flow of control is clear but whose primary operations
are specified by other procedures whose precise meanings are left undefined. The control
abstraction for 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 which determines whether the input size is small enough
so that the answer can be computed without splitting. If this is so function ‘S’ is invoked otherwise,
the problem ‘p’ into smaller sub problems. These sub problems p1, p2, . . . , pk are solved by
recursive application of DANDC.

Where, T (n) is the time for DANDC on ‘n’ inputs, g (n) is the time to complete the answer
directly for small inputs and f (n) is the time for Divide and Combine.

2.2 Binary Search

If we have ‘n’ records which have been ordered by keys so that x1 < x2 < … < x n. When we are
given a element ‘x’, binary search is used to find the corresponding element from the list. In case

[26]
‘x’ is present, we have to determine a value ‘j’ such that a[j] = x (successful search). If ‘x’ is not
in the list then j is to set to zero (un successful search) [7].

In Binary search we jump into the middle of the file, where we find key a[mid], and compare ‘x’
with a[mid]. If x = a[mid] then 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 at all. Similarly, if a[mid] > x, then further
search is only necessary in that past of the file which follows a[mid].

If we use recursive procedure of finding the middle key a[mid] of the un-searched portion of a
file, then every un-successful 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

BINSRCH (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)
do{
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;

[27]
}
low and high are integer variables such that each time through the loop either ‘x’ is found or 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.

Time complexity of Binary Search

Cases Time Complexity

Best O(1)
Average O(logn)
Worst O(logn)

Space Complexity of Binary Search is:

Space Complexity in iterative implementation O(1)

Space Complexity in recursive implementation O(logn)

2.3 Finding Maximum and Minimum

The Max-Min Problem in algorithm analysis is finding the maximum and minimum value in an
array. To find the maximum and minimum numbers in a given array numbers [] of size n, we will
present divide and conquer approach. In this approach, the array is divided into two halves. Then
using recursive approach maximum and minimum numbers in each halves are found. Later, return
the maximum of two maxima of each half and the minimum of two minima of each half [8].

A Divide and Conquer Algorithm for this problem would proceed as follows:

» 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.

[28]
 » 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

Algorithm DC_MAXMIN (A, low, high)

// Description : Find minimum and maximum element from array using divide and conquer
approach

// Input : Array A of length n, and indices low = 0 and high = n - 1

// Output : (min, max) variables holding minimum and maximum element of array

if n == 1 then

return (A[1], A[1])

else if n == 2 then

if A[1] < A[2] then

return (A[1], A[2])

else

return (A[2], A[1])

else

mid ← (low + high) / 2

[LMin, LMax] = DC_MAXMIN (A, low, mid)

[RMin, RMax] = DC_MAXMIN (A, mid + 1, high)

if LMax > RMax then

// Combine solution

max ← LMax

else

max ← RMax

[29]
 end

if LMin < RMin then

// Combine solution

min ← LMin

else

min ← RMin

end

return (min, max)

end

Time complexity = O(n) and space complexity = O(logn) (For recursion call stack).

2.4 Merge Sort

Merge sort algorithm is a classic example of divide and conquer. To sort an array, recursively, sort
its left and right halves separately and then merge them. The time complexity of merge mort in the
best case, worst case and average case is O (n log n) and the number of comparisons used is nearly
optimal. This strategy is so simple, and so efficient but the problem here is that there seems to be
no easy way to merge two adjacent sorted arrays together in place (The result must be built up in
a separate array) [7].

The fundamental operation in this algorithm is merging two sorted lists. Because the lists are
sorted, this can be done in one pass through the input, if the output is put in a third list. The basic
merging algorithm takes two input arrays ‘a’ and ’b’, an output array ‘c’, and three counters, a ptr,
b ptr and c ptr, which are initially set to the beginning of their respective arrays.

The smaller of a[a ptr] and b[b ptr] is copied to the next entry in ‘c’, and the appropriate counters
are advanced. When either input list is exhausted, the remainder of the other list is copied to ‘c’.

[30]
To illustrate how merge process works. For example, let us consider the array ‘a’ containing 1, 13,
24, 26 and ‘b’ containing 2, 15, 27, 38. First a comparison is done between 1 and 2. 1 is copied to
‘c’. Increment a ptr and c ptr.

and then 2 and 13 are compared. 2 is added to ‘c’. Increment b ptr and c ptr.

then 13 and 15 are compared. 13 is added to ‘c’. Increment a ptr and c ptr.

24 and 15 are compared. 15 is added to ‘c’. Increment b ptr and c ptr.

24 and 27 are compared. 24 is added to ‘c’. Increment a ptr and cptr.

26 and 27 are compared. 26 is added to ‘c’. Increment a ptr and cptr.

As one of the lists is exhausted. The remainder of the b array is then copied to ‘c’.

[31]
 Algorithm

Algorithm MERGESORT (low, high)

// a (low : high) is a global array to be sorted.
{
if (low < high)
{
mid := (low + high)/2//finds where to split the set
MERGESORT(low, mid) //sort one subset
MERGESORT(mid+1, high) //sort the other subset
MERGE(low, mid, high) // combine the results
}
}
Algorithm MERGE (low, mid, high)
// a (low : high) is a global array containing two sorted subsets
// in a (low : mid) and in a (mid + 1 : high).
// The objective is to merge these sorted sets into single sorted
// set residing in a (low : high). An auxiliary array B is used.
{
h :=low; i := low; j:= mid + 1;
while ((h <= mid) and (J <= high))
do {
if (a[h] <= a[j]) then {
b[i] := a[h]; h := h + 1;

[32]
}
else{
b[i] :=a[j]; j := j + 1;
}
i := i + 1;
}
if (h > mid) then
for k := j to high do
{
b[i] := a[k]; i := i + 1;
}
else
for k := h to mid do
{
b[i] := a[K]; i := i + l;
}
for k := low to high do
a[k] := b[k];
}
Example

For example, let us select the following 8 entries 7, 2, 9, 4, 3, 8, 6, 1 to illustrate merge sort
algorithm:

[33]
Figure 2:2 Tree for Merge sort

Tree Calls of MERGESORT (1, 8)

The following figure represents the sequence of recursive calls that are produced by
MERGESORT when it is applied to 8 elements. The values in each node are the values of the
parameters low and high.

Figure 2:3 Tree Calls of Merge sort

Tree
Calls of MERGE ()
The tree representation of the calls to procedure MERGE by MERGESORT is as follows:

[34]
Figure 2:4 Calls of Merge Sort function

2.4.1 Analysis of Merge Sort

We will assume that ‘n’ is a power of 2, so that we always split into even halves, so we solve for
the case n = 2k. For n = 1, the time to merge sort is constant, which we will be denote by 1.
Otherwise, the time to merge sort ‘n’ numbers is equal to the time to do two recursive merge sorts
of size n/2, plus the time to merge, which is linear [7]. The equation says this exactly:

This is a standard recurrence relation, which can be solved several ways. We will solve by
substituting recurrence relation continually on the right–hand side.

We have,

Since we can substitute n/2 into this main equation

We have,

Again, by substituting n/4 into the main equation, we see that

[35]
So, we have,

Continuing in this manner, we obtain:

As n = 2k, K = log2n substituting this in the above equation

Representing this in O notation:

T(n) = O (n log n)
We have assumed that n = 2k. The analysis can be refined to handle cases when ‘n’ is not a power
of 2. The answer turns out to be almost identical.

Although merge sort’s running time is O (n log n), it is hardly ever used for main memory sorts.
The main problem is that merging two sorted lists requires linear extra memory and the additional
work spent copying to the temporary array and back, throughout the algorithm, has the effect of
slowing down the sort considerably. The Best- and worst-case time complexity of Merge sort is O
(n log n).

Time complexity of Merge Sort

Cases Time Complexity

Best O(nlogn)
Average O(nlogn)
Worst O(nlogn)

Time complexity of Merge Sort is O (nLog n) in all the 3 cases (worst, average and best) as
merge sort always divides the array in two halves and takes linear time to merge two halves.
[36]
Space Complexity of Merge Sort is:

Space Complexity O(n)

2.5 Quick sort

Quick sort uses a divide-and-conquer approach. It is accomplished by dividing the array into two
partitions and then sorting each partition recursively.

In Quicksort, the array is partitioned by placing all items smaller than some pivot item before that
item and all items larger than the pivot item after it. See figure 1. After each partition, the pivot
item is in the right place. Also, each partition is decreasing. We can guarantee that until there is
one element in partition, we will have a sorted array [4].

Problem: Sort Array a of N elements in ascending order

Input: Array a, index of first array element lo and last array element.

Output: Array a in ascending order.

[37]
Line 1, function quicksort sort array a with N element. lo is the lower index, hi is the upper index
of the region of array a that is to be sorted.

Line2-4 is the partition part. Line 3, i is pointed to the first element of the array, j points to the last.
Line 4, x is the pivot item which can be any item. k% is the percentage of the best performance of
quick sort. We will use 50%=k% in this module.

Line 5-16. After partitioning the sequence, quicksort treats the two parts recursively by the same
procedure. The recursion ends whenever a part consists of one element only. Line 14 repeats line
6-13 until i >j. Line 7 searches for first element a[i] greater or equal to x. Line 8 searches for last
element a[j] less than or equal to x. Line 9-13, If i<=j, exchange a[i] and a[j] and move i and j.

Below figure illustrate the implementation of Quicksort. Given an array a [] = {6,5,1,2}, 1 is

chosen as the pivot item in line 1. i is pointed to the first element a [1], j points to the last a [4].
Compare a [1] with pivot, a [1] > pivot. Because a [4] pivot, so exchange a [3] with a [1]. Line 3,
i=j=2, so partition stops here. After this, 1 is in the right place. Line 4, 6 is chosen as pivot item.
Swap 6 and 2. When i>j, stop partitioning.

[38]
Comparison between two array elements is the key operation of quick sort. Because before we sort
the array, we need to compare between array elements.

The worst case of quick sort occur when we choose the smallest or the largest element as the pivot.
It needs the most comparisons in each iteration. See figure above, we want to sort a = [6,5,1,2].
From line 1 to 2, the smallest item 1 is chosen as the pivot. All elements need to compare with the
pivot item once. From line 2 to 3, the largest item 6 is chosen as the pivot. All elements need to
compare with the pivot item once. From line 3 to 4, 1 comparison is needed.

[39]
Let T(N) be the number of comparisons needed to sort an array of N elements. In the worst case,
we need N-1 comparisons in the first round. Then we need T(N-1) comparisons to sort N-1
elements. T(N) = N-1 + T(N-1)

We need 0 times to sort 1 element:

T (1) = 0

T(N-1) = (N-2) + T(N-2)

T(N-2) = N-3+T(N-3)

T[N-(N-1] = [N-(N-1)]+T[N-(N-1)] = 1+T(0) =1

T(N) = (N-1)+T(N-1)

= (N-1)+(N-2)+T(N-2)

= (N-1)+(N-2)+(N-3)+T(N-3)

= (N-1)+(N-2)+(N-3)+…+T(N-(N-1))

= (N-1)+(N-2)+(N-3)+…+1

= (N2+N)/2

= O(N2)

Thus, we have a O(N2) time complexity in the worst case.

Time complexity of Quicksort

Cases Time Complexity

Best O(nlogn)
Average O(nlogn)
Worst O(n2)

[40]
Space Complexity of Quicksort

Space Complexity O(nlogn)

2.6 Selection Sort

Selection sort is conceptually the simplest sorting algorithm. This algorithm will first find
the smallest element in the array and swap it with the element in the first position, then it will find
the second smallest element and swap it with the element in the second position, and it will keep
on doing this until the entire array is sorted. It is called selection sort because it
repeatedly selects the next-smallest element and swaps it into the right place.

How Selection Sort Works?

Following are the steps involved in selection sort (for sorting a given array in ascending order):

» Starting from the first element, we search the smallest element in the array, and replace it
with the element in the first position.

» We then move on to the second position, and look for smallest element present in the
subarray, starting from index 1, till the last index.

» We replace the element at the second position in the original array, or we can say at the
first position in the subarray, with the second smallest element.

» This is repeated, until the array is completely sorted.

Example: Let's consider an array with values {3, 6, 1, 8, 4, 5}

[41]
 Below, we have a pictorial representation of how selection sort will sort the given array

Figure 2:5 Steps for Selection Sort

In the first pass, the smallest element will be 1, so it will be placed at the first position. Then
leaving the first element, next smallest element will be searched, from the remaining elements.
We will get 3 as the smallest, so it will be then placed at the second position. Then
leaving 1 and 3(because they are at the correct position), we will search for the next smallest
element from the rest of the elements and put it at third position and keep doing this until array is
sorted.

Chapter two Review Questions

1) What does FIND-MAXIMUM-SUBARRAY return when all elements of A are negative?

2) Given an array arr [5] = {4, 1, 3, 9, 7} its starting position low and its ending position high.
Implement the partition () and quickSort () functions to sort the array and put expected time
and space complexity
3) Given an array arr [5] = {4 1 3 9 7} its starting position l and its ending position r. Sort the
array using merge sort algorithm. Don’t forget to write its time and space complexity.
4) Explain how Merge sort works?
5) Explain why the complexity of binary search is O(logn)?

[42]
 Chapter Three

3. Greedy Model
3.1 Overview of Greedy Model

A Greedy algorithm is an approach to solving a problem that selects the most appropriate option
based on the current situation. This algorithm ignores the fact that the current best result may not
bring about the overall optimal result. Even if the initial decision was incorrect, the algorithm never
reverses it, and this simple, intuitive algorithm can be applied to solve any optimization problem
which requires the maximum or minimum optimum result. The best thing about this algorithm is
that it is easy to understand and implement.

The runtime complexity associated with a greedy solution is pretty reasonable. However, you can
implement a greedy solution only if the problem statement follows two properties mentioned
below:

» Greedy Choice Property: Choosing the best option at each phase can lead to a global
(overall) optimal solution.

» Optimal Substructure: If an optimal solution to the complete problem contains the

optimal solutions to the subproblems, the problem has an optimal substructure.

Steps for Creating a Greedy Algorithm

By following the steps given below, you will be able to formulate a greedy solution for the given
problem statement:

» Step 1: In a given problem, find the best substructure or subproblem

» Step 2: Determine what the solution will include (e.g., largest sum, shortest path)

» Step 3: Create an iterative process for going over all subproblems and creating an
optimum solution

[43]
Example of Greedy Algorithm

Problem Statement: Find the best route to reach the destination city from the given starting
point using a greedy method.

Figure 3:1 Examples of Greedy Models

Greedy Solution: In order to tackle this problem, we need to maintain a graph structure. And for
that graph structure, we'll have to create a tree structure, which will serve as the answer to this
problem. The steps to generate this solution are given below:

» Start from the source vertex

» Pick one vertex at a time with a minimum edge weight (distance) from the source vertex

» Add the selected vertex to a tree structure if the connecting edge does not form a cycle

» Keep adding adjacent fringe vertices to the tree until you reach the destination vertex

3.2 Job sequencing with deadlines

The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing
with Deadlines [9].

[44]
Here-

» You are given a set of jobs

» Each job has a defined deadline and some profit associated with it

» The profit of a job is given only when that job is completed within its deadline

» Only one processor is available for processing all the jobs

» Processor takes one unit of time to complete a job

The problem statement - “How can the total profit be maximized if only one job can be completed
at a time?”
Approach to Solution

» A feasible solution would be a subset of jobs where each job of the subset gets completed
within its deadline
» Value of the feasible solution would be the sum of profit of all the jobs contained in the subset
» An optimal solution of the problem would be a feasible solution which gives the maximum
profit
Greedy Algorithm-

» Greedy Algorithm is adopted to determine how the next job is selected for an optimal solution

» The greedy algorithm described below always gives an optimal solution to the job sequencing
problem

Step-01:

» Sort all the given jobs in decreasing order of their profit.

Step-02:

» Check the value of maximum deadline.

» Draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.
Step-03:

» Pick up the jobs one by one

[45]
» Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed before
its deadline
Examples: Given the jobs, their deadlines and associated profits as shown

Answer the following questions

1. Write the optimal schedule that gives maximum profit.

2. Are all the jobs completed in the optimal schedule?
3. What is the maximum earned profit?
Solution:
Step-01: Sort all the given jobs in decreasing order of their profit

Step-02: Value of maximum deadline = 5. So, draw a Gantt chart with maximum time on Gantt
chart = 5 units as shown

Now,

» We take each job one by one in the order they appear in Step-01

[46]
 » We place the job on Gantt chart as far as possible from 0
Step-03:

» We take job J4.

» Since its deadline is 2, so we place it in the first empty cell before deadline 2 as-

Step-04: We take job J1

Since its deadline is 5, so we place it in the first empty cell before deadline 5 as

Step-05: We take job J3.

Since its deadline is 3, so we place it in the first empty cell before deadline 3 as-

Step-06:

» We take job J2.

» Since its deadline is 3, so we place it in the first empty cell before deadline 3.

» Since the second and third cells are already filled, so we place job J2 in the first cell as-

Step-07:

» Now, we take job J5.

» Since its deadline is 4, so we place it in the first empty cell before deadline 4 as-

[47]
Now,

» The only job left is job J6 whose deadline is 2

» All the slots before deadline 2 are already occupied

» Thus, job J6 cannot be completed

Now, the given questions may be answered as-

1) The optimal schedule is- J2, J4, J3, J5, J1

This is the required order in which the jobs must be completed in order to obtain the maximum
profit

2) All the jobs are not completed in optimal schedule. This is because job J6 could not be
completed within its deadline.
3) Maximum earned profit
= Sum of profit of all the jobs in optimal schedule
= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of job J1
= 180 + 300 + 190 + 120 + 200
= 990 units

3.3 Optimal merge pattern

Optimal merge pattern is a pattern that relates to the merging of two or more sorted files in a
single sorted file. This type of merging can be done by the two-way merging method. If we have
two sorted files containing n and m records respectively then they could be merged together, to
obtain one sorted file in time O (n+m).

[48]
There are many ways in which pairwise merge can be done to get a single sorted file. Different
pairings require a different amount of computing time. The main thing is to pairwise merge the n
sorted files so that the number of comparisons will be less.

The formula of external merging cost is:

𝑛

∑ 𝑓(𝑖)𝑑(𝑖)
𝑖=1

Where, f (i) represents the number of records in each file and d (i) represents the depth.

Algorithm for optimal merge pattern

Algorithm Tree(n)

//list is a global list of n single node

For i=1 to i= n-1 do

// get a new tree node

Pt: new treenode;

// merge two trees with smallest length

(Pt = lchild) = least(list);

(Pt = rchild) = least(list);

(Pt =weight) = ((Pt = lchild) = weight) = ((Pt = rchild) = weight);

Insert (list, Pt);

// tree left in list

Return least(list);

[49]
An optimal merge pattern corresponds to a binary merge tree with minimum weighted external
path length. The function tree algorithm uses the greedy rule to get a two- way merge tree for n
files. The algorithm contains an input list of n trees. There are three field child, rchild, and weight
in each node of the tree. Initially, each tree in a list contains just one node. This external node has
lchild and rchild field zero whereas weight is the length of one of the n files to be merged. For any
tree in the list with root node t, t = it represents the weight that gives the length of the merged file.
There are two functions least (list) and insert (list, t) in a function tree. Least (list) obtains a tree in
lists whose root has the least weight and return a pointer to this tree. This tree is deleted from the
list. Function insert (list, t) inserts the tree with root t into the list.

The main for loop in this algorithm is executed in n-1 times. If the list is kept in increasing order
according to the weight value in the roots, then least (list) needs only O(1) time and insert (list, t)
can be performed in O(n) time. Hence, the total time taken is O (n2). If the list is represented as a
minheap in which the root value is less than or equal to the values of its children, then least (list)
and insert (list, t) can be done in O (log n) time. In this condition, the computing time for the tree
is O (n log n).

Example

Consider the sequence {3, 5, 9, 11, 16, 18, 20}. Find optimal merge pattern for this data

Solution:
At each step, merge the two smallest sequences

Step 1: Given sequence is,

Step 2: Merge the two smallest sequences and sort in ascending order

[50]
Step 3: Merge the two smallest sequences and sort in ascending order

Step 4: Merge the two smallest sequences and sort in ascending order

Step 5: Merge the two smallest sequences and sort in ascending order

Step 6: Merge the two smallest sequences and sort in ascending order

[51]
Step 7: Merge the two smallest sequences and sort in ascending order

Total time = 8 + 17 + 27 + 35 + 47 + 82 = 216

3.4 Minimum spanning trees

Problem: Laying Telephone Wire and Minimize the total length of wire connecting the customers.

Figure 3:2 Minimum Spanning Tree

Definition: Assume you have an undirected graph G = (V, E) with weights assigned to edges. The
objective is “use smallest set of edges of the given graph to connect everything together”. How?
A minimum spanning tree is a least-cost subset of the edges of a graph that connects all the nodes
[10], [1]. It is a sub-graph of an undirected weighted graph G, such that:

» It is a tree (i.e., it is acyclic)

» It covers all the vertices V

[52]
 » contains |V| - 1 edges
» The total cost associated with tree edges is the minimum among all possible spanning trees

Applications of MST is:

» Network design, road planning, etc.

How can we generate a MST?

A MST is a least-cost subset of the edges of a graph that connects all the nodes. A greedy method
to obtain a minimum-cost spanning tree builds this tree edge by edge. The next edge to include is
chosen according to some optimization criterion.

Criteria: to choose an edge that results in a minimum increase in the sum of the costs of the edges
so far included.

General procedure:

» Start by picking any node and adding it to the tree

» Repeatedly: Pick any least-cost edge from a node in the tree to a node not in the tree, and
add the edge and new node to the tree
» Stop when all nodes have been added to the tree

Prim’s algorithm

Prim’s algorithm starts with a single node and works its way through several adjacent nodes,
exploring all of the connected edges along the way. Edges with the minimum weights that do not
cause cycles in the graph get selected for t inclusion in the MST structure. Hence, we can say that
Prim’s algorithm takes a locally optimum decision in order to find the globally optimal solution.
That is why it is also known as a Greedy Algorithm [10].

Prim’s: Always takes the lowest-cost edge between nodes in the spanning tree and nodes not yet
in the spanning tree.

» If A is the set of edges selected so far, then A forms a tree

o The next edge (u, v) to be included in A is a minimum cost edge not in A such that A υ
{(u, v)} is also a tree, where u is in the tree & v is not.
[53]
Property: At each step, we add the edge (u, v) s.t. the weight of (u,v) is minimum among all edges.
This spanning tree grows by one new node and edge at each iteration. Each step maintains a
minimum spanning tree of the vertices that have been included thus far. When all vertices have
been included, we have a minimum cost spanning tree for the graph.

Example: find the minimum spanning tree using Prim algorithm

Figure 3:3 Minimum Spanning Tree for Prim's Algorithm

Prim’s Algorithm procedure

primMST (G, cost, n, T)

Pick a vertex 1 to be the root of the spanning tree T
mincost = 0
for i = 2 to n do near (i) = 1
near (1) = 0
for i = 1 to n-1 do
find j such that near(j) ≠ 0 and cost (j, near(j)) is min
T(i,1) = j; T(i,2) = near (j)
mincost = mincost + cost(j,near(j))
near (j) = 0
for k = 1 to n do
if near(k) ≠ 0 and cost (k, near(k) > cost(k,j) then
near (k) = j
end for

[54]
end for
return mincost
end procedure
Correctness of Prim’s
If the algorithm is correct it halts with the right answer or optimal solution. Optimal solution is
obtained if:

o Prim algorithm adds n-1 edges (with minimum cost) to the spanning tree without creating
a cycle

Example: Graph G (V, E) given below contains 9 vertices and 12 edges. We are supposed to
create a minimum spanning tree T (V’, E’) for G (V, E) such that the number of vertices in T will
be 9 and edges will be 8 (9-1).

o Primarily, to begin with the creation of MST, you will choose an arbitrary starting vertex. Let’s
say node A is your starting vertex. This means it will be included first in your tree structure.

[55]
 o After the inclusion of node, A, you will look into the connected edges going outward from
node A and you will pick the one with a minimum edge weight to include it in your T (V’,
E’) structure.

o Now, you have reached node B. From node B, there are two possible edges out of which
edge BD has the least edge weight value. So, you will include it in your MST.

o From node D, you only have one edge. So, you will include it in your MST. Further, you have
node H, for which you have two incident edges. Out of those two edges, edge HI has the least
cost, so you will include it in MST structure.

[56]
o Similarly, the inclusion of nodes G and E will happen in MST.

o After that, nodes E and C will get included. Now, from node C, you have two incident edges.
Edge CA has the tiniest edge weight. But its inclusion will create a cycle in a tree structure,
which you cannot allow. Thus, we will discard edge CA as shown in the image below.

o And we will include edge CF in this minimum spanning tree structure

[57]
o The summation of all the edge weights in MST T(V’, E’) is equal to 30, which is the least
possible edge weight for any possible spanning tree structure for this particular graph.

Kruskal’s algorithm

Kruskal algorithm: Always tries the lowest-cost remaining edge. It considers the edges of the
graph in increasing order of cost. In this approach, the set T of edges so far selected for the spanning
tree may not be a tree at all stages in the algorithm. But it is possible to complete T into a tree [10].

o Create a forest of trees from the vertices

o Repeatedly merge trees by adding “safe edges” until only one tree remains. A “safe edge”
is an edge of minimum weight which does not create a cycle

Example:

Figure 3:4 Examples for Kruskal Algorithm

Kruskal Algorithm
procedure kruskalMST (G, cost, n, T)
i = mincost = 0
while i < n – 1 do
delete a minimum cost edge (u,v)

[58]
j = find(u)
k = find(v)
if j ≠ k then
i = i +1
T(i,1) = u; T(i,2) = v
mincost = mincost + cost(u,v)
union(j,k)
end if
end while
if i ≠ n-1 then return “no spanning tree”
return mincost
end procedure
o After each iteration, every tree in the forest is a MST of the vertices it connects
o Algorithm terminates when all vertices are connected into one tree
o Running time is bounded by sorting (or findMin): O (n2)

Correctness of Kruskal

If the algorithm is correct it halts with the right answer or optimal solution. Optimal solution is
obtained if:

o Kruskal algorithm adds n-1 edges (with minimum cost) to the spanning tree without
creating a cycle

Exercise: Create a Minimum Spanning tree using Kruskal algorithm with all necessary steps

3.5 Single Source Shortest Pattern

There are a few different types of shortest path problems. The simplest one is the single-source
shortest path problem. The most general statement of the problem is the shortest weighted
path problem. This is one of the hardest versions of the problem. A weighted path is a path in a
weighted graph. The weight of a path is the sum of the weights of the edges on the path. A weighted
path from a vertex s to a vertex v is a shortest weighted path if there is no other path in the graph

[59]
from s to v that has shorter weight. For convenience, when we say a shortest path we mean a
shortest weighted path, not a path with the fewest edges. The distance between two vertices is the
weight of a shortest path between the vertices.

The shortest path problem is the problem of finding a path between two vertices (or nodes) in a
graph such that the sum of the weights of its constituent edges is minimized. For example, finding
the shortest path between two intersections on a road.

Algorithms such as Breadth-First-Search (BFS) for unweighted graphs or Dijkstra algorithm

solve this problem.

Dijkstra's algorithm

Dijkstra's algorithm solves the shortest-path problem for any weighted, directed graph with non-
negative weights. With Dijkstra's Algorithm, you can find the shortest path between nodes in a
graph. Particularly, you can find the shortest path from a node (called the "source node") to all
other nodes in the graph, producing a shortest-path tree [11].

Basics of Dijkstra's Algorithm

o Dijkstra's Algorithm basically starts at the node that you choose (the source node) and it
analyzes the graph to find the shortest path between that node and all the other nodes in the
graph.

o The algorithm keeps track of the currently known shortest distance from each node to the
source node and it updates these values if it finds a shorter path.

o Once the algorithm has found the shortest path between the source node and another node,
that node is marked as "visited" and added to the path.

o The process continues until all the nodes in the graph have been added to the path. This way,
we have a path that connects the source node to all other nodes following the shortest path
possible to reach each node.

o Dijkstra's Algorithm can only work with graphs that have positive weights. This is because,
during the process, the weights of the edges have to be added to find the shortest path.

[60]
o If there is a negative weight in the graph, then the algorithm will not work properly. Once a
node has been marked as "visited", the current path to that node is marked as the shortest
path to reach that node. And negative weights can alter this if the total weight can be
decremented after this step has occurred.

For instance, consider the following graph. We will start with vertex A, So vertex A has a distance
0, and the remaining vertices have an undefined (infinite) distance from the source. Let S be the
set of vertices whose shortest path distances from the source are already calculated.

Initially, S contains the source vertex. S = {A}.

We start from source vertex A and start relaxing A's neighbors. Since vertex B can be reached
from a direct edge from vertex A, update its distance to 10 (weight of edge A–B). Similarly, we
can reach vertex E through a direct edge from A, so we update its distance from INFINITY to 3.

[61]
After processing all outgoing edges of A, we next consider a vertex having minimum distance. B
has a distance of 10, E has distance 3, and all remaining vertices have distance INFINITY. So, we
choose E and push it into set S. Now our set becomes S = {A, E}. Next, we relax with E's neighbors.
E has 2 neighbors B and C. We have already found one route to vertex B through vertex A having
cost 10. But if we visit a vertex B through vertex E, we are getting an even cheaper route, i.e., (cost
of edge A–E + cost of edge E–B) = 3 + 1 = 4 < 10 (cost of edge A–B).

[62]
We repeat the process till we have processed all the vertices, i.e., Set S becomes full.

[63]
Chapter three Review Questions

1) What is the difference between Dynamic programming and Greedy Algorithm?

2) Given a directed graph where every edge has weight as either 1 or 2, find the shortest path
from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is
O(V+E).
3) Considering the following graph, find the minimal spanning tree using prim’s algorithm
[64]
4) We have 6 files with size of 2, 3, 5, 7, 9, 13 and find optimal merge cost
5) Consider the below table for jobs given with profit and deadline:
Jobs J1 J2 J3 J4 J5 J6 J7 J8 J9

Profit 15 20 30 18 18 10 23 16 25

Deadline 7 2 5 3 4 5 2 7 3

Find the maximum profit earned?

[65]
 Chapter Four

4. Dynamic Programming and Traversal techniques

Dynamic programming computes its solution forward/backward by synthesizing them from
smaller sub-solutions, and by trying many possibilities and choices before it arrives at the optimal
set of choices There is no a priori test by which one can tell if the Greedy method will lead to an
optimal solution. By contrast, there is a test for Dynamic Programming, called The Principle of
Optimality [1].

The Principle of Optimality

In Dynamic programming an optimal sequence of decisions is obtained by making explicit appeal

to the principle of optimality.

Definition: A problem is said to satisfy the Principle of Optimality if the sub-solutions of an

optimal solution of the problem are themselves optimal solutions for their sub-problems.

o In solving a problem, we make a sequence of decisions D1, D2, ..., Dn. If this sequence is
optimal, then the k decisions also be optimal.

Examples: The shortest path problem satisfies the principle of optimality.

» This is because if a, x1, x2,..., xn, b is a shortest path from node a to node b in a graph, then the
portion of xi to xj on that path is a shortest path from xi to xj.
» DP reduces computation by:
o Storing solution to a sub-problem the first time it is solved
o Looking up the solution when sub-problem is encountered again
o Solving sub-problems in a bottom-up or top-down fashion

Dynamic programming (DP)

» DP is an algorithm design method that can be used when the solution to a problem can be
viewed as the result of a sequence of decisions.

[66]
Example: The solution to knapsack problem can be viewed as the result of a sequence of decisions.
We have to decide the values of xi , 1 ≤ i ≤ n. First we make a decision on x1, then x2 and so on.

» For some problems, an optimal sequence of decisions can be found by making the decisions
one at a time using greedy method. For other problems, it is not possible to make step-wise
decisions based on only local information. One way to solve such problems is to try all possible
decision sequences. However, time and space requirement is prohibitive.
» DP reduces those possible sequences not leading to optimal decision.
Dynamic programming approaches
» To solve a problem by using dynamic programming:
o Find out the recurrence relations.
✓ Dynamic programming is a technique for efficiently computing recurrences by
storing partial results
o Represent the problem by a multistage graph.
o In summary, if a problem can be described by a multistage graph, then it can be
solved by dynamic programming

Forward approach and backward approach

o If the recurrence relations are formulated using the backward approach, then the relations
is solved beginning with the last decision.
o If the recurrence relations are formulated using the forward approach, then the relations
are solved starting from the beginning until we each to the final decision
Example: 0-1 knapsack problem

[67]
4.1 Multistage graphs, all pairs shortest pattern

Find the shortest path in multistage graphs for the following example?

The greedy method cannot be applied to this case: (S, A, D, T) 1+4+18 = 23. The real shortest
path is: (S, C, F, T) 5+2+2 = 9.

The shortest path

» Given a multi-stage graph, how can I find a shortest path?

o Let p(i, j) denote the minimum cost path from vertex j to the terminal vertex T. Let
COST(i,j) denote the cost of p(i,j) path. Then using the
» Forward approach we obtain:
COST(i,j) = min { COST(i+1,k) + c(k,j)}
(j,k) Є E, k Є Vi+1

Backward approach: Let p(i,j) be a minimum cost path from vertex S to a vertex j in Vi . Let
COST(i,j) be the cost of p(i,j).

COST(i,j) = min { COST(i,k) + c(k,j-1)}

k Є Vi+1 (j,k) Є E

Note: If (i, j) is not element of E then COST(i, j) = inf.

Algorithm

procedure shortest_path (COST[], A[], n)

//cost[i,j] is the cost of edges[i,j] and A[i,j] is the shortest path from i to j

[68]
//cost[i,i] is 0.0
for i = 1 to n do
for j = 1 to n do
A(i, j) := COST(i, j) //copy cost into A
for k = 1 to do
for i = 1 to do
for j = 1 to do
A(i, j ) = min(A(i, j), A(i,k) + A(k,j));
end for
end for
end for
return A(1..n,1..n)
end shortest_path
o This algorithm runs in time O(n3)

4.2 Optimal binary search trees

Optimal Binary Search Tree extends the concept of Binary search tree. Binary Search Tree (BST)
is a nonlinear data structure which is used in many scientific applications for reducing the search
time. In BST, left child is smaller than root and right child is greater than root. This arrangement
simplifies the search procedure. Optimal Binary Search Tree (OBST) is very useful in dictionary
search. The probability of searching is different for different words. OBST has great application
in translation. If we translate the book from English to German, equivalent words are searched
from English to German dictionary and replaced in translation.

Words are searched same as in binary search tree order. Binary search tree simply arranges the
words in lexicographical order. Words like ‘the’, ‘is’, ‘there’ are very frequent words, whereas
words like ‘xylophone’, ‘anthropology’ etc. appears rarely. It is not a wise idea to keep less
frequent words near root in binary search tree. Instead of storing words in binary search tree in
lexicographical order, we shall arrange them according to their probabilities. This arrangement

[69]
facilitates few searches for frequent words as they would be near the root. Such tree is
called Optimal Binary Search Tree.

Consider the sequence of n keys K = < k1, k2, k3, …, kn> of distinct probability in sorted order
such that k1< k2< … <kn. Words between each pair of key lead to unsuccessful search, so for n
keys, binary search tree contains n + 1 dummy keys di, representing unsuccessful searches. Two
different representations of BST with same five keys {k1, k2, k3, k4, k5} probability is shown in
following figure.
With n nodes, there exist Ω(4n / n3/2) different binary search trees. An exhaustive search for optimal
binary search tree leads to huge amount of time.
The goal is to construct a tree which minimizes the total search cost. Such tree is called optimal
binary search tree. OBST does not claim minimum height. It is also not necessary that parent of
sub tree has higher priority than its child. Dynamic programming can help us to find such optima
tree.

Figure 4:1: Binary search trees with 5 keys

Mathematical formulation

o We formulate the OBST with following observations

o Any sub tree in OBST contains keys in sorted order ki…kj, where 1 ≤ i ≤ j ≤ n.
o Any sub tree in OBST contains keys in sorted order ki…kj, where 1 ≤ i ≤ j ≤ n.

[70]
 o Suppose kr is the root of sub tree containing keys ki…..kj. So, left sub tree of root
kr contains keys ki….kr-1 and right sub tree contain keys kr+1 to kj. Recursively, optimal sub
trees are constructed from the left and right sub trees of kr.

o Let e[i, j] represents the expected cost of searching OBST. With n keys, our aim is to find
and minimize e[1, n].
o Base case occurs when j = i – 1, because we just have the dummy key di-1 for this case.
Expected search cost for this case would be e[i, j] = e[i, i – 1] = qi-1.
o For the case j ≥ i, we have to select any key kr from ki…kj as a root of the tree.
o With kr as a root key and sub tree ki…kj, sum of probability is defined as

Thus, a recursive formula for forming the OBST is stated below:

e[i, j] gives the expected cost in the optimal binary search tree.

Algorithm for Optimal Binary Search Tree

The algorithm for optimal binary search tree is specified below:

Algorithm OBST(p, q, n)
// e[1…n+1, 0…n ] : Optimal sub tree
// w[1…n+1, 0…n] : Sum of probability
// root[1…n, 1…n] : Used to construct OBST
for i ← 1 to n + 1 do
e[i, i – 1] ← qi – 1
w[i, i – 1] ← qi – 1
end

[71]
for m ← 1 to n do
for i ← 1 to n – m + 1 do
j←i+m–1
e[i, j] ← ∞
w[i, j] ← w[i, j – 1] + pj + qj
for r ← i to j do
t ← e[i, r – 1] + e[r + 1, j] + w[i, j]
if t < e[i, j] then
e[i, j] ← t
root[i, j] ← r
end
end
end
end
return (e, root)
The OBST algorithm runs in cubic time.

4.3 0/1 Knapsack

The problem is called a “0-1” problem, because each item must be entirely accepted or rejected.
Just another version of this problem is the “Fractional Knapsack Problem”, where we can take
fractions of items.

Given a knapsack with maximum capacity W, and a set of n items with weight w1, w2, , wn and
benefit value p1, p2, …, pn (all wi, pi & W are integer values), the problem is:

o How to pack the knapsack to achieve maximum total value of packed items? That is:

[72]
0/1 Knapsack: DP approach

» To solve a knapsack problem, we need to carefully identify the sub-problems. If items are
labeled 1…n, then a sub-problem would be to find an optimal solution for Sk = {items
labeled 1, 2, .. k} along with w, which will represent the exact weight for each subset of
items [7].
» The sub-problem then will be to compute S [k, w]

First
case: wk>w. Item k can’t be part of the solution, since if it was, the total weight would be >
w, which is unacceptable.
Second case: wk <=w. Then the item k can be in the solution, and we choose the case with
greater value.
0-1 Knapsack Algorithm

procedure DPknapsack(P[], w[], W, n)

for w = 0 to W do
S[0,w] = 0
for i = 1 to n do
S[i,0] = 0
for w = 1 to W do
if wi <= w then // item i can be part of the solution
if pi + S[i-1,w-wi] > S[i-1,w] then
S[i,w] = pi + S[i-1,w- wi]
else
S[i,w] = S[i-1,w]

else S[i,w] = S[i-1,w] // wi > w

end procedure

» Running time is reduced from O (2n) (brute force approach) to O(n*W)

[73]
Example:

Let’s run our algorithm on the following data: n = 4 (# of elements) W = 5 (max weight)
Elements (weight, profit): (2,3), (3,4), (4,5), (5,6).

4.4 Reliability design

Reliability means the ability of an apparatus, machine, or system to consistently perform its
intended or required function or mission, on demand and without degradation or failure. Reliability
design using dynamic programming is used to solve a problem with a multiplicative optimization
function. The problem is to design a system which is composed of several devices connected in
series (below Fig-3.3(b)). Let r; be the reliability of device D; (i.e. r; is the probability that device
i will function properly). Then, the reliability of the entire system is πri . Even if the individual
devices are very reliable (the ri 's are very close to one), the reliability of the system may not be
very good [7].

Figure 4:2 Devices connected in series

Figure 4:3 Multiple Devices Connected in Parallel in each stage

[74]
Multiple copies of the same device type are connected in parallel (Fig-3.3(b)) through the use of
switching circuits. The switching circuits determine which devices in any given group are
functioning properly. They then make use of one such device at each stage.

If stage i contains mi copies of device Di then the probability that all mi have a malfunction is (1
- ri) mi. Hence the reliability of stage i becomes 1 - (1 - ri) m i. Thus, if ri = 0.99 and mi = 2 the stage
reliability becomes 0.9999. In any practical situation, the stage reliability will be a little less than
m
1 - (1 - ri) i because the switching circuits themselves are not fully reliable. Also, failures of
copies of the same device may not be fully independent (e.g. if failure is due to design defect). Let
us assume that the reliability of stage i is actually given by a function Φi(mi), 1<=i<=n. (It is quite
conceivable that Φi(mi) may decrease after a certain value of m ;). The reliability of the system of
stages is ∏1<=i<=nΦi(mi).

Our problem is to use device duplication to maximize reliability. This maximization is to be carried
out under a cost constraint. Let ci be the cost of each unit of device i and let c be the maximum
allowable cost of the system being designed.

We wish to solve the following maximization problem:

maximize ∏1<=i<=nΦi(mi)

subject to ∑1<=i<=n cimi <=c

mi>=1 and integer i, 1<=i<=n

dynamic programming solution may be obtained in a manner similar to that used for the knapsack
problem. Since, we may assume each ci; > 0, each mi must be in the range 1<=mi<=ui where

The upper bound ui follows from the observation that mj>=1. An optimal solution m1, m2, •••, mn
is the result of a sequence of decisions, one decision for each mi. Let fi(x) represent the maximum
value of Φ(mj), 1<=j<=i subject to the constraints. ∑1<=j<=i cjmj <=x and 1<=mj<=uj, 1<=j<=i.
Then, the value of an optimal solution is fn(c). The last decision made requires one to choose mn
from one of { l, 2, 3, ... , un.}. Once a value for mn has been chosen, the remaining decisions must

[75]
be such as to use the remaining funds c - cnmn in an optimal way. The principal of optimality holds
and

For any fi(x), i>=1 this equation generalizes to

4.5 Travelling salesman problem

Problem Statement: A traveler needs to visit all the cities from a list, where distances between
all the cities are known and each city should be visited just once. What is the shortest possible
route that he visits each city exactly once and returns to the origin city?

Solution

➢ Travelling salesman problem is the most notorious computational problem. We can use
brute-force approach to evaluate every possible tour and select the best one. For n number
of vertices in a graph, there are (n - 1)! number of possibilities
➢ Instead of brute-force using dynamic programming approach, the solution can be obtained
in lesser time, though there is no polynomial time algorithm
➢ Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted
edges. An edge e(u, v) represents that vertices u and v are connected. Distance between
vertex u and v is d(u, v), which should be non-negative.
➢ Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence,
this is a partial tour. We certainly need to know j, since this will determine which cities are
most convenient to visit next. We also need to know all the cities visited so far, so that we
don't repeat any of them. Hence, this is an appropriate sub-problem
➢ For a subset of cities S Є {1, 2, 3, ... , n} that includes 1, and j Є S, let C(S, j) be the length
of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.
➢ When |S| > 1, we define C(S, 1) = ∝ since the path cannot start and end at 1. Now, let
express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We
should

[76]
 select the next city in such a way that

Algorithm: Traveling-Salesman-Problem

C ({1}, 1) = 0

for s = 2 to n do

for all subsets S Є {1, 2, 3, …, n} of size s and containing 1

C (S, 1) = ∞

for all j Є S and j ≠ 1

C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}

Return minj C ({1, 2, 3, …, n}, j) + d(j, i).

Analysis

There are at the most 2n.n sub-problems and each one takes linear time to solve. Therefore, the
total running time is O (2n. n2).

4.6 Game trees

A game tree is a graph representing all possible game states within such a game. Such games
include well-known ones such as chess, checkers, Go, and tic-tac-toe. This can be used to measure
the complexity of a game, as it represents all the possible ways a game can pan out. Due to the
large game trees of complex games such as chess, algorithms that are designed to play this class
of games will use partial game trees, which makes computation feasible on modern computers.
Various methods exist to solve game tree. To better understand the game tree, it can be thought of
as a technique for analyzing adversarial games, which determine the actions that player takes to
win the game. In game theory, a game tree is a directed graph whose nodes are positions in a game
(e.g., the arrangement of the pieces in a board game) and whose edges are moves (e.g., to move
pieces from one position on a board to another).

[77]
The number of leaf nodes in the complete game tree is the number of possible different ways the
game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes.

4.7 Disconnected components

A graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph
G is disconnected, then every maximal connected subgraph of G is called a connected component
of the graph G. A component of a graph is defined as a maximal subgraph in which a path exists
from every node to every other (i.e., they are mutually reachable). The size of a component is
defined as the number of nodes it contains. A connected graph has only one component.

How to numbers of disconnected components

➢ Create a adjacency list to store connected nodes in a graph. remember graph here is a
undirected so, if 1 -> 2 then 2 -> 1.
➢ Maintain visited array in order to avoid infinite loop.
➢ Now loop for each node and whenever disconnected component found increment ans
variable.

4.8 Depth first search

In depth-first search, we visit the starting node and then proceed to follow links through the graph
until we reach a dead end. In an undirected graph, a node is a dead end if all of the nodes adjacent
to it have already been visited. In a directed graph, if a node has no outgoing edges, we also have

[78]
a dead end. When we reach a dead end, we back up along our path until we find an unvisited
adjacent node and then continue in that new direction. The process will have completed when we
back up to the starting node and all the nodes adjacent to it have been visited. In illustrating this
algorithm and all others in this chapter, if presented with a choice of two nodes, we will choose
the node with the numerically or alphabetically smaller label. When this algorithm is implemented,
that choice will depend on how the edges of the graph are stored [12].

Consider the graph in above, if we begin the depth-first traversal at node 1, we then visit, in order,
the nodes 2, 3, 4, 7, 5, and 6 before we reach a dead end. We would then back up to node 7 to find
that node 8 hasn’t been visited, but that immediately leads to a dead end. We next back up to node
4 and find that node 9 hasn’t been visited, but again we have an immediate dead end. We then
continue to back up until we reach the starting node, and because all nodes adjacent to it have been
visited, we are done.

Algorithm for depth-first search

DepthFirstSearch (G, v)
G is the graph
v is the current node
Visit( v )
Mark( v )
for every edge vw in G do
if w is not marked then
DepthFirstSearch (G, w)

[79]
end if
end for
This recursive algorithm relies on the system stack of the computer to keep track of where it has
been in the graph so that it can properly back up when it reaches dead ends. We could create a
similar non recursive algorithm by using a stack data structure and pushing and popping graph
vertices ourselves.

Chapter four Review Questions

1) What meant by Principle of Optimality in dynamic programming?

2) Find a minimum cost path from ‘S’ to ‘t’ in multistage graph using dynamic programming?

3) Design a three-stage system with device types D1, D2, D3. The costs are Rs. 30, Rs. 15 and
Rs. 20 respectively. The cost of the system is to be no more than Rs. 105. The reliability of
each device type is 0.9,0.8 and 0.5 respectively.
4) Problem: Let p (1: 3) = (0.5, 0.1, 0.05) q (0: 3) = (0.15, 0.1, 0.05, 0.05) Compute and construct
OBST for above values using Dynamic approach.
5) Solve knapsack instance M=8, and n=4. let pi and wi are as shown below

[80]
 Chapter Five

5. Back Tracking
It is a systematic way to search for a solution to a problem among all available options in a search
space. It does so by assuming that the solutions are represented by vectors (v1, ..., vm) of values
and by traversing, in a depth first manner, the domains of the vectors until the solutions are found

o Often the problem to be solved calls for finding one vector that maximizes (or minimizes
or satisfies) a criterion function P (x1, ..., xm).

We build from a partial solution of length k, v = (a1, ..., ak) and try to extend it by adding another
element. After extending it, we will test whether what we have so far is still possible as a partial
solution [1].

o If it is still a candidate solution, great. If not, we delete ak and try the next element from
Sk:

Backtracking approach

An important requirement in backtracking is that there must be proper hierarchy in systematically

searching for solutions so that sets of solutions that do not fulfill a certain requirement are rejected
before the solutions are produced.

o For this reason the examination and production of the solutions follows a model of non-
cycle graph for which in this case we will consider as a tree.
o It is easily understood that the tree (or any other graph) is produced during the examination
of the solutions so that no rejected solutions are produced.
o When a node is rejected, the whole sub-tree is rejected, and we backtrack to the ancestor
of the node so that more children are produced and examined.

5.1 The Queens Problem

» Consider a n by n chess board, and the problem of placing n queens on the board without the
queens threatening one another.

[81]
» The solution space is {1, 2, 3,…, n} n. The backtracking algorithm may record the columns
where the different queens are positioned. Trying all vectors (p1, ..., pn) implies nn cases
queens threatening one another.
» Noticing that all the queens must reside in different columns reduces the number of cases to n!
» For the latter case, the root of the traversal tree has degree n, the children have degree n - 1,
the grandchildren degree n - 2, and so forth.

How backtracking works

» As a bounding function we use if (x1, ..., xi) is the path to the current E-node (node being
expanded), then all children nodes with parent-child labeling xi+1 are such that (x1, ..., xi+1)
represents the chessboard configuration in which no two queens are attacking.
» Start with the root node as the only live node. This become the E-node and the path is ().
Generate one child (say 2). The path is now (1), which corresponds to placing queen 1 on
column 1
» Node 2 becomes the E-node. Node 3 is then generated. If the node is attacked by the previous
node, the path is immediately killed. Otherwise add to the path list (1, 2) and generate the next
node. If the path cannot lead to an answer node then backtrack and try another path.

5.1.1 8 queen problem

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that
none of them attack one another (no two are in the same row, column, or diagonal). More
generally, the n queens problem places n queens on an n×n chessboard.

[82]
Algorithm for n-queens

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two
queens attack each other.

» Let (x1, ..., xn) represent a solution in which xi is the column of the ith row where the ith queen
is placed. All xi’s be distinct since no two queens can be placed in the same column.
o Computing time = 0 + 1 + 2 + … + n

Algorithm

procedure NQueens (k, n)

for i = 1 to n do
if place (k, i) then
x[k] = i
if k = n then print (x[1: n])
else NQueens (k+1, n)
end if
end for
end NQueens
procedure place (k, i) //returns true if a queen is placed at (k,i)
for j = 1 to k-1 do
if (x[j] = i) or ((abs(x[j] - i) = (abs (j - k)) then
//two in the same column or in the same diagonal
return false
return true
end place

5.2 Graph coloring and Hamiltonian cycles

Both are the algorithm of backtracking. It is an algorithmic technique where the goal is to get all
solutions to a problem using the brute force approach. It consists of building a set of all the

[83]
solutions incrementally. Since a problem would have constraints, the solutions that fail to satisfy
them will be removed.

5.2.1 Graph coloring

We have been given a graph and we are asked to color all vertices with the ‘M’ number of given
colors, in such a way that no two adjacent vertices should have the same color.

Figure 5:1 Graph Coloring

It is possible to color all the vertices with the given colors then we have to output the colored
result, otherwise output ‘no solution possible.

Graph Coloring Solution using Backtracking Algorithm

In this approach, we color a single vertex and then move to its adjacent (connected) vertex to color
it with different color. After coloring, we again move to another adjacent vertex that is uncolored
and repeat the process until all vertices of the given graph are colored.

In case, we find a vertex that has all adjacent vertices colored and no color is left to make it color
different, we backtrack and change the color of the last-colored vertices and again proceed further.

If by backtracking, we come back to the same vertex from where we started and all colors were
tried on it, then it means the given number of colors (i.e. ‘m’) is insufficient to color the given
graph and we require more colors (i.e. a bigger chromatic number).

Steps To color graph using the Backtracking Algorithm:

» Different colors:

[84]
 o Confirm whether it is valid to color the current vertex with the current color (by
checking whether any of its adjacent vertices are colored with the same color)
o If yes then color it and otherwise try a different color
o Check if all vertices are colored or not
o If not then move to the next adjacent uncolored vertex.
» If no other color is available then backtrack (i.e. un-color last colored vertex).

5.2.2 Hamiltonian cycles

Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A
Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in
the graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a
given graph contains Hamiltonian Cycle or not. If it contains, then prints the path. Following are
the input and output of the required function.

Input: A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is
adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge
from i to j, otherwise graph[i][j] is 0.

Output: An array path[V] that should contain the Hamiltonian Path. path[i] should represent the
ith vertex in the Hamiltonian Path. The code should also return false if there is no Hamiltonian
Cycle in the graph.

Figure 5:2 Graph and its Hamiltonian Circle

[85]
How to Find the Hamiltonian Cycle using Backtracking?

» Using the backtracking method, we can easily find all the Hamiltonian Cycles present in the
given graph.
» The idea is to use the Depth-First Search algorithm to traverse the graph until all the vertices
have been visited.
» We traverse the graph starting from a vertex (arbitrary vertex chosen as starting vertex) and
» At any point during the traversal, we get stuck (i.e., all the neighbor vertices have been
visited), we backtrack to find other paths (i.e., to visit another unvisited vertex)
» If we successfully reach back to the starting vertex after visiting all the nodes, it means the
graph has a Hamiltonian cycle otherwise not.

5.3 Knapsack problems

The knapsack is nothing but a sack where in which we need to place the given items according to
the capacity of the knapsack. The knapsack problem is useful in solving resource allocation
problems.

o Let X = <x1, x2, x3, . . . ., xn> be the set of n items, W = <w1, w2, w3, . . . , wn> and V =
<v1, v2, v3, . . . ,vn> be the set of weight and value associated with each item in X,
respectively.
o Let M be the total capacity of the knapsack, i.e. knapsack cannot hold items having a
collective weight greater than M.
o Select items from X such that it maximizes the profit and the collective weight of selected
items does not exceed the knapsack capacity.
o The knapsack problem has two variants. 0/1 knapsack does not allow breaking up the item,
whereas a fractional knapsack does. 0/1 knapsack is also known as a binary knapsack.
o The Knapsack problem can be formulated as, Maximize
subjected to
✓ xi in (0,1) for binary knapsack
✓ xi in 0,1 for fractional knapsack
Algorithm:
Bound (CP, CW, K) {

[86]
 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] ;
return b; }}

5.4 0/1 Knapsack problems

The 0/1 Knapsack problem can also make the use of back tracking algorithm. Here, we are given
a knapsack with ‘n’ number of objects such that i= 1 ,2,3,4,…,n and each of these objects are
assigned their weights ‘wi’ and values ‘vi’ respectively. The ambition of this problem is to
determine the maximum values of the objects which shall fill the knapsack such that the total
weights of those objects won’t exceed ‘W’. As this is a 0/1 problem, we are only allowed to take
either the whole/complete object or not. We shall not be allowed to take any fractional values of
the object. Thus, we can express the problem mathematically as follows:

Maximize ∑𝑖=1
𝑛 (𝑣 i ) Such that: ∑𝑖=1
𝑛 (𝑤 i) <=W
Thus, this mathematical representation depicts that the solution to fill the knapsack shall contain
all those objects whose weight shall not exceed the given maximum Weight, but shall contain the
maximum sum of the values vi.

EXAMPLE

The example depicts a 0/1 Knapsack problem with 5 different objects. These objects have the
weights as 3,4,9,10,12 units respectively and their corresponding values are 4,15,18,25,30. Now,
we are provided this problem to determine a solution such that we can maximize these values
where the total weight does not exceed 15. These weights and values are represented in the tabular
form:

Weights(wi) 3 4 9 10 12

[87]
 Values(vi) 4 15 18 25 30

In this solution, we shall take the objects in their ascending order of weights. Though it is not
essential to stick to a specific ordering of the weight values, we have selected this approach as it
allows reducing the depth of the trees when considered in either ascending or the descending order.
Furthermore, each node on the tree structure depicted by the example can be interpreted as follows:

3,9;22

This implies, the node consists of objects of weight 3 & 9, and the summation of their values is
22. We shall interpret all the other nodes similarly. Also, it is notable that the number of objects in
each node is equal to the depth of that node in the given tree structure.

5.4.1 Interpreting the solution

The tree structure thus constructed shall be parsed in the Depth First Search technique. Thus, for
each node, the depth is parsed, rather than parsing through the breadth. Here, once we start from
root node (;0), we shall parse through the tree as follows:

(;0)-----> (3;4)---->(3,3;8)---->(3,3,3;12)----->(3,3,3,3;16)----->(3,3,3,3,3;20)

[88]
From this parsing the current optimal solution shall be (3,3,3,3,3;20)

Similarly, parsing the second branch, we get,

( ;0)----->(3;4)----->(3,3;8)------->(3,3,4;23)------>(3,3,4,4;39)

As of now, the optimal solution becomes (3,3,4,4;39)

Again, let us parse through other branches:

( ;0)---->(3;4)----->(3,3;8)----->(3,3,9;26)

(;0)---→(3;4)----->(3,4;19)------>(3,4,4;34)------->(3,4,4,4;49)

As, for now the new optimal solution is (3,4,4,4;49).

Again, parsing through all other branches, we come to a conclusion that the highest count of values
is in node (3,4,4,4;49). Thus, the best solution is the set of objects with weights: 3,4,4 and 4,
totaling the value of 49.

ALGORITHM

The following algorithm employs back tracking mechanism to determine appropriate weighted
objects that satisfy the condition of having maximum weight W. Here, arrays w[] and v[]
represents the weights and values corresponding to each objects respectively. Also, n represents
the number of the objects and W represents the maximum weight allowed to be used in the
knapsack.

1. function backTrackSack(m,W)
2. {
3. value =0;
4. for i = m to n
5. {
6. if (w[i]<=W)
7. {
8. value =maximum(value, v[i]+backTrackSack(i,W-w[i]))
9. }
10. return Value;
11. }

The above depicted function performs the depth first search in the tree structure thus created and
determines an appropriate solution that satisfies the given condition. Line 8 in this function
performs the DFS.

[89]
Also, we define the maximum() function as follows:
function maximum(x,y)
{
if(x>y)
return x;
return y;
}
This function is a simple helper function which returns the largest value among the given two
parameters.

5.5 Travelling sales person problems (TSP)

The problem assumes a set of n cities, and a salesperson which needs to visit each city exactly
once and return to the base city at the end. The solution should provide a route of minimal length.
The traveling salesperson problem is an NP-hard problem, and so no polynomial time algorithm
is available for it.

Given an instance G = (V, E) the backtracking algorithm may search for a vector of cities (v1, ...,
v|V |) which represents the best route.

The validity criteria may just check for number of cities in the routes, pruning out routes longer
than |V |. In such a case, the algorithm needs to investigate |V ||V | vectors from the solution space.

Traveling Salesperson

» On the other hand, the validity criteria may check for repetition of cities, in which case the
number of vectors reduces to |V |!.
» That is, complexity = n!

[90]
 » Given the following problem, starting from city „a‟ apply backtracking algorithm to find
the shortest path to visit all cities (and back to city a).

» The route (a, b, d, c) is the shortest one with length = 51. Can we reach to this decision
using backtracking algorithm?

Branch and Bound Algorithm

Approach

o Track the best current solution found

o Eliminate partial solutions that cannot improve upon best current solution
o Reduces amount of backtracking
o Not guaranteed to avoid exponential time O(2n)

Example: Travel Salesperson

» Branch and bound algorithm for TSP

o Find possible paths using recursive backtracking
o Track cost of best current solution found
o Stop searching path
✓ if cost > best current solution
o Return lowest cost path
» If good solution found early, can reduce search
» May still require exponential time O(2n)

[91]
Chapter five Review Questions
1) Consider knapsack problem: n = 8. (W1, W2, W3, W4, W5, W6, W2, W8) = (1, 11, 21, 23, 33,
43, 45, 55), P = (11, 21, 31, 33, 43, 53, 55, 65), m = 110. Solve the problem using backtracking
approach.
2) The following graph shows a set of cities and distance between every pair of cities-

If salesman starting city is A, then find TSP tour and cost of the tour?
3) Consider a graph G = (V, E) shown in fig. below. find a Hamiltonian circle using
Backtracking method

4) How Backtracking is used to find Hamiltonian cycle?

5) How Branch and bound algorithm works for TSP?

[92]
References
[1] “Ambo University @ Woliso Campus School of Technology and Informatics Computer
Science Department Analysis of Algorithm Course Full hondout Program : Extension
Semister : II Course Code : CoSc 3131 Prepared and Compiled by : Yoobsan Bechera (
BSc ) May / 2,” 2020.

[2] C. G. Jennings, Review of Analysis of Algorithms:An Active Learning Approach , vol. 32,
no. 4. 2001. doi: 10.1145/568425.568430.

[3] JavaTpoint, “Data Structure,” 2021. https://www.javatpoint.com/data-structure-

introduction (accessed Aug. 25, 2022).

[4] K. Jung, “Design and Analysis of Algorithm Branch-and-Bound Technique,” 2013.

[5] J. Bullinaria, “Lecture Notes for Data Structures and Algorithms,” Sch. Comput. Sci. Univ.
Birmingham, no. March, p. 126, 2019, [Online]. Available:
https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf

[6] CODECRUCKS, “Set Representation Methods,” 2021. https://codecrucks.com/set-theory-

mathematics-for-algorithm/ (accessed Aug. 25, 2022).

[7] B. T. Iii and Y. I. Sem, “Lecture Notes Department of Computer Science and Engineering
Malla Reddy College of Engineering & Technology,” vol. 2, 2019.

[8] “Divide-and-Conquer Divide a problem into subprograms of the same kind ; solve
subprograms using the same approach , and combine partial,” pp. 1–23.

[9] S. Sahni, Analysis of Algorithms. 2004. doi: 10.1201/9781420035179.pt1.

[10] S. Radhakrishnan, D. Kolippakkam, and V. S. Mathura, Introduction to algorithms. 2007.

doi: 10.1007/978-0-387-84870-9_3.

[11] Programiz, “Dijkstra’s Algorithm.” https://www.programiz.com/dsa/dijkstra-

algorithm#:~:text=Dijkstra’s algorithm allows us to,the vertices of the graph. (accessed
Aug. 26, 2022).

[12] D. Self, A creative approach, vol. 10, no. 1. 1970. doi: 10.1080/00239707008556880.

[93]