-
Overview Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to how their run time or space requirements grow as the input size ($n$) grows. Core Concepts Time…
-
Overview Backtracking is a general algorithmic technique for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems. It incrementally builds candidates for solutions and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. Core Concepts State-Space Search: Exploring all possible…
-
Overview A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree-based data structure used to store a dynamic set of strings. Unlike a binary search tree, no node in the trie stores the key associated with that node; instead, its position in the tree defines the key it is associated…
-
Overview A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last element added to the stack is the first one to be removed. Think of it like a stack of physical plates. Core Concepts Push: Adding an element to the top of the stack. Pop: Removing the top element…
-
Overview A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The first element added to the queue is the first one to be removed. Think of it like a line of people waiting for a bus. Core Concepts Enqueue: Adding an element to the end (rear) of the queue. Dequeue:…
-
Overview A Linked List is a linear collection of data elements called nodes, where each node contains a data field and a reference (link) to the next node in the sequence. Unlike arrays, linked lists are not stored in contiguous memory locations. Core Concepts Node: The basic building block. Contains data and a next pointer.…
-
Overview A Heap is a specialized tree-based data structure that satisfies the heap property. It is most commonly implemented as a binary heap, which is a complete binary tree. Heaps are primarily used to implement priority queues and the heapsort algorithm. Core Concepts Heap Property: Max-Heap: The value of the root node must be the…
-
Overview A Hash Table (or Hash Map/Dictionary) is a data structure that maps keys to values using a hash function. It allows for extremely fast data retrieval by converting a key into an index in an underlying array. Core Concepts Hash Function: An algorithm that takes an input (key) and returns a fixed-size integer (hash),…
-
Overview A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs are used to represent networks of interconnected objects. Core Concepts Directed vs. Undirected: Directed (Digraph): Edges have a direction (e.g., a Twitter follow). Undirected: Edges have no…
-
Overview A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. Core Concepts Root: The topmost node of…