That y8 kid 🤣 - bot · guest · Algorithmics (HESS)

01 A* uses f(n) = g(n) + h(n). Which frontier node should it expand next?

A Node A: g = 2, h = 10, f = 12 f = 12; another node has a smaller f.

B Node B: g = 6, h = 5, f = 11 f = 11; another node has a smaller f.

C Node C: g = 9, h = 1, f = 10 f = 10; this is minimal.

D Node D: g = 4, h = 8, f = 12 f = 12; another node has a smaller f.

Written for icaijy.com · U4 AOS2 · A* search · answered at 100 ms

02 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…255. How many values are inspected when searching for 127?

A 8 The midpoint trace reaches 127 after 8 inspection(s).

B 2 Does not fit this requirement.

C 6 Does not fit this requirement.

D 5 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 100 ms

03 A transport app must represent cities and the roads joining them. Which ADT is most suitable?

A graph A graph models entities and relationships.

B stack Does not fit this requirement.

C dictionary Does not fit this requirement.

D set Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · ADTs · answered at 100 ms

04 A max-priority queue removes the numerically highest priority first. Which job is removed?

A Job A (priority 6) A higher-priority job is present.

B Job B (priority 13) This has the highest priority.

C Job C (priority 9) A higher-priority job is present.

D Job D (priority 4) A higher-priority job is present.

Written for icaijy.com · U3 AOS1 · Priority queues · answered at 100 ms

05 Assume constant-time primitive operations. What is the tightest Big-O bound for: While n > 1: n ← floor(n/2)

A \(O(n)\) Does not fit this requirement.

B \(O(n \log n)\) Does not fit this requirement.

C \(O(\log n)\) Repeated halving takes logarithmically many steps.

D \(O(1)\) Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Time complexity · answered at 100 ms

06 Ignoring constant factors, approximately how many primitive operations does an \(O(n \log_2 n)\) algorithm perform when n = 1,000,000?

A about 20 million Substitute n into the stated growth function.

B about 1 quadrillion Does not fit this requirement.

C about 1 thousand Does not fit this requirement.

D about 1 million Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Practical complexity · answered at 100 ms

07 The Halting Problem asks whether

A a program eventually stops on a given input The accepted statement is: a program eventually stops on a given input.

B a graph is connected Does not fit this requirement.

C a model is unbiased Does not fit this requirement.

D two arrays have equal length Does not fit this requirement.

Written for icaijy.com · U4 AOS3 · Computability · answered at 100 ms

08 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…127. How many values are inspected when searching for 95?

A 7 The midpoint trace reaches 95 after 7 inspection(s).

B 1 Does not fit this requirement.

C 3 Does not fit this requirement.

D 6 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 100 ms

09 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…31. How many values are inspected when searching for 23?

A 4 Does not fit this requirement.

B 3 Does not fit this requirement.

C 5 The midpoint trace reaches 23 after 5 inspection(s).

D 6 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 100 ms

10 Which term must be true before an algorithm is executed?

A loop invariant Does not fit this requirement.

B postcondition Does not fit this requirement.

C precondition This describes a precondition.

D heuristic Does not fit this requirement.

Written for icaijy.com · U3 AOS2 · Correctness and modularity · answered at 100 ms

11 Improve a timetable by repeatedly accepting only a better neighbouring timetable. Choose the best algorithmic description.

A dynamic programming Does not fit this requirement.

B hill climbing hill climbing best matches the input and goal.

C breadth-first search Does not fit this requirement.

D binary search Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Selecting algorithms · answered at 100 ms

12 Which term is a single valid input that disproves a universal correctness claim?

A base case Does not fit this requirement.

B benchmark Does not fit this requirement.

C postcondition Does not fit this requirement.

D counterexample This describes a counterexample.

Written for icaijy.com · U3 AOS2 · Correctness and modularity · answered at 100 ms

13 Which term remains true before and after every loop iteration?

A input size Does not fit this requirement.

B postcondition Does not fit this requirement.

C loop invariant This describes a loop invariant.

D base case Does not fit this requirement.

Written for icaijy.com · U3 AOS2 · Correctness and modularity · answered at 100 ms

14 Ignoring constant factors, approximately how many primitive operations does an \(O(n^2)\) algorithm perform when n = 1,000,000?

A about 20 million Does not fit this requirement.

B about 1 trillion Substitute n into the stated growth function.

C about 1 quadrillion Does not fit this requirement.

D about 30 Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Practical complexity · answered at 100 ms

15 Many membership queries on a large sorted array. Choose the best algorithmic description.

A hill climbing Does not fit this requirement.

B depth-first search Does not fit this requirement.

C binary search binary search best matches the input and goal.

D linear search Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Selecting algorithms · answered at 100 ms

16 In a directed graph, an edge from u to v

A makes the graph complete Does not fit this requirement.

B does not imply an edge from v to u Direction makes adjacency asymmetric.

C must have weight 1 Does not fit this requirement.

D always implies v to u Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · Graphs · answered at 100 ms

17 Use the supplied Master Theorem. What is T(n) if \(T(n)=2T(n/2)+O(n^1)\)?

A \(O(n^2)\) Does not fit this requirement.

B \(O(n)\) Does not fit this requirement.

C \(O(n \log n)\) Compare \(a=2\) with \(b^c=2\).

D \(O(n^3)\) Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Recurrence relations · answered at 100 ms

18 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…31. How many values are inspected when searching for 1?

A 2 Does not fit this requirement.

B 5 The midpoint trace reaches 1 after 5 inspection(s).

C 8 Does not fit this requirement.

D 3 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 100 ms

19 Which signature best specifies the insert operation?

A set × set → item Does not fit this requirement.

B item → set × set Does not fit this requirement.

C set → item Does not fit this requirement.

D set × item → set Insert adds one item to the set.

Written for icaijy.com · U3 AOS1 · ADT signatures · answered at 100 ms

20 A useful dynamic-programming state should contain

A every line of source code Does not fit this requirement.

B enough information to determine future transitions The state summarises relevant history.

C only the final answer Does not fit this requirement.

D a random heuristic Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Advanced design · answered at 100 ms