Lecture Notes for Data Structures and Algorithms
Lecture Notes for
Data Structures and Algorithms
Revised each year by John Bullinaria
School of Computer Science
University of Birmingham
Birmingham, UK
Version of 27 March 2019
These notes are currently revised each year by John Bullinaria. They include sections based on
notes originally written by Mart??n Escardo? and revised by Manfred Kerber. All are members
of the School of Computer Science, University of Birmingham, UK.
c School of Computer Science, University of Birmingham, UK, 2018
1
Contents
1 Introduction
1.1 Algorithms as opposed to programs . . . . .
1.2 Fundamental questions about algorithms . .
1.3 Data structures, abstract data types, design
1.4 Textbooks and web-resources . . . . . . . .
1.5 Overview . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
patterns
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
6
7
7
8
2 Arrays, Iteration, Invariants
9
2.1 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Loops and Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Lists, Recursion, Stacks, Queues
3.1 Linked Lists . . . . . . . . . . . . .
3.2 Recursion . . . . . . . . . . . . . .
3.3 Stacks . . . . . . . . . . . . . . . .
3.4 Queues . . . . . . . . . . . . . . . .
3.5 Doubly Linked Lists . . . . . . . .
3.6 Advantage of Abstract Data Types
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Searching
4.1 Requirements for searching . . . . . . . .
4.2 Specification of the search problem . . . .
4.3 A simple algorithm: Linear Search . . . .
4.4 A more efficient algorithm: Binary Search
5 Efficiency and Complexity
5.1 Time versus space complexity . . . . .
5.2 Worst versus average complexity . . .
5.3 Concrete measures for performance . .
5.4 Big-O notation for complexity class . .
5.5 Formal definition of complexity classes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12
12
15
16
17
18
20
.
.
.
.
21
21
22
22
23
.
.
.
.
.
25
25
25
26
26
29
6 Trees
31
6.1 General specification of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.2 Quad-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.3 Binary trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2
6.4
6.5
6.6
6.7
6.8
Primitive operations on binary trees
The height of a binary tree . . . . .
The size of a binary tree . . . . . . .
Implementation of trees . . . . . . .
Recursive algorithms . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Binary Search Trees
7.1 Searching with arrays or lists . . . . . . . . . . . . . .
7.2 Search keys . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Binary search trees . . . . . . . . . . . . . . . . . . . .
7.4 Building binary search trees . . . . . . . . . . . . . . .
7.5 Searching a binary search tree . . . . . . . . . . . . . .
7.6 Time complexity of insertion and search . . . . . . . .
7.7 Deleting nodes from a binary search tree . . . . . . . .
7.8 Checking whether a binary tree is a binary search tree
7.9 Sorting using binary search trees . . . . . . . . . . . .
7.10 Balancing binary search trees . . . . . . . . . . . . . .
7.11 Self-balancing AVL trees . . . . . . . . . . . . . . . . .
7.12 B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 Priority Queues and Heap Trees
8.1 Trees stored in arrays . . . . . . . . .
8.2 Priority queues and binary heap trees
8.3 Basic operations on binary heap trees
8.4 Inserting a new heap tree node . . . .
8.5 Deleting a heap tree node . . . . . . .
8.6 Building a new heap tree from scratch
8.7 Merging binary heap trees . . . . . . .
8.8 Binomial heaps . . . . . . . . . . . . .
8.9 Fibonacci heaps . . . . . . . . . . . . .
8.10 Comparison of heap time complexities
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9 Sorting
9.1 The problem of sorting . . . . . . . . . . . . . . .
9.2 Common sorting strategies . . . . . . . . . . . . .
9.3 How many comparisons must it take? . . . . . .
9.4 Bubble Sort . . . . . . . . . . . . . . . . . . . . .
9.5 Insertion Sort . . . . . . . . . . . . . . . . . . . .
9.6 Selection Sort . . . . . . . . . . . . . . . . . . . .
9.7 Comparison of O(n2 ) sorting algorithms . . . . .
9.8 Sorting algorithm stability . . . . . . . . . . . . .
9.9 Treesort . . . . . . . . . . . . . . . . . . . . . . .
9.10 Heapsort . . . . . . . . . . . . . . . . . . . . . . .
9.11 Divide and conquer algorithms . . . . . . . . . .
9.12 Quicksort . . . . . . . . . . . . . . . . . . . . . .
9.13 Mergesort . . . . . . . . . . . . . . . . . . . . . .
9.14 Summary of comparison-based sorting algorithms
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
36
37
37
38
.
.
.
.
.
.
.
.
.
.
.
.
40
40
40
41
41
42
43
44
46
47
48
48
49
.
.
.
.
.
.
.
.
.
.
51
51
52
53
54
55
56
58
59
61
62
.
.
.
.
.
.
.
.
.
.
.
.
.
.
63
63
64
64
66
67
69
70
71
71
72
74
75
79
81
9.15 Non-comparison-based sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9.16 Bin, Bucket, Radix Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
10 Hash Tables
10.1 Storing data . . . . . . . . . . . . . . . . . . . . . . .
10.2 The Table abstract data type . . . . . . . . . . . . .
10.3 Implementations of the table data structure . . . . .
10.4 Hash Tables . . . . . . . . . . . . . . . . . . . . . . .
10.5 Collision likelihoods and load factors for hash tables
10.6 A simple Hash Table in operation . . . . . . . . . . .
10.7 Strategies for dealing with collisions . . . . . . . . .
10.8 Linear Probing . . . . . . . . . . . . . . . . . . . . .
10.9 Double Hashing . . . . . . . . . . . . . . . . . . . . .
10.10Choosing good hash functions . . . . . . . . . . . . .
10.11Complexity of hash tables . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
85
85
85
87
87
88
89
90
92
94
96
96
11 Graphs
11.1 Graph terminology . . . . . . . . . . . . . . . .
11.2 Implementing graphs . . . . . . . . . . . . . . .
11.3 Relations between graphs . . . . . . . . . . . .
11.4 Planarity . . . . . . . . . . . . . . . . . . . . .
11.5 Traversals ¨C systematically visiting all vertices .
11.6 Shortest paths ¨C Dijkstra¡¯s algorithm . . . . . .
11.7 Shortest paths ¨C Floyd¡¯s algorithm . . . . . . .
11.8 Minimal spanning trees . . . . . . . . . . . . .
11.9 Travelling Salesmen and Vehicle Routing . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
98
99
100
102
103
104
105
111
113
117
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12 Epilogue
A Some Useful Formulae
A.1 Binomial formulae .
A.2 Powers and roots . .
A.3 Logarithms . . . . .
A.4 Sums . . . . . . . . .
A.5 Fibonacci numbers .
118
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
119
. 119
. 119
. 119
. 120
. 121
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 1 an introduction to codes and coding
- introduction to python for econometrics statistics and
- data structures and analysis
- using bloomberg to get the data you need
- writing fast fortran routines for python
- python for programmers
- python 3 cheat sheet limsi
- gpu programming made easy
- lecture notes for data structures and algorithms
- dictionaries and hash tables purdue university
Related searches
- strategic management lecture notes pdf
- financial management lecture notes pdf
- business management lecture notes pdf
- organic chemistry lecture notes pdf
- corporate finance lecture notes pdf
- philosophy of education lecture notes slideshare
- business administration lecture notes pdf
- advanced microeconomics lecture notes pdf
- microeconomics lecture notes pdf
- marketing lecture notes pdf
- lecture notes in microeconomic theory
- mathematical logic lecture notes pdf