Data Structures and Algorithms Vocabulary

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/60

flashcard set

Earn XP

Description and Tags

Comprehensive vocabulary flashcards covering fundamental data structures, algorithms, asymptotic analysis, trees, heaps, hash tables, graph algorithms, greedy methods, divide-and-conquer, and randomized algorithms.

61 Terms

1
New cards

Abstract Data Type (ADT)

A formal specification of a data type defined purely in terms of its data items and associated operations from the user's perspective, independent of its concrete programming implementation.

2
New cards

Big-Oh Notation (OO)

An asymptotic upper bound stating that T(n)=O(f(n))T(n) = O(f(n)) if there exist constants c>0c > 0 and n0>0n_0 > 0 such that T(n)≤c⋅f(n)T(n) \le c \cdot f(n) for all n>n0n > n_0.

3
New cards

Big-Omega Notation (Ω\Omega)

An asymptotic lower bound stating that T(n)=Ω(f(n))T(n) = \Omega(f(n)) if there exist constants c>0c > 0 and n0>0n_0 > 0 such that T(n)≥c⋅f(n)T(n) \ge c \cdot f(n) for all n>n0n > n_0.

4
New cards

Big-Theta Notation (Θ\Theta)

An asymptotically tight bound stating that T(n)=Θ(f(n))T(n) = \Theta(f(n)) if and only if T(n)=O(f(n))T(n) = O(f(n)) and T(n)=Ω(f(n))T(n) = \Omega(f(n)).

5
New cards

Polynomial Time Efficiency

The formal criterion that an algorithm is efficient if its worst-case step count on an input of size nn is bounded by a polynomial p(n)=adnd+⋯+a1n+a0p(n) = a_d n^d + \dots + a_1 n + a_0.

6
New cards

Positional List ADT

A list ADT that stores elements at abstract locations called positions, where each position continues to reference the same entry regardless of subsequent insertions or deletions elsewhere in the collection.

7
New cards

Doubly Linked List

A concrete data structure consisting of a sequence of nodes where each node stores an element and references to both its previous (prev) and next (next) nodes, bounded by header and trailer sentinel nodes.

8
New cards

Stack ADT

A sequential collection following Last-In-First-Out (LIFO) semantics, where elements are inserted via push(e) and removed via pop() at the top position.

9
New cards

Queue ADT

A sequential collection following First-In-First-Out (FIFO) semantics, supporting element insertion at the rear via enqueue(e) and element removal from the front via dequeue().

10
New cards

Dynamic Iterator vs. Snapshot Iterator

A snapshot iterator freezes the contents of the data structure at the moment of creation, whereas a dynamic iterator actively reflects modifications made to the collection during iteration.

11
New cards

Rooted Tree

A hierarchical data structure consisting of nodes with parent-child relationships containing a unique root node without a parent, where every other node has a unique parent and no cycles exist.

12
New cards

Internal Node vs. External Node

An internal node is any tree node that has at least one child, whereas an external node (or leaf) has zero children.

13
New cards

Depth of a Node vs. Height of a Tree

The depth of a node is the number of ancestors excluding itself, while the height of a tree is the maximum depth among all nodes in the tree.

14
New cards

Proper Binary Tree

An ordered tree in which each internal node has at most two children, labeled respectively as left and right children, such that every internal node has exactly two children.

15
New cards
<p>Binary Tree Node (Linked Structure)</p>

Binary Tree Node (Linked Structure)

A concrete representation of a binary tree node containing fields for its stored element, a pointer to its parent node, a pointer to its left child, and a pointer to its right child.

16
New cards
<p>General Tree Node (Linked Structure)</p>

General Tree Node (Linked Structure)

A concrete representation of a general tree node containing fields for its stored element, a reference to its parent node, and a linear sequence/collection of references to all its children.

17
New cards

Preorder Traversal

A tree traversal strategy that visits the current node vv before recursively traversing the subtrees rooted at each of its children.

18
New cards

Postorder Traversal

A tree traversal strategy that recursively visits the subtrees rooted at each child of node vv before performing the visit operation on node vv itself.

19
New cards

Inorder Traversal

A traversal specific to binary trees that recursively visits the left subtree of node vv, then visits node vv, and finally recursively visits the right subtree of node vv.

20
New cards

Euler Tour Traversal

A generic binary tree walk that circumnavigates the perimeter of the tree, visiting each node up to three times: on the left (preorder), from below (inorder), and on the right (postorder).

21
New cards

Binary Search Tree (BST) Property

The ordering condition for a binary tree stating that for every node vv, every key in the left subtree of vv is strictly less than key(v)\text{key}(v), and every key in the right subtree of vv is strictly greater than key(v)\text{key}(v).

22
New cards

Inorder Successor (BST Deletion)

The internal node holding the smallest key in the right subtree of node ww, used to replace the entry of ww when deleting a node possessing two internal children.

23
New cards

AVL Tree

A rank-balanced binary search tree in which the rank of every node represents its subtree height, satisfying the constraint that the heights of the two children of every internal node differ by at most 11.

24
New cards
<p>Trinode Restructuring (Single Rotation)</p>

Trinode Restructuring (Single Rotation)

A local tree rebalancing operation on nodes xx, yy, and zz that restores the AVL balance constraint in O(1)O(1) time by rotating the middle-value node to become the parent of the other two.

25
New cards

Map ADT

A searchable collection of unique key-value entries supporting lookup (get(k)), insertion or value replacement (put(k, v)), and deletion (remove(k)).

26
New cards

Priority Queue ADT

An abstract data type storing key-value items that grants access and deletion exclusively to the entry with the minimum key via min() and remove_min().

27
New cards
<p>Min-Heap</p>

Min-Heap

A binary tree storing items that satisfies the Heap-Order property (key(v)≥key(parent(v))\text{key}(v) \ge \text{key}(\text{parent}(v)) for all v≠rootv \ne \text{root}) and the Complete Binary Tree property, ensuring a height of O(log⁡n)O(\log n).

28
New cards

Upheap vs. Downheap

Upheap restores the heap-order property by swapping a key along an upward path to the root after insertion; downheap restores it by swapping a key downward with its smaller child after removal.

29
New cards

Heap-Sort

A comparison-based sorting algorithm that inserts nn elements into a heap priority queue and sequentially executes nn remove_min() operations, running in O(nlog⁡n)O(n \log n) time.

30
New cards

Array Representation of a Heap

A compact array layout for a heap of size nn where the root is at index 00, and for any node at index ii, its left child is at 2i+12i + 1, its right child is at 2i+22i + 2, and its parent is at ⌊(i−1)/2⌋\lfloor (i - 1)/2 \rfloor.

31
New cards

Load Factor (α\alpha)

The ratio α=nN\alpha = \frac{n}{N} representing the average number of entries per bucket in a hash table, where nn is the number of stored keys and NN is the total array capacity.

32
New cards

Separate Chaining

A collision resolution mechanism where each hash table cell points to an external linked list containing all key-value entries mapped to that bucket index.

33
New cards

Linear Probing

An open addressing technique that resolves collisions by systematically probing consecutive table cells circularly until an empty slot or matching key is found.

34
New cards

DEFUNCT Sentinel

A marker placed in an open addressing hash table slot upon deletion, ensuring that subsequent search probes continue traversing rather than halting prematurely as they would at an empty slot.

35
New cards

Cuckoo Hashing

An open addressing scheme employing two tables and two hash functions where each key has exactly two permitted locations, achieving worst-case O(1)O(1) search and removal by evicting existing occupants upon collision.

<p>An open addressing scheme employing two tables and two hash functions where each key has exactly two permitted locations, achieving worst-case $$O(1)$$ search and removal by evicting existing occupants upon collision.</p>
36
New cards

Set ADT vs. MultiSet (Bag)

A Set ADT stores an unordered collection of unique elements without duplicates, whereas a MultiSet (Bag) allows duplicate elements and tracks the occurrence count of each element.

37
New cards

Adjacency List Structure

A graph storage representation using O(n+m)O(n + m) space where each vertex maintains an incidence list of its connected edges, allowing traversal of incident edges in O(deg(v))O(\text{deg}(v)) time.

38
New cards
<p>Adjacency Matrix Structure</p>

Adjacency Matrix Structure

A graph storage representation using an n×nn \times n 2D array where entry A[u,v]A[u, v] stores an edge reference or null, requiring O(n2)O(n^2) space and supporting O(1)O(1) edge lookups.

39
New cards

Depth-First Search (DFS)

A graph traversal running in O(n+m)O(n + m) time that follows outgoing edges leading to unexplored vertices as deeply as possible before backtracking, categorizing edges into tree edges and back edges.

40
New cards

Breadth-First Search (BFS)

A graph traversal running in O(n+m)O(n + m) time that visits vertices in successive concentric layers of increasing path distance from a starting vertex ss, classifying non-tree edges as cross edges.

41
New cards

Cut Edge (Bridge)

An edge in a connected graph whose removal strictly increases the total number of connected components, thereby disconnecting the graph.

42
New cards

Edge Relaxation

The fundamental update step in shortest-path algorithms that adjusts the tentative distance to vertex zz via edge e=(u,z)e = (u, z) using the rule D[z]←min⁡{D[z],D[u]+w(u,z)}D[z] \leftarrow \min\{D[z], D[u] + w(u, z)\}.

43
New cards

Dijkstra’s Algorithm

A greedy algorithm that computes the shortest path from a start vertex ss to all other vertices in a graph with non-negative edge weights, running in O(mlog⁡n)O(m \log n) time using a min-heap.

44
New cards

Cut Property (MST)

The theorem establishing that for any subset of vertices SS, the minimum-cost edge with exactly one endpoint in SS and one in V∖SV \setminus S belongs to every minimum spanning tree of the graph.

45
New cards

Cycle Property (MST)

The theorem establishing that for any cycle CC in a graph, the edge with the strictly maximum cost in CC cannot belong to any minimum spanning tree.

46
New cards

Prim's Algorithm

A greedy minimum spanning tree algorithm that grows a single tree by iteratively attaching the minimum-weight edge connecting a vertex in the visited set to a vertex outside it, running in O(mlog⁡n)O(m \log n) time with a binary heap.

47
New cards

Kruskal's Algorithm

A minimum spanning tree algorithm that considers all edges in non-decreasing order of cost, inserting each edge into the spanning forest if and only if it does not form a cycle, using a Union-Find data structure.

48
New cards

Union-Find ADT

A data structure maintaining an evolving partition of elements into disjoint sets, supporting operations make_sets(A), find(u) (returning the set identifier for uu), and union(u, v) (merging the sets of uu and vv).

49
New cards

Fractional Knapsack Problem

A resource allocation problem where arbitrary fractions 0≤xi≤wi0 \le x_i \le w_i of items can be packed to maximize total benefit within weight capacity WW, solved optimally by greedily picking items with the largest benefit-to-weight ratio biwi\frac{b_i}{w_i}.

50
New cards

Interval Partitioning Problem

A task scheduling problem aiming to find the minimum number of classrooms required to schedule nn lectures without overlaps, solved optimally in O(nlog⁡n)O(n \log n) time by greedily assigning lectures ordered by increasing start time.

51
New cards

Prefix Code

A binary character code where no codeword is a prefix of any other codeword, allowing unambiguous decoding and direct representation as leaf nodes of an encoding tree.

52
New cards

Huffman’s Algorithm

A greedy bottom-up algorithm running in O(n+dlog⁡d)O(n + d \log d) time that builds an optimal prefix code tree by repeatedly extracting and merging the two trees with the lowest frequencies using a priority queue.

53
New cards

Merge-Sort

A divide-and-conquer sorting algorithm that splits an array of size nn into two halves, recursively sorts each half, and merges them in O(n)O(n) time, resulting in an overall time complexity of O(nlog⁡n)O(n \log n).

54
New cards

Comparison Sorting Lower Bound

The information-theoretic limit proving that any comparison-based sorting algorithm requires at least Ω(nlog⁡n)\Omega(n \log n) comparisons in the worst case, derived from the log⁡2(n!)\log_2(n!) height of a decision tree with n!n! leaves.

55
New cards

Maxima-Set (Pareto Frontier)

The set of points in a 2D plane that are not dominated by any other point, where point qq dominates pp if q.x≥p.xq.x \ge p.x and q.y≥p.yq.y \ge p.y (with q≠pq \ne p); computed via divide-and-conquer in O(nlog⁡n)O(n \log n) time.

56
New cards

Karatsuba Integer Multiplication

A divide-and-conquer algorithm that multiplies two nn-bit integers using only 3 recursive multiplications of size n/2n/2 instead of 4, achieving a recurrence of T(n)=3T(n/2)+O(n)T(n) = 3T(n/2) + O(n) and a running time of O(nlog⁡23)≈O(n1.585)O(n^{\log_2 3}) \approx O(n^{1.585}).

57
New cards

Median-of-Medians Selection

A deterministic divide-and-conquer algorithm that finds the kthk^{\text{th}} smallest element in an unsorted array in O(n)O(n) worst-case time by partitioning elements into groups of 5 and recursively choosing the median of their medians as a balanced pivot.

58
New cards

Fisher-Yates Shuffle

An unbiased randomized algorithm that permutes an array of nn elements uniformly at random in O(n)O(n) time by iterating through index ii from 00 to n−1n - 1 and swapping A[i]A[i] with a randomly chosen element from index range {i,…,n−1}\{i, \dots, n - 1\}.

59
New cards
<p>Skip List Node</p>

Skip List Node

A structural node in a skip list maintaining four directional references: before(p) and after(p) on the same horizontal level, and above(p) and below(p) within the same vertical tower.

60
New cards

Skip List

A randomized layered linked-list data structure implementing the Map ADT where towers grow based on independent coin flips, providing O(log⁡n)O(\log n) expected time for search, insertion, and deletion using O(n)O(n) expected space.

61
New cards

Discrete Logarithm Problem

The cryptographic hard problem of recovering the integer exponent xx given a cyclic group generator gg, prime pp, and value Y=gx mod pY = g^x \bmod p, forming the security foundation of Diffie-Hellman key exchange.