Algorithms and Data Structures 1

Module 1: Complexity and Asymptotic Analysis

Classic algorithms are defined as generally applicable, unambiguous, and formal executable rules meant for the step-by-step solving of a specific task class. Deterministic algorithms possess exactly one possibility of continuation at any given point during processing. To evaluate these algorithms, memory and runtime complexities are measured, where the runtime complexity for a problem of size $n$ is denoted as $T_P(n)$.

The strict worst-case runtime is formally defined as:
$$T_P(n) = \sup \{ T_P(x) \mid |x| = n \text{ and } x \text{ is input for } P \}$$

Amortized worst-case analysis considers the average effort across the worst possible sequence of operations.

Asymptotic behaviour utilizes Big-O notation, characterizing functions where $f = O(g)$ holds if $$\exists c \in \mathbb{R}^+, n_0 \in \mathbb{N}_0, \forall n \ge n_0: f(n) \le c g(n)$$,. Polynomial time algorithms fall under bounds like $O(n^k)$, whereas exponential time limits reflect $O(k^n)$ bounds.

For recursive algorithms, complexity is calculated using the Master Theorem for equations structured as $$T(n) = aT(n/b) + f(n)$$. The theorem is split into three core cases:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for a constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a} \log^k n)$, then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and $af(n/b) \le cf(n)$, then $T(n) = \Theta(f(n))$.

Module 2: Abstract Data Types & Linear Structures

Abstract Data Types (ADTs) conceptualize data structures by defining the data stored, supported operations, and specific error conditions. Dynamic data structures, including lists, stacks, and queues, are generated dynamically at runtime to resize as needed.

The Stack ADT operates on a Last-In-First-Out (LIFO) model, accessing only the topmost element. Array-based and linked-node stack implementations yield $O(1)$ constant runtimes for push and pop operations,. Stacks act as critical auxiliary structures; for example, the algorithm to compute spans $S[i]$ of an array takes quadratic $O(n^2)$ time natively but reduces to $O(n)$ time when utilizing a stack to record "look back" indices,.

The Queue ADT provides First-In-First-Out (FIFO) access, adding elements to the rear and removing them from the front,. Doubly linked lists extend this by maintaining references to both the previous and next nodes, allowing more efficient, bidirectional traversal and node manipulation,. Skip Lists offer a probabilistic arrangement of levels $h$, where sequences shrink progressively, yielding an average height of $\log N$ and search times of $O(\log N)$. Elements from a level $S_{i-1}$ carry a probability of $1/2$ to ascend to level $S_i$.

Module 3: Recursion and Recurrence Relations

Recursion resolves issues by mapping complex occurrences down to smaller, self-similar occurrences. Every valid recursive setup mandates a base case (a trivial, direct answer) and a recursive case (breaking the problem down).
A classical example is the factorial function, formulated as:

$$n! = n(n-1)!$$

Additionally, binomial coefficients evaluate via mutual subset calculations:

$$bin(n, k) = bin(n-1, k-1) + bin(n-1, k)$$

Tail recursion arises when the recursive call is the absolute final statement executed, omitting any residual stack evaluation and facilitating compiler optimizations to iterative loops,. The Towers of Hanoi puzzle involves shifting $N$ discs between rods recursively. The computational effort traces the recurrence relation: $T(N) = 2T(N-1) + 1$, yielding the geometric sum: $T(N) = 2^N - 1 = O(2^N)$.

Module 4: Trees, Heaps, and Priority Queues

A tree represents an acyclic, simple, coherent graph characterized by exactly one root node and zero cycles. The vertical distance determines node depths, and the total height dictates worst-case boundaries bounded mathematically by: $$\text{height} \ge \log_2(\text{number of nodes}) - 1$$. Traversals typically follow Preorder, Postorder, and Inorder schemas.

Priority Queues fetch items based on a total order relation, meaning elements $k$ abide by reflexivity, transitivity, and anti-symmetry. Employing an unsorted sequence to power a priority queue creates severe inefficiencies, degrading selection sorting to $O(N^2)$ due to full sequence traversal for insertions and removals,.

Heaps operate as optimized binary trees abiding by the heap-order property, where order is continuously restored via Upheap (bubbling up smaller children) or Downheap (swapping a parent with its smallest child),. Vector-based implementations map nodes logically instead of via pointers: a node at index $i$ stores its left child at index $2i$ and its right child at $2i+1$. Bottom-up heap construction establishes global heaps iteratively by processing sub-heaps progressively.

Module 5: Sorting Algorithms

Comparison-based sorting possesses a firm lower efficiency bound of $\Omega(N \log N)$. This barrier is mathematically derived using Stirling's approximation of $n!$:

$$\log_2(n!) \approx \log_2 \left( \sqrt{2\pi n} \left( \frac{n}{e} \right)^n \right) = \Theta(n \log n)$$

Basic methodologies like SelectionSort and InsertionSort parse progressively to build ordered subsets, averaging $O(N^2)$ runtimes,. ShellSort leverages gap sequences to cross-compare elements, historically deploying sequences like Sedgewick's $4^i + 3 \cdot 2^i - 1$.

Divide-and-conquer mechanics power MergeSort and QuickSort,. MergeSort inherently guarantees $O(N \log N)$ by cutting sequences equally and zipping them logically. QuickSort utilizes a pivot to partition arrays in-place; while highly efficient on average ( $O(N \log N)$ ), it fails toward $O(N^2)$ if the pivot repeatedly segregates edge elements poorly.

BucketSort circumvents the comparison barrier via digital key separation, dropping data into discrete shelves to maintain linear average-case constraints,.

Module 6: Strings & Pattern Matching

String mapping frequently utilizes the MAD (Multiply, Add, and Divide) hash function, defined as $$h(k) = |ak+b| \bmod N$$. The Rabin-Karp pattern matching algorithm updates rolling hashes continuously in constant time by executing:

$$x(i+1) = x(i) \cdot b - t[i] \cdot b^m + t[i+m]$$

The Knuth-Morris-Pratt (KMP) method bypasses raw brute-force search by navigating a Finite State Machine (FSM) constructed strictly from the pattern's sub-prefixes,. KMP utilizes a match(j) array to execute safe shifts without redundant comparisons.

Standard Tries act as character-by-character search trees where paths terminate in valid string nodes. To suppress prefix redundancy, strings are padded with terminating symbols like $. Compressed Tries (PATRICIA Tries) significantly decrease memory overhead by dissolving single-child structural chains into compact string-coordinate tuples,.

Module 7: Randomized Algorithms & Optimization

Randomized algorithms use stochastic mechanisms to make logical pathway decisions, behaving non-deterministically. Las Vegas algorithms reliably produce the correct mathematical answer despite variable completion times, whereas Monte Carlo algorithms stick to a firm time limit while hazarding a potentially incorrect prediction.

Monte Carlo simulations model probabilistic domains using vast numbers of random sampling iterations. Estimating definite integrals under this mechanism compares points strictly above or below a curve threshold $y_{rand} \le f(x_{rand})$.

Simulated Annealing mimics thermodynamic metal cooling to sidestep gradient-method local optima traps. Based on the Boltzmann distribution, it evaluates potential energy states probabilistically:

$$\text{Prob}(E) \sim \exp \left( \frac{-E}{kT} \right)$$

Better configurations ( $E_{i+1} \le E_i$ ) are universally embraced, while costlier layouts are adopted randomly via the threshold $\exp(-(E_{i+1} - E_i)/kT)$.