Comprehensive Study Notes: AP Computer Science Principles

Course Overview and Curricular Framework

• Curricular Foundation:

  • Based on the Understanding by Design® (Wiggins and McTighe) model.

  • The AP Computer Science Principles course is designed to be equivalent to a first-semester introductory college computing course.

  • Provides a clear description of course requirements necessary for student success and conceptual understanding across fundamental areas of computing.

• AP Computer Science Offerings:

  • AP Computer Science A: Focuses specifically on computing skills related to programming in Java.

  • AP Computer Science Principles: Provides a broad introduction to computer science and explores how computing relates to other fields.

  • Students can take either offering in any order or concurrently.

  • Both courses underscore the importance of communicating solutions appropriately and in ways relevant to societal needs, addressing traditional issues of equity, access, and broadening participation in computing.

• Prerequisites:

  • Successful completion of a first-year high school algebra course with a strong foundation in basic linear functions, composition of functions, and multi-approach problem-solving strategies.

  • Ability to use a Cartesian $(x, y)$ coordinate system to represent points on a plane.

  • Significant computer science coursework builds upon a foundation of mathematical reasoning that must be acquired prior to the course.

  • Prior computer science experience is not required.

• Programming Language Requirements:

  • The course does not designate a specific programming language.

  • Teachers have the flexibility to select the programming language(s) most appropriate for their classroom.

Course Weighting: Big Ideas and Computational Thinking Practices

• Big Ideas and Multiple-Choice Exam Weighting:

  • Big Idea 1: Creative Development: Accounts for $10\%-13\%$ of the exam.

  • Big Idea 2: Data: Accounts for $17\%-22\%$ of the exam.

  • Big Idea 3: Algorithms and Programming: Accounts for $30\%-35\%$ of the exam.

  • Big Idea 4: Computer Systems and Networks: Accounts for $11\%-15\%$ of the exam.

  • Big Idea 5: Impact of Computing: Accounts for $21\%-26\%$ of the exam.

• Computational Thinking Practices and Exam Weighting:

  • Practice 1: Computational Solution Design: Design and evaluate computational solutions for a purpose ($18\%-25\%$ weighting).

  • Practice 2: Algorithms and Program Development: Develop and implement algorithms ($20\%-28\%$ weighting).

  • Practice 3: Abstraction in Program Development: Develop programs that incorporate abstractions ($7\%-12\%$ weighting).

  • Practice 4: Code Analysis: Evaluate and test algorithms and programs ($12\%-19\%$ weighting).

  • Practice 5: Computing Innovations: Investigate computing innovations ($28\%-33\%$ weighting).

  • Practice 6: Responsible Computing: Contribute to an inclusive, safe, collaborative, and ethical computing culture (Not assessed on the Multiple-Choice Section).

Create Performance Task Requirements and Guidelines

• Task Description:

  • Centered on the creative, collaborative development of software designed to solve a problem, enable innovation, explore personal interests, or express creativity.

  • Requires a minimum of $9\,\text{hours}$ of dedicated in-class time.

• Submission Components:

  • Final Program Code: Can be created independently or collaboratively.

  • Video Demonstration: Displays the program running and demonstrates specific functionality developed by the student; must be completed independently.

  • Personalized Project Reference: Contains specific code segments; must be created independently without partner assistance.

• Collaboration Rules and Limitations:

  • Collaboration with partners is permitted only on the development of program code.

  • The video and written response/Personalized Project Reference must be completed strictly independently.

  • Once a teacher assigns the performance task as an AP score component, students cannot receive outside assistance from anyone other than designated project partners (and only on code development).

  • Students in nontraditional classroom environments must consult a school-based AP Coordinator for administrative instructions.

Big Idea 1: Creative Development

• 1.1 Collaboration:

  • Computing Innovation Definition: Includes a program as an integral part of its function. Can be physical (e.g., self-driving car), nonphysical computing software (e.g., picture editing software), or a nonphysical computing concept (e.g., e-commerce).

  • Case Study — Self-Driving Cars:

  • Artificial Intelligence and Machine Learning: Uses AI/ML algorithms to analyze sensor data, make real-time driving decisions, and recognize pedestrians, obstacles, and traffic signs.

  • Sensor Fusion: Combines data from cameras, lidar, radar, and ultrasonic sensors to build an integrated environmental model.

  • High-Performance Computing: Uses GPUs, high-performance processors, FPGAs, and ASICs to execute computationally heavy algorithms in real-time.

  • Mapping and Localization: Employs high-definition geometric maps alongside real-time map matching to locate vehicles accurately.

  • Connectivity and Communication: Uses GPS, cellular networks, Vehicle-to-Vehicle (V2V), and Vehicle-to-Infrastructure (V2I) communication for cooperative driving and traffic coordination.

  • Safety and Redundancy: Implements fault-tolerant architectures, redundant computing systems, and automated fail-safes.

  • Case Study — E-Commerce:

  • Online Marketplaces & Digital Storefronts: Web-based platforms allowing $24/7$ transactions globally without physical retail boundaries.

  • Secure Transactions: Protects financial data using encryption, Secure Sockets Layer (SSL), and tokenization.

  • Inventory & Logistics: Digital inventory tracking and algorithmic dispatching reduce operational costs and error rates.

  • Personalization: Machine learning engines analyze browsing patterns and historical purchases to recommend targeted items.

  • Data Analytics & Digital Marketing: Aggregates consumer metrics for targeted pricing, marketing campaigns, and customer relationship management (CRM).

  • Benefits of Collaboration:

  • Diverse Perspectives: Blends multiple backgrounds to uncover flaws, reduce algorithmic bias, and identify creative solutions.

  • Knowledge Sharing & Skill Complementarity: Merges expertise across software design, hardware architecture, data analysis, and UI/UX.

  • Resource Pooling: Shares computing infrastructure, datasets, and development equipment.

  • Rapid Iteration & Network Effects: Accelerates peer review, debugging, and testing.

  • Collaborative Tools:

  • Google Workspace: Cloud-based editing (Docs, Sheets, Slides, Drive) supporting real-time multi-user document modification.

  • Microsoft Office 365: Cloud-integrated suite for real-time document co-authoring.

  • Slack: Channel-based asynchronous and real-time team messaging and workspace integrations.

  • GitHub: Distributed version control, repository hosting, issue tracking, and pull request reviews.

  • Zoom: Video conferencing tool featuring breakout rooms, screen sharing, and interactive whiteboards.

  • Core Interpersonal Skills:

  • Active communication, emotional intelligence, constructive conflict resolution, trust-building, adaptability, negotiation, and consensus building.

• 1.2 Program Function and Purpose:

  • Program: A collection of program statements that performs a specific task when run by a computer (commonly referred to as software).

  • Code Segment: A collection of program statements forming part of a program.

  • Behavior vs. Purpose:

  • Purpose: The overarching goal of the program (e.g., solving a problem or artistic expression).

  • Behavior: How the program operates during execution, often characterized by user interaction and state changes.

  • Inputs and Outputs:

  • Inputs: Data sent to a program (tactile, audio, visual, text) originating from users, sensors, or other software.

  • Events: Actions supplying input data (mouse clicks, keystrokes, timers) triggering specific blocks in event-driven programming.

  • Outputs: Data sent to an output device (tactile feedback, audio signals, graphics, text displays) determined by inputs and prior state.

• 1.3 Program Design and Development:

  • Development Phases: Investigating and reflecting, designing, prototyping, and testing.

  • Process Models:

  • Iterative Development: Requires continual revision and refinement based on testing and user feedback.

  • Incremental Development: Breaks a problem into smaller modules, verifying each component independently before full system integration.

  • Investigation Strategies: Surveys, user testing sessions, direct interviews, and environmental observations used to establish program specifications.

  • Design Phase Artifacts: Brainstorming boards, storyboards, modular component diagrams, UI layouts, and explicit testing protocols.

  • Documentation & Attribution:

  • Documentation: Written descriptions detailing program functionality, technical constraints, events, and procedures.

  • Comments: Human-readable in-code documentation ignored by compilers and interpreters.

  • Attribution: Direct citations within program documentation identifying external authors, open-source repositories, or peer partners.

• 1.4 Identifying and Correcting Errors:

  • Error Taxonomies:

  • Logic Error: Flaws in program logic resulting in unexpected, incorrect outputs without halting the program.

  • Syntax Error: Violations of the grammatical rules of the programming language preventing compilation or interpretation.

  • Run-time Error: Failures occurring during execution that cause abnormal program termination (e.g., division by zero).

  • Overflow Error: Occurs when calculating an integer value exceeding the memory allocated for numeric representation.

  • Debugging Methods: Boundary test cases (evaluating minimum, maximum, and extreme inputs), hand tracing, visualization diagrams, software debuggers, and temporary print/display output statements.

Big Idea 2: Data

• 2.1 Binary Numbers:

  • Bit & Byte Definitions:

  • Bit: Binary digit, taking the value of $0$ or $1$.

  • Byte: A sequence of $8\,\text{bits}$.

  • Abstraction in Representation: Bits are grouped to represent higher-level abstractions including numeric values, characters, and RGB colors.

  • Analog vs. Digital Data:

  • Analog Data: Values change smoothly and continuously over time (e.g., audio pitch/volume, painted colors, physical speed).

  • Sampling Technique: Digitizing analog signals by recording discrete measurements at fixed time intervals (samples).

  • Precision Limits and Storage Consequences:

  • Integer limits in fixed-bit languages create overflow errors. (Note: AP exam pseudocode integer size is bounded only by overall system memory).

  • Real numbers stored in fixed bits lead to round-off errors and approximation artifacts.

  • Specific mathematical range boundaries for real numbers are excluded from the AP Exam.

  • Number Bases and Conversions:

  • Binary utilizes base $2$ (digits $0, 1$); decimal utilizes base $10$ (digits $0-9$).

  • The positional value of a bit at position $n$ (indexing from right to left starting at $0$) corresponds to $2^n$.

  • The total value of an integer equals:       $\sum (\text{bit}_n \times 2^n)$

• 2.2 Data Compression:

  • Compression Purpose: Reduces the total bit count needed to store or transmit data; fewer bits do not inherently represent less information.

  • Lossless Compression:

  • Permits exact reconstruction of the original file.

  • Used when data integrity cannot be compromised (executable files, text documents, critical medical imagery).

  • Lossy Compression:

  • Irreversibly discards unnoticeable or redundant data to achieve significantly higher compression ratios.

  • Used where transmission speed or bandwidth is prioritized over absolute quality (streaming video, audio, web images).

• 2.3 Extracting Information from Data:

  • Information Discovery: Pattern recognition, clustering, and trend analysis derived from raw data.

  • Correlation vs. Causation: Statistical correlation between variables does not imply a direct causal relationship.

  • Metadata: Structured data that describes other data (file creation timestamps, geo-tags, image dimensions). Changes or deletions to metadata leave the underlying primary data unaltered.

  • Data Cleaning: The process of standardizing records without modifying meaning (e.g., resolving conflicting capitalizations, abbreviations, or spelling discrepancies).

  • Scalability Challenges: Processing massive datasets requires distributed or parallel computational systems.

• 2.4 Using Programs with Data:

  • Computational techniques include filtering (selecting rows meeting criteria), transforming (mapping values, such as doubling array elements), aggregating (calculating sums, averages, maximums), and charting/graphing.

Big Idea 3: Algorithms and Programming

• 3.1 Variables and Assignments:

  • A variable represents an abstraction that stores a single value or collection at an allocated memory location.

  • AP Reference Syntax:

  • Text: a <-- expression

  • Block format:

    

  • Evaluation: Evaluates the right-hand expression first, copying the evaluated result into variable a.

  • Variable Overwrites: A variable retains only the most recently assigned value: text a <-- 1 b <-- a a <-- 2 DISPLAY(b) -- Output remains 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

• 3.2 Data Abstraction:

  • Lists: Ordered sequences of elements referenced by integer index values.

  • AP Reference List Indexing: Starts at index $1$ up to LENGTH(aList). Accessing an index outside $[1, \text{LENGTH}]$ produces an execution error and terminates the program.

  • List Initialization and Assignment:

  • Explicit literal: aList <-- [value1, value2, value3]

    

  • Empty list: aList <-- []

    

  • List copy assignment: aList <-- bList (duplicates content from bList to aList).

    

• 3.3 Mathematical Expressions & 3.4 Strings:

  • Building Blocks of Algorithms: Every algorithm can be constructed using combinations of sequencing, selection, and iteration.

  • Arithmetic Operators: Addition (+), subtraction (-), multiplication (*), division (/), and modulus (MOD).

  • Modulus Operator: a MOD b returns the integer remainder when $a$ is divided by $b$ ($a \ge 0$, $b > 0$). Precedence matches multiplication and division.

  • Example: 17 MOD 5 evaluates to 2.

  • Strings: Concatenation merges strings end-to-end; substrings represent continuous character sequences extracted from an existing string.

• 3.5 Boolean Expressions & Logical Operators:

  • Relational Operators: Relational checks return Boolean (true/false) states: =, ≠, >, <, ≥, ≤.

  • Logical Operators:

  • NOT condition: Inverts the Boolean condition.

    

  • condition1 AND condition2: True only if both conditions evaluate to true.

    

  • condition1 OR condition2: True if either condition or both evaluate to true.

    

• 3.6 Conditionals & 3.7 Nested Conditionals:

  • Single-Branch Selection: Executes statement block only if condition evaluates to true.

    

  • Dual-Branch Selection: Uses IF (condition) { ... } ELSE { ... } to guarantee execution of one alternative path.

  • Nested Selection: Placing conditional statements inside existing conditional blocks.

• 3.8 Iteration Constructs:

  • Count-Controlled Iteration: REPEAT n TIMES executes statement block exactly $n$ times.

    

  • Condition-Controlled Iteration: REPEAT UNTIL (condition) loops until condition evaluates to true. If the condition is true initially, statements do not execute.

• 3.10 List Operations & Traversals:

  • Element Access: aList[i] accesses element at index $i$.

    

  • Element Extraction: x <-- aList[i].

    

  • Element Mutation: aList[i] <-- x.

    

  • Element Swap/Transfer: aList[i] <-- aList[j].

    

  • List Insertion: INSERT(aList, i, value) shifts elements at indices $\ge i$ to the right by one position and inserts value at index $i$.

    

  • List Appending: APPEND(aList, value) places value at the end of aList, increasing length by $1$.

    

  • List Removal: REMOVE(aList, i) deletes element at index $i$ and shifts all elements at indices $> i$ left by one position.

    

  • List Length: LENGTH(aList) returns the total count of elements.

    

  • List Traversals: FOR EACH item IN aList assigns item sequentially to each element from index $1$ to LENGTH(aList).

    

• 3.11 Searching Algorithms:

  • Sequential / Linear Search: Scans every element sequentially until target is found or list ends. Operates on unsorted and sorted datasets.

  • Binary Search: Requires data sorted in advance. Compares the target against the middle item and discards half the remaining items per iteration.

• 3.12 Calling & 3.13 Developing Procedures:

  • Definitions: Named reusable blocks of instructions that can receive parameters and output results.

  • Procedural Abstraction & Modularity: Breaking large programs into modular procedures allows developers to focus on high-level design while internal logic is updated without impacting callers.

  • AP Reference Procedure Declaration:

  • Text: PROCEDURE procName(param1, param2, ...) { <block of statements> }

  • Block format:

    

  • I/O Functions:

  • DISPLAY(expression): Outputs the value followed by a trailing space.

    

  • INPUT(): Takes a value entered by the user and returns it.

    

  • RETURN(expression): Immediately halts procedure execution and passes the evaluated result back to the caller.

    

• 3.14 Libraries, 3.15 Random Values & 3.16 Simulations:

  • Libraries & APIs: Software libraries provide pre-written procedures. Application Programming Interfaces (APIs) document how library procedures function and interface.

  • Random Generation: RANDOM(a, b) returns an integer in the range $[a, b]$ inclusive, with uniform distribution.

  • Simulations: Abstract models of real-world phenomena used when actual experiments are too costly, dangerous, large, or slow.

• 3.17 Algorithmic Efficiency & 3.18 Undecidable Problems:

  • Problem Classes:

  • Decision Problem: Produces a binary yes/no output.

  • Optimization Problem: Searches for the best possible outcome among numerous viable candidates.

  • Efficiency Scales:

  • Reasonable Time: Algorithms exhibiting polynomial runtime or lower (constant, linear, quadratic, cubic: $n^c$).

  • Unreasonable Time: Algorithms with exponential or factorial operational bounds ($2^n$, $n!$).

  • Heuristics: Approximate shortcut techniques providing acceptable solutions when finding the optimal solution is computationally impractical.

  • Undecidable Problems: Problems where no single algorithm can be constructed that provides a correct yes/no answer for every possible input.

Big Idea 4: Computer Systems and Networks

• 4.1 Architecture of the Internet:

  • Definitions:

  • Computing Device: A physical machine running programs (servers, laptops, routers, smart sensors).

  • Computing System: An interconnected group of devices and software working cooperatively.

  • Computer Network: An interconnected collection of devices communicating data (a type of computing system).

  • Bandwidth: Maximum volume of data transmitted over a network channel in a fixed duration, measured in bits per second.

  • Internet Structure:

  • A globally distributed network of interconnected networks running on open, standardized protocols.

  • Protocols are nonproprietary sets of operational rules (IP, TCP, UDP).

  • Dynamic Routing: Packets route dynamically across variable physical paths rather than following fixed routes.

  • Data Streams and Packet Switching:

  • Information travels packaged within packets consisting of data payloads along with routing/reassembly metadata.

  • Packets may take different physical paths, arrive out of chronological order, or drop entirely.

  • Internet vs. World Wide Web (WWW):

  • Internet: The underlying physical and network routing infrastructure.

  • World Wide Web: A high-level system of linked web pages, media files, and programs operating across HTTP on top of the Internet.

• 4.2 Fault Tolerance and Reliability:

  • Fault Tolerance: System capacity to remain fully functional despite component failures.

  • Redundancy: Implementing backup paths and hardware lines. If an individual node or link fails, dynamic routing automatically re-routes traffic.

• 4.3 Parallel and Distributed Computing:

  • Computational Models:

  • Sequential Computing: Solves operations in strict chronological sequence on a single processor.

  • Parallel Computing: Breaks a problem into concurrent operations executed simultaneously across multiple processor cores.

  • Distributed Computing: Runs tasks concurrently across physically separate computers networked together.

  • Speedup Calculations:     $\text{Speedup} = \frac{\text{Sequential Runtime}}{\text{Parallel Runtime}}$

  • Parallel Runtime Limits: Total execution time equals the sequential phase duration plus the runtime of the longest parallel sub-task. The sequential portion prevents infinite scaling of speedup when adding processing units.

Big Idea 5: Impact of Computing

• 5.1 Dual Effects of Computing Innovations:

  • Computing advances create intended benefits but routinely generate unintended negative side effects.

  • Examples:

  • World Wide Web: Designed for open scientific document sharing; expanded into a global network utilized also for disinformation and tracking.

  • Targeted Advertising: Increases customer acquisition for small businesses, but can compromise user privacy.

  • Machine Learning & Data Mining: Powers breakthroughs in medicine, but risks reinforcing systemic discrimination when trained on biased data.

• 5.2 The Digital Divide:

  • Disparities in access to internet bandwidth, computing devices, and digital services driven by socioeconomic, geographic, and demographic inequalities.

  • The divide impacts access to education, economic mobility, and administrative representation.

• 5.3 Computing Bias:

  • Bias can emerge from programmer assumptions in algorithm design or unrepresentative historical training datasets.

  • Collecting more data does not eliminate bias if the underlying collection processes are flawed.

• 5.4 Crowdsourcing and Citizen Science:

  • Crowdsourcing: Aggregating contributions, labor, or funding from large networks of online users.

  • Citizen Science: Distributed scientific research where non-professional volunteers collect and submit observations through digital tools.

• 5.5 Legal and Ethical Concerns:

  • Intellectual Property: Digital assets belong legally to their creators. Plagiarism constitutes unauthorized appropriation.

  • Licensing Frameworks:

  • Creative Commons: Public copyright licenses allowing creators to grant permissions for sharing and modifying their creative work.

  • Open Source: Programs distributed with source code available for free inspection, modification, and redistribution.

  • Open Access: Scholarly articles and research distributed freely without paywall barriers.

• 5.6 Safe Computing & Cybersecurity:

  • Personally Identifiable Information (PII): Data linking directly to an identity (Social Security numbers, age, phone numbers, biometric, financial, and medical history).

  • Authentication:

  • Multi-Factor Authentication (MFA): Requires evidence from at least two different categories:

    1. Knowledge Factor: Something you know (passwords, PINs).

    2. Possession Factor: Something you have (smartcards, authenticator tokens).

    3. Inherence Factor: Something you are (biometrics: fingerprints, retina scans).

  • Encryption Protocols:

  • Symmetric Key Encryption: Uses a single secret key for both encoding and decoding.

  • Public Key (Asymmetric) Encryption: Uses a mathematically paired public key for encoding and private key for decoding.

  • Certificate Authorities: Trusted validation organizations issuing digital certificates confirming public key ownership.

  • System Vulnerabilities and Attack Vectors:

  • Phishing: Deceptive messages tricking users into disclosing passwords or PII.

  • Keylogging: Spyware tracking physical keyboard entries.

  • Rogue Access Points: Malicious Wi-Fi routers intercepting and altering plaintext data traffic.

  • Viruses and Malware: Programs designed to replicate, disrupt system operations, or provide backdoor access.

Practical Implementations and Laboratory Reference (Lua)

• Foundational Syntax and Interactive Loops (Weeks 10–18):

  • Standard Output & String Formatting:

  print("Hello World")
  local myName = "Student"
  print("Name: " .. myName)  -- String concatenation using ..
      ```
  * **Interactive Console Input and Conditionals:**
  

  lua io.write("> ") -- Prints without adding an automatic newline local choice = io.read() if choice == "re-enter" then print("you chose to re-enter") elseif choice == "seek shelter" then print("you chose to seek shelter") else print("invalid choice") end     ```

  • Sentinel-Controlled Loops and Modular Menus:lua function main() local done = false while not done do print("Menu: E1 - Example, Q - Quit") io.write("Choice: ") local choice = io.read() if choice == "E1" then example1() elseif choice == "Q" then done = true else print("Invalid Choice") end end end     

• Searching and Complexity Implementations (Weeks 20–21):

  • Sequential / Linear Search ($O(n)$):

  function linearSearch(array, target)
      for index, value in ipairs(array) do
          if value == target then
              return index
          end
      end
      return -1
  end
      ```
  * **Binary Search Implementation ($O(\log n)$):**
  

  lua function binarySearch(array, target) local low = 1 local high = #array while low <= high do local mid = (low + high) // 2 -- Integer floor division local guess = array[mid] if guess == target then return mid elseif guess > target then high = mid - 1 else low = mid + 1 end end return -1 end     ```

  • Quadratic Time Algorithm ($O(n^2)$):

  function quadraticTimeAlgorithm(array)
      for i = 1, #array do
          for j = 1, #array do
              local a = array[i] + array[j]
          end
      end
  end
      ```
  * **Permutation Generation ($O(n!)$ using Heap's Algorithm Logic):**
  

  lua function generatePermutations(array, n) if n == 1 then return 1 else local count = 0 for i = 1, n do count = count + generatePermutations(array, n - 1) if n % 2 == 0 then array[i], array[n] = array[n], array[i] else array[1], array[n] = array[n], array[1] end end return count end end     ```

• Data Structures and Dictionaries (Week 22):

  • Dictionary / Hash Map Pattern: ```lua local inventory = {}

  function addItem(inventory, item) if inventory[item] then inventory[item] = inventory[item] + 1 else inventory[item] = 1 end end

  function hasItem(inventory, item) return inventory[item] ~= nil and inventory[item] > 0 end     ```