CONTENTS
Preface = xi
Synopsis = xii
Course Structure = xiii
Acknowledgments = xiv
CHAPTER 1 Programming Principles = 1
1.1 Introduction = 2
1.2 The Game of Life = 3
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 = 6
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 = 21
1.4.5 Program Tracing = 22
1.4.6 Principles of Program Testing = 23
Pointers and Pitfalls = 26
Review Questions = 27
References for Further Study = 28
The C Language = 28
Programming Principles = 28
The Game of Life = 29
CHAPTER 2 Introduction to Software Engineering = 30
2.1 Program Maintenance = 31
2.2 Lists in C = 35
2.3 Algorithm Development : A Second Version of Life = 37
2.3.1 The Main Program = 37
2.3.2 Refinement : Development of the Subprograms = 39
2.3.3 Coding the Functions = 40
2.4 Verification of Algorithms = 44
2.4.1 Proving the Program = 44
2.4.2 Invariants and Assertions = 46
2.4.3 Initialization = 47
2.5 Program Analysis and Comparison = 48
2.6 Conclusions and Preview = 51
2.6.1 The Game of Life = 51
2.6.2 Program Design = 53
2.6.3 The C Language = 55
Pointers and Pitfalls = 57
Review Questions = 57
References for Further Study = 58
CHAPTER 3 Lists = 59
3.1 Static and Dynamic Structures = 60
3.2 Stacks = 60
3.2.1 Definition and Operations = 60
3.2.2 Examples = 61
3.2.3 Array Implementation of Stacks = 64
3.3 Queues = 68
3.3.1 Definitions = 68
3.3.2 Implementations of Queues = 69
3.3.3 Circular Queues in C = 72
3.4 Application of Queues : Simulation = 77
3.4.1 Introduction = 77
3.4.2 Simulation of an Airport = 78
3.4.3 The Main Program = 80
3.4.4 Steps of the Simulation = 81
3.4.5 Random Numbers = 84
3.4.6 Sample Results = 85
3.5 Other Lists and their Implementation = 89
Pointers and Pitfalls = 96
Review Questions = 96
Reverences for Further Study = 97
CHAPTER 4 Linked Lists = 98
4.1 Dynamic Memory Allocation and Pointers = 99
4.1.1 The Problem of Overflow = 99
4.1.2 Pointers = 99
4.1.3 Further Remarks = 100
4.1.4 Dynamic Memory Allocation = 101
4.1.5 Pointers and Dynamic Memory in C = 101
4.2 Linked Stacks and Queues = 106
4.2.1 Declarations = 106
4.2.2 Linked Stacks = 107
4.2.3 Linked Queues = 111
4.3 Further Operations on Linked Lists = 114
4.3.1 Algorithms for Simply Linked Lists = 114
4.3.2 Comparison of Implementations = 120
4.3.3 Programming Hints = 121
4.4 Application : Polynomial Arithmetic = 123
4.4.1 Purpose of the Project = 123
4.4.2 The Main Program = 124
4.4.3 Data Structures and Their Implementation = 128
4.4.4 Reading and Writing Polynomials = 130
4.4.5 Addition of Polynomials = 131
4.4.6 Completing the Project = 132
4.5 Linked Listen in Arrays = 135
4.6 Abstract Data Types and Their Implementations = 140
4.6.1 Introduction = 140
4.6.2 General Definitions = 141
4.6.3 Refinement of Data Specification = 143
Pointers and Pitfalls = 145
Review Questions = 146
References for Further Study = 146
CHAPTER 5 Searching = 147
5.1 Searching : Introduction and Notation = 148
5.2 Sequential Search = 151
5.3 Binary Search = 154
5.3.1 The Forgetful Version = 155
5.3.2 Recognizing Equality = 156
5.4 comparison Trees = 157
5.4.1 Analysis for n 〓 10 = 158
5.4.2 Generalization = 161
5.4.3 Comparison of Methods = 164
5.4.4 A General Relationship = 165
5.5 Lower Bounds = 167
5.6 Asymptotics = 171
Pointers and Pitfalls = 175
Review Questions = 176
References for Further Study = 177
CHAPTER 6 Tables and Information Retrieval = 178
6.1 Introduction : Breaking the Ig n Barrier = 179
6.2 Rectangular Arrays = 179
6.3 Tables of Various Shapes = 182
6.3.1 Triangular Tables = 182
6.3.2 Jagged Tables = 184
6.3.3 Inverted Tables = 184
6.4 Tables : A New Abstract Data Type = 187
6.5 Hashing = 189
6.5.1 Sparse Tables = 189
6.5.2 Choosing a Hash Function = 191
6.5.3 Collision Resolution with Open Addressing = 193
6.5.4 Collision Resolution by Chaining = 197
6.6 Analysis of Hashing = 201
6.7 Conclusions : Comparison of Methods = 206
6.8 Application : The Life Game Revisited = 207
6.8.1 Choice of Algorithm = 207
6.8.2 Specification of data Structures = 207
6.8.3 The Main Program = 209
6.8.4 Functions = 210
Pointers and Pitfalls = 213
Review Questions = 214
References for Further Study = 216
CHAPTER 7 Sorting = 216
7.1 Introduction and Notation = 217
7.2 Insertion Sort = 218
7.2.1 Contiguous Version = 219
7.2.2 Linked Version = 220
7.2.3 Analysis = 222
7.3 Selection Sort = 225
7.4 Shell Sort = 228
7.5 Lower Bounds = 230
7.6 Divide and Conquer = 233
7.6.1 The Main Ideas = 233
7.6.2 An Example = 234
7.6.3 Recursion = 237
7.6.4 Tree of Subprogram Calls = 237
7.7 Mergesort for Linked Lists = 240
7.7.1 The Functions = 240
7.7.2 Analysis of Mergesort = 242
7.8 Quicksort for Contiguous Lists = 246
7.8.1 The Main Function = 247
7.8.2 Partitioning the List = 247
7.8.3 Analysis of Quicksort = 249
7.8.4 Average-Case Analysis of Quicksort = 251
7.8.5 Comparison with Mergesort = 253
7.9 Review : Comparison of Methods = 256
Pointers and Pitfalls = 259
Review Questions = 259
References for Further Study = 260
CHAPTER 8 Recursion = 262
8.1 Divide and Conquer = 263
8.1.1 The Towers of Hanoi = 263
8.1.2 The Solution = 264
8.1.3 Refinement = 264
8.1.4 Analysis = 265
8.2 Postponing the Work = 266
8.2.1 Generating Permutations = 266
8.2.2 Backtracking : Nonattacking Queens = 271
8.3 Tree-Structured Programs : Look-Ahead in Games = 278
8.3.1 Game Trees = 278
8.3.2 The Minimax Method = 279
8.3.3 Algorithm Development = 280
8.3.4 Refinement = 281
8.4 Compilation by Recursive Descent = 284
8.5 Principles of Recursion = 288
8.5.1 Guidelines for Using Recursion = 288
8.5.2 How Recursion Works = 288
8.5.3 Tail Recursion = 292
8.5.4 When Not to Use Recursion = 294
8.5.5 Guidelines and Conclusions = 299
Pointers and Pitfalls = 300
Review Questions = 301
References for Further Study = 302
CHAPTER 9 Binary Trees = 304
9.1 Definitions = 305
9.2 Treesearch = 308
9.3 Traversal of Binary Trees = 309
9.4 Treesort = 312
9.4.1 Insertion into a Search Tree = 313
9.4.2 The Treesort Algorithm = 314
9.4.3 Deletion from a Search Tree = 316
9.5 Building a Binary Search Tree = 321
9.5.1 Getting Started = 323
9.5.2 Declarations and the Main Program = 324
9.5.3 Inserting a Node = 325
9.5.4 Finishing the Task = 325
9.5.5 Evaluation = 326
9.5.6 Random Search Trees and Optimality = 327
9.6 Height Balance : AVL Trees = 330
9.6.1 Definition = 330
9.6.2 Insertion of a Node = 330
9.6.3 Deletion of a Node = 337
9.6.4 The Height of an AVL Tree = 338
9.7 Contiguous Representation of Binary Trees : Heaps = 343
9.7.1 Binary Trees in Contiguous Storage = 343
9.7.2 Heaps and Heapsort = 344
9.7.3 Analysis of Heapsort = 348
9.7.4 Priority Queues = 349
Pointers and Pitfalls = 351
Review Questions = 352
References for Further Study = 353
CHAPTER 10 Trees and Graphs = 354
10.1 Orchards, Trees, and Binary Trees = 355
10.1.1 On the Classification of Species = 355
10.1.2 Ordered Trees = 356
10.1.3 Forests and Orchards = 357
10.1.4 The Formal Correspondence = 359
10.1.5 Rotations = 360
10.1.6 Summary = 360
10.2 Lexicographic Search Trees : Tries = 362
10.2.1 Tries = 362
10.2.2 Searching for a Key = 363
10.2.3 C Algorithm = 364
10.2.4 Insertion into a Trie = 365
10.2.5 Deletion from a Trie = 365
10.2.6 Assessment of Tries = 366
10.3 External Searching : B-Trees = 367
10.3.1 Access Time = 367
10.3.2 Multiway Search Trees = 367
10.3.3 Balanced Multiway Trees = 367
10.3.4 Insertion into a B-tree = 368
10.3.5 C Algorithms : Searching and Insertion = 370
10.3.6 Deletion from a B-tree = 375
10.4 Graphs = 382
10.4.1 Mathematical Background = 382
10.4.2 Computer Representation = 384
10.4.3 Graph Traversal = 388
10.4.4 Topological Sorting = 391
10.4.5 A Greedy Algorithm :Shortest Paths = 395
10.4.6 Graphs as Data Structures = 399
Pointers and Pitfalls = 401
Review Questions = 402
References for Further Study = 402
CHAPTER 11 Case Study : The Polish Notation = 404
11.1 The Problem = 405
11.1.1 The Quadratic Formula = 405
11.1.2 Unary Operators and Priorities = 406
11.2 The Idea = 406
11.2.1 Expression Trees = 406
11.2.2 Polish Notation = 408
11.2.3 C Method = 410
11.3 Evaluation of Polish Expressions = 410
11.3.1 Evaluation of an Expression in Prefix Form = 410
11.3.2 C Conventions = 411
11.3.3. C Function for Prefix Evaluation = 412
11.3.4 Evaluation of Postfix Expressions = 413
11.3.5 Proof of the Program : Counting Stack Entries = 414
11.3.6 Recursive Evaluation of Postfix Expressions = 417
11.4 Translation from Infix Form to Polish Form = 421
11.5 An Interactive Expression Evaluator = 426
11.5.1 The Main Program = 426
11.5.2 Representation of the Data = 428
11.5.3 Predefined Tokens = 430
11.5.4 Translation of the Expression = 430
11.5.5 Evaluating the Expression = 439
11.5.6 Summary = 440
References for Further Study = 442
APPENDIX A Mathematical Methods = 443
A.1 Sums of Powers of Integers = 443
A.2 Logarithms = 446
A.2.1 Definition of Logarithms = 446
A.2.2 Simple Properties = 447
A.2.3 Choice of Base = 448
A.2.4 Natural Logarithms = 448
A.2.5 Change of Base = 449
A.2.6 Logarithmic Graphs = 450
A.2.7 Harmonic Numbers = 450
A.3 Permutations, Combinations, Factorials = 452
A.3.1 Permutations = 452
A.3.2 Combinations = 453
A.3.3 Factorials = 453
A.4 Fibonacci Numbers = 456
A.5 Catalan Numbers = 456
A.5.1 The Main Result = 456
A.5.2 The Proof by One-to-One Correspondences = 457
A.5.3 History = 460
A.5.4 Numerical Results = 460
References for Further Study = 460
APPENDIX B Removal of Recursion = 462
B.1 General Methods for Removing Recursion = 462
B.1.1 Preliminary Assumptions = 463
B.1.2 General Rules = 463
B.1.3 Indirect Recursion = 464
B.1.4 Towers of Hanoi = 465
B.1.5 Further Simplifications = 467
B.2 Recursion Removal by Folding = 467
B.2.1 Program Schemata = 467
B.2.2 Proof of the Transformation = 469
B.2.3 Towers of Hanoi : The Final Version = 471
B.3 Nonrecursive Quicksort = 472
B.4 Stackless Recursion Removal :Mergesort = 474
B.5 Threaded Binary Trees = 478
B.5.1 Introduction = 478
B.5.2 Threads = 480
B.5.3 Inorder and Preorder Traversal = 481
B.5.4 Insertion in a Threaded Tree = 482
B.5.5 Postorder Traversal = 484
References for Further Study = 488
APPENDIX C An Introduction to C = 489
C.1 Introduction = 489
C.1.1 Overview of a C Program = 489
C.2 C Elements = 490
C.2.1 Reserved Words = 490
C.2.2 Constants = 490
C.3 Types and Declarations = 491
C.3.1 Basic Types = 491
C.3.2 Arrays = 492
C.3.3 Enumerations = 492
C.3.4 Structures = 492
C.3.5 Unions = 493
C.3.6 typedef = 494
C.4 Operators = 495
C.5 Control Flow Statements = 496
C.5.1 If-Else = 496
C.5.2 Switch = 497
C.5.3 Loops = 497
C.5.4 Break and Continue = 498
C.5.5 Goto = 498
C.6 Pointers = 498
C.6.1 Pointer to a Simple Variable = 498
C.6.2 Pointer to an Array = 499
C.6.3 Array of Pointers = 500
C.6.4 Pointer to Structures = 500
C.7 Functions = 501
C.7.1 Arguments to Functions : Call by Value = 502
C.7.2 Arguments to Functions : Call by Reference = 502
C.7.3 Function Prototypes and Include Files = 503
C.8 Pointers and Functions = 504
C.8.1 Pointer to a Function = 504
C.8.2 Functions that Return a Pointer = 504
C.8.3 Pointer to a Pointer as an Argument = 505
References for Further Study = 506
Index = 507
