Data Structures and Algorithms in Java

Vocabulary flashcards generated from the Data Structures & Algorithms Java lecture notes, covering essential computer science concepts, Java architecture details, algorithms, and key data structure definitions.

Algorithm

A finite, well-defined sequence of steps that solves a problem.

Data Structure

A way of organising data in memory so that operations such as insert, delete, search, and update are efficient.

JDK (Java Development Kit)

The complete development kit containing the JRE along with development tools such as javac, javadoc, jar, and debuggers.

JRE (Java Runtime Environment)

The execution environment containing the JVM and core class libraries required to run Java programs.

JVM (Java Virtual Machine)

An abstract machine that loads, verifies, and executes bytecode using a class loader, interpreter, and JIT (Just-In-Time) compiler.

Integer Caching Trap

The behavior in Java where Integer wrapper objects within the range $-128$ to $127$ are cached and evaluate to true on == comparisons, whereas values outside this range evaluate to false.

Amortized Analysis

An analysis method computing the average cost per operation over a worst-case sequence of operations, such as dynamic array reallocation in ArrayList.add() averaging $O(1)$.

Sieve of Eratosthenes

An algorithm for finding all prime numbers up to $n$ by iteratively marking the multiples of each prime as composite, running in $O(n \log(\log(n)))$ time.

Kadane's Algorithm

An algorithm used to find the maximum sum of a contiguous subarray in an array of numbers in $O(n)$ time.

Moore's Voting Algorithm

An algorithm that identifies the majority element (an element appearing more than $\frac{n}{2}$ times) in an array using $O(n)$ time and $O(1)$ auxiliary space.

Cycle Sort

An in-place sorting algorithm used when elements fall in the range $1$ to $n$ (or $0$ to $n$), placing each element directly at its correct index in $O(n)$ time.

Knuth-Morris-Pratt (KMP) Algorithm

A pattern-matching algorithm that utilizes a longest proper prefix-suffix (LPS) array to prevent redundant character checks, running in $O(n + m)$ time.

LRU Cache

A Least Recently Used cache structure maintaining item access order using a HashMap combined with a doubly linked list to achieve $O(1)$ get and put operations.

Monotonic Stack

A stack structure maintaining its elements strictly in increasing or decreasing order, used to find the next or previous greater or smaller element in $O(n)$ time.

Dijkstra's Algorithm

A greedy single-source shortest path algorithm for graphs with non-negative edge weights using a min-priority queue, running in $O((V + E) \log(V))$ time.

Bellman-Ford Algorithm

A single-source shortest path algorithm capable of handling graphs with negative edge weights and detecting negative weight cycles in $O(V \times E)$ time.

Floyd-Warshall Algorithm

A dynamic programming algorithm designed to compute all-pairs shortest paths in a weighted graph in $O(V^3)$ time.

Disjoint Set Union (DSU)

A data structure tracking a partition of elements into disjoint sets that supports find and union operations in near-constant time ($O(\alpha(n))$) using path compression and union by rank or size.

Trie

A tree-based prefix data structure storing strings character by character, enabling search, insertion, and prefix lookups in $O(L)$ time where $L$ is the length of the string.

Segment Tree

A binary tree structure that stores range aggregate values over array intervals, allowing range queries and point or range updates in $O(\log(n))$ time.

Fenwick Tree (Binary Indexed Tree)

A compact structure that computes prefix sums and supports element updates in an array in $O(\log(n))$ time using bitwise operations (i & (-i)).

A* Search Algorithm

A pathfinding algorithm evaluating nodes using $f(n) = g(n) + h(n)$, combining the actual path cost $g(n)$ with an admissible heuristic estimate $h(n)$.