BSc CSIT 3rd Semester Data Structures and Algorithms (CSC211): Complete Notes, Algorithms, C Programs, Complexity Analysis & Exam Guide

Introduction

Data Structures and Algorithms is the course that separates programmers who can write code from engineers who can write good code. Every interview at a tech company — from a startup to Google — tests exactly what this course covers. But beyond interviews and exams, DSA is the mental framework that determines whether you reach for the right tool when solving a real problem: whether you instinctively know that this problem needs a tree, that one needs a hash table, and that one needs a stack.

CSC211 appears in the 3rd semester of BSc CSIT at Tribhuvan University, and it's the point in the curriculum where programming stops being about syntax and starts being about thinking. You already know how to write C programs from the first semester. DSA teaches you to write programs that work efficiently — that don't slow down as input size grows, that use memory carefully, and that solve genuinely complex problems through structured logic.

This course directly feeds into nearly every advanced course and every technical interview you'll ever take. Sorting, searching, trees, graphs, and hashing are not textbook-only concepts — they're the implementation details hidden inside every database, every search engine, every route-finding app, every compiler. When you study DSA properly, you're learning how the software you use every day actually works.

For TU exams specifically, DSA rewards students who understand algorithms well enough to trace through them step by step with a given input. Unlike theory-only subjects, DSA exam questions typically ask you to write C code, trace an algorithm with example data, or analyze time complexity — all skills that require actual practice, not just reading.

Official Course Information

Particular	Details
Course Title	Data Structure and Algorithm
Course Code	CSC211
Semester	Third Semester
Nature of Course	Theory + Lab
Full Marks	60 + 20 + 20
Pass Marks	24 + 8 + 8
Credit Hours	3

Text Book: Y. Langsam, MJ Augenstein, AM Tanenbaum — Data Structures using C and C++, Prentice Hall India, 2nd Edition Reference Books: Leen Ammeral — Programs and Data Structures in C; G.W. Rowe — Introduction to Data Structure and Algorithms with C and C++; R.L. Kruse, B.P. Leung, C.L. Tondo — Data Structure and Program Design in C

Official Unit-Wise Syllabus Overview

Unit	Title	Hours
1	Introduction	4
2	Stack	4
3	Queue	4
4	Recursion	4
5	Lists	8
6	Sorting	8
7	Searching and Hashing	7
8	Trees and Graphs	8

Units 5 (Lists), 6 (Sorting), 7 (Searching/Hashing), and 8 (Trees and Graphs) each carry 7–8 hours and dominate the exam. Unit 8 alone covers BST, AVL trees, graph traversals, Minimum Spanning Trees, and Dijkstra's algorithm — plan more revision time here than any other unit.

---

Algorithm Complexity Cheat Sheet

Students constantly search for this, so here it is upfront as a reference. All complexities assume n = input size.

Sorting Algorithm Complexities

Algorithm	Best Case	Average Case	Worst Case	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Shell Sort	O(n log n)	Depends on gap	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)

Searching Algorithm Complexities

Algorithm	Best Case	Average Case	Worst Case
Linear Search	O(1)	O(n)	O(n)
Binary Search	O(1)	O(log n)	O(log n)

Data Structure Operation Complexities

Data Structure	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)
Singly Linked List	O(n)	O(n)	O(1) at head	O(1) at head
Stack	O(n)	O(n)	O(1) push	O(1) pop
Queue	O(n)	O(n)	O(1) enqueue	O(1) dequeue
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
BST (worst)	O(n)	O(n)	O(n)	O(n)
Hash Table (avg)	—	O(1)	O(1)	O(1)
Hash Table (worst)	—	O(n)	O(n)	O(n)

---

Unit 1: Introduction (4 Hrs)

Data Types, Data Structures, and ADTs

A data type defines a set of values and the operations that can be performed on them. An int in C is a data type — it holds integer values and supports arithmetic operations.

A data structure is a way of organizing and storing data in memory so it can be accessed and modified efficiently. It's not just about what the data is, but how it's arranged. The same information (a list of names) stored as an array and as a linked list will have different performance characteristics for different operations.

An Abstract Data Type (ADT) describes a data structure by what it does — its operations and their behavior — without specifying how it's implemented. A Stack ADT says: you can push, pop, and peek, and it follows LIFO order. Whether the underlying implementation uses an array or a linked list is an implementation detail hidden from the user of the ADT.

Linear vs. Non-Linear Structures:

• Linear: Elements arranged in sequence. Each element has exactly one predecessor and one successor (except at ends). Examples: Array, Linked List, Stack, Queue.
• Non-Linear: Elements arranged without a strict sequence. One element can connect to many. Examples: Tree, Graph.

Dynamic Memory Allocation in C

Static allocation (declaring int arr[100]) fixes size at compile time. Dynamic allocation lets you request memory at runtime — exactly the amount you need.

#include <stdlib.h>

/* Allocate memory for a node */
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
if (newNode == NULL) {
    printf("Memory allocation failed");
    exit(1);
}

/* Always free when done */
free(newNode);

malloc(size) returns a void pointer to the allocated memory, or NULL if allocation fails. Always check for NULL. Always call free() when the memory is no longer needed to avoid memory leaks. Dynamic allocation is essential for linked lists, trees, and graphs — any structure whose size isn't known at compile time.

Algorithms and Asymptotic Notation

An algorithm is a finite, step-by-step procedure for solving a problem. A good algorithm is correct (produces right output), efficient (uses minimal time and space), and clear (unambiguous steps).

Asymptotic notation describes how an algorithm's resource usage scales as input size grows — ignoring constants and lower-order terms because we care about behavior at large scale.

• O (Big-O): Upper bound — worst-case growth rate. O(n²) means in the worst case, time grows as a quadratic function of n.
• Ω (Omega): Lower bound — best-case growth rate.
• Θ (Theta): Tight bound — both upper and lower. O and Ω are the same function.

Common growth rates (slowest to fastest): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

An algorithm with O(1) is ideal — constant time regardless of input size. O(n²) algorithms become impractically slow for large inputs (sorting a million records with bubble sort would require a trillion operations).

Important Questions — Unit 1

1. What is a data structure? Differentiate between linear and non-linear data structures.
2. Define Abstract Data Type (ADT). Why is ADT important in data structure design?
3. Explain asymptotic notations (O, Ω, Θ) with examples.
4. Differentiate between algorithm and program.
5. Explain dynamic memory allocation in C with malloc and free.

---

Unit 2: Stack (4 Hrs)

Concept and ADT

A stack is a linear data structure following the LIFO (Last In, First Out) principle. Think of a stack of plates — you add to the top and remove from the top. The last plate placed is the first one taken.

Stack Operations:

• Push: Add an element to the top
• Pop: Remove the element from the top
• Peek/Top: View the top element without removing it
• isEmpty: Check if stack is empty
• isFull: Check if stack is full (array implementation)

C Implementation of Stack (Array)

#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1;

void push(int item) {
    if (top == MAX - 1) { printf("Stack Overflow\n"); return; }
    stack[++top] = item;
}

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

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

int isEmpty() { return top == -1; }

Infix to Postfix Conversion

This is one of the most commonly examined stack applications. Infix notation (A + B) is how humans write expressions; postfix notation (AB+) eliminates the need for parentheses and is easier for computers to evaluate.

Algorithm:

1. Scan expression left to right
2. If operand (number/variable): output it directly
3. If (: push to stack
4. If ): pop and output until ( is found
5. If operator: pop and output operators of higher or equal precedence, then push current operator
6. After scanning: pop and output all remaining operators

Operator precedence: ^ > * / > + -

Solved Example: Convert A + B * C - D to postfix

Character	Stack	Output
A		A
+	+	A
B	+	AB
*	+ *	AB
C	+ *	ABC
-	-	ABC*+
D	-	ABC*+D
End		ABC*+D-

Result: ABC*+D-

Applications of Stack

• Expression conversion and evaluation (infix → postfix → evaluate)
• Function call management (call stack in recursion)
• Undo operations in editors
• Backtracking algorithms
• Browser history (back button)

Important Questions — Unit 2

1. Define stack. Explain push and pop operations with diagrams.
2. Convert infix expression (A+B)*(C-D)/E to postfix with trace table.
3. Evaluate postfix expression 523*+4- showing stack trace.
4. Write C program to implement stack using array.
5. List and explain applications of stack.

---

Unit 3: Queue (4 Hrs)

Concept and ADT

A queue is a linear data structure following the FIFO (First In, First Out) principle — like a line at a ticket counter. The first person who joins the queue is the first to be served.

Queue Operations:

• Enqueue: Add element to the rear
• Dequeue: Remove element from the front
• Front/Peek: View the front element
• isEmpty: Check if queue is empty

Types of Queue

Linear Queue: Basic implementation with fixed front and rear pointers. Problem: even when space is freed at the front by dequeue operations, it cannot be reused — the queue appears "full" even when it isn't.

Circular Queue: Solves the wasted space problem by wrapping around. When rear reaches the end, it wraps to index 0 (if front isn't there). rear = (rear + 1) % MAX

Priority Queue: Elements have priorities; the element with the highest priority is dequeued first regardless of insertion order. Used in Dijkstra's algorithm and CPU scheduling.

Double-Ended Queue (Deque): Insertion and deletion allowed at both ends. Can act as both a stack and a queue.

Circular Queue — C Implementation

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int item) {
    if ((rear + 1) % MAX == front) { printf("Queue Full\n"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    queue[rear] = item;
}

int dequeue() {
    if (front == -1) { printf("Queue Empty\n"); return -1; }
    int item = queue[front];
    if (front == rear) { front = rear = -1; }
    else front = (front + 1) % MAX;
    return item;
}

Applications of Queue

• CPU scheduling (process scheduling)
• Printer spooling
• BFS graph traversal
• Buffering in data streams
• Breadth-first search

Important Questions — Unit 3

1. Define queue. Differentiate between stack and queue.
2. Explain circular queue. Why is it preferred over linear queue?
3. Write C program to implement circular queue.
4. Explain priority queue and its applications.
5. What is Deque? How does it differ from ordinary queue?

---

Unit 4: Recursion (4 Hrs)

Principle of Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two essential parts:

1. Base case: The simplest version of the problem that can be solved directly (stops the recursion)
2. Recursive case: The function reduces the problem and calls itself

Without a base case, recursion runs infinitely (stack overflow).

Classic Recursive Algorithms

Factorial:

int factorial(int n) {
    if (n == 0 || n == 1) return 1;   /* base case */
    return n * factorial(n - 1);       /* recursive case */
}
/* factorial(4) = 4 * factorial(3) = 4 * 3 * 2 * 1 = 24 */

Fibonacci:

int fibonacci(int n) {
    if (n <= 1) return n;             /* base cases: fib(0)=0, fib(1)=1 */
    return fibonacci(n-1) + fibonacci(n-2);
}
/* Note: This has O(2ⁿ) time complexity — exponential. */
/* Use dynamic programming or iteration for large n. */

GCD (Euclidean Algorithm):

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
/* gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6 */

Tower of Hanoi:

Move n disks from source peg to destination peg using auxiliary peg, following the rule: never place a larger disk on a smaller one.

void hanoi(int n, char source, char dest, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, dest);
        return;
    }
    hanoi(n-1, source, aux, dest);   /* move n-1 disks to aux */
    printf("Move disk %d from %c to %c\n", n, source, dest);
    hanoi(n-1, aux, dest, source);   /* move n-1 disks from aux to dest */
}

For n disks, Tower of Hanoi requires 2ⁿ - 1 moves. Time complexity: O(2ⁿ).

Recursion vs Iteration

Aspect	Recursion	Iteration
Approach	Function calls itself	Uses loops
Memory	Stack frame per call (O(n) stack space for depth n)	Usually O(1) extra space
Readability	Often clearer for naturally recursive problems	Clearer for simple repetition
Speed	Overhead from function calls	Generally faster
Risk	Stack overflow for very deep recursion	Infinite loop if condition wrong

Tail Recursion: When the recursive call is the very last operation. Some compilers optimize tail recursion into iteration (tail-call optimization), eliminating the stack overhead.

Important Questions — Unit 4

1. What is recursion? Explain with factorial example.
2. Write a recursive C program for Tower of Hanoi. Explain with n=3.
3. Differentiate between recursion and iteration.
4. Write recursive programs for GCD and Fibonacci.
5. What is tail recursion? How does it differ from regular recursion?

---

Unit 5: Lists (8 Hrs)

Array vs Linked List

Before diving into linked lists, understanding why they exist matters. Arrays are fast at random access (arr[5] is instant) but slow at insertion and deletion in the middle (everything after must shift). They also have fixed size. Linked lists solve both problems at the cost of sequential-only access.

Aspect	Array	Linked List
Memory	Contiguous blocks	Non-contiguous, scattered
Size	Fixed at declaration	Dynamic, grows/shrinks
Random Access	O(1)	O(n)
Insertion at beginning	O(n) — shift all elements	O(1) — update pointers
Deletion at beginning	O(n) — shift all elements	O(1) — update pointer
Memory overhead	None	Extra pointer per node

Types of Linked List

Singly Linked List: Each node has data and a pointer to the next node. The last node points to NULL.

[10|→] → [20|→] → [30|→] → [40|NULL]

Doubly Linked List: Each node has data, a next pointer, and a previous pointer.

NULL←[10|→] ⇄ [20|→] ⇄ [30|→] ⇄ [40|NULL]

Circular Linked List: The last node's next pointer points back to the first node (no NULL terminator).

Singly Linked List — C Implementation

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

/* Insert at beginning */
struct Node* insertBeginning(struct Node* head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    return newNode;   /* new node becomes the head */
}

/* Insert at end */
void insertEnd(struct Node* head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (head == NULL) { head = newNode; return; }
    struct Node* temp = head;
    while (temp->next != NULL) temp = temp->next;
    temp->next = newNode;
}

/* Delete from beginning */
struct Node* deleteBeginning(struct Node* head) {
    if (head == NULL) { printf("Empty list\n"); return NULL; }
    struct Node* temp = head;
    head = head->next;
    free(temp);
    return head;
}

/* Traverse and print */
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d → ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

Stack and Queue as Linked Lists

Implementing Stack and Queue using linked lists removes the size limitation of array-based implementations:

Stack using Linked List: Push = insertBeginning, Pop = deleteBeginning. Both O(1).

Queue using Linked List: Maintain both head (front) and tail (rear) pointers. Enqueue = insert at tail, Dequeue = delete at head. Both O(1).

Important Questions — Unit 5

1. Differentiate between array and linked list implementation of lists.
2. Explain types of linked lists with diagrams.
3. Write C program to insert at beginning, end, and specified position in a singly linked list.
4. Write C program to delete a node from a specified position in a linked list.
5. Explain how stack and queue can be implemented using linked lists.

---

Unit 6: Sorting (8 Hrs)

Sorting is the process of arranging elements in ascending or descending order. Understanding each algorithm's behavior — not just its code — is what the exam tests.

Bubble Sort

Compare adjacent elements and swap if out of order. Largest elements "bubble" to the end.

Trace example — sort [64, 34, 25, 12, 22]:

• Pass 1: [34, 25, 12, 22, 64]
• Pass 2: [25, 12, 22, 34, 64]
• Pass 3: [12, 22, 25, 34, 64]
• Pass 4: [12, 22, 25, 34, 64]

Key: Best case O(n) when already sorted (with early exit optimization).

Selection Sort

Find the minimum element and place it at the beginning. Repeat for remaining unsorted portion.

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        /* swap arr[minIdx] with arr[i] */
        int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp;
    }
}

Key: Always O(n²) — makes fewer swaps than bubble sort but same number of comparisons.

Insertion Sort

Build sorted array one element at a time. Each new element is inserted into its correct position in the already-sorted portion.

Key: Best case O(n) for nearly-sorted arrays. Efficient in practice for small datasets.

Merge Sort

Divide and conquer: split array in half, recursively sort each half, merge the two sorted halves.

[38, 27, 43, 3]
     ↙        ↘
[38, 27]    [43, 3]
  ↙   ↘      ↙   ↘
[38] [27] [43] [3]
  ↘   ↙      ↘  ↙
[27, 38]    [3, 43]
       ↘   ↙
   [3, 27, 38, 43]

Key: Always O(n log n). Requires O(n) extra space. Stable sort (equal elements maintain relative order).

Quick Sort

Divide and conquer: choose a pivot, partition so elements less than pivot are left, greater are right, recursively sort both partitions.

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
    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);
    }
}

Key: Average O(n log n), worst case O(n²) when pivot is always smallest/largest. In-place (O(log n) stack space). Usually fastest in practice.

Heap Sort

Build a max-heap from the array, then repeatedly extract the maximum and place at the end.

Key: Always O(n log n). In-place. Not stable.

Important Questions — Unit 6

1. Explain bubble sort with trace table for [5, 3, 8, 4, 2].
2. Write Quick Sort algorithm. What is its best, worst, and average case complexity?
3. Explain merge sort with diagram. Why is it preferred over quick sort in some cases?
4. Write C program for insertion sort.
5. Compare all sorting algorithms on: best/worst/average complexity, space complexity, stability.

---

Unit 7: Searching and Hashing (7 Hrs)

Linear Search

Scan every element until the target is found or the array ends. O(n) worst case.

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++)
        if (arr[i] == target) return i;
    return -1;  /* not found */
}

Binary Search

Requires sorted array. Repeatedly halve the search space by comparing target with the middle element.

Solved Example — Search for 35 in [10, 20, 35, 50, 60, 75, 90]:

Step	Low	High	Mid	arr[mid]	Action
1	0	6	3	50	35 < 50 → search left
2	0	2	1	20	35 > 20 → search right
3	2	2	2	35	Found at index 2

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Time complexity: O(log n) — each comparison eliminates half the remaining elements.

Hashing

Hashing maps keys to array indices using a hash function, enabling average O(1) insertion and lookup.

Hash Function: h(key) = key % tableSize

Example: Insert keys 18, 26, 35, 9 into a table of size 7:

• 18 % 7 = 4 → index 4
• 26 % 7 = 5 → index 5
• 35 % 7 = 0 → index 0
• 9 % 7 = 2 → index 2

Collision: Two keys map to the same index. Must be resolved.

Collision Resolution Techniques:

Technique	Method	Advantage	Disadvantage
Chaining	Each index holds a linked list of all keys mapping there	Never table gets "full"	Extra memory for pointers
Open Addressing	Find another empty slot using a probing sequence	No extra memory	Performance degrades at high load
Linear Probing	Check next slot, then next, linearly	Simple	Clustering problem
Quadratic Probing	Check slots at 1², 2², 3² intervals	Reduces primary clustering	Secondary clustering
Double Hashing	Use second hash function to determine step size	Minimizes clustering	More computation

Load Factor = (number of elements) / (table size). Performance degrades significantly when load factor exceeds 0.7.

Important Questions — Unit 7

1. Explain binary search with a solved trace table example.
2. Compare linear search and binary search on time complexity, requirements, and use case.
3. What is hashing? Explain hash functions with examples.
4. Explain collision resolution: chaining and open addressing.
5. Write C program for binary search.

---

Unit 8: Trees and Graphs (8 Hrs)

Binary Trees

A tree is a hierarchical data structure. A binary tree is one where each node has at most two children (left and right).

Key terminology:

• Root: Top node (no parent)
• Leaf: Node with no children
• Height: Length of longest path from root to leaf
• Level: Distance from root (root is level 0)
• Complete binary tree: All levels full except possibly the last, filled left to right
• Full binary tree: Every node has 0 or 2 children

Tree Traversals

All three traversal orders visit every node exactly once:

         1
        / \
       2   3
      / \
     4   5

• Inorder (Left → Root → Right): 4, 2, 5, 1, 3 ← gives sorted order for BST
• Preorder (Root → Left → Right): 1, 2, 4, 5, 3
• Postorder (Left → Right → Root): 4, 5, 2, 3, 1
• Level Order (BFS): 1, 2, 3, 4, 5

void inorder(struct Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

Binary Search Tree (BST)

A BST maintains the property: for every node, all values in the left subtree are less, all values in the right subtree are greater.

BST Insertion trace — insert 5, 3, 7, 1, 4 in sequence:

5

Insert 3: 3 < 5, go left → left child of 5 Insert 7: 7 > 5, go right → right child of 5 Insert 1: 1 < 5 go left, 1 < 3 go left → left child of 3 Insert 4: 4 < 5 go left, 4 > 3 go right → right child of 3

BST Search: O(log n) average, O(n) worst case (degenerate/skewed tree — all insertions go one direction).

Inorder traversal of a BST gives sorted output.

AVL Tree

An AVL tree is a self-balancing BST. After every insertion or deletion, it checks the balance factor of each node (balance factor = height of left subtree − height of right subtree). If the balance factor becomes −2 or +2, rotations are applied to restore balance.

Four rotation cases:

• LL Rotation (Right Rotation): New node inserted in left subtree of left child.
• RR Rotation (Left Rotation): New node inserted in right subtree of right child.
• LR Rotation: New node inserted in right subtree of left child. (Left rotate, then right rotate)
• RL Rotation: New node inserted in left subtree of right child. (Right rotate, then left rotate)

AVL trees guarantee O(log n) for all operations by keeping the tree balanced.

Graphs

A graph G = (V, E) consists of a set of vertices V and edges E connecting them. Unlike trees, graphs can have cycles and can be disconnected.

Directed vs Undirected: Directed (digraph) edges have direction (A→B ≠ B→A). Undirected edges are bidirectional.

Graph Representation:

• Adjacency Matrix: 2D array where matrix[i][j] = 1 if edge exists. O(V²) space.
• Adjacency List: Each vertex stores list of its neighbors. O(V+E) space. Efficient for sparse graphs.

BFS and DFS

BFS (Breadth-First Search): Visit all neighbors at current distance before going deeper. Uses a Queue.

BFS on graph with adjacency {1:[2,3], 2:[4], 3:[4,5], 4:[], 5:[]} starting at 1:

• Start: Queue=[1], Visited={1}
• Process 1: Enqueue 2,3 → Queue=[2,3], Output: 1
• Process 2: Enqueue 4 → Queue=[3,4], Output: 1 2
• Process 3: Enqueue 5 → Queue=[4,5], Output: 1 2 3
• Process 4: Queue=[5], Output: 1 2 3 4
• Process 5: Queue=[], Output: 1 2 3 4 5

BFS Time Complexity: O(V+E)

DFS (Depth-First Search): Go as deep as possible before backtracking. Uses a Stack (or recursion).

void DFS(int graph[][MAX_V], int visited[], int v, int numV) {
    visited[v] = 1;
    printf("%d ", v);
    for (int i = 0; i < numV; i++)
        if (graph[v][i] == 1 && !visited[i])
            DFS(graph, visited, i, numV);
}

Minimum Spanning Trees

A spanning tree of a graph includes all vertices with the minimum number of edges (V−1) forming a tree. A Minimum Spanning Tree (MST) minimizes total edge weight.

Kruskal's Algorithm:

1. Sort all edges by weight (ascending)
2. Add edge to MST if it doesn't form a cycle (use Union-Find to detect cycles)
3. Repeat until MST has V−1 edges

Prim's Algorithm:

1. Start from any vertex
2. Repeatedly add the minimum-weight edge connecting the MST to a new vertex
3. Continue until all vertices are included

Time Complexity: Kruskal's O(E log E). Prim's O(V²) basic, O(E log V) with priority queue.

Dijkstra's Shortest Path Algorithm

Finds the shortest path from a source vertex to all other vertices in a weighted graph (non-negative weights).

Solved Example: Graph with vertices A,B,C,D, weights: A-B:4, A-C:2, B-C:1, B-D:5, C-D:8

Source: A

Step	Visited	dist[A]	dist[B]	dist[C]	dist[D]
Initial	{}	0	∞	∞	∞
Visit A	{A}	0	4	2	∞
Visit C (min=2)	{A,C}	0	3	2	10
Visit B (min=3)	{A,C,B}	0	3	2	8
Visit D (min=8)	{A,C,B,D}	0	3	2	8

Shortest paths from A: B=3, C=2, D=8. Time Complexity: O(V²) basic.

Important Questions — Unit 8

1. Define binary tree. Explain inorder, preorder, and postorder traversals with diagrams.
2. What is a BST? Insert elements [5,3,7,1,4] and show resulting tree.
3. Explain AVL tree. Show how rotations restore balance with an example.
4. Differentiate between BFS and DFS. Trace BFS on a given graph.
5. Explain Kruskal's and Prim's algorithms for minimum spanning tree.
6. Explain Dijkstra's algorithm with a step-by-step solved example.
7. Explain collision resolution techniques in hashing.

---

Past Paper Analysis (TU CSC211 Exam Patterns)

Appears almost every year:

• Stack operations + infix to postfix conversion with trace
• BST — insertion and traversal (inorder gives sorted output)
• Sorting algorithm comparison table (time complexities)
• BFS or DFS trace on a given graph
• Linked list operations (insertion, deletion with diagrams)
• Binary search with trace table
• AVL tree and rotations
• Hashing and collision resolution

Frequently appears:

• Tower of Hanoi (write program + explain for n=3)
• Merge sort or quick sort trace
• Queue types (circular queue explanation + implementation)
• Recursion vs iteration comparison
• Dijkstra's shortest path

Occasionally appears:

• Prim's vs Kruskal's algorithm comparison
• Shell sort
• Double-ended queue (Deque)
• Dynamic memory allocation in C

Rarely appears as standalone long question:

• Tail recursion specifics
• External vs internal sorting distinction

---

Study Plans

30-Day Plan

• Days 1–4: Unit 1 — ADT, dynamic memory allocation, asymptotic notation
• Days 5–8: Units 2–3 — Stack (push/pop + infix to postfix), Queue types
• Days 9–12: Unit 4 — Recursion (factorial, Fibonacci, TOH, GCD)
• Days 13–18: Unit 5 — Linked list (all types, all operations, C programs)
• Days 19–23: Unit 6 — All sorting algorithms with trace tables and complexities
• Days 24–27: Unit 7 — Binary search (trace), hashing, collision resolution
• Days 28–30: Unit 8 — BST, AVL, BFS/DFS, MST, Dijkstra + past question practice

15-Day Plan

• Days 1–2: Units 1–2
• Days 3–4: Units 3–4
• Days 5–7: Unit 5 (linked list — write programs, don't just read)
• Days 8–10: Unit 6 (sorting — do trace tables for at least 3 algorithms)
• Days 11–12: Unit 7
• Days 13–15: Unit 8 (most content, most exam weight — spread across 3 days)

7-Day Plan

• Day 1: Units 1–3 (intro, stack with infix-postfix, queue types)
• Day 2: Unit 4 + Unit 5 overview (recursion + linked list types)
• Day 3: Unit 5 in depth (linked list C programs)
• Day 4: Unit 6 (sorting — trace bubble, quick, merge)
• Day 5: Unit 7 (binary search trace + hashing)
• Day 6: Unit 8 — Trees (BST, AVL, traversals)
• Day 7: Unit 8 — Graphs (BFS, DFS, Dijkstra) + complexity cheat sheet

Night Before Exam

• Redo infix-to-postfix trace once with a parenthesized expression.
• Write BST insertion sequence and confirm inorder gives sorted output.
• Scan the sorting complexity table — worst case of quick sort (O(n²)) vs merge sort (always O(n log n)) is a common short-answer trap.
• Trace BFS or DFS on a simple 5-node graph once to keep the procedure fresh.
• Don't attempt new topics — focus on what you've already practiced.

---

Common Mistakes Students Make

The most frequent marks lost in DSA exams:

Infix to postfix: Operator precedence errors (* before +) or forgetting to pop remaining stack operators at the end.

BST confusion: Assuming BST operations are always O(log n). For skewed trees (sorted insertions), all operations degrade to O(n) — this is why AVL trees exist.

Stack overflow in recursion: Students write correct recursive logic but forget the base case or write it incorrectly, causing infinite recursion. Always identify the base case first.

Bubble sort "optimization": Many students memorize O(n²) for all cases but the optimized bubble sort (with early exit) achieves O(n) for already-sorted arrays. The exam may test this.

Hashing index collision: When demonstrating chaining vs open addressing, students often skip showing what happens when a second key maps to the same index. Show the collision explicitly.

Graph traversal order: BFS gives level-order traversal (queue-based); DFS gives depth-first order (stack/recursion-based). Mixing these up when tracing is a common error.

---

Quick Revision Sheet

Concept	Key Fact
Stack	LIFO — Last In First Out
Queue	FIFO — First In First Out
Linked List advantage	Dynamic size, O(1) insert/delete at known position
Array advantage	O(1) random access
BST inorder	Always gives sorted ascending order
AVL balance factor	-1, 0, or +1 — any other value triggers rotation
BFS uses	Queue
DFS uses	Stack (or recursion)
Merge Sort space	O(n) extra
Quick Sort space	O(log n) stack
Binary Search requires	Sorted array
Hash table average	O(1) insert/search
Dijkstra works with	Non-negative weights only
Tower of Hanoi moves	2ⁿ - 1 for n disks

---

Frequently Asked Questions

Is DSA difficult for BSc CSIT students? DSA has a steeper learning curve than most first-semester subjects because it requires both understanding and practice. Students who only read algorithms without tracing them through examples consistently struggle in the exam. The ones who practice tracing and writing code find it much more manageable.

Which chapters are most important? Trees and Graphs (Unit 8), Lists (Unit 5), and Sorting (Unit 6) carry the most teaching hours and exam weight. Within those, BST operations, linked list programs, infix-to-postfix conversion, and Dijkstra's algorithm are almost guaranteed to appear.

Is DSA useful for placements? It's arguably the most placement-relevant course in the entire BSc CSIT curriculum. Every technical interview at software companies — from small firms to Google — tests DSA concepts. Arrays, linked lists, trees, graphs, sorting, and searching are the literal syllabus of technical interviews.

How many programs should I practice for the DSA exam? At minimum: linked list insertion/deletion, stack push/pop, circular queue, binary search, and BST insertion and traversal. Bubble sort and quick sort in C are also worth having memorized.

What is the best book for TU CSC211 DSA? The official text is Data Structures using C and C++ by Langsam, Augenstein, and Tanenbaum. For supplementary practice, Data Structures and Algorithms Made Easy by Narasimha Karumanchi is very accessible.

Can I pass by studying only important questions? You can pass by focusing on high-frequency topics, but DSA questions require you to actually execute algorithms and trace through examples — not just reproduce a memorized answer. Practice is non-negotiable.

Why does quick sort's worst case reach O(n²)? When the pivot is always the smallest or largest element (e.g., sorted input with last-element pivot), every partition creates one subarray of size n-1 and one of size 0, leading to n levels of recursion — the same as a quadratic algorithm.

What's the difference between Kruskal's and Prim's for MST? Kruskal's sorts all edges and adds them one by one if they don't form a cycle (edge-centric). Prim's grows the MST from a starting vertex by always adding the cheapest edge connecting the existing MST to a new vertex (vertex-centric). Both produce a valid MST; Prim's is better for dense graphs, Kruskal's for sparse.

---

Conclusion

Data Structures and Algorithms is the course that your entire software engineering career is built on. The understanding of how data is organized and how algorithms process it efficiently — the core of this course — shows up in every technical interview, every system design decision, and every performance optimization you'll ever make.

For the TU exam, the combination that works is: understand each data structure's properties conceptually, practice tracing algorithms through given examples step by step (especially BST, BFS/DFS, sorting, and Dijkstra's), and write the key C programs until they come naturally. The complexity cheat sheet and quick revision section are designed for the final days before the exam.

This guide covers the complete CSC211 syllabus based on official TU course content and consistent past paper analysis. Bookmark it and return to the complexity tables and trace examples during revision.

For related subjects, see: C Programming (CSC115) Complete Guide, Introduction to Information Technology (CSC114) Complete Guide, Digital Logic (CSC116) Complete Guide, Computer Networks (CSC263) Complete Guide, Mathematics-I (MTH117) Complete Guide, and Cryptography (CSC316) Complete Guide.