Data abstraction is the programming process of creating a data type, usually a class, that hides the details of the
data representation in order to make the data type easier to work with.
Row-major OrderingIn row-major ordering, elements are stored row by row. The address of an element [i,j][i, j][i,j] can be
computed using the formula: Address(i,j)=Base Address+((i×Number of Columns)+j)×Element Size\text{Address}(i, j) = \
text{Base Address} + \left( (i \times \text{Number of Columns}) + j \right) \times \text{Element
Size}Address(i,j)=Base Address+((i×Number of Columns)+j)×Element Size
Column-major OrderingIn column-major ordering, elements are stored column by column. The address of an element [i,j]
[i, j][i,j] can be computed using the formula: Address(i,j)=Base Address+((j×Number of Rows)+i)×Element Size\
text{Address}(i, j) = \text{Base Address} + \left( (j \times \text{Number of Rows}) + i \right) \times \text{Element
Size}Address(i,j)=Base Address+((j×Number of Rows)+i)×Element Size
Operation Principle of Quick Sort
1. Divide: Choose a "pivot" element from the array. The pivot can be any element, but common choices are the first
element, the last element, or the middle element.
2. Partition: Rearrange the elements in the array such that all elements less than the pivot are on the left side of the
pivot, and all elements greater than the pivot are on the right side. The pivot element is now in its correct sorted
position.
3. Conquer :Apply the process recursively to the left and right sub-arrays.
4. Example
Consider an example array: 34,7,23,32,5,6234, 7, 23, 32, 5, 6234,7,23,32,5,62
Step-by-Step Execution
1. Initial Array:
[34,7,23,32,5,62][34, 7, 23, 32, 5, 62][34,7,23,32,5,62]
2. Choose a Pivot: Let’s choose the last element as the pivot. Thus, the pivot is 626262.
3. Partitioning:
o We start with two pointers: one at the beginning of the array (left) and one at the end (right).
o We move elements smaller than the pivot to the left and elements larger than the pivot to the right.
o Since 626262 is already greater than all elements, no swaps are needed in this pass.
o After partitioning, the array remains: [34,7,23,32,5,62][34, 7, 23, 32, 5, 62][34,7,23,32,5,62]
o The pivot 626262 is now in its correct position.
4. Recursively Apply Quick Sort to Sub-arrays:
o Left Sub-array: [34,7,23,32,5][34, 7, 23, 32, 5][34,7,23,32,5]
o Right Sub-array: [][][] (empty)
5. Choose Pivot for Left Sub-array: Let’s choose 555 (last element of the left sub-array) as the pivot.
6. Partitioning the Left Sub-array:
o Initial Left Sub-array: [34,7,23,32,5][34, 7, 23, 32, 5][34,7,23,32,5]
o After partitioning around pivot 555: [5,7,23,32,34][5, 7, 23, 32, 34][5,7,23,32,34]
o The pivot 555 is now in its correct position.
7. Recursively Apply Quick Sort to the Left Sub-array:
o New Left Sub-array: [5][5][5] (already sorted)
o New Right Sub-array: [7,23,32,34][7, 23, 32, 34][7,23,32,34]
8. Choose Pivot for New Right Sub-array: Let’s choose 343434 as the pivot.
9. Partitioning the New Right Sub-array:
o Initial Right Sub-array: [7,23,32,34][7, 23, 32, 34][7,23,32,34]
o After partitioning around pivot 343434: [7,23,32,34][7, 23, 32, 34][7,23,32,34]
o The pivot 343434 is now in its correct position.
10. Recursively Apply Quick Sort to Sub-arrays:
o Left Sub-array: [7,23,32][7, 23, 32][7,23,32]
o Right Sub-array: [][][] (empty)
11. Choose Pivot for the Sub-array [7,23,32][7, 23, 32][7,23,32]: Let’s choose 323232 as the pivot.
12. Partitioning:
o Initial Sub-array: [7,23,32][7, 23, 32][7,23,32]
o After partitioning around pivot 323232: [7,23,32][7, 23, 32][7,23,32]
o The pivot 323232 is now in its correct position.
13. Final Recursive Calls:
o Left Sub-array: [7,23][7, 23][7,23]
o Right Sub-array: [][][] (empty)
14. Choose Pivot for the Sub-array [7,23][7, 23][7,23]: Let’s choose 232323 as the pivot.
15. Partitioning:
o Initial Sub-array: [7,23][7, 23][7,23]
o After partitioning around pivot 232323: [7,23][7, 23][7,23]
o The pivot 232323 is now in its correct position.
16. Base Case:
o Left Sub-array: [7][7][7] (already sorted)
o Right Sub-array: [][][] (empty)
Final Sorted Array:
[5,7,23,32,34,62][5, 7, 23, 32, 34, 62][5,7,23,32,34,62]
the average time complexity is: T(n)=O(nlogn)T(n) = O(n \log n)T(n)=O(nlogn)
the best-case time complexity is also: T(n)=O(nlogn)T(n) = O(n \log n)T(n)=O(nlogn)
So, the total work done is: T(n)=T(n−1)+O(n)T(n) = T(n-1) + O(n)T(n)=T(n−1)+O(n) This recurrence relation
solves to: T(n)=O(n2)T(n) = O(n^2)T(n)=O(n2)
Advantages Of Linked List:
Dynamic data structure: . So there is no need to give the initial size of the linked list.
No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the
linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-
allocate the memory.
Implementation: Linear data structures like stacks and queues are often easily implemented using a linked
list.
Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list.
There is no need to shift elements after the insertion or deletion of an element only the address present in
the next pointer needs to be updated.
Flexible: This is because the elements in Linked List are not stored in contiguous memory locations
unlike the array.
Efficient for large data: When working with large datasets linked lists play a crucial role as it can grow
and shrink dynamically.
Scalability: Contains the ability to add or remove elements at any position.
Disadvantages Of Linked List:
Memory usage: More memory is required in the linked list as compared to an array. Because in a linked
list, a pointer is also required to store the address of the next element and it requires extra memory for
itself.
Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an
element is not possible in a linked list as in an array by index. For example, for accessing a node at
position n, one has to traverse all the nodes before it.
Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-
linked list, it can be possible as it contains a pointer to the previously connected nodes with each node. For
performing this extra memory is required for the back pointer hence, there is a wastage of memory.
Random Access: Random access is not possible in a linked list due to its dynamic memory allocation .
Lower efficiency at times: For certain operations, such as searching for an element or iterating through
the list, can be slower in a linked list.
Complex implementation: The linked list implementation is more complex when compared to array. It
requires a complex programming understanding.
Difficult to share data: This is because it is not possible to directly access the memory address of an
element in a linked list.
Not suited for small dataset: Cannot provide any significant benefits on small dataset compare to that of
an array.
Algorithm for Insertion at the Beginning of a Singly Linked List
1. Make a new node using the given data.
2. If the linked list’s head is null, set the new node as the linked list’s head and return.
3. Set the new node’s next pointer to the current head of the linked list.
4. Set the linked list’s head to point to the new node.
5. Return.
The basic operations of a queue include:
1. Enqueue: Add an element to the back of the queue.
2. Dequeue: Remove the element at the front of the queue.
3. Peek: Return the element at the front of the queue without removing it.
4. Size: Return the number of elements in the queue.
5. isEmpty: Check if the queue is empty.
Some common applications of Queue data structure :
1. Task Scheduling: Queues can be used to schedule tasks based on priority or the order in which they were
received.
2. Resource Allocation: Queues can be used to manage and allocate resources, such as printers or CPU
processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs, such as data analysis or image
rendering.
4. Message Buffering: Queues can be used to buffer messages in communication systems, such as message
queues in messaging systems or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven systems, such as GUI applications
or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in transportation systems, such as
airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage processes and resources. For example,
a process scheduler might use a queue to manage the order in which processes are executed.
8. Network protocols: Network protocols like TCP and UDP use queues to manage packets that are
transmitted over the network. Queues can help to ensure that packets are delivered in the correct order and
at the appropriate rate.
9. Printer queues :In printing systems, queues are used to manage the order in which print jobs are
processed. Jobs are added to the queue as they are submitted, and the printer processes them in the order
they were received.
10. Web servers: Web servers use queues to manage incoming requests from clients. Requests are added to
the queue as they are received, and they are processed by the server in the order they were received.
11. Breadth-first search algorithm: The breadth-first search algorithm uses a queue to explore nodes in a
graph level-by-level. The algorithm starts at a given node, adds its neighbors to the queue, and then
processes each neighbor in turn.
#include <stdio.h>
// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
int i, j, min, temp;
// One by one move the boundary of the unsorted subarray
for (i = 0; i < n-1; i++) {
// Find the minimum element in the unsorted array
min = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// Swap the found minimum element with the first element
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
int main() {
// Initialize the array
int arr[] = {10, 5, 15, 19, 7, 3};
int n = sizeof(arr) / sizeof(arr[0]);
// Perform selection sort
selectionSort(arr, n);
// Print the sorted array
printf("Sorted array: \n");
printArray(arr, n);
return 0;
A heap is a specialized tree-based data structure that satisfies the heap property. The heap can be classified into two main
types:
1. Max-Heap: In a max-heap, for any given node iii, the value of iii is greater than or equal to the values of its
children. The highest value is at the root of the tree.
2. Min-Heap: In a min-heap, for any given node iii, the value of iii is less than or equal to the values of its children.
The lowest value is at the root of the tree
Max heap Min heap
40 10
/ \ / \
30 15 20 15
/\ /\
10 20 30 40
Construct a min-heap with the following numbers. Show each step. 100,200,30,50,40,500,250,175
30
/ \
40 100
/ \ / \
175 200 500 250
/
50
Evaluate the postfix expression-9-((3*4)+8)/4
o Step 1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
o Step 2: SET PTR = HEAD
o Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
o Step 4: SET PREPTR = PTR
o Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
o Step 6: SET PREPTR -> NEXT = NULL
o Step 7: FREE PTR
o Step 8: EXIT
What is Data Structure?
A data structure is a particular way of organising data in a computer so that it can be used effectively. The idea is to
reduce the space and time complexities of different tasks.
Graph Data Structure is a collection of nodes connected by edges. It’s used to represent relationships between different
entities. Graph algorithms are methods used to manipulate and analyze graphs, solving various problems like finding
the shortest path or detecting cycles.
Basic Operations on Graphs:
Below are the basic operations on the graph:
Insertion of Nodes/Edges in the graph – Insert a node into the graph.
Deletion of Nodes/Edges in the graph – Delete a node from the graph.
Searching on Graphs – Search an entity in the graph.
Traversal of Graphs – Traversing all the nodes in the graph.
Advanced Graph Terminology:
1. Directed Graph (Digraph) :
A Directed Graph consists of nodes (vertices) connected by directed edges (arcs). Each edge has a specific direction, meaning it goes
from one node to another. Directed Graph is a network where information flows in a specific order. Examples include social media
follower relationships, web page links, and transportation routes with one-way streets.
2. Undirected Graph:
In an Undirected Graph, edges have no direction. They simply connect nodes without any inherent order. For example, a social network
where friendships exist between people, or a map of cities connected by roads (where traffic can flow in both directions).
3. Weighted Graph:
Weighted graphs assign numerical values (weights) to edges. These weights represent some property associated with the connection
between nodes. For example, road networks with varying distances between cities, or airline routes with different flight durations, are
examples of weighted graphs.
4. Unweighted Graph:
An unweighted graph has no edge weights. It focuses solely on connectivity between nodes. For example: a simple social network
where friendships exist without any additional information, or a family tree connecting relatives.
Load factor is defined as (m/n) where n is the total size of the hash table and m is the preferred number of entries that can be
inserted before an increment in the size of the underlying data structure is required.
