D a t a S t r u c t u r e s a n d A l g o r i t h m s DSA Annotated Reference with Examples Granville Barne! Luca Del Tongo Data Structures and Algorithms: Annotated Reference with Examples First Edition Copyright (cid:176)c Granville Barnett, and Luca Del Tongo 2008. This book is made exclusively available from DotNetSlackers (http://dotnetslackers.com/) the place for .NET articles, and news from some of the leading minds in the software industry. 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 Preface Every book has a story as to how it came about and this one is no different, although we would be lying if we said its development had not been somewhat impromptu. Put simply this book is the result of a series of emails sent back and forth between the two authors during the development of a library for the .NET framework of the same name (with the omission of the subtitle of course!). The conversation started off something like, “Why don’t we create a more aesthetically pleasing way to present our pseudocode?” After a few weeks this new presentation style had in fact grown into pseudocode listings with chunks of text describing how the data structure or algorithm in question works and various other things about it. At this point we thought, “What the heck, let’s make this thing into a book!” And so, in the summer of 2008 we began work on this book side by side with the actual library implementation. When we started writing this book the only things that we were sure about with respect to how the book should be structured were: 1. alwaysmakeexplanationsassimpleaspossiblewhilemaintainingamoder- atelyfinedegreeofprecisiontokeepthemoreeagermindedreaderhappy; and 2. injectdiagramstodemystifyproblemsthatareevenmoderatlychallenging tovisualise(...andsowecouldrememberhowourownalgorithmsworked when looking back at them!); and finally 3. presentconciseandself-explanatorypseudocodelistingsthatcanbeported easily to most mainstream imperative programming languages like C++, C#, and Java. A key factor of this book and its associated implementations is that all algorithms (unless otherwise stated) were designed by us, using the theory of the algorithm in question as a guideline (for which we are eternally grateful to their original creators). Therefore they may sometimes turn out to be worse than the “normal” implementations—and sometimes not. We are two fellows of the opinion that choice is a great thing. Read our book, read several others on the same subject and use what you see fit from each (if anything) when implementing your own version of the algorithms in question. Throughthisbookwehopethatyouwillseetheabsolutenecessityofunder- standing which data structure or algorithm to use for a certain scenario. In all projects, especially those that are concerned with performance (here we apply an even greater emphasis on real-time systems) the selection of the wrong data structure or algorithm can be the cause of a great deal of performance pain. IV V Thereforeitisabsolutelykeythatyouthinkabouttheruntimecomplexityand space requirements of your selected approach. In this book we only explain the theoreticalimplications to consider, but this is fora good reason: compilers are very different in how they work. One C++ compiler may have some amazing optimisation phases specifically targeted at recursion, another may not, for ex- ample. Of course this is just an example but you would be surprised by how many subtle differences there are between compilers. These differences which may make a fast algorithm slow, and vice versa. We could also factor in the same concerns about languages that target virtual machines, leaving all the actual various implementation issues to you given that you will know your lan- guage’s compiler much better than us...well in most cases. This has resulted in a more concise book that focuses on what we think are the key issues. One final note: never take the words of others as gospel; verify all that can be feasibly verified and make up your own mind. Wehopeyouenjoyreadingthisbookasmuchaswehaveenjoyedwritingit. Granville Barnett Luca Del Tongo Acknowledgements Writing this short book has been a fun and rewarding experience. We would like to thank, in no particular order the following people who have helped us during the writing of this book. Sonu Kapoor generously hosted our book which when we released the first draft received over thirteen thousand downloads, without his generosity this book wouldnot havebeen ableto reachso manypeople. Jon Skeetprovidedus with an alarming number of suggestions throughout for which we are eternally grateful. Jon also edited this book as well. Wewouldalsoliketothankthosewhoprovidedtheoddsuggestionviaemail to us. All feedback was listened to and you will no doubt see some content influenced by your suggestions. A special thank you also goes out to those who helped publicise this book from Microsoft’s Channel 9 weekly show (thanks Dan!) to the many bloggers who helped spread the word. You gave us an audience and for that we are extremely grateful. Thank you to all who contributed in some way to this book. The program- ming community never ceases to amaze us in howwilling its constituentsare to give time to projects such as this one. Thank you. VI About the Authors Granville Barnett GranvilleiscurrentlyaPh.DcandidateatQueenslandUniversityofTechnology (QUT)workingonparallelismattheMicrosoftQUTeResearchCentre1. Healso holdsadegreeinComputerScience,andisaMicrosoftMVP.Hismaininterests are in programming languages and compilers. Granville can be contacted via one of two places: either his personal website (http://gbarnett.org) or his blog (http://msmvps.com/blogs/gbarnett). Luca Del Tongo Luca is currently studying for his masters degree in Computer Science at Flo- rence. His main interests vary from web development to research fields such as data mining and computer vision. Luca also maintains an Italian blog which can be found at http://blogs.ugidotnet.org/wetblog/. 1http://www.mquter.qut.edu.au/ VII