Anonymous Student · guest · Algorithmics (HESS)

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

02 Which design pattern is most clearly used by a recursive maze solver that reverses choices at dead ends?

A backtracking A recursive maze solver that reverses choices at dead ends uses backtracking.

B brute-force search Does not fit this requirement.

C divide and conquer Does not fit this requirement.

D greedy Does not fit this requirement.

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

03 Explore one branch deeply before returning to alternatives. Which algorithm is most fit for purpose?

A PageRank Does not fit this requirement.

B Dijkstra’s algorithm Does not fit this requirement.

C depth-first search DFS follows a branch before backtracking.

D breadth-first search Does not fit this requirement.

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

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

A 5 Does not fit this requirement.

B 3 Does not fit this requirement.

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

D 6 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 15055 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 19052 ms

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

A 2 Does not fit this requirement.

B 5 The midpoint trace reaches 1 after 5 inspection(s).

C 8 Does not fit this requirement.

D 3 Does not fit this requirement.

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

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

A 11 Does not fit this requirement.

B 10 An unsuccessful search may inspect floor(log₂(512)) + 1 = 10 elements.

C 512 Does not fit this requirement.

D 9 Does not fit this requirement.

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

08 Improve a timetable by repeatedly accepting only a better neighbouring timetable. Which approach is most suitable?

A dynamic programming Does not fit this requirement.

B breadth-first search Does not fit this requirement.

C binary search Does not fit this requirement.

D hill climbing hill climbing best matches the input and goal.

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

09 For sufficiently large n, which grows more slowly than \(O(n^3)\)?

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

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

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

D \(O(n^2)\) \(O(n^2)\) has the lower asymptotic growth rate.

Written for icaijy.com · U4 AOS1 · Growth rates · answered at 41071 ms

10 A council must connect all suburbs while minimising total new cable. Which tool is most fit for purpose?

A Floyd–Warshall algorithm Does not fit this requirement.

B PageRank Does not fit this requirement.

C Prim's algorithm Prim's algorithm directly matches the stated requirement.

D Bellman–Ford algorithm Does not fit this requirement.

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

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

12 Explore a game tree and undo choices when a dead end is reached. Which approach is most suitable?

A binary search Does not fit this requirement.

B PageRank Does not fit this requirement.

C backtracking backtracking best matches the input and goal.

D mergesort Does not fit this requirement.

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

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

A 4 Does not fit this requirement.

B 3 Does not fit this requirement.

C 5 Does not fit this requirement.

D 6 The midpoint trace reaches 31 after 6 inspection(s).

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