ASSIGNMENT – 1

Q-1) What is Data Structure? Write Definitions, Operations, and Applications of data structures.
ANS.
1. A data structure is a specialized format for organizing, processing, and storing
data in a computer’s memory. It enables efficient access and manipulation of data,
allowing programmers to perform specific tasks more effectively. In simpler terms,
data structures provide a way to arrange and manage data so that it can be accessed
and updated efficiently.

2. some common operations on data structures are :

➢ Traversing:
• Traversing a data structure means visiting each element stored
within it.
• It can be done with any type of data structure.
• Example: Traversing an array, stack, queue, or linked list.
➢ Searching:
• Searching involves finding a specific element within a data
structure.
• It can be performed on arrays, linked lists, trees, graphs, etc.
• Example: Searching for an element in an array, stack, queue, or
linked list.
➢ Insertion:
• Insertion means adding an element to a data structure.
• It is a common operation across all data structures.
• Example: Adding an element to an array, stack, queue, etc.
➢ Deletion:
• Deletion involves removing data elements from a data structure.
• It can be performed on arrays, linked lists, trees, etc.

3. Applications of Data Structures:

• Arrays: Used in databases, spreadsheets, and scientific
simulations. Real-life examples include storing student grades, stock
prices, and temperature data.
• Linked Lists: Applied in task scheduling, memory management, and
symbol tables. Real-world examples include browser history, music
playlists, and train schedules.
• Stacks: Used for function calls, expression evaluation, and
backtracking. Real-life applications include undo functionality in
software and browser navigation history.
• Queues: Used in print spooling, task scheduling, and network packet
handling. Think of waiting lines at a ticket counter or a call center.
 • Trees: Used for hierarchical data representation (e.g., file systems,
XML parsing). Real-world examples include website navigation menus
and family trees.
• Graphs: Applied in social networks, recommendation systems, and
route planning. Think of Facebook connections or finding the shortest
path on a map.

Q-2) : Discuss Abstract Data Types, Algorithm with Definition.

ANS)
An Abstract Data Type (ADT) is a mathematical model that defines a type of
data along with the operations that can be performed on that data. Unlike built-in data types
(such as integers or floating-point numbers), ADTs allow us to encapsulate data and its
associated behaviors into a single unit. Here are some key points about ADTs:

1. Abstraction:
o ADTs provide a level of abstraction by hiding the implementation
details.
o Users interact with ADTs based on what they can do (operations)
rather than how they are implemented.
o Think of ADTs as black boxes that expose essential functionality while
concealing the inner workings.
2. Essentials of ADTs:
o An ADT consists of:
▪ A set of values (the data it can hold).
▪ A set of operations (functions/methods) that can be performed
on those values.
o The ADT definition does not specify how these operations are
implemented or how data is organized in memory.
3. Examples of ADTs:
o Let’s explore a few common ADTs:
o List ADT:
▪ Represents a collection of elements (values) stored in a
sequence.
▪ Operations include:
▪ get(): Retrieve an element from any position.
▪ insert(): Add an element at any position.
▪ remove(): Remove the first occurrence of an element.
▪ size(): Get the number of elements.
▪ And more…
o Stack ADT:
▪ Follows the Last-In-First-Out (LIFO) principle.
▪ Operations include:
▪ push(): Add an element to the top.
▪ pop(): Remove the top element.
▪ isEmpty(): Check if the stack is empty.
▪ And more…
o Queue ADT:
▪ Follows the First-In-First-Out (FIFO) principle.
 ▪Operations include:
▪ enqueue(): Add an element to the rear.
▪ dequeue(): Remove the front element.
▪ isEmpty(): Check if the queue is empty.
▪ And more…
4. Why Use ADTs?
o ADTs provide a high-level view of data structures.
o They allow us to reason about algorithms and programs without
getting bogged down in implementation details.
o ADTs are essential for designing efficient algorithms and building
robust software systems.

Algorithms

• An algorithm is a step-by-step procedure or set of rules for solving a specific

problem.
• Algorithms operate on data structures (including ADTs) to perform tasks like
searching, sorting, or transforming data.
• Good algorithms are efficient, correct, and well-defined.

Q-3) : Write Short note on : Introduction to Complexity, Big O notation, Time

and Space trade-offs.
ANS)
1. Complexity Analysis

• Complexity analysis is the study of how the performance of an algorithm or

program changes with respect to its input size.
• It helps us understand how much time and memory an algorithm requires as
the problem size grows.
• Complexity analysis guides us in choosing efficient algorithms for solving
real-world problems.

2. Big O Notation

• Big O notation is a mathematical way to describe the limiting behavior of a

function as its input tends toward a particular value or infinity.
• It characterizes the efficiency of an algorithm by analyzing how its runtime or
space requirements grow relative to the input size.
• Key points about Big O notation:
o Represents the worst-case behavior of an algorithm.
o Provides an upper bound on the time or space complexity.
o Common notations include:
▪ O(1): Constant time (e.g., accessing an element in an array).
▪ O(n): Linear time (e.g., iterating through an array).
▪ O(n log n): Log-linear time (e.g., efficient sorting algorithms like
merge sort).
▪ O(n^2): Quadratic time (e.g., nested loops).
 o Helps us compare and choose algorithms based on their scalability.

3. Time-Space Trade-Offs

• A time-space trade-off occurs when an algorithm or program balances

increased space usage with decreased time (or vice versa).
• Situations where this trade-off arises:
o Compressed vs. Uncompressed Data:
▪ Compressed data uses less space but may require more time
for decompression.
▪ Uncompressed data uses more space but allows faster access.
o Re-Rendering vs. Stored Images:
▪ Storing pre-rendered images takes more space but reduces
rendering time.
▪ Re-rendering images on demand uses less space but takes
longer.
o Smaller Code vs. Loop Unrolling:
▪ Smaller code occupies less memory but may require more
computation time.
▪ Loop unrolling optimizes execution speed at the cost of binary
size.
o Lookup Tables vs. Recalculation:
▪ Lookup tables reduce computation time but increase memory
usage.
▪ Recalculating values as needed uses less memory but takes
longer.

Q-4) What is Dynamic Memory Allocation ( Malloc, Calloc, Realloc, Free).

ANS)
1. malloc() (Memory Allocation):
o The malloc() function allocates a single large block of memory with
the specified size.
o It returns a pointer of type void*, which can be cast into a pointer of
any data type.
o The allocated memory is uninitialized (contains garbage values).
o Syntax:

ptr = (cast-type*) malloc(byte-size);

o Example:
int* ptr = (int*) malloc(100 * sizeof(int));

This allocates 400 bytes of memory for an array of integers.

2. calloc() (Contiguous Allocation):

o The calloc() function allocates multiple blocks of memory, each of
the specified sizes.
o It initializes the allocated memory to zero (unlike malloc()).
 o Syntax:

ptr = (cast-type*) calloc(num-elements, element-size);

o Example:
int* ptr = (int*) calloc(5, sizeof(int));

This allocates memory for an array of 5 integers, initialized to zero.

3. realloc() (Reallocate Memory):

o The realloc() function changes the size of an already allocated
memory block.
o It can:
▪ Expand the memory block (if more space is needed).
▪ Shrink the memory block (if less space is needed).
o Syntax:

ptr = realloc(ptr, new-size);

o Example:
ptr = realloc(ptr, 200 * sizeof(int));

This resizes the existing memory block to accommodate 200 integers.

4. free() (Memory Deallocation):

o Dynamically allocated memory created
with malloc() or calloc() doesn’t get freed automatically.
o Use free(ptr) to release the allocated memory.
o Example:

free(ptr);
Q-5) Discuss Recursion with Definition and Examples- Tower of Hanoi problem,
Tail Recursion.
ANS)
Recursion

• Recursion is a powerful programming concept where a function calls itself

directly or indirectly to solve a problem.
• It involves breaking down a complex problem into smaller, similar
subproblems.
• Recursive functions have two main components:
1. Base case: The simplest form of the problem that can be solved
directly.
2. Recursive case: The problem is broken down into smaller instances of
itself.

Tower of Hanoi Problem

• The Tower of Hanoi is a classic mathematical puzzle.

• We have three rods (A, B, and C) and N disks of different sizes.
 • Initially, all disks are stacked on rod A in decreasing order of size (largest at the
bottom).
• The objective is to move the entire stack to another rod (usually rod C), following
these rules:
1. Only one disk can be moved at a time.
2. A disk can only be placed on top of a larger disk or an empty rod.
3. No disk may be placed on top of a smaller disk.

❖ Recursive Solution for Tower of Hanoi

1. Shift ‘N-1’ disks from A to B, using C as the auxiliary rod.

2. Shift the last disk from A to C.
3. Shift ‘N-1’ disks from B to C, using A as the auxiliary rod.

❖ Program->

#include <stdio.h>

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {

if (n == 0) {
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
int N = 3;
towerOfHanoi(N, 'A', 'C', 'B');
return 0;
}
❖ Output:

Tail Recursion

• Tail recursion occurs when the recursive call is the last statement executed in
a function.
• In tail recursion, there is nothing left to do after the recursive call.
• Tail-recursive functions can be optimized by compilers, as they don’t need to
maintain a separate stack frame for each recursive call.
 ❖ Program->

#include <stdio.h>

void print(int n) {
if (n < 0) {
return;
}
printf("%d ", n);
print(n - 1);
}

int main() {
int N = 5;
print(N);
return 0;
}
❖ Output:

Q-6) Discuss Arrays, Implementation of One Dimensional Arrays,

Multidimensional Arrays, Applications of Arrays, Address Calculation, Matrix
Operations, Sparse Matrices.

ANS)

Arrays

• An array is a data structure that stores a fixed-size collection of elements of

the same data type.
• Elements in an array are accessed using an index or subscript.
• Arrays are widely used for organizing and manipulating data efficiently.

One-Dimensional Arrays

• A one-dimensional array (or 1D array) is a linear collection of elements.

• Elements are stored in a contiguous memory block.
• Accessing elements involves a single subscript representing the index.
• Example:

✓ int arr[5]; // Declaration of an integer array with 5 elements

Multidimensional Arrays

• A multidimensional array is an array of arrays.

• It can be thought of as a matrix with rows and columns.
 • Commonly used for representing tables, grids, and matrices.
• Example:

int matrix[3][4]; // Declaration of a 2D array with 3 rows

and 4 columns

Applications of Arrays

1. Storing Data: Arrays are used to store data elements of the same type.
2. Matrices and Tables: Multidimensional arrays represent matrices, tables, and
grids.
3. Searching and Sorting: Arrays are essential for algorithms like binary search
and quicksort.
4. Dynamic Programming: Arrays are used to store intermediate results in
dynamic programming problems.
5. Graphs and Trees: Arrays can represent adjacency matrices for graphs and
trees.

Address Calculation in 1D Arrays

• To find the address of an element in a 1D array:

o Given base address B, storage size of one element W (in bytes), and
lower bound LB of the subscript (if not specified, assume zero):
o Address of A[I] = B + W * (I - LB)

Matrix Operations

• Arrays are used for matrix operations like addition, multiplication, and
transposition.
• These operations are essential in linear algebra, graphics, and scientific
computing.

Sparse Matrices

• A sparse matrix has most of its elements equal to zero.

• It is represented efficiently to save memory and computation time.
• Common representations:
1. Array Representation: Store non-zero elements using triplets (row,
column, value).
2. Linked List Representation: Use linked lists to store non-zero elements

Program Based Questions:

Question-1(Two Sum)
• Given an array of integer nums and an integer target, return indices of the two numbers such
that they add up to the target.
• You may assume that each input would have exactly one solution, and you may not use the
same element twice.
• You can return the answer in any order.
• Example 1:
• Input: nums = [2,7,11,15], target = 9
• Output: [0,1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
• Example 2:
• Input: nums = [3,2,4], target = 6
• Output: [1,2]
• Example 3:
• Input: nums = [3,3], target = 6
• Output: [0,1]
❖ PROGRAM:
#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

*returnSize = 2;
int* arr = (int*)malloc((*returnSize) * sizeof(int));

// Create a hash table to store the value-to-index mapping

int hashTable[2001] = {0}; // Assuming input values are within [-1000, 1000]

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

int complement = target - nums[i];
if (hashTable[complement + 1000] != 0) {
arr[0] = hashTable[complement + 1000] - 1;
arr[1] = i;
break;
}
hashTable[nums[i] + 1000] = i + 1;
}

return arr;
}

int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int size = sizeof(nums) / sizeof(nums[0]);

int returnSize;
int* result = twoSum(nums, size, target, &returnSize);

printf("Indices: %d, %d\n", result[0], result[1]);

free(result);
return 0;
}
❖ Output:
 Question-2(Remove Duplicate from Sorted array)

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such
that each unique element appears only once. The relative order of the elements should be kept the
same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the
following things:

Change the array nums such that the first k elements of nums contain the unique elements in the
order they were present in nums initially. The remaining elements of nums are not important as well
as the size of nums.

Return k.

Example 1:

Input: nums = [1,1,2]

Output: 2, nums = [1,2,_]

Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2
respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]

Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3,
and 4 respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

❖ Program:
#include <stdio.h>
int removeDuplicates(int nums[], int numsSize) {
if (numsSize == 0 || numsSize == 1)
return numsSize;

int j = 0; // Index for unique elements

for (int i = 0; i < numsSize - 1; i++) {

if (nums[i] != nums[i + 1]) {
nums[j++] = nums[i]; // Copy unique element
}
}

nums[j++] = nums[numsSize - 1]; // Copy the last element

return j;
}
 int main() {
int nums[] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);

int uniqueCount = removeDuplicates(nums, numsSize);

printf("Number of unique elements: %d\n", uniqueCount);

printf("Modified array: ");
for (int i = 0; i < uniqueCount; i++) {
printf("%d ", nums[i]);
}
printf("\n");
return 0;
}
❖ Output:

Question 3(Spiral Matrix)

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

❖ Program:
#include <stdio.h>
void generateSpiralMatrix(int n) {
int matrix[n][n];
int num = 1; // Initialize the starting number

int rowStart = 0, rowEnd = n - 1;

int colStart = 0, colEnd = n - 1;
 while (num <= n * n) {
// Move right
for (int i = colStart; i <= colEnd; i++) {
matrix[rowStart][i] = num++;
}
rowStart++;

// Move down
for (int i = rowStart; i <= rowEnd; i++) {
matrix[i][colEnd] = num++;
}
colEnd--;

// Move left
for (int i = colEnd; i >= colStart; i--) {
matrix[rowEnd][i] = num++;
}
rowEnd--;

// Move up
for (int i = rowEnd; i >= rowStart; i--) {
matrix[i][colStart] = num++;
}
colStart++;
}

// Print the generated matrix

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

int main() {
int n;
printf("Enter a positive integer n: ");
scanf("%d", &n);

generateSpiralMatrix(n);

return 0;
}
❖ Output: