Compsci 220 - Coursebook PDF

Preview

Summary

Coursebook...

Description

Introduction to Algorithms and Data Structures M ICHAEL J. D INNEEN

G EORG Y G IMEL’ FARB

c 2016 (Fourth edition)

M ARK C. W ILSON

Contents Contents

2

List of Figures

5

List of Tables

7

Preface

8

I Introduction to Algorithm Analysis

14

1 What is Algorithm Analysis? 1.1 Efficiency of algorithms: first examples . . . . . . . . . . . . . . . . . . . 1.2 Running time for loops and other computations . . . . . . . . . . . . . 1.3 “Big-Oh”, “Big-Theta”, and “Big-Omega” tools . . . . . . . . . . . . . . . 1.4 Time complexity of algorithms . . . . . . . . . . . . . . . . . . . . . . . 1.5 Basic recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Capabilities and limitations of algorithm analysis . . . . . . . . . . . . . 1.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 16 20 21 27 30 36 38

2 Efficiency of Sorting 2.1 The problem of sorting . . . . . . . . 2.2 Insertion sort . . . . . . . . . . . . . . 2.3 Mergesort . . . . . . . . . . . . . . . . 2.4 Quicksort . . . . . . . . . . . . . . . . 2.5 Heapsort . . . . . . . . . . . . . . . . 2.6 Data selection . . . . . . . . . . . . . 2.7 Lower complexity bound for sorting 2.8 Notes . . . . . . . . . . . . . . . . . .

39 39 41 46 49 56 63 66 68

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

3 Efficiency of Searching 69 3.1 The problem of searching . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.2 3.3 3.4 3.5 3.6

Sorted lists and binary search . . . . . . . . . . . Binary search trees . . . . . . . . . . . . . . . . . Self-balancing binary and multiway search trees Hash tables . . . . . . . . . . . . . . . . . . . . . . Notes . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

II Introduction to Graph Algorithms 4 The Graph Abstract Data Type 4.1 Basic definitions . . . . . . . . . . . . . . . . 4.2 Digraphs and data structures . . . . . . . . 4.3 Implementation of digraph ADT operations 4.4 Notes . . . . . . . . . . . . . . . . . . . . . .

. 72 . 77 . 82 . 88 . 101

103 . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

104 . 104 . 110 . 114 . 116

5 Graph Traversals and Applications 117 5.1 Generalities on graph traversal . . . . . . . . . . . . . . . . . . . . . . . 117 5.2 DFS and BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.3 Additional properties of depth-first search . . . . . . . . . . . . . . . . . 124 5.4 Additional properties of breadth-first search . . . . . . . . . . . . . . . . 129 5.5 Priority-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.6 Acyclic digraphs and topological ordering . . . . . . . . . . . . . . . . . 133 5.7 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.8 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 5.9 Maximum matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.10 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6 Weighted Digraphs and Optimization Problems 6.1 Weighted digraphs . . . . . . . . . . . . . . . . 6.2 Distance and diameter in the unweighted case 6.3 Single-source shortest path problem . . . . . . 6.4 All-pairs shortest path problem . . . . . . . . . 6.5 Minimum spanning tree problem . . . . . . . . 6.6 Hard graph problems . . . . . . . . . . . . . . . 6.7 Notes . . . . . . . . . . . . . . . . . . . . . . . .

III Appendices

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

151 . 151 . 153 . 154 . 161 . 164 . 168 . 169

170

A Java code for Searching and Sorting 171 A.1 Sorting and selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 A.2 Search methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

B Java graph ADT 178 B.1 Java adjacency matrix implementation . . . . . . . . . . . . . . . . . . . 181 B.2 Java adjacency lists implementation . . . . . . . . . . . . . . . . . . . . 186 B.3 Standardized Java graph class . . . . . . . . . . . . . . . . . . . . . . . . 191 B.4 Extended graph classes: weighted edges . . . . . . . . . . . . . . . . . . 192 C Background on Data Structures 201 C.1 Informal discussion of ADTs . . . . . . . . . . . . . . . . . . . . . . . . . 201 C.2 Notes on a more formal approach . . . . . . . . . . . . . . . . . . . . . . 203 D Mathematical Background D.1 Sets . . . . . . . . . . . . . . . . . . . . . D.2 Mathematical induction . . . . . . . . . D.3 Relations . . . . . . . . . . . . . . . . . . D.4 Basic rules of logarithms . . . . . . . . . D.5 L’Hˆopital’s rule . . . . . . . . . . . . . . . D.6 Arithmetic, geometric, and other series . D.7 Trees . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

204 . 204 . 205 . 205 . 206 . 207 . 207 . 209

E Solutions to Selected Exercises

211

Bibliography

234

Index

235

List of Figures 1.1 1.2 1.3 1.4 1.5

Linear-time algorithm to sum an array. . . . . . . . . . . Quadratic time algorithm to compute sums of an array. Linear-time algorithm to compute sums of an array. . . “Big Oh” property: g(n) is O(n). . . . . . . . . . . . . . . Telescoping as a recursive substitution. . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

17 18 19 23 34

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Insertion sort for arrays. . . . . . . . . . . . . . . . Recursive mergesort for arrays . . . . . . . . . . . . Linear time merge for arrays . . . . . . . . . . . . . Basic array-based quicksort. . . . . . . . . . . . . . Complete binary tree and its array representation. Maximum heap and its array representation. . . . Heapsort. . . . . . . . . . . . . . . . . . . . . . . . . Basic array-based quickselect. . . . . . . . . . . . . Decision tree for n = 3. . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

45 48 49 55 56 58 61 65 66

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15

A sequential search algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . Binary search for the key 42. . . . . . . . . . . . . . . . . . . . . . . . . . . . Binary tree representation of a sorted array. . . . . . . . . . . . . . . . . . . Binary search with three-way comparisons. . . . . . . . . . . . . . . . . . . Faster binary search with two-way comparisons. . . . . . . . . . . . . . . . Binary trees: only the leftmost tree is a binary search tree. . . . . . . . . . . Search and insertion in the binary search tree. . . . . . . . . . . . . . . . . Removal of the node with key 10 from the binary search tree. . . . . . . . . Binary search trees obtained by permutations of 1, 2, 3, 4. . . . . . . . . . . Binary search trees of height about logn. . . . . . . . . . . . . . . . . . . . . Binary search trees of height about n. . . . . . . . . . . . . . . . . . . . . . . Left and right rotations of a BST. . . . . . . . . . . . . . . . . . . . . . . . . . Multiway search tree of order m = 4. . . . . . . . . . . . . . . . . . . . . . . 2–4 B-tree with the leaf storage size 7. . . . . . . . . . . . . . . . . . . . . . Birthday paradox: Pr365 (n). . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 73 75 76 76 77 78 79 80 81 81 83 85 87 94

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4.1 4.2 4.3 4.4 4.5

A graph G1 and a digraph G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 A subdigraph and a spanning subdigraph of G2 . . . . . . . . . . . . . . . . . 108 The subdigraph of G2 induced by {1, 2, 3}. . . . . . . . . . . . . . . . . . . . 109 The reverse of digraph G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 The underlying graph of G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19

Graph traversal schema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Node states in the middle of a digraph traversal. . . . . . . . . . . . . . . . 118 Decomposition of a digraph in terms of search trees. . . . . . . . . . . . . . 120 A graph G1 and a digraph G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 BFS trees for G1 and G2 , rooted at 0. . . . . . . . . . . . . . . . . . . . . . . . 123 DFS trees for G1 and G2 , rooted at 0. . . . . . . . . . . . . . . . . . . . . . . 124 Depth-first search algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Recursive DFS visit algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Breadth-first search algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . 130 Priority-first search algorithm (first kind). . . . . . . . . . . . . . . . . . . . 134 Digraph describing structure of an arithmetic expression. . . . . . . . . . . 135 Topological orders of some DAGs. . . . . . . . . . . . . . . . . . . . . . . . . 136 A digraph and its strongly connected components. . . . . . . . . . . . . . . 140 Structure of a digraph in terms of its strong components. . . . . . . . . . . 140 Some (di)graphs with different cycle behaviour. . . . . . . . . . . . . . . . . 143 A bipartite graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 A maximal and maximum matching in a bipartite graph. . . . . . . . . . . 146 An algorithm to find an augmenting path. . . . . . . . . . . . . . . . . . . . 147 Structure of the graph traversal tree for finding augmenting paths. . . . . . 149

6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8

Some weighted (di)graphs. . . . . . . . . Dijkstra’s algorithm, first version. . . . . Picture for proof of Dijkstra’s algorithm. Dijkstra’s algorithm, PFS version. . . . . Bellman–Ford algorithm. . . . . . . . . . Floyd’s algorithm. . . . . . . . . . . . . . Prim’s algorithm. . . . . . . . . . . . . . Kruskal’s algorithm. . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. 152 . 155 . 157 . 158 . 159 . 162 . 167 . 168

B.1 Sample output of the graph test program. . . . . . . . . . . . . . . . . . . . 193 D.1 Approximation of an integral by lower rectangles. . . . . . . . . . . . . . . . 209

List of Tables 1.1 Relative growth of linear and quadratic terms in an expression. . . . . . . . 18 1.2 Relative growth of running time T (n) when the input size increases. . . . . 27 1.3 The largest data sizes n that can be processed by an algorithm. . . . . . . . 28 2.1 2.2 2.3 2.4 2.5 2.6

Sample execution of insertion sort. . . . . . . . . . . . . . . . . . . . . . . . Number of inversions Ii , comparisons Ci and data moves Mi . . . . . . . . . Partitioning in quicksort with pivot p = 31. . . . . . . . . . . . . . . . . . . . Inserting a new node with the key 75 in the heap in Figure 2.6. . . . . . . . Deletion of the maximum key from the heap in Figure 2.6. . . . . . . . . . Successive steps of heapsort. . . . . . . . . . . . . . . . . . . . . . . . . . . .

42 44 54 59 59 62

3.1 3.2 3.3 3.4 3.5 3.6

A map between airport codes and locations. . . . . . . . . . . . Height of the optimal m-ary search tree with n nodes. . . . . . Open addressing with linear probing (OALP). . . . . . . . . . . Open addressing with double hashing (OADH). . . . . . . . . . Birthday paradox: Pr365 (n). . . . . . . . . . . . . . . . . . . . . . Average search time bounds in hash tables with load factor λ. .

70 85 90 91 93 97

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4.1 Digraph operations in terms of data structures. . . . . . . . . . . . . . . . . 114 4.2 Comparative worst-case performance of adjacency lists and matrices. . . . 115 6.1 Illustrating Dijkstra’s algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . 156

Introduction to the Fourth Edition

The fourth edition follows the third edition, while incorporates fixes for the errata discovered in the third edition. The textbook’s coverpage displays the complete list of 88 connected forbidden minors for graphs with vertex cover at most 6, computed by M. J. Dinneen and L. Xiong in 2001. This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License. Michael J. Dinneen Georgy Gimel’farb Mark C. Wilson Department of Computer Science University of Auckland Auckland, New Zealand

Introduction to the Third Edition

The focus for this third edition has been to make an electronic version that students can read on the tablets and laptops that they bring to lectures. The main changes from the second edition are: • Incorporated fixes for the errata discovered in the second edition.

• Made e-book friendly by adding cross referencing links to document elements and formatted pages to fit on most small screen tablets (i.e., width of margins minimized). • Limited material for University of Auckland’s CompSci 220 currently taught topics. Removed the two chapters on formal languages (Part III) and truncated the book title. • This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.

Michael J. Dinneen Georgy Gimel’farb Mark C. Wilson Department of Computer Science University of Auckland Auckland, New Zealand {mjd, georgy, mcw}@cs.auckland.ac.nz March 2013

Introduction to the Second Edition

Writing a second edition is a thankless task, as is well known to authors. Much of the time is spent on small improvements that are not obvious to readers. We have taken considerable efforts to correct a large number of errors found in the first edition, and to improve explanation and presentation throughout the book, while retaining the philosophy behind the original. As far as material goes, the main changes are: • • • •

more exercises and solutions to many of them; a new section on maximum matching (Section 5.9); a new section on string searching (Part III); a Java graph library updated to Java 1.6 and freely available for download.

The web site http://www.cs.auckland.ac.nz/textbookCS220/ for the book provides additional material including source code. Readers finding errors are encouraged to contact us after viewing the errata page at this web site. In addition to the acknowledgments in the first edition, we thank Sonny Datt for help with updating the Java graph library, Andrew Hay for help with exercise solutions and Cris Calude for comments. Rob Randtoul (PlasmaDesign.co.uk) kindly allowed us to use his cube artwork for the book’s cover. Finally, we thank MJD all students who have struggled to learn from the first edition and have given us feedback, either positive or negative; GLG my wife Natasha and all the family for their permanent help and support; MCW my wife Golbon and sons Yusef and Yahya, for their sacrifices during the writing of this book, and the joy they bring to my life even in the toughest times. 31 October 2008

Introduction to the First Edition

This book is an expanded, and, we hope, improved version of the coursebook for the course COMPSCI 220 which we have taught several times in recent years at the University of Auckland. We have taken the step of producing this book because there is no single text available that covers the syllabus of the above course at the level required. Indeed, we are not aware of any other book that covers all the topics presented here. Our aim has been to produce a book that is straightforward, concise, and inexpensive, and suitable for self-study (although a teacher will definitely add value, particularly where the exercises are concerned). It is an introduction to some key areas at the theoretical end of computer science, which nevertheless have many practical applications and are an essential part of any computer science student’s education. The material in the book is all rather standard. The novelty is in the combination of topics and some of the presentation. Part I deals with the basics of algorithm analysis, tools that predict the performance of programs without wasting time implementing them. Part II covers many of the standard fast graph algorithms that have applications in many different areas of computer science and science in general. Part III introduces the theory of formal languages, shifting the focus from what can be computed quickly to what families of strings can be recognized easily by a particular type of machine. The book is designed to be read cover-to-cover. In particular Part I should come first. However, one can read Part III before Part II with little chance of confusion. To make best use of the book, one must do the exercises. They vary in difficulty from routine to tricky. No solutions are provided. This policy may be changed in a later edition. The prerequisites for this book are similar to those of the above course, namely two semesters of programming in a structured language such as J...