AP Computer Science Topic Outline

Following is an outline of the major topics covered by the AP Examinations in Computer Science. The ordering here is intended to define the scope of the course, but not necessarily the sequence. The topics in the right-hand column will not be tested on the Computer Science A Examination.

I. Program Design
The overall goal for designing a piece of software (a computer program) is to solve the given problem correctly, but at the same time to specify and designa program that is understandable, can be adapted to changing circumstances, and has the potential to be reuses in whole or in part. The design process needs to be based on a thorough understanding of the problem to be solved.

Computer Science A and BComputer Science AB only
Design Process
  1. Program definition
    1. Specification of purpose and goals
    2. Identification of subtasks to be performed
    3. Identification of the ADT's and operations needed to solve the problem
  2. Program Design
    1. Identification of reusable components from existing code
    2. Subprogram decomposition
    3. Choice of data structures and algorithms
    4. Design of user interface
                                                                                                                     

II. Program Implementation
The overall goals of program implementation parrell 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. Control and data abstraction are important parts of program implementation.

Computer Science A and ABComputer Science AB only
  1. Implementation techniques
    1. Methodology
      1. Top-down devolpment (including use of stub subprograms)
      2. Bottom-up devolpment
    2. Use of abstraction
      1. Control Abstraction
      2. Data Abstraction
        1. abstract data types
        2. encapsulation and information hiding
  2. Programming Constructs
    1. Input and Output
      1. Interactive
      2. Files
    2. Control
      1. Sequential
      2. Conditional
      3. Repetition
        1. Iteration
        2. Recursion
                                                                                                                                                                  

III. Program Analysis
The analysis opf 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.
Computer Science A and BComputer Science AB only
A. Testing
  1. Testing modules in isolation
  2. Identifying boundary cases and generating appropriate test data
  3. Integration testing
B. Debugging
  1. Categorizing erros-syntax, run-time, logic
  2. Identifying and correcting errors
  3. Techniques-using a debugger, adding extra output statements, hand-tracing
C. Understanding and modifying existing code
D. Handling errors
  1. Robust behavior
  1. Exception handling
E. Reasoning about programs
  1. Pre/post conditions
  2. Assertions
  1. Invariants
F. Analysis of algorithms
  1. Informal comparisons of running times
  2. Exact calculation of statement execution counts
  1. Big-O notation
  2. Worst case/average case time and space analysis
G. Numerical limits
  1. Limitations od finite representations (e.g., integer bounds, imprecision of floating point representations, and round-off error)

IV. Standard data structures
Data structures are the means by which the information used by a program is represented within the program. An important theme of the development and application of data structures is abstraction.
Computer Science A and ABComputer Science AB only
  1. Simple data types (e.g., integer, char, boolean, real)
  2. Records
  3. Arrays
D. Linked lists
E. Stacks
F. Queues
G. Trees

V. 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.
Computer Science A and ABComputer Science AB only
A. Searching
  1. Sequential(linear)
  2. Binary
  1. Hashing
B. Sorting
  1. Selection
  2. Insertion
  3. Mergesort
  4. Quicksort
  1. Heapsort
C. Operations
  1. Insertion
  2. Deletion
  3. Traversals
D. Operations on Dynamic data structures
  1. Insertion
  2. Deletion
  3. Traversals

VI. 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 should be considered throughout the course.
Computer Science A and AB
  1. Major hardware components
    1. Primary and secondary memory
    2. Processors
    3. Peripherals
  2. System Software
    1. Language translators
    2. Separate compilation
    3. Operating systems
  3. Types of systems
    1. Single-user systems
    2. Networks
  4. Responsible use of computer systems
    1. System reliability
    2. Privacy
    3. Legal issues and intellectual property
    4. Social and ethical ramifications of computer use