FIT2004
Algorithms and
Data Structures
The original version of the course notes were developed by Daniel Anderson. Over the
course of the years, additions, removals and modifications were done by members of
FIT2004’
...
FIT2004
Algorithms and
Data Structures
The original version of the course notes were developed by Daniel Anderson. Over the
course of the years, additions, removals and modifications were done by members of
FIT2004’s teaching teams including: Nathan Companez, Rafael Dowsley.
a b c
d e
f g
5 8
2
1
4
16
4
8
9
10
d
a
f
b
e
c
s
0
2
4
6 9
7
5
7 10
3
2
1
8
5
4 7
6
9
Last updated February 16, 2023
Contents
1 Analysis of Algorithms 1
1.1 Program Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Arguing Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Arguing Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Common Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Measures of Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Analysis of Basic Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.3 Algorithms’ Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Divide and Conquer 15
2.1 Karatsuba’s Multiplication Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Merge Sort (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Counting Inversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Fast Sorting Algorithms 23
3.1 Heapsort (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Complexity Lower Bounds for Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Sorting Integers Fast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Order Statistics and Selection 41
4.1 Order Statistics and the Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 The Quickselect Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Randomised Pivot Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Median of Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Graphs Basics 49
5.1 Modelling with Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Representation and Storage of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 Graph Traversal and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3.2 Finding Connected Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3.3 Cycle Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.3.4 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.4.1 Properties of Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4.2 Shortest Path Problem Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4.3 Unweighted Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 The Topological Sorting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5.1 Kahn’s Algorithm for Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.5.2 Topological Sorting Using DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.6 Incremental Graph Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.6.1 The Union-Find Disjoint-Set Data Structure . . . . . . . . . . . . . . . . . . . . . . 68
6 Greedy Algorithms 73
6.1 Shortest Path in Graphs with Non-negative Weights . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.1 Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7 Dynamic Programming 83
7.1 The Key Elements of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.2 Top-down vs. Bottom-up Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . 87
7.3 Reconstructing Optimal Solutions to Optimisation Problems . . . . . . . . . . . . . . . 89
7.4 The Unbounded Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.5 The 0-1 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.6 The Edit Distance Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.7 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.8 The Space-Saving Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8 Dynamic Programming Graph Algorithms 101
8.1 Shortest Paths with Negative Weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.2 The All-Pairs Shortest Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.2.1 The Floyd-Warshall algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.3 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.4 The Critical Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9 Network Flow 111
9.1 The Ford-Fulkerson Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.1.1 The Residual Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
9.1.2 Augmenting Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.1.3 Implementation Using Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . 116
9.2 The Minimum Cut Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.2.1 The Min-cut Max-flow Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.4 Circulations with Demands and Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 123
10 Hashing and Hashtables 131
10.1 Hashtables (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
10.2 What is a Good Hash Function? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
10.3 Hashing Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.4 Hashing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.5 Universal Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
10.6 Cuckoo Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
11 Balanced Binary Search Trees 141
11.1 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
11.1.2 Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
12 Prefix Tries and Suffix Trees 147
12.1 The Prefix Trie / Retrieval Tree Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 147
12.1.1 Applications of Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
12.2 Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
12.2.1 Building a Suffix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
12.2.2 Applications of Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
13 Suffix Arrays 155
[Show More]
.png)
