Correlations

Java Software Solutions for AP® Computer Science ©2003

John Lewis, William Loftus, and Cara Cocking

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: 122–123, 124–126, 162–166, 229–231, 271–273
      2. Identification of objects and classes (abstract data types)
        ST: 58–59, 60–62, 62–63, 63–67, 67–71
      3. Identification of class responsibilities (operations on abstract data types)
        ST: 60–62, 62–63, 63–67, 67–71, 106–108, 202, 209, 228, 399–405
    2. Program design
      1. Design of user/client interface
        ST: 3–4, 280–284, 285–288, 428–434, 435–439, 439–442
      2. Choice of data structures and algorithms
        ST: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 560–566, 567–573
      3. Function decomposition
        ST: 80–85, 86–90, 91–94, 95–96, 97–98, 99–102, 122–130, 131–135, 138–140, 140–142, 142–146, 162–166
      4. Identification of reusable components from existing code
        ST: 58–60, 79–82, 82–85, 85–88, 89–94, 162–166, 277–279, 264, 477–493, 514, 565–566

  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: 58–62, 62–68, 68–71, 122–123, 162–166, 317–321, 322–330, 330–332, 552–558, 565–566
        2. Top-down development
          ST: 122–123, 317–320, 321, 322–323, 324–325, 326–327, 327–328, 329–330, 330–332, 552–558, 565–566
      2. Use of abstraction
        1. Abstract data types (including encapsulation and information hiding)
          ST: 31, 58, 61–63, 198–200, 263, 340, 399–405, 428
        2. Procedural abstraction
          ST: 31, 58, 61–63, 198–200, 263, 322–325, 326–327, 330–332, 340, 399–405, 428, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 560–566, 566–573
    2. Programming constructs
      1. Declaration
        1. Constant declarations
          ST: 71, 200, 257, 300, 362
        2. Variable declarations
          ST: 71–74, 77–80, 81–85, 87–88, 89–91, 91–95, 96–99, 101, 105–108, 200, 257, 300, 362
        3. Class declarations
          ST: 87–88, 89–91, 91–95, 96–99, 101, 105–108, 200, 257, 300, 362, 609–615, 616–619
        4. Function declarations
          ST: 162–166, 264, 277–279, 336–339, 341, 458, 477–493, 514, 565–566
        5. Parameter declaration
          1. Value
            ST: 60, 207–208, 249, 252–256, 307–308
          2. Reference
            ST: 60, 87–88, 207–208, 248–256, 307–308, 386–388, 409–410
          3. Constant reference
            ST: 1, 200, 257, 300, 362
      2. Input and output
        1. Interactive
          ST: 4, 146, 277–279, 281–282, 283–285, 286–288, 428–434, 435–442
        2. Files
          ST: 2, 12, 60–62, 96–99, 146, 211
      3. Control
        1. Sequential
          ST: 15, 83–85, 86–88, 89–91, 94–99, 100–101, 122–124
        2. Conditional
          ST: 122–124, 125–127, 127–128, 128–130, 131–133, 133–135
        3. Repetition
          1. Iteration
            ST: 133–135, 142–146, 146–153, 153–156, 156–160, 161–162, 269–271, 340, 459
          2. Recursion
            ST: 133–135, 142–146, 146–153, 153–156, 156–160, 161–162, 454–564, 475–476, 493–503
        4. Functions (including member functions)
          ST: 80–85, 86–90, 91–94, 95–96, 97–98, 99–102, 122–130, 131–135, 138–140, 140–142, 142–146, 162–166, 192–196, 405–408
    3. Generic data types and functions
      1. AP® classes
        ST: 60–62, 62–63, 63–67, 67–71, 106–108, 202, 209, 228, 399–405
      2. Templates
        ST: 60–62, 63–67, 67–71, 85–91, 106–108, 202, 209, 228, 399–405, 610–614, 615–619

  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: 122–123, 150, 202–206, 206–214, 214–220, 492
      2. Identifying boundary cases and generating appropriate test data
        ST: 122–123, 150, 202–206, 206–214, 214–220, 492
      3. Integration testing
        ST: 122–123, 150, 202–206, 206–214, 214–220, 492
    2. Debugging
      The text contains 26 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: 40–41, 66–67, 146, 302
      2. Identifying and correcting errors
        ST: 40–41, 66–67, 146, 302
      3. Techniques—using a debugger, adding extra output statements, hand-tracing
        ST: 40–41, 66–67, 96–99, 146, 302
    3. Understanding and modifying existing code
      ST: 58–60, 79–82, 82–85, 85–88, 89–94, 162–166, 166–174, 229–231, 264, 273–276, 277–279, 423–428, 477–493, 514, 565–566
    4. Handling errors—robust behavior
      ST: 0–41, 66–67, 146, 302
    5. Reasoning about programs
      1. Pre/post conditions
        ST: 124, 125–127, 127–129, 130–131, 133–135, 135–138, 146–149, 149–153, 168–174
      2. Assertions
        ST: 124, 125–127, 127–129, 130–131, 133–135, 135–138, 146–149, 149–153, 168–174
      3. Invariants
        ST: 71, 124, 125–127, 127–129, 130–131, 133–135, 135–138, 146–149, 149–153, 168–174, 200, 257, 300, 362
    6. Analysis of algorithms
      1. Informal comparisons of running times
        ST: 40–41, 146–149, 330–332
      2. Exact calculation of statement execution counts
        ST: 40–41, 146–149, 330–332
      3. Big Oh notation
        ST: 40–41, 66–67, 146, 302–303
      4. Worst Case/Average case time and space analysis
        ST: 40–41, 66–67, 146, 302–303
    7. Numerical limits
      Limitations of finite representations (e.g., integer bounds, imprecision of floating point representations, and round-off error)
      ST: 7–9, 67–70, 71–72, 76–77, 77–79, 80–82, 218

  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: 31, 67–70, 71–72, 76–77, 77–79, 80–82, 218
    2. Aggregate data types
      1. Heterogeneous structs
        ST: 7–9, 58, 67–70, 71–72, 76–77, 77–79, 80–82, 106–108, 202, 209, 228, 399–405
      2. Homogeneous arrays
        ST: 298–300, 301–303, 304–306, 307–308, 309–310, 311–313, 314–316
    3. Classes
      ST: 60–62, 62–63, 63–67, 67–71, 106–108, 202, 209, 228, 399–405
    4. Linked Lists
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516, 518–519, 520–524, 525–526, 527–528, 528–533, 544–545, 545–549, 560–566, 566–573, 613
    5. Stacks
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 528–533, 544–545, 545–549, 560–566, 566–573
    6. Queues
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516–525, 526–528, 544–545, 545–549, 560–566, 566–573
    7. Trees
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 552–559, 560–566, 566–573
    8. Heaps
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 567–573
    9. Priority queues
      ST: 123, 322–325, 326–327, 330–332, 514–515, 516–525, 526–528, 544–545, 545–549, 560–566, 566–573

  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: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
      2. Insertion
        ST: 123, 168–174, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
      3. Deletion
        ST: 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
    2. Operations on dynamic data structures
      1. Traversals
        ST: 123, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
      2. Insertion
        ST: 123, 168–174, 322–325, 326–327, 330–332, 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
      3. Deletion
        ST: 514–515, 516–526, 526–528, 528–533, 544–545, 545–549, 550–552, 560–566, 566–573
      4. Allocation/deallocation
        ST: 67–68, 70–71, 340–342
    3. Searching
      1. Sequential (linear)
        ST: 317–320, 321
      2. Binary
        ST: 317–320, 321, 332–333, 552–558
      3. Hashing
        ST: 332–333
    4. Sorting
      1. Selection
        ST: 317–320, 321, 322–325, 326–327, 327–328, 329–330, 330–332, 552–558
      2. Insertion
        ST: 317–320, 321, 322–325, 326–327, 327–328, 329–330, 330–332, 552–558
      3. Mergesort merge algorithm
        ST: 318, 319, 317–320, 321, 322–325, 326–328, 329–330, 330–332, 552–558
      4. Quicksort partition algorithm
        ST: 317–320, 321, 322–325, 326–328, 329–330, 330–332, 475–476, 552–558
      5. Heapsort
        ST: 317–320, 321, 322–325, 326–328, 329–330, 330–332, 475–476, 552–558, 565

  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: 2–3, 3–4, 10–11, 12–16, 16–18
      2. Processors
        ST: 2–3, 3–4, 10–11, 16–18
      3. Peripherals
        ST: 2–3, 3–4, 10–11, 12–18
    2. System software
      1. Language translators
        ST: 35–37, 37–39, 39–41
      2. Separate compilation
        ST: 35–37, 37–39, 39–41
      3. Operating systems
        ST: 2–3, 3–4, 10–11, 12–18
    3. Types of systems
      1. Single-user systems
        ST: 2–3, 3–4, 5–7, 8–10, 10–16
      2. Networks
        ST: 18–19, 19–20, 20–21, 21–22, 22–24
    4. Responsible use of computer systems
      1. System reliability
        ST: 2–3, 3–4, 5–7, 8–10, 10–16, 18–19, 19–20, 20–21, 21–22, 22–24
      2. Privacy
        ST: 18–19, 19–20, 20–21, 21–22, 22–24, 31, 199
      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

AP® is a trademark registered and/or owned by the College Board, which was not involved in the production of, and does not endorse, this site.