Bot · guest · Algorithmics (HESS)

01 Which class is best described as decision problems whose yes-instances have polynomial-time verifiable certificates?

A NP-Hard only Does not fit this requirement.

B P only Does not fit this requirement.

C undecidable Does not fit this requirement.

D NP That is the definition of NP.

Written for icaijy.com · U4 AOS1 · P, NP and reductions · answered at 100 ms

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

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

B Node B: g = 4, h = 4, f = 8 f = 8; this is minimal.

C Node C: g = 6, h = 2, f = 8 f = 8; another node has a smaller f.

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

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

03 For sufficiently large n, which grows more slowly than \(O(n^3)\)?

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

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

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

D \(O(n^2)\) \(O(n^2)\) has the lower asymptotic growth rate.

Written for icaijy.com · U4 AOS1 · Growth rates · answered at 100 ms

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

A Job A (priority 17) This has the highest priority.

B Job B (priority 11) A higher-priority job is present.

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

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

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

05 Which design pattern or algorithm stores solutions of overlapping subproblems to avoid recomputation?

A simulated annealing Does not fit this requirement.

B greedy Does not fit this requirement.

C divide and conquer Does not fit this requirement.

D dynamic programming This is the defining behaviour of dynamic programming.

Written for icaijy.com · U3/U4 · Algorithm design patterns · answered at 100 ms

06 A transport app must look up a student record using a student ID. Which ADT is most suitable?

A stack Does not fit this requirement.

B set Does not fit this requirement.

C queue Does not fit this requirement.

D dictionary A dictionary maps each key to a value.

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

07 A school system must always process the waiting job with the highest urgency. Which ADT is most suitable?

A stack Does not fit this requirement.

B set Does not fit this requirement.

C priority queue A priority queue removes the highest-priority item.

D queue Does not fit this requirement.

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

08 Which term best matches a system that performs very well on training examples but poorly on new examples?

A overfitting This describes overfitting.

B underflow Does not fit this requirement.

C abstraction Does not fit this requirement.

D backtracking Does not fit this requirement.

Written for icaijy.com · U4 AOS3 · Data-driven algorithms · answered at 100 ms

09 Which signature best specifies the push operation?

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

B stack × item → stack Push adds an item and returns the updated stack.

C stack → item Does not fit this requirement.

D item → stack Does not fit this requirement.

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

10 A bank provides understandable reasons for an automated rejection. Which tool is most fit for purpose?

A privacy Does not fit this requirement.

B transparency transparency directly matches the stated requirement.

C bias Does not fit this requirement.

D time complexity Does not fit this requirement.

Written for icaijy.com · Applied · AI ethics · answered at 100 ms

11 A system groups articles without any supplied category labels. Which tool is most fit for purpose?

A unsupervised learning unsupervised learning directly matches the stated requirement.

B backtracking Does not fit this requirement.

C supervised learning Does not fit this requirement.

D PageRank Does not fit this requirement.

Written for icaijy.com · Applied · data-driven algorithms · answered at 100 ms

12 Which design pattern is most clearly used by binary search?

A brute-force search Does not fit this requirement.

B dynamic programming Does not fit this requirement.

C divide and conquer Binary search uses divide and conquer.

D greedy Does not fit this requirement.

Written for icaijy.com · U3/U4 · Algorithm design patterns · answered at 100 ms

13 For sufficiently large n, which grows more slowly than \(O(n \log n)\)?

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

B \(O(n)\) \(O(n)\) has the lower asymptotic growth rate.

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

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

Written for icaijy.com · U4 AOS1 · Growth rates · answered at 100 ms

14 A research program must test quickly whether a username has already been used. Which ADT is most suitable?

A priority queue Does not fit this requirement.

B stack Does not fit this requirement.

C queue Does not fit this requirement.

D set A set models unique membership.

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

15 A council must connect all suburbs while minimising total new cable. Select the best model or method.

A Bellman–Ford algorithm Does not fit this requirement.

B Prim's algorithm Prim's algorithm directly matches the stated requirement.

C Dijkstra’s algorithm Does not fit this requirement.

D PageRank Does not fit this requirement.

Written for icaijy.com · Applied · graph algorithms · answered at 100 ms

16 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

17 A research program must represent cities and the roads joining them. Which ADT is most suitable?

A graph A graph models entities and relationships.

B dictionary Does not fit this requirement.

C stack Does not fit this requirement.

D set Does not fit this requirement.

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

18 Why can testing many inputs usually not prove that an algorithm is correct for every valid input?

A Untested valid inputs may still fail. A finite test set need not cover the whole input domain.

B Only recursive algorithms can be tested. Does not fit this requirement.

C Big-O notation forbids testing. Does not fit this requirement.

D Testing always changes the algorithm. Does not fit this requirement.

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

19 Using the usual inclusive low/high implementation, at most how many element inspections can an unsuccessful binary search of 8192 sorted items require?

A 15 Does not fit this requirement.

B 8192 Does not fit this requirement.

C 13 Does not fit this requirement.

D 14 An unsuccessful search may inspect floor(log₂(8192)) + 1 = 14 elements.

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

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

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

B 3 Does not fit this requirement.

C 2 Does not fit this requirement.

D 5 Does not fit this requirement.

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