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.

Google Online Preview   Download