i) What do you mean by abstract data type?

An Abstract Data Type (ADT) is a data type that is defined by its behavior rather than its
implementation. It provides a set of operations on data, abstracting away the details of how
these operations are implemented. Examples include stacks, queues, and lists.

ii) Define an algorithm.

An algorithm is a finite sequence of well-defined instructions to solve a specific problem or
to perform a computation. Each step of an algorithm is clear, and it terminates after a finite
number of steps.

iii) What is big 'O' notation?

Big 'O' notation describes the upper bound of an algorithm's time complexity, representing
the worst-case scenario in terms of input size (n). It helps to analyze the performance and
efficiency of an algorithm.

iv) Write down two disadvantages of arrays to implement Stack.

1. Fixed size: Once an array's size is defined, it cannot be changed dynamically.

2. Inefficient memory usage: If the array size is overestimated, it can lead to wasted
memory.

v) How is recursion different from iteration?

 Recursion is a process where a function calls itself to solve a problem.

 Iteration uses loops (like for, while) to repeat operations. Recursion is generally more
memory-intensive than iteration.

vi) Write down the infix expression (325)/(3*2-3)+5 into its equivalent postfix form.
Postfix expression: 3 2 * 5 * 3 2 * 3 - / 5 +

vii) Define the term 'Polish notation'.

Polish notation, or prefix notation, is a way of writing mathematical expressions without
parentheses, where the operator comes before the operands. For example, + 3 4 instead of 3
+ 4.

viii) Define priority queue.

A priority queue is a data structure where each element has a priority assigned to it, and
elements are served based on their priority, with higher-priority elements dequeued before
lower-priority ones.

ix) Define null pointer.

A null pointer is a pointer that does not point to any valid memory address or data. In many
programming languages, it is represented by NULL or nullptr.

x) Distinguish between singly linked list and circular linked list.

 Singly Linked List: Each node points to the next node, and the last node points to
null.
 Circular Linked List: The last node points back to the first node, forming a circular
structure.
xi) Write down the implementing structure of a tree in C.
In C, a tree is typically implemented using a struct with pointers. Example:

struct Node {
int data;
struct Node *left;
struct Node *right;
};

xii) Define tree traversal and its types.

Tree traversal is the process of visiting each node in a tree systematically. The main types
are:

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal
4. Level-order traversal

xiii) Construct a binary tree with the elements 78, 26, 94, 43, 23, 14, 53, 76, 29.
Building a binary tree from a list of elements can vary depending on the rules (e.g., binary
search tree or general binary tree). For a Binary Search Tree:

markdown
Copy code
78
/ \
26 94
/ \ /
23 43 76
/ /
14 53
\
29

xiv) Define height balanced tree.

A height-balanced tree is a binary tree where the difference in height between the left and
right subtrees of any node is at most one. Examples include AVL trees.

xv) Define BFS.

BFS (Breadth-First Search) is a graph traversal algorithm that explores nodes level by level,
starting from a given node and moving outward. It uses a queue to track the nodes.

a) Describe the adjacency matrix to represent a graph with an example.

An adjacency matrix is a 2D array that represents a graph where the rows and columns
correspond to the vertices. If there is an edge between vertex iii and vertex jjj, then the
element at position (i,j)(i, j)(i,j) in the matrix is set to 1 (or the weight of the edge if it's a
weighted graph). Otherwise, it’s set to 0.

For example, consider a graph with 4 vertices (A, B, C, D) and the following edges:

 A-B
  A-C
 B-D

The adjacency matrix representation of this graph would be:

[0110100110000100]\begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0
& 1 & 0 & 0 \\ \end{bmatrix}0110100110000100

Here, each row and column represents a vertex, and the presence of 1 denotes an edge
between vertices.

b) Differentiate between DFS and BFS.

 Depth-First Search (DFS):

o Explores as far as possible down one branch before backtracking.
o Uses a stack (either explicit or recursion).
o Suitable for applications like pathfinding, detecting cycles in graphs.
 Breadth-First Search (BFS):
o Explores all neighbors at the current depth level before moving to the next
depth level.
o Uses a queue.
o Useful for finding the shortest path in an unweighted graph.

c) Define minimum spanning tree.

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected graph
that connects all vertices without any cycles and with the minimum possible total edge
weight. MSTs are commonly used in network design, such as designing a layout of cables
connecting different nodes to minimize the total length of cables.

Question 9

a) Define internal and external sorting techniques.

 Internal Sorting: Sorting is performed in the main memory. It's used when the entire
dataset can fit into the main memory. Examples include Quick Sort, Merge Sort, and
Bubble Sort.
 External Sorting: Sorting is performed when the dataset is too large to fit into the
main memory, and it requires access to external storage like a hard disk. Techniques
like External Merge Sort and Multiway Merge Sort are used in these cases.

b) Write down the algorithm to implement merge sort.

Merge Sort is a divide-and-conquer algorithm. Here’s the algorithm:
 1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves to produce a sorted array.

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

# Recursively sort each half

merge_sort(left_half)
merge_sort(right_half)

# Merge the sorted halves

i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

# Check if any element was left

while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1

c) Find the complexity of bubble sort in different cases.

 Best Case: O(n)O(n)O(n) – When the array is already sorted, Bubble Sort only needs
one pass to confirm the order.
 Average Case: O(n2)O(n^2)O(n2) – In most cases, each element is compared with
others, leading to a quadratic complexity.
 Worst Case: O(n2)O(n^2)O(n2) – When the array is sorted in reverse order, Bubble
Sort performs the maximum number of comparisons and swaps.

Question 10

a) Show the sorting steps of the following elements stored in an integer array Sample[]
= {2, 84, 15, 75, 39, 27, 85, 71, 63, 97, 27, 14} using selection sort.
Selection Sort works by repeatedly finding the minimum element from the unsorted part of
the array and moving it to the sorted part.

Here's the process:

 1. Find the smallest element (2), swap with the first element.
2,84,15,75,39,27,85,71,63,97,27,142, 84, 15, 75, 39, 27, 85, 71, 63, 97, 27,
142,84,15,75,39,27,85,71,63,97,27,14
2. Find the next smallest element (14), swap with the second element.
2,14,15,75,39,27,85,71,63,97,27,842, 14, 15, 75, 39, 27, 85, 71, 63, 97, 27,
842,14,15,75,39,27,85,71,63,97,27,84
3. Continue this process until the array is fully sorted.

I'll skip through all the steps here, but each step involves selecting the minimum of the
remaining unsorted elements and placing it in the correct position.

b) When does bubble sort give a better order of complexity than quick sort?
Bubble Sort can perform better than Quick Sort when the array is already or nearly sorted
because it can stop early in the best-case scenario (O(n)). Quick Sort has an average and
worst time complexity of O(nlog⁡n)O(n \log n)O(nlogn) and O(n2)O(n^2)O(n2), respectively,
and does not take advantage of an already-sorted array.

c) Define Heap and types.

A Heap is a complete binary tree where the value of each node is greater than or equal to (in
a max-heap) or less than or equal to (in a min-heap) the values of its children.

 Max-Heap: The root node has the largest value, and every parent node is greater than
or equal to its children.
 Min-Heap: The root node has the smallest value, and every parent node is less than or
equal to its children.

(xii) Define tree traversal and its types.

Tree traversal is the process of visiting each node in a tree. There are three main types:

1. In-order: Visit left subtree, root, right subtree.

2. Pre-order: Visit root, left subtree, right subtree.
3. Post-order: Visit left subtree, right subtree, root.

(xiii) Construct a Binary tree with the elements 78, 26, 94, 43, 23, 14, 53, 76, 76, 29.
To construct a binary search tree (BST), insert the elements one by one:

1. Insert 78 as the root.

2. Insert 26 to the left of 78.
3. Insert 94 to the right of 78.
4. Continue this process until the tree is fully constructed.
(xiv) Define height balanced tree.
A height-balanced tree is a binary tree in which the height difference between the left and
right subtrees of every node is at most 1. AVL trees are examples of height-balanced trees.

(xv) Define BFS.

BFS (Breadth-First Search) is a graph traversal algorithm that explores vertices level by level.
Starting from a given vertex, it visits all adjacent vertices before moving to the next level of
vertices. BFS uses a queue data structure.

Question 2

a) What do you mean by Complexity of Algorithm?

The complexity of an algorithm refers to the amount of computational resources (like time
and space) it requires to execute. It is usually expressed in terms of time complexity
(execution time) and space complexity (memory usage) with respect to input size.

b) What do you mean by primitive data types?

Primitive data types are basic types provided by a programming language as the building
blocks for data manipulation. Examples include int, char, float, and double. They are
typically built-in and have fixed sizes.

c) Distinguish between data types and data structure.

 Data Type: Specifies the kind of value a variable can hold (e.g., int, float, char).
 Data Structure: Defines the way data is organized, managed, and stored in memory
(e.g., array, linked list, stack).

Question 3

a) Write down the functions PUSH() and POP() in C to implement a Stack.

c
Copy code
#define MAX 100
int stack[MAX];
int top = -1;

void push(int value) {

if (top == MAX - 1) {
printf("Stack overflow\n");
} else {
stack[++top] = value;
 }
}

int pop() {
if (top == -1) {
printf("Stack underflow\n");
return -1;
} else {
return stack[top--];
}
}

b) Explain the terms ‘underflow’ and ‘overflow’ with respect to a Stack.

 Underflow: Occurs when trying to pop an element from an empty stack.

 Overflow: Occurs when trying to push an element onto a full stack.

Question 4

a) What do you mean by ‘Circular Queue’?

A circular queue is a linear data structure that follows the First In First Out (FIFO) principle,
but the last position is connected back to the first position, forming a circular structure. This
structure helps efficiently utilize storage.

b) How the limitations in linear Queue can be avoided using Circular Queue?
In a linear queue, space can be wasted when elements are dequeued from the front. In a
circular queue, the positions freed by dequeuing can be reused by adjusting pointers
circularly, maximizing space usage.

c) Explain ‘Queue Full’ and ‘Queue Empty’ conditions for a Circular Queue using code
of implementation.

#define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;

// Check if queue is full

int isFull() {
return (rear + 1) % MAX == front;
}

// Check if queue is empty

int isEmpty() {
return front == -1;
}
 Queue Full: The queue is full when (rear + 1) % MAX == front.
 Queue Empty: The queue is empty when front == -1.