APCSP Review Notes

APCSP Review

Creative Development and Collaboration

• Computing Innovation Definition:
  • Must include a program as a major part of its function.
  • Can be physical (e.g., self-driving car) or software.
• Collaboration:
  • Many people working together on a task.
  • Provides diverse viewpoints and talent in design.
  • Helps reduce bias due to diverse perspectives.
  • Online tools facilitate including diverse opinions (e.g., Zoom calls).
• Programs:
  • Collection of code statements for a task.
  • Takes input and produces output.
  • Inputs can be audio, text, visual, etc.
  • Inputs come from users or other programs (e.g., Amazon Echo).
  • Program output is based on its inputs.

Program Development Processes

• Programs are adjusted, reviewed, and given feedback.
• Investigation (user testing, reviews, observations) identifies program constraints.
• Methods to check if a program is functioning correctly:
  • User testing
  • User reviews
  • Program observations

Program Errors

• Logic Errors:
  • Mistakes in the algorithm causing incorrect behavior.
  • Example: Adding 10 instead of 5.
• Syntax Errors:
  • Mistakes in the programming language's rules.
• Runtime Errors:
  • Occur during program execution.
  • Example: Accessing an array element out of bounds.
• Overflow Errors:
  • Occur when a compiler tries to handle a number outside its defined range of values.
• Debugging:
  • Using test cases and visualizing code helps reduce errors.

Data

• How Computers Store Data:
  • Computers store data in bits (base 2 numbers).
  • All numbers are represented with ones and zeros.
  • Example: 100 in base 10 is 8 in base 2.
• Converting Decimal to Base 2:
  • Find the highest power the base can be raised to and subtract that from the number until you get zero.
  • Example converting 100 to base 2, 2^3 = 8
• Byte:
  • A byte is defined as eight bits.
• Data Representation:
  • Programmers use lists, variables, or constants.
  • The computer converts that to bits.
  • Bits grouped together can be abstractions (e.g., colors, RGB).
• Context Matters:
  • The same sequence of bits can mean different things in different contexts.
  • Example: Color vs. height in a video game.
• Analog vs. Digital Data:
  • Analog data changes smoothly over time (e.g., pitch, sprinter's position).
  • Digital data can represent analog data, resulting in an abstraction.
• Sampling:
  • Measuring analog data at different intervals (samples).
  • Using intervals to model the analog data.
• Limitations:
  • Programming languages have a fixed number of bits for integers.
  • Overflow error if more bits are needed (e.g., using int instead of long in Java).
  • Round-off error occurs when a value is too precise or includes too many values after the decimal.

Errors in Data Handling

• Round-Off Errors:
  • Due to limited precision.
• Overflow Errors:
  • Result from a value being too large to store.
• Base Conversion Practice:
  • Convert 10 from base 10 to base 2 (answer: 1010 in base 2).
  • Find highest power of 2 less than 10. 2^3 = 8. 10-8 = 2. 2^1 = 2. fill the rest with zeros.

Data Compression

• Reduces the number of bits of transmitted or stored data.
• Lossless Compression:
  • Reduces bits while guaranteeing a complete restoration to the original size.
• Lossy Compression:
  • Reduces bits while allowing only an approximate restoration.
  • Reduces bits more than in lossless compression.

Data Analysis and Implications

• Trends and Connections:
  • Data provides opportunities to identify trends and make connections.
  • Digital data can show correlations; however, correlation does not always equal causation.
  • Causation needs a well-defined experiment.
• Metadata:
  • Data about the data (e.g., time, location of an image).
  • Changes to metadata do not affect the data itself.
  • Allows for structure and organization.
• Data Cleansing:
  • Vital to ensure data is uniform and complete.
  • Incomplete data is hard to analyze.
  • Data sources sometimes need to be combined.
  • Data collection may not always be uniform.
  • Cleaning data makes the data uniform without changing the meaning (e.g., standardizing state abbreviations).
• Bias Reduction:
  • Can be reduced through thoughtful data collection.
  • Larger datasets offer more information but require more time and complex computing systems.
• Data Processing:
  • Programs can be used to process data into information.
  • Tables and diagrams can communicate insights.
  • Datasets can be filtered, transformed, and merged.

Algorithms and Programming

Variables:

• Something that holds a value.
• Use different names to name a variable, better to be creative to describe the variable's purpose
• Languages may require defining variable type.
• Use a meaningful variable name (e.g., "height of clouds" versus "H").

Assignment Expression:

• A value assigned to a variable.
• Every time assignment is done, the variable values change.
  • Example: A=5, then A=10, the value of fiv eis not there in A anymore.

Lists:

• Represent many variables together.
• Indexes reference specific values in the list.
• The first index on the AP exam is one.
• The length of the list is the number of items in the list.

Strings:

• Lists of characters or words.
• Can concatenate strings (combine them).

Math Expressions:

• Addition, subtraction, division, multiplication, and mod.
• Mod returns the remainder (e.g., 10 \mod 3 = 1).
• PEMDAS operations (order of operations) still used.

Boolean Expressions:

• "And": Both conditions must be true.
• "Or": Only one condition has to be true.
• "Not": Neither condition can be true.

If Statements:

• Control sequential control of a program.
• If a condition is true, the program goes to the block.
• The program goes outside the block unless there's an else statement.
• Conditionals can be nested (if statement inside an if statement).

Loops:

• Make it easy for programmers to do the same task many times.
• Repeat n times (you give the value right away) or repeat until X, where X is a conditional (while loop).
• While loops can run infinitely if the condition is never stopped, and it might not even run if the condition is not true in the first place.
• For loops repeat n times, given straight away

Lists again:

• Group of a certain variable type with many values.
• Access element at index I of a list: list at I.
• Adjust value at index I: list at I equals X.
• Insert value at a certain index: insert on the AP exam, value inserted right at that index
• Append: Adds a value at the end.
• Remove: Removes element at the index given.
• Iterate through each element: for each item in a list.
• Linear search: Start from the start and keep going until you find the value.

Binary Search:

• Only use it on sorted lists.
• More efficient than a normal linear search.
• Start at the middle index and check if the value you're looking for is higher or lower.

Procedures:

• Named group of programming instructions with a purpose.
• May have input parameters and a return value.
• Parameters are input variables, and arguments specify the values of the parameters.
• Different parameters might lead to different outputs.
• When you call a procedure, goes to the procedure's statements with the input values given.
• Procedures can return a value or display (print) a value.

Procedures as Abstraction:

• Can abstract more complex topics.
• Helps code readability.

Subdivision:

• Separating sub-programs to help the program work better.
• Also referred to as modularity.

Libraries:

• Software libraries have built-in procedures that can be used in new programs.
• Simplify complex program creation.

APIs:

• Application program interfaces.
• Specifications on how to use procedures in the library and how they behave and how to use them.
• API documentation lists how to use different libraries.

Simulations:

• Abstractions of complex processes.
• Use values to represent a state of a phenomenon.
• Simulate events faster and cheaper than waiting for them in the real world.

Bias in Simulations:

• Can occur if data is skewed.
• Create random numbers in a program by doing this: random A, B, which will generate a random integer between A and B
• Generating random numbers simulates variability in the real world.

Algorithmic Efficiency:

• Decision problems have a yes or no answer.
• Optimization problems find the best solution possible.
• Efficiency is measured as computational resources used by n (size of input).
• Informally measured as the number of times a group of statements occurs.

Reasonable Time:

• Algorithms with polynomial efficiency or faster run in reasonable time.
• Constant, linear, square, or cube algorithms.
• Exponential or factorial algorithms can run in an unreasonable amount of time.

Heuristic Algorithms:

• Find a solution that may not always be accurate but should use a shortcut and will run faster.
• Use when optimal techniques will take way too long to use.

Decidable and Undecidable Problems:

• Decidable problems can be solved by an algorithm for all correct outputs.
• Undecidable problems cannot be solved by an algorithm for all possible inputs.

Skills for Algorithm Creation:

• Algorithms can be written in different ways for the same task.
• Examples: finding the minimum or maximum of two numbers, determining divisibility, finding the sum of a list.

Computer Systems and Networks

The Internet:

• Computing devices (computers, tablets, routers) run programs and connect to the internet.
• Computer networks are groups of connected devices capable of sending and receiving data.
• Paths are routes of directly connected computing devices.
• Routing is the process of finding the path from the sender to the receiver.
• The bandwidth of a computer network is the maximum amount of data that can be sent.
• Measured in bits per second.
• The internet is a computer network consisting of interconnected networks.
• Uses standardized and open communication protocols, scalable, and allows many devices to connect to it.

Access to the Internet:

• Depends on connecting to an internet-connected device.
• Routers connect devices to the internet.
• A protocol is an agreed set of rules specifying the behavior of a system.
• The internet uses open protocols, allowing users to add new devices.

Scalability and Data Transmission:

• The internet was designed to be scalable and meet demands.
• Information is passed through data streams.
• Data streams contain packets (chunks of data with metadata).
• Packets can arrive in order, out of order, or not at all.
• Protocols rearrange packets in order.

Protocols and World Wide Web:

• Examples of Protocols: IP, TCP, and UDP.
• WWW is a system of linked pages and programs.
• The WWW uses the internet and HTTP.

Fault Tolerance and Redundancy:

• Fault tolerance is a system that can support failures.
• The internet is designed to be fault-tolerant with abstractions from routing and transmitting data that can mitigate failure.
• Redundancy uses more components connected to a system so that if some routes fail, then the data will go through other routes and reach the destination that way.
• Introduce Redundancy by having many paths between two connected devices to mitigate failure in case the other parts fail.

Sequential, Parallel, and Distributed Computing:

• In sequential computing, operations are performed one at a time.
• In parallel computing, multiple computers work simultaneously.
• In distributed computing systems, many devices are used to run a program.
• Efficiency compares the time to complete the algorithm which should be the same across all the different systems to make sure the test is accurate.

Parallel Computing Efficiency:

• Consists of a parallel and a sequential portion that is more efficient than normal sequential computing.
• Distributed computing allows problems to be solved that cannot be solved by a single computer because of processing time or storage.
• Parallel computing is limited by the sequential portion.
• At some point, parallel computing would not benefit efficiency anymore.

Impacts of Computing

Benefits and Harmful Effects:

• Computing has both beneficial and harmful effects.
• Innovations may have unintended consequences.
• Computing can increase creativity in other fields like medicine, communications, and the arts.
• Programmers must consider the effects of their innovations.

The Digital Divide:

• Internet access varies between socioeconomic, geographic, and demographic characteristics.
• Need to address issues of access to improve equality and equity.
• The digital divide is affected by the actions of organizations and governments.

Bias in Computing:

• Computing innovations can have biases built in.
• Reflect programmer's biases.
• Important to have many people working on the project to try and reduce bias.
• Programmers should purposely try to reduce bias in the algorithms, and biases can be embedded at all levels of software development.
• Including diverse perspectives is important.

Crowdsourcing:

• Obtaining input from large numbers of people via the internet.
• Getting more points of view benefits an innovation.
• Offers more models of collaboration.

Citizen Science:

• Scientific research done by regular individuals.
• Contribute relevant data to research using their own computing devices.
• Normal citizens doing some research in the area.

Legal and Ethical Concerns:

• Material on a computer is considered intellectual property (IP).
• Easy access to digitized information raises concerns about IP.
• IP should be safeguarded (prevent piracy).
• Using material created by someone else without permission is plagiarism.
• Has legal consequences.
• Prevents people from unfairly using inventions that they can't.

Creative Commons, Open Source, and Open Access:

• Creative Commons: Public copyright license that enables free distribution of copyrighted work.
• Content creators give permission to share, use, and build on the work.
• Open Source: Programs are made freely available and may be redistributed or modified.
• Open Access: Online research output free of restrictions has that anyone can access freely.
• Improves digital access to information.
• Use of materials computed by someone else should always be cited.

Ethical Concerns:

• Computing innovations can raise ethical concerns.
  P
  Safe Computing:
• PII (Personally Identifiable Information): Information that defines someone.
• Technology allows the use and exploitation of information.
• Search engines can use search history for targeted marketing.
• Personal information like cookies can create knowledge about an individual.
• Information placed online may be used in unintended ways (be careful what you post).

Safe Computing Continued:

• Authentication: Protects devices from unauthorized access.
  • Multi-factor authentication.
  • Strong passwords are easy to remember but difficult to guess.
  • Use a combination of upper and lower case letters, symbols, and numbers.
  • Multi-factor authentication has the use of basic questions
• Encryption: Encoding data to prevent unauthorized access.
• Decryption: Decoding data.
• Symmetric Key Encryption: One key is used for both encryption and decryption.
• Public Key Encryption: A pair of keys are used (one public, one private).
• Think of public key encryption like a mailbox: the mail person cannot open anyone's box; he can just put the envelope in. Only you have the key to open the box and decrypt it.
  *
  Certificate Authorities:
• Issue digital certificates that validate the ownership of encryption keys.
  • Computer should have virus and malware detection.
  • Viruses: Malicious programs that gain access to a computer and run independently.
  • Malware: Damaging computing system with bad intention

Phishing:

• Technique where someone tries to trick a user into revealing personal information.
• They use that to access sensitive information.

Keylogging:

• Program records every keystroke made on a computer with the goal of gaining access to passwords.

Rogue Access Point:

• Intercepts data being sent over public networks, which is why it's important to be watchful of lurkers when you're sending important data over networks, as rogue access points may be present on many sites.

Malicious Links:

• Links can be disguised on web pages or in email messages. Can install malware downloads.

Create Task

• Coding project with specific requirements assigned by the teacher during class.

Important Definitions:

• Sequencing: Program runs from top to bottom in order, which is broken when you call a procedure.
• Selection: Boolean statements indicate which statements a program will execute.
• Iteration: Repeating code steps: for loops and while loops.