Growing Algorithms And Data Structures (Fourth Edition) © David Scuse Department of Computer Science University of Manitoba June, 2011 GROWING ALGORITHMS AND DATA STRUCTURES INTRODUCTION ................................................................................................................ 1 1 PROCEDURAL PROGRAMMING ................................................................................... 3 1.1 INTRODUCTION ........................................................................................................... 3 1.2 PROGRAMMING ............................................................................................................ 3 1.3 HELLO WORLD ............................................................................................................ 4 1.4 COMMENTS ................................................................................................................ 5 1.5 ASSIGNMENT STATEMENT ................................................................................................ 6 1.6 CONDITIONAL EXECUTION ............................................................................................... 8 1.7 LOOPS ................................................................................................................... 12 1.8 FUNCTIONS/METHODS ................................................................................................. 13 1.9 LISTS/ARRAYS .......................................................................................................... 14 1.10 PASSING PARAMETERS ............................................................................................. 19 1.11 SCOPE ............................................................................................................... 22 1.12 DATA TYPES ......................................................................................................... 22 1.13 STRINGS ............................................................................................................. 24 1.14 MODULES/CLASSES ................................................................................................ 26 1.15 DETERMINING PRIME NUMBERS ................................................................................... 27 1.16 DIFFERENCES BETWEEN PYTHON 2 AND PYTHON 3 .............................................................. 29 1.17 DIFFERENCES BETWEEN PYTHON AND JAVA ...................................................................... 29 1.18 SUMMARY ............................................................................................................ 29 2 GROWING ALGORITHMS ......................................................................................... 31 2.1 INTRODUCTION ......................................................................................................... 31 2.2 SEARCHING A LIST ..................................................................................................... 31 2.2.1 Linear Search ................................................................................................. 33 2.2.2 Linear Search of an Ordered List ....................................................................... 36 2.2.3 Binary Search ................................................................................................ 38 2.3 SEARCHING A LIST OF STRINGS ...................................................................................... 40 2.4 RECAP ................................................................................................................... 41 2.5 ARRAY INITIALIZATION ................................................................................................. 41 2.6 CONDITIONAL OPERATOR .............................................................................................. 42 2.7 THE FOR STATEMENT ................................................................................................... 43 2.8 SYSTEM.ARRAYCOPY .................................................................................................... 45 2.9 ROTATING THE ELEMENTS IN AN ARRAY .............................................................................. 46 2.10 GENERATING PRIME NUMBERS .................................................................................... 47 2.11 GENERATING SEQUENCES OF VALUES ............................................................................ 48 2.12 GENERATING A FREQUENCY COUNT OF VALUES ................................................................. 49 2.13 MERGE ALGORITHM ................................................................................................. 50 2.14 MERGING STRINGS ................................................................................................. 58 2.15 PARALLEL ARRAYS .................................................................................................. 59 2.15.1 Maintaining the Number of Elements in the Arrays .......................................... 60 2.15.2 Using a Sentinel Value ................................................................................. 63 2.15.3 Copying the Arrays ..................................................................................... 65 2.15.4 Global Variables .......................................................................................... 67 2.15.5 Recap ....................................................................................................... 68 2.16 GROWING ALGORITHMS ............................................................................................ 69 2.17 DEBUGGING ......................................................................................................... 70 2.18 TESTING ............................................................................................................. 74 2.19 DEFENSIVE PROGRAMMING ........................................................................................ 74 2.20 ALGORITHM EFFICIENCY ............................................................................................ 74 2.21 SUMMARY ............................................................................................................ 76 i 3 OBJECTS .................................................................................................................. 77 3.1 INTRODUCTION ......................................................................................................... 77 3.2 DATA TYPES ............................................................................................................. 77 3.3 BASIC OBJECT STRUCTURE ............................................................................................ 77 3.4 WHAT IS AN OBJECT? .................................................................................................. 82 3.5 SIMPLE CLASS STRUCTURE ............................................................................................ 83 3.6 VISIBILITY MODIFIERS ................................................................................................. 85 3.7 MANIPULATING AN OBJECT ............................................................................................ 85 3.8 CLASSES AND INSTANCES ............................................................................................. 86 3.9 STATE INFORMATION ................................................................................................... 87 3.10 ARRAYS OF OBJECTS ............................................................................................... 89 3.11 CLASS VARIABLES AND CLASS METHODS ........................................................................ 92 3.12 WRAPPER CLASSES ................................................................................................. 93 3.13 IMMUTABLE OBJECTS ............................................................................................... 95 3.14 COMPARING OBJECTS .............................................................................................. 96 3.15 ENCAPSULATION AND INFORMATION HIDING ..................................................................... 98 3.16 FACTORY METHOD .................................................................................................. 98 3.17 THE MAIN CLASS ................................................................................................... 99 3.18 SUMMARY .......................................................................................................... 100 4 FILE INPUT AND OUTPUT ...................................................................................... 103 4.1 INTRODUCTION ....................................................................................................... 103 4.2 SCANNER CLASS ...................................................................................................... 103 4.3 BUFFERED FILE INPUT ................................................................................................ 103 4.4 FILE OUTPUT .......................................................................................................... 105 4.5 RECAP ................................................................................................................. 107 4.6 MERGING FILES ....................................................................................................... 108 4.7 TWO USEFUL TEXTPAD FEATURES .................................................................................. 113 4.8 EXCEPTIONS ........................................................................................................... 113 4.8.1 Thowing Exceptions ...................................................................................... 115 4.8.2 Programmer-Defined Exceptions ..................................................................... 116 4.9 AN INPUT/OUTPUT PROCESSING CLASS ........................................................................... 117 5 STRINGS ............................................................................................................... 121 5.1 INTRODUCTION ....................................................................................................... 121 5.2 CHARACTER MANIPULATION ......................................................................................... 121 5.3 CHARACTER WRAPPER CLASS ....................................................................................... 123 5.4 STRINGS ............................................................................................................... 124 5.5 STRING METHODS .................................................................................................... 126 5.6 STRING COMPARISON ................................................................................................ 128 5.7 STRINGS ARE OBJECTS .............................................................................................. 129 5.8 STRINGS ARE IMMUTABLE ............................................................................................ 131 5.9 DATA VALIDATION .................................................................................................... 132 5.10 STRING FORMATTING ............................................................................................. 133 5.11 STRING PROCESSING ............................................................................................. 136 5.12 STRING TOKENIZING ............................................................................................. 138 5.12.1 Extracting Tokens ..................................................................................... 138 5.12.2 String Split Method ................................................................................... 139 5.13 BINARY SEARCH OF AN ARRAY OF STRINGS .................................................................... 139 5.14 PATTERN MATCHING .............................................................................................. 140 5.15 MORE PATTERN MATCHING ...................................................................................... 142 5.16 COUNTING CHARACTERS ......................................................................................... 143 5.17 A MUTABLE STRING CLASS ...................................................................................... 145 5.18 STRINGBUFFER CLASS ........................................................................................... 146 5.18.1 StringBuffer Methods ................................................................................. 146 5.18.2 Using a StringBuffer Object ........................................................................ 147 ii 6 OBJECT EXAMPLES ................................................................................................ 149 6.1 INTRODUCTION ....................................................................................................... 149 6.2 PERSON EXAMPLE ..................................................................................................... 149 6.3 VIDEO STORE EXAMPLE .............................................................................................. 150 6.4 EMPLOYEE EXAMPLE .................................................................................................. 151 6.5 GST ACCOUNT EXAMPLE ............................................................................................ 153 6.6 COFFEE SHOP EXAMPLE .............................................................................................. 154 6.6.1 Iteration 1 ................................................................................................... 154 6.6.2 Iteration 2 ................................................................................................... 155 6.6.3 Iteration 3 ................................................................................................... 156 6.6.4 Iteration 4 ................................................................................................... 157 6.6.5 Recap ......................................................................................................... 159 6.7 WORDS CLASS ........................................................................................................ 159 7 OBJECT REPRESENTATION .................................................................................... 163 7.1 INTRODUCTION ....................................................................................................... 163 7.2 OBJECT REFERENCES ................................................................................................. 163 7.3 ARRAYS ARE OBJECTS ................................................................................................ 165 7.4 STRINGS ............................................................................................................... 168 7.4.1 Strings are Immutable .................................................................................. 169 7.5 PASSING PARAMETERS ............................................................................................... 170 7.6 CLONING OBJECTS ................................................................................................... 174 7.7 INFORMATION ABOUT OBJECTS ..................................................................................... 175 7.8 SUMMARY ............................................................................................................. 175 8 OBJECT ORIENTATION PRACTICES ........................................................................ 177 8.1 INTRODUCTION ....................................................................................................... 177 8.2 BASIC CLASS STRUCTURE ........................................................................................... 177 8.3 REMOVE ACCESSORS AND MUTATORS .............................................................................. 182 8.4 MOVE OBJECT PROCESSING INTO ITS OWN CLASS ................................................................ 184 8.5 USING FILE INPUT .................................................................................................... 186 8.6 USING A FACTORY METHOD ......................................................................................... 187 8.7 COMPLETE CREDIT-CARD EXAMPLE ................................................................................. 188 8.8 SUMMARY ............................................................................................................. 192 9 OBJECT COLLECTIONS ........................................................................................... 193 9.1 INTRODUCTION ....................................................................................................... 193 9.2 ARRAYLISTS ........................................................................................................... 193 9.3 COMPILING ARRAYLISTS ............................................................................................. 195 9.4 ARRAYLIST METHODS ................................................................................................ 196 9.5 CASTING .............................................................................................................. 197 9.6 REVERSING THE ELEMENTS IN AN ARRAYLIST ..................................................................... 198 9.7 SEARCHING AN ARRAYLIST .......................................................................................... 199 9.8 PRINTING THE CONTENTS OF AN ARRAYLIST ....................................................................... 201 9.9 ROTATING THE CONTENTS OF AN ARRAYLIST ...................................................................... 201 9.10 INSERTING INTO AN ARRAYLIST IN ASCENDING ORDER ...................................................... 202 9.11 SEARCHING AN ARRAYLIST OF INTEGERS WITH A BINARY SEARCH .......................................... 202 9.12 SEARCHING AN ARRAYLIST OF STRINGS WITH A BINARY SEARCH ........................................... 203 9.13 CREDIT-CARDS EXAMPLE ........................................................................................ 204 9.14 GENERICS ......................................................................................................... 206 9.15 BOXING AND UNBOXING ......................................................................................... 207 9.16 OUR VERSION OF ARRAYLIST .................................................................................... 208 9.17 ARRAYLIST ALGORITHMS ......................................................................................... 209 9.18 PROCESSING COURSE MARKS ................................................................................... 210 9.19 SUMMARY .......................................................................................................... 214 iii 10 OBJECT HIERARCHIES ........................................................................................... 215 10.1 INTRODUCTION .................................................................................................... 215 10.2 OBJECTS ........................................................................................................... 215 10.3 ANIMALS EXAMPLE ................................................................................................ 216 10.4 CLASS HIERARCHIES ............................................................................................. 219 10.5 VISIBILITY ......................................................................................................... 220 10.6 INHERITING AND OVERRIDING METHODS ....................................................................... 221 10.7 CONSTRUCTORS IN HIERARCHIES ............................................................................... 224 10.8 CASTING OBJECTS ................................................................................................ 227 10.9 INSTANCEOF ....................................................................................................... 228 10.10 CLASS VARIABLES AND CLASS METHODS ...................................................................... 229 10.11 CLASS OBJECT .................................................................................................... 230 10.12 ARRAYS ARE OBJECTS ............................................................................................ 231 10.13 COLLECTIONS OF OBJECTS ....................................................................................... 231 10.14 ARRAYLISTS ....................................................................................................... 233 10.15 GENERICS ......................................................................................................... 234 10.16 DRIVER’S LICENSE EXAMPLE ..................................................................................... 235 10.17 RECAP .............................................................................................................. 238 10.18 SUMMARY .......................................................................................................... 238 11 MORE OBJECT HIERARCHY TOPICS ....................................................................... 239 11.1 INTRODUCTION .................................................................................................... 239 11.2 POLYMORPHISM ................................................................................................... 239 11.3 ABSTRACT CLASSES .............................................................................................. 245 11.4 INHERITING AND SHADOWING VARIABLES ..................................................................... 246 12 OBJECT HIERARCHY EXAMPLES ............................................................................. 249 12.1 INTRODUCTION .................................................................................................... 249 12.2 BANK ACCOUNT EXAMPLE ........................................................................................ 249 12.2.1 Recap ..................................................................................................... 252 12.3 CREDIT CARD EXAMPLE .......................................................................................... 252 12.4 STOCK PORTFOLIO EXAMPLE ..................................................................................... 255 12.4.1 Iteration 1 ............................................................................................... 256 12.4.2 Iteration 2 ............................................................................................... 258 12.4.3 Iteration 3 ............................................................................................... 259 12.4.4 Iteration 4 ............................................................................................... 263 12.4.5 Iteration 5 ............................................................................................... 267 12.4.6 Iteration 6 ............................................................................................... 268 12.4.7 Iteration 7 ............................................................................................... 269 12.4.8 Iteration 8 ............................................................................................... 271 12.4.9 Iteration 9 ............................................................................................... 271 12.4.10 Complete Stock Portfolio Example ............................................................... 272 12.4.11 Recap ..................................................................................................... 277 12.5 SUMMARY .......................................................................................................... 277 13 SORTING ............................................................................................................... 279 13.1 INTRODUCTION .................................................................................................... 279 13.2 BUBBLE SORT ..................................................................................................... 279 13.3 SELECTION SORT ................................................................................................. 282 13.4 INSERTION SORT ................................................................................................. 284 13.5 SORTING AN ARRAY OF STRINGS ................................................................................ 286 13.6 SORTING INTO DESCENDING ORDER ............................................................................ 287 13.7 SUMMARY .......................................................................................................... 287 14 RECURSION ........................................................................................................... 289 14.1 INTRODUCTION .................................................................................................... 289 14.2 ITERATION ......................................................................................................... 289 14.3 RECURSION ........................................................................................................ 290 iv 14.4 PROCESSING STRINGS ........................................................................................... 293 14.4.1 String Reverse ......................................................................................... 293 14.4.2 Palindromes ............................................................................................. 294 14.4.3 String Padding .......................................................................................... 295 14.4.4 Number Conversions ................................................................................. 295 14.5 PROCESSING ARRAYS ............................................................................................. 296 14.6 BINARY SEARCH .................................................................................................. 299 14.7 RECURSIVE MERGE ............................................................................................... 300 14.8 PROCESSING ARRAYLISTS ....................................................................................... 300 14.9 FIBONACCI NUMBERS ............................................................................................. 301 14.10 PROCESSING OBJECTS ........................................................................................... 303 14.11 THE RECURSION STACK .......................................................................................... 304 14.12 ITERATION VERSUS RECURSION ................................................................................. 306 14.13 RECURSION EXAMPLES ........................................................................................... 307 14.13.1 Palindrome .............................................................................................. 307 14.13.2 Reversing Words ....................................................................................... 307 14.13.3 Filling an Array ......................................................................................... 308 14.13.4 Precomputing Values ................................................................................. 308 14.13.5 Frequency Count ...................................................................................... 309 15 LINKED LISTS ....................................................................................................... 311 15.1 INTRODUCTION .................................................................................................... 311 15.2 LISTS .............................................................................................................. 311 15.3 ARRAYS ............................................................................................................ 311 15.4 A SIMPLE LINKED LIST ........................................................................................... 311 15.5 A BETTER LINKED LIST ........................................................................................... 314 15.6 A LINKED LIST CLASS ............................................................................................ 316 15.7 INSERTING AT THE BEGINNING OF A LINKED LIST ............................................................. 319 15.8 INSERTING AT THE END OF A LINKED LIST ..................................................................... 320 15.9 DELETING AN ELEMENT ........................................................................................... 321 15.10 LINKED LIST EXAMPLES .......................................................................................... 326 15.10.1 Find Last Node ......................................................................................... 326 15.10.2 Print String Objects ................................................................................... 327 15.10.3 Print Adjacent String Objects ...................................................................... 327 15.10.4 Reverse List Elements ............................................................................... 328 15.10.5 Add Back Links ......................................................................................... 328 15.10.6 Split a List into Two Lists ........................................................................... 328 15.10.7 Rotating the Contents of a Linked List .......................................................... 329 15.10.8 Remove String Objects .............................................................................. 330 15.11 RECAP .............................................................................................................. 330 15.12 SUMMARY .......................................................................................................... 331 16 MULTI-DIMENSIONAL ARRAYS .............................................................................. 333 16.1 INTRODUCTION .................................................................................................... 333 16.2 ONE-DIMENSIONAL ARRAYS ..................................................................................... 333 16.3 MULTI-DIMENSIONAL ARRAYS ................................................................................... 333 16.4 MATRICES ......................................................................................................... 335 16.5 MATRIX OBJECT ................................................................................................... 337 16.6 ARRAY INITIALIZATION ........................................................................................... 339 16.7 ARRAYS OF OBJECTS ............................................................................................. 339 16.8 TIC-TAC-TOE ..................................................................................................... 340 17 GENERIC DATA STRUCTURES ................................................................................ 343 17.1 INTRODUCTION .................................................................................................... 343 17.2 GENERIC LINKED LIST ............................................................................................ 343 17.3 USING COMPARETO ............................................................................................... 345 17.4 JAVA’S GENERICS ................................................................................................. 346 17.5 USING COMPARETO WITH GENERICS ............................................................................ 349 v 17.6 USING A JAVA INTERFACE ........................................................................................ 349 18 GROWING AND REFACTORING .............................................................................. 353 18.1 INTRODUCTION .................................................................................................... 353 18.2 REFACTORING ..................................................................................................... 353 18.2.1 Rename Method ....................................................................................... 353 18.2.2 Extract Method ......................................................................................... 353 18.2.3 Convert Procedural Design to Objects .......................................................... 354 18.2.4 Comments ............................................................................................... 354 18.3 DESIGN ............................................................................................................ 354 18.4 FLIGHTS EXAMPLE ................................................................................................ 355 18.4.1 Iteration 1 ............................................................................................... 355 18.4.2 Iteration 2 ............................................................................................... 356 18.4.3 Iteration 3 ............................................................................................... 358 18.4.4 Iteration 4 ............................................................................................... 359 18.4.5 Iteration 5 ............................................................................................... 361 18.4.6 Iteration 6 ............................................................................................... 363 18.4.7 Iteration 7 ............................................................................................... 364 18.4.8 Iteration 8 ............................................................................................... 365 18.4.9 Iteration 9 ............................................................................................... 367 18.4.10 Iteration 10 ............................................................................................. 367 18.4.11 Iteration 11 ............................................................................................. 369 18.5 COMPLETE FLIGHTS EXAMPLE .................................................................................... 370 18.6 SUMMARY .......................................................................................................... 375 19 MISCELLANEOUS TOPICS ...................................................................................... 377 19.1 INTRODUCTION .................................................................................................... 377 19.2 SYSTEM STREAMS ................................................................................................. 377 19.3 FILE PROCESSING WRAPPER CLASSES .......................................................................... 381 19.4 BUFFERED CONSOLE INPUT ...................................................................................... 382 19.5 FILES AND THE END-OF-LINE CHARACTER(S) ................................................................. 384 19.6 NON-RECTANGULAR ARRAYS .................................................................................... 384 19.7 PARALLEL ARRAYS ................................................................................................ 385 19.8 HIGHER DIMENSIONAL ARRAYS ................................................................................. 386 19.9 MERGE SORT ...................................................................................................... 387 19.10 QUICKSORT ....................................................................................................... 388 19.11 SORTING A LINKED LIST ......................................................................................... 389 19.12 BINARY TREES .................................................................................................... 393 19.13 TOWERS OF HANOI ............................................................................................... 395 19.14 SYSTEM PROPERTIES ............................................................................................. 397 19.15 INFORMATION ABOUT OBJECTS .................................................................................. 397 19.16 THE SYSTEM TIMER ............................................................................................... 398 19.17 THE STACK TRACE ................................................................................................ 399 19.18 GARBAGE COLLECTION ........................................................................................... 400 19.19 THE HEAP .......................................................................................................... 400 19.20 THE OBJECT HIERARCHY ......................................................................................... 401 19.21 CHANGING THE HASH CODE ..................................................................................... 402 19.22 FILE DIRECTORY PROCESSING ................................................................................... 402 19.23 RECURSIVE FILE DIRECTORY PROCESSING ..................................................................... 403 19.24 STACK-BASED FILE DIRECTORY PROCESSING ................................................................. 404 19.25 CREATING OBJECTS DYNAMICALLY .............................................................................. 406 19.26 CALLING METHODS DYNAMICALLY .............................................................................. 407 19.27 POLYMORPHISM WITHOUT HIERARCHIES ........................................................................ 408 19.28 COMPILING AND EXECUTING A JAVA PROJECT .................................................................. 411 19.29 SUMMARY .......................................................................................................... 413 INDEX ........................................................................................................................... 415 vi INTRODUCTION Courses such as COMP 1010 and COMP 1012 focus on developing algorithms using primitive data types (ints, doubles, etc.), conditions, loops, arrays, and methods. These are the basic building blocks of computer programming and this style of programming is referred to as “procedural programming”. In COMP 1020, we examine how these building blocks can be put together to solve more complex problems. At the same time, we also make the transition from procedural programming to object-oriented programming. Writing good object-oriented programs is not easy, it takes some time to stop thinking in a procedural manner and start thinking in an object-oriented manner. Our study of algorithms concentrates on the development of algorithms that work correctly and are easy to understand. We will not be concerned with developing algorithms that are as efficient as possible. We will note where certain algorithms are inefficient and could be improved but we will not attempt to make each algorithm optimal in terms of its memory requirements and/or execution time. In COMP 1010 and COMP 1012, the organization of each program in an assignment was normally described in class. In this course, the organization of solution for assignments will not be given; instead, the student is expected to develop the structure of each program by him/herself (with some hints from the instructor). Instead of developing the entire program at once, the program will be developed (“grown”) slowly. We will concentrate on “doing the simplest thing that works”, in other words, develop a simple, incomplete version of the algorithm that executes correctly and then gradually improve the algorithm until it provides the required functionality (start small and grow slowly). We will not add functionality that is not explicitly required! “Simple systems are easier to build, easier to maintain, smaller, and faster than complex ones. A simple system ‘maximizes the work done’, by increasing ‘the amount of work not done’. A program must do exactly what’s required by the user. Adding unasked-for-functionality dramatically increases the development time and decreases stability.” Allen Holub, Holub on Patterns, p. 6. David Scuse Department of Computer Science University of Manitoba June, 2011 1 2