Algorithms :
Introduction :
There are many general classes of problems that arise in discrete mathematics.
For instance: given a sequence of integers, find the largest one; given a set, list all its
subsets; given a set of integers, put them in increasing order; given a network, find the
shortest path between two vertices. When presented with such a problem, the first thing to
do is to construct a model that translates the problem into a mathematical context. Discrete
structures used in such models include sets, sequences, and functions—structures discussed
in Chapter 2—as well as such other structures as permutations, relations, graphs, trees,
networks, and finite state machines— concepts that will be discussed in later chapters.
Setting up the appropriate mathematical model is only part of the solution. To complete the
solution, a method is needed that will solve the general problem using the model. Ideally,
what is required is a procedure that follows a sequence of steps that leads to the desired
answer. Such a sequence of steps is called an algorithm.
Definition :
An algorithm is a finite sequence of precise instructions for performing a
computation or for solving a problem.
EXAMPLE 1: Describe an algorithm for finding the maximum (largest) value in a finite sequence of integers.
Solution of Example 1: We perform the following steps.
1. Set the temporary maximum equal to the first integer in the sequence. (The temporary maximum will be
the largest integer examined at any stage of the procedure.)
2. Compare the next integer in the sequence to the temporary maximum, and if it is larger than the
temporary maximum, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers in the sequence.
4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest
integer in the sequence.
ALGORITHM 1 Finding the Maximum Element in a Finite
Sequence.
procedure max(a1, a2,… , an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max{max is the largest element}
PROPERTIES OF ALGORITHMS There are several properties that algorithms generally
share. They are useful to keep in mind when algorithms are described. These properties are:
▶ Input. An algorithm has input values from a specified set.
▶ Output. From each set of input values an algorithm produces output values from a specified set. The output values
are the solution to the problem.
▶ Definiteness. The steps of an algorithm must be defined precisely.
▶ Correctness. An algorithm should produce the correct output values for each set of input
values.
▶ Finiteness. An algorithm should produce the desired output after a finite (but perhaps
large) number of steps for any input in the set.
▶ Effectiveness. It must be possible to perform each step of an algorithm exactly and in a
finite amount of tim
▶ Generality. The procedure should be applicable for all problems of the desired form, not just for a particular set of
input values.
• Searching Algorithms
The problem of locating an element in an ordered list occurs in many contexts. For instance,
a program that checks the spelling of words searches for them in a dictionary, which is just an
ordered list of words. Problems of this kind are called searching problems.
1. THE LINEAR SEARCH
The first algorithm that we will present is called the linear search, Links or sequential search,
algorithm. The linear search algorithm begins by comparing x and a1. When x = a1, the solution
is the location of a1, namely, 1. When x ≠ a1, compare x with a2. If x = a2, the solution is the
location of a2, namely, 2. When x ≠ a2, compare x with a3. Continue this process, comparing x
successively with each term of the list until a match is found, where the solution is the location
of that term, unless no match occurs. If the entire list has been searched without locating x, the
solution is 0.
ALGORITHM 2 : The Linear Search Algorithm.
procedure linear search(x: integer, a1, a2,… , an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location{location is the subscript of the term that equals x,
or is 0 if x is not found}
2. THE BINARY SEARCH :
This algorithm can be used when the list has terms occurring in order of increasing size
(for instance: if the terms are numbers, they are listed from smallest to largest; if they are words,
they are listed Links in lexicographic, or alphabetic, order). This second searching algorithm is
called the binary search algorithm.
ALGORITHM 3 The Binary Search Algorithm
procedure binary search (x: integer, a1, a2,… , an: increasing integers)
i := 1{i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while i < j
m := ⌊(i + j)∕2⌋
if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
return location{location is the subscript i of the term ai equal to x, or
0 if x is not found}
• Sorting :
Sorting is putting these elements into a list in which the elements are in increasing order. For
instance, sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the list d, h, c, a, f
(using alphabetical order) produces the list a, c, d, f, h.
1. THE BUBBLE SORT:
The bubble sort is one of the simplest sorting algorithms, but not one of the most efficient.
It puts a list into increasing order by successively comparing adjacent Links elements,
interchanging them if they are in the wrong order. To carry out the bubble sort, we perform the
basic operation, that is, interchanging a larger element with a smaller one following it, starting at
the beginning of the list, for a full pass. We iterate this procedure until the sort is complete.
ALGORITHM 4 The Bubble Sort.
procedure bubblesort(a1,… , an : real numbers with n ≥ 2)
for i := 1 to n − 1
for j := 1 to n − i
if aj > aj+1 then interchange aj and a j+1
{a1,… , an is in increasing order}
2. THE INSERTION SORT :
The insertion sort is a simple sorting algorithm, but it is usually not the most efficient. To
sort a list with n elements, the insertion sort begins with the second element. The insertion sort
compares this second element with the first element and inserts it Links before the first element
if it does not exceed the first element and after the first element if it exceeds the first element. At
this point, the first two elements are in the correct order. The third element is then compared with
the first element, and if it is larger than the first element, it is compared with the second element;
it is inserted into the correct position among the first three elements.
ALGORITHM 5 The Insertion Sort.
procedure insertion sort(a1, a2,… , an: real numbers with n ≥ 2)
for j := 2 to n
i := 1
while aj > ai
i := i + 1
m := aj
for k := 0 to j − i − 1
aj−k := a j−k−1
ai := m
{a1,… , an is in increasing order}
• String Matching :
Although searching and sorting are the most commonly encountered problems in computer
science, many other problems arise frequently. One of these problems asks where a particular
string of characters P, called the pattern, occurs, if it does, within another string T, called the text.
For instance, we can ask whether the pattern 101 can be found within the string 11001011. By
inspection we can see that the pattern 101 occurs within the text 11001011 at a shift of four
characters, because 101 is the string formed by the fifth, sixth, and seventh characters of the text.
On the other hand, the pattern 111 does not occur within the text 110110001101.
Finding where a pattern occurs in a text string is called string matching. String matching plays
an essential role in a wide variety of applications, including text editing, spam filters, systems
that look for attacks in a computer network, search engines, plagiarism detection, bioinformatics,
and many other important applications.
ALGORITHM 6 Naive String Matcher.
procedure string match (n, m: positive integers, m ≤ n, t1, t2,… , tn, p1, p2,… , pm: characters)
for s := 0 to n − m
j := 1
while ( j ≤ m and ts+j = pj )
j := j + 1
if j > m then print “s is a valid shift”
• Greedy Algorithms :
A Greedy Algorithm is an algorithm that constructs a solution by repeatedly selecting the
locally optimal choice at each stage, with the hope that these choices lead to an optimal overall
solution.
1. Cashier’s algorithm :
The Cashier Algorithm is a greedy algorithm used to return change using the minimum
number of coins or notes.
At each step, the cashier gives the largest possible denomination that does not exceed the
remaining amount.
ALGORITHM 7 Cashier’s Algorithm.
procedure change(c1, c2,… , cr: values of denominations of coins, where
c1 > c2 > ⋯ > cr; n: a positive integer)
for i := 1 to r
di := 0 {di counts the coins of denomination ci used}
while n ≥ ci
di := di + 1 {add a coin of denomination ci}
n := n − ci
{di is the number of coins of denomination ci in the change for i = 1, 2, … , r}
LEMMA 1: If n is a positive integer, then n cents in change using quarters, dimes,
nickels, and pennies using the fewest coins possible has at most two dimes, at most
one nickel, at most four pennies, and cannot have two dimes and a nickel. The
amount of change in dimes, nickels, and pennies cannot exceed 24 cents.
ALGORITHM 8 Greedy Algorithm for Scheduling Talks.
procedure schedule(s1 ≤ s2 ≤ ⋯ ≤ sn: start times of talks,
e1 ≤ e2 ≤ ⋯ ≤ en: ending times of talks)
sort talks by finish time and reorder so that e1 ≤ e2 ≤ ⋯ ≤ en
S := ∅
for j := 1 to n
if talk j is compatible with S then
S := S ∪ {talk j}
return S{S is the set of talks scheduled}
❖ The Halting Problem :
We will now describe a proof of one of the most famous theorems in
computer science. We will show that there is a problem that cannot be solved using
any procedure. That is, we will Links show there are unsolvable problems. The
problem we will study is the halting problem. It asks whether there is a procedure
that does this: It takes as input a computer program and input to the program and
determines whether the program will eventually stop when run with this input. It
would be convenient to have such a procedure, if it existed. Certainly being able to
test whether a program entered into an infinite loop would be helpful when writing
and debugging programs. However, in 1936 Alan Turing showed that no such
procedure exists.
The Growth of Functions :
• Big-O Notation :
Let f and g be functions from the set of integers or the set of real numbers to
the set of real numbers. We say that f(x) is O(g(x)) if there are constants C and k
such that
|f(x)| ≤ C|g(x)|
whenever x > k. [This is read as “f(x) is big-oh of g(x).”]
❖ THE HISTORY OF BIG-O NOTATION :
Big-O notation has been used in mathematics for more than a century. In
computer science it is widely used in the analysis of algorithms, as will be seen in
Section 3.3. The German mathematician Paul Bachmann first introduced big-O
notation in 1892 in an important book on number theory. The big-O symbol is
sometimes called a Landau symbol after the German mathematician Edmund
Landau, who used this notation throughout his work. The use of big-O notation in
computer science was popularized by Donald Knuth, who also introduced the big-
Ω and big-Θ notations defined later in this section.
❖ WORKING WITH THE DEFINITION OF BIG-O NOTATION:
A useful approach for finding a pair of witnesses is to first select a value
of k for which the size of |f(x)| can be readily estimated when x > k and to see
whether we can use this estimate to find a value of C for which |f(x)| ≤ C|g(x)| for x
> k.
Complexity of Algorithms
The computational complexity of the algorithm. An analysis of the time
required to solve a problem of a particular size involves the time complexity of the
algorithm. An analysis of the computer memory required involves the space
complexity of the algorithm.
Time Complexity:
The time complexity of an algorithm can be expressed in terms of the number
of operations used by the algorithm when the input has a particular size. The
operations used to measure time complexity can be the comparison of integers, the
addition of integers, the multiplication of integers, the division of integers, or any
other basic operation. Time complexity is described in terms of the number of
operations required instead of actual computer time because of the difference in
time needed for different computers to perform basic operations. Moreover, it is
quite complicated to break all operations down to the basic bit operations that a
computer uses. Furthermore, the fastest computers in existence can perform basic
bit operations (for instance, adding, multiplying, comparing, or exchanging two
bits) in 10−11 second (10 picoseconds), but personal computers may require 10−8
second (10 nanoseconds), which is 1000 times as long, to do the same operations.
WORST-CASE COMPLEXITY:
The type of complexity analysis done in Example 2 is a worst-case analysis. By the worst-
case performance of an algorithm, we mean the largest number of operations needed to solve the
given problem using this algorithm on input of specified size. Worst-case analysis tells us how
many operations an algorithm requires to guarantee that it will produce a solution.
AVERAGE-CASE COMPLEXITY:
Another important type of complexity analysis, besides worst-case analysis, is called
average-case analysis. The average number of operations used to solve the problem over all
possible inputs of a given size is found in this type of analysis. Average-case time complexity
analysis is usually much more complicated than worst-case analysis. However, the average-case
analysis for the linear search algorithm can be done without difficulty.
Complexity of Matrix Multiplication:
The definition of the product of two matrices can be expressed as an algorithm for
computing the product of two matrices. Suppose that C = [cij] is the m × n matrix that is the
product of the m × k matrix A = [aij] and the k × n matrix = [bij]. The algorithm based on the
definition of the matrix product is expressed in pseudocode in Algorithm 1.
ALGORITHM 1 Matrix Multiplication.
procedure matrix multiplication(A, B: matrices)
for i := 1 to m
for j := 1 to n
cij := 0
for q := 1 to k
cij := cij + aiqbqj
return C {C = [cij] is the product of A and B}
ALGORITHM 2 The Boolean Product of Zero–One Matrices.
procedure Boolean product of Zero–One Matrices (A, B: zero–one matrices)
for i := 1 to m
for j := 1 to n
cij := 0
for q := 1 to k
cij := cij ∨ (aiq ∧ bqj)
return C {C = [cij] is the Boolean product of A and B}
MATRIX-CHAIN MULTIPLICATION:
There is another important problem involving the complexity of the
multiplication of matrices. How should the matrix-chain A1A2 ⋯ An be computed
using the fewest multiplications of integers, where A1, A2, … , An are m1 × m2, m2 ×
Links m3, … , mn × mn+1 matrices, respectively, and each has integers as entries?
the order of the multiplication used does not change the product.) Note that
m1m2m3 multiplications of integers are performed to multiply an m1 × m2 matrix
and an m2 × m3 matrix using Algorithm 1.
Algorithmic Paradigms
We also introduced the concept of a greedy algorithm, giving examples of several problems
that can be solved by greedy algorithms. Greedy algorithms provide an example of an
algorithmic paradigm, that is, a general approach based on a particular concept that can be used
to construct algorithms for solving a variety of problems.
BRUTE-FORCE ALGORITHMS
Brute force is an important, and basic, algorithmic paradigm. In a brute-force algorithm, a
problem is solved in the most straightforward manner based on the statement of the problem and
the definitions of terms. Brute-force algorithms are designed to solve problems without regard to
the computing resources required.
ALGORITHM 3 Brute-Force Algorithm for Closest Pair of Points.
procedure closest-pair((x1, y1),(x2, y2),… ,(xn, yn): pairs of real numbers)
min= ∞
for i := 2 to n
for j := 1 to i − 1
if (xj − xi)2 + (yj − yi)2 < min then
min := (xj − xi)2 + (yj − yi)2
closest pair := ((xi, yi),(xj, yj))
return closest pair
Understanding the Complexity of Algorithms
TABLE 1 Commonly Used Terminology for the
Complexity of Algorithms Complexity Terminology
Θ(1) Constant complexity
Θ(log n) Logarithmic complexity
Θ(n) Linear complexity
Θ(n log n) Linearithmic complexity
Θ(nb) Polynomial complexity
Θ(bn), where b > 1 Exponential complexity
Θ(n!) Factorial complexity
TRACTABILITY
A problem that is solvable using an algorithm with polynomial (or better) worst-case
complexity is called tractable, because the expectation is that the algorithm will produce the
solution to the problem for reasonably sized input in a relatively short time.
Jamahmad(0114)
Made from kenneth rosen edition 8th