DESIGN AND ANALYSIS OF ALGORITHMS

Module 1
INTRODUCTION
Saravana M K
Assistant Professor
Department of CSD
DSATM
Why do you need to study algorithms?
• From a practical standpoint, you have to know a standard set of important
algorithms from different areas of computing;
• In addition, you should be able to design new algorithms and analyze their
efficiency.
• From the theoretical standpoint, the study of algorithms, sometimes called
algorithmics, has come to be recognized as the cornerstone of computer
science.
• Algorithms can be seen as special kinds of solutions to problems, not just
answers but precisely defined procedures for getting answers.
• Consequently, specific algorithm design techniques can be interpreted as
problem solving strategies that can be useful regardless of whether a
computer is involved.
What Is an Algorithm?
• An algorithm is a sequence of unambiguous instructions for solving a
problem, i.e., for obtaining a required output for any legitimate input
in a finite amount of time.
 Contd..
• As examples illustrating the notion of the algorithm, we consider in this
section three methods for solving the same problem:
• Computing the greatest common divisor of two integers.
• These examples will help us to illustrate several important points:
• The non ambiguity requirement for each step of an algorithm cannot be
compromised.
• The range of inputs for which an algorithm works has to be specified
carefully.
• The same algorithm can be represented in several different ways.
• There may exist several algorithms for solving the same problem.
• Algorithms for the same problem can be based on very different ideas and
can solve the problem with dramatically different speeds.
Contd..
• The greatest common divisor of two nonnegative, not-both-zero integers m
and n, denoted gcd(m, n), is defined as the largest integer that divides both m
and n evenly, i.e., with a remainder of zero.
• Euclid of Alexandria (third century b.c.) outlined an algorithm for solving this
problem in one of the volumes of his Elements most famous for its systematic
exposition of geometry.
• In modern terms, Euclid’s algorithm is based on applying repeatedly the
equality gcd(m, n) = gcd(n, m mod n),
• where m mod n is the remainder of the division of m by n, until m mod n is
equal to 0.
• Since gcd(m, 0) = m, the last value of m is also the greatest common divisor of
the initial m and n.
• For example, gcd(60, 24) can be computed as follows:
• gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.
Contd..
• Here is a more structured description of this algorithm:
• Euclid’s algorithm for computing gcd(m, n)
• Step 1 If n = 0, return the value of m as the answer and stop;
otherwise,
• proceed to Step 2.
• Step 2 Divide m by n and assign the value of the remainder to r.
• Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.
• Alternatively, we can express the same algorithm in pseudocode:
Contd.,
• ALGORITHM Euclid(m, n)
• //Computes gcd(m, n) by Euclid’s algorithm
• //Input: Two nonnegative, not-both-zero integers m and n
• //Output: Greatest common divisor of m and n
• while n = 0 do
r ←m mod n
m←n
n←r
• return m
Contd.,
• Consecutive integer checking algorithm for computing gcd(m, n)
• Step 1 Assign the value of min{m, n} to t.
• Step 2 Divide m by t. If the remainder of this division is 0, go to Step
3; otherwise, go to Step 4.
• Step 3 Divide n by t. If the remainder of this division is 0, return the
value of t as the answer and stop; otherwise, proceed to Step 4.
• Step 4 Decrease the value of t by 1. Go to Step 2.
Contd.,
• Find gcd(24, 16)
• 𝑡 = min 24 16 = 16
• Check 24 mod 16 ≠ 0→ decrease 𝑡
• 𝑡 = 15,14,13,12,11,10,9→ not divisors
• 𝑡=8
• 24 mod 8 = 0
• 16 mod 8 = 0
• Therefore,
• gcd 24 16 = 8
Contd.,
• Unlike Euclid’s algorithm, this algorithm, in the form presented, does
not work correctly when one of its input numbers is zero.
• This example illustrates why it is so important to specify the set of an
algorithm’s inputs explicitly and carefully.
Contd.,
• Middle-school procedure for computing gcd(m, n)
• Step 1 Find the prime factors of m.
• Step 2 Find the prime factors of n.
• Step 3 Identify all the common factors in the two prime expansions
found in Step 1 and Step 2. (If p is a common factor occurring pm and pn
times in m and n, respectively, it should be repeated min{pm, pn} times.)
• Step 4 Compute the product of all the common factors and return it as
the greatest common divisor of the numbers given.
Contd.,
• For the numbers 60 and 24, we get
• 60 = 2 . 2 . 3 . 5
• 24 = 2 . 2 . 2 . 3
• gcd(60, 24) = 2 . 2 . 3 = 12.
Fundamentals of Algorithmic Problem Solving
1. Understanding the Problem
• From a practical perspective, the first thing you need to do before designing an
algorithm is to understand completely the problem given.
• Read the problem’s description carefully and ask questions if you have any doubts
about the problem, do a few small examples by hand, think about special cases,
and ask questions again if needed.
• An input to an algorithm specifies an instance of the problem the algorithm
solves.
• It is very important to specify exactly the set of instances the algorithm needs to
handle.
• If you fail to do this, your algorithm may work correctly for a majority of inputs
but crash on some “boundary” value.
• Remember that a correct algorithm is not one that works most of the time, but
one that works correctly for all legitimate inputs.
2. Ascertaining the Capabilities of the Computational Device
• Once a problem completely understood, you need to ascertain the
capabilities of the computational device the algorithm is intended for.
• The vast majority of algorithms in use today are still destined to be
programmed for a computer closely resembling the von Neumann
machine.
• Its central assumption is that instructions are executed one after
another, one operation at a time. Accordingly, algorithms designed to
be executed on such machines are called sequential algorithms.
• The essence of this architecture is captured by the so-called random-
access machine (RAM).
 Contd..
• The central assumption of the RAM model does not hold for some
newer computers that can execute operations concurrently, i.e., in
parallel.
• Algorithms that take advantage of this capability are called parallel
algorithms.
Choosing between Exact and Approximate Problem Solving
• The next principal decision is to choose between solving the problem
exactly or solving it approximately.
• In the former case, an algorithm is called an exact algorithm;
• In the latter case, an algorithm is called an approximation algorithm.
• An approximation algorithm is opted for two reasons:
1. There are important problems that simply cannot be solved exactly for
most of their instances;
• Examples: extracting square roots, solving nonlinear equations, and evaluating
definite integrals.
2. The available algorithms for solving a problem exactly can be
unacceptably slow because of the problem’s intrinsic complexity
 Algorithm Design Techniques
• What is an algorithm design technique?
• An algorithm design technique (or “strategy” or “paradigm”) is a general
approach to solving problems algorithmically that is applicable to a variety
of problems from different areas of computing.
• Learning these techniques is of utmost importance for the following
reasons.
• They provide guidance for designing algorithms for new problems, i.e.,
problems for which there is no known satisfactory algorithm.
• Algorithms are the cornerstone of computer science.
• Algorithm design techniques make it possible to classify algorithms
according to an underlying design idea; therefore, they can serve as a
natural way to both categorize and study algorithms.
 Designing an Algorithm and Data Structures
• While the algorithm design techniques do provide a powerful set of general
approaches to algorithmic problem solving, designing an algorithm for a
particular problem may still be a challenging task.
• Some design techniques can be simply inapplicable to the problem in
question.
• Sometimes, several techniques need to be combined, and there are
algorithms that are hard to pinpoint as applications of the known design
techniques.
• Even when a particular design technique is applicable, getting an algorithm
often requires a nontrivial ingenuity on the part of the algorithm designer.
• With practice, both tasks get easier, but they are rarely easy.
Methods of Specifying an Algorithm
• Once you have designed an algorithm, you need to specify it in some
fashion.
• The two options that are most widely used nowadays for specifying
algorithms are:
1. Using a natural language has an obvious appeal; however, the
inherent ambiguity of any natural language makes a succinct and
clear description of algorithms surprisingly difficult.
2. The Pseudocode is a mixture of a natural language and
programming language like constructs. Pseudocode is usually more
precise than natural language.
Proving an Algorithm’s Correctness
• Once an algorithm has been specified, you have to prove its
correctness.
• That is, you have to prove that the algorithm yields a required result
for every legitimate input in a finite amount of time.
• For some algorithms, a proof of correctness is quite easy; for others,
it can be quite complex.
• A common technique for proving correctness is to use mathematical
induction because an algorithm’s iterations provide a natural
sequence of steps needed for such proofs.
Analyzing an Algorithm
• We usually want our algorithms to possess several qualities.
• After correctness, by far the most important is efficiency.
• There are two kinds of algorithm efficiency: time efficiency, indicating
how fast the algorithm runs, and space efficiency, indicating how
much extra memory it uses.
• Another desirable characteristic of an algorithm is simplicity. Because
simpler algorithms are easier to understand and easier to program;
• Another desirable characteristic of an algorithm is generality. There
are, in fact, two issues here: generality of the problem the algorithm
solves and the set of inputs it accepts.
Coding an Algorithm
• Most algorithms are destined to be ultimately implemented as
computer programs.
• Some influential computer scientists strongly believe that unless the
correctness of a computer program is proven with full mathematical
rigor, the program cannot be considered correct.
• As a practical matter, the validity of programs is still established by
testing.
• Implementing an algorithm correctly is necessary but not sufficient:
• Don't diminish the algorithm’s power by an inefficient
implementation.
Important Problem Types
• The most important problem types:
• Sorting
• Searching
• String processing
• Graph problems
• Combinatorial problems
• Geometric problems
• Numerical problems
Contd..
• The sorting problem is to rearrange the items of a given list in
nondecreasing order. For this problem to be meaningful, the nature of the
list items must allow such an ordering.
• The searching problem deals with finding a given value, called a search
key, in a given set (or a multiset, which permits several elements to have
the same value).
• In recent decades, the rapid proliferation of applications dealing with
nonnumerical data has intensified the interest of researchers and
computing practitioners in string-handling algorithms.
• One particular problem, that of searching for a given word in a text has
attracted special attention from researchers. They call it string matching.
Contd..
• One of the oldest and most interesting areas in algorithmics is graph
algorithms.
• Informally, a graph can be thought of as a collection of points called
vertices, some of which are connected by line segments called edges.
• Graphs are an interesting subject to study, for both theoretical and
practical reasons.
• Graphs can be used for modeling a wide variety of applications,
including transportation, communication, social and economic
networks, project scheduling, and games.
 Contd..
• Basic graph algorithms include graph-traversal algorithms, shortest-path
algorithms and topological sorting for graphs with directed edges.
• Some graph problems are computationally very hard; the most well-
known
• Examples are the traveling salesman problem and the graph-coloring
problem.
• The Traveling salesman problem (TSP) is the problem of finding the
shortest tour through n cities that visits every city exactly once.
• The graph-coloring problem seeks to assign the smallest number of
colors to the vertices of a graph so that no two adjacent vertices are the
same color.
Contd..
• From a more abstract perspective, the traveling salesman problem
and the graph coloring problem are examples of combinatorial
problems.
• These are problems that ask, explicitly or implicitly, to find a
combinatorial object, such as a permutation, a combination, or a
subset that satisfies certain constraints.
• A desired combinatorial object may also be required to have some
additional property such as a maximum value or a minimum cost.
• Combinatorial problems are the most difficult problems in computing,
from both a theoretical and practical standpoint
 Contd..
• Geometric algorithms deal with geometric objects such as points,
lines, and polygons.
• Two classic problems of computational geometry: the closest-pair problem
and the convex-hull problem.
• The closest-pair problem : given n points in the plane, find the closest pair
among them.
• The convex-hull problem asks to find the smallest convex polygon that
would include all the points of a given set.
• Numerical problems are problems that involve mathematical objects of
continuous nature: solving equations and systems of equations, computing
definite integrals, evaluating functions, and so on.
Fundamentals of the Analysis of Algorithm Efficiency
• The Analysis Framework:
• In a general framework for analyzing the efficiency of algorithms.
there are two kinds of efficiency.
• Time efficiency, also called time complexity, indicates how fast an
algorithm in question runs.
• Space efficiency, also called space complexity, refers to the amount
of memory units required by the algorithm in addition to the space
needed for its input and output.
Contd..
• Measuring an Input’s Size
• Let’s start with the obvious observation that almost all algorithms run
longer on larger inputs.
• For example, it takes longer to sort larger arrays, multiply larger matrices,
and so on.
• Therefore, it is logical to investigate an algorithm’s efficiency as a function
of some parameter n indicating the algorithm’s input size.
• In most cases, selecting such a parameter is quite straight forward.
• For, and most other problems dealing with lists example, it will be the size
of the list for problems of sorting, searching, finding the list’s smallest
element.
Contd..
• Units for Measuring Running Time
• The next issue concerns units for measuring an algorithm’s running time.
• We can simply use some standard unit of time measurement, a second, or
millisecond, and so on, to measure the running time of a program
implementing the algorithm.
• There are obvious drawbacks to such an approach.
• Dependence on the speed of a particular computer, dependence on the
quality of a program implementing the algorithm and of the compiler used
in generating the machine code, and the difficulty of clocking the actual
running time of the program.
Contd..
• One possible approach is to count the number of times each of the
algorithm’s operations is executed.
• This approach is both excessively difficult and usually unnecessary.
• Identify the most important operation of the algorithm, called the
basic operation, the operation contributing the most to the total
running time, and compute the number of times the basic operation
is executed.
Contd..
• As a rule, the basic operation of an algorithm is usually the most
time-consuming operation in the algorithm’s innermost loop.
• For example, most sorting algorithms work by comparing elements
(keys) of a list being sorted with each other; for such algorithms, the
basic operation is a key comparison.
• Thus, the established framework for the analysis of an algorithm’s
time efficiency suggests measuring it by counting the number of
times the algorithm’s basic operation is executed on inputs of size n.
Orders of Growth
• Why this emphasis on the count’s order of growth for large input
sizes?
• A difference in running times on small inputs is not what really
distinguishes efficient algorithms from inefficient ones.
• When we have to compute, for example, the greatest common divisor
of two small numbers, it is not immediately clear how much more
efficient Euclid’s algorithm is compared to the other two algorithms.
Contd..
• It is only when we have to find the greatest common divisor of two
large numbers that the difference in algorithm efficiencies becomes
both clear and important.
• For large values of n, it is the function’s order of growth that counts,
• Few functions particularly important for analysis of algorithms.
Worst-Case, Best-Case, and Average-Case
Efficiencies
• It is reasonable to measure an algorithm’s efficiency as a function of a
parameter indicating the size of the algorithm’s input.
• But there are many algorithms for which running time depends not
only on an input size but also on the specifics of a particular input.
• Consider, as an example, sequential search.
• This is a straightforward algorithm that searches for a given item
(some search key K) in a list of n elements by checking successive
elements of the list until either a match with the search key is found
or the list is exhausted.
Contd..
 Example
• Clearly, the running time of this algorithm can be quite different for
the same list size n.
• In the worst case, when there are no matching elements or the first
matching element happens to be the last one on the list, the
algorithm makes the largest number of key comparisons among all
possible inputs of size
• n: Cworst(n) = n.
• The worst-case efficiency of an algorithm is its efficiency for the
worst-case input of size n, which is an input (or inputs) of size n for
which the algorithm runs the longest among all possible inputs of that
size.
Contd..
• The best-case efficiency of an algorithm is its efficiency for the best-
case input of size n, which is an input (or inputs) of size n for which
the algorithm runs the fastest among all possible inputs of that size.
• For example, the best-case inputs for sequential search are lists of
size n with their first element equal to a search key; accordingly,
Cbest(n) = 1 for this algorithm.
• Neither the worst-case analysis nor its best-case counterpart yields
the necessary information about an algorithm’s behavior on a
“typical” or “random” input. This is the information that the average-
case efficiency seeks to provide.
Asymptotic Notations and Basic Efficiency
Classes
• The efficiency analysis framework concentrates on the order of
growth of an algorithm’s basic operation count as the principal
indicator of the algorithm’s efficiency.
• To compare and rank such orders of growth, computer scientists use
three notations: O (big oh), Ω (big omega), and θ(big theta).
• In the following discussion, t (n) and g(n) be any nonnegative
functions defined on the set of natural numbers.
• In the context we are interested in, t (n) will be an algorithm’s running
time (usually indicated by its basic operation count C(n)), and g(n) will
be some simple function to compare the count with.
Asymptotic Notations and Basic Efficiency
Classes
Informal Introduction
• Informally, O(g(n)) is the set of all functions with a lower or
same order of growth as g(n).
• The following assertions are all true:
• n ∈ O(n2),
• 100n + 5 ∈ O(n2),
• ½ n(n − 1) ∈ O(n2).
Contd..
• n3 ≠ O(n2),
• 0.00001n3 ≠ O(n2),
• n4 + n + 1 ≠ O(n2).
Contd..
• The second notation, Ω(g(n)), stands for the set of all
functions with a higher or same order of growth as
g(n).
• For example,
• n3 ∈ Ω(n2),
• ½ n(n − 1) ∈ Ω(n2),
• 100n + 5 ≠ Ω(n2).
Contd..
• Finally, θ(g(n)) is the set of all functions that have the same
order of growth as g(n) .
• Thus, every quadratic function an2 + bn + c, with a > 0 is in
θ(n2),
• others, n2 + sin n and n2 + log n.
Definitions
• DEFINITION A function t(n) is said to be in O(g(n)), denoted t
(n) ∈ O(g(n)),
• if t (n) is bounded above by some constant multiple of g(n)
for all large n, i.e.,
• If there exist some positive constant c and some nonnegative
integer n0 such that
• t (n) ≤ cg(n) for all n ≥ n0.
Big-oh
Contd..
• Example, prove the assertions: 100n + 5 ∈ O(n2).
• 100n + 5 ≤ 100n + n (for all n ≥ 5) = 101n ≤ 101n2.
• Thus, as values of the constants c and n0 required by the definition,
we can take 101 and 5, respectively.
• The definition gives us a lot of freedom in choosing specific values for
constants c and n0.
• Example, we could reason that 100n + 5 ≤ 100n + 5n (for all n ≥ 1) =
105n to complete the proof with c = 105 and n0 = 1.
Contd..
• Ω-notation
• DEFINITION A function t(n) is said to be in
Ω (g(n)), denoted t(n) ∈ Ω(g(n)), if t (n) is bounded below
by some positive constant multiple of g(n) for all large n,
• i.e., if there exist some positive constant c and some
nonnegative integer n0 such that
• t (n) ≥ cg(n) for all n ≥ n0.
Big-omega
Contd..
• Example of the formal proof that
• n3 ∈ Ω(n2):
• n3 ≥ n2 for all n ≥ 0,
• i.e., we can select c = 1 and n0= 0.
Contd..
• θ-notation
• DEFINITION A function t(n) is said to be in θ (g(n)), denoted
t(n) ∈ θ(g(n)), if t(n) is bounded both above and below by
some positive constant multiples of g(n) for all large n, i.e.,
if there exist some positive constants c1 and c2 and some
nonnegative integer n0 such that
• c2g(n) ≤ t (n) ≤ c1g(n) for all n ≥ n0.
Big-theta
Contd..
• Example, prove that ½ n(n − 1) ∈ θ(n2).
• First, prove the right inequality (the upper bound):
• ½ n(n − 1) = ½ n2 − ½ n ≤ ½ n2 for all n ≥ 0.
• Second, we prove the left inequality (the lower bound):
• ½ n(n − 1) = ½ n2 − ½ n ≥ ½ n2 − ½ n ½ n (for all n ≥ 2) =
¼ n2.
• Hence, we can select c2 = ¼ , c1 = ½ , and n0 = 2.
Basic asymptotic efficiency classes
1 Constant

log n Logarithmic

n Linear

n log n n-log-n

n2 Quadratic

n3 Cubic

2n Exponential

n! Factorial
 Time efficiency of Non-recursive algorithms
General Plan for Analysis

1. Decide on parameter n indicating input size

2. Identify algorithm’s basic operation

3. Determine worst, average, and best cases for input of size n

4. Set up a sum for the number of times the basic operation is

executed

5. Simplify the sum using standard formulas and rules.

Useful summation formulas and rules
Example 1: Maximum element
Contd..
• The obvious measure of an input’s size here is the number of
elements in the array, i.e., n.
• The operations that are executed most often are in the algorithm’s for
loop.
• There are two operations in the loop’s body:
• The comparison A[i]> maxval and the assignment maxval←A[i].
• Since the comparison is executed on each repetition of the loop and
the assignment is not, we should consider the comparison to be the
algorithm’s basic operation.
Contd..
• Let C(n) be the number of times the comparison is executed. Find a
formula expressing it as a function of size n.
• The algorithm makes one comparison on each execution of the loop,
which is repeated for each value of the loop’s variable i within the bounds
1 and n − 1, inclusive.
• Therefore, we get the following sum for C(n):
Example 2: Element uniqueness problem
Contd..
• The natural measure of the input’s size here is n, the number of
elements in the array.
• Since the innermost loop contains a single operation (the comparison
of two elements), we should consider it as the algorithm’s basic
operation.
• The number of element comparisons depends not only on n but also
on whether there are equal elements in the array and, if there are,
which array positions they occupy.
• We investigate the worst case only.
Contd..
• By definition, the worst case input is an array for which the number of
element comparisons Cworst(n) is the largest among all arrays of size n.
• An inspection of the innermost loop reveals that there are two kinds
of worst-case inputs.
• arrays with no equal elements and arrays in which the last two
elements are the only pair of equal elements.
Contd..
Example 3: Matrix multiplication
• Given two n × n matrices A and B, find the time efficiency of the
definition-based algorithm for computing their product C = AB.
• By definition, C is an n × n matrix whose elements are computed as
the scalar (dot) products of the rows of matrix A and the columns of
matrix B.
Contd..
Contd..
Contd..
 Plan for Analysis of Recursive Algorithms
• Decide on a parameter indicating an input’s size.

• Identify the algorithm’s basic operation.

• Check whether the number of times the basic op. is executed may vary
on different inputs of the same size. (If so, the worst, average, and best
cases must be investigated separately.)

• Set up a recurrence relation with an appropriate initial condition

expressing the number of times the basic op. is executed.

• Solve the recurrence (or, at the very least, establish its solution’s order
of growth) by backward substitutions or another method.
Example 1: Recursive evaluation of n!
Definition: n ! = 1  2  … (n-1)  n for n ≥ 1 and 0! = 1

Recursive definition of n!: F(n) = F(n-1)  n for n ≥ 1

and
F(0) = 1
Solving the recurrence for M(n)

M(n) = M(n-1) + 1, n> 0

Example 2: The Tower of Hanoi Puzzle
 Solving recurrence for number of moves

M(n) = 2M(n-1) + 1, M(1) = 1

Tree of calls for the Tower of Hanoi Puzzle
BRUTE FORCE APPROACHES
• Brute force is a straightforward approach to solving a problem,
usually directly based on the problem statement and definitions of
the concepts involved.
• The “force” implied by the strategy’s definition is that of a computer
and not that of one’s intellect.
• “Just do it!” would be another way to describe the prescription of the
brute-force approach.
• The brute-force strategy is indeed the one that is easiest to apply.
SELECTION-SORT
• SELECTION-SORT(A)
1. for i ← 0 to n-1
2. smallest ← i
3. for j ← i + 1 to n
4. if A[ j ] < A[ smallest ]
5. smallest ← j
6. Exchange A[i] ↔ A[ smallest ]
Selection sort
0 1 2 3 4 5 6
23 19 15 1 60 34 17 A Input

1 15 17 19 23 34 60 A (Sorted) Output

N=7
No of Iterations are 7
 Selection sort
Iteration 1

23 23 23 23 23 23 23 1
small
19 19 19 19 19 19 19 19
small
15 15 15 15 15 15 15 15
small
1 1 1 1 1 1 1 23
small small small small
60 60 60 60 60 60 60 60

34 34 34 34 34 34 34 34

17 17 17 17 17 17 17 17
 Selection sort
Iteration 2

1 1 1 1 1 1 1

19 19 19 19 19 19 15
small
15 15 15 15 15 15 19
small small small small small
23 23 23 23 23 23 23

60 60 60 60 60 60 60

34 34 34 34 34 34 34

17 17 17 17 17 17 17
Selection sort
Iteration 3

1 1 1 1 1 1

15 15 15 15 15 15

19 19 19 19 19 17
small small small small
23 23 23 23 23 23

60 60 60 60 60 60

34 34 34 34 34 34

17 17 17 17 17 19
small
Selection sort
Iteration 4

1 1 1 1 1

15 15 15 15 15

17 17 17 17 17

23 23 23 23 19
small small small
60 60 60 60 60

34 34 34 34 34

19 19 19 19 23
small
Selection sort
Iteration 5

1 1 1 1

15 15 15 15

17 17 17 17

19 19 19 19

60 60 60 23
small
34 34 34 34
small
23 23 23 60
small
Selection sort
Iteration 6

1 1 1

15 15 15

17 17 17

19 19 19

23 23 23

34 34 34
small small
60 60 60
Selection sort
Iteration 7

1 1

15 15

17 17

19 19

23 23

34 34

60 60
small
Bubble Sort
Bubble sort
0 1 2 3 4 5 6
23 19 15 1 60 34 17 A Input

1 15 17 19 23 34 60 A (Sorted) Output

N=7
No of Iterations are 6
Bubble sort
Iteration 1

23 19 19 19 19 19 19

19 23 15 15 15 15 15

15 15 23 1 1 1 1

1 1 1 23 23 23 23

60 60 60 60 60 34 34

34 34 34 34 34 60 17

17 17 17 17 17 17 60
Bubble sort
Iteration 2

19 15 15 15 15 15

15 19 1 1 1 1

1 1 19 19 19 19

23 23 23 23 23 23

34 34 34 34 34 17

17 17 17 17 17 34

60 60 60 60 60 60
Bubble sort
Iteration 3

15 1 1 1 1

1 15 15 15 15

19 19 19 19 19

23 23 23 23 17

17 17 17 17 23

34 34 34 34 34

60 60 60 60 60
Bubble sort
Iteration 4

1 1 1 1

15 15 15 15

19 19 19 17

17 17 17 19

23 23 23 23

34 34 34 34

60 60 60 60
Bubble sort
Iteration 5

1 1 1

15 15 15

17 17 17

19 19 19

23 23 23

34 34 34

60 60 60
Bubble sort
Iteration 6

1 1

15 15

17 17

19 19

23 23

34 34

60 60
 for (i = 0 ; i < n - 1; i++)
main() {
{ for (j = 0 ; j < n - i - 1; j++)
int array[100], n, i, j, temp; {
if (array[j] > array[j+1])
printf("Enter number of {
temp = array[j];
elements\n");
array[j] = array[j+1];
scanf("%d", &n); array[j+1] = temp;
}
printf("Enter %d }
integers\n", n); }

printf("Sorted list in ascending order:");

for (i = 0; i < n; i++)
scanf("%d", &array[i]); for (i = 0; i < n; i++)
printf("%d\n", array[i]);
}
Sequential Search
Linear search (Sequential Search)
0 1 2 3 4 5 6
23 19 15 1 60 34 17 A Key Input

Message saying key is present in the list or not Output

If the key is present then prints the position

where the key is found in the list
If the key is not present then prints a message
key not found in the list

N=7
Maximum No of comparison is 7
 Linear Search
Case 1: Key =60

23 Key 23 23 23 23

19 19 Key 19 19 19

15 15 15 15 15
Key

1 1 1 1 Key 1

60 60 60 60 60
Key

34 34 34 34 34

17 17 17 17 17
Linear Search
Case 2: Key =23

23 Key

19

15 Best Case
1
Only one comparison
60

34

17
 Linear Search
worst Case
Case 3: Key =17
n comparison
23 Key 23 23 23 23 23 23

19 19 Key 19 19 19 19 19

15 15 15 15 15 15 15
Key

1 1 1 1 Key 1 1 1

60 60 60 60 60 60 60
Key

34 34 34 34 34 34 34
Key

17 17 17 17 17 17 17
 Linear Search
Key not found in the
Case 4: Key = 35
list
23 Key 23 23 23 23 23 23

19 19 Key 19 19 19 19 19

15 15 15 15 15 15 15
Key

1 1 1 1 Key 1 1 1

60 60 60 60 60 60 60
Key

34 34 34 34 34 34 34
Key

17 17 17 17 17 17 17
main()
{ for (i = 0; i < n; i++)
int array[100], search, i, n; {
if (array[i] == search) {
printf("Enter number of elements
in array\n"); printf("%d is present at location
scanf("%d", &n); %d.\n", search, i+1);
break;
printf("Enter %d integer(s)\n", n); }
}
for (i= 0; i < n; i++)
if (i == n)
scanf("%d", &array[i]);
printf("%d isn't present in the
array.\n", search);
printf("Enter a number to
search\n"); }
scanf("%d", &search);
Brute-Force String Matching
• Given a string of n characters called the text and a string of m characters
(m ≤ n) called the pattern, find a substring of the text that matches the
pattern.
• Precisely, we want to find i—the index of the leftmost character of the first
matching substring in the text—such that
• ti = p0, . . . , ti+j = pj, . . . , ti+m−1 = pm−1:
• t0 . . . ti . . . ti+j . . . ti+m−1 . . . tn−1 text T
• p0 . . . pj . . . pm−1 pattern P
• If matches other than the first one need to be found, a string-matching
algorithm can simply continue working until the entire text is exhausted.
Contd..

•
Contd..
Contd..
• Worst case: the algorithm may have to make all m comparisons
before shifting the pattern, and this can happen for each of the n − m
+ 1 tries.
• Thus, in the worst case, the algorithm makes m(n − m + 1) character
comparisons, which puts it in the O(nm) class.