Lecture Notes for
g g
Data Structures and Algorithms
g g g
Revisedg eachg yearg byg Johng Bullinaria
SchoolgofgComputergSciencegUniversit
ygofgBirminghamgBirmingham,gUK
Versiong ofg 27g Marchg 2019
,ThesegnotesgaregcurrentlygrevisedgeachgyeargbygJohngBullinaria.g Theygincludegsectionsgbasedgong
notesgoriginallygwrittengbygMart´ıngEscardó gandgrevisedgbygManfredgKerber.g Allgaregmembersgo
fg theg Schoolg ofg Computerg Science,g Universityg ofg Birmingham,g UK.
⃝cg Schoolg ofg Computerg Science,g Universityg ofg Birmingham,g UK,g 2018
1
,Contents
1 Introduction 5
1.1 Algorithmsg asg opposedg tog programs ..................................................................................5
1.2 Fundamentalg questionsg aboutg algorithms..........................................................................6
1.3 Datag structures,g abstractg datag types,g designg patterns.....................................................7
1.4 Textbooksg andg web-resources .............................................................................................7
1.5 Overview................................................................................................................................8
2 Arrays,g Iteration,g Invariants 9
2.1 Arrays................................................................................................................................... 9
2.2 Loopsg andg Iteration ............................................................................................................10
2.3 Invariants .............................................................................................................................10
3 Lists,g Recursion,g Stacks,g Queues 12
3.1 Linkedg Lists ....................................................................................................................... 12
3.2 Recursion .............................................................................................................................15
3.3 Stacks ...................................................................................................................................16
3.4 Queues.................................................................................................................................17
3.5 Doublyg Linkedg Lists .......................................................................................................... 18
3.6 Advantageg ofg Abstractg Datag Types ..................................................................................20
4 Searching 21
4.1 Requirementsg forg searching ...............................................................................................21
4.2 Specificationg ofg theg searchg problem .................................................................................22
4.3 Agsimplegalgorithm:g LineargSearch ................................................................................ 22
4.4 Ag moreg efficientg algorithm:g Binaryg Search .....................................................................23
5 Efficiencyg andg Complexity 25
5.1 Timeg versusg spaceg complexity ...........................................................................................25
5.2 Worstg versusg averageg complexity ......................................................................................25
5.3 Concreteg measuresg forg performance .................................................................................26
5.4 Big-Og notationg forg complexityg class ................................................................................26
5.5 Formalg definitiong ofg complexityg classes...........................................................................29
6 Trees 31
6.1 Generalg specificationg ofg trees ...........................................................................................31
6.2 Quad-trees...........................................................................................................................32
6.3 Binaryg trees ........................................................................................................................33
2
, 6.4 Primitiveg operationsg ong binaryg trees...............................................................................34
6.5 Theg heightg ofg ag binaryg tree ..............................................................................................36
6.6 Theg sizeg ofg ag binaryg tree ...................................................................................................37
6.7 Implementationg ofg trees ....................................................................................................37
6.8 Recursiveg algorithms ..........................................................................................................38
7 BinarygSearchgTrees 40
7.1 Searchingg withg arraysg org lists ...........................................................................................40
7.2 Searchg keys .........................................................................................................................40
7.3 Binaryg searchg trees ............................................................................................................41
7.4 Buildingg binaryg searchg trees.............................................................................................41
7.5 Searchingg ag binaryg searchg tree .........................................................................................42
7.6 Timeg complexityg ofg insertiong andg search ........................................................................43
7.7 Deletingg nodesg fromg ag binaryg searchg tree .......................................................................44
7.8 Checkingg whetherg ag binaryg treeg isg ag binaryg searchg tree................................................46
7.9 Sortingg usingg binaryg searchg trees.....................................................................................47
7.10 Balancingg binaryg searchg trees ..........................................................................................48
7.11 Self-balancinggAVLgtrees ................................................................................................ 48
7.12 B-trees .................................................................................................................................49
8 Priorityg Queuesg andg Heapg Trees 51
8.1 Treesg storedg ing arrays ........................................................................................................51
8.2 Priorityg queuesg andg binaryg heapg trees ............................................................................52
8.3 Basicg operationsg ong binaryg heapg trees ............................................................................53
8.4 Insertingg ag newg heapg treeg node ........................................................................................54
8.5 Deletingg ag heapg treeg node.................................................................................................55
8.6 Buildingg ag newg heapg treeg fromg scratch ............................................................................56
8.7 Mergingg binaryg heapg trees................................................................................................58
8.8 Binomialg heaps...................................................................................................................59
8.9 Fibonaccig heaps .................................................................................................................61
8.10 Comparisong ofg heapg timeg complexities ............................................................................62
9 Sorting 63
9.1 Theg problemg ofg sorting ......................................................................................................63
9.2 Commong sortingg strategies ............................................................................................... 64
9.3 Howg manyg comparisonsg mustg itg take? .............................................................................64
9.4 Bubbleg Sort .........................................................................................................................66
9.5 Insertiong Sort ......................................................................................................................67
9.6 Selectiong Sort ......................................................................................................................69
9.7 Comparisong ofg O(n2)g sortingg algorithms .........................................................................70
9.8 Sortingg algorithmg stability................................................................................................. 71
9.9 Treesort ...............................................................................................................................71
9.10 Heapsort ..............................................................................................................................72
9.11 Divideg andg conquerg algorithms .........................................................................................74
9.12 Quicksort .............................................................................................................................75
9.13 Mergesort ............................................................................................................................79
9.14 Summaryg ofg comparison-basedg sortingg algorithms .........................................................81
3
g g
Data Structures and Algorithms
g g g
Revisedg eachg yearg byg Johng Bullinaria
SchoolgofgComputergSciencegUniversit
ygofgBirminghamgBirmingham,gUK
Versiong ofg 27g Marchg 2019
,ThesegnotesgaregcurrentlygrevisedgeachgyeargbygJohngBullinaria.g Theygincludegsectionsgbasedgong
notesgoriginallygwrittengbygMart´ıngEscardó gandgrevisedgbygManfredgKerber.g Allgaregmembersgo
fg theg Schoolg ofg Computerg Science,g Universityg ofg Birmingham,g UK.
⃝cg Schoolg ofg Computerg Science,g Universityg ofg Birmingham,g UK,g 2018
1
,Contents
1 Introduction 5
1.1 Algorithmsg asg opposedg tog programs ..................................................................................5
1.2 Fundamentalg questionsg aboutg algorithms..........................................................................6
1.3 Datag structures,g abstractg datag types,g designg patterns.....................................................7
1.4 Textbooksg andg web-resources .............................................................................................7
1.5 Overview................................................................................................................................8
2 Arrays,g Iteration,g Invariants 9
2.1 Arrays................................................................................................................................... 9
2.2 Loopsg andg Iteration ............................................................................................................10
2.3 Invariants .............................................................................................................................10
3 Lists,g Recursion,g Stacks,g Queues 12
3.1 Linkedg Lists ....................................................................................................................... 12
3.2 Recursion .............................................................................................................................15
3.3 Stacks ...................................................................................................................................16
3.4 Queues.................................................................................................................................17
3.5 Doublyg Linkedg Lists .......................................................................................................... 18
3.6 Advantageg ofg Abstractg Datag Types ..................................................................................20
4 Searching 21
4.1 Requirementsg forg searching ...............................................................................................21
4.2 Specificationg ofg theg searchg problem .................................................................................22
4.3 Agsimplegalgorithm:g LineargSearch ................................................................................ 22
4.4 Ag moreg efficientg algorithm:g Binaryg Search .....................................................................23
5 Efficiencyg andg Complexity 25
5.1 Timeg versusg spaceg complexity ...........................................................................................25
5.2 Worstg versusg averageg complexity ......................................................................................25
5.3 Concreteg measuresg forg performance .................................................................................26
5.4 Big-Og notationg forg complexityg class ................................................................................26
5.5 Formalg definitiong ofg complexityg classes...........................................................................29
6 Trees 31
6.1 Generalg specificationg ofg trees ...........................................................................................31
6.2 Quad-trees...........................................................................................................................32
6.3 Binaryg trees ........................................................................................................................33
2
, 6.4 Primitiveg operationsg ong binaryg trees...............................................................................34
6.5 Theg heightg ofg ag binaryg tree ..............................................................................................36
6.6 Theg sizeg ofg ag binaryg tree ...................................................................................................37
6.7 Implementationg ofg trees ....................................................................................................37
6.8 Recursiveg algorithms ..........................................................................................................38
7 BinarygSearchgTrees 40
7.1 Searchingg withg arraysg org lists ...........................................................................................40
7.2 Searchg keys .........................................................................................................................40
7.3 Binaryg searchg trees ............................................................................................................41
7.4 Buildingg binaryg searchg trees.............................................................................................41
7.5 Searchingg ag binaryg searchg tree .........................................................................................42
7.6 Timeg complexityg ofg insertiong andg search ........................................................................43
7.7 Deletingg nodesg fromg ag binaryg searchg tree .......................................................................44
7.8 Checkingg whetherg ag binaryg treeg isg ag binaryg searchg tree................................................46
7.9 Sortingg usingg binaryg searchg trees.....................................................................................47
7.10 Balancingg binaryg searchg trees ..........................................................................................48
7.11 Self-balancinggAVLgtrees ................................................................................................ 48
7.12 B-trees .................................................................................................................................49
8 Priorityg Queuesg andg Heapg Trees 51
8.1 Treesg storedg ing arrays ........................................................................................................51
8.2 Priorityg queuesg andg binaryg heapg trees ............................................................................52
8.3 Basicg operationsg ong binaryg heapg trees ............................................................................53
8.4 Insertingg ag newg heapg treeg node ........................................................................................54
8.5 Deletingg ag heapg treeg node.................................................................................................55
8.6 Buildingg ag newg heapg treeg fromg scratch ............................................................................56
8.7 Mergingg binaryg heapg trees................................................................................................58
8.8 Binomialg heaps...................................................................................................................59
8.9 Fibonaccig heaps .................................................................................................................61
8.10 Comparisong ofg heapg timeg complexities ............................................................................62
9 Sorting 63
9.1 Theg problemg ofg sorting ......................................................................................................63
9.2 Commong sortingg strategies ............................................................................................... 64
9.3 Howg manyg comparisonsg mustg itg take? .............................................................................64
9.4 Bubbleg Sort .........................................................................................................................66
9.5 Insertiong Sort ......................................................................................................................67
9.6 Selectiong Sort ......................................................................................................................69
9.7 Comparisong ofg O(n2)g sortingg algorithms .........................................................................70
9.8 Sortingg algorithmg stability................................................................................................. 71
9.9 Treesort ...............................................................................................................................71
9.10 Heapsort ..............................................................................................................................72
9.11 Divideg andg conquerg algorithms .........................................................................................74
9.12 Quicksort .............................................................................................................................75
9.13 Mergesort ............................................................................................................................79
9.14 Summaryg ofg comparison-basedg sortingg algorithms .........................................................81
3
