unit 6 Flashcards
problem
a general description of a task that can (or cannot) be solved by an algorithm
algorithm
a finite set of instructions that accomplish a task; requires sequencing, selection, and iteration
sequencing
putting steps in 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 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 pf numbers and removes half of the data; this process repeats until the desires value is found or all elements have been eliminated
binary search in terms of binary numbers
the steps are the amount of bits when the input is represented in binary
input= 15
binary= 1111
steps= 4
example of linear search
given a list of numbers, and have to choose the predetermined number
you give the answer by going through each number chronologically
example of binary search
given a list of numbers, and have to choose the predetermined number
you give answer by taking the middle number and see if the predetermined answer is above or below. take middle number again and ask above or below
polynomial efficiency
any algorithm whose efficiency includes n^2, n^3, n^4, etc
polynomial pattern
(n^2-n)/2
ex. x=2, y=1; x=3, y=3; x=4, y=6
the increase between two outputs goes up by one to get next output only when input goes up by 1
exponential efficiency
an algorithm whose efficiency includes an 2^n, 3^n, 4^n etc.
exponential pattern
(2^n)-1
ex. n=2, y=3; n=3, y=7
also the output number of bits represented in binary is input value
the increase between two outputs gets doubled to get next output only when input goes up by 1
reasonable time
algorithms with polynomial efficiency or lower (constant, linear, square, cube, etc) are said to run in a reasonable amount of time
logs are reasonable too
unreasonable time
algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time
factorial
n!
multiply all whole numbers from the given number down to the number 1
ex. 4!= 4 x 3 x 2 x1 = 24
decision problem
“Is there a path?”
optimization problem
“what’s the shortest path?”
some can be unreasonable as there is not an algorithm that can solve the problem in a reasonable time, so we come up with a heuristic solution
heuristic
provides a “good enough” solution to a problem when an actual solution is impractical or impossible
undecidable problem
a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer
halting problem
is is possible to write a program that determines whether another program halts?
- no it doesnt exist
sequential computing
programs run in order, one command at a time