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
  • 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 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]
  • Linked Lists
    • nodes
    • linked list traversal
    • recursive linked list traversal
    • insertion in order, deletion
    • singly-linked vs doubly-linked implementations
    • 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
    • Compiling, linking, executing
    • Compilation errors vs. run-time errors vs. logical errors
  • Ethics