Contents
1 Introduction 1
1.1 What this book is, and what it isn’t . . . . . . . . . . . . . . . . 1
1.2 Assumed knowledge . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 Big Oh notation . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.2 Imperative programming language . . . . . . . . . . . . . 3
1.2.3 Object oriented concepts . . . . . . . . . . . . . . . . . . 4
1.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Tips for working through the examples . . . . . . . . . . . . . . . 6
1.5 Book outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Where can I get the code? . . . . . . . . . . . . . . . . . . . . . . 7
1.8 Final messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I Data Structures 8
2 Linked Lists 9
2.1 Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.4 Traversing the list . . . . . . . . . . . . . . . . . . . . . . 12
2.1.5 Traversing the list in reverse order . . . . . . . . . . . . . 13
2.2 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Reverse Traversal . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Binary Search Tree 19
3.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 Finding the parent of a given node . . . . . . . . . . . . . . . . . 24
3.5 Attaining a reference to a node . . . . . . . . . . . . . . . . . . . 24
3.6 Finding the smallest and largest values in the binary search tree 25
3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
I
, 3.7.2 Postorder . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7.3 Inorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.7.4 Breadth First . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Heap 32
4.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Sets 44
5.1 Unordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 Ordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Queues 48
6.1 A standard queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Double Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7 AVL Tree 54
7.1 Tree Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2 Tree Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
II Algorithms 62
8 Sorting 63
8.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
8.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
9 Numeric 72
9.1 Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.2 Base conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.3 Attaining the greatest common denominator of two numbers . . 73
9.4 Computing the maximum value for a number of a specific base
consisting of N digits . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.5 Factorial of a number . . . . . . . . . . . . . . . . . . . . . . . . 74
9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II
,10 Searching 76
10.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.2 Probability Search . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
11 Strings 79
11.1 Reversing the order of words in a sentence . . . . . . . . . . . . . 79
11.2 Detecting a palindrome . . . . . . . . . . . . . . . . . . . . . . . 80
11.3 Counting the number of words in a string . . . . . . . . . . . . . 81
11.4 Determining the number of repeated words within a string . . . . 83
11.5 Determining the first matching character between two strings . . 84
11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
A Algorithm Walkthrough 86
A.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 86
A.2 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 88
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
B Translation Walkthrough 91
B.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
C Recursive Vs. Iterative Solutions 93
C.1 Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . . 94
C.2 Some problems are recursive in nature . . . . . . . . . . . . . . . 95
C.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
D Testing 97
D.1 What constitutes a unit test? . . . . . . . . . . . . . . . . . . . . 97
D.2 When should I write my tests? . . . . . . . . . . . . . . . . . . . 98
D.3 How seriously should I view my test suite? . . . . . . . . . . . . . 99
D.4 The three A’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
D.5 The structuring of tests . . . . . . . . . . . . . . . . . . . . . . . 99
D.6 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
D.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
E Symbol Definitions 101
III
, Chapter 1
Introduction
1.1 What this book is, and what it isn’t
This book provides implementations of common and uncommon algorithms in
pseudocode which is language independent and provides for easy porting to most
imperative programming languages. It is not a definitive book on the theory of
data structures and algorithms.
For the most part this book presents implementations devised by the authors
themselves based on the concepts by which the respective algorithms are based
upon so it is more than possible that our implementations differ from those
considered the norm.
You should use this book alongside another on the same subject, but one
that contains formal proofs of the algorithms in question. In this book we use
the abstract big Oh notation to depict the run time complexity of algorithms
so that the book appeals to a larger audience.
1.2 Assumed knowledge
We have written this book with few assumptions of the reader, but some have
been necessary in order to keep the book as concise and approachable as possible.
We assume that the reader is familiar with the following:
1. Big Oh notation
2. An imperative programming language
3. Object oriented concepts
1.2.1 Big Oh notation
For run time complexity analysis we use big Oh notation extensively so it is vital
that you are familiar with the general concepts to determine which is the best
algorithm for you in certain scenarios. We have chosen to use big Oh notation
for a few reasons, the most important of which is that it provides an abstract
measurement by which we can judge the performance of algorithms without
using mathematical proofs.
1
1 Introduction 1
1.1 What this book is, and what it isn’t . . . . . . . . . . . . . . . . 1
1.2 Assumed knowledge . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 Big Oh notation . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.2 Imperative programming language . . . . . . . . . . . . . 3
1.2.3 Object oriented concepts . . . . . . . . . . . . . . . . . . 4
1.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Tips for working through the examples . . . . . . . . . . . . . . . 6
1.5 Book outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Where can I get the code? . . . . . . . . . . . . . . . . . . . . . . 7
1.8 Final messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I Data Structures 8
2 Linked Lists 9
2.1 Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.4 Traversing the list . . . . . . . . . . . . . . . . . . . . . . 12
2.1.5 Traversing the list in reverse order . . . . . . . . . . . . . 13
2.2 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Reverse Traversal . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Binary Search Tree 19
3.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 Finding the parent of a given node . . . . . . . . . . . . . . . . . 24
3.5 Attaining a reference to a node . . . . . . . . . . . . . . . . . . . 24
3.6 Finding the smallest and largest values in the binary search tree 25
3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
I
, 3.7.2 Postorder . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7.3 Inorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.7.4 Breadth First . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Heap 32
4.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Sets 44
5.1 Unordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 Ordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Queues 48
6.1 A standard queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Double Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7 AVL Tree 54
7.1 Tree Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2 Tree Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
II Algorithms 62
8 Sorting 63
8.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
8.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
9 Numeric 72
9.1 Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.2 Base conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.3 Attaining the greatest common denominator of two numbers . . 73
9.4 Computing the maximum value for a number of a specific base
consisting of N digits . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.5 Factorial of a number . . . . . . . . . . . . . . . . . . . . . . . . 74
9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II
,10 Searching 76
10.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.2 Probability Search . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
11 Strings 79
11.1 Reversing the order of words in a sentence . . . . . . . . . . . . . 79
11.2 Detecting a palindrome . . . . . . . . . . . . . . . . . . . . . . . 80
11.3 Counting the number of words in a string . . . . . . . . . . . . . 81
11.4 Determining the number of repeated words within a string . . . . 83
11.5 Determining the first matching character between two strings . . 84
11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
A Algorithm Walkthrough 86
A.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 86
A.2 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 88
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
B Translation Walkthrough 91
B.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
C Recursive Vs. Iterative Solutions 93
C.1 Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . . 94
C.2 Some problems are recursive in nature . . . . . . . . . . . . . . . 95
C.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
D Testing 97
D.1 What constitutes a unit test? . . . . . . . . . . . . . . . . . . . . 97
D.2 When should I write my tests? . . . . . . . . . . . . . . . . . . . 98
D.3 How seriously should I view my test suite? . . . . . . . . . . . . . 99
D.4 The three A’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
D.5 The structuring of tests . . . . . . . . . . . . . . . . . . . . . . . 99
D.6 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
D.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
E Symbol Definitions 101
III
, Chapter 1
Introduction
1.1 What this book is, and what it isn’t
This book provides implementations of common and uncommon algorithms in
pseudocode which is language independent and provides for easy porting to most
imperative programming languages. It is not a definitive book on the theory of
data structures and algorithms.
For the most part this book presents implementations devised by the authors
themselves based on the concepts by which the respective algorithms are based
upon so it is more than possible that our implementations differ from those
considered the norm.
You should use this book alongside another on the same subject, but one
that contains formal proofs of the algorithms in question. In this book we use
the abstract big Oh notation to depict the run time complexity of algorithms
so that the book appeals to a larger audience.
1.2 Assumed knowledge
We have written this book with few assumptions of the reader, but some have
been necessary in order to keep the book as concise and approachable as possible.
We assume that the reader is familiar with the following:
1. Big Oh notation
2. An imperative programming language
3. Object oriented concepts
1.2.1 Big Oh notation
For run time complexity analysis we use big Oh notation extensively so it is vital
that you are familiar with the general concepts to determine which is the best
algorithm for you in certain scenarios. We have chosen to use big Oh notation
for a few reasons, the most important of which is that it provides an abstract
measurement by which we can judge the performance of algorithms without
using mathematical proofs.
1
