Data structures and algorithms

Algorithm

A sequence of unambiguous instructions for solving a problem — obtaining a required output for any legitimate input in a finite amount of time.

Finiteness (algorithm property)

An algorithm must terminate after a finite number of steps.

Definiteness (algorithm property)

Each step of an algorithm must be unambiguously specified.

Input (algorithm property)

The valid range of inputs to an algorithm must be clearly specified.

Output (algorithm property)

An algorithm can be proved to produce the correct output given a valid input.

Effectiveness (algorithm property)

Each step of an algorithm must be sufficiently simple and basic to be carried out.

Pseudocode

A way of specifying an algorithm that is compact, independent of any programming language, and easy for humans to read.

Sorting problem

Given a sequence of n numbers, produce a reordering of that sequence so each element is less than or equal to the one after it.

Stable sorting algorithm

A sorting algorithm that preserves the relative order of any two equal elements in its input.

In-place sorting algorithm

A sorting algorithm that does not require extra memory except possibly for a few memory units.

Brute force

An algorithm design strategy that solves a problem in the most straightforward way based on the problem's statement and definitions.

Decrease and conquer

An algorithm design strategy that reduces a problem instance to a smaller instance of the same problem and solves that.

Divide and conquer

An algorithm design strategy that divides a problem into several smaller subproblems, solves each, and combines the solutions.

Transform and conquer

An algorithm design strategy that transforms a problem into another, easier-to-solve problem.

Greedy approach

An algorithm design strategy that makes the locally optimal choice at each step, hoping to find a global optimum.

Dynamic programming

An algorithm design strategy that solves problems by combining solutions to overlapping subproblems, typically storing results to avoid recomputation.

Backtracking / branch and bound

Algorithm design strategies that systematically search through a space of candidate solutions, abandoning ('pruning') branches that cannot lead to a valid or optimal solution.

Array

A sequence of n items of the same data type, stored contiguously in memory and accessible by index in constant time.

Linked list

A sequence of elements called nodes, each containing data and a pointer to the next node; accessed by traversing from the header.

Doubly linked list

A linked list in which every node (except the first and last) contains pointers to both its successor and its predecessor.

Stack

A data structure with 'last in, first out' (LIFO) access, supporting push, pop, and top operations.

Queue

A data structure with 'first in, first out' (FIFO) access, supporting enqueue and dequeue operations.

Priority queue

A data structure (often implemented as a heap) that supports finding/deleting the largest element and inserting new elements.

Graph

A structure G =

Loop (graph)

An edge that connects a vertex to itself.

Complete graph

A graph in which every pair of vertices is connected by an edge, denoted K|V|.

Dense graph

A graph in which only a relatively small number of possible edges are missing.

Sparse graph

A graph with relatively few edges compared to the maximum possible.

Adjacency matrix

A |V| x |V| matrix representation of a graph where each cell indicates whether an edge exists between two vertices; symmetric for undirected graphs.

Adjacency list

A graph representation where each vertex has a list of the vertices it is connected to; efficient for sparse graphs.

Weighted graph

A graph in which a weight or cost is assigned to each edge, used in problems like shortest path and traveling salesman.

Path (graph)

A sequence of adjacent vertices starting from vertex u and ending at vertex v.

Simple path

A path in which all traversed edges and vertices are distinct.

Connected graph

A graph in which there exists a path between every pair of vertices.

Cycle

A simple path that starts and ends at the same vertex (not the same as a loop).

Acyclic graph

A graph that contains no cycles.

Tree (free tree)

A connected acyclic graph.

Forest

An unconnected acyclic graph (a collection of trees).

Rooted tree

A tree in which one vertex is designated as the root, placed at level 0, with the rest of the tree organized beneath it.

Depth of a vertex

The length of the path from the root to that vertex in a rooted tree.

Height of a tree

The length of the longest simple path from the root to a leaf.

Binary tree

A tree in which each vertex has no more than two children.

Binary search tree

A binary tree in which the value at each parent node is larger than all values in its left subtree and smaller than all values in its right subtree.

Set

An unordered collection of unique items, supporting operations like membership checking, union, and intersection.

Dictionary (data structure)

A set with the added operations of searching, adding, and deleting elements.