Analysis and Design of Algorithms- A Beginner's Hope

A Beginner's Hope

Shefali Singhal

• Publisher: BPB Publications
• Year: 2018
• ISBN:
  9789386551894
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer Key Features

• This book is especially designed for beginners and explains all aspects of algorithm and its analysis in a simple and systematic manner.
• Algorithms and their working are explained in detail with the help of several illustrative examples.
• Important features like greedy algorithm, dynamic algorithm, string matching algorithm, branch and bound algorithm, NP hard and NP complete problems are suitably highlighted.
• Solved and frequently asked questions in the various competitive examinations, sample papers of the past examinations are provided which will serve as a useful reference source.

Description
The book has been written in such a way that the concepts and working of algorithms are explained in detail, with adequate examples. To make clarity on the topic, diagrams, calculation of complexity, algorithms are given extensively throughout. Many examples are provided which are helpful in understanding the algorithms by various strategies. This content is user-focused and has been highly updated including algorithms and their real-world examples. What You Will Learn

• Algorithm & Algorithmic Strategy, Complexity of Algorithms
• Divide-and-Conquer, Greedy, Backtracking, String-Matching Algorithm
• Dynamic Programming, P and NP Problems
• Graph Theory, Complexity of Algorithms
• 
  Who This Book is For
  The book would serve as an extremely useful text for BCA, MCA, M. Sc. (Computer Science), PGDCA, BE (Information Technology) and B. Tech. and M. Tech. students. Table of Contents
  1. Algorithm & Algorithmic Strategy
  2. Complexity of Algorithms
  3. Divide-and-Conquer Algorithms
  4. Greedy Algorithm
  5. Dynamic Programming
  6. Graph Theory
  7. Backtracking Algorithms
  8. Complexity of Algorithms
  9. String-Matching Algorithms
  10. P and NP Problems About the Author
  Shefali Singhal is working as an Assistant professor in Computer science and Engineering department, Manav Rachna International University. She has completed her MTech. form YMCA University in Computer Engineering. Her research interest includes Programming Languages, Computer Network, Data mining, and Theory of computation. Neha Garg is working as an Assistant professor in in Computer science and Engineering department, Manav Rachna International University. She has completed her MTech. Form Banasthali University, Rajasthan in Information Technology. Her research interest includes Programming Languages, Data Structure, Operating System, Database Management Systems.
  

CHAPTER-1

Algorithm & Algorithmic Strategy

In this chapter student will understand:

What is an Algorithm? From where this term is originated? Why should one study algorithm? What is the role of an algorithm in other fields? What will happen if algorithms vanish from the picture?

1.1 Algorithm

Given a particular problem, how one can solve it on the computer?

The way you solve any problem in systematic manner by using some input, by following proper sequence of steps and finally getting the desired output. Hence we may say that solving a problem is just like following a recipe to cook a dish. As we can see that a recipe is a box of steps and following those steps in proper sequence will always give the output.

Once we design any algorithm, we need to know how well it works for a given input. Is there any algorithm better than this? In order to answer much such type of queries, algorithm analysis came into the picture.

1.2 History

The term algorithm was named after the name of a Persian author, Abu Ja'far Muhammad IbnMusa'al Khowarizmi (c. 825 A. D.), who has given the definition of the algorithm as:

1. An algorithm is a set of rules for carrying out computation either by hand or by some machine.
2. It is a set of procedures that use some input and give desired output. He said that an algorithm must satisfy the following properties:
   • Input: finite no of input must be externally supplied.
   • Output: At least one output must be produced.
   • Definiteness: Each instruction must be clear with respect to upper bound.
   • Effectiveness: Each instruction must have a meaningful result after execution.
   • Finiteness: If each instruction is executed in a proper sequence then the process must successfully terminate in finite time without going into any infinite loop.

1.3 Scope of Algorithms in different fields

Practically every task that you perform using a computer system depends indirectly on an algorithm that someone has worked previously very hard to make sense of it. Indeed, even the simplest application on a cutting edge computer would not be conceivable to be utilized without calculations. Algorithms are being utilized to oversee memory and load information from the hard drive.

Obviously, there are circumstances when you'll come across a problem that has not been previously studied. In these cases, you have to come up with a new algorithm or apply an old algorithm in a new way. More you think about algorithms in this case better is the odds of discovering rationale to take care of the issue. In many cases, a new problem can be reduced to an old problem without excessive amount of effort, but you need to have a basic fundamental understanding of the previous problem in order to solve the current one.

As an example of this, let's consider what a switch does on the Internet. A switch has N cables plugged into it and gets bundles of information rolling in from the links. The switch has to first analyze the packets and then send them back to the correct cables. A switch, similar to a PC, is controlled by a clock with discrete strides - the packets are sending out at discrete intervals, rather than continuously. In a fast switch, we want to send out as many packets as possible during each interval, so they don't stack up and get dropped. The objective of the algorithm we need to create is to convey how many packets as could be expected under the circumstances during each interval, and furthermore also to send them out with the goal that the ones that arrived earlier get sent out earlier. In this case, it turns out that an algorithm for a problem that is known as “stable matching” is specifically material to our concern, though at first glance this relationship appears to be far-fetched. Only through pre-existing algorithmic knowledge and understanding such a relationship can be found.

Algorithms have a vital role in different areas, few of which we have discussed below

• Data Structures is the real area for existing algorithms and also for generation of new algorithms.
• Cryptography is another study area in computer science where all the techniques like RSA, AES, DES, etc. are completely based on the algorithm.
• Manufacturing units fully utilize automation. There an algorithms who plays an important role.
• In biological field, things like a number of genes in DNA, ECG coding algorithm, etc.
• In the electrical field like embedded programming for IC's, magnetic resonance imaging (MRI), etc.

1.4 Classification Of Algorithms

The classification of an algorithm is based on repetitive execution of the steps and control transfer from one statement to another.

By repetitive steps, an algorithm can be further classified into two types.

1. Direct Algorithm: In this algorithm, one should know the number of iterations in advance.
   For example, to display numbers from 1 to 10, the loop variable should be initialized from 1 to 10. The statement would be as follows
   for (j=1;j<=10;j++)
   In the above statement, it is observed that the loop will iterate ten times.
2. Indirect Algorithm: In this type of algorithm, repetitively steps are executed. It is totally unknown that how many repetitions are to be made.
   For example, the repetitive steps are as follows.
   1. To find the first five Armstrong numbers from 1 to n, where n is the fifth Armstrong number.
   2. To find the first three palindrome numbers.

Algorithm on the basis of selection structure

• Recursive Algorithm: This type of algorithm solves the base cases directly, recurs with a simpler sub problem and does some extra work to convert the solution to the simpler sub problem that produces a solution to the given problem.
  Example:
  • To count the number of elements in a list.
  • Tower of Hanoi problem

Note: A recursive method is a method that calls itself either directly or indirectly. Each repetition of the process is called iteration and the result of iteration is used as the starting point for the next iteration.

Based on the control transfer, there are three categories of algorithms which are discussed below:

• Deterministic: A Deterministic algorithm is either follows a ‘yes’ path or ‘no’ path based on the condition. In these algorithms, when control reaches for decision logic, two paths ‘yes and ‘no’ are shown. Now the program control follows one of the routes depending upon the given condition.
  Example:
  • Testing whether a number is even or odd.
  • Testing whether a number is positive or negative.
• Non-Deterministic: In this type of algorithm to reach to the solution, we have one of the multiple paths.
  Example:
  • To find a day of a week.
  • To find a path between two stations like, path from Delhi to Chennai.
• Random algorithm: Random algorithms are algorithms that make some spontaneous decision during their execution. After executing few instructions the control of the program transfers to another, randomly.
  Example:
  • A random search
  • Random Key generator in cryptography.

1.5 Pseudo Code

In computer theory, we distinguish between algorithm and computer program. Algorithms satisfy the property of finiteness while the program may run in an infinite loop due to waiting for some resource to be allocated, couldn't find terminating condition, etc.

Pseudo code is the informal and compact representation of computer programming algorithm that uses conventions of the structured programming languages like C, C++, etc. It is only intended for human reading rather than machine reading, that's why we write pseudo code in the natural language. There is one more method to represent algorithm in the symbolic representation called flowchart, but we can draw them only for simpler and smaller algorithms.

Pseudo-code typically hides details that are not much essential for understanding the algorithm or may create complexity, such as functions (or subroutines), variable declaration, semicolons, special words and so on. Any version of pseudo-code is acceptable as long as its instructions are unambiguous. Pse...