1|Page

Unit – I
Introduction to Algorithm and Data
Structures
1. Introduction

1.1 From Problem to Program

From Problem to Program involves transforming a real-world problem into a functional

software solution.

1. Problem: A real-world challenge or task that needs solving (e.g., sorting a list of
numbers).

2. Solution: The conceptual approach or plan to solve the problem, including identifying
the necessary operations.

3. Algorithm: A step-by-step sequence of instructions to achieve the solution (e.g., bubble

sort for sorting).

4. Data Structure: The organization and storage of data used by the algorithm (e.g.,
arrays, linked lists, trees).

5. Program: The implementation of the algorithm and data structures using a

programming language to create an executable solution.

This process ensures a logical flow from understanding the problem to writing a program that
solves it efficiently.

1.2 Data Structure

A data structure is a way of organizing, managing, and storing data in a computer so it can be
accessed and modified efficiently.

Example: Consider a set of elements that can be stored in an array data structure. The
representation of the array containing set of elements is as follows:
2|Page

1.2 Difference between Data and Information

Sr. No. Data Information

1 Data is in raw form. Information is processed form of data.

2 Data may or may not be meaningful. Information is always meaningful.
3 Data may not be in some specific Information generally follows specific
order. ordering.
4 Example: Each student’s marks in Example: The average score of a class is
exam are one piece of data. information that can be derived from
given data.

1.2 Abstract Data Structures

An Abstract Data Type (ADT) is a theoretical concept that defines a data type purely in terms
of its behavior (operations) rather than its implementation. It describes what operations can be
performed, not how they are implemented. ADTs provide a blueprint for data structures by
focusing on functionality and hiding implementation details.

ADT ARRAY can be declared as below:

Structure ARRAY(value, index)

declare

CREATE() → array

RETRIEVE(array, index) → value

STORE(array, index, value) → array

The function CREATE() produces an empty array.

The function RETRIEVE() takes as input an array and an index, and either returns the
appropriate value of an error.
3|Page

The function STORE() is used to enter new index-value pairs.

1.3 Linear and Non-Linear Data Structure

1. Linear Data Structure

Linear data structures are the data structures in which data s arranged in a list or in a straight
sequence.

Example: arrays, lists

2. Non-linear Data Structure

Non-linear data structures are the data structures in which data may be arranged in a
hierarchical manner.

Example: trees, graphs

1.4 Static and Dynamic Data Structure

1. Sta c Data Structure

The static data structures are data structures having fixed size memory utilization. One has to
allocate the size of this data structure before using it.

Example: Arrays in C are a static data structure. We first allocate the size of the arrays before
its actual use. Sometimes the size we have allocated for the arrays might be wasted or we may
require a larger size than the one which is existing. Thus, the data structure is static in nature.

2. Dynamic Data Structure

The dynamic data structure is a data structure in which one can allocate the memory as per his
requirement. If one does not want to use some block of memory, he can deallocate it.
4|Page

Example: A linked list is a collection of many nodes. Each node consists of data and pointer
to next node. In linked list, the user can create as many nodes (memory) as he wants, he can
deallocate the memory which cannot be utilized further. The advantage of dynamic data
structure over the static data structure is that there is no wastage of memory.

1.5 Persistent and Ephemeral Data Structure

1. Persistent Data Structure

A persistent data structure is a data structure that can be accessed but cannot be modified.

Any operation on such data structure creates two versions of data structures. Previous version
is saved and all changes are made in the new version.

2. Ephemeral Data Structure

An ephemeral data structure is a data structure that only allows one version to be available
at a time.

When an update is made to an ephemeral data structure, the previous version is lost.

2. Algorithms

2.1 Problem Solving

Problem solving is based on the decisions that are taken.

Following are the six steps of problem solving:

1. Identify the problem: Identifying the problem is the first step in solving the problem.
Problem identification is very essential before solving any problem.
2. Understand the problem: Before solving any problem, it is important to understand
it. There are three aspects based on which the problem can be understood.
 Knowledgebase: While solving the problem, the knowledgebase can be related
to a person or a machine. If the problem is to be solved for a person, then it is
necessary to know what a person knows.
 Subject: Before solving the problem, the subject or the topic on which the
problem is based must be known. For example, to solve a problem involving
Laplace Transformation, it is necessary to first know about Laplace
Transformation.
5|Page

 Communication: For understanding the problem, the developer must

communicate with the client.
3. Identify alternative ways to solve the problem: The developer must know some
alternative ways to solve the problem. These alternatives can be decided by
communicating with the customer.
4. Select the best way to solve the problem from list of alternative solutions: For
selecting the best way to solve the problem, the merits and demerits of each problem
must be analyzed.
5. List the instructions using the selected solution: Based on the knowledgebase
(created/used in step 2) the step-by-step instructions are listed out. Each and every
instruction must be understood by the person or the machine involved in the problem-
solving process.
6. Evaluate the solution: When the solution is evaluated then i) Check whether the
solution is correct or not ii) Check whether it satisfies the requirements of the customer
or not.

2.2 Difficulties in Problem Solving

 People do not know how to solve particular problem.

 Many times, people get afraid of taking decisions.
 While following the problem-solving steps people complete one or two steps
inadequately.
 People do not define the problem statements correctly.
 They do not generate the sufficient list of alternatives. Sometimes good alternatives
might get eliminated. Sometimes the merits and demerits of the alternatives is defined
hastily.
 The sequence of solution is not defined logically, or the focus of the design is
sometimes on detailed work before the framework solution.
 When solving the problems on computer then writing the instructions for the computer
is most crucial task. With lack of knowledgebase, one cannot write the proper
instruction set for the computers.

2.3 Introduction to Algorithms

The word algorithm means “a set of finite rules or instructions to be followed in calculations
or other problem-solving operations”.
6|Page

Characteristics of Algorithms:

 Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps
should be clear in all aspects and must lead to only one meaning.

 Input: An algorithm has zero or more inputs.

 Output: An algorithm produces at least one output.

 Definiteness: All instructions in an algorithm must be definite, precise, and easy to

interpret.

 Finiteness: The algorithm must be finite, i.e. it should terminate after a finite time.

 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.

Example: Algorithm to Compute the Sum of the Digits of a Given Number

Step 1: Start
Step 2: Input the number 'num'.
Step 3: Initialize 'sum' to 0.
Step 4: While 'num' is greater than 0, repeat steps 5 to 7:
Step 5: Extract the last digit of 'num' using:
digit = num % 10
Step 6: Add 'digit' to 'sum':
sum = sum + digit
Step 7: Remove the last digit from 'num' by performing integer
division:
num = num // 10
Step 8: Output 'sum' (the sum of the digits).
Step 9: Stop.
For example, for the number 543:
 5 + 4 + 3 = 12, so the algorithm returns 12.
2.4 Algorithm Design Tools

1. Pseudocode
7|Page

A pseudocode is defined as a step-by-step description of an algorithm. Pseudocode does not

use any programming language in its representation instead it uses the simple English language
text as it is intended for human understanding rather than machine reading.

Pseudocode is the intermediate state between an idea and its implementation(code) in a high-
level language.

Example: Pseudocode to find factorial of a number

1. Start
2. Input n (the number to find the factorial of)
3. Initialize factorial = 1
4. If n < 0:
a. Output "Factorial is not defined for negative numbers"
b. Stop
5. For i = 1 to n:
a. factorial = factorial * i
6. Output factorial
7. Stop

2. Flowchart

A flowchart is a type of diagram that represents a workflow or process. A flowchart can also
be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving
a task.

Example: Flowchart to check whether a given number is a perfect square of an integer

8|Page

3. Complexity of Algorithm

3.1 Space Complexity

The space complexity can be defined as amount of memory required by an algorithm to run.

To compute the space complexity, we use two factors: constant and instance characteristics.

The space requirement S(p) can be given as

S(p) = C + Sp

where C is a constant i.e. fixed part and it denotes the space of inputs and outputs. This space
is an amount of space taken by instruction, variables and identifiers. And Sp is a space
dependent upon instance characteristics. This is a variable part whose space requirement
depends on particular problem instance.
9|Page

3.2 Time Complexity

The amount of time required by an algorithm to execute is called the time complexity of that
algorithm.

For determining the time complexity of a particular algorithm, following steps are carried out:

1. Identify the basic operation of the algorithm.

2. Obtain the frequency count for this basic operation.

3. Consider the order of magnitude of the frequency count and express in terms of big oh
notation.

3.3 Asymptotic Notations

Asymptotic notations are mathematical tools used to describe the performance (time or space
complexity) of algorithms in terms of input size n, especially as the input grows large. They
help express how an algorithm's resource consumption grows with respect to input size.

1. Big-O Nota on (O):

Big-O notation describes the upper bound of the time complexity of an algorithm. It tells you
the worst-case scenario — how much time or space the algorithm will take in the worst
possible case as the input grows.

 Definition: A function f(n) is said to be O(g(n)) if there exist constants c > 0 and n0 ≥ 0
such that:

f(n) ≤ c⋅ g(n) for all n ≥ n0

10 | P a g e

This means f(n) will not grow faster than g(n) for large inputs.

 Example: For a linear search through an array of n elements, the time complexity is
O(n). This means in the worst case; it will take at most linear time as the input size
grows.

2. Theta Nota on (θ):

Theta notation describes the tight bound of an algorithm. It tells you the exact asymptotic
behavior, meaning it represents both the upper bound (worst-case) and lower bound (best-case)
of the algorithm.

 Definition: A function f(n) is said to be θ(g(n)) if there exist constants c1, c2 > 0 and
n0 ≥ 0 such that:

c1⋅ g(n) ≤ f(n) ≤ c2⋅ g(n) for all n≥n0

This means f(n) grows at the same rate as g(n) as the input grows large.

 Example: For an algorithm that runs exactly n steps for an input of size n, the time
complexity is θ (n). This means that for large inputs, the time complexity is both upper-
and lower-bounded by a linear function.

3. Omega Nota on (Ω):

11 | P a g e

Omega notation describes the lower bound of an algorithm. It tells you the best-case scenario
— the minimum time or space an algorithm will take as the input grows.

 Definition: A function f(n) is said to be Ω(g(n)) if there exist constants c > 0 and n0 ≥ 0
such that:

f(n) ≥ c⋅ g(n) for all n ≥ n0

This means f(n) will take at least g(n) time or space for large inputs.

 Example: In a linear search, the best case occurs when the element is found in the first
position. The time complexity is Ω(1), meaning the algorithm will take constant time
in the best case.

3.4 Finding Complexity using Step Count Method

The Step Count or the Frequency Count Method is a technique used to analyze the time
complexity of an algorithm by counting the number of individual steps or basic operations the
algorithm performs, relative to the size of its input. Each line of code or operation is assigned
a step count, and the total number of steps is then expressed as a function of the input size,
typically using Big-O notation.

Steps to Apply the Step Count Method:

1. Identify basic operations in the algorithm (e.g., assignments, comparisons, arithmetic

operations).

2. Count the number of times each basic operation is executed as a function of the input
size (n).
12 | P a g e

3. Sum up the total steps for the algorithm.

4. Express the result using Big-O notation to simplify the analysis.

Example:

int x = 0; …1
for (i = 0; i < n; i++) // Outer loop …(n+1)
{
for (j = n; j > i; j--) // Inner loop …n(n+1)
{
x = x + i + j; // Basic operation …n*n
}
}
f(n) = 1 + (n+1) + n(n+1) + (n*n)

f(n) = 2n2 + 2n + 2

Time Complexity = O(n2)

1.2 Analysis of Programming Constructs: Linear, Quadratic, Cubic, Logarithmic

The time complexity of algorithms is often categorized based on how the number of operations
grows relative to the input size n.

1. Linear Time Complexity (O(n)):

 Description: The number of operations grows proportionally with the input size n.
For each new element in the input, the algorithm does a constant amount of additional
work.

 Example: Iterating through an array of size n.

for (i = 0; i < n; i++) { /* some operation */ }

2. Quadratic Time Complexity (O(n²)):

 Description: The number of operations grows proportionally to the square of the

input size n. This typically occurs with nested loops, where each loop iterates over n
elements.

 Example: Checking all pairs of elements in an array.

13 | P a g e

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) { /* some operation */ }
}
3. Cubic Time Complexity (O(n³)):

 Description: The number of operations grows proportionally to the cube of the input
size n. This happens when you have three nested loops, each iterating over n elements.

 Example: Checking all triplets of elements in an array.

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) { /* some operation */ }
}
}
4. Logarithmic Time Complexity (O(log n)):

 Description: The number of operations grows proportionally to the logarithm of the

input size n. Algorithms that repeatedly halve the input size are often logarithmic.

 Example: Binary search.

int binarySearch(int arr[], int left, int right, int x) {

while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}

4. Algorithmic Strategies
Algorithm design strategy is a general approach by which many problems can be solved
algorithmically. These problems may belong to different areas of computing. Algorithmic
strategies are also called as algorithmic techniques or algorithmic paradigm.
14 | P a g e

4.1 Divide and Conquer Strategy

In divide and conquer method, a given problem is,

1. Divided into smaller sub problems

2. These sub problems are solved independently.
3. If necessary, the solutions of the sub problems are combined to get a solution to the
original problem.

If the sub problems are large enough, then divide and conquer is reapplied.

The divide and conquer technique is as shown below:

The generated sub problems are usually of same type as the original problem. Hence
sometimes recursive algorithms are used in divide and conquer strategy.

Example: Merge Sort

The merge sort is a sorting algorithm that uses the divide and conquer strategy. In this method,
division is dynamically carried out.

Merge sort on an input array within elements consists of three steps:

1. Divide: Partition array into two sub lists s1 and s2 with n/2 elements each.
2. Conquer: Then sort sub-lists s1 and s2.
3. Combine: Merge s1 and s2 in a unique sorted group.

Consider the elements as 38, 27, 43, 10.

15 | P a g e

Now we split this list into two sub-lists.

4.2 Greedy Strategy

This method is popular for obtaining the optimized solutions.

In Greedy technique, the solution is constructed through a sequence of steps, each expanding
a partially constructed solution obtained so far, until a complete solution to the problem is
reached.

In Greedy method following activities are performed:

1. First, we select some solution from input domain.

2. Then we check whether the solution is feasible or not.
3. From the set of feasible solutions, a particular solution that satisfies or nearly satisfies
the objective of the function is called optimal solution.
4. As Greedy method works in stages. At each stage only one input is considered at each
time. Based on this input it is decided whether a particular input gives the optimal
solution or not.

Example: Djikstra’s Algorithm

Djikstra's Algorithm is a popular algorithm for finding the shortest path using Greedy method.
This algorithm is called single source shortest path algorithm.

In this algorithm, for a given vertex called source, the shortest path to all other vertices is
obtained.
16 | P a g e

In this algorithm the main focus is not to find only one single path but to find the shortest paths
from any vertex to all other remaining vertices.

This algorithm is applicable to graphs with non-negative weights only.

Consider a weighted connected graph as given below.

Now we will consider each vertex as a source and with shortest distance from this vertex to
every other remaining vertex. Let us start with vertex A.

Source Vertex Distance with other vertices

A A-B, path = 4
A-C, path = 8
A-D, path = ∞
A-E, path = ∞
B B-C, path = 4 + 1 = 5
B-D, path = 4 + 3 = 7
B-E, path = ∞
C C-D, path = 5 + 7 = 12
C-E, path = 5 + 3 = 8
D D-E, path = 7 + 8 = 15

But we have one shortest distance obtained from A to E and that is A – B – C – D – E with path
length = 4 + 1 + 3 = 8. Similarly other shortest paths can be obtained by choosing appropriate
source and destination.

Djikstra's Shortest path algorithm takes O(ElogV + VlogV) time, where E is the number of
edges and V is the number of vertices of a graph.