APCSP Review: Abstraction, Data, Algorithms, and Internet

Abstraction

Reduces information and detail to facilitate focus on relevant concepts.

Data Representation Levels

Data is represented with multiple levels of abstraction.

Bits

At the lowest level, all digital data is represented by bits.

Byte

A byte is 8 bits.

Nibble

A 4 bits are called a nibble because it's half a byte.

Binary

All computational data (at the lowest level) is represented using binary (base 2) numbers.

Hexadecimal

Base 16 can be used to represent binary data because it makes it shorter with one hexadecimal digit representing 4 bits.

Base Conversions

Numbers can be converted from one base to any other base.

Overflow Errors

Finite representation of integers can lead to overflow errors when numbers exceed the size of the representation.

Round Off Errors

Finite representation of floating point values can lead to round off errors and other issues.

High Level Programming Language

Provides more abstractions to help the programmer, often translated into a lower level language for the computer to execute.

Logic Gate

A hardware abstraction that represents a Boolean function (like and/or).

Models and Simulations

Simplified representations that eliminate unnecessary detail; can reduce the cost of physical testing.

Analogue Data

Has values that change smoothly; an example is music.

Digital Data

Has discrete values.

Sampling

Approximates analogue data by sampling at frequent intervals and storing information at that interval.

Computer Programs

Used to process information and gain valuable insight.

Collaboration

Facilitated by online collaborative tools to understand and share information.

Metadata

Data about the data; for instance, sender, receiver, and time of a text message.

Big Data

Involves significant challenges in storing, processing, curating, structuring, and securing large data sets.

Scalability

Critical when data sets are large; techniques used to manipulate a data set must change when the size of the data set changes scale.

Compression

Reducing the size of the data using computational techniques

Lossless compression

Reducing the size of the data in such a way that the original data can be reconstructed exactly from the compressed version. Example - zipping a file is lossless compression. The file can be reproduced exactly as it was.

Lossy compression

Reducing the size of the data in such a way that the original data cannot be reconstructed exactly from the compressed version. Example - reducing the sample rate of a recording will reduce the size of the file, but some information is lost.

Data representations

Involve storage, security and privacy concerns. These issues create trade-offs when storing and transmitting data.

Storage Media

Choices affect how the data can be manipulated and the costs of doing so.

Algorithm

Precise sequence of instructions for processes to accomplish something.

Sequencing

Executing steps of an algorithm in the order the statements are given.

Iteration

The repetition of part of an algorithm.

Selection

Using a Boolean (true or false) condition to determine what part of an algorithm is used.

Limitations of Algorithms

Many problems can be solved in 'Reasonable Time'. Reasonable time (for CSP purposes ONLY!) is any polynomial amount of time.

Undecidable problems

Problems that CANNOT be solved AT ALL (even in 'unreasonable time') for all inputs.

Halting Problem

An undecidable problem that can have solutions for certain inputs, but CANNOT be solved for some inputs.

Evaluating Algorithms

The efficiency (time and space requirements) of an algorithm can be evaluated by reasoning mathematically about the algorithm.

Correctness of an algorithm

Determined by formal mathematical reasoning about the algorithm.

Searching Algorithms

You should be familiar with linear and binary search.

Linear search

Slower (in general), but can be used with any list.

Binary search

Faster (in general), but the list MUST BE SORTED.

Iterative Development

An iterative development process (creating and testing small segments of code) helps to develop a correct program.

Documentation

Useful when working individually or collaboratively to help develop and maintain useful programs.

Programmer

Someone who designs, implements, tests, debugs, and/or maintains programs.

Collaboration

Most programs outside a classroom setting are written collaboratively.

Algorithm

A precise set of instructions to accomplish some task, written in a programming language for execution by a computer.

Procedures

An abstraction of a named group of programming instructions.

Parameters

The input(s) for a procedure.

Concatenation

Combining two strings into one string.

Substring

Making part of one string a new string.

Integers and floating point numbers

Represented differently in computers; integers have a constrained range due to storage limitations, and floating point representations have finite precision.

Errors

Issues in code that can be categorized as syntax errors, logic errors, or runtime errors.

Syntax Error

An error in the code where the rules of the programming language were not followed.

Logic Error

An error in a program that causes it to behave unexpectedly.

Runtime Error

An error that appears during the execution of the program.

Lists

A way of storing a group of data values, with operations to add, remove, sort, and search.

API (Application Program Interface)

An interface that connects hardware/software to another piece of hardware/software.

Program Style

Meant to make it easier to read, understand, and debug a program, including line length and name formats.

Test Case

An example of possible inputs to a program along with the correct result.

Arithmetic Operations

Operations like add, subtract, multiply, divide, and exponentiation included in most programming languages.

Boolean Logic and Operations

Fundamental to programming, including operations like and, or, and not.

Numeric Operators

Basic arithmetic operators of add, subtract, multiply, and divide, including MOD for remainder in integer division.

ADT (abstract data type)

Allows operations to be performed without knowing exactly what type of data they are being performed on.

The Internet

A network of networks that connects computing devices all over the world.

DNS (Domain Name System)

The hierarchical system that is used to connect a domain name (like google.com) to an IP address that can be used to communicate over the Internet.

Protocols

Protocols are the procedures that are used to send data. The Internet functions as well as it does largely because of the standardization of protocols.

IETF (Internet Engineering Task Force)

The group that selects develops protocols for use with the Internet.

TCP (Transmission Control Protocol)

Deals with error checking and ordering IP packets.

UDP (User Datagram Protocol)

Faster than TCP but without the error checking.

IP (Internet Protocol)

Gets packets to the right place.

SMTP (Simple Mail Transfer Protocol)

Breaks email into packets.

HTTP (HyperText Transfer Protocol)

Breaks webpage into packets.

IP Address

Each device connected to the Internet has an IP Address. IP stands for Internet Protocol, and is used to get a packet from to where it needs to go.

IPv6

A new version of IP created to handle the number of devices connected to the Internet.

Bandwidth

The bit rate (bits per second) of the amount of data that can be sent in a fixed amount of time.

Latency

The amount of time elapsed between the transmission and receipt of a request.

Trust Model

The trust model of the Internet involves trade-offs, such as assuming webpage requests are legitimate, which allows for DDoS attacks.

Cyber Security

Attempting to prevent keep yourself and information you consider private safe in the cyber world.

Phishing

Attempting to gain private information by pretending to be someone to whom private information is regularly disclosed.

DDoS (Distributed Denial of Service)

Preventing legitimate users from accessing an online resource by using many computers to request resources from those servers.

Cryptography

Cryptography is used to keep information private and is based on advanced mathematics.

Asymmetric (Public Key) Encryption

Each person has a Public and a Private Key; the public key is shared and the private key is NEVER shared.

Symmetric (Private Key) Encryption

There is only one key (a private key that is never shared) used to both encrypt and decrypt the data.

Digital signatures

CAs (Certificate Authorities) issue digital certificates which validate the ownership of encrypted keys.

Certificate Authorities (CAs)

Organizations that verify the ownership of a public key.

Private Key

A key used by the recipient to decrypt a message.

Public Key

A key used to encrypt a transmission that can only be decrypted with the corresponding private key.

Certificate Authority (CA)

An entity that verifies the identity of the sender in a public key infrastructure.

VPN (Virtual Private Network)

A service that provides a secure, encrypted connection to a server, allowing access to websites and information anonymously.

Cookies

Small files stored by websites on a user's computer to enhance user experience, which can also raise privacy concerns.

Digital Millennium Copyright Act (DMCA)

An act that manages copyrights in a digital world and exempts intermediaries from liability for infringement using their services.

Creative Commons

A license that simplifies sharing of work with various permissions for use.

Digital Divide

A social and economic gap between those with access to computers and the internet and those without.

Moore's Law

An observation that processing speed doubles approximately every 2 years.

Cloud Computing

Performing tasks remotely via the internet that could be done locally.

Internet of Things

An evolution of the internet connecting various devices beyond just computers.

Crowd Sourcing

Using the internet to allow many people to accomplish a task instead of hiring employees.

Citizen Science

Using crowd sourcing to assist in scientific research, often involving public participation.

Data Mining

The process of finding useful patterns or information within large datasets.

Machine Learning

A form of artificial intelligence that recognizes patterns in data that are difficult to discover otherwise.

Privacy Concern

Issues related to the potential for unauthorized access to personal information.

Intermediaries

Entities that facilitate communication or transactions between parties, often exempt from liability under DMCA.

Digital Rights Management (DRM)

Technologies used to control the use of digital content and devices after sale.