Index
1. Matrix Operations using Functions
1.1 Addition
1.2 Subtraction
1.3 Multiplication
1.4 Transpose
2. Searching Algorithms
2.1 Linear Search
2.2 Binary Search
3. String Operations
3.1 Concatenation
3.2 Comparison
3.3 Length Calculation
3.4 Palindrome Check
3.5 Substring
4. Stack and Queue Operations
4.1 Stack (Push, Pop, Peek)
4.2 Queue (Enqueue, Dequeue)
4.3 Circular Queue
1
5. Linked List
5.1 Singly Linked List (Insertion, Deletion, Traversal)
5.2 Doubly Linked List
5.3 Circular Linked List
6. Searching & Sorting
6.1 Bubble Sort
6.2 Insertion Sort
6.3 Quick Sort
6.4 Merge Sort
7. Trees
7.1 Binary Search Tree (BST) Operations
7.2 B-Tree Operations
7.3 AVL Tree Operations
8. Graphs
8.1 Representation (Adjacency Matrix/List)
8.2 Breadth First Search (BFS)
8.3 Depth First Search (DFS)
2
1. Matrix Operations using Functions
1.1 Addition
Algorithm / Approach
1. Input dimensions of matrices.
2. Input elements of both matrices.
3. Add corresponding elements.
4. Display result.
Program Code (C++ Example)
3
Sample Input / Output
Complexity Analysis
Time Complexity: O(r⋅c)
Space Complexity: O(r⋅c)
o Every element in Matrix A and B is accessed once.
o A third matrix C of the same size is created to store the result.
1.2 Subtraction
Algorithm / Approach
1. Input matrices.
2. Subtract corresponding elements.
3. Display result.
4
Program Code (C++ Example)
Sample Input / Output
5
Complexity Analysis
Time Complexity: O(r.c)
o Each element is visited once for subtraction.
Space Complexity: O(r.c)
o Result matrix C holds the output.
1.3 Multiplication
Algorithm / Approach
1. Input dimensions of matrices (A: r1×c1, B: r2×c2).
2. Check if multiplication is possible (c1 = r2).
3. Multiply row elements of A with column elements of
B.
6
4. Display result.
Program Code (C++ Example)
Sample Input / Output
7
Complexity Analysis
Time: (O(r1 \cdot c1 \cdot c2))
Space: (O(r1 \cdot c2))
1.4 Transpose
Algorithm / Approach
1. Input matrix dimensions.
2. Swap rows with columns.
3. Display result.
Program Code (C++ Example)
8
Sample Input / Output
9
Complexity Analysis
2. Searching Algorithms using Functions
2.1 Linear Search
Algorithm / Approach
1. Input array size and elements.
2. Input the element to search.
3. Traverse array sequentially.
4. If element found, return position; else return not
found.
Program Code (C++ Example)
10
Sample Input / Output
11
Complexity Analysis
Time: (O(n))
Space: (O(1))
2.2 Binary Search
Algorithm / Approach
1. Input sorted array.
2. Input element to search.
3. Compare with middle element.
4. If equal → found.
5. If smaller → search left half.
6. If larger → search right half.
7. Repeat until found or array exhausted.
Program Code (C++ Example)
12
Sample Input / Output
13
Complexity Analysis
Time: (O(\log n))
Space: (O(1))
Got it Anne — thanks for snapping me back to the right track. Let’s properly
continue with Section 4: String Operations from your index, in the same
structured format we’ve been using:
3. String Operations using Functions
3.1 Palindrome Check
Algorithm / Approach
1. Input a string.
2. Compare characters from start and end moving inward.
3. If all match → palindrome, else not.
Program Code (C++ Example)
14
Sample Input / Output
Complexity Analysis
Time: (O(n))
Space: (O(1))
3.2 String Reversal
Algorithm / Approach
15
1. Input a string.
2. Swap characters from start and end.
3. Display reversed string.
Program Code (C++ Example)
Sample Input / Output
Complexity Analysis
Time: (O(n))
Space: (O(1))
3.3 String Concatenation
Algorithm / Approach
16
1. Input two strings.
2. Append second string to first.
3. Display result.
Program Code (C++ Example)
Sample Input / Output
Complexity Analysis
Time: (O(n+m))
Space: (O(n+m))
17
3.4 Substring Search
Algorithm / Approach
1. Input main string and substring.
2. Traverse main string.
3. Compare substring at each position.
4. If match found → return position.
Program Code (C++ Example)
18
Sample Input / Output
19
Complexity Analysis
Time: (O(n \cdot m)) (naive approach)
Space: (O(1))
3.5 String Length
Algorithm / Approach
1. Input a string.
2. Traverse until null terminator (\0).
3. Count characters.
Program Code (C++ Example)
20
Sample Input / Output
Complexity Analysis
Time: (O(n))
Space: (O(1))
3.6 String Comparison
Algorithm / Approach
1. Input two strings.
2. Compare character by character.
3. If equal → return true, else false.
21
Program Code (C++ Example)
Sample Input / Output
Complexity Analysis
22
Time: (O(n))
Space: (O(1))
3.7 String Copy
Algorithm / Approach
1. Input a string.
2. Copy each character into another string.
Program Code (C++ Example)
Sample Input / Output
Complexity Analysis
23
Time: (O(n))
Space: (O(n))
Perfect Anne — let’s build Section 4: Stack and Queue Operations in the
same structured format (algorithm, code, sample I/O, complexity).
4. Stack and Queue Operations
4.1 Stack (Push, Pop, Peek)
Algorithm / Approach
Push: Insert element at the top.
Pop: Remove element from the top.
Peek: Return the top element without removing it.
Program Code (C++ Example)
24
Sample Output
Complexity Analysis
25
Push: (O(1))
Pop: (O(1))
Peek: (O(1))
4.2 Queue (Enqueue, Dequeue)
Algorithm / Approach
Enqueue: Insert element at the rear.
Dequeue: Remove element from the front.
Program Code (C++ Example)
26
Sample Output
Complexity Analysis
Enqueue: (O(1))
Dequeue: (O(1))
27
4.3 Circular Queue
Algorithm / Approach
Use modulo arithmetic to wrap around indices.
Enqueue: Insert at (rear+1) % size.
Dequeue: Remove at (front+1) % size.
Program Code (C++ Example)
28
29
Sample Output
Complexity Analysis
30
Enqueue: (O(1))
Dequeue: (O(1))
Display: (O(n))
5. Linked List
5.1 Singly Linked List (Insertion, Deletion, Traversal)
Algorithm / Approach
Insertion: Create a new node, adjust pointers to insert at beginning,
end, or specific position.
Deletion: Adjust pointers to remove a node by value or position.
Traversal: Start from head, move through each node until NULL.
Program Code (C++ Example)
31
32
Sample Output
Complexity Analysis
Insertion: (O(n)) (end), (O(1)) (beginning)
Deletion: (O(n))
Traversal: (O(n))
33
5.2 Doubly Linked List
Algorithm / Approach
Each node has data, prev, and next.
Insertion: Adjust both prev and next pointers.
Deletion: Update adjacent nodes’ pointers.
Traversal: Can move forward or backward.
Program Code (C++ Example)
34
35
Sample Output
Complexity Analysis
Insertion: (O(n)) (end), (O(1)) (beginning)
Deletion: (O(n))
Traversal: (O(n))
5.3 Circular Linked List
Algorithm / Approach
36
Last node points back to head.
Insertion: Adjust last node’s next to point to new node, and new
node’s next to head.
Deletion: Update links to bypass node.
Traversal: Continue until back at head.
Program Code (C++ Example)
37
Sample Output
Complexity Analysis
38
Insertion: (O(n)) (end), (O(1)) (beginning)
Deletion: (O(n))
Traversal: (O(n))
6. Searching + Sorting
6.1 Sort then Apply Binary Search
Algorithm / Approach
1. Input array size and elements.
2. Sort the array (using any sorting algorithm).
3. Apply Binary Search on the sorted array.
4. Return position if found, else return not found.
Program Code (C++ Example)
39
40
Sample Input / Output
41
Complexity Analysis
Sorting (Bubble Sort): (O(n^2))
Searching (Binary Search): (O(\log n))
Combined: (O(n^2 + \log n)) ≈ (O(n^2))
If Merge Sort or Quick Sort is used: (O(n \log n)) overall
7. Binary Search Tree (BST) + Operations
7.1 Insertion
Algorithm / Approach
1. Start at root.
2. If tree empty → new node becomes root.
3. If key < root → go left; if key > root → go right.
4. Repeat until correct position found.
Program Code (C++ Example)
42
43
Sample Output
Complexity Analysis
Time: (O(h)) where (h) = height of tree (worst case (O(n)), best case
(O(\log n)))
Space: (O(h)) recursion stack
7.2 Deletion
Algorithm / Approach
44
1. Search for node.
2. If leaf → delete directly.
3. If one child → replace with child.
4. If two children → replace with inorder successor, then delete successor.
Program Code (C++ Example)
Sample Output (after deleting 20)
45
Complexity Analysis
Time: (O(h))
Space: (O(h)) recursion stack
7.3 Traversals
Algorithm / Approach
Inorder (LNR): Left → Node → Right
Preorder (NLR): Node → Left → Right
Postorder (LRN): Left → Right → Node
Program Code (C++ Example)
46
Sample Output
Complexity Analysis
Time: (O(n)) (visit all nodes)
Space: (O(h)) recursion stack
47
8. Graph Algorithms
8.1 Graph Representation (Adjacency Matrix & Adjacency
List)
Algorithm / Approach
Adjacency Matrix: Use a 2D array where matrix[i][j] = 1 if there
is an edge from vertex i to j.
Adjacency List: Use an array of lists; each list stores neighbors of a
vertex.
Program Code (C++ Example)
48
49
Sample Input / Output
Complexity Analysis
50
Matrix: Space (O(V^2)), Time (O(1)) for edge check.
List: Space (O(V+E)), Time (O(\deg(V))) for edge traversal.
8.2 Breadth-First Search (BFS)
Algorithm / Approach
1. Start from a source vertex.
2. Use a queue to explore neighbors level by level.
3. Mark visited nodes.
Program Code (C++ Example)
51
Sample Output
Complexity Analysis
Time: (O(V+E))
Space: (O(V))
52
8.3 Depth-First Search (DFS)
Algorithm / Approach
1. Start from a source vertex.
2. Use recursion or stack to explore as deep as possible before
backtracking.
3. Mark visited nodes.
Program Code (C++ Example)
Sample Output
53
Complexity Analysis
Time: (O(V+E))
Space: (O(V))
8.4 Shortest Path (Dijkstra’s Algorithm)
Algorithm / Approach
1. Initialize distances with infinity, source = 0.
2. Use a priority queue to pick the smallest distance vertex.
3. Update distances of neighbors.
4. Repeat until all vertices processed.
Program Code (C++ Example)
54
55
Sample Output
Complexity Analysis
Time: (O((V+E) \log V)) using priority queue
Space: (O(V))
56