Albert · guest · Algorithmics (HESS)

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

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

B 3 Does not fit this requirement.

C 6 Does not fit this requirement.

D 7 Does not fit this requirement.

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

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

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

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

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

D \(O(n^3)\) Compare \(a=8\) with \(b^c=4\).

Written for icaijy.com · U4 AOS1 · Recurrence relations · answered at 2840 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 6245 ms

04 Lambda calculus is important in computability because it

A proves all algorithms efficient Does not fit this requirement.

B provides a model of computation equivalent in power to Turing machines The accepted statement is: provides a model of computation equivalent in power to Turing machines.

C requires machine learning Does not fit this requirement.

D sorts only numeric arrays Does not fit this requirement.

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

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

A 3 Does not fit this requirement.

B 8 Does not fit this requirement.

C 7 The midpoint trace reaches 127 after 7 inspection(s).

D 4 Does not fit this requirement.

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

06 A subgraph may contain

A edges absent from the original graph Does not fit this requirement.

B new vertices only Does not fit this requirement.

C every original edge only Does not fit this requirement.

D subsets of the original vertices and edges A subgraph uses only original vertices and edges.

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

07 In the standard model, a Turing machine reads and writes symbols on

A a neural network Does not fit this requirement.

B a finite queue only Does not fit this requirement.

C a weighted graph Does not fit this requirement.

D an unbounded tape divided into cells The accepted statement is: an unbounded tape divided into cells.

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

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

09 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 19696 ms

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

11 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 30750 ms

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

A \(O(n^2)\) There are n × n iterations.

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

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

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

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

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

14 Patients must be treated according to changing urgency scores. Which tool is most fit for purpose?

A stack Does not fit this requirement.

B set Does not fit this requirement.

C priority queue priority queue directly matches the stated requirement.

D queue Does not fit this requirement.

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

15 How many edges are in an undirected complete graph with 10 vertices?

A 100 Does not fit this requirement.

B 9 Does not fit this requirement.

C 90 Does not fit this requirement.

D 45 There is one edge for each unordered pair: 10×9/2 = 45.

Written for icaijy.com · U3 AOS1 · Graph modelling · answered at 40295 ms

16 A school system must look up a student record using a student ID. Which ADT is most suitable?

A set Does not fit this requirement.

B dictionary A dictionary maps each key to a value.

C stack Does not fit this requirement.

D queue Does not fit this requirement.

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

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

A 2 Does not fit this requirement.

B 4 Does not fit this requirement.

C 6 Does not fit this requirement.

D 7 The midpoint trace reaches 63 after 7 inspection(s).

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

18 How many edges are in an undirected complete graph with 8 vertices?

A 56 Does not fit this requirement.

B 28 There is one edge for each unordered pair: 8×7/2 = 28.

C 64 Does not fit this requirement.

D 7 Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · Graph modelling · answered at 50520 ms

19 Which term proves a recursive claim from a base case and a smaller instance?

A random testing Does not fit this requirement.

B inductive argument This describes a inductive argument.

C simulation Does not fit this requirement.

D hill climbing Does not fit this requirement.

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

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