Unit 10: Algorithms

algorithm

a finite set of instructions that completes a task

iteration

a repetitive portion of algorithm which repeats a specified number of times or until a given condition is met

problem

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

selection

deciding which steps to do next

sequencing

putting steps in an order

binary search

a search algorithm that starts at the middle of a sorted set of numbers and removes half the data, repeating the process until the desired element is found or all elements have been eliminated

efficiency

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

linear search

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

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

decision problem

a problem with a yes/no answer (ex. is there a path from A to B?)

heuristic

provides a “good enough” solution to a problem where an actual solution is impractical or impossible

optimization problem

a problem with the goal of finding the “best” solution among many (ex. what is the shortest path from A to B?)

undecidable problem

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

distributed computing

a model in which programs are run by multiple devices

parallel computing

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

sequential computing

a model in which programs run in order, one command at a time

speedup

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