Data Analysis and Algorithm

• A data structure is a storage that is used to

store and organize data. It is a way of
arranging data on a computer so that it can be
accessed and updated efficiently.
• The idea is to reduce the space and time
complexities of different tasks.
• An efficient data structure also uses minimum
memory space and execution time to process
the structure.
• A data structure is not only used for organizing
the data. It is also used for processing,
retrieving, and storing data. There are
different basic and advanced types of data
structures that are used in almost every
program or software system that has been
developed.
 Need of Data Structure
The structure of the data and the synthesis of
the algorithm are relative to each other.
• Data structure modification is easy.
• It requires less time.
• Save storage memory space.
• Data representation is easy.
• Easy access to the large database
• Linear data structure: Data structure in which data elements are
arranged sequentially or linearly, where each element is attached
to its previous and next adjacent elements, is called a linear data
structure.
Examples of linear data structures are array, stack, queue, linked
list, etc.
– Static data structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.
An example of this data structure is an array.
– Dynamic data structure: In dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be
considered efficient concerning the memory (space) complexity of the
code.
Examples of this data structure are queue, stack, etc.
• Non-linear data structure: Data structures
where data elements are not placed
sequentially or linearly are called non-linear
data structures. In a non-linear data structure,
we can’t traverse all the elements in a single
run only.
Examples of non-linear data structures are
trees and graphs.
• The word Algorithm means ” A set of finite
rules or instructions to be followed .
• A procedure for solving a mathematical
problem in a finite number of steps that
frequently involves recursive operations”.
• The Algorithm designed are language-
independent, i.e. they are just plain
instructions that can be implemented in any
language, and yet the output will be the same,
as expected.
 Need of Algorithm
• Algorithms are necessary for solving complex
problems efficiently and effectively.
• They help to automate processes and make them
more reliable, faster, and easier to perform.
• Algorithms also enable computers to perform tasks
that would be difficult for humans to do manually.
• 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.
Difference between Algorithm and Program
 Characteristics of Algorithm
• Clear and Unambiguous: Each of its steps should be clear in all
aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it
should be well-defined inputs. It may or may not take input.
• 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.
• Finite-ness: The algorithm must be finite, i.e. it should
terminate after a finite time.
• Feasible: The algorithm must be simple, generic, and practical,
such that it can be executed with the available resources.
 Characteristics of Algorithm
• Definiteness: All instructions in an algorithm must be
unambiguous, precise, and easy to interpret. Every
fundamental operator in instruction must be defined without
any ambiguity.
• Finiteness: An algorithm must terminate after a finite number
of steps in all test cases..
• 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.
• Language Independent: It must be just plain instructions that
can be implemented in any language, and yet the output will
be the same, as expected.
 Characteristics of Algorithm
• It should terminate after a finite time.
• 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
• 1. Recursive Algorithm
• This is one of the most interesting Algorithms as it
calls itself with a smaller value as inputs which it gets
after solving for the current inputs. In more simpler
words, It’s an Algorithm that calls itself repeatedly
until the problem is solved.
• Problems such as the Tower of Hanoi or DFS of a
Graph can be easily solved by using these Algorithms.
• For example, here is a code that finds a factorial using
a recursion Algorithm:
 Types of Algorithm
• 2. Divide and Conquer-This is another effective way
of solving many problems. In Divide and Conquer
algorithms, divide the algorithm into two parts; the
first parts divide the problem on hand into smaller
subproblems of the same type. Then, in the second
part, these smaller problems are solved and then
added together (combined) to produce the
problem’s final solution.
• Merge sorting, and quick sorting can be done with
divide and conquer algorithms.
 Types of Algorithm
• 3. Dynamic Programming Algorithm
• These algorithms work by remembering the results
of the past run and using them to find new results. In
other words, a dynamic programming algorithm
solves complex problems by breaking them into
multiple simple subproblems and then it solves each
of them once and then stores them for future use.
• Fibonacci sequence is a good example for Dynamic
Programming algorithms, you can see it working in
the pseudo code:
 Types of Algorithm
• 4. Greedy Algorithm
• These algorithms are used for solving optimization problems. In this algorithm,
we find a locally optimum solution (without any regard for any consequence in
future) and hope to find the optimal solution at the global level.
• The method does not guarantee that we will be able to find an optimal solution.
• The algorithm has 5 components:
• The first one is a candidate set from which we try to find a solution.
• A selection function that helps choose the best possible candidate.
• A feasibility function that helps in deciding if the candidate can be used to find a
solution.
• An objective function that assigns value to a possible solution or to a partial
solution
• Solution function that tells when we have found a solution to the problem.
• Huffman Coding and Dijkstra’s algorithm are two prime examples where the
Greedy algorithm is used.
 Types of Algorithm
• 5. Brute Force Algorithm
• This is one of the simplest algorithms in the
concept. A brute force algorithm blindly iterates all
possible solutions to search one or more than one
solution that may solve a function. Think of brute
force as using all possible combinations of numbers
to open a safe.
• Example of Sequential Search done by using brute
force:
 Types of Algorithm
• 6. Backtracking Algorithm
• Backtracking is a technique to find a solution to a problem
in an incremental approach. It solves problems recursively
and tries to solve a problem by solving one piece of the
problem at a time. If one of the solutions fail, we remove
it and backtrack to find another solution.
• In other words, a backtracking algorithm solves a
subproblem, and if it fails to solve the problem, it undoes
the last step and starts again to find the solution to the
problem.
• N Queens problem is one good example to see
Backtracking algorithm in action.
 Why DSA is important
• Programming is all about data structures and
algorithms. Data structures are used to hold data
while algorithms are used to solve the problem
using that data.
• Data structures and algorithms (DSA) goes through
solutions to standard problems in detail and gives
us an insight into how efficient it is to use each one
of them. It also teaches the science of evaluating
the efficiency of an algorithm. This enables us to
choose the best of various choices.
 Why DSA is important
Finding the sum of the first 1011 natural numbers.
Algorithm

Program
 Why DSA is important
Now suppose there is an error in the program to debug the program and find the error
in the program will take lot of time as there will be for loop running for 10 raise to
power 11 times.

Time to run code = number of instructions * time to execute each instruction

But if we do it with the right method using formula :-

Sum = N * (N + 1) / 2

We can find it for any range and also Scalability which is scale plus ability, which means
the quality of an algorithm/system to handle the problem of larger size.
 Algorithm to add three numbers
• START
• Declare 3 integer variables num1, num2 and num3.
• Take the three numbers, to be added, as inputs in
variables num1, num2, and num3 respectively.
• Declare an integer variable sum to store the resultant
sum of the 3 numbers.
• Add the 3 numbers and store the result in the variable
sum.
• Print the value of the variable sum
• END
Algorithm to find largest among three
numbers
Algorithm to find Roots of a Quadratic
Equation ax2 + bx + c = 0
Algorithm to find factorial of a number
Algorithm to find if the number is prime or
not
Algorithm to find the Fibonacci series till
the terms less than 1000
 Pseudocode Conventions
• It is a false code or is a high-level description of an algorithm. Pseudocode can be
easily understood by someone who has basic knowledge of programming.

• Pseudocode does not have a specific syntax unlike a program that is written
using syntaxes of a particular language. Hence, pseudocode cannot be executed
on a computer, rather it eases the work of a programmer as it can be easily
understood.
• We can use control structures that include for, while, if-then-else, repeat until.
These control structures are common in almost all programming languages and
hence can be used when required.

• Another advantage of pseudocode is that the running time of the program can
be estimated in a general manner using it. A pseudocode gives us a count of
fundamental operations. Also, pseudocode avoids any ambiguity that might be
present in plain text.
 Difference between Pseudocode and
Algorithm
• A pseudocode is a method which is used to represent an
algorithm.
•
• An algorithm has some specific characteristics that
describe the process.
• A pseudocode on the other hand is not restricted to
something. It’s only objective is to represent an algorithm
in a realistic manner. An algorithm is written in plain
English or general language.
• A pseudocode is written with a hint of programming
concepts such as control structures.
Steps to follow while making a pseudocode

• Make use of control structures.

• Naming conventions must be followed
properly.
• Use indentation and white spaces wherever
required as these are the key points for a
pseudocode.
• Keep the pseudocode simple and concise.
 Complexity
• The term algorithm complexity measures how
many steps are required by the algorithm to
solve the given problem. It evaluates the order
of count of operations executed by an
algorithm as a function of input data size.
• The amount of space required for an algorithm to be
executed completely is referred to as Space complexity.
• Time complexity refers to the time taken by an
algorithm to be executed.
• Time complexity or space complexity does not
completely refer to the time taken or space taken to
execute a program. There are several factors that are
taken into consideration while calculating the
complexities like the processing power, operating
software, the compiler etc.
 Space Complexity

• Space complexity is a combination of auxiliary space

and input space. Where auxiliary space is the extra
space or buffer space that will be used by an
algorithm during execution. Also, we know that space
complexity is all about memory. Below are a few
points on how the memory is used during execution.

• Instruction space: the compiled version of

instructions are stored in memory. This memory is
called instruction space.
 Space Complexity

• Environmental stack: We use environmental stacks in cases where

a function is called inside another function.
• For example, a function cat() is called inside the function animals().

• Then the variables of function animals() will be stored temporarily

in a system stack when function cat() is being executed inside the
function animals().

• Data Space: The variables and constants that we use in the

algorithm will also require some space which is referred to as data
space.
• In most of the cases, we neglect environmental stack and
instruction space. Whereas, data space is always considered.
 Space Complexity

• To calculate the space complexity we need to have an idea about the value of the
memory of each data type. This value will vary from one operating system to
another. However, the method used to calculate the space complexity remains the
same.

Example 1:
{ int a,b,c,sum;
sum = a + b + c;
return(sum);
}
• We have 4 variables which are a, b, c, and sum. All these variables are of type int
hence, each of them require 4 bytes of memory.
• Total requirement of memory would be : ((4*4)+4) => 20 bytes.

• Here, we have considered 4 additional bytes of memory which is for the return
value. Also, for this example as the space requirement is fixed it is known as
 Space Complexity

Eg2:-

In this example, we have 3 variables i, k, n each of which will be assigned 4

bytes of memory. Also, for the return value 4 bytes of memory will be
assigned. Here, we also have an array of size n, hence the memory required
for that would be (4*n).

Hence the total memory requirement would be : (4n+16)

This value will vary based on the value of n. As the value of n increases the
memory would also increase linearly. Therefore it is known as Linear Space
Complexity.
 Time Complexity
• Time complexity is most commonly evaluated
by considering the number of elementary
steps required to complete the execution of
an algorithm. Also, many times we make use
of the big O notation which is an asymptotic
notation while representing the time
complexity of an algorithm.
 Time Complexity
• Constant time complexity:
Example:
Statement – printf(“i2 tutorials”);

• In the above example, as it is a single

statement the complexity of it would be
constant. Its complexity wouldn’t change as it
is not dependent on any variable.
 Time Complexity
• Linear time complexity:
Example:
for(i=0; i < N; i++)
{ statement;
}
• Here, the complexity would vary as the number
of times the loop iterates would be based on
the value of n. Hence, the time complexity
would be linear.
 Time Complexity
• Quadratic time complexity:
Example:
for(i=0; i < N; i++)
{ for(j=0; j < N;j++)
{ statement; } }
• Here, in this example we have a loop inside
another loop. In such a case, the complexity
would be proportional to n square. Hence, it
would be of type quadratic and therefore the
complexity is quadratic complexity
 Time Complexity
• Logarithmic time complexity:

In this example, we are working on dividing a set of

numbers into two parts. Which means that the
complexity would be proportional to the number of
times n can be divided by 2, which is a logarithmic
value. Hence we have a logarithmic time complexity.
 Asymptotic Notations
• The efficiency of an algorithm depends on the
amount of time, storage and other resources
required to execute the algorithm. The efficiency is
measured with the help of asymptotic notations.
• An algorithm may not have the same performance
for different types of inputs. With the increase in the
input size, the performance will change.
• The study of change in performance of the algorithm
with the change in the order of the input size is
defined as asymptotic analysis.
 Asymptotic Notations
• Asymptotic notations are the mathematical notations used
to describe the running time of an algorithm when the
input tends towards a particular value or a limiting value.
• Eg: In bubble sort, when the input array is already sorted,
the time taken by the algorithm is linear i.e. the best case.
• But, when the input array is in reverse condition, the
algorithm takes the maximum time (quadratic) to sort the
elements i.e. the worst case.
• When the input array is neither sorted nor in reverse
order, then it takes average time. These durations are
denoted using asymptotic notations.
 Asymptotic Notations
• There are mainly three asymptotic notations:
• Big-O notation
• Omega notation
• Theta notation
 Big-O Notation (O-notation)
• Big-O notation represents the upper bound of the running time of an
algorithm. Thus, it gives the worst-case complexity of an algorithm.
• Big-O gives the upper bound of a function
• Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all
n > n0. }
• The above expression can be described as a function f(n) belongs to
the set O(g(n)) if there exists a positive constant c such that it lies
between 0 and cg(n), for sufficiently large n.
 Omega Notation (Ω-notation)
• Omega notation represents the lower bound of the running
time of an algorithm. Thus, it provides the best case
complexity of an algorithm.
• Ω(g(n)) = { f(n): there exist positive constants c and n0 such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
• The above expression can be described as a
function f(n) belongs to the set Ω(g(n)) if there exists a positive
constant c such that it lies above cg(n), for sufficiently large n.
 Theta Notation (Θ-notation)

• Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.
• Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0
≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }.
• The above expression can be described as a function f(n) belongs to
the set Θ(g(n)) if there exist positive constants c1 and c2 such that it
can be sandwiched between c1g(n) and c2g(n), for sufficiently large n.
• If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥
n0, then f(n) is said to be asymptotically
tight bound.
•
Q2) Algorithms are used for
• a) Easy Programming
• b) Testing and Debugging
• c)Efficient Coding
• d) All of the above

• Q3)Which asymptotic notation is used for lower bound constraint:-

• a) Big O
• b)Theta
• c)Omega
• d) None of the above