unit 6

Question 1

problem

Answer 1

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

Question 2

algorithm

Answer 2

a finite set of instructions that accomplish a task; requires sequencing, selection, and iteration

Question 3

sequencing

Answer 3

putting steps in order

Question 4

selection

Answer 4

deciding which steps to do next

Question 5

iteration

Answer 5

doing some steps over and over

Question 6

efficiency

Answer 6

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

Question 7

linear search

Answer 7

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

Question 8

binary search

Answer 8

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

Question 9

binary search in terms of binary numbers

Answer 9

the steps are the amount of bits when the input is represented in binary
input= 15
binary= 1111
steps= 4

Question 10

example of linear search

Answer 10

given a list of numbers, and have to choose the predetermined number
you give the answer by going through each number chronologically

Question 11

example of binary search

Answer 11

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

Question 12

polynomial efficiency

Answer 12

any algorithm whose efficiency includes n^2, n^3, n^4, etc

Question 13

polynomial pattern

Answer 13

(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

Question 14

exponential efficiency

Answer 14

an algorithm whose efficiency includes an 2^n, 3^n, 4^n etc.

Question 15

exponential pattern

Answer 15

(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

Question 16

reasonable time

Answer 16

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

Question 17

unreasonable time

Answer 17

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

Question 18

factorial

Answer 18

n!
multiply all whole numbers from the given number down to the number 1
ex. 4!= 4 x 3 x 2 x1 = 24

Question 19

decision problem

Answer 19

“Is there a path?”

Question 20

optimization problem

Answer 20

“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

Question 21

heuristic

Answer 21

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

Question 22

undecidable problem

Answer 22

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

Question 23

halting problem

Answer 23

is is possible to write a program that determines whether another program halts?
- no it doesnt exist

Question 24

sequential computing

Answer 24

programs run in order, one command at a time

Question 25

parallel computing

Answer 25

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

Question 26

distributed computing

Answer 26

programs are run by multiple devices

Question 27

speedup

Answer 27

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

Question 28

does speedup reach a limt?

Answer 28

yes
speed up is never equal to the number of processor
some portions of the algorithm cant be made parallel
each additional processor helps a little less.