This document provides a comprehensive guide to all programming assignments listed in the CSCDSC152 syllabus. It includes the core logic, algorithms, and implementation tips needed for a practical exam or viva.
The main objectives of this lab are to:
Upon successful completion, students will be able to:
Many assignments specify using templates. This allows you to write generic code that works with any data type (e.g., int, float, char).
A template class for a Stack would start like this:
template <typename T>
class Stack {
private:
T arr[100];
int top;
public:
void push(T data) {
// ... logic
}
T pop() {
// ... logic
}
// ... other methods
};
When you create an object, you specify the type:
Stack<int> intStack; (A stack for integers)
Stack<float> floatStack; (A stack for floats)
The same logic applies to template functions for sorting or searching.
Task: Write a template program to search an element from a list, offering users the option of Linear or Binary search.
template <typename T> int linearSearch(T arr[], int size, T key)
i = 0 to size - 1.arr[i] == key, return i (index found).-1 (not found).low = 0, high = size - 1.low <= high:
mid = low + (high - low) / 2.arr[mid] == key, return mid.arr[mid] < key, set low = mid + 1.arr[mid] > key, set high = mid - 1.-1.Task: Write a template program (WAP) to sort a list, offering users options for Insertion, Bubble, or Selection sort.
i = 0 to n-2.j = 0 to n-i-2.arr[j] > arr[j+1], swap them.i = 0 to n-2.min_idx) in the range [i, n-1].arr[i] with arr[min_idx].i = 1 to n-1.key = arr[i].j = i - 1.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).Task: WAP to convert a Sparse Matrix into non-zero form and vice-versa.
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].
triplet matrix. Initialize k = 1 (for data, row 0 is header).M x N matrix with nested loops (i for row, j for col).matrix[i][j] != 0:
triplet[k][0] = itriplet[k][1] = jtriplet[k][2] = matrix[i][j]k++triplet[0][0] = M, triplet[0][1] = N, triplet[0][2] = k - 1.M = triplet[0][0], N = triplet[0][1], non_zero = triplet[0][2].M x N matrix and initialize all its elements to 0.k = 1 to non_zero:
row = triplet[k][0]col = triplet[k][1]val = triplet[k][2]matrix[row][col] = val.matrix is now reconstructed.Task: Implement Diagonal, Lower Triangular, Upper Triangular, and Symmetric matrices using a 1D array.
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.
M[i][i] elements are non-zero.
n diagonal elements. Formula: arr[i] stores M[i][i].M[i][j] are non-zero only if i >= j.
n(n+1)/2.k = i(i+1)/2 + jM[i][j] are non-zero only if i <= j.
n(n+1)/2.k = i*n - i(i-1)/2 + j - iM[i][j] == M[j][i].
function factorial_iter(n):
result = 1
for i = 2 to n:
result = result * i
return result
function factorial_recur(n):
if n == 0 or n == 1:
return 1 // Base Case
else:
return n * factorial_recur(n - 1) // Recursive Step
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
function fib_recur(n):
if n <= 1:
return n // Base Cases (0 and 1)
else:
return fib_recur(n - 1) + fib_recur(n - 2)
function gcd_iter(a, b):
while b != 0:
temp = b
b = a % b
a = temp
return a
function gcd_recur(a, b):
if b == 0:
return a // Base Case
else:
return gcd_recur(b, a % b) // Recursive Step
Node structure.
template <typename T>
struct Node {
T data;
Node* next; // For Singly & Circular
Node* prev; // For Doubly
};
Task: Implement insertion, deletion, search, reverse, and concatenate.
head, comparing data. Return true or the node if found, false/NULL otherwise.prev = NULL, current = head, next = NULL.current != NULL:
next = current->nextcurrent->next = prev (reverse the link)prev = currentcurrent = nexthead = prev.list1 to find its last node.last_node_of_list1->next = list2->head.list2; the + operator should ideally create a new list or append list2 to list1).Task: Implement insertion, deletion, search, and reverse.
Key: Every operation must correctly update both next and prev pointers.
p):
newNode->next = p->nextnewNode->prev = pp->next != NULL, then p->next->prev = newNodep->next = newNodep):
p->prev->next = p->nextp->next != NULL, then p->next->prev = p->prevdelete pprev and next pointers.head and tail pointers of the list.Task: Implement insertion, deletion, search, and reverse.
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.
do-while loop to ensure the head is processed.
temp = head; do { ...; temp = temp->next; } while (temp != head);
head or tail, as you must update the tail->next pointer.Task: WAP to scan a polynomial using a linked list and add two polynomials.
struct Term {
int coeff; // Coefficient
int exp; // Exponent
Term* next;
};
poly1, poly2):
result list.p1 (for poly1) and p2 (for poly2).p1 != NULL and p2 != NULL:
p1->exp > p2->exp: Add p1's term to result, advance p1.p1->exp < p2->exp: Add p2's term to result, advance p2.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.result.T arr[MAX_SIZE], int top.top = -1.if top == MAX_SIZE - 1).top++.arr[top] = data.if top == -1).T data = arr[top].top--.data.Node* top (which is just the head of the list).top = NULL.newNode = new Node(data).newNode->next = top.top = newNode.if top == NULL).temp = top.T data = top->data.top = top->next.delete temp.data.T arr[MAX_SIZE], int front, int rear.front = -1, rear = -1.return (rear + 1) % MAX_SIZE == front;return front == -1;front == -1), set front = 0.rear = (rear + 1) % MAX_SIZE.arr[rear] = data.T data = arr[front].front == rear (only one element), set front = -1, rear = -1.front = (front + 1) % MAX_SIZE.data.Task: Create and perform operations on a Double-ended Queue using a Doubly Linked List.
Node* front, Node* rear (use a Doubly Linked List).front and rear pointers. When deleting the *last* element, you must set *both* front and rear to NULL.
This is simple. To reverse S1 using S2:
S1 is not empty, push(S1.pop()) onto S2.S2 holds all elements in reverse order.S1, use a third stack S3 (or a Queue) as an intermediary, or just assign S1 = S2 if the class supports it.To reverse Stack S using Queue Q:
S is not empty, enqueue(S.pop()) into Q. (Elements are now in Q in the original stack order).Q is not empty, push(Q.dequeue()) onto S. (Elements are put back into S in reverse order).Task: Create a BST and implement a large number of operations.
{ T data; Node *left; Node *right; }
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
left/right paths. Return true if found, false if NULL is hit.visit(node), traverse(node->left), traverse(node->right).traverse(node->left), visit(node), traverse(node->right).traverse(node->left), traverse(node->right), visit(node).root.node = dequeue()visit(node)node->left != NULL, enqueue node->left.node->right != NULL, enqueue node->right.
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
function height(node):
if node == NULL: return -1 // or 0 for "count of nodes"
return 1 + max(height(node->left), height(node->right))
function mirror(node):
if node == NULL: return
mirror(node->left)
mirror(node->right)
swap(node->left, node->right)
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)
Task: Create a Threaded Binary Tree (TBT) as per inorder traversal and implement operations like find successor/predecessor, insert, and inorder traversal.
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
};
node != NULL:
visit(node).node->isRightThread == true, node = node->right (follow thread).node = node->right, and then find the leftmost node of that subtree.inorder and predecessor threads of the surrounding nodes.Task: Implement various operations on an AVL Tree.
This builds on Assignment 14 (BST). Your insert and delete functions must now be modified to include rebalancing.
BF = height(node->left) - height(node->right).BF > 1 (Left-Heavy):
node->left->left: Perform LL Rotate (Right Rotate).node->left->right: Perform LR Rotate (Left-Right Rotate).BF < -1 (Right-Heavy):
node->right->right: Perform RR Rotate (Left Rotate).node->right->left: Perform RL Rotate (Right-Left Rotate).