AP Computer Science A Exam Topic Outline

The Computer Science A exam covers the topics in a first-semester introductory college course emphasizing programming in C++, programming methodology including recursion and procedural abstraction. It also covers algorithms, data structures, and data abstraction. You should also know the basic algorithms for counting, running totals, finding largest/smallest/equal values, exchanging values (swaps), and copying data (complete and selective). Minor points of syntax and semantics are not tested on the exam.

I. Program design
    A. Design process
        1. Specification of purpose and goals
        2. Identification of subtasks to be performed.
        3. Identification of the abstract data types (ADT's which include stacks, arrays, etc.) and operations needed to solve the problem.
    B. Program design
        1. Identification of reusable components from existing code.
        2. Subprogram decomposition
        3. Choice of data structurs and algorithms
        4. Design of user interface

II. Program implementation
    A. Implementation techniques
        1. Methodology
            a. Top-down development (including use of subprograms)
            b. Bottom-up development
        2. Use of abstraction
            a. Control abstraction
            b. Data abstraction
                i. Abstract data types (ADT's)
                ii. encapsulation and information hiding
    B. Programming constructs
        1. Input and output
            a. Interactive
            b. Files
        2. Control
            a. Sequential
            b. Conditional
            c. Repetition
                i. Iteration
                ii. Recursion

III. Program Analysis
    A. Testing
        1. Testing modules in isolation
        2. Identifying boundary cases and generating appropriate test data
        3. Integration testing
    B. Debugging
        1. Categorizing errors - syntax, run-time, logic
        2. Identifying and correcting errors
        3. Techiques using a debugger, adding extra output statements, hand-tracing
    C. Understanding and modifying existing code
    D. Handling errors
        1. Robust behavior
    E. Reasoning about programs
        1. Pre/post conditions
        2. Assertions
    F. Analysis of algorithms
        1. Informal comparisons of running times
        2. Exact calculation of statement execution count.
    G. Numerical Limits
        1. Limitations of finite representations (e.g. integer bounds, floating point imprecision)

IV. Standard Data Structures
    A. Simple data types (e.g. integer, char, boolean, real)
    B. Records (structs)
    C. Arrays

V. Standard Algorithms
    A. Searching
        1. Sequential (linear)
        2. Binary
    B. Sorting
        1. Selection
        2. Insertion
        3. Mergesort
        4. Quicksort
    C. Operations
        1. Insertion
        2. Deletion
        3. Traversals