AP Computer Science AB Exam Topic Outline

I. 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.

A. Problem definition
1. Specification of purpose and goals
2. Identification of objects and classes (abstract data types)
3. Identification of class responsibilities (operations on abstract data types)

B. Program design
1. Design of user/client interface
2. Choice of data structures and algorithms
3. Function decomposition
4. Identification of reusable components from existing code

II. 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.

A. Implementation techniques
1. Methodology
a. Object-based development
b. Top-down development

2. Use of abstraction
a. Abstract data types (including encapsulation and information hiding)
b. Procedural abstraction

B. Programming constructs
1. Declaration
a. Constant declarations
b. Variable declarations
c. Class declarations
d. Function declarations
e. Parameter declaration
i. Value
ii. Reference
iii. Constant reference

2. Input and output
a. Interactive
b. Files

3. Control
a. Sequential
b. Conditional
c. Repetition
i. Iteration
ii. Recursion
d. Functions (including member functions)

C. Generic data types and functions
1. AP classes
2. Templates

III. 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.

A. Testing
1. Testing classes and modules in isolation
2. Identifying boundary cases and generating appropriate test data
3. Integration testing

B. Debugging
1. Categorizing errors: compile-time, 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 — robust behavior

E. Reasoning about programs
1. Pre/post conditions
2. Assertions
3. Invariants

F. Analysis of algorithms
1. Informal comparisons of running times
2. Exact calculation of statement execution counts
3. Big-Oh notation
4. Worst case/average case time and space analysis

G. Numerical limits
Limitations of 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. Abstraction is an important theme in the
development and application of data structures.

A. Simple data types (e.g., int, char, bool, double, strings)

B. Aggregate data types
1. Heterogeneous (structs)
2. Homogeneous (arrays)

C. Classes

D. Linked lists

E. Stacks

F. Queues

G. Trees

H. Heaps

I. Priority queues

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.

A. Operations on data structures
1. Traversals
2. Insertion
3. Deletion

B. Operations on dynamic data structures
1. Traversals
2. Insertion
3. Deletion
4. Allocation/deallocation
of memory