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

01 To show new problem X is NP-Hard using known NP-Hard problem Y, the required polynomial reduction direction is

A P → Y Does not fit this requirement.

B Y → X Solving X would then solve Y.

C X → Y Does not fit this requirement.

D X → P Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Complexity limits · answered at 100 ms

02 A basic hill-climbing search may stop before the global optimum because of

A the Master Theorem Does not fit this requirement.

B a local optimum No improving neighbour may exist at a non-global optimum.

C a guaranteed negative cycle Does not fit this requirement.

D a queue overflow by definition Does not fit this requirement.

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

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

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

B 2 Does not fit this requirement.

C 7 Does not fit this requirement.

D 1 Does not fit this requirement.

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

04 Which design pattern is most clearly used by the standard earliest-finish-time interval scheduler?

A dynamic programming Does not fit this requirement.

B divide and conquer Does not fit this requirement.

C brute-force search Does not fit this requirement.

D greedy The standard earliest-finish-time interval scheduler uses greedy.

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

05 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 100 ms

06 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 100 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 100 ms

08 How many edges are in an undirected complete graph with 14 vertices?

A 196 Does not fit this requirement.

B 182 Does not fit this requirement.

C 13 Does not fit this requirement.

D 91 There is one edge for each unordered pair: 14×13/2 = 91.

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

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

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

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

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

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

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

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

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

A 5 The midpoint trace reaches 15 after 5 inspection(s).

B 3 Does not fit this requirement.

C 9 Does not fit this requirement.

D 8 Does not fit this requirement.

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

12 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 100 ms

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

14 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

15 A transport app must serve customers in the order in which they arrived. Which ADT is most suitable?

A stack Does not fit this requirement.

B queue A queue provides first-in, first-out access.

C set Does not fit this requirement.

D dictionary Does not fit this requirement.

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

16 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

17 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 100 ms

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

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

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

C Node C: g = 9, h = 3, f = 12 f = 12; this is minimal.

D Node D: g = 11, h = 2, f = 13 f = 13; another node has a smaller f.

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

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

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

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

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

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

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

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

A 4 Does not fit this requirement.

B 6 The midpoint trace reaches 63 after 6 inspection(s).

C 8 Does not fit this requirement.

D 1 Does not fit this requirement.

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