Unit 3: Algorithms and Programming

What is the value of x after the following code segment is executed? x ← 5 x ← x + 3 x ← x * 2

What is the output of the following code segment? a ← 10 b ← 20 a ← b DISPLAY(a)

What are the values of a and b after the following code segment? a ← 3 b ← 7 temp ← a a ← b b ← temp

What is displayed by this code segment? nums ← [4, 7, 2, 9, 1] max ← nums[1] FOR EACH num IN nums { IF (num > max) { max ← num } } DISPLAY(max)

What is displayed after executing this code? result ← 0 FOR i ← 1 TO 5 { result ← result + i } DISPLAY(result)

A list contains n elements. A linear search is used to find a specific value. What is the maximum number of comparisons needed?

A sorted list contains 1024 elements. Using a binary search, what is the maximum number of comparisons needed to find a specific value?

Which of the following is a key requirement for binary search to work correctly?

What is displayed by the following code? PROCEDURE double(x) { RETURN x * 2 } result ← double(double(3)) DISPLAY(result)

Which algorithm has a reasonable (polynomial) running time?

What is displayed by the following code? list ← [1, 2, 3, 4, 5] FOR EACH item IN list { IF (item MOD 2 = 0) { DISPLAY(item) } }

What is the output of the following code? list ← [3, 1, 4, 1, 5] n ← LENGTH(list) FOR i ← 1 TO n - 1 { IF (list[i] > list[i + 1]) { temp ← list[i] list[i] ← list[i + 1] list[i + 1] ← temp } } DISPLAY(list)

What is displayed by the following code? PROCEDURE mystery(a, b) { IF (a > b) { RETURN a } ELSE { RETURN b } } DISPLAY(mystery(mystery(3, 5), mystery(4, 2)))

An algorithm is designed to work on a list of n items. Which of the following running times would be considered "unreasonable" for large values of n?

What is displayed after the following code? list ← [10, 20, 30] APPEND(list, 40) REMOVE(list, 2) DISPLAY(list)

A robot is in a grid and needs to reach a goal. The robot can move forward, turn left, and turn right. Which of the following is NOT a valid approach to solve this problem?

What does the following procedure compute? PROCEDURE mystery(n) { count ← 0 REPEAT UNTIL (n = 0) { n ← n / 2 (integer division) count ← count + 1 } RETURN count }

A programmer writes two versions of a search algorithm. Version A takes 2n steps, and Version B takes n² steps. For what values of n does Version A perform fewer steps?

What is displayed by the following code? list ← [5, 3, 8, 1, 9, 2] result ← list[1] FOR EACH item IN list { IF (item < result) { result ← item } } DISPLAY(result)

Which of the following is true about the efficiency of algorithms?

What is a "heuristic" approach to solving a problem?

What is displayed by the following code? count ← 0 FOR i ← 1 TO 4 { FOR j ← 1 TO 3 { count ← count + 1 } } DISPLAY(count)

What is a simulation?

What is displayed after the following code? x ← 10 IF (x > 5) { x ← x - 3 } IF (x > 5) { x ← x - 3 } DISPLAY(x)

If a = true and b = false, what is the value of (a AND b) OR (NOT b)?

What is a primary benefit of using procedures (functions) in programming?

In the AP CSP pseudocode, what does list[3] refer to if list = [10, 20, 30, 40]?

What is the value of 17 MOD 5?

In the AP CSP robot pseudocode, a robot is at position (1,1) facing right on a 4×4 grid. After executing MOVE_FORWARD() twice and ROTATE_LEFT() once, the robot is:

What is displayed?\nx ← 15\nIF (x > 20) { DISPLAY("high") }\nELSE { IF (x > 10) { DISPLAY("medium") } ELSE { DISPLAY("low") } }

What does this procedure return when called as mystery(5)?\nPROCEDURE mystery(n) { result ← 0 REPEAT n TIMES { result ← result + n } RETURN result }

What is displayed after this code runs?\nlist ← [3, 7, 1, 9, 4]\nREMOVE(list, 2)\nAPPEND(list, 5)\nDISPLAY(LENGTH(list))

In AP CSP pseudocode, RANDOM(1, 6) generates:

An algorithm that checks every element in a list of n items to find a target has a time complexity described as:

Binary search requires that the data be:

To swap the values of variables a and b, which sequence works correctly?

An undecidable problem is one for which:

A heuristic approach to problem-solving:

Simulations are useful because they:

What is displayed?\nnums ← [2, 4, 6, 8]\nsum ← 0\nFOR EACH num IN nums { sum ← sum + num }\nDISPLAY(sum)

What is displayed?\nfirst ← "Hello"\nsecond ← "World"\nDISPLAY(CONCAT(first, " ", second))

How many times is DISPLAY called?\nREPEAT 3 TIMES { REPEAT 4 TIMES { DISPLAY("*") } }

An algorithm that takes 2^n steps for an input of size n runs in:

What is displayed?\nPROCEDURE triple(x) { RETURN x * 3 }\nresult ← triple(triple(2))\nDISPLAY(result)

Which best describes how computing enables citizen science?

Which code correctly finds the minimum value in a list?\nnums ← [5, 3, 8, 1, 6]

Abstraction in programming allows developers to:

After the following code, what is list?\nlist ← [1, 2, 3]\nINSERT(list, 2, 10)\nAPPEND(list, 20)

After executing:\na ← 5\nb ← a\na ← 10\nWhat is the value of b?

What is displayed?\ncount ← 0\nlist ← [3, 7, 2, 8, 5, 1]\nFOR EACH item IN list { IF (item > 4) { count ← count + 1 } }\nDISPLAY(count)

A robot starts at position (1,1) facing right in a 5×5 grid. What does this code do?\nREPEAT UNTIL (NOT CAN_MOVE(forward)) { MOVE_FORWARD() }

What is displayed?\ni ← 1\nREPEAT 4 TIMES { DISPLAY(i) i ← i + 2 }

What does this code produce?\noriginal ← [10, 25, 5, 30, 15]\nfiltered ← []\nFOR EACH val IN original { IF (val ≥ 15) { APPEND(filtered, val) } }\nDISPLAY(filtered)

Which expression is logically equivalent to NOT (a AND b)?

What is displayed?\nx ← 1\nREPEAT 5 TIMES { x ← x * 2 }\nDISPLAY(x)

What is the difference between RETURN and DISPLAY in a procedure?

What is displayed?\nx ← 64\ncount ← 0\nREPEAT UNTIL (x < 2) { x ← x / 2 count ← count + 1 }\nDISPLAY(count)

What is displayed?\nage ← 16\nhasPermit ← true\nIF (age ≥ 16 AND hasPermit) { DISPLAY("Can drive") }\nELSE { DISPLAY("Cannot drive") }

Consider the following pseudocode: result ← 0 FOR EACH item IN [3, 7, 2, 9, 4] { IF (item > 5) { result ← result + item } } DISPLAY(result) What is displayed?

A programmer writes a procedure to search a sorted list: PROCEDURE search(list, target) { low ← 1 high ← LENGTH(list) REPEAT UNTIL (low > high) { mid ← (low + high) / 2 IF (list[mid] = target) { RETURN mid } ELSE IF (list[mid] < target) { low ← mid + 1 } ELSE { high ← mid - 1 } } RETURN -1 } The list has 1024 elements. What is the maximum number of comparisons needed to find a target or determine it is not in the list?

Consider the following pseudocode: x ← 1 REPEAT 4 TIMES { x ← x * 2 x ← x + 1 } DISPLAY(x) What is displayed?

Two algorithms solve the same problem. Algorithm A runs in n² steps and Algorithm B runs in n × log₂(n) steps, where n is the input size. For n = 8, Algorithm A takes 64 steps. For what approximate input size n would Algorithm A take 100 times longer than Algorithm B?

The following procedure is intended to return true if a list contains any duplicate values. \nPROCEDURE hasDuplicate(list) { FOR EACH item1 IN list { FOR EACH item2 IN list { IF (item1 = item2) { RETURN true } } } RETURN false } \nWhat is wrong with this procedure?

A list of 1000 names is sorted alphabetically. Using binary search, what is the maximum number of comparisons needed to determine that a name is NOT in the list?

Consider the following code segment. \nresult ← 0\nFOR EACH num IN [3, 7, 2, 8, 5] { IF (num > 4) { result ← result + num } }\nDISPLAY(result) \nWhat is displayed?

An algorithm has a running time that doubles each time the input size increases by 1. If the algorithm takes 2 seconds for an input of size 10, approximately how long does it take for an input of size 20?

A robot is in the bottom-left corner of a 4×4 grid and needs to reach the top-right corner. The robot can only move right or up. How many different paths can the robot take?

A programmer writes two versions of a search algorithm. Version A uses linear search and Version B uses binary search on a sorted list. For which list size will the performance difference be MOST noticeable?