상세정보

This book develops the concepts of data structures and algorithm analysis step-by-step in a gradual fashion, proceeding from concrete examples to abstract principles. The presentation stresses motivation, intuition, and utility before giving technical details. Recurring themes such as recursion, levels of abstraction, efficiency, and trade-offs unify the material. Important software engineering concepts and principles are also covered including modularity, abstract data types, and information hiding, as well as new developments such as risk-based software lifecycle models and object-oriented programming. Mathematical foundations are covered and can be engaged at a variety of depths. It is assumed that students using this book for a CS2 course will have already taken a CS1 course covering introductory programming using Pascal.Highlights *Develops the concepts and theory of data structures and algorithm analysis step-by-step, in a gradual fashion, proceeding from concrete examples to abstract principles *Uses recurring themes such as recursion, levels of abstraction, efficiency, and trade-offs to unify the material completely *Provides mathematical foundations that can be engaged at a variety of depths *Covers traditional software engineering principles as well as introducing new concepts such as risk-based software lifecycle models, rapid prototyping, and reusable software components *Introduction to object-oriented programming 0201528800B04062001

정보제공 :

CONTENTS
 Chapter 1 Preparing for The Journey = 1
  1.1 Where are We Going = 1
   Plan for the Chapter = 2
  1.2 Blending Mathematics, Science, and Engineering = 3
  1.3 The Search for Enduring Principles in Computer Science = 6
  1.4 Principles of Software System Structure = 8
  1.5 Efficiency and Tradeoffs = 11
  1.6 Software Engineering Principles = 11
  1.7 Our Approach to Mathematics = 13
  1.8 Some Notes on Programming Notation = 15
  1.9 Preview of Coming Attractions = 18
   Chapter Summary = 20
   Problems and Exercises = 21
 Chapter 2 Linked Data Representations = 22
  2.1 Introduction and Motivation = 22
   Plan for the Chapter = 24
  2.2 What are Pointers the Basic Intuition = 24
   Two Examples of Linked Representations = 25
  2.3 Pascal Pointers -The Rudiments = 27
   Question and Answer Time = 29
  Some Fine Points - Aliases, Recycling, and Dangling Pointers = 30
   The Lifetime of Dynamic Storage = 32
   Dereferencing = 32
   2.3 Review Questions = 32
   2.3 Exercises = 33
  2.4 Pointer Diagramming Notation = 35
   2.4 Review Questions = 37
   2.4 Exercises = 37
  2.5 Linear Linked Lists = 38
   Inserting a New Second Node on a List = 39
   Declaring Data Types for Linked Lists = 42
   Searching for an Item on a List = 43
   Deleting the Last Node of a List = 46
   Inserting a New Last Node ona List = 48
   How to Print a List = 48
  Getting Our Act Together = 51
   Where to From Here = 52
   2.5 Review Questions = 57
   2.6 Exercises = 57
  Pitfalls = 57
  Tips and Techniques = 58
  References for Further Study = 60
  Chapter Summary = 60
 Chapter 3 Introduction to Recursion = 62
  3.1 Introduction and Motivation = 62
   Plan for the Chapter = 63
   Preview of Later Discussions of Recursion = 63
  3.2 Thinking Recursively = 64
   How to Make Things Recursively = 64
   Call Trees and Traces = 69
   Multiplying Things Recursively = 71
   Reversing Lists and Strings = 75
   Reversing Strings = 78
   The General Idea = 80
   3.2 Review Questions = 80
   3.2 Exercises = 81
  3.3 Common Pitfall - Infinite Regresses = 83
   3.3 Review Questions = 85
   3.3 Exercises = 85
  3.4 Quantitative Aspects of Recursive Algorithms = 86
   Towers of Hanoi = 86
   3.4 Review Questions = 90
   3.4 Exercises = 90
  Pitfalls = 90
  Tips and Techniques = 91
  References for Further Study = 91
  Chapter Summary = 91
 Chapter 4 Modularity and Data Abstraction = 93
  4.1 Introduction and Morivation = 93
   Plan for the Chapter = 94
   4.1.2 The Structure of Pascal Units = 95
   4.2 Review Questions = 96
  4.3 Priority Queues - An Abstract Data Type = 97
   A Priority Queue Interface = 97
   Two Implementations for Priority Queues = 99
   Implementing Priority Queues Using Sorted Linked Lists = 101
   Implementing Priority Queues Using Unsorted Arrays = 104
   4.3 Review Questions = 107
   4.3 Exercises = 107
  4.4 A Pocket Calculator Interface = 107
   4.4 Review Questions = 107
   4.4 Exercises = 110
  4.5 How to Hide Data Representations = 111
   4.5 Review Questions = 128
   4.5 Exercises = 128
  4.6 Modularity and Information Hiding in Program Design = 131
   4.6 Review Questions = 134
  Pitfalls = 134
  Tips and Techniques = 134
  References for Further Study = 135
  Chapter Summary = 135
 Chapter 5 Introduction to Software Engineering Concepts = 137
  5.1 Introduction and Motivation = 137
   Plan for the Chapter = 138
  5.2 Top-Down Programming By Stepwise Refinement = 139
   Do You Have A Winning Ticket = 139
   Choosing a Data Representation for the Table = 144
   A Note on Program Modularity = 147
   A Second Refinement = 148
   5.2 Review Questions = 153
   5.2 Exercises = 153
  5.3 Proving Programs Correct = 155
   A Subtle Bug = 160
   A Bit of Formal Logic = 161
   5.3 Review Questions = 165
   5.3 Exercises = 165
  5.5 Testing Programs = 172
   Bottom-Up Testing = 173
   Unit Testing, Formatted Debugging Aids, and Test Drivers = 174
   Integration Testing = 175
   Acceptance Testing and Stubs = 176
   Test Plans = 178
   5.5 Review Questions = 179
   5.5 Exercises = 179
  5.6 The Philosophy of Methods for Binary Searching = 180
   5.6 Review Questions = 185
   5.6 Exercises = 185
   5.7 Software Reuse and Bottom-up Programming = 186
   5.7 Review Questions = 189
   5.7 Exercises = 189
  5.8 Program Structuring and Documentations = 190
   Programming Style Disciplines = 196
   Documentation = 197
   5.8 Review Questions = 198
   5.8 Exercises = 199
  Pitfalls = 200
  Tips and Techniques = 201
  References for Further Study = 202
  Chapter Summary = 202
  Chapter 6 Introduction to Analysis of Algorithms = 205
  6.1 Introduction and Motivation = 205
   Plan for the Chapter = 206
  6.2 What Do We Use for a Yardstick = 207
   6.2 Review Questions = 212
   6.2 Exercise = 212
  6.3 The Intuition Behind O-Notation = 213
  A Word of Caution = 217
    What We'll Discover Later = 217
   6.3 Review Question = 219
   6.3  Exercises = 220
  6.4 O-Notation -Definition and Manipulation = 220
   An Example of a Formal Proof of O-Notation = 221
   Practical Shortcuts for Manipulating O-Notation = 222
   6.4 Review Questions = 224
   6.4 Exercises = 225
  6.5 Analyzing Simple Algorithms = 225
   Analyzing of Sequential Searching = 225
   Analysis of Selection Sort = 227
   Analysis of Recursive Selection Sort = 230
   Analysis of Towers of Hanoi = 232
   Analysis of Merge Sort = 236
   Analysis of Binary Searching = 241
  6.5 Review Questions = 246
  6.5 Exercises = 247
   6.6 What O-Notation Doesn't Tell You = 247
  6.6 Review Questions = 249
    6.6 Exercises = 249
  Pitfalls = 249
  Tips and Techniques = 250
  References for Further Study = 250
  Chapter Summary = 251
 Chapter 7 Linear Data Structures Stacks and Queues = 253
  7.1 Introduction and Motivation = 253
   Plan for the Chapter = 255
  7.2 Some Background on Stacks = 256
   7.2 Review Questions = 258
   7.2 Exercises = 258
  7.3 ADTs for Stacks and Queues = 259
   Interfaces for Stack and Queue  Operations = 261
   7.3 Review Questions = 263
   7.3 Exercises = 263
  7.4 Using the Stack ADT to Check for Balanced Parentheses = 263
   7.4 Review Questions = 270
   7.4 Exercises = 270
  7.5 Using the Stack ADT to Evaluate Postfix Expressions = 267
   7.5 Review Questions = 270
   7.5 Exercise = 270
  7.6 Implementing the Stack ADT = 271
   The Sequential Stack Representation = 271
   The Linked Stack Representation = 273
   7.6 Review Questions = 274
   7.6 Exercise = 275
  7.7 How Pascal Implements Recursive Procedure Calls Using Stacks = 275
   7.7 Review Questions = 280
   7.7 Exercise = 280
  7.8 Implementations of the Queue ADT = 280
   Sequential Queue Representations = 281
   Linked Queue Representation = 284
   Comparing Linked and Sequential Queue Representations = 286
   7.8 Review Questions = 288
   7.8 Exercise = 288
  7.9 More Queue Applications = 289
   Queues in Operating Systems = 289
   Queues in Simulation Experiments = 291
   7.9 Review Questions = 293
   7.9 Exercise = 293
  Pitfalls = 294
  Tips and Techniques = 294
  References for Further Study = 295
  Chapter Summary = 295
 Chapter 8 Lists, Strings, and Dynamic Memory Allocation = 296
  8.1 Introduction  and Motivation = 296
  Plan for the Chapter = 297
   8.2 Lists = 298
   A List ADT = 298
   Sequential List Representations = 298
   The One-Way Linked Representation = 299
   Comparing Sequential and Linked List Representations = 301
   Other Linked List Representations = 302
  Circular Linked Lists = 303
   Two-Way Linked Lists = 303
   Linked Lists with Header Nodes = 304
    8.2 Review Questions = 304
   8.2 Exercise = 304
  8.3 Generalized Lists = 305
   8.3 Review Questions = 308
  8.3 Exercise = 308
  8.4 Applications of Generalized Lists = 308
   8.4 Review Questions = 312
   8.4 Exercise = 312
   8.5 String = 312
   A String ADT = 313
   Some String Representations = 314
   String Representations in Text Files and Word Processors = 316
   8.5 Review Questions = 318
   8.5 Exercise = 318
  8.6 Dynamic Memory Allocation = 319
   Available Space Lists and Garbage Collection = 321
   Heaps and Dynamic  Memory Allocation = 323
   First-Fit = 325
   Best-Fit = 326
   Fragmentation and Coalescing = 327
   Compacting to Deal with Allocation Failures = 328
   Comparing Uses of Heaps in Applications = 330
   Reference Counts = 330
   8.6 Review Questions = 331
   8.6 Exercise = 331
  Pitfalls = 332
  Tips and Techniques = 333
  References for Further Study = 334
  Chapter Summary = 334
 Chapter 9 Tree = 337
  9.1 Introduction and Motivation = 337
  Plan for the Chapter = 338
   9.2 Basic Concepts and Terminology = 339
   9.2 Review Questions = 341
   9.2 Exercise = 341
  9.3 Binary Trees = 342
   9.3 Review Questions = 343
   9.3 Exercise = 343
  9.4 A Sequential Binary Tree Representation = 344
   9.4 Review Questions = 345
   9.4 Exercise = 346
  9.5 An Application-Heaps and Priority Queues = 346
   Converting to the Sequential Representation = 352
   A Few Mathematical Facts About Heaps = 355
   9.5 Review Questions = 358
   9.5 Exercise = 358
  9.6 Traversing Binary Trees = 359
   Traversals Using the Linked Representation of Binary Trees = 361
   9.6 Review Questions = 364
   9.6 Exercise = 364
  9.7 Binary Search Trees = 365
   Analyzing Performance Characteristics = 366
   9.7 Review Questions = 374
   9.7 Exercise = 375
  9.8 AVL Trees and Their Performance = 376
   Building an AVL Tree Using Insertions and Rotations = 380
   Balance Factors and Comments on Rotation Algorithms = 383
   Analysis of Performance = 384
  9.8 Review Questions = 387
   9.8 Exercise = 388
  9.9 Two-Three Trees = 388
   B-Trees-A Generalization of 2 - 3 Trees = 391
   9.9 Review Questions = 392
   9.9 Exercise = 392
  9.10 Tries = 392
   9.10 Review Questions = 394
   9.10 Exercise = 394
  9.11 An Application-Huffman Codes = 394
   9.11 Review Questions = 399
   9.11 Exercise = 399
  Pitfalls = 399
  Tips and Techniques = 400
  References for Further Study = 401
  Chapter Summary = 401
 Chapter 10 Graphs = 405
  10.1 Introduction and Motivation = 405
   Plan for the Chapter = 406
  10.2 Basic Concepts and Terminology = 408
   Some Formal Definitions = 409
   Paths, Cycles, and Adjacency = 410
   Connectivity and Components = 410
   Adjacency Sets and Degrees = 410
   10.2 Review Questions = 411
  10.2 Exercise = 411
  10.3 Graph Representations = 412
    10.3 Review Questions = 414
   10.3 Exercise = 414
  10.4 Graph Searching =  415
   10.4 Review Questions = 419
   10.4 Exercise = 419
  10.5 Topological Ordering = 419
   10.5 Review Questions = 422
   10.5 Exercise = 422
  10.6 Shortest Paths = 423
   10.6 Review Questions = 428
   10.6 Exercise = 428
  10.7 Task Networks = 428
   Critical Path Algorithms = 431
   10.7 Review Questions = 438
   10.7 Exercise = 438
  10.8 Useful Background on Graphs = 439
   Minimal Spanning Trees = 439
   Flow Networks = 441
   The Four-Color Problem = 442
   NP-Complete Graph Problems = 443
   Concluding Remarks = 445
   10.8 Review Questions = 445
   10.8 Exercise = 446
  Pitfalls = 446
  Tips and Techniques = 446
  References for Further Study = 447
  Chapter Summary = 447
 Chapter 11 Hashing and he Table ADT = 450
  11.1 Introduction and Motivation = 450
  Plan for the Chapter = 453
   11.2 The Table ADT = 453
   11.2 Review Questions = 455
   11.2 Exercise = 455
  11.3 Introduction to Hashing by Simple Examples = 455
   11.3 Review Questions = 461
   11.3 Exercise = 461
  11.4 Collisions, Load Factors, and Clusters = 461
   Collisions = 462
   The von Mises Probability Argument = 463
   Load Factors and Clustering = 465
   11.4 Review Questions = 468
   11.4 Exercise = 468
   11.5 Algorithms for Hashing by Open Addressing = 469
   Two Examples of Primary Clustering and Its Absence = 470
   Ensuring That Probe Sequence Cover the Table = 476
   Performance Formulas = 478
   Derivations for Half of the Performance Formulas = 480
   Comparing Theoretical and Empirical Results = 482
   11.5 Review Questions = 483
   11.5 Exercise = 483
  11.6 Choosing a Hash Function = 486
   The Division Method = 487
   Other Hash Function Methods = 488
   11.6 Review Questions = 488
   11.6 Exercise = 488
   11.7 Comparison of Searching Methods Using the Table ADT = 489
   11.7 Review Questions = 493
   11.7 Exercise = 494
 Chapter 12 External Collections of Data = 497
  12.1 Introduction and Motivation = 497
   Plan for the Chapter = 498
  12.2 Characteristics of External Storage Devices = 499
   Tapes = 499
   Disks = 501
   12.2 Review Questions = 504
   12.2 Exercise = 504
  12.3 Techniques That Don't Work Well = 505
   12.3 Review Questions = 507
   12.3 Exercise = 507
  12.4 Techniques That Work Well = 507
   Sorting Large External Files = 507
   The Indexed Sequential Access Method = 509
   Using B-Trees = 513
   Hashing with Buckets = 514
   12.4 Review Questions = 516
   12.4 Exercise = 516
  12.5 Information Retrieval and Databases = 517
   File Inversion Techniques = 517
   Queries and Information Retrieval = 518
   Databases = 519
   12.5 Review Questions = 520
   12.5 Exercise = 520
  Pitfalls = 521
  Tips and Techniques = 521
  References for Further Study = 521
  Chapter Summary = 522
 Chapter 13 Sorting = 524
  13.1 Introduction and Motivation = 524
  Plan for the Chapter = 525
  13.2  Laying Some Groundwork = 527
   13.2 Review Questions = 531
   13.2 Exercise = 532
   13.3 Priority Queue Sorting Methods = 532
   Some Preliminary Assumptions = 532
   Priority Queue Sorting = 533
   Selection Sort = 535
   Heap Sort = 537
   13.3 Review Questions = 539
   13.3 Exercise = 539
  13.4 Divide-and-Conquer Methods = 540
   Merge Sort = 540
   Quick Sort = 540
   13.4 Review Questions = 547
  13.4 Exercise = 547
  1.3.5 Methods That Insert Keys and Keep Them Sorted = 547
   Inserion Sort = 548
   Tree Sort = 550
   13.5 Review Questions = 550
   13.5 Exercise = 550
  13.6 O Methods -Address Calculation Sorting = 551
   Proxmap Sort = 552
   Radix Sort = 563
   13.6 Review Questions = 565
   13.6 Exercise = 565
  13.7 Other Methods = 566
   Shell Sort = 566
   Bubble Sort = 569
   13.7 Review Questions = 571
   13.7 Exercise = 571
   13.8 Comparison and Perspective = 572
   Some Simple Wisdom = 575
   13.8 Review Questions = 575
   13.8 Exercise = 575
  Pitfalls = 576
  Tips and Techniques = 576
  References for Further Study = 577
  Chapter Summary = 577
 Chapter 14 Advanced Recursion = 581
  14.1 Introduction and Motivation = 581
   Plan for the  Chapter = 582
  14.2 Recursion as a Descriptive Methos = 583
   14.2 Review Questions = 585
   14.2 Exercise = 585
  14.3 Using Recursion to Build a Parser = 586
   14.3 Review Questions = 595
   14.3 Exercise = 595
  14.4 Translating from Infix to Postfix = 596
   14.4 Review Questions = 600
   14.4 Exercise = 600
  14.5 Recursion and Program Verification = 601
   Proving that Tree Reversal Works Correctly = 601
   14.5 Review Questions = 605
   14.5 Exercise = 605
  14.6 Pitfalls = 606
  14.7 Tips and Techniques = 607
  14.8 References for Further Study = 607
  14.9 Chapter Summary = 607
 Chapter 15 Object-Oriented Programming = 610
  15.1 Introduction and Motivation = 610
   Plan for the Chapter = 612
  15.2 Exploring OOP Through Progressive Examples = 613
   Defining Subclasses = 618
   Using the Shapes Unit in the Main Program = 619
   Drawing Filled Shapes - The Second Stage OOP Example = 623
  Building and Moving Lists of Shapes - The Third Stage OOP Example = 626
   Conclusions = 638
   15.2 Review Questions = 638
   15.2 Exercise = 639
  15.3 Building Systems Using Object-Oriented Programming = 639
  Imagining a Drawing Application = 639
    Imagining File and Printing Subsystems Using Object-Oriented Programming = 643
   Developing User Interfaces Using Object-Oriented Programming = 646
   15.3 Review Questions = 650
   15.3 Exercise = 650
  15.4 Advantages and Disadvantages of Object Browsers = 652
   15.4 Review Questions = 654
   15.4 Exercise = 654
  Pitfalls = 655
  Tips and Techniques = 655
  References for Further Study = 656
  Chapter Summary = 656
 Chapter 16 Advanced Software Engineering Concepts = 659
  16.1 Introduction and Motivation = 659
   Plan for the Chapter = 660
  16.2 The Software Lifecycle = 660
   Requirements Analysis = 661
   Specification = 662
   Design = 663
   Coding and Debugging = 664
   Testing and Integreation = 665
   Operations, Maintenance, and Upgrade = 666
   16.2 Review Questions = 667
   16.2 Exercise = 667
  16.3 Software Productivity = 667
   The Software Learning Curve = 668
   High Variance in Individual Productivity = 669
   Productivity Differences as a Measure of Comparative Difficulty Among Projects = 670
  16.3 Review Questions = 674
  16.3 Exercise = 675
  16.4 Software Process Models = 675
  The Waterfall Model = 676
  The Spiral Model = 681
  16.4 Review Questions = 684
  16.4 Exercise = 684
  Pitfalls = 685
  Tips and Techniques = 685
 References for Further Study = 686
  Chapter Summary = 686
 Appendix Math Reference and Tutorial = 689
  A.1 Arithmetic Progressions = 689
  Applying the Formulas for Arithmetic Progressions = 692
  A.1 Review Questions = 694
 A.1 Exercise = 694
  A.2 Geometric Progressions = 695
  Applications of Geometric Progressions = 698
  A.2 Review Questions = 700
  A.2 Exercise = 700
  A.3 Floors and Ceilings = 701
  Manipulating Floors and Ceilings = 702
  A.3 Review Questions = 704
  A.3 Exercise = 704
  A.4 Logarithms and Exponentials = 704
  Exponentials = 704
  Logarithms = 705
  Application to Inequalities = 709
  A.4 Review Questions = 710
  A.4 Exercise = 710
  A.5 Modular Arithmetic = 710
  A.5 Review Questions = 713
  A.5 Exercise = 713
  A.6 Sums = 713
  Changing Index Variables = 715
  Application = 715
  Finding Closed Formulas for Sums = 716
  Useful Formulas for Some Special Sums = 720
  A.6 Review Questions = 723
  A.6 Exercise = 723
  A.7 Recurrence Relations = 724
  A.7 Review Questions = 727
  A.7 Exercise = 727
 A.8 Manipulating Logical Expressions = 727
  Problem 1 = 728
  Problem 2 = 729
  Applications = 731
  A.8 Review Questions = 731
  A.8 Exercise = 731
Index = 733