Algorithms/Phase 7 · Integration & Final Testrule sheet · 3 practice sets · drill · final test

Answer key 7.4-key · Item 79 of 79

Final Test — Answer Key🛑Stop here until you have finished the 90-minute final test.🔑 Open the full answer keyQ1 Answer: (C)1 markReaching the last node means walking the whole list.(A) is wrong: Constant time.(B) is wrong: Constant time.(D) is wrong: Constant time.Re-read: Lesson 0.2.1 — Arrays, linked lists, stacks and queues: what each operation costsQ2 Answer: 61 mark⌊log 100⌋.Re-read: Lesson 0.2.2 — Trees, binary search trees and binary heaps: heights and operation costsQ3 Answer: (D)1 mark2²ⁿ / 2ⁿ = 2ⁿ → ∞.(A) is wrong: The ratio log n / n → 0.(B) is wrong: Constant factor 2.(C) is wrong: 2 log n.Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functionsQ4 Answer: 101 mark1024 → 512 → … → 2 → 1: 10 halvings.Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loopsQ5 Answer: (B)1 markn^(log₂ 8) = n³ dominates n².(A) is wrong: Equal case only.(C) is wrong: Ignores the leaves.(D) is wrong: No log factor.Re-read: Lesson 1.2.3 — The master theoremQ6 Answer: 101 mark⌊log 1000⌋ + 1.Re-read: Lesson 2.1.1 — Linear search and binary search: comparisons and correctnessQ7 Answer: 41 mark2000 / 500.Re-read: Lesson 2.2.1 — Hash tables, hash functions, load factor; separate chainingQ8 Answer: (B) (C)1 markSelection and heapsort move equal keys past each other.(A) is wrong: Root swaps.(D) is wrong: Long-distance swaps.Re-read: Lesson 3.1.2 — Insertion sort and inversions; stable and in-place sortingQ9 Answer: 681 markn + ⌈log n⌉ − 2.Re-read: Lesson 3.3.3 — Selection: minimum and maximum, second largest, k-th smallestQ10 Answer: (B)1 markOne pass over the input, one over the counts.(A) is wrong: No.(C) is wrong: No.(D) is wrong: That is comparison sorting.Re-read: Lesson 3.3.2 — Counting sort, radix sort and bucket sortQ11 Answer: 101 mark63 = 111111₂: 5 squarings + 5 extra.Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarrayQ12 Answer: (B)1 markWhole items can leave wasted capacity.(A) is wrong: Optimal there.(C) is wrong: 0/1 fails.(D) is wrong: Fractional is optimal.Re-read: Lesson 4.2.4 — Optimal merge pattern; when greedy failsQ13 Answer: 411 mark2F(8) − 1 = 2 × 21 − 1.Re-read: Lesson 5.1.1 — Overlapping subproblems: memoisation vs tabulation; counting callsQ14 Answer: (A) (B) (D)1 markBFS uses a queue.(C) is wrong: A stack gives DFS.Re-read: Lesson 6.1.1 — Breadth-first search: levels and unweighted shortest pathsQ15 Answer: (B)1 markRelaxing all edges V − 1 times handles negative edges.(A) is wrong: Needs non-negative weights.(C) is wrong: Ignores weights.(D) is wrong: Builds an MST, not paths.Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGsQ16 Answer: 802 marksn log n + n = 64 + 16.Re-read: Lesson 1.2.1 — Recurrences from recursive code; solving by unrolling (substitution)Q17 Answer: 52 marks65536 → 256 → 16 → 4 → 2: four steps, plus T(2) = 1.Re-read: Lesson 1.2.4 — Harder recurrences: change of variables, T(n−1) forms, unequal splitsQ18 Answer: 92 marks23: 1; 43: 2; 13: 3; 27: 1; 37: 2.Re-read: Lesson 2.2.2 — Open addressing: linear probing, quadratic probing, double hashingQ19 Answer: 3.48 to 3.492 marks10 × (0.9)¹⁰ ≈ 3.487.Re-read: Lesson 2.2.3 — Expected probes and collision probabilitiesQ20 Answer: 172 marksPairs 4 × 1; merging into fours 3 + 3; final merge 7.Re-read: Lesson 3.2.1 — Merge sort: merging, recurrence, comparison countsQ21 Answer: 62 marksPivot 7: 4; then [4, 1, 3] with pivot 3: 2; single elements need none.Re-read: Lesson 3.2.2 — Quicksort: partitioning, best, worst and average casesQ22 Answer: 32 marks20↔40; 10↔40; 10↔30. Result [40, 30, 15, 10, 20].Re-read: Lesson 3.2.3 — Heapsort: build-heap in O(n), heapify, extract-maxQ23 Answer: 952 marks40 from the first item (ratio 10), then 11 units at ratio 5 = 55.Re-read: Lesson 4.2.2 — Fractional knapsack; job sequencing with deadlinesQ24 Answer: 2.172 marksMerges 17, 42, 58, 100 sum to 217.Re-read: Lesson 4.2.3 — Huffman codingQ25 Answer: 652 marks(1, 15) + (5, 50).Re-read: Lesson 5.1.2 — 0/1 knapsackQ26 Answer: 92 marksTens 2: 1 way; tens 1: fives 0–2 (3 ways); tens 0: fives 0–4 (5 ways).Re-read: Lesson 5.2.2 — Subset sum, coin change and rod cuttingQ27 Answer: 13442 marksOrder ((A₁A₂)((A₃A₄)A₅)).Re-read: Lesson 5.2.1 — Matrix-chain multiplicationQ28 Answer: (A) (B) (D)2 marksTimes: 1 1/8, 2 2/5, 4 3/4, 3 6/7; 1 → 3 is a tree edge.(C) is wrong: 3 is still white when 1 → 3 is explored.Re-read: Lesson 6.1.2 — Depth-first search: discovery and finish times, edge classificationQ29 Answer: 392 marksEdges added: A–D 5, D–F 6, A–B 7, B–E 7, E–C 5, E–G 9.Re-read: Lesson 6.2.3 — Prim's algorithm; MST complexitiesQ30 Answer: 202 marks1–3–6–5 = 9 + 2 + 9.Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm

Read at your own pace. Try the questions before opening the answers.