 # AP CS Curriculum Topics

### High-Level View

• Logic

• Software Development
• Design: Object-oriented 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
• Object-Oriented Design
• Data Structure Design
• Algorithm Design
• Specifications (pre- and post-conditions, 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
• Black-box testing
• Developing test plans, testing boundary conditions
• Tracing and understanding code
• Compilation vs run-time 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
• 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 Big-Oh (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
• Object-Oriented 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:
one-dimensional and two-dimensional 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 Post-conditions
• 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
• short-circuit 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
• Black-box testing
• Developing test plans, testing boundary conditions
• Tracing and understanding code
• determining correct output or result
• identifying errors
• Compilation vs run-time 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 (top-down, left-right pattern and alternatives),
• index vs value
• off-by-one 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]
• nodes
• insertion in order, deletion
• following pointers

• Trees, especially binary trees
• leaf vs non-leaf nodes
• binary tree traversal: recursive and iterative
• pre-order, in-order, post-order patterns
• traversals that treat leaves and non-leaves 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, off-by-one 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 Big-Oh (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