Bubble sort

Bubble sort is better when the list is small. You start at the start of the list comparing the numbers

adjacent to each other, keeping the highest number.

Continue to do this until all numbers are sorted.

Bubble sort (advantages)

It is very simple and easy to do, especially when dealing with short lists. The answer __________s

to the top.

Merge sort

Merge sort is when you keep dividing up the numbers and then you start '_______' them together

step by step.

When you are splitting up the numbers you do not have to order them, only when you are

'_________' them.

Binary search

______________works with a sorted list. You split the numbers by 2. If you have a number between

1-100,

you continue to divide by 2 and then guess higher or lower. In a

______________________________ it would take 7 passes to guess the correct answer.

Binary search (advantages)

_________________________ is good since it is the simple process of elimination and the simple

process of halving.

This is good when you are dealing with average numbers such as 100 or 50 or 20, etc...
Sequential search

Used to search an unordered list by going through each item.

Sequential search (disadvantages)

This search is not the best because it is one of the slowest searches since it goes through every

item,

such as looking for a phone number in a phone book if you don't know the person's name.

Bucket sort

You put numbers into their correct categories, such as all of the 2's together, then 3's, and so on,

and then sort them into the correct order.

If using a binary sort, how many guesses would it take to guess a number between 1-250?

Efficiency

How long it takes to arrange the values in order.

Tractable

Can be solved within a reasonable time.

Intractable

A problem that is practically impossible to solve. They can be solved but are too inefficient to solve

when the number of inputs grows large.

There are only inefficient algorithms.

Halting Problem
A theory by Alan Turing that there are undecidable problems that cannot be solved.

List-Index

The position of a particular element in a list. Most programming languages start indexes at 0,

meaning the first element is considered to be at index 0.

App Inventor starts indexes at 1, meaning the first element in a list is at index 1.

Algorithm

A precise sequence of instructions for processes that can be executed by a computer.

Binary

A way of representing information using only two options, ones and zeros, typically.

Bit

A contraction of "Binary Digit". A bit is the single unit of information in a computer, typically

represented as a 0 or 1.

Byte

8 bits.

Citizen Science

Lots of people help with a scientific project, like asking everyone around the world to count the

butterflies they see one day.

GIF

Bitmap image format using lossless data compression.

Gigabyte (GB)

1000 MB or a billion bytes.

Heuristic

A problem-solving approach (algorithm) to find a satisfactory solution where finding an optimal or

exact solution is impractical or impossible.

Traveling Salesperson Problem. Anti-virus software.

Image

A type of data used for graphics or pictures.

JPG

Commonly used method of lossy compression for digital images.

Kilobyte (KB)

1000 bytes.

List

A generic term for a programming data structure that holds multiple items.

Lossless Compression

A data compression algorithm that allows the original data to be perfectly reconstructed from the

compressed data.

Lossy Compression

A data compression method that uses inexact approximations, discarding some data to represent

the content. Most commonly seen in image formats like .jpg.

Megabyte (MB)

1000 KB or 1,000,000 bytes.

Metadata

Data that describes other data. For example, a digital image may include metadata that describe the

size of the image, number of colors, or resolution.

Models and Simulations

A program that replicates or mimics key features of a real-world event in order to investigate its

behavior without the cost, time, or danger of running an experiment in real life.

Modulo

A mathematical operation that returns the remainder after integer division. Example: 7 MOD 4 = 3.

Petabyte (PB)

1000 TB or a quadrillion bytes.

Pixel

Short for "picture element" it is the fundamental unit of a digital image, typically a tiny square or dot

which contains a single point of color of a larger image.

PNG

A raster graphics file format that supports lossless data compression.

RGB

The RGB color model uses varying intensities of (R)ed, (G)reen, and (B)lue light to reproduce a
broad array of colors.

Undecidable

A problem that is so difficult, we can't ever create an algorithm that would be able to answer yes or

no for all inputs,

like determining if a user's program run on some input would always stop and not run forever

(Halting Problem).

Modeling

Process of representing a real-world object or phenomenon as a set of mathematical equations.

Raster

The rectangular area of a display screen actually being used to display images.

Index

Lists are _________ed, or numbered, starting with 1, which means that you can retrieve any item

from a list by giving its ________.

Parity bit

A ____________ is a bit that is added as the leftmost bit of a bit string to ensure that the number of

bits that are 1 in the bit string are even or odd.

What would you add to the left of this even parity?

_000 1110

0
What would you add to the left of this odd parity?

_000 0111

Render

Refers to the process of adding realism to computer graphics by adding 3-D qualities, such as

shadows and variations in color and shade.

Binary Number

A number written in the binary system, a system that uses only two digits, 0s and 1s.

Binary Sequence

A sequence of 0s and 1s.

Base of a Number System

The number of distinct digits or symbols used to represent numbers in that system. Our decimal

system is base-10 because it uses 10 digits, 0 through 9.

Binary Number System

A positional number system using base 2.

Octal Number System

A positional number system using base 8.

Hexadecimal Number System

A positional number system using base 16.

PRNG (Pseudo Random Number Generator)

An algorithm that generates a sequence of numbers that seems random but is actually completely

predictable.

Deterministic

Always resulting in a particular pattern.

Nondeterministic

A program that always behaves differently, even when run multiple times with the same input.

Seed

First number in a pseudorandomly selected sequence.

Modulus

Remainder division.

Decidable Problem

A problem in which an algorithm can be constructed to answer "yes" or "no" for all inputs.

Undecidable Problem

Where no algorithm can be made that always leads to a correct yes or no answer.