AP Computer Science Principles Algorithm Quiz

not mine hehe

components of algorithm

sequencing, selection, iteration

sequencing

the order in which things will be done, or step by step

selection

choosing which items to process, usually done via conditional statement

iteration

repeating the above until the task is done

algorithm- inputs&outputs

if an algorithm is presented with the same inputs (and the hardware isn;t broken) it will give exactly the same outptus

algorithm 3 classes

decidable, undecidable, uncomputable

desirable algorithm

increases linearly with the size of the data set (doubling the data doubles the processing time)

when is an algorithm "reasonable"

if it runs into no worse than polynomial time

when is an algorithm "unreasonable"

since they are processed for small collections of data, after the first few data item the times become huge (PROCESSING TIME INCREASES)

decidable problem

one in which an algorithm can be constructed to answer "yes" or "no" for all inputs

undecidable problem

one where no algorithm can be created that gives a correct "yes or no" answer- have no algorithmic solution- no algorithm that solves all instances of the problem

repetition (iteration, loops) statements

allow us to execute a statement multiple times

REPEAT-TIMES

loops is best suited for executing a specific number of repetitions that can be determined in advance

REPEAT n TIMES

{

}

REPEAT-UNTIL

REPEAT UNTIL (condition)

{

}

body of REPEAT-UNTIL loop eventually...

makes the test condition true- if not, infinite loop

infinite loop

executes until the user interrupts the program

nested loops

the body of a loop can contain another loop, each time through the outer loop, the inner loop goes through its full set of iterations

unbounded iteration

when you cannot determine how many times you want to execute the look body, use REPEAT-UNTIL statement

bounded iteration

when you can determine how many times you want to execute the loop body, use a REPEAT-TIMES statement

list

ordered sequence of vales

list elements

values in lists

number of items in a list can be determined by using the LENGTH () function:

LENGTH (scores)

linear/sequential search

examines each item of the list in turn until the desired item is found

FOR-EACH loop

used to access each item in a list in turn

common index variable

i

general format for processing all items in list

i - 1

REPEAT LENGTH (scores) TIMES

{

item specific code

i - i + 1

}

no score value should exceed

100

binary search

more efficient than linear search but can be only performed on a list where the items are already in order, examines the middle item and moves left if the desired item is less than the middle, and right if the desired item is great- process repeats until item is found