AP CSP Programming Part 2

Vocabulary

100

a named group of programming instructions that may have parameters and return values

procedure (aka function)

200

input variables of a procedure. 

parameter

300

specify the values of the parameter when the procedure is called

argument

400

an estimation of the amount of computational resources used by an algorithm (expressed as a function of the size of the input)

efficiency

500

the subdivision of a computer program into separate subprograms 

modularity

Searching

100

Where does a binary search begin in a list?

In the middle

200

Data must be ___________ in order to use the binary search algorithm

sorted

300

What is the maximum number of iterations required for a list that consists of 100 values?

7

400

What is it called when you do a linear search through a list?

traversal

500

What type of loop is used to complete a linear search of a list?

for loop

Efficiency

100

a decision problem for which an algorithm can be written to produce a correct output for all inputs

decidable problem

200

Algorithms with a polynomial efficiency or slower (constant, linear, square, cube etc) are said to run in....

a reasonable amount of time

300

a decision problem for which no algorithm can be constructed that is always capable of of providing a correct answer.

undecidable problem

400

Algorithms with exponential or factorial efficiencies run in ....

an unreasonable amount of time

500

an approach to a problem that produces a solution that is "good enough" when the optimal solution is impractical

heuristic

Lists

100

The first element in a list (in pseudocode not javascript)

index 1 

200

What happens to the items in a list when the code below is run? 

INSERT (myList, 4, "cucumbers");

Inserts cucumber at index 4 of myList AND shifts values in the list that are greater than or equal to 4 to the right

300

What does the code segment below do?

myList.length

finds the length of the list myList

400

What syntax word is used to add an element to a list?

APPEND

500

Given the list below, what command must be added to remove the value of 10 from the list? (remember pseudocode!!)

var myList = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];

REMOVE(myList, 5);

Hodge Podge

100

this command is used in a program when a different value is produced during each execution

random value

200

this command is used to assign a value to the procedure when it is called

return

300

a general description of a task that can or cannot be solved algorithmically

problem

400

Linear or Binary: Which is more efficient when searching a sorted list

Binary

500

A real world representation that uses varying sets of values to reflect the changing state of a phenomenon.

simulation