Best of Luck for the exams..
DO NOT GET CAUGHT.
Rahul Sharma. 9854010108
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 1
1.1 CONCEPT OF ALGORITH.
A
A
common man’s belief is that a computer can do anything and everything that he imagines. It is
very difficult to make people realize that it is not really the computer but the man behind computer
who does everything.
In the modern internet world, man feels that just by entering what he wants to search into the computers
he can get information as desired by him. He believes that, this is done by computer. A common man
seldom understands that a man made procedure called search has done the entire job and the only support
provided by the computer is the execution speed and organized storage of information.
In the above instance, a designer of the information system should know what one frequently searches
for. He should make a structured organization of all those details to store in memory of the computer.
Based on the requirement, the right information is brought out. This is accomplished through a set of
instructions created by the designer of the information system to search the right information matching the
requirement of the user. This set of instructions is termed as program. It should be evident by now that it
is not the computer, which generates automatically the program but it is the designer of the information
system who has created this.
Thus, the program is the one, which through the medium of the computer executes to perform all the
activities as desired by a user. This implies that programming a computer is more important than the
computer itself while solving a problem using a computer and this part of programming has got to be done
by the man behind the computer. Even at this stage, one should not quickly jump to a conclusion that
coding is programming. Coding is perhaps the last stage in the process of programming. Programming
involves various activities form the stage of conceiving the problem up to the stage of creating a model to
solve the problem. The formal representation of this model as a sequence of instructions is called an
algorithm and coded algorithm in a specific computer language is called a program.
BSIT 41 Algorithms
Chapter 1 - Review
One can now experience that the focus is shifted from computer to computer programming and then
to creating an algorithm. This is algorithm design, heart of problem solving.
1.2 CHARACTERISTICS OF AN ALGORITH.
Let us try to present the scenario of a man brushing his own teeth(natural denture) as an algorithm as
follows:
Step 1. Take the brush
Step 2. Apply the paste
Step 3. Start brushing
Step 4. Rinse
Step 5. Wash
Step 6. Stop
If one goes through these 6 steps without being aware of the statement of the problem, he could
possibly feel that this is the algorithm for cleaning a toilet. This is because of several ambiguities while
comprehending every step. Step-1 may imply tooth brush, paint brush, toilet brush, etc. Such an ambiguity
arises from the instruction of the above algorithmic step. Thus every step has to be made unambiguous.
An unambiguous step is called definite instruction. Even if step 2 is rewritten as ‘apply the tooth paste’, to
eliminate ambiguities, yet the conflicts such as, where to apply the tooth paste and where is the source of
the tooth paste, need to be resolved. Hence, the act of applying the toothpaste is not mentioned. Although
unambiguous, such unrealizable steps can’t be included as algorithmic instruction as they are not effective.
The definiteness and effectiveness of an instruction implies the successful termination of that instruction.
However the above two may not be sufficient to guarantee the termination of the algorithm. Therefore,
while designing an algorithm care should be taken to provide a proper termination for algorithm.
Thus, every algorithm should have the following five characteristic feature
1) Input
2) Output
3) Definiteness
4) Effectiveness
5) Termination
Therefore, an algorithm can be defined as a sequence of definite and effective instructions, which
terminates with the production of correct output from the given input.
BSIT 41 Algorithms
In other words, viewed little more formally, an algorithm is a step by step formalization of a mapping
function to map input set onto an output set.
The problem of writing down the correct algorithm for the above problem of brushing the teeth is left
to the reader.
1.3 HOW TO DEVISE THE ALGORITHM.
The process of devising an algorithm is both an art and a science. This is one part that cannot be
automated fully. Given a problem description, one have to think of converting this into a series of steps,
which, when executed in a given sequence solve the problem. To do this, one has to be familiar with the
problem domain and also the computer domains. This aspect may never be taught fully and most often,
given a problem description, how a person proceeds to covert it into an algorithm becomes a matter of his
“style” – no firm rules become applicable here.
For the purpose of clarity in understanding, let us consider the following example.
Problem: Finding the largest value among n>=1 numbers.
Input: the value of n and n numbers
Output: the largest value
Steps :
1. Let the value of the first be the largest value denoted by BIG
2. Let R denote the number of remaining numbers. R=n-1
3. If R != 0 then it is implied that the list is still not exhausted. Therefore look the next number
called NEW.
4. Now R becomes R-1
5. If NEW is greater than BIG then replace BIG by the value of NEW
6. Repeat steps 3 to 5 until R becomes zero.
7. Print BIG
8. Stop
End of algorithm
Chapter 1 - Review
1.4 HOW TO VALIDATE THE ALGORITHM.
Once an algorithm has been devised, it becomes necessary to show that it works. i.e it computes the
correct answer to all possible, legal inputs. One simple way is to code it into a program. However,
converting the algorithms into programs is a time consuming process. Hence, it is essential to be reasonably
sure about the effectiveness of the algorithm before it is coded. This process, at the algorithm level, is
called “validation”. Several mathematical and other empirical methods of validation are available. Providing
the validation of an algorithm is a fairly complex process and most often a complete theoretical validation,
though desirable, may not be provided. Alternately, algorithm segments, which have been proved else
where may be used and the overall working algorithm may be empirically validated for several test cases.
Such methods, although suffice in most cases, may often lead to the presence of unidentified bugs or side
effects later on.
1.5 HOW TO TEST THE ALGORITHM.
If there are more then one possible way of solving a problem, then one may think of more than one
algorithm for the same problem. Hence, it is necessary to know in what domains these algorithms are
applicable. Data domain is an important aspect to be known in the field of algorithms. Once we have more
than one algorithm for a given problem, how do we choose the best among them? The solution is to devise
some data sets and determine a performance profile for each of the algorithms. A best case data set can
be obtained by having all distinct data in the set.
The ultimate test of an algorithm is that the programs based on the algorithm should run satisfactorily.
Testing a program really involves two phases a) debugging and b) profiling. Debugging is the process of
executing programs with sample datasets to determine if the results obtained are satisfactory. When
unsatisfactory results are generated, suitable changes are made in the program to get the desired results.
On the other hand, profiling or performance measurement is the process of executing a correct program
on different data sets to measure the time and space that it takes to compute the results.
However, it is pointed out that “debugging can only indicate the presence of errors but not the absence
of it”. i.e., a program that yields unsatisfactory results with a sample data set is definitely faulty, but just
because a program is producing the desirable results with one/more data sets cannot prove that the
program is ideal. Even after it produces satisfactory results with say 10000 data sets, it’s results may be
faulty with the 10001th set. In order to actually prove that a program is perfect, a process called “proving”
is taken up. Here, the program is analytically proved to correct and in such cases, it is bound to yield
perfect results for all possible sets of data.
1.6 ALGORITHMIC NOTATION.
In this section we present the pseudo code that we use through out the book to describe algorithms.
BSIT 41 Algorithms
The pseudo code used resembles PASCAL and C language control structures. Hence, it is expected that
the reader be aware of PASCAL/C. Even otherwise at least now it is required that the reader should
know preferably C to practically test the algorithm in this course work.
However, for the sake of completion we present the commonly employed control constructs present in
the algorithms.
1. A conditional statement has the following form
If < condition> then
Block 1
Else
Block 2
If end.
This pseudo code executes block1 if the condition is true otherwise block2 is executed.
2. The two types of loop structures are counter based and conditional based and they are as follows
For variable = value1 to value2 do
Block
For end
Here the block is executed for all the values of the variable from value 1 to value 2.
There are two types of conditional looping, while type and repeat type.
While (condition) do
Block
While end.
Here block gets executed as long as the condition is true.
Repeat
Block
Until<condition>
Here block is executed as long as condition is false. It may be observed that the block is executed at
least once in repeat type.