Assignment 1: Linear & Binary Search (Templates)

Task: Write a template program to search an element from a list, offering users the option of Linear or Binary search.

Logic

• Template Function: Your search functions should be template functions.
  template <typename T> int linearSearch(T arr[], int size, T key)
• Linear Search:
  1. Iterate from i = 0 to size - 1.
  2. If arr[i] == key, return i (index found).
  3. If loop finishes, return -1 (not found).
• Binary Search:
  1. Prerequisite: The array must be sorted. You should sort it first (using a sort from Assignment 2).
  2. Set low = 0, high = size - 1.
  3. While low <= high:
     • mid = low + (high - low) / 2.
     • If arr[mid] == key, return mid.
     • If arr[mid] < key, set low = mid + 1.
     • If arr[mid] > key, set high = mid - 1.
  4. If loop finishes, return -1.

Assignment 2: Insertion, Bubble & Selection Sort (Templates)

Task: Write a template program (WAP) to sort a list, offering users options for Insertion, Bubble, or Selection sort.

Logic

• Bubble Sort:
  • Outer loop from i = 0 to n-2.
  • Inner loop from j = 0 to n-i-2.
  • If arr[j] > arr[j+1], swap them.
• Selection Sort:
  • Outer loop from i = 0 to n-2.
  • Find the index of the minimum element (min_idx) in the range [i, n-1].
  • Swap arr[i] with arr[min_idx].
• Insertion Sort:
  • Outer loop from i = 1 to n-1.
  • Store key = arr[i].
  • Set j = i - 1.
  • While j >= 0 and arr[j] > key:
    • arr[j+1] = arr[j] (shift element to the right).
    • j = j - 1.
  • arr[j+1] = key (insert key in its correct position).

Assignment 15: Sparse Matrix Conversion

Task: WAP to convert a Sparse Matrix into non-zero form and vice-versa.

Logic

The "non-zero form" (or Triplet Form) stores only non-zero elements in a k x 3 matrix, where k is the number of non-zero elements.

triplet[k][3] -> [row, column, value]

A header row triplet[0] is often used to store [total_rows, total_cols, total_non_zero].

• Sparse to Triplet:
  1. Create a triplet matrix. Initialize k = 1 (for data, row 0 is header).
  2. Iterate through the original M x N matrix with nested loops (i for row, j for col).
  3. If matrix[i][j] != 0:
     • triplet[k][0] = i
     • triplet[k][1] = j
     • triplet[k][2] = matrix[i][j]
     • k++
  4. Finally, set header: triplet[0][0] = M, triplet[0][1] = N, triplet[0][2] = k - 1.
• Triplet to Sparse:
  1. Read the header: M = triplet[0][0], N = triplet[0][1], non_zero = triplet[0][2].
  2. Create a new M x N matrix and initialize all its elements to 0.
  3. Loop from k = 1 to non_zero:
     • row = triplet[k][0]
     • col = triplet[k][1]
     • val = triplet[k][2]
     • Set matrix[row][col] = val.
  4. The matrix is now reconstructed.

Assignments 18, 19, 20, 21: Special Matrix Implementations

Task: Implement Diagonal, Lower Triangular, Upper Triangular, and Symmetric matrices using a 1D array.

Logic

The goal is to save space by only storing the non-zero (or unique) elements in a 1D array. This requires a "mapping formula" to convert 2D (i, j) indices to a 1D (k) index.

• Diagonal Matrix: Only M[i][i] elements are non-zero.
  • Store only the n diagonal elements. Formula: arr[i] stores M[i][i].
• Lower Triangular: Elements M[i][j] are non-zero only if i >= j.
  • Number of elements = n(n+1)/2.
  • Row-Major Formula: k = i(i+1)/2 + j
• Upper Triangular: Elements M[i][j] are non-zero only if i <= j.
  • Number of elements = n(n+1)/2.
  • Row-Major Formula: k = i*n - i(i-1)/2 + j - i
• Symmetric Matrix: M[i][j] == M[j][i].
  • Store only the lower or upper triangle. Use the same formula as that triangle.

Assignment 11: Factorial (Recursive vs. Iterative)

Logic

• Iterative:

   function factorial_iter(n): result = 1 for i = 2 to n: result = result * i return result 

• Recursive:

   function factorial_recur(n): if n == 0 or n == 1: return 1 // Base Case else: return n * factorial_recur(n - 1) // Recursive Step 

Assignment 12: Fibonacci (Recursive vs. Iterative)

Logic

• Iterative (Efficient):

   function fib_iter(n): if n <= 1: return n a = 0, b = 1, c for i = 2 to n: c = a + b a = b b = c return b 

• Recursive (Inefficient):

   function fib_recur(n): if n <= 1: return n // Base Cases (0 and 1) else: return fib_recur(n - 1) + fib_recur(n - 2) 

Assignment 13: GCD (Recursive vs. Iterative)

Logic (using Euclidean Algorithm)

• Iterative:

   function gcd_iter(a, b): while b != 0: temp = b b = a % b a = temp return a 

• Recursive:

   function gcd_recur(a, b): if b == 0: return a // Base Case else: return gcd_recur(b, a % b) // Recursive Step 

Assignment 3: Singly Linked List (Templates)

Task: Implement insertion, deletion, search, reverse, and concatenate.

Logic

• Insertion: At beginning (O(1)), at end (O(n)), at specific position (O(n)).
• Deletion: At beginning (O(1)), at end (O(n)), at specific position (O(n)).
• Search: Traverse the list from head, comparing data. Return true or the node if found, false/NULL otherwise.
• Reverse:
  • Use three pointers: prev = NULL, current = head, next = NULL.
  • Loop while current != NULL:
    1. next = current->next
    2. current->next = prev (reverse the link)
    3. prev = current
    4. current = next
  • Finally, set head = prev.
• Concatenate (list1 + list2):
  1. Traverse list1 to find its last node.
  2. Set last_node_of_list1->next = list2->head.
  3. (Be careful not to destroy list2; the + operator should ideally create a new list or append list2 to list1).

Assignment 4: Doubly Linked List (Templates)

Task: Implement insertion, deletion, search, and reverse.

Logic

Key: Every operation must correctly update both next and prev pointers.

• Insertion (e.g., after a node p):
  1. newNode->next = p->next
  2. newNode->prev = p
  3. If p->next != NULL, then p->next->prev = newNode
  4. p->next = newNode
• Deletion (of node p):
  1. p->prev->next = p->next
  2. If p->next != NULL, then p->next->prev = p->prev
  3. delete p
• Reverse:
  • Traverse the list. For each node, swap its prev and next pointers.
  • Finally, swap the head and tail pointers of the list.

Assignment 5: Circular Linked List (Templates)

Task: Implement insertion, deletion, search, and reverse.

Logic

Key: The list never has a NULL end. The head's "previous" is the tail, and the tail's next is the head. A tail pointer is often maintained instead of a head, as tail->next gives you the head.

• Traversal: Use a do-while loop to ensure the head is processed.
  temp = head; do { ...; temp = temp->next; } while (temp != head);
• Insertion/Deletion: Similar to singly linked list, but with extra care when modifying the head or tail, as you must update the tail->next pointer.

Assignment 10: Polynomial Addition

Task: WAP to scan a polynomial using a linked list and add two polynomials.

Logic

• Node Structure: Each node represents one term.

   struct Term { int coeff; // Coefficient int exp; // Exponent Term* next; }; 

• Storage: Store the polynomial as a linked list, sorted in descending order of exponent.
• Addition (poly1, poly2):
  1. Create a new result list.
  2. Use two pointers, p1 (for poly1) and p2 (for poly2).
  3. While p1 != NULL and p2 != NULL:
     • If p1->exp > p2->exp: Add p1's term to result, advance p1.
     • If p1->exp < p2->exp: Add p2's term to result, advance p2.
     • If p1->exp == p2->exp: Add the coefficients (p1->coeff + p2->coeff). If the sum is not zero, add the new term to result. Advance both p1 and p2.
  4. When one list finishes, append the entire remainder of the other list to result.

Assignment 7: Stack using Array (Templates)

Logic

• Members: T arr[MAX_SIZE], int top.
• Constructor: Initialize top = -1.
• push(T data):
  1. Check for Overflow (if top == MAX_SIZE - 1).
  2. top++.
  3. arr[top] = data.
• pop():
  1. Check for Underflow (if top == -1).
  2. T data = arr[top].
  3. top--.
  4. Return data.

Assignment 6: Stack using Linked List

Logic

• Member: Node* top (which is just the head of the list).
• Constructor: Initialize top = NULL.
• push(T data): (Insert at Beginning)
  1. newNode = new Node(data).
  2. newNode->next = top.
  3. top = newNode.
• pop(): (Delete at Beginning)
  1. Check for Underflow (if top == NULL).
  2. temp = top.
  3. T data = top->data.
  4. top = top->next.
  5. delete temp.
  6. Return data.

Assignment 8: Queue using Circular Array (Templates)

Logic

• Members: T arr[MAX_SIZE], int front, int rear.
• Constructor: Initialize front = -1, rear = -1.
• isFull(): return (rear + 1) % MAX_SIZE == front;
• isEmpty(): return front == -1;
• enqueue(T data):
  1. Check if full.
  2. If empty (front == -1), set front = 0.
  3. rear = (rear + 1) % MAX_SIZE.
  4. arr[rear] = data.
• dequeue():
  1. Check if empty.
  2. T data = arr[front].
  3. If front == rear (only one element), set front = -1, rear = -1.
  4. Else, front = (front + 1) % MAX_SIZE.
  5. Return data.

Assignment 9: Deque using Linked List

Task: Create and perform operations on a Double-ended Queue using a Doubly Linked List.

Logic

• Members: Node* front, Node* rear (use a Doubly Linked List).
• insertFront(): Insert at the beginning of the DLL.
• insertRear(): Insert at the end of the DLL.
• deleteFront(): Delete from the beginning of the DLL.
• deleteRear(): Delete from the end of the DLL.

Assignment 16: Reverse Stack (using additional Stack)

Logic

This is simple. To reverse S1 using S2:

1. While S1 is not empty, push(S1.pop()) onto S2.
2. Now S2 holds all elements in reverse order.
3. (Optional) If you need the reversed elements back in S1, use a third stack S3 (or a Queue) as an intermediary, or just assign S1 = S2 if the class supports it.

Assignment 17: Reverse Stack (using additional Queue)

Logic

To reverse Stack S using Queue Q:

1. While S is not empty, enqueue(S.pop()) into Q. (Elements are now in Q in the original stack order).
2. While Q is not empty, push(Q.dequeue()) onto S. (Elements are put back into S in reverse order).

Assignment 14: Binary Search Tree (BST) Operations

Task: Create a BST and implement a large number of operations.

Logic

• Node Structure: { T data; Node *left; Node *right; }
• (a) Insertion (Recursive):

   function insert(node, key): if node == NULL: return new Node(key) if key < node->data: node->left = insert(node->left, key) else: node->right = insert(node->right, key) return node 

• (b) Deletion by Copying: (Case 3: 2 children)
  1. Find Inorder Successor (smallest node in the right subtree).
  2. Copy successor's data to the node to be deleted.
  3. Recursively delete the successor (which is an easier 0 or 1-child case).
• (c) Deletion by Merging: (Alternative Case 3)
  1. Find the largest node in the *left* subtree.
  2. Make the *entire right subtree* the right child of that largest node.
  3. Point the parent of the deleted node to the root of the left subtree.
• (d) Search: Similar to insertion, follow left/right paths. Return true if found, false if NULL is hit.
• (e) Traversals (Recursive):
  • Preorder: visit(node), traverse(node->left), traverse(node->right).
  • Inorder: traverse(node->left), visit(node), traverse(node->right).
  • Postorder: traverse(node->left), traverse(node->right), visit(node).
• (f) Traversals (Iterative): Use a Stack. (See theory notes for CSCDSC151, Unit 3).
• (g) Level-by-Level Traversal: Use a Queue.
  1. Enqueue the root.
  2. While Queue is not empty:
     • node = dequeue()
     • visit(node)
     • If node->left != NULL, enqueue node->left.
     • If node->right != NULL, enqueue node->right.
• (h) Count Leaf & Non-Leaf Nodes:

   function countLeaf(node): if node == NULL: return 0 if node->left == NULL and node->right == NULL: return 1 return countLeaf(node->left) + countLeaf(node->right) // Non-leaf is total_nodes - leaf_nodes 

• (i) Display Height of Tree:

   function height(node): if node == NULL: return -1 // or 0 for "count of nodes" return 1 + max(height(node->left), height(node->right)) 

• (j) Create Mirror Image:

   function mirror(node): if node == NULL: return mirror(node->left) mirror(node->right) swap(node->left, node->right) 

• (k) Check if Two BSTs are Equal:

   function areEqual(r1, r2): if r1 == NULL and r2 == NULL: return true if r1 == NULL or r2 == NULL: return false return (r1->data == r2->data) and areEqual(r1->left, r2->left) and areEqual(r1->right, r2->right) 

Assignment 22: Threaded Binary Tree

Task: Create a Threaded Binary Tree (TBT) as per inorder traversal and implement operations like find successor/predecessor, insert, and inorder traversal.

Logic

• Node Structure:

   struct TBTNode { T data; TBTNode *left, *right; bool isLeftThread; // True if left pointer is a thread bool isRightThread; // True if right pointer is a thread }; 

• Inorder Traversal (without stack/recursion):
  1. Find the leftmost node of the tree.
  2. While node != NULL:
     • visit(node).
     • If node->isRightThread == true, node = node->right (follow thread).
     • Else, node = node->right, and then find the leftmost node of that subtree.
• Insertion: This is complex. You must find the correct empty spot, insert the new node, and update the inorder and predecessor threads of the surrounding nodes.

Assignment 23: AVL Tree Operations

Task: Implement various operations on an AVL Tree.

Logic

This builds on Assignment 14 (BST). Your insert and delete functions must now be modified to include rebalancing.

1. Perform the standard BST insertion/deletion.
2. After the operation, move back up the tree (via recursion) to the root.
3. At each node, update its height.
4. Calculate the Balance Factor (BF): BF = height(node->left) - height(node->right).
5. If BF > 1 (Left-Heavy):
   • If key was inserted in node->left->left: Perform LL Rotate (Right Rotate).
   • If key was inserted in node->left->right: Perform LR Rotate (Left-Right Rotate).
6. If BF < -1 (Right-Heavy):
   • If key was inserted in node->right->right: Perform RR Rotate (Left Rotate).
   • If key was inserted in node->right->left: Perform RL Rotate (Right-Left Rotate).