UNIT-I: Introduction to Algorithm Design & Analysis

---

Introduction: Basic Design and Analysis Techniques

An algorithm is a step-by-step procedure for solving a problem. The study of algorithms involves two key aspects:

• Algorithm Design: Creating the algorithm. This involves choosing the right strategy to solve the problem efficiently.
• Algorithm Analysis: Evaluating the algorithm's performance. We are primarily concerned with its time complexity (how long it takes to run) and space complexity (how much memory it uses). This is often expressed using Big O notation, like $O(n)$, $O(n \log n)$, or $O(n^2)$.

---

Algorithm Design Techniques

1. Iterative Techniques

This is the most straightforward approach, where a solution is built up step-by-step in a loop. It involves using constructs like for loops or while loops to repeatedly execute a block of code.

Example: Calculating Factorial (Java)

public class FactorialExample {
    
    public static long factorialIterative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Input must be non-negative.");
        }
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println("Factorial of " + number + " is: " + factorialIterative(number));
        // Output: Factorial of 5 is: 120
    }
}
    

2. Divide and Conquer

This technique solves a problem by breaking it down into smaller, more manageable sub-problems. It follows three main steps:

1. Divide: Break the main problem into smaller, independent sub-problems.
2. Conquer: Solve the sub-problems recursively.
3. Combine: Merge the solutions of the sub-problems to get the solution for the original problem.

Famous algorithms like Merge Sort and Quick Sort are based on this technique.

3. Dynamic Programming (DP)

Dynamic Programming is used for problems with overlapping sub-problems. Instead of re-computing the solution for the same sub-problem, DP saves the result in memory (a technique called memoization) and reuses it.

Example: Fibonacci Sequence with Memoization (Java)

import java.util.HashMap;
import java.util.Map;

public class FibonacciDP {

    // Helper function with memoization map
    private static long fibonacciHelper(int n, Map<Integer, Long> memo) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
        memo.put(n, result);
        return result;
    }

    public static long fibonacci(int n) {
        return fibonacciHelper(n, new HashMap<>());
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number " + n + " is: " + fibonacci(n));
        // Output: Fibonacci number 10 is: 55
    }
}
    

4. Greedy Algorithms

A greedy algorithm builds a solution piece by piece, always choosing the option that looks best at the moment (a locally optimal choice) hoping it leads to a globally optimal solution.

Example: Coin Change Problem (Java)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class GreedyCoinChange {
    
    public static void findCoinChange(int[] denominations, int amount) {
        // Sort in descending order to pick largest coins first
        List<Integer> coins = new ArrayList<>();
        for(int coin : denominations) coins.add(coin);
        coins.sort(Collections.reverseOrder());

        List<Integer> result = new ArrayList<>();
        
        for (int coin : coins) {
            while (amount >= coin) {
                amount -= coin;
                result.add(coin);
            }
        }
        
        System.out.println("Coins used: " + result);
    }

    public static void main(String[] args) {
        int[] denominations = {1, 5, 10, 25};
        int amount = 63;
        findCoinChange(denominations, amount);
        // Output: Coins used: [25, 25, 10, 1, 1, 1]
    }
}
    

UNIT-II: Sorting Techniques

---

Elementary Sorting Techniques

Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Time Complexity	Space Complexity
Best: $O(n)$, Average: $O(n^2)$, Worst: $O(n^2)$	$O(1)$

Java Code:

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // Optimization
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original: " + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [11, 12, 22, 25, 34, 64, 90]
    }
}
    

Insertion Sort

Insertion Sort builds the final sorted array one item at a time by inserting each element into its correct sorted position.

Time Complexity	Space Complexity
Best: $O(n)$, Average: $O(n^2)$, Worst: $O(n^2)$	$O(1)$

Java Code:

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 14};
        System.out.println("Original: " + Arrays.toString(data));
        insertionSort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [10, 14, 14, 29, 37]
    }
}
    

---

Advanced Sorting Techniques

Merge Sort

A Divide and Conquer algorithm that divides the array, sorts the halves recursively, and then merges them.

Time Complexity	Space Complexity
Best/Avg/Worst: $O(n \log n)$	$O(n)$

Java Code:

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int n) {
        if (n < 2) return;
        int mid = n / 2;
        int[] left = new int[mid];
        int[] right = new int[n - mid];

        for (int i = 0; i < mid; i++) left[i] = arr[i];
        for (int i = mid; i < n; i++) right[i - mid] = arr[i];

        mergeSort(left, mid);
        mergeSort(right, n - mid);
        merge(arr, left, right, mid, n - mid);
    }

    private static void merge(int[] a, int[] l, int[] r, int left, int right) {
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) a[k++] = l[i++];
            else a[k++] = r[j++];
        }
        while (i < left) a[k++] = l[i++];
        while (j < right) a[k++] = r[j++];
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original: " + Arrays.toString(data));
        mergeSort(data, data.length);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [3, 9, 10, 27, 38, 43, 82]
    }
}
    

Heap Sort

Uses a binary heap. It first builds a max heap, then repeatedly extracts the largest element and places it at the end of the array.

Time Complexity	Space Complexity
Best/Avg/Worst: $O(n \log n)$	$O(1)$

Java Code:

import java.util.Arrays;

public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
    public static void main(String args[]) {
        int data[] = {12, 11, 13, 5, 6, 7};
        System.out.println("Original: " + Arrays.toString(data));
        new HeapSort().sort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [5, 6, 7, 11, 12, 13]
    }
}
    

Quick Sort

A Divide and Conquer algorithm that picks a pivot, partitions the array around it, and sorts sub-arrays recursively.

Time Complexity	Space Complexity
Best: $O(n \log n)$, Average: $O(n \log n)$, Worst: $O(n^2)$	$O(\log n)$

Java Code:

import java.util.Arrays;

public class QuickSort {
    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 sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
    public static void main(String args[]) {
        int data[] = {10, 7, 8, 9, 1, 5};
        System.out.println("Original: " + Arrays.toString(data));
        new QuickSort().sort(data, 0, data.length - 1);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [1, 5, 7, 8, 9, 10]
    }
}
    

---

Sorting in Linear Time

Count Sort

Counts the occurrences of each unique element and uses that information to place elements directly into the sorted array. Requires a known, small range of integer inputs.

Time Complexity	Space Complexity
Best/Avg/Worst: $O(n+k)$	$O(k)$

Java Code:

import java.util.Arrays;

public class CountSort {
    public static void countSort(int[] arr) {
        if (arr.length == 0) return;
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        for (int num : arr) count[num]++;
        
        int outputIndex = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                arr[outputIndex++] = i;
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] data = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original: " + Arrays.toString(data));
        countSort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [1, 2, 2, 3, 3, 4, 8]
    }
}
    

Radix Sort

A non-comparative sort that works by sorting integers digit by digit, from least significant to most significant.

Time Complexity	Space Complexity
Best/Avg/Worst: $O(d \cdot (n+k))$	$O(n+k)$

Java Code:

import java.util.Arrays;

public class RadixSort {
    static int getMax(int arr[]) {
        int mx = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] > mx) mx = arr[i];
        return mx;
    }
    static void countSortForRadix(int arr[], int exp) {
        int n = arr.length;
        int output[] = new int[n];
        int count[] = new int[10];
        Arrays.fill(count, 0);
        for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(output, 0, arr, 0, n);
    }
    static void radixsort(int arr[]) {
        int m = getMax(arr);
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSortForRadix(arr, exp);
    }
    public static void main(String[] args) {
        int data[] = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original: " + Arrays.toString(data));
        radixsort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [2, 24, 45, 66, 75, 90, 170, 802]
    }
}
    

Bucket Sort

Works by distributing elements into a number of buckets. Each bucket is then sorted individually. Best for uniformly distributed data.

Time Complexity	Space Complexity
Best: $O(n+k)$, Average: $O(n+k)$, Worst: $O(n^2)$	$O(n+k)$

Java Code:

import java.util.*;

public class BucketSort {
    public static void bucketSort(float[] arr) {
        if (arr.length <= 0) return;
        
        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new List[arr.length];
        
        for (int i = 0; i < arr.length; i++) {
            buckets[i] = new ArrayList<Float>();
        }
        
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (int) (arr[i] * arr.length);
            buckets[bucketIndex].add(arr[i]);
        }
        
        for (int i = 0; i < arr.length; i++) {
            Collections.sort(buckets[i]);
        }
        
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            for (float value : buckets[i]) {
                arr[index++] = value;
            }
        }
    }
    public static void main(String[] args) {
        float[] data = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
        System.out.println("Original: " + Arrays.toString(data));
        bucketSort(data);
        System.out.println("Sorted:   " + Arrays.toString(data));
        // Sorted:   [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]
    }
}
    

UNIT-III: Searching Techniques and Complexity Analysis

---

Searching Techniques

Searching is a fundamental operation that involves finding an item with specified properties among a collection of items. The efficiency of a search algorithm is measured by its time and space complexity.

Linear Search

Linear search is the most basic searching algorithm. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. It can be used on any type of list, sorted or unsorted.

Analogy 🧐: Imagine you're looking for a specific card in a shuffled deck by flipping them over one by one from the top.

Time Complexity	Space Complexity
Best: $O(1)$, Average: $O(n)$, Worst: $O(n)$	$O(1)$

Java Code:

import java.util.Arrays;

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Return the index where the target is found
            }
        }
        return -1; // Return -1 if the target is not in the array
    }

    public static void main(String[] args) {
        int[] data = {22, 35, 12, 6, 89, 43, 91};
        int target = 89;
        
        System.out.println("Array: " + Arrays.toString(data));
        int result = linearSearch(data, target);
        
        if (result != -1) {
            System.out.println("Element " + target + " found at index: " + result);
        } else {
            System.out.println("Element " + target + " not found in the array.");
        }
        // Output: Element 89 found at index: 4
    }
}
    

---

Binary Search

Binary Search is a much more efficient searching algorithm, but it has one crucial requirement: the list must be sorted. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

Analogy 📖: It's like looking for a word in a dictionary. You open to the middle, see if your word comes before or after, and then discard half the dictionary. You repeat this until you find the word.

Time Complexity	Space Complexity
Best: $O(1)$, Average: $O(\log n)$, Worst: $O(\log n)$	$O(1)$

Java Code:

import java.util.Arrays;

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoids potential overflow
            
            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }
            
            // If target is greater, ignore the left half
            if (arr[mid] < target) {
                left = mid + 1;
            } 
            // If target is smaller, ignore the right half
            else {
                right = mid - 1;
            }
        }
        
        return -1; // Target not present in the array
    }
    
    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; // Array must be sorted
        int target = 23;
        
        System.out.println("Sorted Array: " + Arrays.toString(data));
        int result = binarySearch(data, target);

        if (result != -1) {
            System.out.println("Element " + target + " found at index: " + result);
        } else {
            System.out.println("Element " + target + " not found in the array.");
        }
        // Output: Element 23 found at index: 5
    }
}
    

---

Medians & Order Statistics

This field deals with finding a specific element in a list without necessarily sorting the entire list first.

• Order Statistic: The i-th order statistic of a set of 'n' elements is the i-th smallest element.
  • The minimum is the 1st order statistic ($i=1$).
  • The maximum is the n-th order statistic ($i=n$).
• Median: The median is the "middle" element. It is the element that divides the set into two halves: a high half and a low half. For a set of n elements, the median is the $(n+1)/2$-th smallest element if n is odd, and typically the lower of the two middle elements (the $n/2$-th smallest) if n is even.

Selection Algorithm (Quickselect)

Finding the median seems like it would require sorting the array first (which takes $O(n \log n)$ time) and then picking the middle element. However, we can do better! The selection algorithm (often called Quickselect) can find the i-th smallest element in an unsorted array in average linear time.

It works very similarly to Quick Sort. It picks a pivot, partitions the array, and then, instead of recursing on both sides like Quick Sort, it only recurses on the side that contains the element we are looking for. This clever optimization reduces the average time complexity from $O(n \log n)$ to $O(n)$.

Time Complexity	Space Complexity
Best: $O(n)$, Average: $O(n)$, Worst: $O(n^2)$	$O(\log n)$

Java Code (to find the k-th smallest element):

import java.util.Arrays;
import java.util.Random;

public class Quickselect {

    public static int findKthSmallest(int[] arr, int k) {
        if (k < 1 || k > arr.length) {
            throw new IllegalArgumentException("k is out of bounds");
        }
        return quickSelect(arr, 0, arr.length - 1, k - 1); // k-1 because we use 0-based index
    }

    private static int quickSelect(int[] arr, int low, int high, int k) {
        while (low <= high) {
            int pivotIndex = partition(arr, low, high);
            if (pivotIndex == k) {
                return arr[pivotIndex];
            } else if (pivotIndex < k) {
                low = pivotIndex + 1;
            } else {
                high = pivotIndex - 1;
            }
        }
        return -1; // Should not happen if k is valid
    }

    private static int partition(int[] arr, int low, int high) {
        // Randomized pivot to avoid worst-case O(n^2)
        int pivotIndex = new Random().nextInt(high - low + 1) + low;
        swap(arr, pivotIndex, high);
        
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, high);
        return i;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] data = {10, 4, 5, 8, 6, 11, 26};
        System.out.println("Original Array: " + Arrays.toString(data));
        
        // Find the median. For n=7, the median is the (7+1)/2 = 4th smallest element.
        int k = 4;
        int median = findKthSmallest(data, k);
        System.out.println("The " + k + "-th smallest element (median) is: " + median);
        // Output: The 4-th smallest element (median) is: 8
        
        // Let's verify by sorting
        Arrays.sort(data);
        System.out.println("Sorted Array:   " + Arrays.toString(data));
        // Sorted Array:   [4, 5, 6, 8, 10, 11, 26]
    }
}
    

UNIT-IV: Arrays

---

An array is a data structure that stores a collection of elements of the same data type in a contiguous block of memory. Each element is identified by an index, or key.

Single and Multi-dimensional Arrays

Single-dimensional Arrays

A single-dimensional array is the simplest form, representing a linear list of elements.

Java Code:

import java.util.Arrays;

public class SingleDimArray {
    public static void main(String[] args) {
        // Declaration and initialization
        int[] numbers = {10, 20, 30, 40, 50};
        
        // Accessing an element by index (0-based)
        System.out.println("Element at index 2: " + numbers[2]); // Output: 30
        
        // Modifying an element
        numbers[3] = 45;
        
        // Iterating through the array
        System.out.print("Array elements: ");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        // Output: Array elements: 10 20 30 45 50 
    }
}
    

Multi-dimensional Arrays

A multi-dimensional array is an "array of arrays." The most common is a 2D array, which can represent a grid or matrix.

Java Code (2D Array):

public class MultiDimArray {
    public static void main(String[] args) {
        // Declaration and initialization of a 3x3 matrix
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        
        // Accessing an element at row 1, column 2
        System.out.println("Element at [1][2]: " + matrix[1][2]); // Output: 6
        
        // Iterating through the 2D array
        System.out.println("Matrix elements:");
        for (int i = 0; i < matrix.length; i++) { // Iterate through rows
            for (int j = 0; j < matrix[i].length; j++) { // Iterate through columns
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println(); // Newline after each row
        }
    }
}
    

Sparse Matrices

A sparse matrix is a matrix where the number of zero elements is much higher than the number of non-zero elements. Storing it as a standard 2D array is inefficient due to the large amount of wasted space for zeros.

A common way to represent a sparse matrix is using a Triplet Representation, where we only store the non-zero elements along with their row and column indices.

Java Code (Triplet Representation):

import java.util.ArrayList;
import java.util.List;

class Triplet {
    int row, col, value;
    Triplet(int r, int c, int v) {
        row = r; col = c; value = v;
    }
    @Override
    public String toString() {
        return "(" + row + ", " + col + ", " + value + ")";
    }
}

public class SparseMatrix {
    public static void main(String[] args) {
        int[][] matrix = {
            {0, 0, 3, 0, 4},
            {0, 0, 5, 7, 0},
            {0, 0, 0, 0, 0},
            {0, 2, 6, 0, 0}
        };
        
        List<Triplet> sparseRepresentation = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != 0) {
                    sparseRepresentation.add(new Triplet(i, j, matrix[i][j]));
                }
            }
        }
        
        System.out.println("Sparse Matrix (Triplet Representation):");
        System.out.println(sparseRepresentation);
        // Output: [(0, 2, 3), (0, 4, 4), (1, 2, 5), (1, 3, 7), (3, 1, 2), (3, 2, 6)]
    }
}
    

UNIT-V: Stacks and Queues

---

Stacks

A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last element added to the stack is the first one to be removed.
Analogy 🥞: A stack of pancakes. You add a new pancake to the top and also take one from the top.

Core operations are: push (add to top), pop (remove from top), and peek (view top element).

Implementing Stack using Array

public class ArrayStack {
    private int[] arr;
    private int top;
    private int capacity;

    public ArrayStack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    public void push(int x) {
        if (isFull()) {
            System.out.println("Stack Overflow");
            return;
        }
        arr[++top] = x;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return -1;
        }
        return arr[top--];
    }

    public int peek() {
        if (isEmpty()) return -1;
        return arr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }
    
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        stack.push(10);
        stack.push(20);
        System.out.println("Top element is: " + stack.peek()); // 20
        System.out.println("Popped element: " + stack.pop()); // 20
        System.out.println("Is stack empty? " + stack.isEmpty()); // false
    }
}
    

Prefix, Infix and Postfix Expressions

These are different ways to write arithmetic expressions:

• Infix: The standard way we write expressions. Operator is between operands. Ex: A + B
• Prefix (Polish Notation): Operator comes before operands. Ex: + A B
• Postfix (Reverse Polish Notation): Operator comes after operands. Ex: A B +

Utility: Postfix and Prefix notations are easier for computers to evaluate because they don't require rules for operator precedence or parentheses. Stacks are the key data structure used to evaluate these expressions and to convert from Infix to Postfix.

Queues

A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The first element added is the first to be removed.
Analogy 🚶‍♂️🚶‍♀️: A line of people waiting for a ticket. The first person in line is the first person served.

Core operations: enqueue (add to rear), dequeue (remove from front).

Array and Linked representation of Queue

Queues can be implemented using arrays (often circular arrays for efficiency) or linked lists.

Java Code (Linked List Queue):

class QNode {
    int key;
    QNode next;
    public QNode(int key) {
        this.key = key;
        this.next = null;
    }
}

public class LinkedListQueue {
    QNode front, rear;

    public LinkedListQueue() {
        this.front = this.rear = null;
    }

    void enqueue(int key) {
        QNode temp = new QNode(key);
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
        this.rear.next = temp;
        this.rear = temp;
    }

    void dequeue() {
        if (this.front == null) return;
        this.front = this.front.next;
        if (this.front == null) this.rear = null;
    }

    public static void main(String[] args) {
        LinkedListQueue q = new LinkedListQueue();
        q.enqueue(10);
        q.enqueue(20);
        System.out.println("Front item is " + q.front.key); // 10
        q.dequeue();
        System.out.println("New front item is " + q.front.key); // 20
    }
}
    

De-queue and Priority Queues

• De-queue (Double-Ended Queue): A generalized version of a queue where elements can be added or removed from either the front or the rear.
• Priority Queue: An abstract data type where each element has an associated "priority." Elements with higher priority are served before elements with lower priority, regardless of their order of arrival. They are often implemented using a Heap.

UNIT-VI: Linked Lists

---

A Linked List is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (a node) contains a data field and a reference (or link) to the next node in the sequence.

Singly, Doubly and Circular Lists

Singly Linked List

Each node contains data and a single pointer to the next node. Traversal is only possible in the forward direction.

Java Code:

public class SinglyLinkedList {
    Node head;

    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; next = null; }
    }
    
    public void insertAtEnd(int newData) {
        Node newNode = new Node(newData);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        list.printList(); // Output: 1 -> 2 -> 3 -> null
    }
}
    

Doubly Linked List

Each node contains data, a pointer to the next node, and a pointer to the previous node. This allows for traversal in both forward and backward directions.

Circular Linked List

A variation where the last node's `next` pointer points back to the head of the list instead of `null`, forming a circle. This is useful for applications that require continuous looping, like round-robin scheduling.

UNIT-VII: Recursion

---

Developing Recursive Definition of Simple Problems

Recursion is a programming technique where a function calls itself to solve a problem. A recursive function must have two key components:

1. Base Case: A condition that stops the recursion. Without a base case, the function would call itself indefinitely, leading to a stack overflow error.
2. Recursive Step: The part of the function that calls itself, but with modified arguments that move it closer to the base case.

Example: Factorial using Recursion

public class RecursiveFactorial {

    public static long factorial(int n) {
        // Base Case: if n is 0, factorial is 1
        if (n == 0) {
            return 1;
        }
        // Recursive Step: n * factorial of (n-1)
        else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println("Factorial of " + number + " is: " + factorial(number));
        // Output: Factorial of 5 is: 120
    }
}
    

Advantages and Limitations of Recursion

Advantages ✅

• Elegance and Readability: Recursive code can be cleaner and more intuitive for problems that are naturally recursive, like tree traversals or divide-and-conquer algorithms.
• Less Code: It can often solve complex problems with fewer lines of code compared to an iterative approach.

Limitations ❌

• Performance Overhead: Each recursive call adds a new frame to the call stack, consuming memory and time. Iterative solutions are often faster.
• Memory Usage: For deep recursion, the call stack can consume a large amount of memory.
• Stack Overflow: If the recursion is too deep (i.e., the base case is not reached after many calls), it can exhaust the stack memory, causing a stack overflow error.

DSA Knowledge Check 🧠

---

1. Which data structure operates on the Last-In, First-Out (LIFO) principle?

• Queue
• Stack
• Array
• Linked List

2. What is the worst-case time complexity of Quick Sort?

• $O(n \log n)$
• $O(n)$
• $O(n^2)$
• $O(\log n)$

3. Which searching algorithm requires the data to be sorted beforehand?

• Linear Search
• Quickselect
• Binary Search
• Greedy Search

4. What is the essential component of a recursive function that prevents infinite loops?

• The recursive step
• A for loop
• The base case
• A return statement

5. A matrix with significantly more zero elements than non-zero elements is called a:

• Multi-dimensional Array
• Sparse Matrix
• Full Matrix
• Triplet

Submit Quiz