First-year courses · Computing

Data structures and algorithms

Data structures and algorithms flashcards: Big O, arrays, lists, stacks, queues, hash tables, trees, heaps, sorting, searching and graph algorithms.

40 cards6 topicsAbout 15 minutes a roundTypical first- or second-year data structures and algorithms course

Print cards to cut out (PDF)Print a study list (PDF)

About this deck

This deck is for computer science and software engineering students in a data structures and algorithms course, typically the course right after introductory programming. It covers asymptotic notation and how to compare growth rates, the core linear structures (arrays, linked lists, stacks, queues and hash tables), trees, binary search trees and heaps, the standard sorting and searching algorithms, breadth-first and depth-first search, Dijkstra's algorithm and topological sorting, and the main design strategies: recursion, divide and conquer, greedy choices and dynamic programming.

You should be able to write loops, functions and recursion in at least one language and follow simple proofs. Logarithms base 2 come up constantly, so recall that log2(1024) = 10.

For every structure, learn three things together: how it is laid out in memory, the cost of its main operations, and one situation where it is the right choice. For every algorithm, trace it by hand on a small input (five to eight items) before memorizing its complexity; the trace is what you will need on a written exam. Explaining a card aloud as if teaching a classmate is an effective check.

Common mistakes: quoting average-case costs as if they were guaranteed (quicksort and hash tables both have bad worst cases); forgetting that binary search only works on sorted data; and dropping the base case of a recursive function, which leads to infinite recursion.

Before you start: An introductory programming course, including loops, functions, arrays and recursion, plus Grade 12 algebra with logarithms.

All 40 cards

Cover the definitions with a sheet of paper and test yourself, or use the study modes above.

Complexity

Big O notation: f(n) is O(g(n)) when f(n) <= c g(n) for some constant c and all large n; it gives an asymptotic upper bound.Example: 3n^2 + 5n + 2 is O(n^2), since it is at most 4n^2 once n >= 6.
Big Omega notation: An asymptotic lower bound: f(n) >= c g(n) for some positive constant c and all large n.Example: Any algorithm that must read all n inputs takes Omega(n) time.
Big Theta notation: A tight bound: the function is both O(g(n)) and Omega(g(n)), so it grows at the same rate as g up to constants.Example: Summing an array of n numbers is Theta(n).
Common growth rates: From slowest to fastest growing: 1, log n, n, n log n, n^2, n^3, 2^n, n!.Example: For n = 1,000,000, log2 n is about 20 while n^2 is 10^12.
Space complexity: The extra memory an algorithm needs as a function of input size, not counting the input itself.Example: Merge sort on an array uses Theta(n) extra space; in-place heap sort uses O(1).
Worst, best and average case: Running time can depend on the particular input; worst case is the maximum over inputs of size n, average case the expected value under an input model.Example: Linear search: best case 1 comparison, worst case n, average about n/2 if the target is present.
Amortized cost: The average cost per operation over a worst-case sequence of operations, which can be small even when a single operation is occasionally expensive.Example: Appending to a doubling dynamic array: copies total under 2n for n appends, so each costs O(1) amortized.

Linear structures and hashing

Array: A fixed-size block of contiguous memory; any element is reached by index in O(1), but inserting in the middle shifts elements, O(n).Example: Element i of an int array starting at address A sits at A + 4i (4-byte ints).
Dynamic array: A resizable sequence that grows by allocating a larger block (often double) and copying when full.Example: Python lists and Java ArrayList work this way.
Singly linked list: A chain of nodes, each holding a value and a pointer to the next; insertion after a known node is O(1), access by position is O(n).Example: Inserting at the head just points the new node to the old head.
Doubly linked list: A list whose nodes link both forward and backward, allowing O(1) removal of a known node and traversal in either direction.Example: Commonly used inside an LRU cache together with a hash map.
Stack: A last-in, first-out (LIFO) collection supporting push, pop and peek in O(1).Example: Push 1, 2, 3 then pop: 3 comes out first. Call stacks and undo features use this.
Queue: A first-in, first-out (FIFO) collection: enqueue at the back, dequeue at the front, both O(1) with a linked list or circular array.Example: Enqueue A, B, C then dequeue: A comes out first.
Hash table: Stores key-value pairs in an array indexed by a hash of the key, giving O(1) average insert, lookup and delete.Example: With 10 buckets and h(k) = k mod 10, key 47 goes to bucket 7.
Collision resolution: Handling two keys that hash to the same slot, by chaining (a list per bucket) or open addressing (probing for another empty slot).Example: With h(k) = k mod 10, keys 47 and 17 collide; linear probing puts 17 in bucket 8.
Load factor: The ratio n/m of stored keys to buckets; tables are resized when it passes a threshold to keep operations fast.Example: 75 keys in 100 buckets gives 0.75, a common resize trigger.

Trees and heaps

Binary search tree: A binary tree where every key in a node's left subtree is smaller and every key in its right subtree is larger.Example: Insert 50, 30, 70, 20, 40: 30 is the left child of 50, and 40 is the right child of 30.
Tree traversals: Preorder visits node, left, right; inorder visits left, node, right; postorder visits left, right, node. Inorder on a BST gives sorted order.Example: For root 2 with children 1 and 3: preorder 2 1 3, inorder 1 2 3, postorder 1 3 2.
Tree height: The number of edges on the longest path from the root down to a leaf; search costs in a BST are proportional to it.Example: A balanced tree of 1,000,000 keys has height about 20; inserting sorted keys into a plain BST gives height n - 1.
Self-balancing search tree: A BST that restructures itself (by rotations) after updates to keep height O(log n), such as AVL and red-black trees.Example: An AVL tree keeps the two subtree heights of every node within 1 of each other.
Binary heap: A complete binary tree stored in an array in which each parent is no greater (min-heap) than its children; insert and remove-min cost O(log n).Example: In a 0-indexed array, node i has children 2i + 1 and 2i + 2 and parent floor((i - 1)/2).
Priority queue: An abstract type that always removes the element with highest priority; usually implemented with a binary heap.Example: An emergency room triage list or the frontier in Dijkstra's algorithm.
Trie: A tree for strings where each edge is a character and each path from the root spells a prefix; lookup time depends on word length, not the number of words.Example: Autocomplete for 'ca' walks c then a and lists every word below that node.

Sorting and searching

Binary search: Searches sorted data by comparing with the middle element and discarding half each step; O(log n).Example: Searching 1,000,000 sorted items needs at most 20 comparisons, since 2^20 > 10^6.
Merge sort: Divide the list in half, sort each half recursively, then merge the sorted halves; Theta(n log n) in all cases and stable.Example: [5, 2, 4, 1] splits to [5, 2] and [4, 1], sorts to [2, 5] and [1, 4], merges to [1, 2, 4, 5].
Quicksort: Pick a pivot, partition into smaller and larger elements, then sort each side recursively; average O(n log n), worst O(n^2).Example: Always choosing the first element as pivot on already sorted input gives the worst case.
Insertion sort: Builds a sorted prefix by inserting each new element into its place; O(n^2) worst case but close to O(n) on nearly sorted data.Example: Inserting 3 into sorted [1, 4, 6] shifts 4 and 6 right to give [1, 3, 4, 6].
Heap sort: Build a max-heap, then repeatedly swap the root to the end and restore the heap; O(n log n) worst case, in place, not stable.Example: Building the heap takes O(n); the n removals take O(log n) each.
Stable sorting: A sort is stable if records with equal keys keep their original relative order.Example: Sorting students by grade with a stable sort keeps them alphabetical within each grade if they started that way.
Comparison sorting lower bound: Any sort that learns about order only through comparisons needs Omega(n log n) comparisons in the worst case.Example: Counting sort can beat it on small integer keys because it does not compare elements.

Graph algorithms

Adjacency list versus adjacency matrix: A list stores each vertex's neighbours using O(V + E) space; a matrix uses a V by V grid, O(V^2) space, but answers 'is there an edge?' in O(1).Example: A sparse road network with 10,000 towns and 30,000 roads suits a list: 100,000,000 matrix cells would be mostly empty.
Breadth-first search: Explores a graph level by level using a queue; on unweighted graphs it finds shortest paths in edges. O(V + E).Example: From A with edges A-B, A-C, B-D: visit order A, B, C, D.
Depth-first search: Explores as far as possible along each branch before backtracking, using a stack or recursion; O(V + E). Used for cycle detection and topological sort.Example: From A with edges A-B, A-C, B-D: one order is A, B, D, C.
Dijkstra's algorithm: Finds shortest paths from one source in a graph with non-negative edge weights by repeatedly settling the closest unsettled vertex.Example: A-B 4, A-C 1, C-B 2: B's distance improves from 4 to 1 + 2 = 3.
Topological sort: A linear order of the vertices of a directed acyclic graph such that every edge goes from earlier to later.Example: Courses with prerequisites: Calc I before Calc II before Differential Equations.

Design techniques

Recursion: A function that solves a problem by calling itself on smaller inputs, with a base case that stops the calls.Example: factorial(n) = n x factorial(n - 1), with factorial(0) = 1; factorial(5) = 120.
Divide and conquer: Split a problem into independent subproblems, solve them recursively, and combine their answers.Example: Merge sort and binary search both follow this pattern.
Master theorem: Gives the solution of T(n) = a T(n/b) + f(n) by comparing f(n) with n^(log_b a).Example: T(n) = 2T(n/2) + n: n^(log_2 2) = n matches f(n), so T(n) = Theta(n log n).
Dynamic programming: Solves overlapping subproblems once each and stores the answers (memoization or a table), turning exponential recursion into polynomial time.Example: Naive recursive Fibonacci makes an exponential number of calls (roughly 1.6^n); storing results computes fib(40) = 102,334,155 in 40 steps.
Greedy algorithm: Builds a solution by always taking the choice that looks best right now; correct only when the problem has the greedy-choice property.Example: Coins 25, 10, 5, 1 make 30 cents as 25 + 5. With coins 1, 3, 4, the best-looking first pick makes 6 as 4 + 1 + 1, but 3 + 3 is better.