Unit-1
Algorithm
The Word algorithm comes from the name of a Persian author, Abu Ja’far Mohammed ibn Musa
al khowarizmi (c.825 AD), who wrote a textbook on mathematics. This word has taken on a
special significance in computer science, where “algorithm” has come to refer to a method that
can be used by a computer for the solution of a problem.
An algorithm is used to provide a solution to a particular problem in a form of well-defined
steps. Whenever we use a computer to solve a particular problem, the steps which lead to the
solution should be properly communicated to the computer. While executing an algorithm on a
computer, several operations such as additions and subtractions are combined to perform more
complex mathematical operations. Algorithms can be expressed using natural language,
flowcharts, etc.
Definition:
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In
addition, all algorithms must satisfy the following criteria:-
1. Input: - Zero or more inputs are externally supplied to the algorithm.
2. Output: - At least one output is produced by an algorithm.
3. Definiteness: - Each step in the algorithm must be clear and unambiguous.
4. Finiteness: - In an algorithm, it will be terminated after a finite number of steps for all
different cases.
5. Effectiveness: - Every instruction must be very basic so that the purpose of those
instructions must be very clear to us.
To achieve definiteness we need to write algorithm in a programming language, such languages
are designed so that each legitimate sentence has a unique meaning. A program is the expression
of an algorithm in a programming language.
Algorithms that are definite and effective are also called computational procedures. One
important example of computational procedures is the operating system of a digital system. This
1
,procedure is designed to control the execution of jobs, in such a way that when no jobs are
available, it does not terminate but continues in a waiting state until a new job is entered.
Advantages of Algorithm:
1. Easy to understand: - Since it is a stepwise representation of a solution to a given
problem, it is easy to understand.
2. Language independent: - It is not dependent on any programming language, so it can
easily be understood by anyone.
3. Debug/Error finding: - Every step is independent/ in a flow so it will be easy to spot and
fix the error.
4. Sub-problems: - It is written in a flow so now the programmer can divide the tasks which
makes them easier to code.
Disadvantages of Algorithms:
1. Creating efficient algorithms is time consuming and requires good logical skills.
2. Nasty to show branching and looping in algorithms.
Example:
Algorithm of adding two numbers
Step1: Start the program
Step2: Read the values of a & b
Step3: Computer the sum of entered numbers ‘a’, ‘b’, c=a+b
Step4: Print the value of ‘c’
Step5: Stop the program
What is the need for algorithms?
1. Algorithms are necessary for solving complex problems efficiently and
effectively.
2. They help to automate processes and make them more reliable, faster, and easier
to perform.
2
, 3. Algorithms also enable computers to perform tasks that would be difficult or
impossible for humans to do manually.
4. They are used in various fields such as mathematics, computer science,
engineering, finance, and many others to optimize processes, analyze data, make
predictions, and provide solutions to problems.
What are the Characteristics of an Algorithm?
The main characteristics of an algorithm are following:
1. Clear and Unambiguous: The algorithm should be clear and unambiguous. Each of its
steps should be clear in all aspects and must lead to only one meaning.
2. Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
It may or may not take input.
3. Well-Defined Outputs: The algorithm must clearly define what output will be yielded and
it should be well-defined as well. It should produce at least 1 output.
4. Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
5. Feasible: The algorithm must be simple, generic, and practical, such that it can be
executed with the available resources. It must not contain some future technology or
anything.
6. Language Independent: The Algorithm designed must be language-independent, i.e. it
must be just plain instructions that can be implemented in any language, and yet the
output will be the same, as expected.
7. Input: An algorithm has zero or more inputs. Each that contains a fundamental operator
must accept zero or more inputs.
8. Output: An algorithm produces at least one output.Every instruction that contains a
fundamental operator must accept zero or more inputs.
9. Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions in an algorithm one can clearly
understand what is to be done. Every fundamental operator in instruction must be defined
without any ambiguity.
10.Finiteness: An algorithm must terminate after a finite number of steps in all test cases.
Every instruction which contains a fundamental operator must be terminated within a
3
, finite amount of time. Infinite loops or recursive functions without base conditions do not
possess finiteness.
11.Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.
What are the properties of an Algorithm?
Properties of an algorithm are following:
● It should terminate after a finite time.
● It should produce at least one output.
● It should take zero or more input.
● It should be deterministic means giving the same output for the same input case.
● Every step in the algorithm must be effective i.e. every step should do some work.
Types of Algorithm:
Brute Force Algorithm: This is the most basic and simplest type of algorithm. A Brute Force
Algorithm is the straightforward approach to a problem i.e., the first approach that comes to our
mind on seeing the problem. More technically it is just like iterating every possibility available to
solve that problem.
Recursive Algorithm: A recursive algorithm is based on recursion. In this case, a problem is
broken into several sub-parts and called the same function again and again.
Examples: Factorial of a Number, Fibonacci Series, Tower of Honai etc.
Divide and Conquer Algorithm: This algorithm breaks a problem into sub-problems, solves a
single sub-problem and merges the solutions together to get the final solution. It consists of the
following three steps:
● Divide
● Solve
● Combine
Examples: Binary Search, Merge Sort, Quick Sort etc.
Dynamic Programming Algorithms: This algorithm uses the concept of using the already
found solution to avoid repetitive calculation of the same part of the problem. It divides the
problem into smaller overlapping subproblems and solves them.
4
Algorithm
The Word algorithm comes from the name of a Persian author, Abu Ja’far Mohammed ibn Musa
al khowarizmi (c.825 AD), who wrote a textbook on mathematics. This word has taken on a
special significance in computer science, where “algorithm” has come to refer to a method that
can be used by a computer for the solution of a problem.
An algorithm is used to provide a solution to a particular problem in a form of well-defined
steps. Whenever we use a computer to solve a particular problem, the steps which lead to the
solution should be properly communicated to the computer. While executing an algorithm on a
computer, several operations such as additions and subtractions are combined to perform more
complex mathematical operations. Algorithms can be expressed using natural language,
flowcharts, etc.
Definition:
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In
addition, all algorithms must satisfy the following criteria:-
1. Input: - Zero or more inputs are externally supplied to the algorithm.
2. Output: - At least one output is produced by an algorithm.
3. Definiteness: - Each step in the algorithm must be clear and unambiguous.
4. Finiteness: - In an algorithm, it will be terminated after a finite number of steps for all
different cases.
5. Effectiveness: - Every instruction must be very basic so that the purpose of those
instructions must be very clear to us.
To achieve definiteness we need to write algorithm in a programming language, such languages
are designed so that each legitimate sentence has a unique meaning. A program is the expression
of an algorithm in a programming language.
Algorithms that are definite and effective are also called computational procedures. One
important example of computational procedures is the operating system of a digital system. This
1
,procedure is designed to control the execution of jobs, in such a way that when no jobs are
available, it does not terminate but continues in a waiting state until a new job is entered.
Advantages of Algorithm:
1. Easy to understand: - Since it is a stepwise representation of a solution to a given
problem, it is easy to understand.
2. Language independent: - It is not dependent on any programming language, so it can
easily be understood by anyone.
3. Debug/Error finding: - Every step is independent/ in a flow so it will be easy to spot and
fix the error.
4. Sub-problems: - It is written in a flow so now the programmer can divide the tasks which
makes them easier to code.
Disadvantages of Algorithms:
1. Creating efficient algorithms is time consuming and requires good logical skills.
2. Nasty to show branching and looping in algorithms.
Example:
Algorithm of adding two numbers
Step1: Start the program
Step2: Read the values of a & b
Step3: Computer the sum of entered numbers ‘a’, ‘b’, c=a+b
Step4: Print the value of ‘c’
Step5: Stop the program
What is the need for algorithms?
1. Algorithms are necessary for solving complex problems efficiently and
effectively.
2. They help to automate processes and make them more reliable, faster, and easier
to perform.
2
, 3. Algorithms also enable computers to perform tasks that would be difficult or
impossible for humans to do manually.
4. They are used in various fields such as mathematics, computer science,
engineering, finance, and many others to optimize processes, analyze data, make
predictions, and provide solutions to problems.
What are the Characteristics of an Algorithm?
The main characteristics of an algorithm are following:
1. Clear and Unambiguous: The algorithm should be clear and unambiguous. Each of its
steps should be clear in all aspects and must lead to only one meaning.
2. Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
It may or may not take input.
3. Well-Defined Outputs: The algorithm must clearly define what output will be yielded and
it should be well-defined as well. It should produce at least 1 output.
4. Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
5. Feasible: The algorithm must be simple, generic, and practical, such that it can be
executed with the available resources. It must not contain some future technology or
anything.
6. Language Independent: The Algorithm designed must be language-independent, i.e. it
must be just plain instructions that can be implemented in any language, and yet the
output will be the same, as expected.
7. Input: An algorithm has zero or more inputs. Each that contains a fundamental operator
must accept zero or more inputs.
8. Output: An algorithm produces at least one output.Every instruction that contains a
fundamental operator must accept zero or more inputs.
9. Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions in an algorithm one can clearly
understand what is to be done. Every fundamental operator in instruction must be defined
without any ambiguity.
10.Finiteness: An algorithm must terminate after a finite number of steps in all test cases.
Every instruction which contains a fundamental operator must be terminated within a
3
, finite amount of time. Infinite loops or recursive functions without base conditions do not
possess finiteness.
11.Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.
What are the properties of an Algorithm?
Properties of an algorithm are following:
● It should terminate after a finite time.
● It should produce at least one output.
● It should take zero or more input.
● It should be deterministic means giving the same output for the same input case.
● Every step in the algorithm must be effective i.e. every step should do some work.
Types of Algorithm:
Brute Force Algorithm: This is the most basic and simplest type of algorithm. A Brute Force
Algorithm is the straightforward approach to a problem i.e., the first approach that comes to our
mind on seeing the problem. More technically it is just like iterating every possibility available to
solve that problem.
Recursive Algorithm: A recursive algorithm is based on recursion. In this case, a problem is
broken into several sub-parts and called the same function again and again.
Examples: Factorial of a Number, Fibonacci Series, Tower of Honai etc.
Divide and Conquer Algorithm: This algorithm breaks a problem into sub-problems, solves a
single sub-problem and merges the solutions together to get the final solution. It consists of the
following three steps:
● Divide
● Solve
● Combine
Examples: Binary Search, Merge Sort, Quick Sort etc.
Dynamic Programming Algorithms: This algorithm uses the concept of using the already
found solution to avoid repetitive calculation of the same part of the problem. It divides the
problem into smaller overlapping subproblems and solves them.
4
