Big Idea 3: Algorithms and Programming

This guide was based on the updated 2020-21 Course Exam Description.

The One Thing You Need to Know About This Big Idea:

This Big Idea covers the vast majority of the code you'll see on the AP test in the spring. It describes basic components of most programming languages such as variables, lists, and procedures. 

Unlike AP Comp Sci A, which only teaches Java, there's no programming language specification for AP CSP. Your teacher could use a block-based language like Scratch or a text-based language like Python. In order to accommodate for these differences, The AP CSP test uses a basic Pseudocode, or a simplified programming language.

The College Board's Pseudocode shares many similarities with the coding language Python, which is used to help write examples across this guide. 

All photos of Pseudocode come from the Exam Reference Sheet on page 214 of the CED, found here.

3.1 Variables and Assignments

**Learning Objective: Represent a value with a variable. **

Learning Objective: Determine the value of a variable as a result of an assignment.

Key Ideas

• a variable is a placeholder for a value
• spelling and capitalization matter for variable names
• data types are different categories of data that your computer can represent

Vocabulary

• variable
• data types

Resources

🔗 3.1: Variables and Assignments

3.2 Data Abstraction

Learning Objective: Represent a list or string using a variable.

Learning Objective: For data abstraction, develop data abstraction using lists to store multiple elements; explain how the use of data abstraction manages complexity in program code.

Key Ideas

• elements are individual values in a list
• each element has an index value
• data abstraction simplifies a set of data by representing it in some general way
• data abstraction lets you create programs that are easier to build, maintain, and read

Vocabulary

• list
• element
• index
• string
• array

Resources

🔗 3.2: Data Abstraction

3.3 Mathematical Expressions

Learning Objective: Express an algorithm that uses sequencing without using a programming language.

**Learning Objective: Represent a step-by-step algorithmic process using sequential code statements. **

Learning Objective: Evaluate expressions that use arithmetic operators.

Key Ideas

• an algorithm represents the problem-solving logic
• programs execute algorithms
• steps in your algorithm are implemented in the order they're written in
• MOD operator
• evaluating an expression is done through an order of operations specified by the programming language

Vocabulary

• algorithm
• sequencing
• code statement
• expression

Resources

🔗 3.3: Mathematical Expressions

3.4 Strings

Learning Objective: Evaluate expressions that manipulate strings.

Key Ideas

• strings are an ordered list of characters that you can navigate through using index values
• you can't perform mathematical operations with strings, but you can still manipulate them
• slicing is the process to create a substring
• concatenation is the process of joining strings together

Vocabulary

• string concatenation
• substring

Resources

🔗 3.4: Strings

3.5 Boolean Expressions

Learning Objective: For relationships between two variables, expressions, or values, write expressions using relational operators; evaluate expressions that use relational operators.

Learning Objective: For relationships between Boolean values, write expressions using logical operators; evaluate expressions that use logic operators.

Key Ideas

• Boolean variables can only represent the values true or false
• relational operators are used with Boolean values to test the relationship between two values
• NOT, AND, and OR are logical operators that evaluate either Boolean expressions or a single Boolean value

Vocabulary

• Boolean value

Resources

🔗 3.5: Boolean Expressions

3.6 Conditionals

Learning Objective: Express an algorithm that uses selection without using a programming language.

Learning Objective: For selection, write conditional statements; determine the result of conditional statements.

Key Ideas

• selection statements in programming are used to control the flow of execution in a program
• if statements and else statements execute different segments of code based on specified conditions

Vocabulary

• selection

Resources

🔗 3.6: Conditionals

3.7 Nested Conditionals

**Learning Objective: For nested selection, write nested conditional statements; determine the result of nested conditional statements. **

Key Ideas

• nested conditional statements are conditional statements inside conditional statements
• if the conditions for the outer conditional statement are not satisfied, the conditions for the nested conditional statement will not even be checked

Vocabulary

• nested conditional statements

Resources

🔗 3.7: Nested Conditionals

3.8 Iteration 

Learning Objective: Express an algorithm that uses iteration without using a programming language.

Learning Objective: For iteration, write iteration statements; determine the result or side effect of iteration statements.

Key Ideas

• "repeat n times" loops happen a set number of times - these are for loops in Python
• "repeat until (condition)" loops happen until a condition is met - these are while loops in Python
• you can use logical operators when writing conditions for loops

Vocabulary

• iteration

Resources

🔗 3.8: Iteration

3.9 Developing Algorithms

Learning Objective: Compare multiple algorithms to determine if they yield the same side effect or result.

**Learning Objective: For algorithms, create algorithms; combine and modify existing algorithms. **

Key Ideas

• different algorithms can be used to achieve the same goals
• algorithms that look similar might yield different side effects or results
• new algorithms can be created from scratch or by combining and modifying algorithms that already exist

Vocabulary

none 

Resources

🔗 3.9: Developing Algorithms

3.10 Lists

Learning Objective: For list operations, write expressions that use list indexing and list procedures; evaluate expressions that use list indexing and list procedures.

**Learning Objective: For algorithms involving elements of a list, write iteration statements to traverse a list; determine the result of an algorithm that includes list traversal. **

Key Ideas

• there are basic operations you can perform on a list- access an element by index- assign the value of an element of a list to a variable- assign a value to an element- assign the value of one element in the list to another- insert elements at a given index- add elements to the end of the list- remove elements- determine the length of the list
• you can traverse through a list, either through a complete traversal or a partial traversal

Vocabulary

• traverse
• linear/sequential search

Resources

🔗 3.10: Lists

3.11 Binary Search

Learning Objective: For binary search algorithms, determine the number of iterations required to find a value in a data set; explain the requirements necessary to complete a binary search.

Key Ideas

• binary search algorithms eliminate half the data with each round of splitting
• data must first be sorted in order to use a binary search method

Vocabulary

• binary search

Resources

🔗 3.11: Binary Search

3.12 Calling Procedures

**Learning Objective: For procedure calls, write statements to call procedures; determine the result or effect of a procedure call. **

Key Ideas

• you use a procedure to use the same set of instructions without having to rewrite it into your code
• procedures often require some sort of parameter in order to work
• you call procedures with arguments
• once a procedure terminates (either because there are no more lines or you use a return statement), the program goes back to where the procedure was called and continues reading code sequentially

Vocabulary

• procedure
• parameters
• arguments

Resources

🔗 3.12: Calling Procedures

3.13 Developing Procedures

Learning Objective: Explain how the use of procedural abstraction manages complexity in a program.

**Learning Objective: Develop procedural abstractions to manage complexity in a program by writing procedures. **

Key Ideas

• you can call a procedure without knowing how it works
• procedures allow you to solve a large problem based on the solution to smaller sub-problems
• procedural abstraction allows programmers the flexibility to modify or fix procedures without affecting the whole program, as long as the procedure continues to function in the same way

Vocabulary

• procedural abstraction
• modularity

Resources

🔗 3.13: Developing Procedures

3.14 Libraries

Learning Objective: Select appropriate libraries or existing code segments to use in creating new programs.

Key Ideas

• you can import already-existing code from a library to help you create new programs
• you can also import code you've already written
• APIs help you understand how the procedures in a library behave and how to use them

Vocabulary

• software library
• application program interface

Resources

🔗 3.14: Libraries

3.15 Random Values

**Learning Objective: For generating random values, write expressions to generate possible values; evaluate expressions to determine the possible results. **

Key Ideas

• using random number generation in a program means we might get a different result every time we run the program

Vocabulary

none

Resources

🔗 3.15: Random Values

3.16 Simulations

**Learning Objective: For simulations, explain how computers can be used to represent real-world phenomena or outcomes; compare simulations with real-world contexts. **

Key Ideas

• simulations are simplifications of complex objects or phenomena for a stated goal, such as investigating real-world events and conditions
• to develop a simulation, you have to remove certain real world details or simplify how something functions
• simulations run the risk of being too simple or conveying the wrong message about what you're trying to study
• simulations may contain bias based on what the creator chose to include or exclude

Vocabulary

• simulation

Resources

🔗 3.16: Simulations

3.17 Algorithmic Efficiency

**Learning Objective: For determining the efficiency of an algorithm, explain the difference between algorithms that run in reasonable time and those that do not; identify situations where a heuristic solution may be more appropriate. **

Key Ideas

• informally, efficiency is measured by determining how many times a statement or statement group executes
• algorithms that run with a polynomial efficiency or lower are said to run in a reasonable amount of time
• algorithms that run with an exponential or factorial efficiency run in an unreasonable amount of time
• some problems can't be solved in a reasonable amount of time, so we look for an approximate solution using a heuristic

Vocabulary

• problem
• instance
• decision problem
• optimization problem
• efficiency
• reasonable amount of time
• unreasonable amount of time
• heuristic

Resources

🔗 3.17: Algorithmic Efficiency

3.18 Undecidable Problems

Learning Objective: Explain the existence of undecidable problems in computer science.

Key Ideas

• an undecidable problem may be solvable for some cases, but there is no algorithm that will solve the problem in all cases

Vocabulary

• decidable problem
• undecidable problem

Resources

🔗 3.18: Undecidable Problems

Exam Weighing:

• 30-35% of the AP Exam
• Practically, this translates to a good portion of the questions on the test. This unit also makes up the bulk of your final Create project. It's a big part of this course.