CSIT 3rd DSA Study Guide with Soln

CSIT 3rd Semester Data Structures and Algorithms Study Guide

A comprehensive resource to score 60/60 in your board exams with detailed notes, exercises, interactive quizzes, model question sets, and progress tracking!

Welcome to the DSA Study Guide!

This guide is tailored for CSIT 3rd semester students at Tribhuvan University to master Data Structures and Algorithms (CSC211). It’s organized into eight units, each covering a core topic with detailed notes, 10 high-mark exercise questions, a 10-question interactive quiz, and reference videos from YouTube. Five model question sets simulate the board exam format (Group A: 2×10 marks, Group B: 8×5 marks), and a progress tracker monitors your quiz scores and syllabus coverage. The webpage is responsive, features animations, and offers dark/light mode options for a user-friendly experience. Focus on high-mark questions (5–10 marks) to maximize your score and aim for 60/60!

How to Use: Review notes, solve exercises, take quizzes to log scores, practice model sets, and track progress with the hovering tracker. Use reference videos for visual learning.

Model Question Sets

Model Set 1

This model set mirrors the CSIT board exam format, with Group A (2 × 10 marks) and Group B (8 × 5 marks), totaling 60 marks. Questions are designed based on past papers (2074–2078) and syllabus trends to maximize exam readiness.

Group A (20 marks)

(10 marks) Explain amortized analysis with its types. Provide an example of aggregate method analysis for a dynamic array.

Answer:

Definition: Amortized analysis determines the average time per operation over a sequence of operations, smoothing out costly operations to provide a more accurate performance measure than worst-case analysis.

Types of Amortized Analysis:

Aggregate Method: Calculates total cost of n operations and divides by n to find average cost per operation.
Accounting Method: Assigns amortized costs to operations, ensuring total amortized cost ≥ total actual cost, with some operations “saving” credit for others.
Potential Method: Uses a potential function to track stored “energy” in the data structure, accounting for differences between actual and amortized costs.

Example: Aggregate Method for Dynamic Array:

Scenario: A dynamic array doubles its size when full during an append operation.
Operations: Consider n appends starting with size 1.
Cost Analysis:
- Normal append (no resize): Cost = 1 (add element).
- Resize append (when full): Cost = i (copy i elements to new array of size 2i).
- Resizes occur at sizes 1, 2, 4, ..., n/2, i.e., when i = 2^k.
- Total cost for n appends:
  - Normal appends: n (one per operation).
  - Resizes: At sizes 1, 2, 4, ..., n/2, costs are 1, 2, 4, ..., n/2.
  - Sum of resize costs: 1 + 2 + 4 + ... + n/2 = n – 1 (geometric series).
  - Total cost: n + (n – 1) ≈ 2n.
- Amortized cost per append: Total cost / n = 2n / n = O(1).

Significance: Shows that despite occasional O(n) resizes, average append cost is constant, making dynamic arrays efficient.

Applications: Used in hash tables, binary counters, and queue implementations to justify performance.

Conclusion: Amortized analysis reveals true efficiency, critical for designing scalable data structures.

(10 marks) Write a program to implement a Binary Search Tree (BST) with insertion and search operations. Explain its working and analyze complexity.

Answer:

Definition: A Binary Search Tree is a binary tree where each node has a key such that all keys in the left subtree are smaller, and all keys in the right subtree are larger.

Program (in C):

#include 
#include 

struct Node {
    int key;
    struct Node *left, *right;
};

struct Node* createNode(int key) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int key) {
    if (root == NULL) return createNode(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}

struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->key == key) return root;
    if (key < root->key)
        return search(root->left, key);
    return search(root->right, key);
}

Working:

Insertion: Start at root. If null, create new node with key. If key < root’s key, recurse left; if key > root’s key, recurse right. Example: Insert 50, 30, 70 into empty BST:
- Insert 50: Root = [50].
- Insert 30: 30 < 50, left child = [30].
- Insert 70: 70 > 50, right child = [70].
- Tree: [50, left=[30], right=[70]].
Search: Start at root. If null or key found, return node. If key < root’s key, search left; else, search right. Example: Search 30:
- Root=50, 30<50, go left.
- Node=30, found, return node.

Complexity:

Time:
- Balanced BST: O(log n) for insert/search, as height is log n.
- Worst Case (skewed, like a list): O(n), as height is n.
Space: O(h) for recursion stack, where h is height (log n balanced, n skewed).

Use: Efficient for ordered data, like dictionaries or priority queues.

Significance: BSTs enable fast operations but require balancing (e.g., AVL, Red-Black) for guaranteed performance.

Group B (40 marks)

(5 marks) Differentiate between static and dynamic data structures with examples.

Answer:

Static Data Structure: Fixed size, allocated at compile time, cannot resize at runtime.

Example: Array (e.g., int arr[100] in C).
Advantage: Fast access (O(1)), simple memory management.
Limitation: Wastes space if underused; cannot grow if full.

Dynamic Data Structure: Variable size, allocated at runtime, can grow/shrink.

Example: Linked List (e.g., nodes with malloc in C).
Advantage: Flexible size, efficient for insertions/deletions.
Limitation: Slower access (O(n)), overhead of pointers.

Comparison:

Memory: Static is fixed (stack); dynamic is flexible (heap).
Use: Static for known sizes (e.g., matrix); dynamic for unpredictable sizes (e.g., list of users).

Example: Static array for 10 student grades vs. dynamic linked list for variable student enrollments.

Significance: Choice depends on data size predictability and operation needs.

(5 marks) Explain the significance of stack in function call management.

Answer:

Definition: A stack is a LIFO (Last In, First Out) data structure managing function calls via a call stack.

Significance:

Function Calls: Each function call pushes a frame onto the stack, storing local variables, parameters, and return address.
Recursion: Tracks recursive calls, ensuring correct return order (e.g., factorial(3) pushes factorial(3), factorial(2), factorial(1)).
Memory Management: Automatically allocates/deallocates memory for local variables when functions enter/exit.
Backtracking: Maintains state for nested calls, enabling proper resumption.

Example: For nested calls f1() → f2() → f3():

Push f1’s frame, then f2’s, then f3’s.
Pop f3’s frame on return, then f2’s, then f1’s, restoring state.

Advantages: Ensures correct execution order, efficient memory use.

Limitation: Stack overflow for deep recursion (e.g., large n in factorial).

Significance: Critical for runtime systems, enabling structured programming.

(5 marks) Write an algorithm to reverse a queue using a stack.

Answer:

Algorithm:

Input: Queue Q with elements.
Initialize an empty stack S.
While Q is not empty:
- Dequeue element x from Q.
- Push x onto S.
While S is not empty:
- Pop element y from S.
- Enqueue y into Q.
Return Q (now reversed).

Program (in C):

#include 
#define MAX 100

struct Queue {
    int arr[MAX];
    int front, rear;
};

struct Stack {
    int arr[MAX];
    int top;
};

void enqueue(struct Queue* q, int x) {
    q->arr[++q->rear] = x;
}

int dequeue(struct Queue* q) {
    return q->arr[q->front++];
}

void push(struct Stack* s, int x) {
    s->arr[++s->top] = x;
}

int pop(struct Stack* s) {
    return s->arr[s->top--];
}

void reverseQueue(struct Queue* q) {
    struct Stack s;
    s.top = -1;
    while (q->front <= q->rear) {
        push(&s, dequeue(q));
    }
    while (s.top >= 0) {
        enqueue(q, pop(&s));
    }
}

Working: For queue [1,2,3] (front=1, rear=3):

Dequeue 1, push to stack: S=[1].
Dequeue 2, push: S=[1,2].
Dequeue 3, push: S=[1,2,3].
Pop 3, enqueue: Q=[3].
Pop 2, enqueue: Q=[3,2].
Pop 1, enqueue: Q=[3,2,1].

Time Complexity: O(n), as each element is moved twice.

Space Complexity: O(n) for stack.

(5 marks) Explain how AVL trees maintain balance after insertion.

Answer:

Definition: An AVL tree is a self-balancing BST where the height difference (balance factor) between left and right subtrees of any node is at most 1.

Balance Maintenance:

Balance Factor: For each node, balance factor = height(left) – height(right), must be {-1, 0, 1}.
Insertion Process:
- Perform standard BST insertion.
- Update heights of nodes along insertion path.
- Check balance factor of each ancestor.
- If unbalanced (|balance factor| > 1), apply rotations.
Rotations:
- LL (Left-Left): Node’s left child’s left subtree is heavy → Right rotation.
- RR (Right-Right): Node’s right child’s right subtree is heavy → Left rotation.
- LR (Left-Right): Left child’s right subtree is heavy → Left rotation on left child, then right rotation.
- RL (Right-Left): Right child’s left subtree is heavy → Right rotation on right child, then left rotation.

Example: Insert 10, 20, 30 (RR case):

Insert 10: [10].
Insert 20: [10,right=20].
Insert 30: [10,right=[20,right=30]], node 10 unbalanced (balance factor=-2).
Apply left rotation at 10: New root = [20,left=10,right=30].

Time Complexity: O(log n) for insertion and balancing, as height is logarithmic.

Significance: Ensures efficient O(log n) operations, unlike unbalanced BSTs.

(5 marks) Compare adjacency matrix and adjacency list for graph representation.

Answer:

Adjacency Matrix: V×V matrix where M[i][j] = 1 (or weight) if edge exists from vertex i to j, else 0.

Example: For vertices A, B, edge A→B, matrix is [[0,1],[0,0]].

Adjacency List: Each vertex stores a list of adjacent vertices.

Example: For same graph, A: [B], B: [].

Comparison:

Space: Matrix uses O(V²); list uses O(V + E), better for sparse graphs.
Edge Lookup: Matrix is O(1); list is O(degree(v)).
Adding Edge: Matrix is O(1); list is O(1) with proper structure.
Use: Matrix for dense graphs (e.g., complete graphs); list for sparse graphs (e.g., social networks).

Example: In a graph with 100 vertices and 200 edges, list saves space (O(300) vs. O(10000)).

Significance: Choice depends on graph density and operation frequency for efficiency.

(5 marks) Write an algorithm for topological sort in a DAG and explain its use.

Answer:

Algorithm (DFS-based):

Input: Directed Acyclic Graph (DAG) with adjacency list, V vertices.
Initialize visited array (all false), empty stack S.
For each unvisited vertex v:
- Call DFS(v):
  - Mark v as visited.
  - For each neighbor u of v, if unvisited, DFS(u).
  - Push v onto S after all neighbors processed.
Pop elements from S to get topological order.

Working: For DAG with edges 1→2, 2→3:

DFS(1): Visit 1, DFS(2), visit 2, DFS(3), visit 3, push 3, push 2, push 1.
Stack: [3,2,1]. Pop: [1,2,3].

Time Complexity: O(V + E), as DFS visits each vertex and edge once.

Space Complexity: O(V) for stack and visited array.

Use:

Scheduling: Order tasks with dependencies (e.g., course prerequisites).
Build Systems: Compile files in dependency order.
Deadlock Detection: Ensure cyclic-free task ordering.

Significance: Ensures valid ordering in systems with directed dependencies.

(5 marks) Explain why quick sort is preferred over bubble sort.

Answer:

Quick Sort: Divides array around a pivot, recursively sorts subarrays.

Bubble Sort: Repeatedly swaps adjacent elements if out of order.

Why Quick Sort Preferred:

Efficiency: Quick sort has O(n log n) average time vs. bubble sort’s O(n²), faster for large datasets.
Practical Performance: In-place partitioning minimizes memory; bubble sort’s many swaps are slow.
Scalability: Quick sort handles large arrays well; bubble sort is impractical beyond small lists.

Example: Sorting [5,2,9,1]: Quick sort may take ~4 comparisons (pivot-based); bubble sort takes up to 6 swaps.

Trade-off: Quick sort’s O(n²) worst case (rare with good pivots) vs. bubble sort’s consistent O(n²).

Use: Quick sort for general-purpose sorting; bubble sort for tiny arrays or teaching.

Significance: Quick sort’s speed makes it a standard in libraries (e.g., C’s qsort).

(5 marks) Discuss why dynamic programming is suitable for the knapsack problem.

Answer:

Knapsack Problem: Maximize value of items in a knapsack of capacity W, selecting whole (0/1) or fractional items.

Why Dynamic Programming Suitable:

Overlapping Subproblems: Deciding whether to include item i involves solving subproblems for remaining capacity, which repeat across recursive calls.
Optimal Substructure: Optimal solution for n items and capacity W builds on optimal solutions for n-1 items and reduced capacity.
Efficiency: DP stores subproblem solutions in a table, avoiding recomputation (e.g., O(nW) vs. O(2^n) for brute force).

Example: 0/1 Knapsack: Items [(v=60,w=10), (v=100,w=20)], W=30:

Table dp[i][w] computes max value for i items, capacity w.
Solution: Include both items for value 160.

Contrast: Greedy fails for 0/1 knapsack (suboptimal for indivisible items) but works for fractional.

Time Complexity: O(nW), filling n×W table.

Significance: DP ensures optimal solutions for complex optimization problems like knapsack.

Model Set 2

This model set replicates the CSIT board exam format, with Group A (2 × 10 marks) and Group B (8 × 5 marks), totaling 60 marks. Questions are crafted based on past papers (2074–2078) and syllabus trends to optimize exam preparation.

Group A (20 marks)

(10 marks) Explain Dijkstra’s algorithm for single-source shortest paths with a program. Analyze its complexity and discuss its applications.

Answer:

Definition: Dijkstra’s algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

Algorithm:

Input: Graph G (V vertices, E edges), source vertex s, weights w(u,v).
Initialize distances: dist[s] = 0, dist[v] = ∞ for v ≠ s.
Initialize priority queue Q with all vertices, using dist as key.
While Q is not empty:
- Extract vertex u with minimum dist[u].
- For each neighbor v of u:
  - If dist[u] + w(u,v) < dist[v], update dist[v] = dist[u] + w(u,v).
  - Update Q with new dist[v].
Return dist array.

Program (in C, using adjacency list and min-heap):

#include 
#include 
#define INF 99999
#define MAX 100

struct Edge {
    int v, weight;
};

struct Graph {
    struct Edge* adj[MAX];
    int size[MAX];
    int V;
};

struct HeapNode {
    int vertex, dist;
};

void swap(struct HeapNode* a, struct HeapNode* b) {
    struct HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(struct HeapNode heap[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && heap[left].dist < heap[smallest].dist)
        smallest = left;
    if (right < n && heap[right].dist < heap[smallest].dist)
        smallest = right;
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(heap, n, smallest);
    }
}

void dijkstra(struct Graph* g, int s, int dist[]) {
    struct HeapNode heap[MAX];
    int heapSize = g->V;
    int i;

    for (i = 0; i < g->V; i++) {
        dist[i] = INF;
        heap[i].vertex = i;
        heap[i].dist = INF;
    }
    dist[s] = 0;
    heap[s].dist = 0;

    for (i = heapSize / 2 - 1; i >= 0; i--)
        heapify(heap, heapSize, i);

    while (heapSize > 0) {
        struct HeapNode min = heap[0];
        heap[0] = heap[heapSize - 1];
        heapSize--;
        heapify(heap, heapSize, 0);

        int u = min.vertex;
        for (i = 0; i < g->size[u]; i++) {
            int v = g->adj[u][i].v;
            int w = g->adj[u][i].weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                for (int j = 0; j < heapSize; j++) {
                    if (heap[j].vertex == v) {
                        heap[j].dist = dist[v];
                        break;
                    }
                }
                for (int j = heapSize / 2 - 1; j >= 0; j--)
                    heapify(heap, heapSize, j);
            }
        }
    }
}

Working: For graph with vertices {0,1,2}, edges (0→1,4), (0→2,8), (1→2,2):

Initialize: dist[0]=0, dist[1]=∞, dist[2]=∞.
Extract 0: Update dist[1]=4, dist[2]=8.
Extract 1: Update dist[2]=min(8,4+2)=6.
Extract 2: No updates.
Output: dist=[0,4,6].

Complexity:

Time: O((V + E) log V) with a min-heap (V extract-min, E decrease-key).
Space: O(V) for dist array and heap.

Applications:

Navigation: Find shortest routes in GPS systems.
Networking: Optimize routing in protocols like OSPF.
Robotics: Path planning in weighted environments.

Significance: Efficient for sparse graphs with non-negative weights, widely used in real-world systems.

(10 marks) Write a program to implement merge sort using divide and conquer. Explain its working and analyze its complexity.

Answer:

Definition: Merge sort is a divide-and-conquer sorting algorithm that divides an array into halves, recursively sorts them, and merges the sorted halves.

Program (in C):

#include 

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    int i, j, k;

    for (i = 0; i < n1; i++) L[i] = arr[l + i];
    for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Working: For array [5,2,9,1]:

Divide: Split into [5,2], [9,1].
Conquer: Recursively sort to [2,5], [1,9].
Combine: Merge [2,5] and [1,9] → [1,2,5,9].
Merge process: Compare 1<2, take 1; 2<5, take 2; 5<9, take 5; take 9.

Complexity:

Time: O(n log n), as array is halved (log n levels) and merged (n per level).
Space: O(n) for temporary arrays during merge.

Significance: Stable and predictable performance, ideal for large datasets and linked lists.

Use: External sorting, sorting records with equal keys, and parallel processing.

Group B (40 marks)

(5 marks) Explain the role of queues in process scheduling.

Answer:

Definition: A queue is a FIFO (First In, First Out) data structure used to manage tasks or processes.

Role in Process Scheduling:

Job Queue: Stores processes waiting for CPU allocation (e.g., ready queue).
Fairness: FIFO ensures processes are executed in arrival order (e.g., Round-Robin scheduling).
Multilevel Queues: Different queues for priority levels (e.g., system vs. user processes).
I/O Handling

Example: In Round-Robin, processes [P1,P2,P3] in ready queue get CPU time slices in order, requeued after execution.

Advantages: Simple, ensures fairness, supports multitasking.

Limitation: Inefficient for priority-based scheduling without modifications.

Significance: Queues enable efficient resource allocation in operating systems.

(5 marks) Write an algorithm to detect a cycle in a linked list.

Answer:
Algorithm (Floyd’s Cycle Detection):

Input: Linked list with head node.

Initialize two pointers: slow = head, fast = head.

While fast and fast->next are not null:

Move slow one step: slow = slow->next.

Move fast two steps: fast = fast->next->next.

If slow == fast, return true (cycle detected).

Return false (no cycle).

Program (in C):

#include #include struct Node { int data; struct Node* next; }; int detectCycle(struct Node* head) { struct Node *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return 1; } return 0; }

Working: For list 1→2→3→4→2 (cycle at 2):

Initial: slow=1, fast=1.

Step 1: slow=2, fast=3.

Step 2: slow=3, fast=2.

Step 3: slow=4, fast=4 (meet, cycle detected).

Time Complexity: O(n), as pointers traverse list once.

Space Complexity: O(1), using only two pointers.

Significance: Efficiently detects loops in data structures or algorithms.

(5 marks) Discuss the advantages of Red-Black trees over AVL trees.

Answer:
Red-Black Tree: A self-balancing BST with nodes colored red or black, ensuring approximate balance.

AVL Tree: A self-balancing BST with strict balance (height difference ≤ 1).

Advantages of Red-Black Trees:

Fewer Rotations: Red-Black trees require fewer rotations for insertions/deletions due to relaxed balancing (O(1) vs. O(log n) in AVL), faster for frequent updates.

Efficient Inserts/Deletes: Color flips and simpler rules reduce overhead in dynamic datasets.

Practical Performance: Slightly taller trees (2 log n vs. log n height) but faster in practice for write-heavy workloads.

Example: Inserting 10, 20, 30:

AVL: Strict balancing may rotate at each step.

Red-Black: Color flips often suffice, deferring rotations.

Trade-off: AVL trees offer faster lookups (O(log n) guaranteed) due to stricter balance.

Use: Red-Black for databases, memory allocators; AVL for lookup-heavy systems.

Significance: Red-Black trees balance speed and flexibility, common in standard libraries (e.g., C++ STL).

(5 marks) Explain breadth-first search (BFS) and its applications.

Answer:
Definition: BFS explores a graph level by level, visiting all neighbors of a node before moving to the next level, using a queue.

Algorithm:

Input: Graph G (V vertices, adjacency list), start vertex s.

Initialize queue Q, visited array (all false).

Enqueue s, mark s visited.

While Q is not empty:

Dequeue vertex u.

Process u (e.g., print).

For each unvisited neighbor v of u:

Mark v visited, enqueue v.

Working: For graph with edges 0→1, 0→2, 1→3:

Start at 0: Enqueue 0, visit 0.

Dequeue 0: Enqueue 1, 2, visit 1, 2.

Dequeue 1: Enqueue 3, visit 3.

Dequeue 2, 3: No new vertices.

Order: 0, 1, 2, 3.

Applications:

Shortest Path: Finds shortest path in unweighted graphs (e.g., maze solving).

Social Networks: Discover friends within k degrees.

Web Crawling: Explore linked pages level by level.

Time Complexity: O(V + E) with adjacency list.

Significance: BFS ensures optimal solutions for level-based traversal problems.

(5 marks) Compare linear search and binary search with their use cases.

Answer:

Linear Search: Checks each element sequentially until target is found or list ends.

Time: O(n) worst/average case.

Use Case: Small or unsorted lists (e.g., finding a name in a short array).

Binary Search: Halves sorted array repeatedly to find target.

Time: O(log n) worst/average case.

Use Case: Large sorted datasets (e.g., database indices, phonebooks).

Comparison:

Input: Linear needs no preprocessing; binary requires sorted data.

Efficiency: Linear is slower for large n; binary is logarithmic.

Complexity: Linear is simpler to implement; binary needs sorting if unsorted.

Example: Search 7 in [1,3,7,9]: Linear takes 3 steps; binary takes 2.

Significance: Choose linear for simplicity or unsorted data, binary for efficiency in sorted contexts.

(5 marks) Explain why merge sort is preferred for linked lists over quick sort.

Answer:
Merge Sort: Divides list into halves, sorts recursively, and merges sorted halves.

Quick Sort: Partitions list around a pivot, recursively sorts sublists.

Why Merge Sort Preferred:

Access Pattern: Linked lists lack random access, making quick sort’s pivot selection and partitioning slow (O(n) per partition). Merge sort uses sequential access, merging naturally.

Stability: Merge sort is stable, preserving order of equal elements; quick sort is not, which matters for complex keys.

Predictability: Merge sort guarantees O(n log n); quick sort risks O(n²) with poor pivots.

Example: Sorting [5,2,9,1]: Merge sort divides and merges in O(n log n); quick sort struggles with pointer adjustments.

Trade-off: Merge sort uses O(n) extra space, but linked lists prioritize time efficiency.

Significance: Merge sort’s sequential nature makes it ideal for linked list sorting in practice.

(5 marks) Discuss the greedy choice property with an example.

Answer:
Definition: The greedy choice property states that a locally optimal choice at each step leads to a globally optimal solution for certain problems.

Example: Activity Selection:

Problem: Select maximum non-overlapping activities from a set with start and end times.

Greedy Choice: Choose the activity with the earliest end time that doesn’t conflict with selected activities.

Execution: Activities [(1,4), (3,5), (2,7), (5,9)]:

Sort by end time: [(1,4), (3,5), (5,9), (2,7)].

Pick (1,4), skip (3,5) and (2,7) due to overlap, pick (5,9).

Output: [(1,4), (5,9)].

Correctness: Earliest end time maximizes remaining time for other activities, ensuring optimal selection.

Significance: Greedy choice simplifies algorithms but requires proof of optimality (e.g., for MST, scheduling).

Use: Applied in Kruskal’s algorithm, Huffman coding, and scheduling problems.

(5 marks) Explain how dynamic programming optimizes the Fibonacci sequence computation.

Answer:
Problem: Compute the nth Fibonacci number (F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1).

Why Dynamic Programming:

Overlapping Subproblems: Naive recursion (e.g., F(5) = F(4) + F(3)) recomputes F(3) multiple times.

DP Solution: Store results in a table to avoid recomputation.

Program (in C):

#include int fibonacci(int n) { int dp[n+1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; return dp[n]; }

Working: For n=5:

dp[0]=0, dp[1]=1.

dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

Output: 5 (sequence: 0,1,1,2,3,5).

Complexity:

Time: O(n) vs. O(2^n) for naive recursion.

Space: O(n) for table (optimizable to O(1) with two variables).

Significance: DP eliminates redundant calculations, making Fibonacci computation efficient for large n.

Model Set 3

This model set follows the CSIT board exam format, with Group A (2 × 10 marks) and Group B (8 × 5 marks), totaling 60 marks. Questions are designed based on past papers (2074–2078) and syllabus trends to ensure comprehensive exam preparation.

Group A (20 marks)

(10 marks) Explain Kruskal’s algorithm for finding a minimum spanning tree with a program. Analyze its complexity and discuss its applications.

Answer:

Definition: Kruskal’s algorithm finds a minimum spanning tree (MST) in a weighted, connected, undirected graph by greedily selecting edges in increasing order of weight, avoiding cycles.

Algorithm:

Input: Graph G with V vertices, E edges, weights w(e).

Sort all edges by weight in non-decreasing order.

Initialize empty MST and disjoint-set data structure for cycle detection.

For each edge (u,v) in sorted order:

If u and v are in different sets (no cycle), add (u,v) to MST.

Union the sets containing u and v.

Stop when MST has V-1 edges.

Return MST.

Program (in C, using disjoint-set):

#include #include #define MAX 100 struct Edge { int u, v, weight; }; struct Graph { int V, E; struct Edge* edges; }; int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } void unionSet(int parent[], int x, int y) { parent[x] = y; } int compare(const void* a, const void* b) { return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight; } void kruskal(struct Graph* g) { int parent[MAX]; for (int i = 0; i < g->V; i++) parent[i] = -1; qsort(g->edges, g->E, sizeof(g->edges[0]), compare); printf("Edges in MST:\n"); int mstEdges = 0, i = 0; while (mstEdges < g->V - 1 && i < g->E) { struct Edge e = g->edges[i++]; int x = find(parent, e.u); int y = find(parent, e.v); if (x != y) { printf("%d - %d: %d\n", e.u, e.v, e.weight); unionSet(parent, x, y); mstEdges++; } } }

Working: For graph with vertices {0,1,2,3}, edges [(0-1,1), (1-2,2), (0-2,3), (2-3,4)]:

Sort edges: [(0-1,1), (1-2,2), (0-2,3), (2-3,4)].

Pick (0-1,1): No cycle, add to MST.

Pick (1-2,2): No cycle, add.

Pick (0-2,3): Cycle detected (0,1,2 already connected), skip.

Pick (2-3,4): No cycle, add.

MST: (0-1,1), (1-2,2), (2-3,4), total weight = 7.

Complexity:

Time: O(E log E) for sorting edges + O(E log V) for union-find with path compression ≈ O(E log E).

Space: O(V) for parent array + O(E) for edge list.

Applications:

Network Design: Minimize cost in wiring or cabling (e.g., LAN setup).

Clustering: Group data points with minimal connections.

Image Segmentation: Partition pixels based on edge weights.

Significance: Efficient for sparse graphs, widely used in optimization problems.

(10 marks) Write a program to implement the 0/1 knapsack problem using dynamic programming. Explain its working and analyze its complexity.

Answer:

Definition: The 0/1 knapsack problem maximizes the total value of items placed in a knapsack of capacity W, where each item is either included fully or excluded.

Program (in C):

#include int max(int a, int b) { return a > b ? a : b; } int knapsack(int W, int wt[], int val[], int n) { int dp[n+1][W+1]; int i, w; for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i == 0 || w == 0) dp[i][w] = 0; else if (wt[i-1] <= w) dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]); else dp[i][w] = dp[i-1][w]; } } return dp[n][W]; }

Working: For items [(v=60,w=10), (v=100,w=20), (v=120,w=30)], W=50:

Initialize dp[0][w] = 0, dp[i][0] = 0.

For i=1, w=10: wt[0]=10 ≤ 10, dp[1][10] = max(60+dp[0][0], dp[0][10]) = 60.

For i=2, w=30: wt[1]=20 ≤ 30, dp[2][30] = max(100+dp[1][10], dp[1][30]) = 160.

For i=3, w=50: wt[2]=30 ≤ 50, dp[3][50] = max(120+dp[2][20], dp[2][50]) = 160.

Result: dp[3][50] = 160 (items 1 and 2).

Complexity:

Time: O(nW), filling n×W table.

Space: O(nW) for dp table (optimizable to O(W) with 1D array).

Significance: Guarantees optimal solution for discrete optimization, unlike greedy approaches.

Use: Resource allocation, budgeting, and scheduling with constraints.

Group B (40 marks)

(5 marks) Explain the role of stacks in expression evaluation.

Answer:
Definition: A stack is a LIFO (Last In, First Out) data structure used to manage operators and operands in expression evaluation.

Role:

Infix to Postfix Conversion: Stack stores operators based on precedence, outputting operands in correct order (e.g., A+B*C → ABC*+).

Postfix Evaluation: Stack pushes operands, pops them for operations, and pushes results (e.g., 23*5+: Push 2, 3, pop 3,2 for 2*3=6, push 6, push 5, pop 5,6 for 6+5=11).

Parenthesis Matching: Stack ensures balanced parentheses by pushing opening brackets and popping for closing ones.

Example: Evaluate 2*3+5 (postfix: 23*5+):

Push 2, 3; see *, pop 3,2, push 6 (2*3).

Push 5; see +, pop 5,6, push 11 (6+5).

Result: 11.

Advantages: Simplifies parsing and computation, handles precedence naturally.

Significance: Essential for compilers, calculators, and symbolic computation.

(5 marks) Write an algorithm to reverse a singly linked list.

Answer:
Algorithm:

Input: Singly linked list with head node.

Initialize pointers: prev = NULL, curr = head, next = NULL.

While curr is not NULL:

next = curr->next (save next node).

curr->next = prev (reverse link).

prev = curr (move prev forward).

curr = next (move curr forward).

Head = prev (new head after reversal).

Return head.

Program (in C):

#include #include struct Node { int data; struct Node* next; }; struct Node* reverseList(struct Node* head) { struct Node *prev = NULL, *curr = head, *next = NULL; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

Working: For list 1→2→3:

Initial: prev=NULL, curr=1, next=NULL.

Step 1: next=2, 1→NULL, prev=1, curr=2.

Step 2: next=3, 2→1, prev=2, curr=3.

Step 3: next=NULL, 3→2, prev=3, curr=NULL.

Output: 3→2→1.

Time Complexity: O(n), single pass through list.

Space Complexity: O(1), using only three pointers.

(5 marks) Discuss the significance of height-balanced trees in search operations.

Answer:
Definition: A height-balanced tree (e.g., AVL, Red-Black) maintains a height of O(log n) by ensuring the height difference between subtrees is bounded.

Significance in Search:

Efficiency: Balanced trees guarantee O(log n) search time, as height is logarithmic (e.g., AVL height ≈ 1.44 log n).

Contrast with Unbalanced: Unbalanced BSTs may degenerate to O(n) (e.g., linked list), slowing searches.

Consistency: Balancing after insertions/deletions ensures predictable performance, critical for large datasets.

Example: Search 50 in balanced BST [50,30,70]: O(log 3) ≈ 2 steps vs. O(3) in skewed tree [30→50→70].

Applications: Databases (B-trees), file systems, and dictionaries rely on balanced trees for fast lookups.

Trade-off: Balancing incurs O(log n) overhead per update but optimizes searches.

Significance: Ensures scalable performance in search-heavy systems.

(5 marks) Explain depth-first search (DFS) and its applications.

Answer:
Definition: DFS explores a graph by traversing as far as possible along each branch before backtracking, using recursion or a stack.

Algorithm:

Input: Graph G (V vertices, adjacency list), start vertex s.

Initialize visited array (all false).

Call DFS(s):

Mark s visited, process s (e.g., print).

For each unvisited neighbor v of s, call DFS(v).

Working: For graph with edges 0→1, 0→2, 1→3:

DFS(0): Visit 0, DFS(1), visit 1, DFS(3), visit 3, backtrack, DFS(2), visit 2.

Order: 0, 1, 3, 2.

Applications:

Topological Sorting: Order tasks in DAGs (e.g., course prerequisites).

Connected Components: Identify clusters in undirected graphs.

Pathfinding: Solve mazes or puzzles with backtracking.

Time Complexity: O(V + E) with adjacency list.

Significance: DFS is versatile for deep exploration and graph analysis tasks.

(5 marks) Compare bubble sort and insertion sort with their use cases.

Answer:

Bubble Sort: Repeatedly swaps adjacent elements if out of order.

Time: O(n²) worst/average, O(n) best (sorted).

Use Case: Educational purposes or tiny arrays (e.g., sorting 5 numbers).

Insertion Sort: Builds sorted portion by inserting elements into correct position.

Time: O(n²) worst/average, O(n) best (nearly sorted).

Use Case: Small or nearly sorted data (e.g., real-time updates in small lists).

Comparison:

Stability: Both are stable, preserving equal elements’ order.

Performance: Insertion sort is faster for partially sorted data; bubble sort has more swaps.

Implementation: Insertion sort is adaptive; bubble sort is simpler but less efficient.

Example: Sorting [3,1,2]: Insertion sort takes ~3 comparisons; bubble sort may take ~4 swaps.

Significance: Insertion sort is preferred for small or adaptive cases; bubble sort is rarely used practically.

(5 marks) Explain why binary search is efficient for sorted arrays.

Answer:
Definition: Binary search finds a target in a sorted array by repeatedly halving the search space.

Why Efficient:

Logarithmic Time: Each step reduces the search space by half, yielding O(log n) time (e.g., 1000 elements need ~10 steps).

Divide and Conquer: Compares mid-point, eliminating half the array based on comparison.

Contrast with Linear Search: Linear search is O(n), scanning all elements, inefficient for large data.

Example: Search 7 in [1,3,5,7,9]:

mid=2 (arr[2]=5), 7>5, search [7,9].

mid=3 (arr[3]=7), found in 2 steps.

Limitation: Requires sorted input, needing O(n log n) preprocessing if unsorted.

Significance: Ideal for static, sorted datasets like indices or lookup tables.

(5 marks) Discuss the optimal substructure property with an example.

Answer:
Definition: Optimal substructure means an optimal solution to a problem contains optimal solutions to its subproblems, enabling recursive or iterative solutions.

Example: Longest Common Subsequence (LCS):

Problem: Find the longest subsequence common to strings X and Y (e.g., X="ABCBD", Y="ABDC").

Property: If LCS(X,Y)=Z, then:

If last characters match (X[m]=Y[n]), Z includes X[m] and LCS(X[1..m-1], Y[1..n-1]).

If they differ, Z is the longer of LCS(X[1..m-1], Y) or LCS(X, Y[1..n-1]).

Execution: For "ABCBD", "ABDC", LCS("ABCB","ABD") is a subproblem solved optimally to build LCS.

Result: LCS = "ABD".

Significance: Enables dynamic programming or greedy solutions (e.g., shortest paths, knapsack).

Use: Optimizes problems like sequence alignment, graph algorithms, and resource allocation.

(5 marks) Explain how divide and conquer is used in quick sort.

Answer:
Definition: Quick sort is a divide-and-conquer sorting algorithm that partitions an array around a pivot and recursively sorts subarrays.

How Used:

Divide: Choose a pivot (e.g., last element), partition array into elements ≤ pivot and > pivot.

Conquer: Recursively sort the two subarrays (elements before and after pivot).

Combine: No explicit combine step, as partitioning sorts in-place.

Example: Sort [5,2,9,1]:

Pivot=1: Partition → [1,5,2,9].

Left empty, right=[5,2,9], pivot=9: Partition → [2,5,9].

Sort [2,5]: Pivot=5, partition → [2,5].

Result: [1,2,5,9].

Complexity:

Time: O(n log n) average, O(n²) worst (unbalanced partitions).

Space: O(log n) for recursion stack.

Significance: Fast in practice, widely used due to in-place sorting and cache efficiency.

Model Set 4

This model set mirrors the CSIT board exam format, with Group A (2 × 10 marks) and Group B (8 × 5 marks), totaling 60 marks. Questions are crafted based on past papers (2074–2078) and syllabus trends to maximize exam readiness.

Group A (20 marks)

(10 marks) Explain Huffman coding algorithm with a program to construct a Huffman tree. Analyze its complexity and discuss its applications.

Answer:

Definition: Huffman coding is a greedy algorithm that constructs an optimal prefix-free binary code for data compression, assigning shorter codes to more frequent symbols.

Algorithm:

Input: Array of characters and their frequencies.

Create a min-heap of nodes, each with a character and frequency.

While heap has more than one node:

Extract two nodes with minimum frequencies.

Create a new internal node with frequency equal to their sum, with the two nodes as children.

Insert the new node into the heap.

The remaining node is the root of the Huffman tree.

Traverse the tree to assign codes (left=0, right=1).

Program (in C, building the Huffman tree):

#include #include #define MAX 100 struct Node { char data; int freq; struct Node *left, *right; }; struct MinHeap { int size; struct Node* array[MAX]; }; struct Node* newNode(char data, int freq) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->freq = freq; node->left = node->right = NULL; return node; } void swapNode(struct Node** a, struct Node** b) { struct Node* t = *a; *a = *b; *b = t; } void heapify(struct MinHeap* heap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < heap->size && heap->array[left]->freq < heap->array[smallest]->freq) smallest = left; if (right < heap->size && heap->array[right]->freq < heap->array[smallest]->freq) smallest = right; if (smallest != idx) { swapNode(&heap->array[smallest], &heap->array[idx]); heapify(heap, smallest); } } struct Node* extractMin(struct MinHeap* heap) { struct Node* temp = heap->array[0]; heap->array[0] = heap->array[heap->size - 1]; heap->size--; heapify(heap, 0); return temp; } void insertHeap(struct MinHeap* heap, struct Node* node) { heap->size++; int i = heap->size - 1; while (i && node->freq < heap->array[(i - 1) / 2]->freq) { heap->array[i] = heap->array[(i - 1) / 2]; i = (i - 1) / 2; } heap->array[i] = node; } struct Node* buildHuffmanTree(char data[], int freq[], int n) { struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); heap->size = n; int i; for (i = 0; i < n; i++) heap->array[i] = newNode(data[i], freq[i]); for (i = n / 2 - 1; i >= 0; i--) heapify(heap, i); while (heap->size > 1) { struct Node *left = extractMin(heap); struct Node *right = extractMin(heap); struct Node *top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertHeap(heap, top); } return extractMin(heap); }

Working: For characters [A,B,C], frequencies [5,1,2]:

Create nodes: A(5), B(1), C(2).

Heap: [B(1), C(2), A(5)].

Extract B(1), C(2), combine to $(3): Tree [$3, left=B, right=C].

Heap: [$(3), A(5)].

Extract $(3), A(5), combine to $(8): Tree [$8, left=$3, right=A].

Codes: A=0, B=10, C=11.

Complexity:

Time: O(n log n) for building heap (n insertions, each O(log n)) and extracting/combining nodes (n-1 operations, each O(log n)).

Space: O(n) for heap and tree nodes.

Applications:

Data Compression: Used in ZIP, JPEG, MP3 for efficient storage.

File Archiving: Minimizes file size in tools like WinRAR.

Communication: Optimizes bandwidth in data transmission.

Significance: Achieves optimal variable-length coding, critical for efficient data handling.

(10 marks) Write a program to implement quick sort using divide and conquer. Explain its working and analyze its complexity.

Answer:

Definition: Quick sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions the array into elements less than or equal to and greater than the pivot, and recursively sorts subarrays.

Program (in C):

#include void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; int j; for (j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

Working: For array [5,2,9,1]:

Pivot=1: Partition → [1,5,2,9], pivot at index 0.

Left subarray empty, right=[5,2,9].

Pivot=9: Partition → [5,2,9], pivot at index 2.

Sort [5,2]: Pivot=2, partition → [2,5].

Result: [1,2,5,9].

Complexity:

Time: O(n log n) average (balanced partitions), O(n²) worst (sorted array, poor pivot).

Space: O(log n) average for recursion stack, O(n) worst.

Significance: Fast in-place sorting, widely used due to cache efficiency and average-case performance.

Use: General-purpose sorting in libraries (e.g., C’s qsort), sorting large datasets.

Group B (40 marks)

(5 marks) Explain the role of priority queues in event-driven simulations.

Answer:
Definition: A priority queue is a data structure where elements are dequeued based on priority (e.g., min or max value), typically implemented with a heap.

Role in Event-Driven Simulations:

Event Scheduling: Stores events (e.g., packet arrivals) with timestamps as priorities, ensuring the earliest event is processed first.

Efficiency: Min-heap allows O(log n) insertion and O(log n) extraction of next event, critical for large event sets.

Dynamic Updates: Supports adding new events or modifying existing ones (e.g., rescheduling) efficiently.

Example: In a network simulation, events [Packet1 at t=2, Packet2 at t=1, Packet3 at t=5]:

Min-heap: [t=1, t=2, t=5].

Dequeue Packet2 (t=1), process, add new event (t=3).

Update heap: [t=2, t=3, t=5].

Advantages: Ensures correct temporal order, scalable for complex simulations.

Significance: Essential for modeling systems like networks, traffic, or job scheduling.

(5 marks) Write an algorithm to merge two sorted linked lists.

Answer:
Algorithm:

Input: Two sorted linked lists, head1 and head2.

Initialize dummy node for result list, curr pointing to dummy.

While head1 and head2 are not NULL:

If head1->data ≤ head2->data:

curr->next = head1, head1 = head1->next.

Else:

curr->next = head2, head2 = head2->next.

curr = curr->next.

Attach remaining nodes: curr->next = head1 (if any) or head2 (if any).

Return dummy.next as merged list head.

Program (in C):

#include #include struct Node { int data; struct Node* next; }; struct Node* mergeLists(struct Node* head1, struct Node* head2) { struct Node dummy; struct Node* curr = &dummy; dummy.next = NULL; while (head1 && head2) { if (head1->data <= head2->data) { curr->next = head1; head1 = head1->next; } else { curr->next = head2; head2 = head2->next; } curr = curr->next; } curr->next = head1 ? head1 : head2; return dummy.next; }

Working: For lists 1→3→5 and 2→4→6:

Compare 1<2: Add 1, curr→1, head1=3→5.

Compare 3>2: Add 2, curr→2, head2=4→6.

Compare 3<4: Add 3, curr→3, head1=5.

Compare 5>4: Add 4, curr→4, head2=6.

Compare 5<6: Add 5, curr→5, head1=NULL.

Add 6: curr→6.

Output: 1→2→3→4→5→6.

Time Complexity: O(n + m), where n, m are list lengths.

Space Complexity: O(1), excluding output list.

(5 marks) Discuss the significance of B-trees in database systems.

Answer:
Definition: A B-tree is a self-balancing, m-ary tree where nodes store multiple keys and pointers, designed for disk-based storage with high fan-out.

Significance in Databases:

Efficient I/O: B-trees minimize disk I/O by storing many keys per node, reducing tree height (O(log n) with large branching factor).

Range Queries: Sorted keys enable fast range searches (e.g., SELECT * WHERE age BETWEEN 20 AND 30).

Dynamic Updates: Supports insertions/deletions in O(log n) via node splitting/merging, maintaining balance.

Example: In a database index with 1M records, a B-tree with order 100 has height ~3, needing ~3 disk reads vs. ~20 for a binary tree.

Advantages: High fan-out optimizes for disk access, unlike BSTs designed for memory.

Applications: Used in SQL databases (e.g., MySQL), file systems (e.g., NTFS), and key-value stores.

Significance: Ensures scalable performance for large-scale data retrieval and updates.

(5 marks) Explain Prim’s algorithm for minimum spanning tree and its differences from Kruskal’s.

Answer:
Prim’s Algorithm:

Definition: Greedily builds an MST by starting from a vertex and repeatedly adding the minimum-weight edge connecting the MST to an unvisited vertex.

Steps:

Initialize a min-heap with all vertices, key[start]=0, others ∞.

While heap is not empty:

Extract vertex u with minimum key.

Add u to MST.

For each neighbor v not in MST, if edge weight < key[v], update key[v].

Output: MST edges.

Differences from Kruskal’s:

Approach: Prim’s grows MST from a vertex (vertex-based); Kruskal’s selects edges globally (edge-based).

Data Structure: Prim’s uses a min-heap (O((V + E) log V)); Kruskal’s uses sorting and union-find (O(E log E)).

Graph Type: Prim’s suits dense graphs (heap efficient); Kruskal’s suits sparse graphs (fewer edges to sort).

Example: For edges (0-1,1), (1-2,2), (0-2,3):

Prim’s: Start at 0, add (0-1,1), then (1-2,2).

Kruskal’s: Sort edges, pick (0-1,1), (1-2,2).

Time Complexity: O((V + E) log V) for Prim’s with heap.

Significance: Prim’s is effective for dense graphs in network optimization.

(5 marks) Compare selection sort and merge sort with their use cases.

Answer:

Selection Sort: Repeatedly finds the minimum element and places it at the start.

Time: O(n²) worst/average/best.

Use Case: Small datasets or when writes are costly (e.g., sorting 10 elements with minimal swaps).

Merge Sort: Divides array into halves, sorts recursively, and merges sorted halves.

Time: O(n log n) worst/average/best.

Use Case: Large datasets or linked lists (e.g., external sorting of files).

Comparison:

Efficiency: Merge sort is faster for large n; selection sort is slow but simple.

Stability: Merge sort is stable; selection sort is not.

Space: Merge sort uses O(n); selection sort is in-place (O(1) extra).

Example: Sorting [5,2,9,1]: Selection sort takes ~6 comparisons; merge sort takes ~8 but scales better.

Significance: Merge sort for general-purpose sorting; selection sort for minimal writes or teaching.

(5 marks) Explain why heaps are efficient for priority queues.

Answer:
Definition: A heap is a complete binary tree where each node’s value is at least as large (max-heap) or small (min-heap) as its children’s.

Why Efficient for Priority Queues:

Fast Operations: Insert and extract-min/max are O(log n), as heap maintains partial order via heapify.

Compact Storage: Array-based implementation (e.g., parent at i, children at 2i+1, 2i+2) uses O(n) space with no pointers.

Balance: Complete binary tree ensures height O(log n), optimizing operations.

Example: Min-heap [1,3,5]: Insert 2 → [1,2,5,3], extract-min → 1, reheapify to [2,3,5].

Contrast: Unsorted list has O(1) insert but O(n) extract-min; sorted list has O(n) insert.

Significance: Heaps enable efficient scheduling and event management in systems like Dijkstra’s algorithm.

(5 marks) Discuss the overlapping subproblems property with an example.

Answer:
Definition: Overlapping subproblems occur when a recursive algorithm solves the same subproblems multiple times, making dynamic programming (DP) efficient by storing results.

Example: Matrix Chain Multiplication:

Problem: Find the minimum cost to multiply matrices A1×A2×A3 (dimensions [10×20, 20×30, 30×40]).

Subproblems: Cost of (A1×A2)×A3 vs. A1×(A2×A3) involves recomputing costs for A1×A2, A2×A3.

DP Solution: Use table dp[i][j] for cost of multiplying Ai to Aj, filling it bottom-up to avoid recomputation.

Execution: For i=1 to j=3, compute min cost, storing subproblem results (e.g., dp[1][2]).

Result: Optimal parenthesization (e.g., (A1×A2)×A3).

Significance: DP reduces time from exponential to polynomial by caching subproblem solutions.

Use: Optimizes problems like knapsack, LCS, and shortest paths.

(5 marks) Explain how binary search trees support dynamic set operations.

Answer:
Definition: A binary search tree (BST) organizes keys such that left subtree keys are smaller and right subtree keys are larger, enabling dynamic set operations.

How Supports:

Insert: Add a key by traversing to the correct position (e.g., insert 5 into [3,7] adds 5 as right child of 3), O(h) time, where h is height.

Search: Find a key by comparing with root and recursing left/right (e.g., search 7 in [3,5,7]), O(h).

Delete: Remove a key, adjusting tree (e.g., delete leaf, replace with successor for nodes with two children), O(h).

Successor/Predecessor: Find next/previous key via in-order traversal, O(h).

Example: BST [5,3,7]: Insert 4 → [5,3→4,7], search 3 → found in 2 steps.

Efficiency: O(log n) for balanced BSTs, O(n) worst case (skewed).

Significance: BSTs enable flexible data management in dictionaries, databases, and priority queues.

Model Set 5

This model set follows the CSIT board exam format, with Group A (2 × 10 marks) and Group B (8 × 5 marks), totaling 60 marks. Questions are designed based on past papers (2074–2078) and syllabus trends to ensure comprehensive exam preparation.

Group A (20 marks)

(10 marks) Explain Bellman-Ford algorithm for single-source shortest paths with a program. Analyze its complexity and discuss its applications.

Answer:

Definition: Bellman-Ford algorithm computes shortest paths from a source vertex to all vertices in a weighted graph, handling negative edge weights and detecting negative cycles.

Algorithm:

Input: Graph G (V vertices, E edges), source vertex s, weights w(u,v).

Initialize: dist[s] = 0, dist[v] = ∞ for v ≠ s.

Relax all edges V-1 times:

For each edge (u,v), if dist[u] + w(u,v) < dist[v], update dist[v] = dist[u] + w(u,v).

Check for negative cycles:

For each edge (u,v), if dist[u] + w(u,v) < dist[v], report negative cycle.

Return dist array.

Program (in C):

#include #define INF 99999 #define MAX 100 struct Edge { int u, v, weight; }; void bellmanFord(int V, int E, struct Edge edges[], int src, int dist[]) { int i, j; for (i = 0; i < V; i++) dist[i] = INF; dist[src] = 0; for (i = 1; i <= V - 1; i++) { for (j = 0; j < E; j++) { int u = edges[j].u; int v = edges[j].v; int w = edges[j].weight; if (dist[u] != INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w; } } for (j = 0; j < E; j++) { int u = edges[j].u; int v = edges[j].v; int w = edges[j].weight; if (dist[u] != INF && dist[u] + w < dist[v]) { printf("Graph contains negative cycle\n"); return; } } }

Working: For graph with vertices {0,1,2}, edges (0→1,4), (1→2,-3), (0→2,8):

Initialize: dist[0]=0, dist[1]=∞, dist[2]=∞.

Pass 1: Relax (0→1,4): dist[1]=4; (1→2,-3): dist[2]=1; (0→2,8): dist[2]=1.

Pass 2: Relax all edges, no updates (dist[2]=1 already optimal).

Check: No negative cycles.

Output: dist=[0,4,1].

Complexity:

Time: O(V * E), as V-1 passes relax E edges, plus one cycle check.

Space: O(V) for dist array.

Applications:

Network Routing: Handles negative weights in financial networks.

Cycle Detection: Detects arbitrage opportunities in currency exchange.

Traffic Systems: Models penalties in path planning.

Significance: Robust for graphs with negative weights, unlike Dijkstra’s, though slower.

(10 marks) Write a program to implement a hash table with linear probing. Explain its working and analyze its complexity.

Answer:

Definition: A hash table stores key-value pairs using a hash function to map keys to array indices, with linear probing to resolve collisions by checking the next slot.

Program (in C):

#include #define SIZE 10 #define EMPTY -1 #define DELETED -2 struct HashTable { int keys[SIZE]; int values[SIZE]; }; void initHashTable(struct HashTable* ht) { int i; for (i = 0; i < SIZE; i++) { ht->keys[i] = EMPTY; ht->values[i] = 0; } } int hash(int key) { return key % SIZE; } void insert(struct HashTable* ht, int key, int value) { int index = hash(key); int i = index; while (ht->keys[i] != EMPTY && ht->keys[i] != DELETED && i < SIZE) { i = (i + 1) % SIZE; if (i == index) { printf("Table full\n"); return; } } ht->keys[i] = key; ht->values[i] = value; } int search(struct HashTable* ht, int key) { int index = hash(key); int i = index; while (ht->keys[i] != EMPTY && i < SIZE) { if (ht->keys[i] == key) return ht->values[i]; i = (i + 1) % SIZE; if (i == index) break; } return -1; // Not found }

Working: For keys [15,25,35], hash function key%10:

Insert (15,100): hash(15)=5, slot 5 empty, store key=15, value=100.

Insert (25,200): hash(25)=5, slot 5 taken, try 6 (linear probe), store key=25, value=200.

Insert (35,300): hash(35)=5, slots 5,6 taken, try 7, store key=35, value=300.

Search 25: hash(25)=5, check 5 (15≠25), check 6 (25=25), return 200.

Complexity:

Time: O(1) average for insert/search with low load factor; O(n) worst case (clustering or full table).

Space: O(n) for table slots.

Significance: Simple collision resolution, efficient for small datasets with good hash functions.

Use: Symbol tables, caches, and small-scale databases.

Group B (40 marks)

(5 marks) Explain the role of deques in sliding window algorithms.

Answer:
Definition: A deque (double-ended queue) supports insertions and deletions at both ends, making it ideal for maintaining dynamic subsets.

Role in Sliding Window Algorithms:

Maintaining Extremes: Stores indices of elements in a window, keeping maximum/minimum at the front (e.g., for maximum in a window of size k).

Efficient Updates: Removes out-of-window elements from front and useless elements from back (e.g., smaller values when seeking max), both O(1).

Amortized O(1) Operations: Each element is pushed/popped at most once per window slide.

Example: Find max in each window of size 3 for [1,3,5,2]:

Window [1,3,5]: Deque stores indices [2] (5 is max).

Slide to [3,5,2]: Remove out-of-window, add 2, remove smaller values, deque=[2] (5 is max).

Advantages: Reduces time from O(k) per window to O(1) amortized.

Significance: Optimizes problems like maximum subarray or stock price analysis.

(5 marks) Write an algorithm to find the middle element of a singly linked list in one pass.

Answer:
Algorithm (Two-Pointer Technique):

Input: Singly linked list with head node.

Initialize two pointers: slow = head, fast = head.

While fast->next and fast->next->next are not NULL:

slow = slow->next (move one step).

fast = fast->next->next (move two steps).

Return slow->data as the middle element.

Program (in C):

#include #include struct Node { int data; struct Node* next; }; int findMiddle(struct Node* head) { struct Node *slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } return slow->data; }

Working: For list 1→2→3→4→5:

Initial: slow=1, fast=1.

Step 1: slow=2, fast=3.

Step 2: slow=3, fast=5.

Stop (fast->next NULL), slow=3.

Output: 3 (middle).

Time Complexity: O(n), single pass with fast moving twice as fast.

Space Complexity: O(1), using two pointers.

(5 marks) Discuss the significance of self-balancing trees in real-time applications.

Answer:
Definition: Self-balancing trees (e.g., AVL, Red-Black) maintain O(log n) height by adjusting structure after insertions/deletions.

Significance in Real-Time Applications:

Predictable Performance: Guarantee O(log n) for search, insert, delete, critical for time-sensitive systems.

Dynamic Updates: Handle frequent insertions/deletions efficiently, unlike static structures.

Ordered Operations: Support range queries and successor/predecessor lookups in O(log n).

Example: In a real-time inventory system, Red-Black trees maintain product IDs, enabling fast lookups and updates as stock changes.

Applications: Task schedulers, memory allocators, and real-time databases (e.g., Redis).

Trade-off: Balancing overhead is minor compared to O(n) risk of unbalanced trees.

Significance: Ensures consistent performance in dynamic, time-critical environments.

(5 marks) Explain Floyd-Warshall algorithm and its use cases.

Answer:
Definition: Floyd-Warshall algorithm computes shortest paths between all pairs of vertices in a weighted graph, handling negative weights but no negative cycles.

Algorithm:

Input: Graph as adjacency matrix adj[V][V].

Initialize dist[V][V] = adj[V][V], dist[i][i] = 0, dist[i][j] = ∞ if no edge.

For each vertex k (intermediate):

For each i,j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Return dist matrix.

Working: For graph with edges (0→1,4), (1→2,3), (0→2,8):

Initial dist: [[0,4,8], [∞,0,3], [∞,∞,0]].

k=1: Update dist[0][2] = min(8, 4+3) = 7.

Other k: No updates.

Output: [[0,4,7], [∞,0,3], [∞,∞,0]].

Use Cases:

Routing: Compute all-pairs shortest paths in networks.

Transitive Closure: Determine reachability in graphs.

Urban Planning: Optimize multi-point travel distances.

Time Complexity: O(V³), iterating over all i,j,k.

Significance: Comprehensive solution for dense graphs and all-pairs problems.

(5 marks) Compare heap sort and quick sort with their use cases.

Answer:

Heap Sort: Builds a max-heap, repeatedly extracts the maximum to sort.

Time: O(n log n) worst/average/best.

Use Case: When guaranteed O(n log n) is needed (e.g., embedded systems with fixed memory).

Quick Sort: Partitions array around a pivot, recursively sorts subarrays.

Time: O(n log n) average, O(n²) worst.

Use Case: General-purpose sorting with good average performance (e.g., sorting user data in apps).

Comparison:

Stability: Neither is stable.

Space: Heap sort uses O(1) extra; quick sort uses O(log n) for recursion.

Performance: Quick sort is faster in practice (cache-friendly); heap sort is consistent but slower due to heap operations.

Example: Sorting [5,2,9,1]: Heap sort builds heap [9,5,2,1], extracts 9,8,5,1; quick sort partitions faster on average.

Significance: Heap sort for worst-case guarantees; quick sort for typical use.

(5 marks) Explain why AVL trees are suitable for frequent lookups.

Answer:
Definition: AVL trees are self-balancing BSTs where the height difference between subtrees is at most 1, ensuring O(log n) height.

Why Suitable for Frequent Lookups:

Balanced Height: Strict balancing keeps height O(log n), minimizing search steps (e.g., ~10 steps for 1000 nodes).

Fast Search: O(log n) lookup time compared to O(n) in skewed BSTs.

Consistency: Balancing after updates ensures predictable performance, ideal for read-heavy systems.

Example: Search 50 in AVL tree [50,30,70]: 1-2 steps vs. 3 in skewed [30→50→70].

Trade-off: Slower insertions (O(log n) rotations) but optimized for lookups.

Significance: Preferred in dictionaries, indices, and lookup-intensive applications.

(5 marks) Discuss the greedy choice property in the context of fractional knapsack.

Answer:
Definition: The greedy choice property ensures that a locally optimal choice at each step yields a globally optimal solution.

Context: Fractional Knapsack:

Problem: Maximize value in a knapsack of capacity W, allowing fractional items.

Greedy Choice: Select items with the highest value-to-weight ratio (v/w).

Execution: Items [(v=60,w=10), (v=100,w=20), (v=120,w=30)], W=50:

Sort by v/w: [6,5,4].

Take (60,10) fully (W=40, v=60).

Take (100,20) fully (W=20, v=160).

Take (120,30) fractionally (20/30, v=160+80=240).

Correctness: Highest v/w maximizes value per unit weight, filling capacity optimally.

Significance: Unlike 0/1 knapsack, fractional knapsack’s greedy approach is optimal due to divisibility.

Use: Resource allocation, cargo loading, and scheduling with divisible tasks.

(5 marks) Explain how dynamic programming optimizes the longest common subsequence problem.

Answer:
Definition: The longest common subsequence (LCS) problem finds the longest sequence common to two strings (e.g., "ABCD" and "ACFD" have LCS "ACD").

Why Dynamic Programming:

Overlapping Subproblems: Recursive LCS(X[1..m],Y[1..n]) recomputes LCS for prefixes (e.g., X[1..m-1],Y[1..n-1]).

Optimal Substructure: LCS of X,Y builds on LCS of prefixes.

DP Solution: Use table dp[m+1][n+1] to store lengths, avoiding recomputation.

Program (in C):

#include #include int lcs(char* X, char* Y, int m, int n) { int dp[m+1][n+1]; int i, j; for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) dp[i][j] = 0; else if (X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]; } } return dp[m][n]; }

Working: For X="ABCD", Y="ACFD":

dp[1][1]: A=A, dp[1][1]=1.

dp[2][2]: B≠F, dp[2][2]=max(dp[1][2],dp[2][1])=1.

dp[4][4]: D=D, dp[4][4]=dp[3][3]+1=3.

Output: 3 (LCS="ACD").

Complexity: O(mn) time, O(mn) space vs. O(2^{m+n}) for recursion.

Significance: DP makes LCS tractable for large strings in bioinformatics and text comparison.

Progress Tracker

Unit Score Coverage

Unit 1 0 12.5%

Total Score: 0/80

Coverage: 0%

Unit	Score	Coverage
Unit 1	0	12.5%

Exclusive Study Content Just for You!

Me dropping premium study resources you won't find anywhere else—completely free! Even the god behind this (me truly) can't fail you now—haha, just kidding! But seriously, this treasure comes with a small price: your loyalty and friendship. Join my vibe, connect with us, and follow along on socials to keep the learning party going!

Follow Us!

Progress Overview

Total Score: 0/80

Coverage: 0%