AP Computer Science Principles - Big Idea 3

Big Idea 3: Algorithms and Programming

Overview

• Algorithms and Programming constitute 30-35% of the AP exam weighting.
• This big idea emphasizes the understanding, writing, and implementation of algorithms in programming.
• It is recommended to pair this big idea with other big ideas throughout the school year.

Computational Thinking Practices

• Focus on practices 1.A, 2.A, 2.B, 3.B, and 4.B.

Key Concepts

• Problem Solving: Not all problems are best solved with a program; some are too simple, others too complex.
• Procedural Abstraction: Grouping code into procedures for readability and reusability, often using parameters for generalization.
• Data Abstraction: Using lists to represent data, like grocery lists or seating charts, to manage complexity by naming a collection of data without specific representational details.

Preparing for the AP Exam

• Practice predicting the output of code segments.
• Progress from diagrams or pseudocode to writing simple programs and then complex programs using abstraction.
• Understand code segment functionality to answer written response prompts independently.

Essential Questions

• AAP-1: How can we store data in a program to solve problems?
• AAP-2: What happens if steps in a routine are reordered? How does reordering affect decisions?
• AAP-3: How do video games or apps group actions based on user input?
• AAP-4: What types of problems are more easily solved with or without a computer? Why?

Big Idea 3 At A Glance

• This section outlines the learning objectives, topics, skills, and unit/module for various aspects of algorithms and programming.
• Topics range from variables and assignments to algorithmic efficiency and undecidable problems.

3.1 Variables and Assignments

• Learning Objectives: AAP-1-A, AAP-1.B
• Skills: 3.A (Generalize data sources through variables), 4.B (Determine the result of code segments)
• Enduring Understanding: AAP-1 (To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways).
• Essential Knowledge:
  • AAP-1.A.1: A variable is an abstraction inside a program that can hold a value with associated data storage.
  • AAP-1.A.2: Meaningful variable names enhance code readability.
  • AAP-1.A.3: Programming languages use types like numbers, Booleans, lists, and strings.
  • AAP-1.A.4: Some values are better suited for specific data types.
  • AAP-1.B.1: The assignment operator changes the value of a variable.
  • AAP-1.B.2: Assignment operator example: a ← expression.
  • AAP-1.B.3: The most recent assigned value is the one stored. Example:
    a ← 1 b ← a a ← 2 DISPLAY(b) // Displays 1

3.2 Data Abstraction

• Learning Objectives: AAP-1.C, AAP-1.D
• Skills:
  • 3.A Generalize data sources through variables.
  • 3.B Use abstraction to manage complexity in a program.
  • 3.C Explain how abstraction manages complexity.
• Essential Knowledge:
  • AAP-1.C.1: A list is an ordered sequence of elements (e.g., [value1, value2, value3, ...]).
  • AAP-1.C.2: An element is an individual value in a list.
  • AAP-1.C.3: An index references elements in a list or string.
  • AAP-1.C.4: A string is an ordered sequence of characters.
  • AAP-1.D.1: Data abstraction separates abstract properties from concrete details.
  • AAP-1.D.2: Data abstractions manage complexity by naming data collections.
  • AAP-1.D.3: Lists are used to create data abstractions.
  • AAP-1.D.4: Using data abstraction can make programs easier to develop and maintain.
  • AAP-1.D.5: Data abstractions may contain different types of elements.
  • AAP-1.D.6: Lists allow multiple related items to be treated as a single value (also known as arrays in some languages).
  • AAP-1.D.7: Notation for creating lists: aList ← [value1, value2, value3, ...] or aList ← [] for an empty list.
  • AAP-1.D.8: Index values in lists start from 1. If a list index is out of bounds, an error occurs.

3.3 Mathematical Expressions

• Learning Objectives: AAP-2.A, AAP-2.B, AAP-2.C
• Skills:
  • 2.A Represent algorithmic processes without using a programming language.
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.A.1: An algorithm is a finite set of instructions to accomplish a specific task.
  • AAP-2.A.2: Algorithms can be expressed in natural language, diagrams, or pseudocode.
  • AAP-2.A.3: Programs implement algorithms using programming languages.
  • AAP-2.A.4: Algorithms use sequencing, selection, and iteration.
  • AAP-2.B.1: Sequencing is applying algorithm steps in order.
  • AAP-2.B.2: A code statement expresses an action.
  • AAP-2.B.3: An expression is a value, variable, operator, or procedure call.
  • AAP-2.B.4: Expressions evaluate to a single value.
  • AAP-2.B.5: Evaluation follows a set order of operations.
  • AAP-2.B.6: Sequential statements execute in order.
  • AAP-2.B.7: Clarity and readability are important.
  • AAP-2.C.1: Arithmetic operators include addition, subtraction, multiplication, division, and modulus.
  • AAP-2.C.2: a MOD b evaluates to the remainder when a is divided by b (e.g., 17 MOD 5 = 2).
  • AAP-2.C.3: Arithmetic operators: +, -, *, /, MOD (e.g., 17 / 5 = 3.4).
  • AAP-2.C.4: Order of operations applies; MOD has the same precedence as * and /.

3.4 Strings

• Learning Objective: AAP-2.D
• Skill: 4.B (Determine the result of code segments)
• Essential Knowledge:
  • AAP-2.D.1: String concatenation joins strings end-to-end.
  • AAP-2.D.2: A substring is part of an existing string.

3.5 Boolean Expressions

• Learning Objectives: AAP-2.E, AAP-2.F
• Skills:
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.E.1: A Boolean value is either true or false.
  • AAP-2.E.2: Relational operators: =, ≠, >, <, ≥, ≤.
  • AAP-2.F.1: Logical operators: NOT, AND, OR.
  • AAP-2.F.2: NOT condition evaluates to true if condition is false, otherwise false.
  • AAP-2.F.3: condition1 AND condition2 evaluates to true if both conditions are true, otherwise false.
  • AAP-2.F.4: condition1 OR condition2 evaluates to true if either condition is true, or both, otherwise false.
  • AAP-2.F.5: Operands for logical operators are Boolean expressions or values.

3.6 Conditionals

• Learning Objectives: AAP-2.G, AAP-2.H
• Skills:
  • 2.A Represent algorithmic processes without using a programming language.
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.G.1: Selection determines which parts of an algorithm are executed based on a condition.
  • AAP-2.H.1: Conditional statements (if-statements) affect flow of control based on Boolean expression values.
  • AAP-2.H.2: IF(condition) { <block of statements> } executes the block if condition is true.
  • AAP-2.H.3: IF(condition) { <first block of statements> } ELSE { <second block of statements> } executes the first block if condition is true, otherwise the second block.

3.7 Nested Conditionals

• Learning Objective: AAP-2.I
• Skills:
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.I.1: Nested conditional statements are conditional statements within conditional statements.

3.8 Iteration

• Learning Objectives: AAP-2.J, AAP-2.K
• Skills:
  • 2.A Represent algorithmic processes without using a programming language.
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.J.1: Iteration is a repeating portion of an algorithm.
  • AAP-2.K.1: Iteration statements repeat a set of statements until a stopping condition is met.
  • AAP-2.K.2: REPEAT n TIMES { <block of statements> } executes the block n times.
  • AAP-2.K.3: REPEAT UNTIL(condition) { <block of statements> } repeats the block until the condition is true.
  • AAP-2.K.4: In REPEAT UNTIL, an infinite loop occurs if the ending condition never evaluates to true.
  • AAP-2.K.5: In REPEAT UNTIL, if the conditional is initially true, the loop body is not executed.

3.9 Developing Algorithms

• Learning Objectives: AAP-2.L, AAP-2.M
• Skills:
  • 1.D Evaluate solution options.
  • 2.A Represent algorithmic processes without using a programming language.
  • 2.B Implement and apply an algorithm.
• Essential Knowledge:
  • AAP-2.L.1: Algorithms can be written differently to accomplish the same tasks.
  • AAP-2.L.2: Similar algorithms can yield different side effects or results.
  • AAP-2.L.3: Conditional statements can be written as equivalent Boolean expressions.
  • AAP-2.L.4: Boolean expressions can be written as equivalent conditional statements.
  • AAP-2.L.5: Different algorithms can solve the same problem.
  • AAP-2.M.1: Algorithms can be created from ideas, combining or modifying existing algorithms.
  • AAP-2.M.2: Existing algorithms include finding max/min, computing sum/average, identifying divisibility, or robot pathfinding.
  • AAP-2.M.3: Using existing correct algorithms reduces development time, testing, and simplifies error identification.

3.10 Lists

• Learning Objectives: AAP-2.N, AAP-2.O
• Skills:
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-2.N.1: Basic list operations include accessing elements by index (aList[i]), assigning values to variables (x ← aList[i]), and assigning values to elements (aList[i] ← x).
  • AAP-2.N.2: List procedures include:
    • aList[i] ← aList[j]
    • INSERT(aList, i, value)
    • APPEND(aList, value)
    • REMOVE(aList, i)
    • LENGTH(aList)
  • AAP-2.O.1: Traversing a list involves accessing elements, either completely or partially.
  • AAP-2.O.2: Iteration statements are used to traverse lists.
  • AAP-2.O.3: FOR EACH item IN aList { <block of statements> } assigns each element of aList to item sequentially.
  • AAP-2.O.4: Algorithms using iteration with lists include finding min/max or computing sum/average.
  • AAP-2.O.5: Linear/sequential search checks each element until the desired value is found.

3.11 Binary Search

• Learning Objectives: AAP-2.P
• Skills:
  • 1.A Investigate the situation, context, or task.
  • 1.D Evaluate solution options.
• Essential Knowledge:
  • AAP-2.P.1: Binary search starts in the middle of a sorted dataset and eliminates half of the data iteratively.
  • AAP-2.P.2: Data must be sorted for binary search.
  • AAP-2.P.3: Binary search is generally more efficient than linear search on sorted data.

3.12 Calling Procedures

• Learning Objectives: AAP-3.A
• Skills:
  • 3.B Use abstraction to manage complexity in a program.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-3.A.1: A procedure is a named group of programming instructions that may have parameters and return values.
  • AAP-3.A.2: Procedures are also known as methods or functions.
  • AAP-3.A.3: Parameters are input variables; arguments specify parameter values when the procedure is called.
  • AAP-3.A.4: A procedure call interrupts sequential execution to execute the procedure's statements before continuing.
  • AAP-3.A.5: Procedure call syntax: procName(arg1, arg2, ...).
  • AAP-3.A.6: DISPLAY(expression) displays the value of the expression, followed by a space.
  • AAP-3.A.7: RETURN(expression) returns control and the expression's value to the calling point.
  • AAP-3.A.8: result ← procName(arg1, arg2, ...) assigns the returned value to result.
  • AAP-3.A.9: INPUT() accepts a value from the user and returns it.

3.13 Developing Procedures

• Learning Objectives: AAP-3.B, AAP-3.C
• Skills:
  • 3.B Use abstraction to manage complexity in a program.
  • 3.C Explain how abstraction manages complexity.
• Essential Knowledge:
  • AAP-3.B.1: Procedural abstraction names a process, allowing use based on what it does, not how.
  • AAP-3.B.2: It allows large problems to be solved by solving smaller subproblems with procedures.
  • AAP-3.B.3: Subdividing a program into subprograms is called modularity.
  • AAP-3.B.4: Procedural abstraction generalizes functionality, enabling code reuse and managing complexity.
  • AAP-3.B.5: Parameters allow procedures to be generalized and reused with different inputs.
  • AAP-3.B.6: It improves code readability.
  • AAP-3.B.7: Internals of a procedure can be changed without notifying users, as long as its function is preserved.
  • AAP-3.C.1: Procedure definition syntax:
    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> }
  • AAP-3.C.2: Procedure with return syntax:
    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> RETURN(expression) }

3.14 Libraries

• Learning Objective: AAP-3.D
• Skill: 2.B (Implement and apply an algorithm)
• Essential Knowledge:
  • AAP-3.D.1: A software library contains procedures for use in new programs.
  • AAP-3.D.2: Existing code segments can come from libraries or previously written code.
  • AAP-3.D.3: Libraries simplify the creation of complex programs.
  • AAP-3.D.4: APIs are specifications for how procedures in a library behave.
  • AAP-3.D.5: Documentation is necessary to understand the behaviors provided by an API or library.

3.15 Random Values

• Learning Objectives: AAP-3.E
• Skills:
  • 2.B Implement and apply an algorithm.
  • 4.B Determine the result of code segments.
• Essential Knowledge:
  • AAP-3.E.1: RANDOM(a, b) generates a random integer from a to b, inclusive.
  • AAP-3.E.2: Using random numbers means each execution may produce a different result.

3.16 Simulations

• Learning Objectives: AAP-3.F
• Skills:
  • 1.A Investigate the situation, context, or task.
  • 1.D Evaluate solution options.
• Essential Knowledge:
  • AAP-3.F.1: Simulations are abstractions of complex objects or phenomena.
  • AAP-3.F.2: A simulation uses varying sets of values to reflect the changing state of a phenomenon.
  • AAP-3.F.3: They mimic real-world events to draw inferences in a less constrained environment.
  • AAP-3.F.4: Developing simulations involves removing specific details or simplifying functionality.
  • AAP-3.F.5: Simulations can contain bias.
  • AAP-3.F.6: Simulations are useful when real-world experiments are impractical.
  • AAP-3.F.7: They facilitate the formulation and refinement of hypotheses.
  • AAP-3.F.8: Random number generators can simulate real-world variability.

3.17 Algorithmic Efficiency

• Learning Objectives: AAP-4.A
• Skills: 1.D (Evaluate solution options)
• Essential Knowledge:
  • AAP-4.A.1: A problem is a task description that may or may not be solvable algorithmically.
  • AAP-4.A.2: Decision problems have yes/no answers; optimization problems seek the