Computer Science Unit 10 notes

under big idea 5

Problem

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

Algorithm

a finite set of instructions that accomplish a task

Sequencing

putting steps in an order

Selection

deciding which 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 checking each element in order until the desired value is found

Binary Search

a search algorithm starting in the middle and eliminating half the data until the desired value is found

Reasonable Time

algorithms with polynomial efficiency or lower running in a reasonable amount of time

Unreasonable Time

algorithms with exponential or factorial efficiencies running in an unreasonable amount of time

Heuristic

provides a "good enough" solution when an actual solution is impractical or impossible

Decision Problem

a problem with a yes/no answer

Optimization Problem

a problem aiming to find the "best" solution among many

Undecidable Problem

a problem with no algorithm always providing a correct yes/no answer

Sequential Computing

programs running one command at a time in order

Parallel Computing

breaking programs into small pieces, running some simultaneously

Distributed Computing

running programs on multiple devices

Speedup

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