CONTENTS
PREFACE = ⅸ
Synopsis = ⅹ
Changes in the Third Edition = xi
Course Structure = xii
Book Production = xiii
Acknowledgments = xiv
CHAPTER 1 Programming Principles = 1
1.1 Introduction = 2
1.2 The Game of Life = 4
1.2.1 Rules for the Game of Life = 4
1.2.2 Examples = 4
1.2.3 The Solution = 6
1.2.4 Life :The Main Program = 7
1.3 Programming Style = 9
1.3.1 Names = 9
1.3.2 Documentation and Format = 11
1.3.3 Refinement and Modularity = 12
1.4 Coding, Testing, and Further Refinement = 17
1.4.1 Stubs = 17
1.4.2 Counting Neighbors = 18
1.4.3 Input and Output = 19
1.4.4 Drivers = 23
1.4.5 Program Tracing = 24
1.4.6 Principles of Program Testing = 25
Pointers and Pitfalls = 29
Review Questions = 31
References for Further Study = 31
Pascal = 31
Programming Principles = 32
The Game of Life = 32
CHAPTER 2 Introduction to Software Engineering = 33
2.1 Program Maintenance = 34
2.1.1 Review of the Life Program = 34
2.1.2 A Fresh Start and a New Method for Life = 36
2.2 Algorithm Development :A Second Version of Life = 39
2.2.1 Lists :Specifications for a Data Structure = 39
2.2.2 The Main Program = 43
2.2.3 Information Hiding = 45
2.2.4 Refinement :Development of the Subprograms = 46
2.2.5 Verification of Algorithms = 49
2.3 Coding = 52
2.3.1 The List Package = 53
2.3.2 Error Processing = 54
2.3.3 Information Hiding = 45
2.4 Coding the Life Procedures = 59
2.5 Program Analysis and Comparison = 62
2.6 Conclusions and Preview = 64
2.6.1 The Game of Life = 64
2.6.2 Program Design = 66
2.6.3 Pascal = 68
Pointers and Pitfalls = 70
Review Questions = 71
References for Further Study = 71
CHAPTER 3 Stacks and Recursion = 73
3.1 Stacks = 74
3.1.1 Introduction = 74
3.1.2 First Example :Reversing a Line = 75
3.1.3 Information Hiding = 76
3.1.4 Specifications for a stack = 77
3.1.5 Implementation of Stacks = 79
3.1.6 Linked Stacks = 81
3.2 Introduction to Recursion = 88
3.2.1 Stack Frames for Subprograms = 88
3.2.2 Tree of Subprogram Calls = 88
3.2.3 Factorials :A Recursive Definition = 90
3.2.4 Divide and Conquer :The Towers of Hanoi = 92
3.3 Principles of Recursion = 98
3.3.1 Designing Recursive Algorithms = 98
3.3.2 How Recursion Works = 99
3.3.4 When Not to Use Recursion = 105
3.3.5 Guidelines and Conclusions = 109
Pointers and Pitfalls = 111
Review Questions = 112
References for Further Study = 113
CHAPTER 4 Examples of Recursion = 114
4.1 Backtracking :Postponing the Work = 115
4.1.1 Solving the Eight-Queens Puzzle = 115
4.1.2 Example :Four Queens = 116
4.1.3 Backtracking = 117
4.1.4 Refinement :Choosing the Data Structures = 117
4.1.5 Analysis of Backtracking = 121
4.2 Tree-Structured Programs :Look-Ahead in Games = 12
4.2.1 Game Tree = 123
4.2.2 The Minimax Method = 124
4.2.3 Algorithm Development = 125
4.2.4 Refinement = 127
4.3 Compilation by Recursive Descent = 129
4.3.1 The Main Program = 129
4.3.2 Type Declarations = 131
4.3.3 Parsing Statements = 131
4.3.4 A Pascal Statement Parser = 135
Pointers and Pitfalls = 147
Review Questions = 147
References for Further Study = 148
CHAPTER 5 Queues = 149
5.1 Definitions = 150
5.2 Implementations of Queues = 153
5.3 Circular Queues in Pascal = 157
5.4 Application of Queues :Simulation = 162
5.4.1 Introduction = 162
5.4.2 Simulation of an Airport = 162
5.4.3 Random Numbers = 164
5.4.4 The Main Program = 164
5.4.5 Steps of the Simulation = 166
5.4.6 Sample Results = 168
5.5 Linked Queues = 171
5.6 Application :Polynomial Arithmetic = 176
5.6.1 Purpose of the Project = 176
5.6.2 The Main Program = 176
5.6.3 Data Structures and Their Implementation = 179
5.6.4 Reading and Writing Polynomials = 181
5.6.5 Addition of Polynomials = 183
5.6.6 Completing the Project = 185
5.7 Abstract Data Types and Their Implementations = 187
5.7.1 Introduction = 187
5.7.2 General Definitions = 187
5.7.3 Refinement of Data Specification = 191
Pointer and Pitfalls = 193
Review Questions = 194
References for Further Study = 194
CHAPTER 6 Lists = 195
6.1 List Specifications = 196
6.2 Implementation of Lists = 198
6.2.1 Contiguous Implementation = 198
6.2.2 Simply Linked Implementation = 199
6.2.3 Variation :Keeping the Current Position = 203
6.2.4 Doubly Linked Lists = 204
6.2.5 Comparison of Implementations = 207
6.3 Strings = 210
6.3.1 String Operations = 210
6.3.2 Implementation of Strings = 211
6.4 Application :A Text Editor = 216
6.4.1 Specifications = 216
6.4.2 Implementation = 217
6.5 Linked Lists in Arrays = 224
6.6 Generating Permutations = 233
Pointer and Pitfalls = 238
Review Questions = 239
References for Further Study = 240
CHAPTER 7 Searching = 241
7.1 Searching :Introduction and Notation = 242
7.2 Sequential Search = 243
7.3 Coatrooms :A Project = 249
7.3.1 Introduction and Specification = 249
7.3.2 Demonstration and Testing Programs = 252
7.4 Binary Search = 255
7.4.1 Algorithm Development = 257
7.4.2 The Forgetful Version = 257
7.4.3 Recognizing Equality = 259
7.5 Comparison Trees = 262
7.5.1 Analysis for n^ = 263
7.5.2 Generalization = 266
7.5.3 Comparison of Methods = 268
7.5.4 A General Relationship = 269
7.6 Lower Bounds = 272
7.7 Asymptotics = 276
7.7.1 Introduction = 276
7.7.2 The Big Oh Notation = 277
7.7.3 Imprecision of the Big Oh Notation = 280
7.7.4 Ordering of Common Functions = 281
Pointers and Pitfalls = 282
Review Questions = 283
References for Further Study = 283
CHAPTER 8 Sorting = 285
8.1 Introduction and Notation = 286
8.2 Insertion Sort = 287
8.2.1 Ordered Lists = 287
8.2.2 Sorting by Insertion = 288
8.2.3 Linked Version = 290
8.2.4 Analysis = 291
8.3 Selection Sort = 296
8.3.1 The Algorithm = 296
8.3.2 Contiguous Implementation = 297
8.3.3 Analysis = 298
8.3.4 Comparisons = 299
8.4 Shell Sort = 300
8.5 Lower Bounds = 302
8.6 Divide-and-Conquer Sorting = 305
8.6.1 The Main Ideas = 305
8.6.2 An Example = 306
8.7 Mergesort for Linked Lists = 311
8.7.1 The Procedures = 311
8.7.2 Analysis of Mergesort = 313
8.8 Quicksort for Contiguous Lists = 318
8.8.1 The Main Procedure = 318
8.8.2 Partitioning the List = 319
8.8.3 Analysis of Quicksort = 321
8.8.4 Average-Case Analysis of Quicksort = 323
8.8.5 Comparison with Mergesort = 325
8.9 Heaps and Heapsort = 328
8.9.1 Two-Way Trees as Lists = 329
8.9.2 Heapsort = 330
8.9.3 Analysis of Heapsort = 333
8.9.4 Priority Queues = 334
8.10 Review :Comparison of Methods = 337
Pointers and Pitfalls = 340
Review Questions = 341
References for Further Study = 341
CHAPTER 9 Tables and Information Retrieval = 343
9.1 Introduction :Breaking the lg n Barrier = 344
9.2 Rectangular Arrays = 344
9.3 Tables of Various Shapes = 347
9.3.1 Triangular Tables = 347
9.3.2 Jagged Tables = 349
9.3.3 Inverted Tables = 349
9.4 Tables :A New Abstract Data Type = 352
9.5 Application :Radix Sort = 355
9.5.1 The Idea = 355
9.5.2 Implementation = 356
9.5.3 Analysis = 359
9.6 Hashing = 360
9.6.1 Sparse Tables = 360
9.6.2 Choosing a Hash Function = 362
9.6.3 Collision Resolution with Open Addressing = 364
9.6.4 Collision Resolution by Chaining = 368
9.7 Analysis of Hashing = 373
9.8 Conclusions :Comparison of Methods 379
9.9 Application :The Life Game Revisited = 379
9.9.1 Choice of Algorithm = 380
9.9.2 Specification of Data Structures = 380
9.9.3 The Main Program = 381
9.9.4 Procedures = 383
Pointers and Pitfalls = 386
Review Questions = 387
References for Further Study = 338
CHAPTER 10 Binary Trees = 389
10.1 Binary Trees = 390
10.1.1 Definitions = 390
10.1.2 Traversal of Binary Tree = 392
10.1.3 Linked Implementation of Binary Trees = 397
10.2 Binary Search Trees = 402
10.2.1 Ordered Lists and Implementations = 403
10.2.2 Treesearch = 404
10.2.3 Insertion into a Binary Search Tree = 407
10.2.4 Treesort = 410
10.2.5 Deletion from a Binary Search Tree = 411
10.3 Building a Binary Search Tree = 419
10.3.1 Getting Started = 420
10.3.2 Declarations and the Main Procedure = 421
10.3.3 Inserting a Node = 422
10.3.4 Finishing the Task = 423
10.3.5 Evaluation = 424
10.3.6 Random Search Trees and Optimality = 425
10.4 Height Balance :AVL Trees = 427
10.4.1 Definition = 428
10.4.2 Insertion of a Node = 429
10.4.3 Deletion of a Node = 435
10.4.4 The Height of an AVL Tree = 437
10.5 Splay Trees :A Self-Adjusting Data Structure = 441
10.5.1 Introduction = 441
10.5.2 Splaying Steps = 442
10.5.3 Splaying Algorithm = 445
10.5.4 Amortized Algorithm Analysis :Introduction = 449
10.5.5 Amortized Analysis of Splaying = 452
Pointers and Pitfalls = 458
Review Questions = 459
References for Further Study = 460
CHAPTER 11 Multiway Trees = 462
11.1 Orchards, Trees, and Binary Trees = 463
11.1.1 On the Classification of Species = 463
11.1.2 Ordered Trees = 464
11.1.3 Forests and Orchards = 466
11.1.4 The Formal Correspondence = 467
11.1.5 Rotations = 468
11.1.6 Summary = 468
11.2 Lexicographic Search Trees :Tries = 471
11.2.1 Tries = 471
11.2.2 Searching for a Key = 471
11.2.3 Pascal Algorithm = 472
11.2.4 Insertion into a Trie = 473
11.2.5 Deletion from a Trie = 474
11.2.6 Assessment of Trie = 475
11.3 Extemal Searching :B-Tree = 476
11.3.1 Access Time = 476
11.3.2 Multiway Search Tree = 476
11.3.3 Balanced Multiway Trees = 476
11.3.4 Insertion into a B-tree = 477
11.3.5 Pascal Algorithms :Searching and Insertion = 479
11.3.6 Deletion from a B-tree = 486
11.4 Red-Black Trees = 494
11.4.1 Introduction = 494
11.4.2 Definition and Insertion = 479
11.4.3 Insertion = 497
11.4.4 Pascal Insertion = 499
Pointers and Pitfalls = 502
Review Questions = 503
References for Further Study = 503
CHAPTER 12 Graphs = 505
12.1 Mathematical Background = 506
12.1.1 Definitions and Examples = 506
12.1.2 Undirected Graphs = 507
12.1.3 Directed Graphs = 507
12.2 Computer Representation = 508
12.3 Graph Traversal = 513
12.3.1 Methods = 513
12.3.2 Depth-First Algorithm = 513
12.3.3 Breadth-First Algorithm = 515
12.4 Topological Sorting = 516
12.4.1 The Problem = 516
12.4.2 Depth-First Algorithm = 517
12.4.3 Breadth-First Algorithm = 518
12.5 A Greedy Algorithm :Shortest Paths = 520
12.6 Graphs as Data Structures = 525
Pointers and Pitfalls = 525
Review Questions = 527
References for Further Study = 528
CHAPTER 13 Case Study :The Polish Notation = 529
13.1 The Problem = 530
13.1.1 The Quadratic Formula = 530
13.2 The Idea = 532
13.2.1 Expression Trees = 532
13.2.2 Polish Notation = 534
13.2.3 Pascal Method = 535
13.3 Evaluation of Polish Expressions = 535
13.3.1 Evaluation of an Expression in Prefix Form = 535
13.3.2 Pascal Conventions = 536
13.3.3 Pascal Procedure for Prefix Evaluation = 537
13.3.4 Evaluation of Postfix Expressions = 538
13.3.5 Proof of the Program :Counting Stack Entries = 539
13.3.6 Recursive Evaluation of Postfix Expressions = 542
13.4 Translation from Infix Form to Polish From = 546
13.5 An Interactive Expression Evaluator = 552
13.5.1 Overall Structure = 552
13.5.2 Representation of the Data = 554
13.5.3 Initialization and Auxiliary Tasks = 557
13.5.4 Translation of the Expression = 571
13.5.5 Evaluating the Expression = 571
13.5.6 Graphing the Expression = 573
References for Further Study = 576
APPENDIX A Mathematical Methods = 577
A.1 Sums of Powers of Integers = 578
A.2 Logarithms = 580
A.2.1 Definition of Logarithms = 581
A.2.2 Simple Properties = 581
A.2.3 Choice of Base = 582
A.2.4 Natural Logarithms = 582
A.2.5 Notation = 583
A.2.6 Change of Base = 584
A.2.7 Logarithmic Graphs = 584
A.2.8 Harmonic Numbers = 586
A.3 Permutations, Combinations, Factorials = 587
A.3.1 Permutations = 587
A.3.2 Combinations = 587
A.3.3 Factorials = 588
A.4 Fibonacci Numbers = 589
A.5 Catalan Numbers = 591
A.5.1 The Main Result = 591
A.5.2 The Poof by One-to-One Correspondences = 591
A.5.3 History = 594
A.5.4 Numerical Results = 594
References for Further Study = 595
APPENDIX B Random Numbers = 597
B.1 Introduction = 598
B.2 Method = 598
B.3 Program Development References for Further Study = 599
APPENDIX C Units, Include Files, and Utility Procedures = 604
C.1 Turbo Pascal Units = 605
C.1.1 Introduction = 605
C.1.2 Syntax for Units = 605
C.2 Include Files = 607
C.2.1 Changing Units to Include Files = 607
C.2.2 Generics = 608
C.3 Units in the Text = 610
C.3.1 Data Structures = 610
C.3.2 The Utility Unit = 611
C.3.3 Unit for Timing Programs = 613
C.3.4 File Processing Unit = 615
C.3.5 Random Number Unit = 618
C.4 Programs for Searching and Sorting = 618
C.4.1 Demonstration Program = 618
C.4.2 Creating Data Files for Testing = 618
APPENDIX D Pascal Features = 626
D.1 Pascal Records = 627
D.2 Procedures = 632
D.2.1 Procedures as parameters = 632
D.2.2 Forward Declarations = 634
D.3 Pointers and Linked Lists = 634
D.3.1 Introduction and Survey = 634
D.3.2 Pointers and Dynamic Memory in Pascal = 637
D.3.3 The Basics of Linked Lists = 641
D.3.4 Linked Implementation of Simple Lists = 645
D.3.5 Programming Hints = 647
D.4 Syntax Diagrams = 650
D.5 General Rules = 661
D.5.1 Identifiers = 661
D.5.2 Rules for Spaces = 662
D.5.3 Guidelines Used for Program Format = 663
D.5.4 Punctuation = 663
D.5.5 Alternative Symbols = 664
D.6 Standard Declarations = 664
D.6.1 Constants = 664
D.6.2 Types = 666
D.6.3 Variables = 666
D.6.4 Procedures = 667
D.6.5 Functions = 667
D.7 Operators = 668
INDEX = 669
