Fundamental of Data Structures Unit I

Algorithm
An algorithm is a detailed sequence of steps or instructions designed to solve a specific problem or perform a task.
Algorithms are the foundation of programming and computational thinking.

Characteristics of a Good Algorithm:

1. Input: What information or data does the algorithm require?

2. Output: What is the result or goal of the algorithm?
3. Steps: Each step should be precise and unambiguous.
4. Effectiveness: Every operation should be simple enough to be carried out in a finite time.
5. Termination: The algorithm must always finish in a finite number of steps.

Steps to Create an Algorithm:

1. Understand the problem you are solving.

2. Identify inputs and outputs.
3. Break the problem into smaller, logical steps.
4. Define the sequence of steps clearly.
5. Optimize for simplicity and efficiency.

Examples:
2. Algorithm to Find the Largest of Three Numbers
1. Algorithm to Find the Sum of Two Numbers
Problem: Identify the largest number among three inputs.
Problem: Add two numbers and display the result.
Algorithm:
Algorithm:
1. Start.
1. Start Input two numbers, A and B. 2. Input three numbers, A, B, and C.
2. Compute Sum= A + B. 3. If A>B and A>C, print "A is the largest".
3. Output the result Sum. 4. Else, if B>C, print "B is the largest".
4. Stop. 5. Else, print "C is the largest".
6. Stop.

4. Algorithm to Compute the Factorial of a Number

3. Algorithm to Check if a Number is Even or Odd
Problem: Calculate the factorial of a number N.
Problem: Determine if a given number N is even or odd.
Algorithm:
Algorithm:
1. Start.
1. Start. 2. Input N.
2. Input the number N. 3. Initialize Fact=1.
3. If N mod 2 = 0, print "Even". 4. For i=1 to N, do:
4. Otherwise, print "Odd". o Fact=Fact×i.
5. Stop. 5. Output Fact.
6. Stop.

1 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

5. Algorithm to Reverse a Given Number

Problem: Reverse the digits of a number N.

Algorithm:

1. Start.
2. Input N.
3. Initialize Reverse=0.
4. While N>0, do:
o Extract the last digit: Digit=N mod 10.
o Update reverse: Reverse=Reverse×10+Digit.
o Remove the last digit: N=N÷10.
5. Output Reverse.
6. Stop.

Advantages of Using Algorithms:

1. Clear Structure: It helps in logical problem-solving.

2. Optimization: Algorithms can be analyzed for efficiency.
3. Language Independence: An algorithm is not tied to any specific programming language.

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.

For example: 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.

There are mainly three asymptotic notations:

1. Big-O notation
2. Omega notation
3. Theta notation

1. 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.
2 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

Big-O gives the upper bound of a function

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(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.

For any value of n, the running time of an algorithm does not cross the time provided by O(g(n)).

Since it gives the worst-case running time of an algorithm, it is widely used to analyze an algorithm as we are always
interested in the worst-case scenario.

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

Omega gives the lower bound of a function

Ω(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.

For any value of n, the minimum time required by the algorithm is given by Omega Ω(g(n)).

3. 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.
3 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

Theta bounds the function within constants factors

For a function g(n), Θ(g(n)) is given by the relation:

Θ(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.

Table summarizing time complexities for common algorithms:

Algorithm Best Case (Ω) Worst Case (OO) Average Case (Θ)
Linear Search Ω(1 O(n) Θ(n)
Binary Search Ω(1) O(log⁡n) Θ(log⁡n)
Bubble Sort Ω(n) O(n2) Θ(n2)
Merge Sort Ω(nlog⁡n) O(nlog⁡n) Θ(nlog⁡n)
Insertion Sort Ω(n) O(n2) Θ(n2)

Data Structures
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.

Depending on your requirement and project, it is important to choose the right data structure for your project. For
example, if you want to store data sequentially in the memory, then you can go for the Array data structure.

Data Structure Representation

4 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Types of Data Structure

Basically, data structures are divided into two categories:

 Linear data structure

 Non-linear data structure

Linear data structures:

In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in
particular order, they are easy to implement.

However, when the complexity of the program increases, the linear data structures might not be the best choice because of
operational complexities.

Popular linear data structures are:

1. Array Data Structure

In an array, elements in memory are arranged in continuous memory. All the elements of an array are of the same type.
And, the type of elements that can be stored in the form of arrays is determined by the programming language.

2. Stack Data Structure

In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be
removed first.

It works just like a pile of plates where the last plate kept on the pile will be removed first.

3. Queue Data Structure

5 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Unlike stack, the queue data structure works in the FIFO principle where first element stored in the queue will be removed
first.

It works just like a queue of people in the ticket counter where first person on the queue will get the ticket first.

4. Linked List Data Structure

In linked list data structure, data elements are connected through a series of nodes. And, each node contains the data items
and address to the next node.

Non linear data structures:

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead they are arranged in a
hierarchical manner where one element will be connected to one or more elements.

Non-linear data structures are further divided into graph and tree based data structures.

1. Graph Data Structure

In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges.

Popular Graph Based Data Structures:

 Spanning Tree and Minimum Spanning Tree

 Strongly Connected Components
 Adjacency Matrix
 Adjacency List ect..

2. Trees Data Structure

Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one
edge between two vertices.

Popular Tree based Data Structure

 Binary Tree
 Binary Search Tree
 AVL Tree etc..

Basic Operations in Data Structures

a. Traversal

 Definition: Visiting and processing each element of the data structure exactly once.
 Purpose: To display data, search for elements, or perform other operations.
 Example:
o In an array: Iterating through all elements.
o In a tree: Preorder, Inorder, or Postorder traversal.

b. Insertion

 Definition: Adding an element to the data structure.

 Purpose: Dynamically grow the data structure by adding new data.
6 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

 Complexity:
o Array: O(1) for appending; O(n) for inserting at a specific position.
o Linked List: O(1) if inserting at the beginning.
o Binary Search Tree: O(log⁡n) for balanced trees.

c. Deletion

 Definition: Removing an element from the data structure.

 Purpose: Dynamically shrink the data structure by removing unwanted data.
 Complexity:
o Array: O(n) (due to shifting elements).
o Linked List: O(1) if the element's location is known.
o Binary Search Tree: O(log⁡n) for balanced trees.

d. Searching

 Definition: Finding an element in the data structure that meets a certain criterion.
 Purpose: To locate data for further processing.
 Complexity:
o Array: O(n) (linear search), O(log⁡n) (binary search for sorted arrays).
o Binary Search Tree: O(log⁡n) for balanced trees.

e. Updating

 Definition: Modifying the value of an existing element in the data structure.

 Purpose: Reflect changes in the stored data.
 Complexity:
o Array: O(1) (direct access using an index).
o Linked List: O(n) (traversal required to locate the element).

f. Sorting

 Definition: Sorting is a fundamental operation in computer science where elements in a data structure
(array, list, etc.) are rearranged into a specific order, typically ascending or descending.
 Purpose: Efficiency, Data Organization, Preprocessing Step.
 Complexity: Quick Sort (O(nlog⁡n)), Merge Sort (O(nlog⁡n)).

Linear Vs Non-linear Data Structures

Now that we know about linear and non-linear data structures, let's see the major differences between them.

Linear Data Structures Non Linear Data Structures

The data items are arranged in sequential order, one The data items are arranged in non-sequential
after the other. order (hierarchical manner).
All the items are present on the single layer. The data items are present at different layers.
It can be traversed on a single run. That is, if we It requires multiple runs. That is, if we start from
start from the first element, we can traverse all the the first element it might not be possible to
elements sequentially in a single pass. traverse all the elements in a single pass.
The memory utilization is not efficient. Different structures utilize memory in different
efficient ways depending on the need.
The time complexity increase with the data size. Time complexity remains the same.
Example: Arrays, Stack, Queue Example: Tree, Graph, Map

7 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Arrays
Definition: An array in C is a collection of elements of the same data type stored in contiguous memory locations. Each
element is accessed using an index.

Declaration:

To declare an array, you specify the data type, the array name, and the number of elements in square brackets.

int numbers[10]; // This declaration creates an array named `numbers` that can hold 10 integers.

Initialization:

Arrays can be initialized at the time of declaration or later.

Initialization at Declaration:

int numbers[5] = {1, 2, 3, 4, 5};

Initialization Later:

numbers[0] = 1;

numbers[1] = 2;

numbers[2] = 3;

numbers[3] = 4;

numbers[4] = 5;

Operations on Arrays:

The array data structure supports a variety of operations, such as inserting, deleting, traversing, searching, updating, and
sorting elements.

1. Traversal

Definition: Accessing each element of the array one by one to perform a specific operation (e.g., display, sum).

Algorithm:
Start
1. For `i = 0` to `n-1`:
a. Access and process `arr[i]`.
2. End loop.
Stop
8 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

C Program:
#include <stdio.h>
void traverse(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
traverse(arr, n);
return 0;
}

2. Insertion

Definition: Add a new element at a specific index.

Algorithm:
Start
1. If the array is full, output "Overflow" and Stop.
2. Shift elements from `pos` to `n-1` one position to the right.
3. Insert the new element at `arr[pos]`.
4. Increment the size of the array.
Stop

C Program:
#include <stdio.h>
void insert(int arr[], int *n, int pos, int element) {
for (int i = *n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = element;
(*n)++;
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5, pos = 2, element = 25;
insert(arr, &n, pos, element);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

3. Deletion

Definition: Remove an element from a specific index.

9 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Algorithm:
Start
1. If the array is empty, output "Underflow" and Stop.
2. Shift elements from `pos+1` to `n-1` one position to the left.
3. Decrement the size of the array.
Stop

C Program:
#include <stdio.h>
void delete(int arr[], int *n, int pos) {
for (int i = pos; i < *n - 1; i++) {
arr[i] = arr[i + 1];
}
(*n)--;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, pos = 2;
delete(arr, &n, pos);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

4. Searching

Definition: Find the index of a specific element in the array.

Algorithm (Linear Search):

Start
1. For `i = 0` to `n-1`:
a. If `arr[i] == target`, output `i` and Stop.
2. If the element is not found, output -1.
Stop

C Program:
#include <stdio.h>
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, target = 30;
int result = search(arr, n, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
10 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

printf("Element not found\n");

}
return 0;
}

5. Updating

Definition: Replace the value of an element at a specific index.

Algorithm:
Start
1. Set `arr[pos] = new_value`.
2. Output the updated array.
Stop

C Program:
#include <stdio.h>
void update(int arr[], int n, int pos, int new_value) {
if (pos >= 0 && pos < n) {
arr[pos] = new_value;
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, pos = 2, new_value = 35;
update(arr, n, pos, new_value);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

6. Sorting

Definition: Rearrange elements in ascending or descending order.

Algorithm (Bubble Sort):

Start
1. For `i = 0` to `n-1`:
a. For `j = 0` to `n-i-2`:
i. If `arr[j] > arr[j+1]`, swap `arr[j]` and `arr[j+1]`.
2. End loops.
3. Output the sorted array.
Stop

C Program:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
11 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

arr[j] = arr[j + 1];

arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {50, 30, 20, 10, 40};
int n = 5;
bubbleSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Types of Arrays

One-dimensional Arrays:

A linear sequence of elements.

int one_dimensional[5] = {1, 2, 3, 4, 5};

Two-dimensional Arrays:

Arrays with rows and columns, often used to represent matrices.

int two_dimensional[3][3] = {

{1, 2, 3},

{4, 5, 6},

{7, 8, 9}

};

Accessing elements:

12 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

int value = two_dimensional[1][2]; // Accesses element at row 1, column 2

Arrays as Abstract Data Types (ADT)

As an ADT, arrays encapsulate:

-Data: The actual elements stored in the array.

-Operations: Procedures to manipulate the array, like accessing, inserting, deleting, and updating elements.

-Structure: The organization of elements in memory.

Representation of Linear Arrays in Memory

Arrays are stored in contiguous memory locations. The address of each element can be calculated using the base address
and the element's index.

Address Calculation:

Address of A[i]=Base Address+(i×Size of Each Element)

Example:

If `A` is an integer array starting at memory address `1000`, and each integer takes 4 bytes, the address of `A[3]` is:

Address of A[3]=1000+(3×4)=1012

Complete Example in C

Here is a complete program demonstrating declaration, initialization, and basic operations on a one-dimensional array:

#include <stdio.h>

int main() {

// Declaration and initialization

int numbers[10] = {1, 2, 3, 4, 5};

// Traversal

printf("Array elements: ");

for(int i = 0; i < 5; i++) {

printf("%d ", numbers[i]);

printf("\n");

// Insertion
13 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

int size = 5;

int index = 2;

int value = 10;

for(int i = size; i > index; i--) {

numbers[i] = numbers[i - 1];

numbers[index] = value;

size++;

printf("After insertion: ");

for(int i = 0; i < size; i++) {

printf("%d ", numbers[i]);

printf("\n");

// Deletion

for(int i = index; i < size - 1; i++)

{ numbers[i] = numbers[i + 1]; }

size--;

printf("After deletion: ");

for(int i = 0; i < size; i++) {

printf("%d ", numbers[i]);

printf("\n");

// Searching

int search_value = 3;

int found = -1;

for(int i = 0; i < size; i++) {

if(numbers[i] == search_value) {

found = i;

14 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

break;

} }

if(found != -1) {

printf("Element found at index %d\n", found);

} else {

printf("Element not found\n");

// Updating

numbers[2] = 7; // Update value at index 2

printf("After updating: ");

for(int i = 0; i < size; i++) {

printf("%d ", numbers[i]);

printf("\n");

return 0;

This program demonstrates the basic concepts and operations on arrays in C, providing a clear understanding of how
arrays function and are managed in memory.

Multidimensional Arrays

Multidimensional arrays in C can be thought of as arrays of arrays. The most common type is the two-dimensional array,
which can be used to represent matrices.

Two-dimensional Arrays

Declaration and Initialization:

15 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

#include <stdio.h>

int main() {

int matrix[3][3] = {

{1, 2, 3},

{4, 5, 6},

{7, 8, 9}

};

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

printf("%d ", matrix[i][j]);

printf("\n");

return 0;

Accessing Elements:

int value = matrix[1][2]; // Accesses element at row 1, column 2 (value 6)

Representation of Multidimensional Arrays in Memory

Multidimensional arrays are stored in memory in either row-major or column-major order. C uses row-major order,
where elements of each row are stored in consecutive memory locations.

For a two-dimensional array `matrix[3][3]`, the memory layout would be:

matrix[0][0], matrix[0][1], matrix[0][2], matrix[1][0], matrix[1][1], matrix[1][2], matrix[2][0], matrix[2][1],

matrix[2][2]

Address Calculation:

For a two-dimensional array `A[m][n]`, the address of an element `A[i][j]` in row-major order is calculated as:

Address of A[i][j]=Base Address+((i×n)+j)×Size of Each Element

Example:

If `A` is a 3x3 integer array starting at memory address `1000`, and each integer takes 4 bytes, the address of `A[1][2]`
is:

Address of A[1][2]=1000+((1×3)+2)×4=1000+(3+2)×4=1000+20=1020

16 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Matrix

A matrix is a two-dimensional array of numbers arranged in rows and columns. Matrices are often denoted as A=[ij],
where i j is the element in the i-th row and j-th column.

Matrix Dimensions

The size of a matrix is denoted as m×n:

 m: Number of rows.
 n: Number of columns.

Matrix operations
1. Matrix Addition

Mathematical Description:

Matrix addition combines two matrices A and B of the same size (m×n) by adding their corresponding elements:

Algorithm:

1. Check if the dimensions of A and B are the same.

2. Initialize an empty matrix C of size m×n.
3. For each element i,j in the matrices:
o Add A[i][j] and B[i][j].
o Store the result in C[i][j].
4. Return the resulting matrix C.

Algorithm in Pseudocode:
MatrixAddition(A, B, C, rows, cols):
if size(A) != size(B):
print "Matrices must have the same dimensions"
return
for i = 0 to rows - 1:
for j = 0 to cols - 1:
C[i][j] = A[i][j] + B[i][j]

17 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

C Program:
#include <stdio.h>

void addMatrices(int rows, int cols, int A[rows][cols], int B[rows][cols], int C[rows][cols]) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
}

int main() {
int A[2][2] = {{1, 2}, {3, 4}};
int B[2][2] = {{5, 6}, {7, 8}};
int C[2][2];

addMatrices(2, 2, A, B, C);
printf("Result of Matrix Addition:\n");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", C[i][j]);
}
printf("\n");
}

return 0;
}

2. Matrix Subtraction

Mathematical Description:

Matrix subtraction subtracts corresponding elements of two matrices A and B:

Algorithm:

1. Check dimensions of A and B.

2. Initialize C with the same dimensions as A and B.
3. Subtract B[i][j] from A[i][j], and store the result in C[i][j].
4. Return C.

Pseudocode:
MatrixSubtraction(A, B, C, rows, cols):
if size(A) != size(B):
print "Matrices must have the same dimensions"
18 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru
Fundamental of Data Structures Unit I

return
for i = 0 to rows - 1:
for j = 0 to cols - 1:
C[i][j] = A[i][j] - B[i][j]

C Program:
#include <stdio.h>

void subtractMatrices(int rows, int cols, int A[rows][cols], int B[rows][cols], int C[rows][cols]) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
}

int main() {
int A[2][2] = {{1, 2}, {3, 4}};
int B[2][2] = {{5, 6}, {7, 8}};
int C[2][2];

subtractMatrices(2, 2, A, B, C);

printf("Result of Matrix Addition:\n");

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", C[i][j]);
}
printf("\n");
}

return 0;
}

3. Matrix Multiplication

Mathematical Description:

Matrix multiplication involves multiplying rows of the first matrix with columns of the second. For matrices A(m×n)
and B(n×p), the resulting matrix C will have dimensions m×p. Each element C[i][j] is calculated as:

19 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Algorithm:

1. Ensure c1c1 (columns of A) equals r2 (rows of B).

2. Initialize matrix C of dimensions r1×c2 with zeros.
3. For each row ii of A and column jj of B:
o Compute the dot product of i-th row of A and j-th column of B.

Pseudocode:
MatrixMultiplication(A, B, C, r1, c1, c2):
if c1 != r2:
print "Invalid dimensions for multiplication"
return
for i = 0 to r1 - 1:
for j = 0 to c2 - 1:
C[i][j] = 0
for k = 0 to c1 - 1:
C[i][j] += A[i][k] * B[k][j]

C Program:
#include <stdio.h>

void multiplyMatrices(int r1, int c1, int c2, int A[r1][c1], int B[c1][c2], int C[r1][c2]) {
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
C[i][j] = 0;
for (int k = 0; k < c1; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}

int main() {
int A[2][2] = {{1, 2}, {3, 4}};
int B[2][2] = {{5, 6}, {7, 8}};
int C[2][2];

multiplyMatrices(2, 2, A, B, C);

printf("Result of Matrix Addition:\n");

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", C[i][j]);
}
printf("\n");
}

return 0;
}

20 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

4. Transpose of a Matrix

Description:

The transpose of a matrix A is obtained by swapping its rows and columns. For a matrix A with dimensions m×n, its
transpose AT will have dimensions n×m. Mathematically:

Algorithm:

1. Initialize a new matrix T of size n×m.

2. For each element A[i][j]
o Set T[j][i]=A[i][j].
3. Return the resulting transposed matrix T.

Pseudocode:
MatrixTranspose(A, T, rows, cols):
for i = 0 to rows - 1:
for j = 0 to cols - 1:
T[j][i] = A[i][j]

C Program:
#include <stdio.h>

void transposeMatrix(int rows, int cols, int A[rows][cols], int T[cols][rows]) {

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
T[j][i] = A[i][j];
}
}
}

int main() {
int A[2][3] = {{1, 2, 3}, {4, 5, 6}};
int T[3][2];

transposeMatrix(2, 3, A, T);

printf("Transpose of Matrix:\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", T[i][j]);
}
printf("\n");
}

return 0;
}

21 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

5. Determinant of a 2×2 Matrix

Description:

The determinant of a 2×2 matrix A is a scalar value that can be computed as:

Algorithm:

1. Check if the matrix is 2×2.

2. Compute: determinant=A[0][0]⋅A[1][1]−A[0][1]⋅A[1][0].
3. Return the determinant.

Pseudocode:
DeterminantOf2x2Matrix(A):
return A[0][0] * A[1][1] - A[0][1] * A[1][0]

C Program:
#include <stdio.h>

int determinantOf2x2Matrix(int A[2][2]) {

return A[0][0] * A[1][1] - A[0][1] * A[1][0];
}

int main() {
int A[2][2] = {{1, 2}, {3, 4}};
int det = determinantOf2x2Matrix(A);

printf("Determinant of the matrix: %d\n", det);

return 0;
}

6. Matrix Scalar Multiplication

Description:

Scalar multiplication scales each element of a matrix A by a scalar k. For each element:

22 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru

Fundamental of Data Structures Unit I

Algorithm:

1. Initialize an empty matrix CC of the same size as AA.

2. Multiply each element A[i][j] by k and store it in C[i][j].

Pseudocode:
ScalarMultiplication(A, C, rows, cols, k):
for i = 0 to rows - 1:
for j = 0 to cols - 1:
C[i][j] = k * A[i][j]

C Program:
#include <stdio.h>

void scalarMultiplyMatrix(int rows, int cols, int A[rows][cols], int k, int C[rows][cols]) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
C[i][j] = k * A[i][j];
}
}
}

int main() {
int A[2][2] = {{1, 2}, {3, 4}};
int C[2][2];
int k = 3;

scalarMultiplyMatrix(2, 2, A, k, C);

printf("Result of Scalar Multiplication:\n");

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", C[i][j]);
}
printf("\n");
}

return 0;
}

23 Prof. Venkoba Kutagamari, Assistant Professor, SNPSU, Bengaluru