IT2311 - Data Structures and Algorithms
Unit I: Introduction: Linear Data Structures & Analysis of Algorithms
S.No Date Topics to be covered
1 16.7.25 Introduction to Algorithms
Analysis of Algorithms: Efficiency of an Algorithm
2 17.7.25
Frequency count and its importance
3 18.7.25 Time Complexity, Space Complexity
Introduction to Data Structures, Abstract Data Types
4 19.7.25
(ADTs)
5 19.7.25 Lists: Array implementation
6 21.7.25 Dynamic implementation -Singly Linked Lists
7 23.7.25 Doubly-Linked Lists
8 24.7.25 Circularly Linked Lists
9 25.7.25 Linked List application: Polynomial Representation-Addition
Test Date : 28.7.25 ( Unit Test-1)
Course Outcome:
CO 1: Identify the asymptotic notations to find the complexity of an
algorithm and define linear and non-linear data structures
Introduction to Algorithms
An algorithm is a finite set of instructions
that, if followed, accomplishes a particular
task.
In addition, all algorithms must satisfy the
following criteria:
Input
Output
Definiteness
Finiteness
Effectiveness.
Introduction to Algorithms
Example :
Calculating Greatest common Divisor
The Greatest common Divisor (GCD) of two
non zero numbers a and b is basically the largest
integer that divides both a and b evenly i.e with
a remainder of zero.
GCD using three methods
1. Euclid's algorithm
2. Consecutive integer checking algorithm
3. Finding Guessing repetitive factors Euclid's
algorithm to compute Greatest Common
Divisor (GCD) of two non negative integers.
Introduction to Algorithms
1. Euclid's algorithm to compute Greatest
Common Divisor (GCD) of two non negative
integers.
gcd (m, n) = gcd (n, m mod n) until the m and n
is equal to 0 Where m mod n is the remainder
of the division of m by n
Step 1: Start
Step 2: If n = 0, return the value of m as the
answer and stop, otherwise proceed to step 3.
Step 3: Divide m by n and assign the value of the
remainder to r.
Step 4: Assign the value of n to m and the value
of r to n. Goto step 2
Step 5: Stop
Introduction to Algorithms
Example, gcd (60,24) can be computed as follows,
gcd (60,24) gcd (m, n)
m =60, n=24;
m % n = 12
n=m (24)
r=n (12)
gcd (24, 12) m/2 = 2 (remainder 0)
n=m (12)
r=n (0)
gcd (12, 0) =12
Hence, gcd(60, 24) = gcd(24,l2)=gcd(12,0)=12
Introduction to Algorithms
2. Consecutive integer checking algorithm In this method
while finding the GCD of a and b we first of all find the
minimum value of them.
Suppose if , value of b is minimum then we start checking
the divisibility by each integer which is lesser than or equal
to b.
Step 1: Start
Step 2: Assign the value of mini {m, n} to t
Step 3: Divide m by t.
If the remainder of this division is 0, go to step 4,
Otherwise goto step 5.
Step 4: Divide n by t.
If the remainder of this division is 0, return the value of
t as the answer and stop. Otherwise proceed to
step 5.
Step 5: Decrease the value of t by I. Go to step 3.
Step 6: Stop
Introduction to Algorithms
Algorithm GCD int check (a,b)
t ← min ( a, b)
while (t>=1) do
{
If ( a mod t == 0 AND b mod t == 0) then
Return t
Else
t ← t-1
}
Return 1
Introduction to Algorithms
3. Finding GCD using repetitive factors The third
procedure for finding the greatest common divisor
Introduction to Algorithms
Algorithm:
Step 1: Start
Step 2: Find the prime Factor of m.
Step 3: Find the prime factors of n.
Step 4: Identify all the common factors in the two
prime expressions Found in step 2 and step 3.
If' P is a common factor occurring pm and pn
times in m and n respectively. It should be repeated
min (pm, and pn) times.
Step 5: Compute the product of the all the common
factors and return it as the greatest common divisor
of the numbers given.
Step 6: Stop.
Analysis of Algorithms
Efficiency of an Algorithm
Frequency count and its importance
Efficiency of an Algorithm
✓ Efficiency of an algorithm is determined by measuring
the time, space and amount of resources, it uses for
executing the program.
✓ The efficiency of the algorithm is determined with
respect to central processing units time and internal
memory.
✓ There are two types of algorithm efficiency.
o Time efficiency (or) Time Complexity
o Space efficiency (or) Space Complexity
Analysis of Algorithms
Time Efficiency / Time Complexity
✓ Time efficiency indicates how fast the algorithm runs.
✓ The time taken by a program to complete its task depends on the
number of steps in an algorithm.
✓ The time required by a program to complete its task will not always be
the same.
✓ It depends on the type of problem to be solved. It can be of two types.
o Compilation Time
o Run Time (or) Execution Time
✓ The time (T) taken by an algorithm is the sum of the compile time and
execution time.
Compilation Time
✓ The amount of time taken by the compiler to compile an algorithm is
known as compilation time.
✓ During compilation time, it does not calculate the executable statements,
it calculates only the declaration statements and check for any syntax and
semantic errors.
✓ The different compilers can take different times to compile the same
program.
Analysis of Algorithms
Execution Time
✓ The execution time depends on the size of the algorithm.
✓ If the number of instructions in an algorithm is large then the run time
is also large.
✓ If the number of instructions in an algorithm is small then the time need
to execute the program is small.
✓ The execution time is calculated for executable statements and not for
the declaration statements.
✓ The complexity is normally expressed as an order of magnitude.
✓ Example: O (n^ 2)
✓ The time complexity of a given algorithm is defined as computation of
function f() as a total number of statements that are executed for
computing the value f(n).
✓ The time complexity is a function which depends on the value of n. The
time complexity can be classified as 3 types.
They are
1. Worst Case analysis
2. Average Case analysis
3. Best Case analysis
Analysis of Algorithms
Frequency count and its importance
Step Count Method
The step count method is one of the methods
to analyze the Time complexity of an algorithm.
In this method, counts the number of times
each instruction is executed.
Based on that we will calculate the Time
Complexity.
The step Count method is also called as
Frequency Count method.
Frequency count and its importance
Step count for different statements:
1. Comments: - 0
2. Conditional statements:
Conditional statements - 1
if-else statements - 1
switch… case.. statements - 1
nested if and if else ladder statements - 1
3. Loop statements:
Loop statements are iterative statements - n
for(i = 0; i ≤ n; i++) statement - n+1
While - n
Do while - n
4. Functions:
BEGIN, END and goto statements - n
Frequency count and its importance
Illustration of Step Count Method:
Analysis of Linear Search algorithm
Linearsearch(arr, n, key)
{
i = 0; ----------------------------------O(1)times
for(i = 0; i < n; i++) ----------------O(n+1)times
{
if(arr[i] == key) -------------O(1)times
{
printf(“Found”);-----O(0)/O(1)times
}
}
}
Frequency count and its importance
i = 0, is an initialization statement and takes O(1)
times.
for(i = 0;i < n ; i++), is a loop and it takes O(n+1)
times .
if(arr[i] == key), is a conditional statement and takes
O(1) times.
printf(“Found”), is a function and that takes O(0)/O(1)
times.
Therefore Total Number of times it is executed is n +
4 times.
As we ignore lower exponents in time complexity
total time became O(n).
Time complexity: O(n).
Auxiliary Space: O(1)
Frequency count and its importance
Searching for an element in a matrix
AlgoMatrixsearch(mat[][], key)
{
r= len(mat); // number of rows
c =len(mat[0]); // number of columns
for(i = 0; i < r; i++)
{
for(j = 0; j < c; j++)
{
if(mat[i][j] == key)
{
printf(“Element found”);
}
}
}
}
Frequency count and its importance
r = len(mat), takes O(1) times.
c = len(mat[0]), takes O(1) times
for(i = 0; i < r; i++), takes O(r + 1) times
for(j = 0; j < c; j++), takes O(( c + 1 ) ) for each time
the outer loop is satisfied. So total r times the loop is
executed. O((r) * (c + 1) )
if(mat[i][j] == key), takes O(1) times
printf(“Element found”), takes O(0)/O(1) times.
Total Number of times it is executed is
(1 + 1 + (r + 1) + (r) * (c + 1) + 1) times.
As we ignore the lower exponents, total complexity
became O(r * (c + 1)).
Time Complexity: O(n^2). Auxiliary Space: O(n^2)
Frequency count and its importance
Types of Algorithm
There are two ways to write an algorithm, namely, top-down
approach (Iterative algorithm) and bottom-up approach
(Recursive algorithm).
For example, the iterative and recursive algorithm for finding a
factorial of a given number n is given below:
1. Iterative :
Fact(n)
{
for i = 1 to n
fact = fact * i;
return fact;
}
Here the factorial is calculated as 1x2x3x….xn
Frequency count and its importance
2. Recursive :
Fact(n)
{
if n = 1
return 1;
else
return n * fact(n-1);
}
Here the factorial is calculated as n x (n-1) x (n-2) x…. x 1
Frequency count and its importance
Step-count Method and Asymptotic Notation
Time and space complexity are calculated using step
count method.
Some basic assumptions are;
There is no count for { and } .
Each basic statement like assignment and return
have a count of 1.
If a basic statement is iterated, then multiply by
the number of times the loop is run.
The loop statement is iterated n times, it has a
count of (n + 1).
Here the loop runs n times for the true case
and a check is performed for the loop exit (the false
condition), hence the additional 1 in the count.
Frequency count and its importance
Frequency count and its importance
Frequency count and its importance
