Uni.

RN

UNITED COLLEGE OF ENGINEERING & RESEARCH, PRAYAGRAJ (010) Department of CSE/AIML

Date:
First Sessional Examination (Odd Semester 2024-25) SEMESTER: 3rd 24/10/2024
TIME: 2 hours SUBJECT: Data Structure Paper Code: BCS301 MM. 20
READ ALL INSTRUCTIONS AND QUESTIONS VERY CAREFULLY
SECTION A (Attempt all questions)
Rank the following bounds in increasing order of their growth rates with reasons: O(log n), O(n2),
O(1), O(n2 log n)

The increasing order of growth rate is: O(1), O(log n), O(n2), , O(n2 log n)

1 a

Write the differences between array and linked list. Also write various types of linked list.

1 b
 Define a stack. Evaluate the following Postfix expression:
2 3 9 * + 2 3 ^ - 6 2 / +

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end.
1 c It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an
element is added in the stack, it is added on the top of the stack, and the element can be deleted
only from the stack. In other words, a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the stack.
Answer: 24
Define recursion. Find the output of the following code for n=3:
void fun(int n)
{
if (n > 0) {
fun (n - 1);
printf("%d ", n);
fun (n-1);
1 d }
}

The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called a recursive function. Using a recursive algorithm, certain problems
can be solved quite easily.
Answer: 1 2 1 3 1 2 1
Define stable sorting techniques. Also give examples of stable and unstable sorting techniques.

In a stable sorting algorithm, data is sorted in a way that preserves the original order of elements having equal
keys. This means that if two elements have the same key, the one that appeared earlier in the input will also
1 e appear earlier in the sorted output. For instance, if element A[i] and element A[j] have the same key and i < j,
then in sorted order, A[i] should come before A[j].Eg. Insertion sort, Bubble sort, Counting sort

In an unstable sorting algorithm, data is sorted so that the order of elements with equal keys is not preserved
after sorting. Eg. Quick sort, Heap sort
 Uni. RN

SECTION B (Attempt any two questions)

Explain the various representations of polynomials. Write an algorithm/function to add two
polynomials using linked list.

A polynomial is an algebraic expression consisting of variables, coefficients, and operations such as addition,
subtraction, multiplication, and non-negative exponentiation of variables.
E.g., P(x) = x² − 5x + 9
Polynomial representation using linked list
This section will see how to represent polynomials using linked lists.
Each node in the linked list denotes one term of the polynomial.
Every node stores -
• Value of exponent
• Value of coefficient
• Pointer to the next node

So, the structure of the node looks like this -

Node* add(Node* poly1, Node* poly2) {

Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
 if (poly1->exp == poly2->exp) {
insert(&result, poly1->coef + poly2->coef, poly1->exp);
poly1 = poly1->next;
poly2 = poly2->next;
} else if (poly1->exp > poly2->exp) {
insert(&result, poly1->coef, poly1->exp);
poly1 = poly1->next;
} else {
insert(&result, poly2->coef, poly2->exp);
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insert(&result, poly1->coef, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insert(&result, poly2->coef, poly2->exp);
poly2 = poly2->next;
}
return result;
}

Assume that the declaration of multi-dimensional arrays X and Y to be:

X (-2:2, 2:22) and Y (1:8, -5:5, -10:5)
(i) Find the length of each dimension and number of elements in X and Y.
(ii) Find the address of element Y (2, 2, 3), assuming Base address of Y = 400 and each
element occupies 4 memory locations.

For array X:
L1=5
L2=21
No. of elements=5x21=105
For array Y:
L1=8
3 L2=11
L3=16
No. of elements=8x11x16=1408

E1=2-1=1
E2=2-(-5)=7
E3=3-(-10)=13

Address in RMO = BA + [[E1*L2 + E2]*L3 + E3]*W

= 400+[[1*11+7]*16+13]*4
= 1604
ADDRESS IN CMO = BA[[E3*L2+E2]*L1+E1]*W
 Uni. RN

= 400+[[13*11+7]*8+1]*4
= 5204
Define the following terms in brief:
(i) Time & Space complexity
(ii) Best case, worst case & average case analysis
(iii) Asymptotic Notations

Time complexity is a concept in computer science that describes the amount of time an algorithm takes to run as
a function of the length of the input. It's a crucial aspect of algorithm analysis as it helps understand how efficiently
an algorithm performs, particularly as the size of the input data increases.
Measure of Efficiency: Time complexity provides a way to quantify the efficiency of an algorithm in terms of time.
It's particularly important for understanding the scalability of an algorithm.

Space complexity is a term in computer science used to describe the amount of memory space required by an
algorithm to run as a function of the length of the input. It is an important metric for understanding how efficient
an algorithm is in terms of memory usage, especially in environments where memory resources are limited.
Key Points About Space Complexity
Memory Usage Measurement: Space complexity measures the total amount of memory or storage space
an algorithm needs to complete. This includes both the space taken up by the input data and any additional space
used by the algorithm for variables, data structures, and function calls.

• Best case
The minimum number of steps an algorithm takes on input data. This analysis determines the lower bound on how
4 long it takes an algorithm to complete a task.
• Worst case
The maximum number of steps an algorithm takes on input data. This analysis provides information about how
long an algorithm takes to run when it's unstable or when the inputs produce poor results.
• Average case
The average number of steps an algorithm takes on input data. This analysis provides a general overview of how
the algorithm performs under normal conditions.
For example, in sequential search, the best case is when the algorithm matches the target immediately after one
comparison. The worst case is when the algorithm matches the last item in the list or doesn't match anything after
making n comparisons.

Asymptotic Notations:
• Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by
understanding how their efficiency changes as the input size grows.
• These notations provide a concise way to express the behavior of an algorithm’s time or space complexity
as the input size approaches infinity.
• Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative
growth rates of algorithms’ complexities.
• It enables comparisons of algorithms’ efficiency by abstracting away machine-specific constants and
implementation details, focusing instead on fundamental trends.
• Asymptotic analysis allows for the comparison of algorithms’ space and time complexities by examining
their performance characteristics as the input size varies.
 • By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can categorize algorithms
based on their worst-case, best-case, or average-case time or space complexities, providing valuable
insights into their efficiency.

1. 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.
Let g and f be the function from the set of natural numbers to itself. The function f is said to be Θ(g), if there are
constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0.

2. Big-O Notation (O-notation):

Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-case
complexity of an algorithm.
▪ It is the most widely used notation for Asymptotic analysis.
▪ It specifies the upper bound of a function.
▪ The maximum time required by an algorithm or the worst-case time complexity.
▪ It returns the highest possible output value(big-O) for a given input.
▪ Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution
in the longest amount of time possible.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive constant C and n0 such that,
0 ≤ f(n) ≤ cg(n) for all n ≥ n0.

3. Omega Notation (Ω-Notation):

 Uni. RN

Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case
complexity of an algorithm.
The execution time serves as a lower bound on the algorithm’s time complexity.
It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount
of time.
Let g and f be the function from the set of natural numbers to itself. The function f is said to be Ω(g), if there is a
constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n0

SECTION C (Attempt any two question)

Explain Stack and its applications. Convert the following Infix expression into Postfix expression
using Tabular method. A – B / C * D + E * F / G.

A stack is a linear data structure in which the insertion of a new element and removal of an existing element takes
place at the same end represented as the top of the stack.

Applications of Stacks:
• Function calls: Stacks are used to keep track of the return addresses of function calls, allowing the program
to return to the correct location after a function has finished executing.
• Recursion: Stacks are used to store the local variables and return addresses of recursive function calls,
allowing the program to keep track of the current state of the recursion.
 • Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse Polish
Notation).
• Syntax parsing: Stacks are used to check the validity of syntax in programming languages and other formal
languages.
• Memory management: Stacks are used to allocate and manage memory in some operating systems and
programming languages.

0 (
1 A ( A
2 – (– A
3 B (– AB
4 / (– / AB
5 C (– / ABC
6 * (– * ABC/
7 D (– * ABC/D
8 + (+ ABC/D*–
9 E (+ ABC/D*–E
10 * (+* ABC/D*–E
11 F (+* ABC/D*–EF
12 / (+/ ABC/D*–EF*
13 G (+/ ABC/D*–EF*G
14 ) ABC/D*–EF*G/+
Differentiate between iteration and recursion. Write the recursive solution for Tower of Hanoi
6
problem. Show the working of your algorithm for n=3 disks.
Uni. RN

void tower_hanoi(char source, char aux, char dest, int n)

{
if(n==1)
printf("\n%c----->%c",source,dest);
else
{
tower_hanoi(source,dest,aux,n-1);
printf("\n%c----->%c",source,dest);
tower_hanoi(aux,source,dest,n-1);
}
}
 Write a C program to implement stack and its operations using singly linked list.

#include <stdio.h>
#include <stdlib.h>
// Node structure to represent elements in the stack
struct Node {
int data;
struct Node* next;
};
// Stack structure to manage the stack
7 struct Stack {
struct Node* top;
};
// Function to create a new node with given data
struct Node* newNode(int data) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
 Uni. RN

// Function to create a new stack and initialize it

struct Stack* createStack() {
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->top = NULL;
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return !stack->top; // Returns 1 if the stack is empty, otherwise returns 0
}
// Function to push a value onto the stack
void push_data(struct Stack* stack, int data) {
printf("\n Push data %d", data);
struct Node* node = newNode(data);
node->next = stack->top;
stack->top = node; // The new node becomes the top of the stack
}
// Function to pop a value from the stack
int pop_data(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // Returns -1 if the stack is empty
}
struct Node* temp = stack->top;
int popped = temp->data; // Value to be popped from the top of the stack
stack->top = temp->next; // Move the top pointer to the next node
free(temp); // Free the memory of the popped node
return popped; // Return the popped value
}

int main() {
// Creating a stack and pushing elements onto it
struct Stack* stack1 = createStack();
push_data(stack1, 1);
push_data(stack1, 2);
push_data(stack1, 3);
push_data(stack1, 4);

// Popping elements from the stack and displaying them

printf("\n\n Pop data: %d", pop_data(stack1));
printf("\n Pop data: %d", pop_data(stack1));
printf("\n Pop data: %d", pop_data(stack1));
printf("\n Pop data: %d", pop_data(stack1));

// Checking if a stack is empty or not

 printf("\n\n Check a stack is empty or not?\n");
struct Stack* stack2 = createStack();
if (isEmpty(stack2)) {
printf(" Stack is empty!\n");
} else {
printf(" Stack is not empty!\n");
}
}

SECTION D (Attempt any one question)

Explain how Binary search is different from linear search. Write an algorithm to implement Binary
search. Apply your algorithm to find item 40 in the list: 11 22 25 27 30 33 37 40 44
48 50 55
Also discuss the time complexity of Binary search algorithm.

8
 Uni. RN

Write an algorithm/function for bubble sort. Also explain the time complexity in all cases. Apply
the algorithm on the following elements:
11, 3, 14, 1, 17, 61, 51, 18, 91, 1, 19, 10

Bubble Sort
Bubble Sort is a simple sorting algorithm commonly used to sort elements in a list or array. It works by repeatedly
comparing adjacent elements and swapping them if they are in the wrong order. The algorithm iterates through
the list multiple times until no more swaps are needed, resulting in a sorted sequence. During each iteration, the
largest unsorted element "bubbles" up to its correct position, hence the name "Bubble Sort."

9 // An optimized version of Bubble Sort

void bubbleSort(int arr[], int n){
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = true;
}
 }

// If no two elements were swapped by inner loop,

// then break
if (swapped == false)
break;
}
}

#### END OF PAPER ####

Course Outcome Wise CO1 CO2 CO3 CO4 CO5

Marks Distribution
11 11 7 0 0

Bloom’s Taxonomy Wise L1 L2 L3 L4 L5 L6

Marks Distribution
0 6 23 0 0 0