Albert 2 · guest · Algorithmics (HESS)

01 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 5179 ms

02 Which design pattern or algorithm orders frontier states using cost-so-far plus an estimated remaining cost?

A Prim's algorithm Does not fit this requirement.

B A* This is the defining behaviour of A*.

C Dijkstra’s algorithm Does not fit this requirement.

D PageRank Does not fit this requirement.

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

03 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 14160 ms

04 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 20421 ms

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

06 Find shortest distances between every pair of vertices. Which algorithm is most fit for purpose?

A depth-first search Does not fit this requirement.

B Bellman–Ford algorithm Does not fit this requirement.

C Floyd–Warshall algorithm Floyd–Warshall solves all-pairs shortest paths.

D Prim's algorithm Does not fit this requirement.

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

07 A school system must test quickly whether a username has already been used. Which ADT is most suitable?

A stack Does not fit this requirement.

B queue Does not fit this requirement.

C priority queue Does not fit this requirement.

D set A set models unique membership.

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

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

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

B \(O(n)\) The body runs n times.

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

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

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

09 How many edges are in an undirected complete graph with 5 vertices?

A 4 Does not fit this requirement.

B 25 Does not fit this requirement.

C 10 There is one edge for each unordered pair: 5×4/2 = 10.

D 20 Does not fit this requirement.

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

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

A 8 The midpoint trace reaches 63 after 8 inspection(s).

B 1 Does not fit this requirement.

C 4 Does not fit this requirement.

D 2 Does not fit this requirement.

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

11 How many edges are in an undirected complete graph with 6 vertices?

A 15 There is one edge for each unordered pair: 6×5/2 = 15.

B 5 Does not fit this requirement.

C 30 Does not fit this requirement.

D 36 Does not fit this requirement.

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

12 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 · not answered before time expired