DESCRETE STRUCTURE

CHAPTER # 3 TOPIC : ALGORITHIMS

EXERCISE #
3.1

INTRODUCTION TO ALGOTITHIMS:

There are many general classes of problems that arise in discrete mathematics. 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.
The term algorithm is a corruption of the name al-Khwarizmi, a mathematician of the ninth century,
whose book on Hindu numerals is the basis of modern decimal notation. Originally, the word algorism
was used for the rules for performing arithmetic using decimal notation. Algorism evolved into the
word algorithm by the eighteenth century. With the growing interest in computing machines, the
concept of an algorithm was given a more general meaning, to include all definite procedures for
solving problems, not just the procedures for performing arithmetic.

DEFINITION OF ALGORITHIM:

An algorithm is a finite sequence of precise instructions for performing a computation or for

solving a problem.

PROPERTIES OF ALGORITHIM:
 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 time.
• Generality: The procedure should be applicable for all problems of the desired form, not
just for a particular set of input values.

SEARCHING ALGORITHIMS:

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.
The general searching problem can be described as follows: Locate an element x in a list of distinct
elements a1, a2,...,an, or determine that it is not in the list. The solution to this search problem is the
location of the term in the list that equals x (that is, i is the solution if x = ai) and is 0 if x is not in the list.

THERE ARE TWO TYPES OF SEARCH ALGOTITHIMS:

1. THE LINEAR SEARCH 2. THE BINARY SEARCH

THE LINEAR SEARCH:

The first algorithm that we will present is called the linear search, 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. The pseudocode for the linear search algorithm
is displayed as Algorithm 2.
 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.

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 in
lexicographic, or alphabetic, order). This second searching algorithm is called the binary search algorithm.
. It proceeds by comparing the element to be located to the middle term of the list. The list is then split
into two smaller sub lists of the same size, or where one of these smaller lists has one fewer term than
the other.

The search continues by restricting the search to the appropriate sub list based on the comparison of the
element to be located and the middle term. In Section 3.3, it will be shown that the binary search
algorithm is much more efficient than the linear search algorithm. Example 3 demonstrates how a binary
search works.

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 :

Ordering the elements of a list is a problem that occurs in many contexts. For example, to produce a
telephone directory it is necessary to alphabetize the names of subscribers. Similarly, producing a
directory of songs available for downloading requires that their titles be put in alphabetic order. Putting
addresses in order in an e-mail mailing list can determine whether there are duplicated addresses.
Creating a useful dictionary requires that words be put in alphabetical order. Similarly, generating a parts
list requires that we order them according to increasing part number. An amazingly large percentage of
computing resources is devoted to sorting one thing or another. Hence, much effort has been devoted
to the development of sorting algorithms. A surprisingly large number of sorting algorithms have been
devised using distinct strategies, with new ones introduced regularly. In his fundamental work, The Art
of Computer Programming, Donald Knuth devotes close to 400 pages to sorting, covering around 15
different sorting algorithms in depth! More than 100 sorting algorithms have been devised, and it is
surprising how often new sorting algorithms are developed. Among the newest sorting algorithms that
have caught on is the library sort, also known as the gapped insertion sort, invented as recently as 2006.

There are many reasons why sorting algorithms interest computer scientists and mathematicians.
Among these reasons are that some algorithms are easier to implement, some algorithms are more
efficient (either in general, or when given input with certain characteristics, such as lists slightly out of
order), some algorithms take advantage of particular computer architectures, and some algorithms are
particularly clever. In this section we will introduce two sorting algorithms, the bubble sort and the
insertion sort. Two other sorting algorithms, the selection sort and the binary insertion sort, are
introduced in the exercises, and the shaker sort is introduced in the Supplementary Exercises.

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 elements, interchanging them if they
are in the wrong order.
 ALGORITHM 4 The Bubble Sort:
Procedure bubble sort (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 aj+1
{a1,...,an is in increasing order}

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 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 := aj−k−1
ai := m
{a1,...,an is in increasing order}