pakyu Christian Gutierrez CS student na taga Caloocan

Tree Edge (DFS)

An edge that discovers a previously unvisited vertex and becomes part of the DFS tree.

Pivot (Quick Sort)

The element chosen to partition the array into smaller and larger elements.

Insertion Sort

A sorting algorithm that builds a sorted list by inserting each element into its proper position.

Topological Sort

An ordering of vertices in a directed acyclic graph where every edge points from an earlier vertex to a later vertex.

Post-order Traversal

A tree traversal that visits all subtrees before visiting the node itself.

Interpolation Search

A search algorithm that estimates the target's position based on the values at the ends of the search interval.

In-order Traversal

A tree traversal that visits the left subtree, the node, and then the right subtree.

Gapped Insertion Sort

An insertion sort performed on elements separated by a fixed gap, used in Shell Sort.

Depth-First Search (DFS)

A graph traversal method that explores as far as possible along one path before backtracking.

Decrease by a Constant

A decrease-and-conquer technique that reduces the problem size by a fixed amount in each step.

Pre-order Traversal

A tree traversal that visits the node before its subtrees.

Cross Edge (BFS)

An edge connecting vertices on the same or adjacent levels that is not part of the BFS tree.

Prim Key

The minimum edge weight needed to connect a vertex to the growing minimum spanning tree.

Kahn's Algorithm

A queue-based algorithm that repeatedly removes vertices with zero in-degree to produce a topological order.

Decrease by a Constant Factor

A decrease-and-conquer technique that reduces the problem size by a fixed fraction, such as one-half, in each step.

Time Complexity Θ(n²)

An asymptotic bound indicating that the running time grows proportionally to the square of the input size.

Relaxation (Shortest Path)

The process of updating a vertex's shortest known distance when a shorter path is found.

Merge Sort

A stable divide-and-conquer sorting algorithm that splits, sorts, and merges arrays recursively.

Top-Down

A problem-solving approach that starts with the original problem and recursively breaks it into smaller sub-problems.

BFS Queue

The queue used to store vertices waiting to be explored in Breadth-First Search.

Union-Find

A data structure that manages disjoint sets and supports efficient union and find operations.

DFS Stack

The stack used to store vertices waiting to be explored in Depth-First Search.

Shaker Sort

A bi-directional variation of Bubble Sort that alternates left-to-right and right-to-left passes.

Breadth-First Search (BFS)

A graph traversal algorithm that visits vertices level by level using a queue.

Space Complexity O(V + E)

Memory usage proportional to the number of vertices and edges in a graph.

Quick Sort

An in-place divide-and-conquer sorting algorithm that partitions an array around a pivot and recursively sorts the partitions.

DFS-based Topological Sort

A topological sorting method that performs DFS and outputs vertices in reverse finishing order.

Minimum Spanning Tree (MST)

A set of edges that connects all vertices with the minimum total weight and no cycles.

Binary Search

A search algorithm that repeatedly halves the search interval to find a target in a sorted array.

Shell Sort

An in-place sorting algorithm that sorts elements separated by decreasing gap values.

Decrease and Conquer

An algorithm design strategy that solves a problem by reducing it to a smaller instance and extending the solution.

Prim's Algorithm

A greedy algorithm that builds a minimum spanning tree by repeatedly adding the cheapest edge connected to the current tree.

Euclid's GCD Algorithm

An algorithm that repeatedly replaces the larger number with the remainder until the remainder becomes zero.

Kruskal's Algorithm

A greedy algorithm that builds a minimum spanning tree by adding edges in increasing order of weight while avoiding cycles.

In-degree

The number of incoming edges to a vertex.

Partition (Quick Sort)

The process of rearranging elements so those smaller than the pivot are on one side and larger elements are on the other.

Dijkstra's Algorithm

A greedy algorithm that finds the shortest paths from a source vertex to all other vertices in a graph with non-negative edge weights.

Gap Sequence (Shell Sort)

A sequence of decreasing gap values used to determine which elements are compared in Shell Sort.

Russian-Peasant Multiplication

A multiplication algorithm that repeatedly halves one number and doubles the other, adding selected values.

Quickselect

An algorithm that finds the k-th smallest element by partitioning the array around a pivot.

Variable-Size-Decrease

A decrease-and-conquer technique where the amount of reduction varies depending on the input.

Fake-Coin Problem

A puzzle that identifies a counterfeit coin using repeated weighings that reduce the number of candidates.

Directed Acyclic Graph (DAG)

A directed graph with no cycles.

Shortest-Path Tree

A tree containing the shortest paths from a source vertex to all reachable vertices.

Greedy Algorithm

An algorithmic strategy that makes the locally optimal choice at each step without reconsidering previous choices.

Stable Sort

A sorting algorithm that preserves the relative order of equal elements.

Time Complexity O(E log E)

The running time of algorithms that sort edges and use Union-Find operations, such as Kruskal's Algorithm.

Bottom-Up

An iterative approach that starts with the smallest sub-problems and builds up to the original problem.

Divide and Conquer

An algorithm design strategy that divides a problem into independent sub-problems, solves them recursively, and combines their solutions.

Back Edge (DFS)

An edge that connects a vertex to one of its ancestors in the DFS tree, indicating a cycle in a directed graph.