Analysis of Algorithms - Modules 1 to 3

Comprehensive practice flashcards defining essential terminology, algorithms, complexity bounds, and recurrence methods covered across Modules 1 to 3.

Algorithm

A step-by-step procedure and set of rules defined in a specific order to carry out a predefined computation or solve a problem.

Definiteness

An algorithm property requiring all instructions to be unambiguous, simple to interpret, concise, and precise, leaving no room for multiple interpretations.

Finiteness

An algorithm property stating that every algorithm must terminate after a finite number of steps, ensuring loops have finite bounds and recursive calls possess well-defined base cases.

Effectiveness

An algorithm property requiring operations to be basic enough to be performed exactly using elementary operations, analogous to pencil-and-paper computation.

Space Complexity

The amount of memory required by an algorithm to execute and solve a problem, governed by fixed-size components (instructions, constants) and variable-size components (recursion stack, dynamic structures).

Time Complexity

The measure of time taken by an algorithm to solve a problem, expressed as a function of the number of primitive operations performed rather than physical clock time.

Primitive Operation

The most frequent fundamental operation appearing in an algorithm (such as comparison in sorting or addition in matrix sum) that forms the dominant cost component.

Order of Growth

The relationship between input size $n$ and algorithm performance, describing how rapidly the running time grows as input size increases.

Big Oh Notation ($O$)

An asymptotic notation providing an upper bound for execution time; $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

Big Omega Notation ($\Omega$)

An asymptotic notation providing a lower bound for execution time; $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$.

Big Theta Notation ($\Theta$)

An asymptotic notation providing an asymptotically tight bound; $f(n) = \Theta(g(n))$ if there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$.

Crossover Point ($n_0$)

The threshold value of problem size $n$ beyond which a function $f(n)$ strictly stays within the bound established by $c \cdot g(n)$.

Intractable Problem

A problem that can theoretically be solved but requires an unacceptably large, computationally infeasible amount of time, giving it no practical application.

Tractable Problem

A problem that can be solved theoretically and practically within a reasonable amount of time, specifically in polynomial time $O(p(n))$ by a deterministic Turing machine.

Decision Problem

A computational problem that produces a Boolean output of either 'Yes' or 'No' for any given input instance.

Optimization Problem

A computational problem seeking the best solution (such as maximum profit or least cost) from the entire set of feasible solutions.

P Problems (PTIME / DTIME)

The class of problems that can be solved in polynomial time by deterministic algorithms.

NP Problems

The class of problems solvable in non-deterministic polynomial time, operating with a non-deterministic guessing stage and a deterministic polynomial-time verification stage.

Polynomial-Time Reducibility ($A \le_p B$)

A transformation mapping input $x$ of decision problem $A$ to input $f(x)$ of problem $B$ in polynomial time such that $f(x)$ is 'Yes' for $B$ if and only if $x$ is 'Yes' for $A$.

NP-Complete (NPC) Problem

A decision problem $C$ that is in class NP, where every problem $X$ in NP is reducible to $C$ in polynomial time ($X \le_p C$).

NP-Hard Problem

A problem to which every problem in NP can be reduced in polynomial time, regardless of whether it belongs to NP or is a decision problem.

Vertex Cover

A subset of vertices $V' \subseteq V$ in a graph $G = (V, E)$ such that every edge $(u, v) \in E$ has at least one endpoint incident in $V'$.

Clique

A complete subgraph of a graph $G$ in which an edge exists between every distinct pair of vertices.

Selection Sort

An in-place, comparison-based sorting algorithm that iteratively selects the minimum element from the unsorted sublist and swaps it into its correct position, taking $\Theta(n^2)$ time across all cases.

Insertion Sort

An in-place, incremental sorting algorithm that builds a sorted array by inserting one unsorted element at a time into its proper place by shifting larger elements to the right.

Insertion Sort Simulation on Array

An 8-step simulation demonstrating how each incoming number is compared, larger elements are shifted right, and the number is inserted into its correct position.

Recurrence Equation

An equation that recursively defines a function or sequence using smaller argument values, commonly representing the running time of recursive algorithms.

Forward Substitution

A recurrence solving method that computes the solution of progressively larger problems starting from the base condition until problem size $n$ is solved.

Backward Substitution

A recurrence solving method that repeatedly replaces $T(n)$ with expressions involving $T(n-1)$, $T(n-2)$, and so on until it reaches the base condition.

Recursion Tree

A tree structure where each node represents the cost of an individual subproblem at a given level of recursion, allowing the total cost to be calculated by summing all levels.

Master Method

An algorithmic tool used to quickly solve recurrences of the form $T(n) = a \cdot T(n/b) + f(n)$ by comparing $f(n)$ to $n^{\log_b(a)}$.

Divide and Conquer

A top-down recursive design paradigm that breaks a problem into smaller independent subproblems (Divide), solves them recursively (Conquer), and merges their results into a solution (Combine).

In-place Sorting

A sorting algorithm characteristic where sorting requires only a constant amount of additional memory ($O(1)$) beyond the input array.

Stable Sorting

A sorting algorithm characteristic ensuring that elements with equal key values retain their relative original input order in the sorted output.

Two-Way Merge

The process of combining two sorted arrays of size $m$ and $n$ into a single sorted array of size $(m + n)$ using linear comparisons.

Merge Sort

A divide-and-conquer sorting algorithm that splits an array into two halves, recursively sorts each half, and merges them in linear time, yielding $\Theta(n \log_2(n))$ complexity across all cases.

Quick Sort (Partition Exchange Sort)

A divide-and-conquer algorithm invented by Tony Hoare that chooses a pivot, partitions elements such that smaller values precede the pivot and larger values succeed it, and sorts subarrays recursively.

Randomized Quick Sort

A variant of quicksort that selects a pivot randomly to avoid worst-case $O(n^2)$ behavior on sorted or nearly sorted inputs, achieving expected $O(n \log_2(n))$ time.

Binary Search

A divide-and-conquer search algorithm on sorted arrays that tests the target key against the middle element, reducing the search space by half each iteration to run in $O(\log_2(n))$ time.

Ternary Search

A search algorithm that divides a sorted array into three equal parts using two cut points (oneThird and twoThird), exhibiting a worst-case running time of $\Theta(\log(n))$.

Min-Max Problem (Divide and Conquer)

An algorithm that finds the maximum and minimum elements in an array simultaneously by recursively splitting the array, requiring only $(\frac{3n}{2} - 2)$ comparisons.

Strassen's Matrix Multiplication

A divide-and-conquer algorithm that multiplies two $n \times n$ matrices using 7 submatrix multiplications instead of 8, achieving a time complexity of $O(n^{\log_2(7)}) \approx O(n^{2.81})$.

Greedy Algorithm

A problem-solving paradigm that builds a solution step by step by making locally optimal, irrevocable choices at each stage without reconsidering past decisions.

Greedy Choice Property

The property that a globally optimal solution can be assembled by making sequential locally optimal choices at each decision point.

Optimal Substructure

The property that an optimal solution to a problem contains within it the optimal solutions to its constituent subproblems.

Dijkstra's Algorithm

A greedy algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights in $O(|V|^2)$ time.

Fractional Knapsack Problem

A knapsack problem variant where items can be divided into fractions, solved optimally by a greedy strategy that sorts and selects items by decreasing profit-to-weight ratio ($v_i / w_i$).

0/1 Knapsack Problem

A knapsack problem variant where each item must either be fully included or completely excluded; greedy heuristics fail to guarantee an optimal solution for this variant.

Job Sequencing with Deadlines

An optimization problem of scheduling unit-time jobs with deadlines and profits on a single processor, solved greedily by ordering jobs by decreasing profit and scheduling each in its latest free feasible slot.

Spanning Tree

A connected, acyclic subgraph of a connected, undirected graph $G = (V, E)$ that contains all vertices $V$ and a subset of edges $E' \subseteq E$ with cardinality $|V| - 1$.

Minimum Spanning Tree (MST)

A spanning tree of a weighted, connected, undirected graph that possesses the minimum possible sum of edge weights.

Prim's Algorithm

A greedy algorithm that constructs an MST starting from an arbitrary vertex by repeatedly adding the minimum-weight edge connecting the current tree to an unvisited vertex; optimal for dense graphs.

Kruskal's Algorithm

A greedy algorithm that constructs an MST by sorting all edges by weight and iteratively adding the minimum-weight edge that does not create a cycle using Disjoint Set (Union-Find) operations.

Mean Retrieval Time (MRT)

The average time required to retrieve programs stored on a tape, which is minimized by ordering programs in non-decreasing order of their lengths.