Unit 3: Algorithms & Programming
CS Principles · Unit 3 · Paper 2

Algorithms & Programming unit test

A test on this unit alone, marked as a percentage and a letter grade — for the test your class is actually sitting, rather than for May. Answer everything, then submit once: seeing the answer to question 3 before attempting question 4 makes the final percentage meaningless.

Paper 1Paper 2Paper 3
Each paper is built from this unit’s 56 terms and is the same for everyone, so a teacher can assign “Unit 3, Paper 2” and every student sits the identical test. Multiple choice is marked objectively; the written sections you mark yourself against the model answer and rubric.
Suggested time 33 min 30 points0/17 attempted
1

Decidable vs undecidable

2

Variable

3

List indexing in AP pseudocode

4

Binary search

5

INSERT

6

REPEAT UNTIL

7

FOR EACH loop

8

Sequential computing

9

Undecidable problem

10

Nested conditional

11

NOT

12

Simulation

Short answer 1. Define or explain: Heuristic

3 pts

Short answer 2. Define or explain: Speedup

3 pts

Short answer 3. Define or explain: Algorithm

3 pts

Short answer 4. Define or explain: Why binary search needs a sorted list

3 pts

Free response

6 pts

A programmer writes the following procedure, intending it to return the number of values in a list that are greater than a given threshold. List indexes begin at 1. PROCEDURE countAbove(values, limit) { count ← 0 i ← 1 REPEAT UNTIL (i > LENGTH(values)) { IF (values[i] > limit) { count ← count + 1 } } RETURN(count) }

Trace the call countAbove([5, 12, 3], 4) and describe exactly what happens.

Identify the error and state the single change that fixes it.

After the fix, state what countAbove([5, 12, 3], 4) returns and what countAbove([1, 2], 9) returns.

Explain how you would test the corrected procedure to be confident it is right, and describe how the number of steps grows as the list gets longer.