icaijy · Algorithmics (HESS)

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

A \(O(n \log n)\) Compare \(a=3\) with \(b^c=3\).

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

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

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

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

02 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 1271 ms

03 Connect all offices with minimum total cable length. Which algorithm is most fit for purpose?

A Prim's algorithm This is a minimum spanning tree problem.

B PageRank Does not fit this requirement.

C Dijkstra’s algorithm Does not fit this requirement.

D Floyd–Warshall algorithm Does not fit this requirement.

Written for icaijy.com · U3 AOS2 · Graph algorithms · answered at 4440 ms

04 One lookup in an unsorted list of five items. Which approach is most suitable?

A PageRank Does not fit this requirement.

B Prim's algorithm Does not fit this requirement.

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

D Floyd–Warshall Does not fit this requirement.

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

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

A 6 Does not fit this requirement.

B 4 The midpoint trace reaches 7 after 4 inspection(s).

C 2 Does not fit this requirement.

D 7 Does not fit this requirement.

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

06 An organisation names who is responsible for harms caused by its model. What is the most relevant issue?

A memoisation Does not fit this requirement.

B anonymity Does not fit this requirement.

C overfitting Does not fit this requirement.

D accountability The scenario directly illustrates accountability.

Written for icaijy.com · U4 AOS3 · AI ethics · answered at 9401 ms

07 A tree with n vertices has exactly

A \(n+1\) edges Does not fit this requirement.

B \(2n\) edges Does not fit this requirement.

C n edges Does not fit this requirement.

D \(n-1\) edges A connected acyclic graph has \(n-1\) edges.

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

08 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 13003 ms

09 A face-recognition model works poorly for a group scarcely represented in its training set. What is the most relevant issue?

A guaranteed neutrality Does not fit this requirement.

B a faster runtime Does not fit this requirement.

C a proof of correctness Does not fit this requirement.

D bias from unrepresentative data The scenario directly illustrates bias from unrepresentative data.

Written for icaijy.com · U4 AOS3 · AI ethics · answered at 16413 ms

10 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 19615 ms

11 A form must reject an ID if it is already present. Which tool is most fit for purpose?

A dictionary Does not fit this requirement.

B stack Does not fit this requirement.

C priority queue Does not fit this requirement.

D set set directly matches the stated requirement.

Written for icaijy.com · Applied · ADTs · answered at 20239 ms

12 Find a path using the fewest edges in an unweighted graph. Which algorithm is most fit for purpose?

A PageRank Does not fit this requirement.

B breadth-first search BFS explores vertices in increasing edge distance.

C Prim's algorithm Does not fit this requirement.

D depth-first search Does not fit this requirement.

Written for icaijy.com · U3 AOS2 · Graph algorithms · answered at 23524 ms

13 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 27018 ms

14 A postcode indirectly encodes socioeconomic or ethnic background. What is the most relevant issue?

A a proxy variable may reproduce discrimination The scenario directly illustrates a proxy variable may reproduce discrimination.

B the algorithm becomes undecidable Does not fit this requirement.

C the feature is automatically fair Does not fit this requirement.

D the model becomes unsupervised Does not fit this requirement.

Written for icaijy.com · U4 AOS3 · AI ethics · answered at 27438 ms

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

A 6 The midpoint trace reaches 1 after 6 inspection(s).

B 1 Does not fit this requirement.

C 2 Does not fit this requirement.

D 8 Does not fit this requirement.

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

16 Assume constant-time primitive operations. What is the tightest Big-O bound for: Three nested loops each run from 1 to n.

A \(O(n^3)\) The iteration counts multiply.

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

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

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

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

17 A browser must return through previously visited pages in reverse order. Which tool is most fit for purpose?

A set Does not fit this requirement.

B stack stack directly matches the stated requirement.

C queue Does not fit this requirement.

D priority queue Does not fit this requirement.

Written for icaijy.com · Applied · ADTs · answered at 31488 ms

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

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

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

C Job C (priority 8) This has the highest priority.

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

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

19 A campus planner needs shortest walking distances between every pair of buildings. Which concept best matches this situation?

A Bellman–Ford algorithm Does not fit this requirement.

B PageRank Does not fit this requirement.

C Prim's algorithm Does not fit this requirement.

D Floyd–Warshall algorithm Floyd–Warshall algorithm directly matches the stated requirement.

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

20 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 39191 ms

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

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

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

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

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

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

22 In a weighted graph, a weight is usually attached to

A an edge or vertex to represent a quantity Weights encode cost, distance or another quantity.

B only isolated vertices Does not fit this requirement.

C the drawing scale Does not fit this requirement.

D the graph title Does not fit this requirement.

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

23 Assume constant-time primitive operations. What is the tightest Big-O bound for: For i from 1 to n: For j from 1 to 67: constantWork()

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

B \(O(n)\) 67 is a constant independent of n.

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

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

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

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

A 13 Does not fit this requirement.

B 2048 Does not fit this requirement.

C 11 Does not fit this requirement.

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

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

25 A research program must look up a student record using a student ID. Which ADT is most suitable?

A stack Does not fit this requirement.

B dictionary A dictionary maps each key to a value.

C set Does not fit this requirement.

D queue Does not fit this requirement.

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

26 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 56123 ms

27 Assume constant-time primitive operations. What is the tightest Big-O bound for: While n > 0: n ← n − 2

A \(O(n)\) Dividing the iteration count by constant 2 keeps it linear.

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

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

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

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

28 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 59739 ms