Unit 1

What is Algorithm
• Step by step process/method to perform some
action/solving some problem.
• Finite set of actions
• Skeleton of the actual program.
Defination: It is a sequence of unambigous instructions for
solving a problem ,i.e obtaining required output for any
legitimate input in finite amount of time.
Criteria for writing an algorithm:

• Input: it should have a legitimate or proper input,

externally supplied.
• Output: atleast one quantity is produced as an
output.
• Definiteness : each instructions is clear and
unambiguous.
• Finiteness: algorithm should terminate in finite
no.of steps.
• Effectiveness: feasable, each instruction should
direct to the solution part.
 Methods of Specifying an algorithms
1. Natural Language
2. Flowchart
3. Programming language
4. Combination of all
Natural Language:
This involves describing the algorithm in plain English or another human language. While easy to understand for
humans, natural language can be ambiguous and lead to misinterpretations. It is often used for high-level
descriptions or informal explanations.
Pseudocode:
This is a semi-formal method that combines elements of natural language with programming language-like constructs
(e.g., IF-THEN-ELSE, FOR loops, variable assignments). Pseudocode is more precise than natural language and less tied
to specific syntax than a programming language, making it widely used for algorithm design and communication
among developers.
Flowcharts:
These are graphical representations of an algorithm's steps and decision points, using standardized symbols to depict
operations, inputs/outputs, and control flow. Flowcharts provide a visual overview of the algorithm's logic and can be
helpful for understanding complex processes.
Programming Language Code:
This is the most formal and precise method, where the algorithm is translated directly into executable code in a
specific programming language (e.g., Python, Java, C++). This method is used for implementing the algorithm and
requires adherence to the language's syntax and semantics.
Mathematical Notation:
• For algorithms with strong mathematical foundations, specific mathematical symbols and formulas can be used
to precisely define operations, relationships, and properties. This is common in fields like numerical analysis or
cryptography.
Euclid’s algorithm:
• Euclid’s algorithm is based on applying repeatedly the
equality gcd(m, n) = gcd(n, m mod n) until the second number
becomes zero, which makes the problem trivial.
Fundamentals of algorithmic problem
solving(Algorithm design and analysis process)
1.Understanding the problem:
• Before designing an algorithm is to understand completely the problem given.
• An input to an algorithm specifies an instance of the problem the algorithm solves. It is
very important to specify exactly the set of instances the algorithm needs to handle.
2. Decide on: computational means, exact vs. approximate solving, algorithm design
technique:
• Once you completely understand a problem, you need to ascertain the capabilities of
the computational device the algorithm is intended for.
Exact Algorithm: An exact algorithm is a computational method that guarantees finding the
optimal solution to a given problem. These algorithms aim for perfect accuracy, often at the
potential cost of higher computational time or resource usage, especially for complex
problems.
Ex: Finding the smallest element in an array. An exact algorithm would involve iterating
through the entire array, comparing each element to a current minimum value, and
updating the minimum if a smaller element is found. This process guarantees finding the
absolute smallest element.
Approximation Algorithm: An approximation algorithm is a
computational method that aims to find a near-optimal solution
to a problem within a reasonable time frame, especially for
problems where finding the exact optimal solution is
computationally infeasible or too time-consuming.
Ex: The Traveling Salesman Problem (TSP). Finding the shortest
possible route that visits a set of cities and returns to the origin
city is an NP-hard problem.
An algorithm design technique is a general approach to solving
problems algorithmically that is applicable to a variety of
problems from different areas of computing
• we need to look into appropriate model which could be
selected for solving the problem and along with this we
choose the solution of the problem exactly and solving the
problem approximately. And we use several algorithm design
techniques.
3.Design an algorithm:
• Formulating the algorithm.( designing and defining a step-by-step
procedure or set of instructions to solve a specific problem)
• While the algorithm design techniques do provide a powerful set
of general approaches to algorithmic problem solving, designing an
algorithm for a particular problem may still be a challenging task.
Some design techniques can be simply inapplicable to the problem
in question. Sometimes, several techniques need to be combined.
4. Prove correctness:
• Once an algorithm has been specified, you have to prove its
correctness. That is, you have to prove that the algorithm yields a
required result for every legitimate input in a finite amount of
time.
• A common technique for proving correctness is to use mathemati-
cal induction because an algorithm’s iterations provide a natural
sequence of steps needed for such proofs
5.Analyse the algorithm :
• once it is corrected we need to analyse it.
• After correctness, by far the most important is
efficiency.
• there are two kinds of algorithm efficiency:
time efficiency, indicating how fast the
algorithm runs, and space efficiency,
indicating how much extra memory it uses.
6.Code the algorithm: once the algorithm is
ready it can be implemented as computer
programs.
Time Complexity
• Time complexity quantifies the amount of time an algorithm takes to run as a function of the input
size.
• It typically focuses on the number of elementary operations performed, such as comparisons,
assignments, or arithmetic operations.
• Big O notation is commonly used to express time complexity, describing the upper bound on the
growth rate of the algorithm's runtime.
Ex:
int sumArray (int arr[], int n)
{
int sum = 0; // 1 operation
for (int i = 0; i < n; i++) { // n iterations
sum += arr[i]; // 1 operation per iteration
}
return sum; // 1 operation
}
In this example, the loop runs n times, and inside the loop, a constant number of operations are
performed. Thus, the time taken grows linearly with the input size n. The time complexity is O(n).
Space Complexity
• Space complexity quantifies the amount of memory an algorithm
uses during its execution as a function of the input size.
• This includes both the memory used to store the input and any
auxiliary space required for variables, data structures, or recursive
calls.
Ex:
int sumArray(int arr[], int n)
{
int sum = 0; // Stores one integer
// arr[] is input space, not auxiliary space
return sum;
}
In this example, the sum variable uses a constant amount of memory
regardless of the input array's size n. Therefore, the auxiliary space
complexity is O(1). If we consider the input array itself as part of the
space complexity, it would be O(n) because the array's size depends
on n.
Important problem types:
• Sorting
• Searching
• String processing
• Graph problems
• Combinatorial problems
• Geometric problems
• Numerical problems
1.Sorting :
• Is the process of arranging a collection of items, such as numbers, words, or
objects, into a specific order.
• The sorting problem is to rearrange the items of a given list in nondecreasing
order.
• A sorting algorithm is called stable if it preserves the relative order of any two
equal elements in its input
• An algorithm is said to be in-place if it does not require extra memory, except,
possibly, for a few memory units.
2.Searching:
• The searching problem deals with finding a given value, called a search key, in
a given set .
3. Sting Processing:
• A string is a sequence of characters from an alphabet. Strings of particular
interest are text strings, which comprise letters, numbers, and special
characters
• String processing refers to the manipulation and analysis of sequences of
characters, commonly known as strings, within computer programs.
• Searching for a given word in a text called as string matching.
4.Graph problems:
• graph can be thought of as a collection of points called vertices,
some of which are connected by line segments called edges.
• Graphs can be used for modeling a wide variety of applications,
including transportation, communication, social and economic
networks, project scheduling, and games.
• graph algorithms include graph-traversal algorithms (how can one
reach all the points in a network?), shortest-path algorithms (what
is the best route be- tween two cities?), and topological sorting for
graphs with directed edges .
• Some graph problems are computationally very hard; the most well-
known examples are the traveling salesman problem and the graph-
coloring problem.
• The traveling salesman problem (TSP) is the problem of finding the
shortest tour through n cities that visits every city exactly once.
• The graph-coloring problem seeks to assign the smallest number of
colors to the vertices of a graph so that no two adjacent vertices are
the same colour.
5. Combinatorial problems
• The traveling salesman problem and the graph- coloring problem
are examples of combinatorial problems.
• These are problems that ask, explicitly or implicitly, to find a
combinatorial object such as a permutation, a combination, or a
subset that satisfies certain constraints.
• A desired combinatorial object may also be required to have some
additional property such as a maximum value or a minimum cost.
• combinatorial problems are the most difficult problems in
computing, from both a theoretical and practical standpoint.
• First, the number of combinatorial objects typically grows
extremely fast with a problem’s size, reaching unimaginable
magnitudes even for moderate-sized instances.
• Second, there are no known algorithms for solving most such
problems exactly in an acceptable amount of time.
• Some combinatorial problems can be solved by efficient
algorithms.
6. Geometric Problems
• Geometric algorithms deal with geometric objects such as
points, lines, and polygons.
• The ancient Greeks were very much interested in developing
procedures for solving a variety of geometric problems,
including problems of constructing simple geometric shapes
triangles, circles, and so on with an unmarked ruler and a
compass just bits, bytes, and good old human ingenuity.
• Today people are interested in geometric algorithms with quite
different applications in mind, such as computer graphics,
robotics, and tomography.
• Two classic problems of computational geometry: the closest-
pair problem and the convex-hull problem.
• The closest-pair problem is self-explanatory: given n points in
the plane, find the closest pair among them.
• The convex-hull problem asks to find the smallest convex
polygon that would include all the points of a given set.
7. Numerical Problems
• Numerical problems, another large special
area of applications, are problems that involve
mathematical objects of continuous nature:
solving equations and systems of equations,
computing definite integrals, evaluating
functions, and so on..
 Fundamental Data Structures

• A data structure can be defined as a particular

scheme of organizing related data items.