Henry 67 · guest · Algorithmics (HESS)

01 Assume constant-time primitive operations. What is the tightest Big-O bound for: For i from 1 to n: j ← 1; While j < n: j ← 2j

A \(O(n \log n)\) A logarithmic loop occurs n times.

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

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

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

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

02 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 20810 ms

03 A useful dynamic-programming state should contain

A every line of source code Does not fit this requirement.

B enough information to determine future transitions The state summarises relevant history.

C only the final answer Does not fit this requirement.

D a random heuristic Does not fit this requirement.

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

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

05 Worst-case time complexity gives

A the average over one dataset Does not fit this requirement.

B an upper bound over all inputs of a given size Worst case considers the most costly input of each size.

C the exact time on every device Does not fit this requirement.

D the memory used by the best input Does not fit this requirement.

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

06 In a weighted graph, a weight is usually attached to

A an edge or vertex to represent a quantity Weights encode cost, distance or another quantity.

B only isolated vertices Does not fit this requirement.

C the drawing scale Does not fit this requirement.

D the graph title Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · Graphs · answered at 42128 ms

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

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

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

A 4 Does not fit this requirement.

B 3 Does not fit this requirement.

C 5 The midpoint trace reaches 23 after 5 inspection(s).

D 6 Does not fit this requirement.

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