221 cards
A data structure is a particular way of organizing data in a computer so that it can be used effectively, while an algorithm is a step-by-step procedure that defines a set of instructions to be executed in a certain order to produce the desired output. Together, these two concepts form the backbone of computer science,...
A binary tree is a tree data structure in which each node has at most two children, referred to as the left and right child. A binary search tree (BST) imposes an ordering constraint: every node in the left subtree holds a value less than the parent, and every node in the right subtree holds a value greater. This order...
A hash table stores data in an associative manner, arranging values in an array format where each data value has its own unique index. Hashing is the process of converting a given key into a numeric value that is then used as that index. When two different keys hash to the same index, a collision occurs. Collisions are...
A graph is a non-linear data structure consisting of nodes, also called vertices, and edges that connect pairs of vertices. Two principal ways exist to represent a finite graph in memory: an adjacency matrix is a square matrix whose entries indicate whether pairs of vertices are adjacent, while an adjacency list is a c...
Searching is one of the most fundamental algorithmic tasks. Linear search examines every item one by one, giving a time complexity of \(O(n)\). Binary search repeatedly divides a sorted array's search interval in half, achieving a time complexity of \(O(\log n)\) but requiring sorted input. Interpolation search improve...
Several recurring paradigms underlie the design of efficient algorithms. Recursion is the process in which a function calls itself as a subroutine, while iteration uses a loop to repeat a process; recursion can be more memory intensive because of call-stack overhead. Dynamic programming is a paradigm that solves a comp...
String matching is a deep subfield with its own family of algorithms. The Knuth-Morris-Pratt algorithm searches for occurrences of a word W within a text S by exploiting the structure of the pattern itself, so that when a mismatch occurs, the word embodies enough information to determine where the next match could begi...