icaijy · Algorithmics (HESS)

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

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

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

C \(O(n \log n)\) Compare \(a=2\) with \(b^c=2\).

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

Written for icaijy.com · U4 AOS1 · Recurrence relations · answered at 2982 ms

02 Which signature best specifies the pop operation?

A stack → stack Pop removes the top item and returns the updated stack in this specification.

B item → stack Does not fit this requirement.

C stack × item → stack Does not fit this requirement.

D stack → item × item Does not fit this requirement.

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

03 An admissible A* heuristic

A must always equal zero Does not fit this requirement.

B depends only on elapsed time Does not fit this requirement.

C always overestimates the cost Does not fit this requirement.

D never overestimates the remaining optimal cost This condition preserves optimality.

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

04 A classifier learns from emails already labelled spam or not spam. Which tool is most fit for purpose?

A PageRank Does not fit this requirement.

B backtracking Does not fit this requirement.

C supervised learning supervised learning directly matches the stated requirement.

D binary search Does not fit this requirement.

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

05 A greedy algorithm is claimed to be optimal. Which evidence is strongest?

A It worked on ten random inputs. Does not fit this requirement.

B It uses a priority queue. Does not fit this requirement.

C Its code is short. Does not fit this requirement.

D A proof that every greedy choice can be part of an optimal solution. An exchange-style argument establishes optimality generally.

Written for icaijy.com · U3 AOS2 · Correctness · answered at 25885 ms

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

A about 1 billion Does not fit this requirement.

B about 1 trillion Does not fit this requirement.

C about 1 million Substitute n into the stated growth function.

D about 30 Does not fit this requirement.

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

07 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 35833 ms

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

09 Which term best matches a system that seeks structure in unlabelled data?

A unsupervised learning This describes unsupervised learning.

B supervised learning Does not fit this requirement.

C backtracking Does not fit this requirement.

D formal verification Does not fit this requirement.

Written for icaijy.com · U4 AOS3 · Data-driven algorithms · answered at 47662 ms

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

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

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

13 Use the supplied Master Theorem. What is T(n) if \(T(n)=1T(n/3)+O(n^0)\)?

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

B \(O(\log n)\) Compare \(a=1\) with \(b^c=1\).

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

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

Written for icaijy.com · U4 AOS1 · Recurrence relations · answered at 57542 ms

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

A about 1 quadrillion Does not fit this requirement.

B about 1 billion Substitute n into the stated growth function.

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 58516 ms