Lab 1, Page 2: Problem vs. Instance of a Problem

• A problem is a general description of a task that may (or may not) be solved algorithmically.
• An instance of a problem is one case of a problem, with specific inputs.

Lab 1, Page 2: Linear Search vs. Sequential Search

• An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten.
  
AAP-2.O.5
• A linear search (or sequential search) algorithm checks each element of a list in order, a process which takes linear time.

Lab 1, Page 3: Binary Search

A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.

Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.

Lab 1, Page 4: Efficiency

The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.

Lab 1, Page 5: Linear Time, Sublinear Time, Constant Time, and Quadratic Time

• An algorithm takes linear time the number of steps is proportional to the input size; doubling the input size doubles the time required.
• An algorithm takes sublinear time if the number of steps grows more slowly than the size.
• An algorithm takes constant time if it takes the same number of steps regardless of input size.
• An algorithm takes quadratic time if the number of steps is proportional to the square of the input size.

Lab 1, Page 5: Polynomial Time and Exponential Time

• An algorithm takes polynomial time if the number of steps is less than or equal to a power of the size of the input, such as constant (n⁰), sublinear, linear (n¹), quadratic (n²), or cubic (n³).
• An algorithm takes exponential time if the number of steps is proportional to an exponential function of the size of the input, such as 2ⁿ, 10ⁿ, etc., which is much slower than any polynomial.

Lab 1, Page 6: Decision Problem vs. Optimization Problem

• A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?").
• An optimization problem is one with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?").

Lab 1, Page 6: Decidable Problem vs. Undecidable Problem

A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.

An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

Lab 1, Page 8: Sequential Computing vs. Parallel Computing

This section covers two computational models:

• In sequential computing, operations are performed in order one at a time.
• In parallel computing, the program is broken into smaller steps, some of which are performed at the same time. Modern computers have multiple processors (2, 4, or 8) in a single computer, so you can do small-scale parallel processing on the machine on your desk.

Lab 1, Page 8: Distributed Computing

Distributed computing is a form of parallel computing that uses multiple computers (perhaps even spread out around the world).

Lab 1, Page 8: Processor

A processor is a piece of circuitry inside a computer that processes the instructions from computer programs.

Image credit: Wikipedia user Solipsist

Lab 1, Page 8: Speedup

Programmers refer to the speedup of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution:
\text{speedup} = \frac{\text{sequential time}}{\text{parallel time}}

Lab 2, Page 1: Simulations

Simulations are computer representations of real things or situations that vary over time. A simulation is an abstraction designed for a particular purpose.

Lab 3, Page 1: Data vs. Information

• Data are the values that computers receive from various sources, including human activity, sensors, etc.
• Information is the humanly-useful patterns extracted from data.

Data provide opportunities for identifying trends, making connections, and addressing problems. Information is the result of analyzing that data.

Lab 3, Page 1: Correlation

A correlation is a particular kind of information, namely a dependence between two variables. For example in the first picture here, as one variable goes up the other goes down. It's also a correlation when as one variable goes up or down the other changes in the same manner.

Lab 3, Page 1: Insight

Insight is a meaningful conclusion drawn from analyzing information.

Lab 3, Page 3: Records, Fields, and Columns

• A record is one row in a dataset (other than the first row, which contains the column headings). A single record might be the data for one student in your school, the data for one earthquake that happened, the data for one hospital in the U.S, or the data for one contact in your contact list. In other words, a record is a horizontal slice of the dataset.
• A field is one item of a record in a dataset. It might be one person's homeroom teacher, the magnitude of an earthquake in Los Angeles last week, the owner of one hospital in Chicago, or the phone number of one person in your contact list.
• A column is a list containing the data from one field for all records in a dataset. A column might be the homeroom teacher for every student in your school, the magnitude of every earthquake in the dataset, the owner of every hospital in the U.S., or the phone number of every person in your contact list. In other words, a column is a vertical slice of the dataset.

Lab 3, Page 3: Cleaning Data

Cleaning data is the process of making the data uniform without changing its meaning (such as replacing abbreviations, spellings, and capitalizations with the intended word or converting miles to kilometers). Programmers can use programs to filter and clean digital data, thereby gaining insight and knowledge.

Lab 3, Page 5: Classifying Data

Classifying data means distributing data into groups based on common characteristics.

Lab 3, Page 5: Mode

The mode of a data set is the value that appears most often in it.

Lab 3, Page 6: Metadata

Metadata are data about data. For example, the piece of data may be an image, while the metadata may include the date of creation or the file size of the image.

Lab 4, Page 1: Proof by Contradiction

A proof by contradiction is a two-step proof that a statement is false, which is done by

1. assuming the statement is true
2. based on that assumption, proving something known to be false (that is, showing the assumption creates a contradiction)

Lab 4, Page 1: Undecidable Statement vs Self-Contradictory Statement

An undecidable statement might be true or might be false; we don't know which.

A self-contradictory statement can be neither true nor false.

Lab 4, Page 2: Infinite Loop, Unsolvable Problem, and Undecidable Problem

An infinite loop is a sequence of computer instructions that repeats forever.

An unsolvable problem is one for which no algorithm can ever be written to find the solution.

An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value. Undecidable problems are a subcategory of unsolvable problems that include only problems that should have a yes/no answer (such as: does my code have a bug?).

Lab 7, Page 1

Multi-paradigm languages take ideas from several different approaches to programming style. Here are a few approaches you have seen in Snap!:

• Sequential programming, where operations are performed in order one at a time
• Functional programming, where computation is achieved by composing functions (reporter and predicate blocks) inside each other rather than sequencing (i.e., ordering) command blocks
• Object-Oriented programming, code is organized around objects (such as sprites), which may contain their own data or code, rather than around functions or sequenced instructions

Lab 7, Page 1

The syntax of a language is the notation it uses (punctuation, words reserved for specific purposes, etc.). Human languages have syntax, too: nouns vs. verbs, commas vs. semicolons, and so on.