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

01 An exponential-time algorithm on large inputs illustrates

A an undecidable problem Does not fit this requirement.

B a soft limit of computability The problem is computable but may be impractical.

C a syntax error Does not fit this requirement.

D a violation of Church–Turing Does not fit this requirement.

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

02 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

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

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

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

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

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

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

04 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

05 A classifier learns from emails already labelled spam or not spam. Select the best model or method.

A unsupervised learning Does not fit this requirement.

B binary search Does not fit this requirement.

C PageRank Does not fit this requirement.

D supervised learning supervised learning directly matches the stated requirement.

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

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

A 5 An unsuccessful search may inspect floor(log₂(16)) + 1 = 5 elements.

B 4 Does not fit this requirement.

C 6 Does not fit this requirement.

D 16 Does not fit this requirement.

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

07 Many membership queries on a large sorted array. Which approach is most suitable?

A linear search Does not fit this requirement.

B depth-first search Does not fit this requirement.

C hill climbing Does not fit this requirement.

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

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

08 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

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

A about 1 million Does not fit this requirement.

B about 1 thousand Does not fit this requirement.

C about 1 billion Does not fit this requirement.

D about 30 Substitute n into the stated growth function.

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

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

11 Which signature best specifies the front operation?

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

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

C queue → item Front observes the next item without adding one.

D item → queue Does not fit this requirement.

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

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

A 1024 Does not fit this requirement.

B 10 Does not fit this requirement.

C 12 Does not fit this requirement.

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

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

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

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

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

C Node C: g = 4, h = 10, f = 14 f = 14; another node has a smaller f.

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

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

14 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

15 Tabulation is usually

A randomised backtracking Does not fit this requirement.

B a reduction proof Does not fit this requirement.

C bottom-up evaluation of DP states Tabulation fills a table in dependency order.

D a Turing Test Does not fit this requirement.

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

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

A 1 Does not fit this requirement.

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

C 6 Does not fit this requirement.

D 7 Does not fit this requirement.

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

17 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

18 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

19 A fare graph includes rebates represented by negative edges and has no negative cycle. Which concept best matches this situation?

A PageRank Does not fit this requirement.

B Floyd–Warshall algorithm Does not fit this requirement.

C Prim's algorithm Does not fit this requirement.

D Bellman–Ford algorithm Bellman–Ford algorithm directly matches the stated requirement.

Written for icaijy.com · Applied · graph algorithms · 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 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 100 ms