AP Comp Sci Principles assessment- Unit 6

Problem

Problem

a general description of a task that can (or cannot) be solved with an algorithm

Algorithm

a finite set of instructions that can accomplish a task

Sequencing

putting steps in an order

Selection

deciding what steps to do next

Iteration

doing some steps over and over

Efficiency

a measure of how many steps are needed to complete an algorithm

Linear Search

a search algorithm which checks each element of a list, in order, until the desired value is found or all elements in the list have been checked

Binary Search

a search algorithm that starts at the middle of a sorted set of numbers and removes half of the data; this process repeats until the desired value is found or all elements have been eliminated

Reasonable Time

algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time

Unreasonable Time

algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time

n²

reasonable

2^n

unreasonable

Heuristic

provides a “good enough” solution to a problem when an actual solution is impractical for impossible

Undecidable Problem

a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer

Sequential Computing

programs run in order, one command at a time

Parallel Computing

programs are broken into small pieces, some of which are run simultaneously

Distributed Computing

programs are run by multiple devices

Speedup Time

the time used to complete a task sequentially divided by the time to complete a task in parallel