Introduction
>>
Data Structures and Algorithms
Peter Ljunglöf
Alex Gerdes
Jonas Duregård
(editors)
2016–2026
1
Introduction
1.1
Motivation and core concepts
1.2
Practical examples
1.3
Case study: Linear and binary search in arrays
1.4
The right data structure for the problem
1.5
Abstract data types
1.6*
Review
1.6.1
Quiz: Data structures and algorithms
2
Sorting, part 1
2.1
Terminology and notation
2.1.1
Comparing algorithms
2.1.2
Terminology
2.2
Comparing values
2.2.1
Two main approaches to comparing values
2.2.2
Natural vs key-based comparison
2.3
Overview of algorithms
2.3.1
In-place sorting
2.4
Bubble sort
2.4.1
Analysis of Bubble sort
2.5
Selection sort
2.5.1
Selection sort analysis
2.6
Insertion sort
2.6.1
Insertion sort analysis
2.7*
Empirical analysis and code tuning
2.7.1
Empirical comparison
2.7.2
Optimising Bubble sort
2.7.3
Optimising Selection sort
2.7.4
Optimising Insertion sort
2.8*
Review
2.8.1
Quiz: Sorting terminology
2.8.2
Quiz: Bubble sort
2.8.3
Quiz: Selection sort
2.8.4
Quiz: Insertion sort
2.8.5
Quiz: Exchange sort
3
Algorithm analysis, part 1
3.1
Problems, algorithms, and programs
3.2
Invariants, preconditions, and postconditions
3.3
Comparing algorithm performance
3.4
Order of growth and time functions
3.5
Best, worst, and average cases
3.6
Asymptotic analysis in practice
3.7*
Examples of algorithm analysis
3.8*
Empirical analysis and code tuning
3.8.1
Comparative timing
3.8.2
Simulation
3.8.3
Code tuning
3.9*
Review
3.9.1
Quiz: Introduction to algorithm analysis
3.9.2
Quiz: Growth rates
3.9.3
Quiz: Running time
4
Sorting, part 2
4.1
Recursion
4.1.1
Divide and conquer
4.2
Mergesort
4.2.1
Merging
4.2.2
Categorising Mergesort
4.2.3
Complexity analysis
4.2.4
Implementing Mergesort
4.2.5
Optimisations
4.2.6
Bottom-up Mergesort
4.3
Quicksort
4.3.1
Partitioning
4.3.2
Categorising Quicksort
4.3.3
Implementing Quicksort
4.3.4
Selecting a pivot
4.3.5
Complexity analysis
4.3.6
Variants and optimisations
4.4
Summary of sorting algorithms
4.4.1
Stability, adaptivity and in-place
4.4.2
Time complexity
4.5*
Empirical comparison of sorting algorithms
4.6*
Review
4.6.1
Quiz: Mergesort
4.6.2
Quiz: Quicksort
4.6.3
Quiz: Comparison of sorting algorithms
5
Algorithm analysis, part 2
5.1
Upper bounds: the big-
O
notation
5.1.1
Big-
O
and logarithms
5.1.2
The complexity hierarchy
5.1.3
Simplifying rules
5.1.4
Recursive functions
5.1.5
Advanced algorithm analysis
5.2
Lower bounds and tight bounds
5.2.1
Tight bounds: the
\Theta
notation
5.2.2
Strict bounds
5.2.3
Summary of asymptotic notations
5.2.4
Asymptotic equivalence
5.2.5
Classifying functions using limits
5.3
Analysing problems
5.3.1
Case study: Inversions and quadratic sorting algorithms
5.4
Common misunderstandings
5.4.1
Best-case upper bound, or worst-case lower bound?
5.5*
Case study: Lower bounds for sorting
5.6*
Review
5.6.1
Quiz: Big-
O
notation
5.6.2
Quiz: Asymptotic notations
5.6.3
Quiz: Analysing problems
5.6.4
Quiz: Common misunderstandings
6
Sequences
6.1
Stacks and queues
6.2
Linked lists
6.2.1
Stacks as linked lists
6.2.2
Queues as linked lists
6.3
Array-based sequences
6.3.1
Array-based stacks
6.3.2
Array-based queues
6.4
Dynamic arrays
6.4.1
Resizing the internal array
6.4.2
Doubling the size
6.4.3
Multiplying by any factor
6.4.4
Resizing an array-based queue
6.4.5
Shrinking the internal array
6.5
Analysing linked lists and dynamic arrays
6.5.1
Time complexity
6.5.2
Memory usage
6.5.3
Queues as pairs of stacks
6.6
Other kinds of sequences
6.7*
Sorting a linked list with Mergesort
6.8*
Other kinds of sequences
6.8.1
Priority queues
6.8.2
Double-ended queues
6.8.3
General lists
6.8.4
Implementing general lists using linked lists
6.8.5
Implementing general lists using arrays
6.8.6
When to use linked lists?
6.8.7
How are lists implemented in the standard libraries?
6.9*
Implementing recursion using stacks
6.10*
Review
6.10.1
Quiz: Stacks and queues
6.10.2
Quiz: Linked lists
6.10.3
Quiz: Static array-based lists
6.10.4
Quiz: Summary questions about sequences
7
Algorithm analysis, part 3
7.1
Amortised analysis
7.1.1
The accounting method
7.1.2
The potential method
7.1.3
When not to use amortisation
7.1.4
Different types of average analysis
7.2
Case study: Analysing dynamic arrays
7.2.1
Doubling the array size
7.2.2
Resizing by any constant factor
7.3
Recurrence relations
7.3.1
Expanding recurrences
7.3.2
The Master theorem
7.3.3
Case study: Karatsuba multiplication
7.4
Multiple parameters
7.5*
Space complexity
7.5.1
Space complexity of data structures
7.5.2
Space complexity of algorithms
7.5.3
Space/time tradeoff
7.6*
Deriving the Master theorem
7.7*
Case study: Average-case analysis of Quicksort
8
Abstract data types
8.1
Collections and sequences
8.1.1
Stacks and queues as abstract data types
8.1.2
Double-ended queues and general lists
8.2
Priority queues
8.2.1
Implementing priority queues using sorted lists
8.3
Sets and maps
8.3.1
Sets
8.3.2
Maps, or dictionaries
8.3.3
Multimaps
8.3.4
Implementing sets and maps using linked lists
8.4
Sorted sets and maps
8.4.1
Sorted sets
8.4.2
Sorted maps
8.4.3
Implementing sorted sets and maps using dynamic arrays
8.5
Analysing the naive implementations
8.5.1
Priority queues
8.5.2
Sets and maps
8.5.3
Sorted sets and maps
8.5.4
Summary
8.6*
Comparison with the Java API
9
Trees and heaps
9.1
Binary trees
9.1.1
Full, perfect, and complete binary trees
9.1.2
Implementing binary trees
9.1.3
Traversing trees
9.1.4
Traversal without recursion
9.2
Tree representations
9.2.1
Modelling different kinds of tree nodes
9.2.2
General trees
9.2.3
Traversing a general tree
9.3
Case study: Disjoint sets
9.4
Heaps for priority queues
9.5
Binary heaps
9.5.1
Representing complete binary trees as arrays
9.5.2
Using dynamic arrays
9.5.3
Implementing binary heaps
9.5.4
Inserting into a heap
9.5.5
Removing from a heap
9.5.6
Changing the priority of elements
9.6
Meldable heaps
9.7*
Space requirements
9.8*
Implementing tree traversal
9.8.1
More about implementing tree traversals
9.9*
Iteration, recursion, and information flow
9.10*
Implementing general trees
9.11*
Case study: Disjoint sets in depth
9.11.1
Parent pointer trees
9.11.2
Equivalence classes
9.11.3
Weighted union
9.11.4
Path compression
9.12*
Case study: Building a heap
9.13*
Case study: In-place heapsort
9.13.1
Analysis of in-place Heapsort
9.14*
Case study: Huffman coding
9.14.1
Huffman coding trees
9.14.2
Building Huffman trees
9.14.3
Assigning and using Huffman codes
9.14.4
Decoding
9.14.5
How efficient is Huffman coding?
9.14.6
Proof of optimality for Huffman coding
9.15*
Review
9.15.1
Quiz: Binary trees
9.15.2
Quiz: Example binary tree
9.15.3
Quiz: Binary tree traversals
9.15.4
Quiz: Binary heaps
9.15.5
Quiz: Heapsort
10
Search trees
10.1
Binary search trees
10.1.1
Implementing BST sets and maps
10.1.2
Searching in and adding to a BST
10.1.3
Deleting from a BST
10.1.4
Complexity analysis
10.1.5
Guided information flow
10.2
Self-balancing trees
10.2.1
Tree rotations
10.3
AVL trees
10.3.1
Implementing AVL nodes
10.3.2
Inserting into an AVL tree
10.3.3
Implementing insertion
10.3.4
Deleting a node
10.3.5
Complexity analysis
10.3.6
Yet another sorting algorithm
10.4
2-3 trees and B-trees
10.4.1
Searching in a 2-3 tree
10.4.2
Inserting into a 2-3 tree
10.4.3
Deleting from a 2-3 tree
10.4.4
Complexity analysis
10.4.5
Red-black trees and 2-3-4 trees
10.4.6
B-trees
10.4.7
File systems and databases
10.4.8
B+ trees
10.5*
B+ trees in more detail
10.5.1
Analysis of B+ trees
10.6*
Splay trees
10.6.1
Splaying
10.6.2
Searching in a splay tree
10.7*
Skip lists
10.8*
Review
10.8.1
Quiz: Binary search trees
11
Hash tables
11.1
Hash table overview
11.1.1
Maps where keys are small integers
11.1.2
Maps where keys are arbitrary integers
11.1.3
Maps where keys are objects
11.2
Separate chaining
11.3
Open addressing and linear probing
11.4
Resizing hash tables
11.5
Deleting entries from open addressing hash tables
11.5.1
Shrinking tables
11.6
Quality of hash functions
11.6.1
A good hash function for strings
11.7
Complexity of hash table operations
11.8
Implementation of open addressing
11.8.1
Resizing the internal array
11.8.2
Lazy deletion
11.9*
Different probing strategies
11.9.1
Linear probing by steps
11.9.2
Pseudo-random probing
11.9.3
Quadratic probing
11.9.4
Double hashing
11.10*
Better hash functions
11.10.1
Binning
11.10.2
The mid-square method
11.10.3
A simple hash function for strings
11.10.4
Improved string folding
11.11*
Hash tables in standard libraries
11.12*
Bucket hashing
11.12.1
An alternative approach to bucket hashing
11.13*
Review
11.13.1
Quiz: Hash functions
11.13.2
Quiz: Hash tables
12
Graphs
12.1
Definitions and properties
12.1.1
Programming graph algorithms
12.2
Traversing graphs: DFS and BFS
12.2.1
Depth-first traversal
12.2.2
Breadth-first traversal
12.3
Shortest-path problems and Dijkstra’s algorithm
12.3.1
Dijkstra’s shortest-path algorithm
12.3.2
Extracting the shortest-path tree
12.3.3
Optimising Dijkstra’s algorithm
12.4
Minimum spanning trees and Prim’s algorithm
12.4.1
Prim’s MST algorithm
12.5
Kruskal’s MST algorithm
12.6
Complexity analysis
12.7
Graph representation and implementation
12.8*
Implementing graphs
12.8.1
Adjacency matrix
12.8.2
Adjacency list
12.9*
Topological sort for directed acyclic graphs
12.9.1
Depth-first algorithm
12.9.2
Queue-based algorithm
12.10*
Floyd’s algorithm: All-pairs shortest paths
12.11*
Review
12.11.1
Quiz: Graph terminology
12.11.2
Quiz: Space requirements for graphs
12.11.3
Quiz: Graph summary questions
13*
Appendices
13.1*
Mathematical preliminaries
13.1.1
Sets
13.1.2
Relations
13.1.3
Miscellaneous notations
13.1.4
Logarithms
13.1.5
Summations
13.1.6
Mathematical proof techniques
13.1.7
Estimation
13.1.8
Random numbers
13.2*
Programming preliminaries
13.2.1
Pseudocode
13.2.2
Data types
13.2.3
Mutable and immutable data
13.2.4
Functions
13.2.5
Interfaces
13.2.6
Compound data types
13.2.7
Computer memory
13.3*
Glossary
13.4*
Bibliography