3.2 — Data Abstraction

Lists & strings, indexes, and how abstraction manages complexity.

Learning Objectives

  • Represent a list or string using a variable.
  • For data abstraction, develop data abstraction using lists to store multiple elements.
  • Explain how the use of data abstraction manages complexity in program code.

Essential Knowledge

  • A list is an ordered sequence of elements.
  • An element is an individual value in a list.
  • An index is a common method for referencing the elements in a list or string using natural numbers.
  • A string is an ordered sequence of characters.
  • Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation.
  • Data abstraction can be created using lists.
  • The exam reference sheet provides notation for lists and describes a list structure whose index values are 1 through the number of elements (inclusive). For all list operations, if a list index is less than 1 or greater than the length of the list, an error is produced and the program will terminate.

New Types of Variables

Strings

  • An ordered sequence of characters.
  • May contain letters, numbers, and special characters.
  • Examples: words, phrases, sentences, ID numbers.

Lists

  • An ordered sequence of elements.
  • Each element is a variable.
  • Examples: playlist of songs, names of students in a class, contacts in your phone.

List Index

  • Each element of a list (and each character of a string) is referenced by an index.
  • For the AP exam, the index starts at 1.
  • Using an index < 1 or > length causes an error.
pets ← ["🐶","🐱","🐹","🐢"]
# Indexes: 1..4 (AP CSP)
# pets[1] = "🐶"

Data Abstraction — Lists

  • Lists allow for data abstraction — bundle variables together (strings, numbers, characters, etc.).
  • Give one name to a set of memory cells.
  • You do not need to know in advance how many variables will be needed.
  • You do not need to know how the elements are stored together.

How Lists Manage Complexity

  • Fewer variables: one list variable can hold many related items (e.g., all students).
  • Dynamic size: add/remove elements without redefining many variables (e.g., new student transfers).
  • Consistent computation: apply the same computation over all items (e.g., curve all test scores).

3.3 — Mathematical Expressions

Values, variables, operators, functions — expressions evaluate to a single result.

What Are Mathematical Expressions?

In programming, a mathematical expression is a combination of values, variables, operators, and functions that the computer evaluates to produce a single result.

5 + 3
x * y - z
abs(a - b)

Operators

+   addition
-   subtraction
*   multiplication
/   division
**  exponents
%   modulo (remainder)

Note: In Python, MOD is represented by %.

Example: Calculating Distance

Distance between two points (x₁, y₁) and (x₂, y₂):

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)
diffX ← x2 - x1
diffY ← y2 - y1
distance ← sqrt(diffX * diffX + diffY * diffY)

Key Takeaways

  • Expressions evaluate to a single value.
  • Operators perform operations on values or variables.
  • Functions can be used to perform more complex calculations.
  • Understanding expressions is crucial for developing algorithms and controlling program behavior.

Additional Resources

  • Mathematical Expressions Study Guide (Fiveable)
  • AP Central: Course and Exam Description
https://fiveable.me/ap-comp-sci-p/unit-3/mathematical-expressions/study-guide/00lGBdF7QyY5hmd1rubD
https://apcentral.collegeboard.org/media/pdf/ap-computer-science-principles-course-and-exam-description.pdf

3.5 — Boolean Expressions & Logic

Booleans, relational operators, modulus, and logical operators (NOT, AND, OR).

Boolean Values

Booleans represent two states: True or False. They often come from evaluating expressions (e.g., 5 < 10 → True) and are used in if-statements, loops, and decision making.

myHairIsBlack = True
iHaveADog = False

Key takeaway: Booleans let a program decide what to do based on conditions.

Relational Operators

==   Equal           (5 == 5)  → True
!=   Not equal       (4 != 5)  → True
>    Greater than    (7 > 3)   → True
<    Less than       (2 < 8)   → True
>=   Greater or equal (6 >= 6) → True
<=   Less or equal    (9 <= 4) → False

College Board expectations: recognize/apply relational operators, predict Boolean results, and use them within if-statements and algorithms.

Modulus Operator (%)

Finds the remainder after division — great for even/odd tests and cycles.

print(10 % 2)  # 0 (even)
print(7 % 2)   # 1 (odd)
  • num % 2 == 0 → even
  • num % 2 == 1 → odd
  • day % 7 → day of week in a cycle

College Board expectations: determine remainders, apply modulus in conditions, write Boolean expressions with % to detect patterns.

Logical Operators

NOT (negation)

isCloudy = True
print(not isCloudy)  # False

AND (conjunction)

didHomework = True
scored80 = True
canGoOut = didHomework and scored80  # True

OR (disjunction)

isWeekend = True
hasHoliday = False
dayOff = isWeekend or hasHoliday  # True

College Board expectations: apply NOT/AND/OR, predict outcomes of compound expressions, and recognize how combinations support decisions.

3.17 — Algorithms & Efficiency

Problems vs. instances, Big-O growth, reasonable vs. unreasonable time, heuristics.

Big-O Notation Basics

O(1)   Constant      → same time regardless of input size
O(n)   Linear        → grows proportionally with input size
O(n²)  Quadratic     → grows with square of input size
O(2ⁿ)  Exponential   → explodes rapidly as input increases

What is a Problem?

A problem is a general task that we want an algorithm to solve.

Example: Sorting is a problem (putting numbers in order).

What is an Instance?

An instance is a specific case of a problem with actual input values.

Example: Sorting (2, 3, 1, 7) is one instance of the sorting problem.

Types of Problems

  • Decision Problem: Yes/No answer. Example: “Is there a path from A to B?”
  • Optimization Problem: Find the best solution. Example: shortest path from A to B.

Measuring Efficiency

Efficiency describes how fast an algorithm’s cost grows as input size increases (count operations, not wall-clock time).

Reasonable vs. Unreasonable Time

  • Reasonable: O(1), O(log n), O(n), O(n log n), O(n²*)
  • Unreasonable: O(2ⁿ), O(n!).

Quadratic (O(n²)) can be okay for small/medium n.

Example: Algorithm Growth

Input n | Alg1 (5n) | Alg2 (3ⁿ) | Alg3 (4n²) | Alg4 (n!)
   1    |     5     |     3     |     4      |   1
   2    |    10     |     9     |    16      |   2
   3    |    15     |    27     |    36      |   6
   4    |    20     |    81     |    64      |  24
   5    |    25     |   243     |   100      | 120

Heuristic Approaches

A heuristic is a smart shortcut that finds a good-enough solution efficiently — not always optimal, but practical when exact methods are too slow.

Traveling Salesperson Problem (TSP)

  • Visit all cities once, return to start → minimize distance.
  • Routes grow factorially:
    • 4 cities → 6 routes
    • 10 cities → 362,880 routes
    • 20 cities → ~10¹⁷ routes
  • Heuristics help when exact solutions are impossible for large n (e.g., Nearest Neighbor).

Example: High School Scheduling

Best use of a heuristic: creating the master schedule (complex & constrained).

Not heuristic-needed for: searching prices, calculating GPA, generating passwords.

Quick Check

In which situation is a heuristic most useful?

  • A. Searching a list of prices for the smallest value
  • ✅ B. Creating the master schedule for a high school
  • C. Calculating GPA for all students
  • D. Generating passwords

Quick Glossary

  • Problem — a general task an algorithm aims to solve.
  • Instance — a specific case of a problem.
  • Decision Problem — Yes/No answer.
  • Optimization Problem — best solution.
  • Efficiency / Big-O — how cost grows with input size.
  • Heuristic — shortcut method, not guaranteed optimal.
  • TSP — classic optimization problem (visit all cities, shortest route).