Correlations

Java: How to Program 4th Edition, © 2002

Harvey M. Deitel and Paul J. Deitel

Correlated with AP* Computer Science AB, May 1999

ST = Student textbook pages

Computer Science AB

1. Program Design
   The overall goal for designing a piece of software (a computer program) is to correctly solve the given problem. At the same time, this goal should encompass specifying and designing a program that is understandable, can be adapted to changing circumstances, and has the potential to be reused in whole or in part. The design process needs to be based on a thorough understanding of the problem to be solved.
   1. Problem definition
      1. Specification of purpose and goals
         ST: 41–44, 45–46, 56–60, 61–64, 76–84, 107–109
      2. Identification of objects and classes (abstract data types)
         ST: 42–43, 58–62, 90–91, 107, 116, 135–140, 350–352, 382–385, 392, 417, 446, 452, 459, 477, 512–513, 530, 836, 901–903, 981, 1085, 1331, 1384, 1459
      3. Identification of class responsibilities (operations on abstract data types)
         ST: 18, 58–59, 62, 70, 115, 126, 161, 291, 382–385, 392, 417, 435, 452, 474, 512, 896, 1085, 1375
   2. Program design
      1. Design of user/client interface
         ST: 4, 67, 264, 268–271, 280, 283, 319, 332, 386, 393, 400, 467, 602–603, 604–610, 611, 612–617, 618–622, 622–626, 627–628, 629–634, 637–639, 648, 652, 705
      2. Choice of data structures and algorithms
         ST: 251, 259–263, 269–272, 281–283, 324, 342, 372, 393, 395, 396, 397, 399, 482–483, 494, 512, 579, 583, 586–587, 603–604, 605, 628, 635, 649, 654–655, 726, 732, 758, 820, 823, 895–897, 899, 900–902, 903–905, 906–908, 910–913, 915–919, 920, 922–927, 928, 930, 931–933, 936–937, 939–943, 965, 991, 1070, 1323, 1327, 1384, 1387, 1391, 1399, 1415, 1418, 1435–1436
      3. Function decomposition
         ST: 51–54, 97–104, 189–196, 239–245, 300–312, 356–357, 440–444, 592–600, 642–645, 713–719, 799–803, 835–836, 887–893, 972–977, 1064–1067
      4. Identification of reusable components from existing code
         ST: 264, 268–271, 280, 283, 319, 332, 386, 393, 400, 467, 602–603, 604–610, 611, 612–617, 618–622, 622–626, 627–628, 629–634, 637–639, 648, 652, 705, 1384–1387
   
   
2. Program Implementation
   The overall goals of program implementation parallel those of program design. Modules of the program that fill common needs should be built so that they can be reused easily in other programs. Procedural and data abstraction are important parts of program implementation.
   1. Implementation techniques
      1. Methodology
         1. Object-based development
            ST: 22–24, 42, 90–91, 107, 116, 135–140, 350–352, 382, 446, 452, 459, 477, 513, 530, 836, 901–903, 981, 1331, 1384, 1459
         2. Top-down development
            ST: 7, 166, 174, 432, 1160
      2. Use of abstraction
         1. Abstract data types (including encapsulation and information hiding)
            ST: 152, 381, 432, 474–477, 486–487, 516–519, 521, 656, 1056
         2. Procedural abstraction
            ST: 152, 381, 432, 474–477, 486–487, 516–519, 521, 649, 656, 758, 1056, 1229
   2. Programming constructs
      1. Declaration
         1. Constant declarations
            ST: 215, 270, 322, 560
         2. Variable declarations
            ST: 24, 71, 75, 126, 128, 203, 258, 261, 380, 412
         3. Class declarations
            ST: 115–116, 135–140, 161–163, 169–170, 176–177, 180, 350–352, 382–385, 392, 417, 446, 452, 459, 477, 512–513, 530, 836, 901–903, 981, 1085, 1331, 1384, 1459
         4. Function declarations
            ST: 116–117, 121, 122–123, 124–125, 190–191, 193, 199–201
         5. Parameter declaration
            1. Value
               ST: 249, 252, 254, 289, 318, 981, 1007
            2. Reference
               ST: 266–269, 280
            3. Constant reference
               ST: 282–283, 320–321, 323–324
      2. Input and output
         1. Interactive
            ST: 602–603, 604–610, 611, 612–617, 618–622, 622–626, 627–628, 629–634, 637–639, 1440–1449, 1460–1469
         2. Files
            ST: 115, 293, 352, 383, 583, 895, 897, 900, 903–915, 916–918, 919–920, 921–927, 928–929, 931–933, 936–939, 961, 991, 996–998, 1003–1004, 1006–1008, 1058–1060
      3. Control
         1. Sequential
            ST: 56–66, 67–77, 88, 109–119, 151, 154, 204–205, 206–214, 217, 230–233, 236, 269, 281, 338–342, 343–349, 380–390, 400–408, 452–461, 487–495, 516–517, 538–546, 549–550, 552–553, 556, 558, 563–568, 607–612, 1393–1403, 1404–1414, 1415–1425, 1438–1448, 1449–1459, 1460–1463
         2. Conditional
            ST: 153–156, 159–163, 176–177, 181, 383, 854
         3. Repetition
            1. Iteration
               ST: 198–204, 205–208, 210–216
            2. Recursion
               ST: 278–279, 284–287, 310, 368, 1131
         4. Functions (including member functions)
            ST: 116–117, 121, 122–123, 124–125, 190–191, 193, 199–201, 382, 434
   3. Generic data types and functions
      1. AP* classes
         ST: 837–839, 840–847, 848–853, 860–868, 1094–1096, 1097–1107
      2. Templates
         ST: 133, 521–525, 795
   
   
3. Program Analysis
   The analysis of programs includes analyzing and testing programs to determine whether they correctly meet their specifications. It also includes the analysis of programs or the algorithms they implement so as to understand their time and space requirements when applied to different data sets.
   1. Testing
      1. Testing classes and modules in isolation
         ST: 58–59, 62, 66, 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 805–807, 809, 810–818, 819–820, 824, 841
      2. Identifying boundary cases and generating appropriate test data
         ST: 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 805–807, 809, 810–818, 819–820, 824, 841
      3. Integration testing
         ST: 16, 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 841
   2. Debugging
      The text contains 46 Testing and Debugging Tips, which show the student how to test programs to find subtle bugs. These are repeated at the end of each chapter.
      1. Categorizing errors—compile-time, run-time, logic
         ST: 58–59, 62, 66, 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 805–807, 809, 810–818, 819–820, 824, 841
      2. Identifying and correcting errors
         ST: 58–59, 62, 66, 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 805–807, 809, 810–818, 819–820, 824, 841
      3. Techniques—using a debugger, adding extra output statements, hand-tracing
         ST: 473, 841
   3. Understanding and modifying existing code
      ST: 1384–1387, 1388–1390, 1391–1392, 1393–1400, 1401–1403, 1404–1407, 1408, 1409–1415, 1416–1419, 1420–1428, 1429–1435, 1436–1437, 1438–1454, 1455–1457, 1458–1459, 1460–1465
   4. Handling errors—robust behavior
      ST: 805–808, 809–811, 812–817, 818–823, 824–829, 830–836
   5. Reasoning about programs
      1. Pre/post conditions
         ST: 150–152, 153–154, 155–158
      2. Assertions
         ST: 160–164, 165–172, 201–205
      3. Invariants
         ST: 215, 270, 282–283, 320–321, 323–324, 560
   6. Analysis of algorithms
      1. Informal comparisons of running times
         ST: 332–334, 335–337
      2. Exact calculation of statement execution counts
         ST: 338–342
      3. Big Oh notation
         ST: 338–342
      4. Worst Case/Average case time and space analysis
         ST: 338–342
   7. Numerical limits
      Limitations of finite representations (e.g., integer bounds, imprecision of floating point representations, and round-off error)
      ST: 72–74, 76–78, 79–84, 123–126
   
   
4. Standard Data Structures
   Data structures are the means by which the information used by a program is represented within the program. Abstraction is an important theme in the development and application of data structures
   1. Simple data types (e.g., int, char, bool, double, strings)
      ST: 60, 69, 71–74, 103, 109, 156, 225, 513, 538, 1114, 1156
   2. Aggregate data types
      1. Heterogeneous structs
         ST: 113–114, 121–122, 123–125, 152, 176, 203, 215–217, 230, 251, 259–263, 269–272, 281–283, 324
      2. Homogeneous arrays
         ST: 287, 314–319, 326–328, 895, 982, 1208–1210, 1215–1221
   3. Classes
      ST: 42–43, 58–62, 90–91, 107, 116, 135–140, 350–352, 382–385, 392, 417, 446, 452, 459, 477, 512–513, 530, 836, 901–903, 981, 1085, 1331, 1384, 1459
   4. Linked lists
      ST: 383, 1095–1097, 1206, 1230, 1235
   5. Stacks
      ST: 310, 383, 432, 811, 828, 831, 1095, 1108
   6. Queues
      ST: 383, 430–433, 1095, 1113
   7. Trees
      ST: 112, 1116, 1223, 1380
   8. Heaps
      ST: 83, 430–433
   9. Priority queues
      ST: 383, 433, 1095, 1113
   
   
5. Standard Algorithms
   Standard algorithms can serve as examples of good solutions to standard problems. Programs implementing them can serve as models of good program design. They provide examples for analysis of program efficiency. Many are intertwined with standard data structures.
   1. Operations on data structures
      1. Traversals
         ST: 1121
      2. Insertion
         ST: 383, 566, 1098, 1155
      3. Deletion
         ST: 566, 1123, 1190
   2. Operations on dynamic data structures
      1. Traversals
         ST: 1121
      2. Insertion
         ST: 383, 566, 1098, 1155
      3. Deletion
         ST: 566, 1123, 1190
      4. Allocation/deallocation of memory
         ST: 426, 825, 839, 901, 1162, 1202
   3. Searching
      1. Sequential (linear)
         ST: 335–336, 337–338, 368
      2. Binary
         ST: 335–338, 340, 1221
      3. Hashing
         ST: 548, 575, 1148, 1161–1162
   4. Sorting
      1. Selection
         ST: 332–335, 944, 1095, 1223–1226
      2. Insertion
         ST: 334–335
      3. Mergesort merge algorithm
         ST: 334–335, 367–368
      4. Quicksort partition algorithm
         ST: 368
      5. Heapsort
         ST: 334–335, 367–368
   
   
6. Computer Systems
   A working knowledge of the major hardware and software components of computer systems is necessary for the study of computer science, as is the importance of considering the ethical and social implications of computing systems. These topics need not be covered in detail, but they should be considered throughout the course.
   1. Major hardware components
      1. Primary and secondary memory
         ST: 3, 7–8, 9, 11, 14, 15, 19, 25, 27, 46–48
      2. Processors
         ST: 7, 1249, 1259, 1262
      3. Peripherals
         ST: 8, 68–72, 109–110, 534, 648, 676–678, 686–688
   2. System software
      1. Language translators
         ST: 10–12, 16–19, 21, 61–62, 119, 1095
      2. Separate compilation
         ST: 10–12, 16, 21, 61–62, 119, 1095
      3. Operating systems
         ST: 2–7, 8–9, 10, 11–12, 13–15, 16–19, 20–21, 60, 68, 61–62, 107, 131, 604, 722, 758, 839
   3. Types of systems
      1. Single-user systems
         ST: 8, 161–163, 169–170, 175–177, 207–208, 252–253
      2. Networks
         ST: 9, 978–980, 981–985, 986–989, 990–991, 992–1002, 1003–1010, 1011–1025, 1026–1035, 1036–1055, 1056–1060
   4. Responsible use of computer systems
      1. System reliability
         ST: 57–59, 71, 259, 270, 271, 274, 275, 280, 286, 287, 316, 317, 394, 395, 448, 473, 560, 563, 628, 656, 660, 841
      2. Privacy
         ST: 19–21, 116, 152, 388–401, 434, 451, 656–661, 1262
      3. Legal issues and intellectual property
         ST: 27, 33–34, 64–65, 67–70, 77, 83, 90, 94–96
      4. Social and ethical ramifications of computer use
         ST: 27, 33–34, 64–65, 67–70, 77, 83, 90, 94–96