DSA502MJ: Data Structure and Algorithms

1|P ag e
1. DATA

Definition:
Data refers to raw facts and figures that may or may not have meaning.
By itself, data is not very useful, but when processed, it provides
information.

 Examples of Data:
o Numbers: 10, 25, 50
o Text: "Hello", "India"
o Images, Videos, Audio
o Sensor readings: temperature = 32°C

In programming, data is stored in variables.

Example in Python:

age = 21 # integer data

name = "Gaurav" # string data
marks = 85.5 # float data

2. DATA STRUCTURE

Definition:
A data structure is a way to organize, store, and manage data so that it
can be used efficiently.
Think of data structures as containers or tools to arrange data.
For example:

 A cup is a structure for holding water.

 A bookshelf is a structure for holding books.
 In programming, we have structures to hold numbers, strings, and
objects.

2|P ag e
Types of Data Structures

1. Primitive Data Structures (Basic)

o Integer (int), Float (float), Character (char), Boolean
(true/false).
2. Non-Primitive Data Structures (Advanced)
o Linear Data Structures: Data is arranged in a sequence.
 Array, String, Linked List, Stack, Queue
 Non-Linear Data Structures: Data is arranged
hierarchically. Tree, Graph
o

Example of a List in Python (Linear Data Structure)

# List in Python
numbers = [10, 20, 30, 40, 50]
print(numbers[2]) # Accessing element -> Output: 30

Here, numbers is a data structure (list) that stores multiple integers.

3. ALGORITHM

Definition:
An algorithm is a step-by-step procedure or set of rules to solve a
specific problem.

Think of an algorithm as a recipe:

 If you want to cook pasta, you follow steps:

1. Boil water.
2. Add pasta.
3. Cook for 10 minutes.
4. Drain water.
5. Serve.

3|P ag e
Similarly, in programming, algorithms give steps to solve problems.

Example Algorithm: Find the largest number in a list

1. Start
2. Assume the first number is the largest.
3. Compare with the next number.
4. If the next number is bigger, update the largest.
5. Repeat until the list ends.
6. Output the largest number.
7. Stop

Python Implementation:

numbers = [10, 45, 32, 67, 89, 21]

largest = numbers[0] # Step 2: assume first number is largest

for num in numbers:
if num > largest:
largest = num

print("Largest number is:", largest)

Output:
Largest number is: 89

Key Differences:

Concept Meaning Example

Data Raw facts or values 42, "Hello"
Structure Way of organizing/storing data List [1,2,3]
4|P ag e
 Concept Meaning Example
Algorithm Step-by-step process to solve a problem Find max number

In short:

 Data = Values
 Data Structure = How you organize values
 Algorithm = How you process values

1. DATA

Real-life Analogy:
Think of data as ingredients in a kitchen.

 Flour, sugar, eggs, milk – they are raw items.

 By themselves, they don’t do much.
 But when you organize and process them, you get a cake 🍰.

Example in computing:

 Numbers: 25, 100, 5

 Words: "Apple", "Mango"
 A photo, sound, or temperature value

DATA = Raw material (like rice, wheat, numbers, text)

2. DATA STRUCTURE

Real-life Analogy:
A data structure is like a container that organizes data properly.

 A plate arranges food.

 A cupboard stores clothes.

5|P ag e
  A bookshelf organizes books.

In programming, data structures arrange numbers, strings, and objects.

Diagram Example:

List (like a row of boxes) → [10] [20] [30] [40]

Stack (like plates) → Top -> [plate] [plate] [plate]
Queue (like people in line) → Front -> [A] [B] [C] <- Rear
Tree (like family tree) → Root
/ \
Child Child

3. ALGORITHM

Real-life Analogy:
An algorithm is a recipe or set of instructions you follow to achieve
something.

Example: Making Tea ☕

1. Boil water
2. Add tea leaves
3. Add sugar
4. Add milk
5. Stir and serve

Similarly, in programming, an algorithm is a step-by-step process to

solve a problem.

6|P ag e
Simple Real-life Example of All Three

Problem: You want to find your friend’s phone number from your
contacts.

1. Data:
o The phone numbers stored in your phone (raw values).
2. Data Structure:
o The contact list that stores names and numbers in an
organized way.
3. Algorithm:
o Steps you follow:
 Open contacts
 Search for friend’s name
 Get the phone number
 Call friend

FINAL VISUAL SUMMARY

DATA → Ingredients (sugar, rice, milk)

DATA STRUCTURE → Container (jar, cupboard, shelf) that organizes
items
ALGORITHM → Recipe/Steps (how to use ingredients to make food)

That’s why in computer science:

 Data is the input,

 Data Structure is the way we arrange it,
 Algorithm is the process to solve problems efficiently.

7|P ag e
 1.1 Arrays/List: Introduction & Definition of an Array
An array is a data structure that stores a collection of elements of the
same data type in a single, contiguous block of memory.
Each element is accessed using an index, a unique number that
represents its position in the array, with the first element typically at
index 0.
Arrays allow for efficient management of related data, as they provide a
way to group and access multiple values under a single variable name.
# In Python, we declare Array:-

arr = [ ]

Initialization of Array
Arrays can be initialized in different ways in different languages. Below
are some language-specific array initializations:

# This list will store integer type elements

arr = [1, 2, 3, 4, 5]

8|P ag e
# This list will store character type elements (strings in Python)

arr = ['a', 'b', 'c', 'd', 'e']

# This list will store float type elements

arr = [1.4, 2.0, 24.0, 5.0, 0.0] # All float values

9|P ag e
1.2 Memory Allocation & Indexing

1. Arrays vs Lists in Python

 List (Python Built-in):

o Can store different types of data (int, float, string, objects).
o Dynamic in size (can grow/shrink).
o Implemented as a dynamic array internally.
 Array (Python array module):
o Stores same type of elements (all integers, or all floats, etc).
o More memory-efficient than list.
o Closer to arrays in C/Java.

List Array
Can consist of elements belonging Only consists of elements belonging
to different data types to the same data type
No need to explicitly import a Need to explicitly import the array
module for the declaration module for declaration
Cannot directly handle arithmetic Can directly handle arithmetic
operations operations
Preferred for a shorter sequence of Preferred for a longer sequence of
data items data items
Greater flexibility allows easy
Less flexibility since addition, and
modification (addition, deletion) of
deletion has to be done element-wise
data
The entire list can be printed A loop has to be formed to print or
without any explicit looping access the components of the array
Consume larger memory for easy Comparatively more compact in
addition of elements memory size
10 | P a g e
 List Array
Nested lists can be of variable size Nested arrays has to be of same size.
Can perform direct operations
using functions like:
count() - for counting a particular
element in the list
sort() - sort the complete list
max() - gives maximum of the list
min() - gives minimum of the list
sum() - gives sum of all the
elements in list for integer list Need to import proper modules to
index() - gives first index of the perform these operations.
element specified
append() - adds the element to the
end of the list
remove() - removes the element
specified

No need to import anything to use

these functions.
and many more...
Example:
Example:
import array
my_list = [1, 2, 3, 4]
arr = array.array('i', [1, 2, 3])

11 | P a g e
2. Memory Allocation

Python List

 Each element in a list is a reference (pointer) to an object in

memory.
 Even if the list looks continuous, it internally stores pointers to
objects.

Example:

mylist = [10, 20, 30, 40]

print(id(mylist[0])) # memory address of element 10
print(id(mylist[1])) # memory address of element 20

Memory layout (conceptual):

mylist = [10, 20, 30, 40]

List container (stores pointers):

Index : 0 1 2 3
Addr : 1000 1008 1016 1024 <- points to objects

Objects in memory:
10 -> stored somewhere (say 2000)
20 -> stored somewhere (say 3000)
30 -> stored somewhere (say 4000)
40 -> stored somewhere (say 5000)

So list doesn’t guarantee elements are stored contiguously like C

arrays.

12 | P a g e
Python Array (array module)

import array

arr = array.array('i', [10, 20, 30, 40]) # 'i' means integer

print(arr.buffer_info()) # (address, length)

Memory layout for arrays:

Index : 0 1 2 3
Value : 10 20 30 40
Addr : 2000 2004 2008 2012 (if int = 4 bytes)

3. Indexing

List Indexing

mylist = [10, 20, 30, 40, 50]

print(mylist[0]) # 10
print(mylist[2]) # 30
print(mylist[-1]) # 50 (last element, negative indexing)

Negative indexing in Python means:

mylist[-1] → last element

mylist[-2] → second last element

Array Indexing

import array

arr = array.array('i', [10, 20, 30, 40, 50])

print(arr[0]) # 10

13 | P a g e
print(arr[3]) # 40
print(arr[-1]) # 50

4. Address Calculation (For Arrays)

Formula:

Address of element[i] = Base address + (i × size of each element)

Example:
If arr = [10,20,30,40], base address = 2000, each int = 4 bytes:

 arr[0] = 2000 + (0×4) = 2000

 arr[1] = 2000 + (1×4) = 2004
 arr[2] = 2000 + (2×4) = 2008
 arr[3] = 2000 + (3×4) = 2012

Key Takeaways:

 Lists = flexible, store mixed data, internally store references.

 Arrays = memory-efficient, store same type, contiguous memory.
 Indexing = accessing elements via position.
 Negative indexing works in both lists & arrays in Python.

14 | P a g e
1.3 One-Dimensional (1-D) Arrays

One Dimensional Array:

 It is a list of the variable of similar data types.

 It allows random access and all the elements can be accessed with
the help of their index.

 The size of the array is fixed.

 For a dynamically sized array, vector can be used in C++.

 Representation of 1D array:

Common Operations

(A) Traversal (access each element)

numbers = [10, 20, 30, 40, 50]

for num in numbers:

print(num, end=" ")

Output:

15 | P a g e
10 20 30 40 50

(B) Insertion
numbers = [10, 20, 30]
numbers.append(40) # insert at end
numbers.insert(1, 15) # insert at index 1
print(numbers)

Output:
[10, 15, 20, 30, 40]

(C) Deletion
numbers = [10, 20, 30, 40]
numbers.remove(20) # delete by value
del numbers[2] # delete by index
print(numbers)

Output:

[10, 40]

(D) Searching
numbers = [10, 20, 30, 40]
print(30 in numbers) # True
print(numbers.index(40)) # 3 (position)

(E) Updating
numbers = [10, 20, 30, 40]
numbers[2] = 99 # update element at index 2
print(numbers)

Output:
16 | P a g e
[10, 20, 99, 40]

2. Two-Dimensional (2-D) Arrays

A 2-D array/list is like a table (matrix) with rows and columns.
Two Dimensional Array:
 It is a list of lists of the variable of the same data type.

 It also allows random access and all the elements can be accessed
with the help of their index.

 It can also be seen as a collection of 1D arrays. It is also known as

the Matrix.

 Its dimension can be increased from 2 to 3 and 4 so on.

 They all are referred to as a multi-dimension array.

 The most common multidimensional array is a 2D array.

 Representation of 2 D array:

17 | P a g e
Example:

matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

Conceptual visualization:

Row 0 → [1, 2, 3]
Row 1 → [4, 5, 6]
Row 2 → [7, 8, 9]

Common Operations

(A) Traversal
matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

for row in matrix:

for val in row:
print(val, end=" ")
print()

Output:
123
456
789

18 | P a g e
(B) Insertion
matrix = [[1, 2], [3, 4]]
matrix.append([5, 6]) # add new row
matrix[0].append(9) # add new element to row 0
print(matrix)

Output:
[[1, 2, 9], [3, 4], [5, 6]]

(C) Deletion
matrix = [[1, 2, 3], [4, 5, 6]]
del matrix[1][2] # delete element (row=1, col=2)
print(matrix)

Output:
[[1, 2, 3], [4, 5]]

(D) Searching
matrix = [[1, 2, 3],
[4, 5, 6]]

found = False
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 5:
print(f"Found at ({i}, {j})")
found = True

Output:

Found at (1, 1)
19 | P a g e
(E) Updating
matrix = [[1, 2, 3],
[4, 5, 6]]

matrix[0][1] = 99 # update row 0, col 1

print(matrix)

Output:
[[1, 99, 3], [4, 5, 6]]

3. Summary Table

Operation 1-D Array/List 2-D Array/List

Traversal Loop over elements Nested loop over rows & columns

Insertion append(), insert() Add row or add element inside a row

Deletion remove(), del Delete row/element using del

Searching in, index() Nested loop to find element

Updating list[i] = val matrix[i][j] = val

So in short:

 1-D lists/arrays → Linear sequence (like a line of lockers).

 2-D lists/arrays → Matrix (like a school timetable).
 Operations are similar, but 2-D needs nested loops.

20 | P a g e
Difference Table:

One Dimension
Basis Two Dimension Array
Array
Store a single list of
Store a 'list of lists' of the
Definition the element of a
element of a similar data type.
similar data type.
Represent multiple data items as
Representatio Represent multiple
a table consisting of rows and
n data items as a list.
columns.
The declaration varies
for different The declaration varies for
programming different programming
language: language:

1. For C++, 1. For C++,

datatype datatype
Declaration variable_name[r variable_name[row][colu
ow] mn]
2. For Java, 2. For Java,
datatype [] datatype [][]
variable_name= variable_name= new
new datatype[row][column]
datatype[row]

Dimension One Two

size of(datatype of the size of(datatype of the variable
Size(bytes) variable of the array) * of the array)* the number of
size of the array rows* the number of columns.
Address Address of a[index] is Address of a[i][j] can be

21 | P a g e
 One Dimension
Basis Two Dimension Array
Array
calculation. equal to (base calculated in two ways row-
Address+ Size of each major and column-major
element of array *
index). 1. Column Major: Base
Address + Size of each
element (number of
rows(j-lower bound of the
column)+(i-lower bound
of the rows))

2. Row Major: Base

Address + Size of each
element (number of
columns(i-lower bound of
the row)+(j-lower bound
of the column))

int arr[5]; //an array int arr[2][5]; //an array with

with one row and five two rows and five columns will
columns will be be created.
Example
created. a b c d e
{a , b , c , d , e} f g h i j

22 | P a g e
1.4 Applications of Array Data Structure:

Applications of Arrays:

 2D Arrays are used to implement matrices.

 Arrays can be used to implement various data structures like a

heap, stack, queue, etc.

 They allow random access.

 They are cache-friendly.

1. 5 What is a Sparse Matrix?

A sparse matrix is a matrix in which most of the elements are 0
(empty).

 Storing all zeros wastes memory.

 Instead, we only store the non-zero elements along with their row
and column index.

Example (Normal Matrix):

5 × 5 matrix:

0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
0 0 0 0 0

Here, out of 25 elements, only 6 are non-zero.

Storing 25 elements is wasteful → instead we store only the non-zero
ones.

23 | P a g e
2. Representation of Sparse Matrix

We can use 3-tuple form (row, column, value).

For the above example:

Row Col Val

0 2 3
0 4 4
1 2 5
1 3 7
3 1 2
3 2 6

This saves memory

3. Sparse Matrix using Array in Python

# Normal matrix
matrix = [
[0, 0, 3, 0, 4],
[0, 0, 5, 7, 0],
[0, 0, 0, 0, 0],
[0, 2, 6, 0, 0],
[0, 0, 0, 0, 0]
]

# Sparse matrix representation using 3-tuple

sparse = []

rows = len(matrix)
cols = len(matrix[0])

for i in range(rows):

24 | P a g e
 for j in range(cols):
if matrix[i][j] != 0:
sparse.append([i, j, matrix[i][j]])

print("Sparse Matrix Representation (row, col, value):")

for row in sparse:
print(row)

Output:
Sparse Matrix Representation (row, col, value):
[0, 2, 3]
[0, 4, 4]
[1, 2, 5]
[1, 3, 7]
[3, 1, 2]
[3, 2, 6]

4. Advantages of Sparse Matrix Representation

1. Memory Efficient → Stores only non-zero elements.
2. Faster Computations → Matrix operations (addition,
multiplication) skip zeros.

6. Summary
 Normal matrix wastes memory if too many zeros.
 Sparse matrix stores only (row, col, value) in an array.
 Saves space and is widely used in graphs, AI, and scientific
computing.

25 | P a g e
1.6 String manipulation using arrays

1. Why Strings as Arrays?

 In programming, a string is basically an array of characters.

 Example:
 "HELLO"
 Index: 0 1 2 3 4
 Char : H E L L O
 So, string manipulation = operations on arrays of characters.

2. Basic String Manipulations (using arrays)

(A) Traversal (Access each character)

string = "HELLO"

for i in range(len(string)):
print(f"Index {i}: {string[i]}")

Output:

Index 0: H
Index 1: E
Index 2: L
Index 3: L
Index 4: O

26 | P a g e
(B) Concatenation (Joining two arrays of characters)

str1 = "Hello"
str2 = "World"

result = str1 + " " + str2

print(result)

Output:
Hello World

(c) Deletion (Remove a character)

string = "Helllo"
char_array = list(string)

char_array.remove("l") # removes first 'l'

new_string = "".join(char_array)
print(new_string)

Output:
Hello

(F) Searching (Find index of a character)

string = "Programming"
print(string.index("g")) # first occurrence of 'g'
print("z" in string) # check if 'z' exists

Output:

27 | P a g e
3
False

(G) Updating (Replace character)

string = "Jxva"
char_array = list(string)

char_array[1] = "a" # replace 'x' with 'a'

new_string = "".join(char_array)
print(new_string)

Output:

Java

3. Advanced Manipulations

Reverse a String

string = "Python"
rev = string[::-1]
print(rev)

Output:
nohtyP

28 | P a g e
Count Frequency of Characters

string = "datastructure"
freq = {}

for ch in string:
freq[ch] = freq.get(ch, 0) + 1

print(freq)

Output:

{'d': 1, 'a': 2, 't': 3, 's': 1, 'r': 2, 'u': 1, 'c': 1, 'e': 1}

Summary:
 Strings can be treated as arrays of characters.
 Operations: Traversal, Concatenation, Substring, Insertion,
Deletion, Searching, Updating, Reversing, Palindrome.
 In Python, since strings are immutable, we often convert them to
character arrays (lists) for manipulation.

29 | P a g e