
AP CS
Curriculum Topics

HighLevel View
 Logic
 Software Development
 Design:
Objectoriented design,
Data structure design
 Implementation:
Basic programming concepts,
Functions,
Recursion
 Testing
 Data Structures
 Design and Analysis
 Strings, Arrays, Matrices
 Classes and Structs
 AB only: Stacks, Queues, Linked Lists, Trees
 Algorithms
 Design and Analysis
 Elementary algorithms, searching and sorting algorithms,
recursive algorithms
 Case Study
 Concepts
 Implementation
 Testing (Black box and clear box testing)
 Other
 Number Representation
 Compilation process
 Ethics
Intermediate View
 Logic
 Boolean expressions, including DeMorgan's Laws
 assertions, invariants (see Specifications)
 using Boolean expressions in conditions (e.g., if, for, while)
 Software Development
 Software Design
 ObjectOriented Design
 Data Structure Design
 Algorithm Design
 Specifications (pre and postconditions, invariants,
assertions)
 Implementation
 Basic Programming Constructs and Elementary
Patterns
 Arithmetic and Logical Operators
 Conditional Statements
 Loops
 Recursion
 I/O (console and file I/O)
 Function Implementation
 Declaration and definition syntax
 Parameter passing
(AB includes passing pointers by value and reference)
 Scope
 etc.
 Testing
 Blackbox testing
 Developing test plans, testing boundary conditions
 Tracing and understanding code
 Compilation vs runtime vs logical errors
 Data Structures
 Data structure design and analysis
 Strings, Arrays, and Matrices (
apstring, apvector,
apmatrix
)
 Classes and Structs
 Constructing and using aggregates of the basic data structures
listed above
AB Data Structures
 Creating Templated Classes
 Stacks and Queues (
apstack, apqueue
)
 Pointers
 Linked Lists
 Trees, especially binary trees and binary search trees
 Algorithms
 Basic elementary algorithms
 Recursion
 Searching algorithms
 Sorting algorithms (including merge and partition algorithms)
 Efficiency analysis (time and space): informal (A and AB) and
BigOh (AB only)
 Other
 Number Representation
 Compilation process
 Ethics
Detailed View
 Logic
 Boolean expressions, including DeMorgan's Laws
 assertions, invariants (see Specifications)
 using Boolean expressions in conditions (e.g., if, for, while)
 Software Development
 Software Design
 ObjectOriented Design
 Interacting objects,
Encapsulation and data hiding,
Reuse
 FUTURE: Inheritance, Extending Classes
 Data Structure Design
 Data structure design and
analysis (comparing data structures, space
considerations, determining appropriateness of
different data structures for different tasks)
 Abstractions vs concrete data representation
 Specific abstractions:
onedimensional and twodimensional arrays,
AB only: stack, queue, tree (especially binary tree),
binary search tree, priority queue
FUTURE: sets, maps, etc? iterators?
 Class design: responsibilities and data abstraction
 Implementation of concrete data structures
(see below)
 Algorithm Design
(see below)
 Specifications
 Pre and Postconditions
 Invariants (loop invariants, FUTURE: object invariants?)
 Assertions
 Implementation
 Basic Programming Constructs
 Arithmetic and Logical Operators
 identifying the type of an expression
 arithmetic operator precedence
 integer division, mod operator
 shortcircuit of && and  operators
 Conditional Statements
 if patterns, such as
if (no else), if / else, if / else if / else if / else patterns,
nested ifs (e.g., two orthogonal conditions)
 switch statement
 Loops
 for, while, and do/while
 loop patterns, such as
 Process All pattern (e.g., print all, compute sum, etc)
 find min/max
 apvector traversal, apmatrix traversal
 verifying input
 iterative binary search, iterative tree traversal (AB)
 loop invariants, loop exit conditions
 Recursion
 recursive patterns, such as
 treat the base case separately
 reversing a list
 recursive binary search, recursive tree traversal
 tail recursion?
 I/O
 standard and file i/o
 i/o patterns
 Function Implementation
 Declaration and definition syntax
 Variable scope
 Variable definition/initialization (defining primitives and
constructing objects), strong typing
 Initialized vs uninitialized values
(see Testing)
 Basic programming constructs (see above)
 Invoking methods and functions
 Parameter passing
(AB includes passing pointers by value and reference)
 Aliasing
 Member functions vs. free functions
 Templates (AB includes defining templates)
 Testing
 Blackbox testing
 Developing test plans, testing boundary conditions
 Tracing and understanding code
 determining correct output or result
 identifying errors
 Compilation vs runtime vs logical errors
 Data Structures
 Data structure design and analysis
(see above)
 Strings, Arrays, and Matrices
 apstring/apvector/apmatrix indexing,
apstring/apvector traversal (forward and backward),
apmatrix traversal (topdown, leftright pattern and alternatives),
 index vs value
 offbyone errors
 string concatenation
 Struct:
accessing members,
struct constructors
 Classes
 OO design (see above)
 responsibilities of various classes
 reading interfaces, including function signatures and
pre/postconditions (understand function behavior and
determine calling syntax)
 accessors vs modifiers (including const member function syntax)
 invoking methods in client code
 constructors (declaring, defining, and using)
 initialization lists
 defining member functions (see Function
Implementation above)
 accessing members (data & functions) within object
 client and object access to public vs private members
 concept (encapsulation) and recognizing valid/invalid code
 helper functions
 object invariants? (see Specifications)
 Constructing and using aggregates of the basic data structures
listed above
AB Data Structures
 Creating Templated Classes
 Stacks and Queues
 using stack/queue abstract data types
 stack/queue implementation
 Pointers
 understanding pointers (following code)
 dereferencing pointers
 pointers & types: type of pointer, and type of dereferenced pointer
 dynamic memory allocation (new) [delete is now useful,
but not tested]
 Linked Lists
 nodes
 linked list traversal
 recursive linked list traversal
 insertion in order, deletion
 singlylinked vs doublylinked implementations
 following pointers
 Trees, especially binary trees
 leaf vs nonleaf nodes
 binary tree traversal: recursive and iterative
 preorder, inorder, postorder patterns
 traversals that treat leaves and nonleaves differently
(e.g., count all leaves)
 binary search trees (building, searching, traversing)
 Algorithms
 Algorithm Design and Analysis
 Basic elementary patterns (see implementation section,
especially basic programming constructs)
 Recursion (including base cases, offbyone errors)
 Searching algorithms: sequential (sorted and unsorted data), binary,
hash tables and hash functions
 Sorting algorithms (currently insertion, selection, merge, quick, heap)
 Related algorithms: merge and partition algorithms
 Efficiency analysis (time and space): informal (A and AB) and
BigOh (AB only)
 Algorithm Implementation
 Implementation of searching and sorting algorithms,
including merge and partition algorithms
 Other
 Number Representation
 Binary numbers, decimal numbers
 Converting binary <> decimal
 Numerical limits
 Difference between floating point numbers and
real numbers
 Compilation process
 Compiling, linking, executing
 Compilation errors vs. runtime errors vs. logical errors
 Ethics
This page is maintained by Alyce Brady
(abrady@kzoo.edu) at
Kalamazoo College.
Official Disclaimer