Hands-On 8

datastructures.cpp

#include <iostream>
#include <stdexcept>

// Fixed sizes for each data structure
#define STACK_SIZE 5
#define QUEUE_SIZE 5
#define LIST_SIZE 10

// --------------------------
// Stack Class Implementation
// --------------------------
class Stack
{
private:
    int stack[STACK_SIZE]; // Fixed-size array to store stack elements
    int top;               // Index of the top element; -1 means empty

public:
    // Constructor: Initializes the stack as empty
    Stack() : top(-1)
    {
        // No dynamic allocation is used; the array is fixed-size
    }

    // Check if the stack is empty
    bool isEmpty() const
    {
        return top == -1;
    }

    // Check if the stack is full
    bool isFull() const
    {
        return top == STACK_SIZE - 1;
    }

    // Add an element to the stack
    void push(int value)
    {
        if (isFull())
        {
            throw std::overflow_error("Stack is full");
        }
        stack[++top] = value; // Increment top and add the value
    }

    // Remove and return the top element from the stack
    int pop()
    {
        if (isEmpty())
        {
            throw std::underflow_error("Stack is empty");
        }
        return stack[top--]; // Return the value and decrement top
    }

    // Return the top element without removing it
    int peek() const
    {
        if (isEmpty())
        {
            throw std::underflow_error("Stack is empty");
        }
        return stack[top];
    }

    // Display all elements in the stack
    void display() const
    {
        if (isEmpty())
        {
            std::cout << "Stack is empty" << std::endl;
        }
        else
        {
            std::cout << "Stack elements: ";
            for (int i = 0; i <= top; i++)
            {
                std::cout << stack[i] << " ";
            }
            std::cout << std::endl;
        }
    }
};

// ---------------------------
// Queue Class Implementation using head and tail
// ---------------------------
class Queue
{
private:
    int queue[QUEUE_SIZE]; // Fixed-size array to store queue elements
    int head;              // Index of the first element in the queue
    int tail;              // Index of the last element in the queue
    int count;             // Current number of elements in the queue

public:
    // Constructor: Initializes an empty queue
    Queue() : head(0), tail(-1), count(0)
    {
        // The fixed-size array is automatically allocated on the stack
    }

    // Check if the queue is empty
    bool isEmpty() const
    {
        return count == 0;
    }

    // Check if the queue is full
    bool isFull() const
    {
        return count == QUEUE_SIZE;
    }

    // Add an element to the queue
    void enqueue(int value)
    {
        if (isFull())
        {
            throw std::overflow_error("Queue is full");
        }
        // Circularly update tail index
        tail = (tail + 1) % QUEUE_SIZE;
        queue[tail] = value;
        count++;
    }

    // Remove and return the element at the head of the queue
    int dequeue()
    {
        if (isEmpty())
        {
            throw std::underflow_error("Queue is empty");
        }
        int value = queue[head];
        head = (head + 1) % QUEUE_SIZE; // Circularly update head index
        count--;
        return value;
    }

    // Return the element at the head without removing it
    int peek() const
    {
        if (isEmpty())
        {
            throw std::underflow_error("Queue is empty");
        }
        return queue[head];
    }

    // Display all elements in the queue
    void display() const
    {
        if (isEmpty())
        {
            std::cout << "Queue is empty" << std::endl;
        }
        else
        {
            std::cout << "Queue elements: ";
            int i = head;
            for (int j = 0; j < count; j++)
            {
                std::cout << queue[i] << " ";
                i = (i + 1) % QUEUE_SIZE;
            }
            std::cout << std::endl;
        }
    }
};

// ------------------------------
// Node and SinglyLinkedList Implementation
// ------------------------------

#include <iostream>
#include <stdexcept>

class Node
{
public:
    int data;   // Data stored in the node
    Node *next; // Pointer to the next node

    // Constructor: Initializes a node with the given data
    Node(int data) : data(data), next(nullptr) {}
};

class SinglyLinkedList
{
private:
    Node *head; // Pointer to the first node in the list

public:
    // Constructor: Initializes an empty linked list
    SinglyLinkedList() : head(nullptr) {}

    // Check if the linked list is empty
    bool isEmpty() const
    {
        return head == nullptr;
    }

    // Insert a new node with the provided data at the beginning
    void insertFirst(int data)
    {
        Node *newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    // Insert a new node with the provided data at the end of the list
    void insertLast(int data)
    {
        Node *newNode = new Node(data);
        if (isEmpty())
        {
            head = newNode;
        }
        else
        {
            Node *last = head;
            while (last->next != nullptr)
            {
                last = last->next;
            }
            last->next = newNode;
        }
    }

    // Delete the first occurrence of the node with the specified data
    void deleteNode(int data)
    {
        if (isEmpty())
        {
            throw std::underflow_error("List is empty");
        }

        Node *currentNode = head;
        Node *previousNode = nullptr;

        // Traverse the list to find the node with the matching data
        while (currentNode != nullptr && currentNode->data != data)
        {
            previousNode = currentNode;
            currentNode = currentNode->next;
        }

        if (currentNode == nullptr)
        {
            throw std::invalid_argument("Data not found");
        }

        // If node to delete is the head
        if (previousNode == nullptr)
        {
            head = currentNode->next;
        }
        else
        {
            previousNode->next = currentNode->next;
        }

        delete currentNode;
    }

    // Search for a node with the given data
    Node *search(int data) const
    {
        Node *currentNode = head;
        while (currentNode != nullptr)
        {
            if (currentNode->data == data)
            {
                return currentNode;
            }
            currentNode = currentNode->next;
        }
        return nullptr; // Node with data not found
    }

    // Display all nodes in the linked list
    void display() const
    {
        if (isEmpty())
        {
            std::cout << "List is empty" << std::endl;
        }
        else
        {
            Node *currentNode = head;
            std::cout << "List elements: ";
            while (currentNode != nullptr)
            {
                std::cout << currentNode->data << " ";
                currentNode = currentNode->next;
            }
            std::cout << std::endl;
        }
    }

    // Destructor: Clean up dynamically allocated nodes
    ~SinglyLinkedList()
    {
        while (!isEmpty())
        {
            deleteNode(head->data);
        }
    }
};

// ---------------------------
// Main function to test the data structures
// ---------------------------
int main()
{
    // Test the Stack
    std::cout << "Testing Stack:" << std::endl;
    Stack stack;
    try
    {
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.display();
        std::cout << "Stack top: " << stack.peek() << std::endl;
        std::cout << "Popped: " << stack.pop() << std::endl;
        stack.display();
    }
    catch (const std::exception &e)
    {
        std::cerr << e.what() << std::endl;
    }

    std::cout << std::endl;

    // Test the Queue
    std::cout << "Testing Queue:" << std::endl;
    Queue queue;
    try
    {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.display();
        std::cout << "Queue front: " << queue.peek() << std::endl;
        std::cout << "Dequeued: " << queue.dequeue() << std::endl;
        queue.display();
    }
    catch (const std::exception &e)
    {
        std::cerr << e.what() << std::endl;
    }

    std::cout << std::endl;

    std::cout << "Testing SinglyLinkedList:" << std::endl;
    SinglyLinkedList list;
    try
    {
        // Insert elements
        list.insertFirst(100); // Insert 100 at the front
        list.insertLast(200);  // Insert 200 at the end
        list.insertLast(300);  // Insert 300 at the end
        list.display();        // Display list after insertions

        // Delete a node and display again
        list.deleteNode(200); // Delete node with data 200
        list.display();       // Display list after deletion
    }
    catch (const std::exception &e)
    {
        std::cerr << e.what() << std::endl;
    }

    return 0;
}

ith_stat.py

import random

# =====================================================
# MEDIAN-OF-MEDIANS HELPER FUNCTION FOR PIVOT SELECTION
# =====================================================
def median_of_medians(arr, low, high, chunk_size=5):
    """
    Returns an approximate median (pivot) for arr[low...high] using the median-of-medians method.
    """
    n = high - low + 1
    # If the subarray is small, sort and return the true median.
    if n <= chunk_size:
        subarr = arr[low:high+1]
        subarr.sort()
        return subarr[n // 2]
    
    # Otherwise, partition the array into chunks of 'chunk_size'
    medians = []
    for i in range(low, high + 1, chunk_size):
        chunk = arr[i:min(i + chunk_size, high + 1)]
        chunk.sort()
        medians.append(chunk[len(chunk) // 2])
    
    # Recursively compute the median of the medians
    return median_of_medians(medians, 0, len(medians) - 1, chunk_size)

# =====================================================
# PARTITION FUNCTION USING MEDIAN-OF-MEDIANS PIVOT SELECTION
# =====================================================
def partition_median(arr, low, high):
    """
    Partitions arr[low...high] using a pivot selected by the median-of-medians method.
    Returns the final index of the pivot.
    """
    pivot_value = median_of_medians(arr, low, high)
    
    # Find the index of the pivot_value and move it to the end.
    # In case of duplicates, we select the first occurrence.
    for idx in range(low, high + 1):
        if arr[idx] == pivot_value:
            arr[idx], arr[high] = arr[high], arr[idx]
            break

    # Standard partition procedure (like fixed-pivot quicksort)
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot_value:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# =====================================================
# QUICKSORT USING MEDIAN-OF-MEDIANS PIVOT
# =====================================================
def quicksort_median(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition_median(arr, low, high)
        quicksort_median(arr, low, pivot_idx - 1)
        quicksort_median(arr, pivot_idx + 1, high)

# =====================================================
# QUICKSELECT (ITH ORDER STATISTIC) USING MEDIAN-OF-MEDIANS PIVOT
# =====================================================
def quickselect(arr, i, low=0, high=None):
    """
    Returns the ith smallest element in arr.
    Here i is 1-indexed (i.e. i=1 returns the smallest element).
    """
    if high is None:
        high = len(arr) - 1

    # If the list contains only one element, return it.
    if low == high:
        return arr[low]
    
    pivot_idx = partition_median(arr, low, high)
    k = pivot_idx - low + 1  # Pivot's rank in the subarray

    if i == k:
        return arr[pivot_idx]           # converge
    elif i < k:
        return quickselect(arr, i, low, pivot_idx - 1)              # search in the left part
    else:
        return quickselect(arr, i - k, pivot_idx + 1, high)         # search in the right part

# =====================================================
# DEMONSTRATION
# =====================================================
if __name__ == "__main__":
    # Create an unsorted array.
    unsorted_arr = [random.randint(1, 100) for _ in range(20)]
    print("Unsorted array:")
    print(unsorted_arr)

    # Sort the array using quicksort with median-of-medians pivot.
    arr_to_sort = unsorted_arr.copy()
    quicksort_median(arr_to_sort)
    print("\nSorted array:")
    print(arr_to_sort)

    # Choose an order statistic to find.
    # For example, to find the median (1-indexed):
    n = len(unsorted_arr)
    median_index = (n + 1) // 2

    # Since quickselect modifies the list in-place, work on a copy.
    arr_for_select = unsorted_arr.copy()
    median_value = quickselect(arr_for_select, median_index)
    print(f"\nThe median (the {median_index}th smallest element) is: {median_value}")

    # You can also test for other order statistics:
    smallest = quickselect(unsorted_arr.copy(), 1)
    largest = quickselect(unsorted_arr.copy(), n)
    print(f"Smallest element: {smallest}")
    print(f"Largest element: {largest}")