Tài liệu An introduction to data structures and algorithms

An Introduction to Data Structures and Algorithms Consulting Editor John C. Chemiavsky, National Science Foundation J.A. Storer An Introduction to Data Structures and Aigorithms Springer Science+Business Media, LLC James A. Storer Department of Computer Science Brandeis University Waltham, MA 02454 U.S.A. Library of Congress Cataloging-in-Publication Data Storer, James A. (James Andrew), 1953An introduetion to data struetures and algorithms / J.A. Storer. p. em. Inc1udes bibliographieal referenees and index. ISBN 978-1-4612-6601-3 ISBN 978-1-4612-0075-8 (eBook) DOI 10.1007/978-1-4612-0075-8 1. Data struetures (Computer seienee) 2. Computer algorithms. I. Title. QA76.9.D33 S73 2001 oo5.7'3-de21 2001043503 AMS Subjeet Classifieations: Primary---(j8P05, 68W40, 68WIO; Seeondary---(j8Q25, 68P10, 68W20, 68W25 Printed on acid-free paper ©2002 J.A. Storer Originally published by Birkhauser Boston / Springer-Verlag New York, Inc. in 2002 Softcover reprint of the hardcover 1st edition 2002 All rights reserved. This work may not be translated or copied in whole or in part without the written permission ofthe publisher (Springer Science+Business Media, LLC), except for brief excerpts in connection with reviews or scholarly analysis. U se in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. SPIN 10841937 Typeset by the author Cover design by Mary Burgess, Cambridge, MA 9 87 6 54 32 1 Preface This book is for college-level students who are attending accompanying lectures on data structures and algorithms. Except for the introduction, exercises, and notes for each chapter, page breaks have been put in manually and the format corresponds to a lecture style with ideas presented in "digestible" page-size quantities. It is assumed that the reader's background includes some basic mathematics and computer programming. Algorithms are presented with "pseudo-code", not programs from a specific language. It works well to complement a course based on this book with a programming "lab" that uses a manual for a specific programming language and assigns projects relating to the material being taught. Chapters 1 through 4 go at a slower pace than the remainder of the book, and include sample exercises with solutions; some of the sections in these chapters are starred to indicate that it may be appropriate to skip them on a first reading. A first course on data structures and algorithms for undergraduates may be based on Chapters 1 through 4 (skipping most of the starred sections), along with portions of Chapter 5 (algorithm design), the first half of Chapter 6 (hashing), the first half of Chapter 12 (graphs), and possibly an overview of Chapter 13 (parallel models of computation). Although Chapters 1 through 4 cover more elementary material, and at a slower pace, the concise style of this book makes it important that the instructor provide motivation, discuss sample exercises, and assign homework to complement lectures. For upper class undergraduates or first-year graduate students who have already had a course on elementary data structures, Chapters 1 through 4 can be quickly reviewed and the course can essentially start with the algorithm design techniques of Chapter 5. There is no chapter on sorting. Instead, sorting is used in many examples, which include bubble sort, merge sort, tree sort, heap sort, quick sort, and several parallel sorting algorithms. Lower bounds on sorting by comparisons are included in the chapter on heaps, in the context of lower bounds for comparison based structures. There is no chapter on NP-completeness (although a section of the chapter on graph algorithms does overview the notion). Formal treatment of complexity issues like this is left to a course on the theory of computation. Although traditional serial algorithms are taught, the last chapter presents the PRAM model for parallel computation, discusses PRAM simulation, considers how the EREW PRAM, HC/CCClButterfiy, and mesh models can be used for PRAM simulation, and concludes with a discussion of hardware area-time tradeoffs as a way of comparing the relative merits of simulation models. Although it is not clear what parallel computing models will prevail in practice in the future, the basic concepts presented in the chapter can provide a foundation for further study on specific practical architectures. Also, from the point of view of studying algorithms, it is instructive to see how basic principles taught in the previous chapters can be adapted to other models. Acknowledgements Many people provided helpful comments during the writing of this book. In particular I would like to thank (in alphabetical order): R. Alterman, B. Carpentieri, 1 Chemiavsky, M. Cohn, I. Gessel, A. Kostant, G. Motta, T. Hickey, 1 Reif, F. Rizzo, 1 E. Storer, and I. Witten. lA.S.2001 Contents Preface ..................................................................................................................... v Acknowledgements .................................................................................................. vi 1. It)l~ ~oclel •••••••••...•••...•••...•••...•••..•.•.••.•••.••. ••.••...•. 1 Introduction ................................................................................................... 1 Pseudo-Code .................................................................................................. 4 Example: n! - Pseudo-Code Versus Machine Code ............................. 5 Motivation for Asymptotic Time Complexity ................................................... 6 Analyzing Algorithms with Asymptotic Notation ............................................. 7 The 0 Notation .................................................................................. 7 Example: Bubble Sort ......................................................................... 8 Example: Run-Length Codes ............................................................... 9 Example: Horner's Method for Polynomial Evaluation ....................... 10 Example: Matrix Multiplication ........................................................ 11 Example: Pascal's Triangle of Binomial Coefficients .......................... 12 (*) Example: Solving Sets of Linear Equations ................................... 14 (*) Example: Lagrange Interpolation of Polynomials .......................... 16 Logarithms and Exponentials ........................................................................ 19 (*) Non-Integer Logarithms and Exponentials .................................... 20 Logarithms and Exponentials Versus Polynomials .............................. 21 Example: Binary Search ................................................................... 22 Example: Binary Numbers ................................................................ 23 (*) Representing Arrays ................................................................................ 24 The Significance of Asymptotic Complexity .................................................. 25 Basic Approach to Algorithm Design ............................................................. 26 Sample Exercises ......................................................................................... 27 Exercises ................................... , ................................................................. 42 Chapter Notes .............................................................................................. 54 2. Lists ................................................................... 59 Introduction ................................................................................................. 59 Array Implementation of Stacks .................................................................... 61 Example: Using a Stack to Reverse an Array ...................................... 62 (*) Example: Evaluating a Postfix Expression with a Stack ................. 63 Array Implementation of Queues ("Circular Queues") .................................... 64 Example: Using a Queue to Separate an Array ................................... 65 General Purpose Lists ................................................................................... 66 Example: Using the Basic List Operations .......................................... 67 Representing Lists With Pointers ................................................................... 68 Pointer Variables .............................................................................. 69 (*) Implementing Pointers ................................................................. 70 Implementation of the Basic List Operations in 0(1) Time .............................. 71 Example: Details of the INSERT Operation ....................................... 72 Example: Details ofthe DELETE Operation ...................................... 73 Example: Reversing a Singly Linked List.. ......................................... 74 (*) Example: The POP(i) Stack Operation .......................................... 75 Sample Exercises ......................................................................................... 76 Exercises ..................................................................................................... 81 Chapter Notes .............................................................................................. 85 3. Induction and Recursion ........................................... 87 Introduction ................................................................................................. 87 Example: Binary Search ................................................................... 89 Example: Traversing Linked Lists ..................................................... 90 Example: Fast Computation of Integer Exponents ............................... 91 (*) Example: Converting a String to a Number ................................... 92 (*) Example: Evaluating a Prefix Expression ...................................... 93 (*) Example: Converting Infix to Prefix or Postfix .............................. 94 Proof by Induction ........................................................................................ 95 Example: Summing Powers of 2 ........................................................ 95 Example: Summing Odd Integers ...................................................... 96 Example: Correctness of Binary Search ............................................. 97 Example: Towers of Hanoi Puzzle ..................................................... 98 Elimination of Recursion .............................................................................. 99 Example: Eliminating Recursion from n! ......................................... 100 Example: Complexity of Recursive n! ............................................. 101 Example: Eliminating Recursion from Towers of Hanoi ................... 102 Example: Complexity of TOWER ................................................... 103 Example: Non-Recursive Towers of Hanoi Algorithm ...................... 104 Sample Exercises ....................................................................................... 105 Exercises ................................................................................................... 117 Chapter Notes ............................................................................................ 125 viii CONTENTS 4. Trees ................................................................. 127 Introduction ............................................................................................... 127 Tree Terms ................................................................................................ 128 Representing Trees ..................................................................................... 129 Pre-Order Traversal. ................................................................................... 130 Example: Height of a Vertex v ........................................................ 130 Level-Order Traversal ................................................................................ 131 Example: MIN-HEIGHT of a Vertex v ............................................ 131 Binary Search Trees ................................................................................... 132 Basic Binary Search Tree Operations ............................................... 133 Details of the DELETEMIN Operation ............................................ 134 Example: Some Sample Binary Search Tree Manipulations............... 135 In-Order Traversal of a Binary Search Tree ...................................... 136 Example: Evaluating An Arithmetic Expression ............................... 137 (*) Joining and Splitting Binary Search Trees ................................... 138 Indexing a Binary Search Tree ........................................................ 140 (*) Binary Search Tree Ordering Lemma ......................................... 141 (*) Average Time to Build a Binary Search Tree .............................. 142 The Rotation Operation for Binary Search Trees .......................................... 144 Self-Adjusting Binary Search Trees ............................................................. 146 (*) Amortized Complexity of Self-Adjusting Binary Search Trees ..... 148 Example: Tree Sort......................................................................... 149 Joining and Splitting Self-Adjusting Binary Search Trees ................. 150 Sample Exercises ....................................................................................... 151 Exercises ................................................................................................... 156 Chapter Notes ............................................................................................ 160 5. Algorithm Design ................................................... 161 Introduction ............................................................................................... 161 Divide and Conquer.................................................................................... 163 Example: Merge Sort ...................................................................... 164 Example: Quick Sort ...................................................................... 166 Example: Finding the /(h Largest Element ........................................ 167 Example: Polynomial Multiplication................................................ 168 Example: Strassen's Algorithm for Matrix Multiplication .................. 169 Divide and Conquer Recurrence Relations ................................................... 170 Dynamic Programming ............................................................................... 171 Example: The Knapsack Problem .................................................... 171 CONTENTS ix Example: The Paragraphing Problem ............................................... 172 Example: Optimal Ordering of Matrix Multiplications ...................... 173 Example: Context-Free Language Recognition ................................. 174 Dynamic Programming Sums ...................................................................... 175 Randomized Algorithms ............................................................................. 176 Example: Statistical Sampling ......................................................... 176 Example: Randomized Quick Sort ................................................... 177 Example: Randomized kth Largest Element.. ..................................... 178 Greedy Algorithms ..................................................................................... 180 Example: Bin Packing .................................................................... 180 Example: HuffInan Trees ................................................................ 181 Example: Shortest Common Superstrings ......................................... 182 Simulated Annealing .................................................................................. 183 Exercises ................................................................................................... 184 Chapter Notes ............................................................................................ 197 6. Hashing ....................................................................................................... 203 Introduction ............................................................................................... 203 Basic Hashing Algorithm ............................................................................ 204 Hash Functions for Data Items with Many Bits ............................................. 205 Complexity of Hashing ............................................................................... 206 The Constant e ........................................................................................... 207 Expected Number of Empty Buckets ........................................................... 208 Chernoff Bound ......................................................................................... 209 Size of the Largest Bucket .......................................................................... 210 Overfilling a Hash Table ............................................................................. 212 Resizing a Hash Table ................................................................................ 213 Universal Hashing ...................................................................................... 214 Twin Hashing ............................................................................................ 215 Bloom Filters ............................................................................................. 216 Exercises ................................................................................................... 217 Chapter Notes ............................................................................................ 221 x CONTENTS 7. Heaps ................................................................ 223 Introduction ............................................................................................... 223 Complete k-ary Trees ................................................................................. 224 Full k-ary Trees .......................................................................................... 225 Heap Implementation with Full Trees .......................................................... 226 Building a Heap in Linear Time .................................................................. 227 Heap Sort. .................................................................................................. 228 Implementing Heaps with Pointers .............................................................. 229 Lower Bounds on Heap Operations and Sorting ........................................... 230 Exercises ................................................................................................... 232 Chapter Notes ............................................................................................ 236 8. Balanced Trees ..................................................... 237 Introduction ............................................................................................... 237 2-3 Trees ................................................................................................... 238 Inserting into a 2-3 Tree .................................................................. 239 Deleting from a 2-3 Tree ................................................................. 241 Joining 2-3 Trees ............................................................................ 244 Splitting 2-3 Trees .......................................................................... 246 Red-Black Trees ......................................................................................... 248 Properties of Red-Black Trees ......................................................... 249 Equivalence of Red-Black and 2-3 Trees .......................................... 250 Example: Red-Black Tree Insertion Algorithm ................................. 251 Example: Inserting into a Red-Black Tree in Sorted Order ................ 252 Height of a Red-Black Tree ............................................................. 253 AVL Trees ................................................................................................. 254 The AVL Algorithm ....................................................................... 255 Height of an AVL Tree ................................................................... 256 Storing Data Only in the Leaves .................................................................. 258 Exercises ................................................................................................... 259 Chapter Notes ............................................................................................ 267 9. Sets Over a Small Universe ....................................... 269 Introduction ............................................................................................... 269 On the Fly Array Initialization..................................................................... 271 In-Place Permutation .................................................................................. 272 CONTENTS Xl Bucket Sorting ........................................................................................... 273 Bit-Vector Representation of Sets ................................................................ 274 Union-Find Problem ................................................................................... 275 Linked List Implementation of Union-Find ...................................... 276 Tree Implementation of Union-Find ................................................ 277 Tree Implementation of Union-Find with Path Compression ............. 278 Example: Off-Line Processing of Heap Operations ........................... 280 Other Operations that can be Added to Union-Find ........................... 281 Exercises ................................................................................................... 282 Chapter Notes ............................................................................................ 288 10. Graphs ............................................................. 289 Introduction ............................................................................................... 289 Graph Terms .............................................................................................. 290 Representing Graphs .................................................................................. 291 Depth-First Search...................................................................................... 292 Breadth-First Search ................................................................................... 293 Depth-First Spanning Trees ......................................................................... 294 Bi-Connected and Strongly-Connected Components ..................................... 295 Bi-Connected Components of an Undirected Graph .......................... 296 Strongly-Connected Components of a Directed Graph ...................... 297 Minimum Weight Spanning Trees ............................................................... 298 Proof of Correctness of Prim and Kruskal Algorithms ....................... 298 Implementation of Prim's Algorithm ................................................ 299 Implementation of Kruskal's Algorithm ........................................... 300 Topological Sort of a Directed Graph .......................................................... 301 Euler Paths ................................................................................................. 302 Single-Source Minimum Cost Paths ............................................................ 303 Dijkstra's Algorithm ....................................................................... 303 Adjacency Matrix Implementation of Dijkstra's Algorithm ................ 304 Adjacency List Implementation of Dijkstra's Algorithm .................... 304 All Pairs Minimum Cost Paths .................................................................... 305 Floyd's Algorithm for Shortest Paths................................................ 305 Warshall's Algorithm for Transitive Closure..................................... 306 Generic Path Finding Framework .................................................... 307 Maximum Flow.......................................................................................... 308 Undirected Paths ............................................................................ 309 xii CONTENTS Augmenting Paths .......................................................................... 309 Augmenting Path Theorem for Flow ................................................ 309 Max-Flow = Min-Cut Theorem ....................................................... 309 Generic Approach to Computing Maximum Flow ............................. 310 Edmonds-Karp Algorithm .............................................................. 311 The Residual and Level Graphs ....................................................... 313 Blocking Flows .............................................................................. 314 Dinic's Algorithm ........................................................................... 314 MKM Algorithm ............................................................................ 315 Bounded Flow ................................................................................ 316 Maximum Matching ................................................................................... 318 Augmenting Path Theorem for Matching ......................................... 318 Matching in Bipartite Graphs .......................................................... 319 Matching in Undirected Graphs ....................................................... 321 Stable Marriage .......................................................................................... 324 NP-Complete Graph Problems .................................................................... 325 Polynomial-Time Reductions .......................................................... 326 NP-Complete Problems .................................................................. 326 The Class NP ................................................................................. 326 The "first" NP-Complete Problem ................................................... 327 The "second" NP-Complete Problem ............................................... 327 Dealing with NP-Complete Graph Problems .................................... 328 Exercises ................................................................................................... 329 Chapter Notes ............................................................................................ 348 11. Strings .............................................................. 355 Introduction ............................................................................................... 355 Lexicographic Sorting of Strings ................................................................. 357 Knuth-Morris-Pratt (KMP) String Matching ............................................... 358 KMP Algorithm Using Back-Up Links ............................................ 358 Back-Up Diagrams ......................................................................... 359 Efficient Computation ofthe KMP Back-Up Array ........................... 360 Converting the KMP Back-Up Array to Direct Links ........................ 361 KMP Algorithm Using Direct Links ................................................ 361 Reducing the Space for the KMP Direct Array ................................. 362 Boyer-Moore String Matching .................................................................... 363 Karp-Rabin Randomized "Finger Print" String Matching .............................. 364 Shift-And String Matching .......................................................................... 365 Shift-and with don't-care positions ................................................... 365 Shift-And with Anything-But Positions ............................................ 366 CONTENTS xiii Shift-And with Minimum Mis-Matches ........................................... 368 Shift-And with Character Mapping .................................................. 369 Shift-And with Character Bit-Vectors .............................................. 370 Comparison of String Matching Methods ..................................................... 373 Pattern Matching ........................................................................................ 374 Pattern Diagrams ............................................................................ 375 McNaughton-Yamada Algorithm .................................................... 376 Matching with Pattern Diagrams ..................................................... 378 Tries .......................................................................................................... 379 Example: Sorting Strings with Tries ................................................ 379 Example: Aho-Corasick Multiple String Matching ........................... 380 Example: Prefix and Huffman Codes ............................................... 381 Example: Data Compression using a Dynamic Dictionary ................. 382 Compact Tries ............................................................................................ 384 Suffix Tries ................................................................................................ 385 Example Applications of Suffix Tries .............................................. 385 Simple Suffix Trie Construction Algorithm ...................................... 386 McCreight's Linear Time Suffix Trie Construction ........................... 387 Example: Brute-Force Versus McCreight on an$ .............................. 389 Sliding Suffix Tries .................................................................................... 390 Sliding Window With Two McCreight Tries .................................... 391 Fiala-Greene Sliding Suffix Trie Algorithm ..................................... 392 Example: Data Compression using a Sliding Window ....................... 394 Edit Distance: A Measure of String Similarity .............................................. 395 Example: Longest Common Sub-Sequence ...................................... 396 Arithmetic Codes ....................................................................................... 397 Conceptual Arithmetic Encoding / Decoding Algorithm .................... 398 Defining The End of a Finite String ................................................. 399 Example ........................................................................................ 400 On-Line Encoding and Decoding ..................................................... 402 Practical Considerations .................................................................. 402 The Burrows-Wheeler Transform ............................................................... 403 Inverse BWT Using Only Two Passes ............................................. 404 Example: MTF Data Compression ................................................... 405 Exercises ................................................................................................... 407 Chapter Notes ............................................................................................ 414 XIV CONTENTS 12. Discrete Fourier Transform ..................................... 421 Introduction ............................................................................................... 421 Complex Numbers ...................................................................................... 422 Complex Exponentials ................................................................................ 423 Principal nth Roots of Unity ......................................................................... 424 Definition of the DFT ................................................................................. 425 F and G are Inverse Functions ..................................................................... 426 Similarity of F and G.................................................................................. 426 Examples ................................................................................................... 427 How to Split F into Two Computations of Half the Size ................................ 431 Divide and Conquer "Butterfly" .................................................................. 432 Recursive FFT Algorithm ........................................................................... 433 In-Place Bit Reversal .................................................................................. 434 Recursive In-Place FFT Algorithm .............................................................. 435 Non-Recursive In-Place FFT Algorithm....................................................... 436 Simplified Non-Recursive In-Place FFT Algorithm ...................................... 437 DFT over Finite Fields on an Array of Integers ............................................ 439 Example: Fast Convolutions with the DFT ................................................... 440 DFT On Two Arrays of Reals ..................................................................... 441 DFT On A Single Array of Reals ................................................................. 442 Inverse DFT for Reals ................................................................................ 443 Discrete Cosine Transform.......................................................................... 444 C and D are Inverse Functions ..................................................................... 445 DCT Basis Functions .................................................................................. 446 Relationship of the DCT to the DFT ............................................................ 447 Computing the DCT in O(nlog(n)) Time ..................................................... 448 Computing the Inverse DCT in O(nlog(n)) Time .......................................... 449 Two Dimensional DFT and DCT ................................................................. 451 Example: JPEG Image Compression ............................................................ 452 Example: MPEG Video Compression .......................................................... 453 Exercises ................................................................................................... 454 Chapter Notes: ........................................................................................... 467 CONTENTS xv 13. Parallel Computation ............................................. 471 Introduction ............................................................................................... 471 Example: Summing an Array .......................................................... 478 Example: List Prefix-Sum / List Ranking ......................................... 479 Example: List Prefix-Sum on a Binary Tree ..................................... 480 Example: 0(1) CRCW Array Max with 0(n2) Processors .................. 482 Example: O(loglog(n)) CRCW Array Max with O(n) Processors ....... 483 Example: Matrix Multiplication ...................................................... 484 Example: Merge Sort.. .................................................................... 485 Example: Quick Sort ...................................................................... 486 Brent's Lemma ........................................................................................... 487 PRAM Simulation ...................................................................................... 488 EREW PRAM MODEL .............................................................................. 489 Example: Broadcast on an EREW PRAM ........................................ 489 Example: Sum on an EREW PRAM ................................................ 489 Example: Matrix Multiplication on an EREW PRAM ....................... 490 Data Distribution on an EREW PRAM ............................................ 491 Sorting on an EREW PRAM ........................................................... 492 Hypercube / CCC / Butterfly Networks ........................................................ 496 Hypercube (HC) ............................................................................. 496 Cube Connected Cycles (CCC) ....................................................... 496 Butterfly (BF) ................................................................................ 497 Equivalence ofthe CCC and Butterfly Networks .............................. 498 Example: Broadcast and Sum on a Butterfly ..................................... 499 Example: Prefix-Sum on a Butterfly ................................................ 500 Example: Matrix Multiplication on a Butterfly ................................. 501 Data Distribution on a Butterfly ...................................................... 502 Sorting on a Butterfly ..................................................................... 504 1-1 Packet Routing on a Butterfly .................................................... 506 Mesh Network ........................................................................................... 507 Example: Broadcast on a Mesh ........................................................ 508 Example: Sum on a Mesh ............................................................... 508 Example: Prefix-Sum on a Mesh ..................................................... 509 Example: Matrix Multiplication on a Mesh ...................................... 510 Data Distribution on a Mesh ............................................................ 512 Sorting on a Mesh .......................................................................... 513 1-1 Packet Routing on a Mesh ......................................................... 514 Area-Time Tradeoffs .................................................................................. 515 Computer Chips ............................................................................. 515 Boolean Functions .......................................................................... 515 Example: cMOS ............................................................................. 516 xvi CONTENTS Example: nMOS ............................................................................. 517 Constructing Memory With Chips ................................................... 518 Computing with Chips .................................................................... 520 Parallel Hardware Layout ............................................................... 521 Area-Time Tradeoff for Sorting....................................................... 522 Sorting Area-Time Tradeoff vs. PRAM Simulation .......................... 524 Generalizations ofthe Sorting Area-Time Tradeoff........................... 524 Exercises ................................................................................................... 525 Chapter Notes ............................................................................................ 540 Appendix: Common SumS ........................................... 543 A. Approximating Sums with Integrals ........................................................ 543 B. Arithmetic Sum...................................................................................... 545 C. Simple Geometric Sum (unweighted, k=O)............................................... 546 D. Linear Weighted Geometric Sum (k= 1) ................................................... 547 E. Quadratic Weighted Geometric Sum (k=2) .............................................. 548 F. Cubic Weighted Geometric Sum (k=3) .................................................... 549 G. Weighted Geometric Sum (for any non-negative integer k) ....................... 550 I. Harmonic Sum ........................................................................................ 553 1. Sums of Inverse Powers ........................................................................... 554 Bibliography ........................................................... 555 Notation ................................................................ 583 Index .................................................................... 585 CONTENTS xvii 1. RAM Model Introduction Efficient data structures and algorithms can be the key to designing practical programs. Most of this book addresses the traditional model of a computer as pictured below; some memory together with a single processor that can perform basic arithmetic operations (e.g., add, subtract, multiply, divide), make logical tests (e.g., test if a value is less than zero), and follow flow of control accordingly (e.g., goto instructions). The processor may include a few special registers that can be manipulated faster than normal memory, but the bulk of memory is uniform in the sense that access to all locations of memory is equally fast, from which comes the name Random Access Memory (RAM). Of course, computers in practice are much more complicated, with cache memory, secondary storage, mUltiple processors, etc. However, design methodology based on the RAM model has traditionally served well in more complex models. ;r~4()~ c8;cc~§~~ m~mQ~ . ~:. :,: :<:'. ":': A key simplifying assumption is that operations are unit-cost. Each basic instruction takes one "unit" of time, and we count the number of basic instructions executed to measure time. Furthermore, the size of a number in an operation is not taken into account. For example, it is one time unit to add two numbers, independent of their size. Although these assumptions are not true in practice, if we do not "abuse" the unit-cost RAM model, our designs will be sound and provide the basis for practical algorithms on a variety of architectures. For example, if we have enough memory in practice to store n integers, then it is reasonable to assume that basic machine instructions can manipulate integers in the range 0 to n. On the other hand, consider the following program that repeatedly multiplies by 10: 1. Set the variable x equal to 10. 2. Repeat for n steps the operation of mUltiplying x by 10. Since each multiplication adds another digit to x, this program computes a value with over n digits. When n is large, it may not be realistic to assume that numbers of n digits J. A. Storer, An Introduction to Data Structures and Algorithms © J.A. Storer 2002 can be stored in a single machine register and multiplied with a single machine instruction. A more "dramatic" example repeatedly squares a value: 1. Set the variable x equal to 10. 2. Repeat for n steps the operation of multiplying the variable x times itself. Since each multiplication in this program about doubles the number of base 10 digits to represent x (i.e., x is a 1 followed by a number of O's that doubles with each multiplication), this program computes a value with roughly 2n digits. For example, even when n is only 25, this is more than 30 million digits. It is possible to strengthen the RAM model by charging a cost per operation that depends on the size of the numbers involved. However, the extra complication is really not necessary if we are willing to exercise good judgement to understand when it would not be practical to manipulate in a fixed time unit numbers that are involved in an algorithm. The only data structure that we consider to be part of the basic RAM model is the standard one dimensional array, or equivalently the ability to perform indirect addressing. For a fixed integer x, not only are there machine instructions to read or write to memory location x, but we can also read or write to memory location y, where y is the value stored in memory location x. Indirect addressing corresponds exactly to the notion of a one dimensional array. For example, setting a variable x to the value of A[i] does not place the contents of the memory location i into x, but rather, it copies the contents of a memory location that is determined by the value of i. In fact, we shall see how indirect addressing can be used to implement arrays of any dimension. In practice, one generally avoids the complexity and tedium of programs written directly with machine instructions and relies on compilers to translate higher level programming languages into "assembly language" that can be more or less directly mapped to the actual machine instructions encoded with O's and 1'so Since we are concerned here only with basic data structures and algorithm design, and not with all of the "messy stuff" that is needed in practice (input-output, graphics, systems calls, file storage, etc.), we express algorithms with simple "pseudo-code" using a mixture of English and constructs that are available, in some form, in most languages (if-then-else, etc.). Hopefully, the syntax of pseudo-code used in this book is self-explanatory to anyone who has had some programming background. The first example of this chapter computes the factorial function; that is, n! is the product of the integers 1 through n (define n !=1 for n - Xem thêm -