Introduction
>>
Data Structures and Algorithms
Peter Ljunglöf
Alex Gerdes
(editors)
2016–2025
1
Introduction
1.1
Motivation
1.2
Selecting a data structure
1.3
Practical examples
1.4
Mathematical preliminaries
1.5
Programming preliminaries
1.6
Case study: Searching in a list
1.6.1
Binary search
1.7
Abstract data types
1.7.1
Linear collections
1.7.2
Sets and maps
1.7.3
Graphs
1.8
Review questions
2
Algorithm analysis, part 1: Introduction
2.1
Problems, algorithms, and programs
2.1.1
Problems
2.1.2
Algorithms
2.1.3
Programs
2.2
Invariants, preconditions, and postconditions
2.3
Comparing algorithms
2.3.1
Basic operations and input size
2.4
Growth rates
2.4.1
Getting a faster computer
2.4.2
Comparing different growth rates
2.5
Best, worst, and average cases
2.5.1
The problem with average case
2.6
Asymptotic analysis
2.6.1
Orders of growth
2.6.2
Should we use
O
O
,
Ω
\Omega
or
Θ
\Theta
?
2.7
Algorithm analysis in practice
2.7.1
Simplification rules
2.7.2
The complexity hierarchy
2.7.3
Analysing code fragments
2.7.4
Examples of algorithm analysis
2.7.5
Advanced algorithm analysis
2.7.6
Other control statements
2.7.7
Recursive functions
2.8
Case study: Analysing binary search
2.8.1
Complexity of binary search
2.9
Code tuning
2.10
Empirical analysis
2.11
Review questions
2.11.1
Review questions: Introduction
2.11.2
Review questions: Growth rates
2.11.3
Review questions: Running time
3
Sorting, part 1: Simple algorithms
3.1
Terminology and notation
3.1.1
Comparing algorithms
3.1.2
Terminology
3.2
Comparing values
3.2.1
Two main approaches to comparing values
3.2.2
Natural vs key-based comparison
3.3
Overview of algorithms
3.3.1
Bubble sort overview
3.3.2
Selection sort overview
3.3.3
Insertion sort overview
3.3.4
Summary
3.4
Bubble sort
3.4.1
Bubble sort analysis
3.5
Selection sort
3.5.1
Selection sort analysis
3.6
Insertion sort
3.6.1
Insertion sort analysis
3.7
Summary analysis of basic sorting algorithms
3.7.1
Inversions and the reason for the quadratic behaviour
3.8
Empirical analysis and code tuning
3.9
Review questions
3.9.1
Review questions: Terminology
3.9.2
Review questions: Bubble sort
3.9.3
Review questions: Selection sort
3.9.4
Review questions: Insertion sort
3.9.5
Review questions: Exchange sort
4
Sorting, part 2: Divide-and-conquer algorithms
4.1
Recursion and divide-and-conquer
4.1.1
Recursion
4.1.2
Divide and conquer
4.2
Mergesort
4.2.2
Complexity analysis
4.3
Implementing Mergesort
4.4
Quicksort
4.4.1
Partition
4.4.2
Complexity analysis
4.5
Implementing Quicksort
4.5.1
Partition
4.5.2
Selecting the pivot
4.5.3
More practical improvements
4.6
Empirical comparison of sorting algorithms
4.7
Review questions
4.7.1
Review questions: Mergesort
4.7.2
Review questions: Quicksort
4.7.3
Review questions: Comparison of sorting algorithms
5
Algorithm analysis, part 2: Theory
5.1
Upper bounds: the big-
O
O
notation
5.1.1
Formal definition
5.1.2
Simplifying rules
5.1.3
big-
O
O
and logarithms
5.2
Lower bounds and tight bounds
5.3
Analysing problems
5.3.1
Case study: Lower bounds for sorting
5.4
Common misunderstandings
5.4.1
Best-case upper bound, or worst-case lower bound?
5.5
Review questions
5.5.1
Review questions: Upper bounds
5.5.2
Review questions: Asymptotic notations
5.5.3
Review questions: Analysing problems
5.5.4
Review questions: Common misunderstandings
6
Stacks, queues, and lists
6.1
Collections
6.1.1
What is a sequence?
6.2
Stacks and queues
6.2.1
Case study: Implementing recursion
6.3
Stacks implemented as linked lists
6.4
Queues implemented as linked lists
6.4.1
Case study: Sorting a linked list using Mergesort
6.5
Stacks implemented using arrays
6.6
Queues implemented using arrays
6.6.1
Circular queues
6.7
Dynamic arrays
6.7.1
Resizing the internal array
6.7.2
How much to increase the array size
6.7.3
Resizing an array-based queue
6.7.4
Shrinking the internal array
6.8
Comparison of linked lists vs dynamic arrays
6.9
Double-ended queues
6.10
General lists
6.11
Priority queues
6.11.1
ADT for priority queues
6.11.2
Use cases for priority queues
6.11.3
Implementing priority queues using sorted lists
6.12
Review questions
6.12.1
Review questions: Stacks and queues
6.12.2
Review questions: Linked lists
6.12.3
Review questions: Static array-based lists
6.12.4
Summary questions
7
Algorithm analysis, part 3: Advanced theory
7.1
Space bounds
7.1.1
Space complexity of data structures
7.1.2
Space complexity of algorithms
7.1.3
Space/time tradeoff
7.2
Amortised analysis
7.3
Case study: Analysing dynamic arrays
7.4
Recurrence relations
7.5
Multiple parameters
8
Trees
8.1
Binary trees
8.1.1
Binary trees are recursive data structures
8.2
Case study: Full binary trees
8.3
Implementing binary trees
8.3.1
Differentiating between internal nodes and leaves
8.3.2
Space requirements
8.4
Traversing a binary tree
8.4.1
Preorder, postorder and inorder
8.4.2
Implementation
8.5
Iteration, recursion, and information flow
8.6
General trees
8.6.1
Definitions and terminology
8.6.2
ADT for general trees
8.6.3
Traversing a general tree
8.6.4
Sequential tree representations
8.7
Review questions
8.7.1
Review questions: Binary tree definition
8.7.2
Review questions: Example binary tree
8.7.3
Review questions: Binary tree traversals
9
Priority queues and heaps
9.1
Implementing priority queues using binary trees
9.1.1
The heap property
9.2
Binary heaps
9.2.1
Representing complete binary trees as arrays
9.2.2
Implementing binary heaps
9.2.3
Inserting into a heap
9.2.4
Removing from the heap
9.2.5
Binary heaps as priority queues
9.2.6
Changing the priority of elements
9.2.7
Building a heap
9.3
Case study: Heapsort
9.4
Case study: Huffman coding
9.5
Review questions
9.5.1
Review questions: Binary heaps
9.5.2
Review questions: Heapsort
10
Sets and maps
10.1
Sets
10.2
Maps, or dictionaries
10.2.1
Multimaps
10.3
Case study: Implementing sets using lists
10.3.1
Implementing maps
10.4
Sorted sets and maps
10.4.1
Sorted sets
10.4.2
Sorted maps
11
Search trees
11.1
Binary search trees
11.1.1
Recursive search and insert
11.1.2
Removing from a BST
11.1.3
Analysis
11.1.4
Guided information flow
11.2
Self-balancing trees
11.3
AVL trees
11.3.1
Rotations
11.3.2
AVL tree insertion
11.4
Splay trees
11.5
Disjoint sets and the Union/Find algorithm
11.6
Skip lists
11.7
Review questions
11.7.1
Review questions: Binary search trees
12
Hash tables
12.1
Hash functions
12.1.1
Properties of a hash function
12.1.2
Basic principles of hash functions
12.2
Converting objects to table indices
12.2.1
Compressing a hash code
12.2.2
Modular compression
12.2.3
Negative hash codes
12.2.4
The hash code never changes
12.2.5
Handling collisions
12.3
Separate chaining
12.3.1
Alternatives to a linked list
12.3.2
Resizing is important
12.3.3
Implementation
12.3.4
Load factor and resizing
12.4
Implementing sets and maps using separate chaining
12.4.1
Implementing sets
12.4.2
Implementing maps
12.5
Open addressing
12.6
Implementing sets and maps using open addressing
12.6.1
Resizing
12.6.2
Implementing maps
12.7
Deletion in open addressing
12.7.1
Simple implementation of deletion
12.7.2
Two load factors
12.8
Different probing strategies
12.9
Analysis of hash tables
12.9.1
Analysis of open addressing
12.10
Better hash functions
12.10.3
A simple hash function for strings
12.10.4
Improved string folding
12.11
Bucket hashing
12.12
Hash tables in practice
12.12.1
Algorithmic complexity attacks
12.12.2
Breaking hash functions
12.12.3
How are hash tables implemented in standard libraries?
12.13
Review questions
12.13.1
Review questions: Hash functions
12.13.2
Review questions: Hash tables
13
Graphs
13.1
Definitions and properties
13.2
Graph representations
13.3
Implementing graphs
13.3.1
Adjacency matrix
13.3.2
Adjacency list
13.4
Traversing graphs
13.4.1
Depth-first search
13.4.2
Breadth-first search
13.5
Minimum spanning trees, MST
13.6
Prim’s algorithm for finding the MST
13.6.1
Priority queue implementation of Prim’s algorithm
13.6.2
Correctness of Prim’s algorithm
13.7
Kruskal’s algorithm for finding the MST
13.8
Shortest-paths problems
13.9
Dijkstra’s shortest-path algorithm
13.9.1
Using a priority queue
13.10
Specialised algorithms on weighted graphs
13.10.1
All-pairs shortest paths: Floyd’s algorithm
13.10.2
Acyclic graphs: Topological sort
13.11
Review questions
13.11.1
Review questions: Graph terminology
13.11.2
Review questions: Graph space requirements
13.11.3
Summary questions
14
Glossary
15
Bibliography