AskSia - COMP90038

final 60%，纸质开卷，15+180，22 页。[1]Source: asksia-bible-comp90038-bilingual.pdf你已上完课和小测。盖住已做的步骤,自己重跑每段追踪––插入 AVL 键、heapify 数组、填 Floyd 矩阵、判断主定理 (Master Theorem)的情形。手算追踪的速度正是 Q1 考的; 每周的小测(10%)反复练同样的动作。 C 3 . APPLY 3 · 应用 It's the exam (or A1/A2). The decoder card and the per- algorithm complexity lines are your index: bounded universe - counting sort; O(n log n) -+ presort+scan; nearest-of-k ++ super-source Dijkstra. For Q3- Q10 always state AND justify time AND space. 这是考试(或A1/A2)。解码器卡片和逐算法的复杂度行就是你的索引:有界宇宙→counting sort; O(n log n) → 先排序+扫描;最近k 之一→超级源点 Dijkstra。对 Q3-Q10 永远要给出并论证时间和空间界。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ! The assessment shape - and where the marks really live 考核形态 ––以及分数真正藏在哪里 Quizzes 10% (10 weekly Canvas quizzes, Wk 2-11, MCQ/short numeric) . Assignment 115% (recurrence proofs + design-and-analyse - no Al tools permitted) · Assignment 2 15% (algorithm design) · Final 60% - in-person, open book (paper based), 15 min reading + 180 min writing, 22-page paper. The structure is fixed: Q1 = 10x1-mark MCQ hand-traces; Q2 = 5×2-mark True/False with justification (1 mark answer + 1 mark constants-or-counterexample - T/F alone = half marks); Q3-Q10 = design-and-analyse (3-8 marks, where most of the 60% sits). Open book lulls you into not practising; the marks are in speed and method, which no amount of flipping buys. 小测 10% (10 次每周 Canvas 小测,第 2-11周,MCQ/简短数值)· 作业一 15%(递推证明+设计与分析 -- 不允许使用 AI 工具)·作业二15%(算法设计)·期末60% -- 现场、开卷(纸质),15分钟阅读+180 分钟书写,22 页试卷。结构固定:Q1= 10×1分 MCQ 手算追踪;Q2= 5×2 分判断题须给理由(1分答案+1分常数或反例 -- 只写 T/F = 半分);Q3-Q10= 设计与分析(3-8分,60% 的大头都在这)。开卷会让你麻痹不去练;而分数在于速度和方法, 再怎么翻书也买不来。 i How this book was built - and the two-layer rule 本书如何构建 · -以及两层规则 Standard, published algorithm theory - the data structures, recurrences, the Master Theorem, the asymptotic definitions, Dijkstra/Prim/Floyd/Warshall/Huffman - is taught plainly with our own pseudocode and our own traces (canonical references: Levitin, Introduction to the Design and Analysis of Algorithms 3e; CLRS; Erickson; Skiena). The unit's specific exam stems, assignment datasets and lecturer hypotheticals are paraphrased and re-numbered with fresh AskSia inputs - never reproduced verbatim. Examinability note: Horspool string search is examinable; Boyer-Moore, KMP and Rabin-Karp are NOT; closest-pair D&C (§5. 4) is NOT; NP-completeness is light awareness only. Verify weights, dates and the exact open-book rules on your own LMS (canvas. lms. unimelb. edu. au). 标准、已出版的算法理论 -- 数据结构、递推、主定理(Master Theorem)、渐近定义、 Dijkstra/Prim/Floyd/Warshall/Huffman -- 都用我们自己的伪代码和自己的追踪平实讲授(权威参考:Levitin, Introduction to the Design and Analysis of Algorithms 3e; CLRS; Erickson; Skiena)。本课具体的考题题干、作业数据集和讲师假想例都已用全新 AskSia 输入改述并重新编号 -- 绝不照抄。考查范围说明:Horspool 字符串搜索属于考查范围;Boyer-Moore、KMP、Rabin-Karp 不考;最近点对 D&C (§5. 4)不考;NP完全性仅作了解。请在你自己的 LMS (canvas. lms. unimelb. edu. au) 上核实分值、日期和开卷的确切规则。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 THE BLUEPRINT - THE EXAM BLUEPRINT FINAL 60% . OPEN BOOK (PAPER) Open book is the trap 开卷才是陷阱 60% . 3 hours . paper based - the win is the decoder + the recipe deck, not 700 pages 60% · 3 小时 · 纸质 -- 优势在解码器+套路卡,而非 700 页书 TL;DR. "Open book" sounds like a gift; it is a time trap. You may bring paper copies of the textbook, every lecture slide and every workshop solution - but you cannot flip 700pp of Levitin + 21 decks in 180 min. The win is (a) the design-technique decoder below - read off the technique from the required complexity - and (b) a deck of concise recipe cards you index in seconds, not minutes. 太长不看。“开卷”听起来像礼物,其实是时间陷阱。你可以带教材、每张讲义和每份习题课答案的纸质副本 -- 但你没法在 180 分钟里翻完 700 页 Levitin+21 套讲义。优势在于(a)下面这个设计技术解码器 -- 从所需复杂度读出技术 -- 以及 (b)一叠你能在数秒而非数分钟内索引到的简明套路卡。 1 - 60% OPEN-BOOK FINAL 开卷期末 22pp EXAM PAPER 试卷 3h +15 MIN READING +15 分钟阅读 recipe NOT RECALL 不是死记 [16]

Q1 = hand trace；Q2 = T/F + justification；Q3–Q10 = design & analyse。[1]Source: asksia-bible-comp90038-bilingual.pdf你已上完课和小测。盖住已做的步骤,自己重跑每段追踪––插入 AVL 键、heapify 数组、填 Floyd 矩阵、判断主定理 (Master Theorem)的情形。手算追踪的速度正是 Q1 考的; 每周的小测(10%)反复练同样的动作。 C 3 . APPLY 3 · 应用 It's the exam (or A1/A2). The decoder card and the per- algorithm complexity lines are your index: bounded universe - counting sort; O(n log n) -+ presort+scan; nearest-of-k ++ super-source Dijkstra. For Q3- Q10 always state AND justify time AND space. 这是考试(或A1/A2)。解码器卡片和逐算法的复杂度行就是你的索引:有界宇宙→counting sort; O(n log n) → 先排序+扫描;最近k 之一→超级源点 Dijkstra。对 Q3-Q10 永远要给出并论证时间和空间界。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ! The assessment shape - and where the marks really live 考核形态 ––以及分数真正藏在哪里 Quizzes 10% (10 weekly Canvas quizzes, Wk 2-11, MCQ/short numeric) . Assignment 115% (recurrence proofs + design-and-analyse - no Al tools permitted) · Assignment 2 15% (algorithm design) · Final 60% - in-person, open book (paper based), 15 min reading + 180 min writing, 22-page paper. The structure is fixed: Q1 = 10x1-mark MCQ hand-traces; Q2 = 5×2-mark True/False with justification (1 mark answer + 1 mark constants-or-counterexample - T/F alone = half marks); Q3-Q10 = design-and-analyse (3-8 marks, where most of the 60% sits). Open book lulls you into not practising; the marks are in speed and method, which no amount of flipping buys. 小测 10% (10 次每周 Canvas 小测,第 2-11周,MCQ/简短数值)· 作业一 15%(递推证明+设计与分析 -- 不允许使用 AI 工具)·作业二15%(算法设计)·期末60% -- 现场、开卷(纸质),15分钟阅读+180 分钟书写,22 页试卷。结构固定:Q1= 10×1分 MCQ 手算追踪;Q2= 5×2 分判断题须给理由(1分答案+1分常数或反例 -- 只写 T/F = 半分);Q3-Q10= 设计与分析(3-8分,60% 的大头都在这)。开卷会让你麻痹不去练;而分数在于速度和方法, 再怎么翻书也买不来。 i How this book was built - and the two-layer rule 本书如何构建 · -以及两层规则 Standard, published algorithm theory - the data structures, recurrences, the Master Theorem, the asymptotic definitions, Dijkstra/Prim/Floyd/Warshall/Huffman - is taught plainly with our own pseudocode and our own traces (canonical references: Levitin, Introduction to the Design and Analysis of Algorithms 3e; CLRS; Erickson; Skiena). The unit's specific exam stems, assignment datasets and lecturer hypotheticals are paraphrased and re-numbered with fresh AskSia inputs - never reproduced verbatim. Examinability note: Horspool string search is examinable; Boyer-Moore, KMP and Rabin-Karp are NOT; closest-pair D&C (§5. 4) is NOT; NP-completeness is light awareness only. Verify weights, dates and the exact open-book rules on your own LMS (canvas. lms. unimelb. edu. au). 标准、已出版的算法理论 -- 数据结构、递推、主定理(Master Theorem)、渐近定义、 Dijkstra/Prim/Floyd/Warshall/Huffman -- 都用我们自己的伪代码和自己的追踪平实讲授(权威参考:Levitin, Introduction to the Design and Analysis of Algorithms 3e; CLRS; Erickson; Skiena)。本课具体的考题题干、作业数据集和讲师假想例都已用全新 AskSia 输入改述并重新编号 -- 绝不照抄。考查范围说明:Horspool 字符串搜索属于考查范围;Boyer-Moore、KMP、Rabin-Karp 不考;最近点对 D&C (§5. 4)不考;NP完全性仅作了解。请在你自己的 LMS (canvas. lms. unimelb. edu. au) 上核实分值、日期和开卷的确切规则。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 THE BLUEPRINT - THE EXAM BLUEPRINT FINAL 60% . OPEN BOOK (PAPER) Open book is the trap 开卷才是陷阱 60% . 3 hours . paper based - the win is the decoder + the recipe deck, not 700 pages 60% · 3 小时 · 纸质 -- 优势在解码器+套路卡,而非 700 页书 TL;DR. "Open book" sounds like a gift; it is a time trap. You may bring paper copies of the textbook, every lecture slide and every workshop solution - but you cannot flip 700pp of Levitin + 21 decks in 180 min. The win is (a) the design-technique decoder below - read off the technique from the required complexity - and (b) a deck of concise recipe cards you index in seconds, not minutes. 太长不看。“开卷”听起来像礼物,其实是时间陷阱。你可以带教材、每张讲义和每份习题课答案的纸质副本 -- 但你没法在 180 分钟里翻完 700 页 Levitin+21 套讲义。优势在于(a)下面这个设计技术解码器 -- 从所需复杂度读出技术 -- 以及 (b)一叠你能在数秒而非数分钟内索引到的简明套路卡。 1 - 60% OPEN-BOOK FINAL 开卷期末 22pp EXAM PAPER 试卷 3h +15 MIN READING +15 分钟阅读 recipe NOT RECALL 不是死记 [4]Source: asksia-bible-comp90038-bilingual.pdfThe final is in-person and open book (paper based). Authorised materials are paper copies of the textbook, all lecture slides, and the workshop solutions; you may also refer to your own earlier written work. No devices, no dictionary (ask an invigilator if a term is unclear). So print this bible double-sided, tab the decoder and the complexity card, and bring it in - it is faster to flip than the textbook. Confirm the current rules on your own subject LMS before the day. 期末是现场、开卷(纸笔)。允许的材料是教科书、全部讲义幻灯片和习题课答案的纸质副本;你也可参阅自己此前的书面作业。不得带设备、不得带字典(词义不清可问监考)。所以把这本 bible 双面打印、给解码器和复杂度卡贴上标签带进去 -- 它比教科书翻得快。考前请在你自己科目的 LMS 上确认当前规则。 - COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 EXAM DECODER . OPEN- BOOK PLAYBOOK D. 2 The paper - 22 pages, 60 marks, 3 parts D. 2 试卷 -- 22页,60分,3部分 Know the shape before you sit down. There is a 15-minute reading time then 180 minutes of writing. The marks split into three bands - and each band wants a different shape of answer. 坐下前先知道试卷形状。有15分钟阅读时间,然后180分钟书写。分数分三档 -- 每档想要不同形状的答案。 60% OF THE SUBJECT 本科目的 22pp PAPER, ON PAPER 纸质,纸笔答 15min READING TIME 阅读时间 180min WRITING TIME 答题时间 Band What it is How to answer Q1 - MCQ 10 × 1 mark; each a multi-minute hand-trace (AVL inserts, 2-3 build, linear probing, Warshall R2, Floyd D1, preorder+inorder++postorder, DFS topsort, MST weight, "which fact is true") Trace in the margin, ~3 min each; no working is marked, so just get the answer right. Do the cheap ones first; flag a slow trace and move on. Q2 -T/F 5 x 2 marks; True/False WITH justification (1 mark verdict + 1 mark proof) Verdict, then exhibit constants (asymptotic claim) or one counterexample ("always/never" claim). Bare T/F = half marks. Q3-Q10 short-answer / design-and-analyse, 3-8 marks each - the high-mark core - design Name the technique (use the decoder), give the method/recurrence, then STATE AND JUSTIFY the time AND the space bound. That is where the marks live. On Q3-Q10: always state AND justify BOTH time AND space ★ 关于 Q3-Q10:始终陈述并论证时间和空间两者 The single highest-yield habit in this exam. For every design answer write the bound and one line of why: e. g. "O(IVI+|EI) time - each vertex and edge is touched O(1) times in the flood-fill; O(IV]+[E]) space - adjacency lists plus an O(IVI) group array. " Drop the space bound, or assert a bound with no justification, and you leave 1-2 marks on the table per question. Label worst / expected / amortised explicitly - an unlabelled O(n) for an expected-time algorithm is a half answer. 本场考试单项收益最高的习惯。每个设计题答案都写出界并附一行理由:例如“O(Iv]+[E])时间 -- flood-fill 中每个顶点和每条边被触及 O(1)次;O(Iv)+|E|)空间 -- 邻接表加一个 O(IV)的分组数组。”漏掉空间界、或断言一个界却不论证, 每题就会丢 1-2 分。明确标注 worst / expected / amortised -- 给一个 expected-time 算法写无标注的 O(n)只是半个答案。 D. 3 The 15 + 180 clock [16]

Q3–Q10 永远写并论证 time + space。[4]Source: asksia-bible-comp90038-bilingual.pdfThe final is in-person and open book (paper based). Authorised materials are paper copies of the textbook, all lecture slides, and the workshop solutions; you may also refer to your own earlier written work. No devices, no dictionary (ask an invigilator if a term is unclear). So print this bible double-sided, tab the decoder and the complexity card, and bring it in - it is faster to flip than the textbook. Confirm the current rules on your own subject LMS before the day. 期末是现场、开卷(纸笔)。允许的材料是教科书、全部讲义幻灯片和习题课答案的纸质副本;你也可参阅自己此前的书面作业。不得带设备、不得带字典(词义不清可问监考)。所以把这本 bible 双面打印、给解码器和复杂度卡贴上标签带进去 -- 它比教科书翻得快。考前请在你自己科目的 LMS 上确认当前规则。 - COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 EXAM DECODER . OPEN- BOOK PLAYBOOK D. 2 The paper - 22 pages, 60 marks, 3 parts D. 2 试卷 -- 22页,60分,3部分 Know the shape before you sit down. There is a 15-minute reading time then 180 minutes of writing. The marks split into three bands - and each band wants a different shape of answer. 坐下前先知道试卷形状。有15分钟阅读时间,然后180分钟书写。分数分三档 -- 每档想要不同形状的答案。 60% OF THE SUBJECT 本科目的 22pp PAPER, ON PAPER 纸质,纸笔答 15min READING TIME 阅读时间 180min WRITING TIME 答题时间 Band What it is How to answer Q1 - MCQ 10 × 1 mark; each a multi-minute hand-trace (AVL inserts, 2-3 build, linear probing, Warshall R2, Floyd D1, preorder+inorder++postorder, DFS topsort, MST weight, "which fact is true") Trace in the margin, ~3 min each; no working is marked, so just get the answer right. Do the cheap ones first; flag a slow trace and move on. Q2 -T/F 5 x 2 marks; True/False WITH justification (1 mark verdict + 1 mark proof) Verdict, then exhibit constants (asymptotic claim) or one counterexample ("always/never" claim). Bare T/F = half marks. Q3-Q10 short-answer / design-and-analyse, 3-8 marks each - the high-mark core - design Name the technique (use the decoder), give the method/recurrence, then STATE AND JUSTIFY the time AND the space bound. That is where the marks live. On Q3-Q10: always state AND justify BOTH time AND space ★ 关于 Q3-Q10:始终陈述并论证时间和空间两者 The single highest-yield habit in this exam. For every design answer write the bound and one line of why: e. g. "O(IVI+|EI) time - each vertex and edge is touched O(1) times in the flood-fill; O(IV]+[E]) space - adjacency lists plus an O(IVI) group array. " Drop the space bound, or assert a bound with no justification, and you leave 1-2 marks on the table per question. Label worst / expected / amortised explicitly - an unlabelled O(n) for an expected-time algorithm is a half answer. 本场考试单项收益最高的习惯。每个设计题答案都写出界并附一行理由:例如“O(Iv]+[E])时间 -- flood-fill 中每个顶点和每条边被触及 O(1)次;O(Iv)+|E|)空间 -- 邻接表加一个 O(IV)的分组数组。”漏掉空间界、或断言一个界却不论证, 每题就会丢 1-2 分。明确标注 worst / expected / amortised -- 给一个 expected-time 算法写无标注的 O(n)只是半个答案。 D. 3 The 15 + 180 clock [16]

永远标清 worst / expected / amortised。[6]Source: asksia-bible-comp90038-bilingual.pdfAlways label which. Quickselect/quicksort: O(n2) worst but O(n)/O(n log n) expected - the good bound needs randomisation. Master case a vs b7 a < b7 => O(n7) (leaf-light); a = b7 => O(n7 log n); a > b7 => O(n^{log_b a}). Easy to flip the inequality. Matrix vs list traversal Adjacency matrix => O(V2); adjacency list => O(V+E). The single most-tested representation distinction. DFS topsort order Output in reverse pop/finish order, not push order; break ties alphabetically per the exam convention. Min vs max heap Read the question. Sample uses a MIN-heap; child(i)=2i,2i+1; heapify is O(n), not O(n log n). LR vs RL rotation Look at where the new key landed relative to the lowest unbalanced node, not just the shape; rotate the median up. 2-3 split promotes On overflow of a 3-node (3 keys), promote the middle key up; height grows only when the root splits. Chaining vs linear probing Same keys, different mechanics: chaining - longest chain length; probing - cell placement with wrap-around + clustering. Prim vs Dijkstra Same skeleton, different priority: Prim = lightest crossing edge; Dijkstra = smallest distance from source. MST # shortest-path tree. Warshall vs Floyd Warshall uses v/A on a 0/1 matrix (closure); Floyd uses min/+ on a weight matrix (co for no edge). k is the outermost loop in both. Greedy vs DP knapsack 0/1 knapsack by benefit-ratio is a classic wrong answer; the optimal method is the @(nW) DP table. COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ★ How examiners reward precision 阅卷怎么给分阅卷怎么给分 On every Q3-Q10 design question, state AND justify both the time and space bound - that is where the marks live. 〔每道设计题都要同时写出并论证时间与空间复杂度。〕 The exam rewards the exact wording: "O(n) expected", "non-negative weights only", "heapify is O(n)", "rotate at the lowest unbalanced node" - precision is marks. 在每道 Q3-Q10 设计题上,都要写出并论证时间与空间两个界 -- 分数就在那里。〔每道设计题都要同时写出并论证时间与空间复杂度。〕考试奖励精确的措辞:“O(n) expected"、"non-negative weights only"、"heapify is O(n)”、 "rotate at the lowest unbalanced node" -- 精确就是分数。 How to drill the glossary 用法 ✓ 用法 Cover the right two columns and recite the meaning from the English term - then flip and recall the English from the 中文. 〔遮住右两列、由术语复述释义;再由中文回想英文。〕 This is open-book paper exam kit: print it, no devices - confirm the rules on your own LMS. 遮住右边两列、由英文术语复述释义 -- 再反过来由中文回想英文。〔遮住右两列、由术语复述释义;再由中文回想英文。〕这是开卷纸笔考试的工具:打印出来,不带设备 -- 在你自己的LMS 上确认规则。[9]Source: asksia-bible-comp90038-bilingual.pdf10 Greedy algorithms Prim · Dijkstra . Huffman . super-source trick → 11 Limitations & intractability P / NP / NP-complete . Hamiltonian vs Euler (light) → Part 5 . Walk in ready 12 Glossary every term EN + +x . the recipe index → 13 Practice bank & worked solutions Q1 traces · Q2 T/F · Q3-Q10 design, re-numbered → 14 Exam morning & the decoder complexity-technique . timing . print-and-bring → i Why this order 为何是这个顺序 COMP90038 follows the Levitin technique-family sequence: first the analysis toolkit (RAM model, asymptotics, recurrences) and brute force, then the four design paradigms in order - decrease-and-conquer, divide-and- conquer, transform-and-conquer (heaps, balanced trees, hashing), dynamic programming and greedy. Each chapter is a stack of recipe cards. Part 5 turns it into marks: a bilingual glossary + recipe index, the re-numbered practice bank, and a one-page exam-morning decoder you flip to first. COMP90038 遵循 Levitin 的技术家族顺序:先是分析工具箱(RAM 模型、渐近、递推)和蛮力,然后按序讲四大设计范式–––减治、分治、变治(堆、平衡树、哈希)、动态规划和贪心。每一章都是一摞配方卡。第5部分把它变成分数: 双语术语表 +配方索引、重新编号的练习库,以及考试当天先翻的一页解码器。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 1 . FOUNDATIONS CH 1 . FOUNDATIONS EXAM CORE The cost model: Word-RAM & the three flavours 代价模型:Word-RAM 与三种口径 Cells, registers & the four 0(1) ops . integer-division quirks . worst / expected / amortised - always say which 单元、寄存器与四种 O(1)操作 · 整数除法的坑 · 最坏 / 期望 /摊还 -- 永远说清是哪种 TL;DR. Every running-time claim in COMP90038 is counted on the Word-RAM machine: memory is an array of fixed-width cells, the CPU has a few registers, and exactly four kinds of atomic operation cost (1) each. Running time = how many atomic ops as a function of input size n; space = how many cells you ever touch. Before you can say an algorithm is "fast" you must say which case you mean - worst, expected, or amortised. Open-book or not, you cannot flip your way out of getting this counting wrong. 太长不看。COMP90038 中每一个运行时间的论断都在 Word-RAM 机器上计数:内存是固定宽度单元组成的数组,CPU 有少量寄存器,恰好有四类原子操作,每个代价为 ⊙(1)。运行时间= 多少次原子操作,作为输入规模 n 的函数;空间=你曾触及多少个单元。在说一个算法“快”之前,你必须说清是哪种情形 -- 最坏、期望还是摊还。开卷与否,你都无法靠翻书绕过把这个计数算错。 ★ What the exam asks here 这里考试问什么 This chapter is the engine room for Q1(j) (the "which complexity statement is correct" MCQ), all of Q2 (true/false with justification - 1 mark answer + 1 mark constants/counterexample), and Q6 (solve a recurrence two ways). The recurring demand: state worst vs expected vs amortised explicitly, and on every Q3-Q10 design answer state AND justify the time and space bound - that is literally where the marks live. 本章是 Q1(j)(“哪条复杂度陈述正确”的 MCQ)、整道 Q2(判断题须给理由 -- 1分答案+1分常数/反例)和 Q6(用两种方法解递推)的发动机房。反复出现的要求:明确说出 worst vs expected vs amortised,并在每道 Q3-Q10 设计答案里给出并论证时间和空间界 -- 分数确实就在那里。

Big-O / $\Omega$ / $\Theta$ 定义要会写常数。[13]Source: asksia-bible-comp90038-bilingual.pdfCOMP90038 . THE OPEN-BOOK REALITY i Open-book logistics - honour these exactly 开卷流程 -- 严格遵守这些 The final is in-person and open book (paper based): authorised materials are paper copies of the textbook, lecture slides and workshop solutions - no devices. That is precisely why this bible is built as a concise per-algorithm recipe companion you can print and bring in, not a memorise-everything sheet. Always confirm the current rules on your own subject LMS. 期末是现场、纸质开卷:允许带入的是教科书、讲义和习题课答案的纸质副本 -- 不准带设备。这正是为什么本 bible 被做成一份逐算法的精炼配方手册,可打印带入,而不是一张死记一切的纸。请务必在你自己的课程 LMS 上确认当前规则。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 1 . FOUNDATIONS 1. 3 Asymptotic notation - the formal definitions 1. 3 渐近记号 -- 形式化定义 To compare orders of growth we drop constants and low-order terms. The three workhorses, each defined by exhibiting constants - and exhibiting those constants is exactly how you earn the justification mark in Q2. 为比较增长阶,我们丢掉常数和低阶项。三大主力,每个都靠给出常数来定义 -- 而给出这些常数正是你在 Q2 中赢得论证分的方式。 THE THREE IN ENGLISH f € 0(g) ⇔ grows no faster than g" f E Q(g) ⇔ "f grows no slower than g" f € 0(g) + 0(g) n Q(g) = "same growth" Formally - the lines to quote in a justification: 形式化地说 -- 在论证里要引用的几行: f(n) E O(g(n) > c > 0, no 20 : f(n) < c . g(n) Vn > no f(n) En(g(n) > c > 0, no 20 : f(n) >c . g(n) Vn > no f(n) E O(g(n) -> C1, C2 > 0, no : cig(n) ≤ f(n) ≤ c2g(n) Vn > no ✓ The limit shortcut (sanity-check, not a proof substitute) 极限捷径(用来检验,不能替代证明) If limno f(n)/g(n) = 0=>feO(g) butf¢@(g); = a positive constant => f = @(g); = = > f € (g) but f ¢ O(g). Handy for ranking log n vs nº - but in an exam still state the constants when asked to justify. 若 limn→∞ f(n)/g(n)=0 ⇒ f ∈O(g) 但 f ∈/ ((g); = 一个正常数⇒ f ∈ 日(g); = ∞ ⇒ f ∈ Ω(g) 但f E/O(g)。用来排序 log n 与 nE 很方便 -- 但考试里被要求论证时仍要写出常数。 i E VS = , and why "tight" matters ∈ vs =,以及为何“紧”很重要 O(g) is a set of functions, so f € 0(g) is cleaner than the common abuse f = O(g). O is an upper bound that need not be tight: n € 0(n2) is true but loose. Use O when you can pin both sides - e. g. selection sort is @(n2), not merely O(n2). - -

$\log(xy)=\log x+\log y$。[16]

$\log_b x=\frac{\log x}{\log b}$。[16]

分治递推：$$T(n)=aT(n/b)+f(n)$$[12]Source: asksia-bible-comp90038-bilingual.pdf太长不看。分治把一个实例切成 a 个规模 n/b 的子实例,递归求解各个,再用 f(n)的工作合并 -- 得到递推 T(n)=a· T(n/b)+f(n)。两种排序住在这里(mergesort、quicksort),而一个工具主宰分数:主定理,它从三个数读出递推的日。考试明确要你背诵并应用它 -- 所以这张卡片就是为 30秒翻查而做的。 ★ What the exam asks here 这里考试问什么 (1) Solve a recurrence two ways - by expansion (backward substitution) and by the Master Theorem, naming all four parameters and the case (the canonical Sample-Q6 type). (2) Identify the O of a given T(n) =aT (n/b)+0(nd) by the a vs bd comparison. (3) State the properties of mergesort / quicksort - worst vs expected, stable?, in-place? (4) Give the postorder of a tree, or reconstruct a tree from preorder + inorder then read off postorder. Always say which flavour of bound: worst / expected. (1) 用两种方法解一个递推 -- 展开法(向后代入)和主定理(Master Theorem),写出全部四个参数和情形(经典样卷 Q6 题型)。(2)通过 a vs bd 比较,判断给定 T(n)=aT(n/b)+(nd)的口。(3) 陈述 mergesort / quicksort 的属性 - worst vs expected、稳定吗?原地吗?(4)给出一棵树的后序,或从前序+中序重建一棵树再读出后序。永远说清是哪种界:worst / expected。 5. 1 The divide-and-conquer template 5. 1 分治模板 Three moves, every time: 三步,每次都一样: - Divide the size-n instance into a sub-instances of size n/b (usually a non-overlapping split, b ≥ 2). Divide把规模为n的实例分成a个规模为n/b的子实例 (通常是不重叠的划分,b≥2)。 - - Conquer each sub-instance by recursion (base case at small n). Conquer 用递归解每个子实例(小 n时为基础情形)。 - Combine the sub-answers into the full answer in f(n) extra work. Combine 以 f(n)的额外工作把子答案合并成完整答案。 THE D&C RECURRENCE D&C recurrence - a sub-instances, size n/b each: T(n) = a . T(n/b) + f(n) a = # sub-problems (branching factor) b = shrink factor (size divides by b) f(n) = divide + combine cost COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 The cost obeys a recurrence whose shape is fixed by the trio (a, b, f) - which is exactly what the Master Theorem consumes. 代价服从一个递推,其形状由三元组(a,b,f)固定 -- 而这正是主定理所消化的。 5. 2 Mergesort - the optimal comparison sort 5. 2 Mergesort –– 最优比较排序 Mergesort splits the array in half, sorts each half recursively, then merges the two sorted halves. The merge is the examinable mechanic: a three-pointer scan that walks both halves and the output in lock-step, in O(n) time. Mergesort 把数组对半切,递归排序每一半,再归并两个有序半。归并是可考的机制:一次三指针扫描,同步走过两个半和输出,时间 O(n)。 C(n) = 2C(n/2) +O(n), C(1) =0 => C(n) = O(nlogn) i The 3-pointer merge in one breath 一口气讲完的三指针归并 Pointers i (left half), j (right half), k (output). Compare L [ i] vs R[j], copy the smaller to out [ k ], advance that pointer and k; when one half empties, copy the rest of the other. To keep mergesort stable, break ties by taking from the left half (L [i] ≤ R [ j], not <). 指针 i (左半)、j(右半)、k (输出)。比较 L[i] 与 R[j],把较小者复制到 out [k],推进那个指针和 k;当一半空了,把另一半剩下的复制过去。要让 mergesort 稳定,平局时从左半取(L[i] ≤ R[j],而非<)。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经

Master Theorem 比较 $a$ 和 $b^d$。[10]Source: asksia-bible-comp90038-bilingual.pdfcombine cost wins (leaf-light) balanced: every level equal recursion dominates (root-light) Worked: mergesort T(n)=2T(n/2) +n a=2, b=2, d=1 -> b^d = 2^1 = 2 = a -> Case 2 -> 0(n log n) Fig 5. 2 - The three-case decision card. Compare a with bd: leaf-light (a<bd) - the combine cost wins; balanced (a=bd) - every level costs the same, pick up a log n; root-light (a>bd) - the recursion dominates and the answer is n^(log_b a). Fig 5. 2 -- 三情形决策卡。把 a 与 bd 比较:叶轻(a<bd)→合并代价占优;平衡(a=bd)→每层代价相同,多出一个 log n;根轻(a>bd)→递归主导,答案为 n^(log_b a)。 ! The whole exam risk is flipping a vs bd 整场考试的风险就在搞反 a 与 bd Write the comparison the same way every time: put a on the left, bd on the right. a < bd - combine wins - @(nd); a = bd -> O(nd log n); a > bd - recursion wins - O(n^{log_b a}). Get the inequality direction backwards and every downstream answer is wrong - this is the #1 lost mark on this topic. 每次都用同样的写法写比较:把 a 放左边,bd 放右边。a < bd →合并取胜→⊙(nd); a = bd → ⊙(nd log n); a > bd → 递归取胜→日(n^{log_b a})。把不等号方向写反,下游每个答案都错 -- 这是本主题第一大失分点。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 5 . DIVIDE & CONQUER + MASTER THM 5. 4 The 4-parameter identification ritual 5. 4 四参数识别仪式 Every Master-Theorem question is the same five steps. Do them in this order and you cannot misfire: 每道主定理题都是同样五步。按这个顺序做,你就不会出错: 1 Read off a - the coefficient (number of recursive calls). 读出 a -- 系数(递归调用次数)。 2 Read off b - the divisor of n inside T(. ). 读出 b -- T(·)内对 n 的除数。 3 Read off f(n) and its exponent d so that f(n)=@(nd) (constant work => d=0; linear => d=1; n2 => d=2; n log n is not a pure nd - flag it). 读出 f(n) 及其指数 d,使 f(n)∈日(n°)(常数工作⇒ d=0;线性⇒ d=1; n2⇒d=2; n log n 不是纯 nd -- 把它标出来)。 4 Compute bd and compare with a. 计算 bd 并与 a 比较。 5 Name the case and write the O. Done. 说出情形并写出 ⊙。完成。 i The four parameters the exam wants named 考试要你命名的四个参数 Sample-Q6 phrasing asks you to give a, b, c, d and the case. Here c is the recurrence's leading constant inside f(n)=c. nd (it does not affect the @ - only d and the a-vs-bd comparison do). State all four anyway; the marks are in showing the identification. 样卷 Q6 的措辞要你给出 a,b,c,d 和情形。这里 c 是递推中 f(n)=c·nd 里的首项常数(它不影响 ⊙ -- 只有 d 和 a- vs-bd 比较影响)。无论如何把四个都写出来;分数在于展示你做了识别。 - 5. 5 Master-Theorem worksheet

$a<b^d \Rightarrow O(n^d)$。[10]Source: asksia-bible-comp90038-bilingual.pdfcombine cost wins (leaf-light) balanced: every level equal recursion dominates (root-light) Worked: mergesort T(n)=2T(n/2) +n a=2, b=2, d=1 -> b^d = 2^1 = 2 = a -> Case 2 -> 0(n log n) Fig 5. 2 - The three-case decision card. Compare a with bd: leaf-light (a<bd) - the combine cost wins; balanced (a=bd) - every level costs the same, pick up a log n; root-light (a>bd) - the recursion dominates and the answer is n^(log_b a). Fig 5. 2 -- 三情形决策卡。把 a 与 bd 比较:叶轻(a<bd)→合并代价占优;平衡(a=bd)→每层代价相同,多出一个 log n;根轻(a>bd)→递归主导,答案为 n^(log_b a)。 ! The whole exam risk is flipping a vs bd 整场考试的风险就在搞反 a 与 bd Write the comparison the same way every time: put a on the left, bd on the right. a < bd - combine wins - @(nd); a = bd -> O(nd log n); a > bd - recursion wins - O(n^{log_b a}). Get the inequality direction backwards and every downstream answer is wrong - this is the #1 lost mark on this topic. 每次都用同样的写法写比较:把 a 放左边,bd 放右边。a < bd →合并取胜→⊙(nd); a = bd → ⊙(nd log n); a > bd → 递归取胜→日(n^{log_b a})。把不等号方向写反,下游每个答案都错 -- 这是本主题第一大失分点。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 5 . DIVIDE & CONQUER + MASTER THM 5. 4 The 4-parameter identification ritual 5. 4 四参数识别仪式 Every Master-Theorem question is the same five steps. Do them in this order and you cannot misfire: 每道主定理题都是同样五步。按这个顺序做,你就不会出错: 1 Read off a - the coefficient (number of recursive calls). 读出 a -- 系数(递归调用次数)。 2 Read off b - the divisor of n inside T(. ). 读出 b -- T(·)内对 n 的除数。 3 Read off f(n) and its exponent d so that f(n)=@(nd) (constant work => d=0; linear => d=1; n2 => d=2; n log n is not a pure nd - flag it). 读出 f(n) 及其指数 d,使 f(n)∈日(n°)(常数工作⇒ d=0;线性⇒ d=1; n2⇒d=2; n log n 不是纯 nd -- 把它标出来)。 4 Compute bd and compare with a. 计算 bd 并与 a 比较。 5 Name the case and write the O. Done. 说出情形并写出 ⊙。完成。 i The four parameters the exam wants named 考试要你命名的四个参数 Sample-Q6 phrasing asks you to give a, b, c, d and the case. Here c is the recurrence's leading constant inside f(n)=c. nd (it does not affect the @ - only d and the a-vs-bd comparison do). State all four anyway; the marks are in showing the identification. 样卷 Q6 的措辞要你给出 a,b,c,d 和情形。这里 c 是递推中 f(n)=c·nd 里的首项常数(它不影响 ⊙ -- 只有 d 和 a- vs-bd 比较影响)。无论如何把四个都写出来;分数在于展示你做了识别。 - 5. 5 Master-Theorem worksheet

$a=b^d \Rightarrow O(n^d\log n)$。[10]Source: asksia-bible-comp90038-bilingual.pdfcombine cost wins (leaf-light) balanced: every level equal recursion dominates (root-light) Worked: mergesort T(n)=2T(n/2) +n a=2, b=2, d=1 -> b^d = 2^1 = 2 = a -> Case 2 -> 0(n log n) Fig 5. 2 - The three-case decision card. Compare a with bd: leaf-light (a<bd) - the combine cost wins; balanced (a=bd) - every level costs the same, pick up a log n; root-light (a>bd) - the recursion dominates and the answer is n^(log_b a). Fig 5. 2 -- 三情形决策卡。把 a 与 bd 比较:叶轻(a<bd)→合并代价占优;平衡(a=bd)→每层代价相同,多出一个 log n;根轻(a>bd)→递归主导,答案为 n^(log_b a)。 ! The whole exam risk is flipping a vs bd 整场考试的风险就在搞反 a 与 bd Write the comparison the same way every time: put a on the left, bd on the right. a < bd - combine wins - @(nd); a = bd -> O(nd log n); a > bd - recursion wins - O(n^{log_b a}). Get the inequality direction backwards and every downstream answer is wrong - this is the #1 lost mark on this topic. 每次都用同样的写法写比较:把 a 放左边,bd 放右边。a < bd →合并取胜→⊙(nd); a = bd → ⊙(nd log n); a > bd → 递归取胜→日(n^{log_b a})。把不等号方向写反,下游每个答案都错 -- 这是本主题第一大失分点。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 5 . DIVIDE & CONQUER + MASTER THM 5. 4 The 4-parameter identification ritual 5. 4 四参数识别仪式 Every Master-Theorem question is the same five steps. Do them in this order and you cannot misfire: 每道主定理题都是同样五步。按这个顺序做,你就不会出错: 1 Read off a - the coefficient (number of recursive calls). 读出 a -- 系数(递归调用次数)。 2 Read off b - the divisor of n inside T(. ). 读出 b -- T(·)内对 n 的除数。 3 Read off f(n) and its exponent d so that f(n)=@(nd) (constant work => d=0; linear => d=1; n2 => d=2; n log n is not a pure nd - flag it). 读出 f(n) 及其指数 d,使 f(n)∈日(n°)(常数工作⇒ d=0;线性⇒ d=1; n2⇒d=2; n log n 不是纯 nd -- 把它标出来)。 4 Compute bd and compare with a. 计算 bd 并与 a 比较。 5 Name the case and write the O. Done. 说出情形并写出 ⊙。完成。 i The four parameters the exam wants named 考试要你命名的四个参数 Sample-Q6 phrasing asks you to give a, b, c, d and the case. Here c is the recurrence's leading constant inside f(n)=c. nd (it does not affect the @ - only d and the a-vs-bd comparison do). State all four anyway; the marks are in showing the identification. 样卷 Q6 的措辞要你给出 a,b,c,d 和情形。这里 c 是递推中 f(n)=c·nd 里的首项常数(它不影响 ⊙ -- 只有 d 和 a- vs-bd 比较影响)。无论如何把四个都写出来;分数在于展示你做了识别。 - 5. 5 Master-Theorem worksheet

$a>b^d \Rightarrow O(n^{\log_b a})$。[10]Source: asksia-bible-comp90038-bilingual.pdfcombine cost wins (leaf-light) balanced: every level equal recursion dominates (root-light) Worked: mergesort T(n)=2T(n/2) +n a=2, b=2, d=1 -> b^d = 2^1 = 2 = a -> Case 2 -> 0(n log n) Fig 5. 2 - The three-case decision card. Compare a with bd: leaf-light (a<bd) - the combine cost wins; balanced (a=bd) - every level costs the same, pick up a log n; root-light (a>bd) - the recursion dominates and the answer is n^(log_b a). Fig 5. 2 -- 三情形决策卡。把 a 与 bd 比较:叶轻(a<bd)→合并代价占优;平衡(a=bd)→每层代价相同,多出一个 log n;根轻(a>bd)→递归主导,答案为 n^(log_b a)。 ! The whole exam risk is flipping a vs bd 整场考试的风险就在搞反 a 与 bd Write the comparison the same way every time: put a on the left, bd on the right. a < bd - combine wins - @(nd); a = bd -> O(nd log n); a > bd - recursion wins - O(n^{log_b a}). Get the inequality direction backwards and every downstream answer is wrong - this is the #1 lost mark on this topic. 每次都用同样的写法写比较:把 a 放左边,bd 放右边。a < bd →合并取胜→⊙(nd); a = bd → ⊙(nd log n); a > bd → 递归取胜→日(n^{log_b a})。把不等号方向写反,下游每个答案都错 -- 这是本主题第一大失分点。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 5 . DIVIDE & CONQUER + MASTER THM 5. 4 The 4-parameter identification ritual 5. 4 四参数识别仪式 Every Master-Theorem question is the same five steps. Do them in this order and you cannot misfire: 每道主定理题都是同样五步。按这个顺序做,你就不会出错: 1 Read off a - the coefficient (number of recursive calls). 读出 a -- 系数(递归调用次数)。 2 Read off b - the divisor of n inside T(. ). 读出 b -- T(·)内对 n 的除数。 3 Read off f(n) and its exponent d so that f(n)=@(nd) (constant work => d=0; linear => d=1; n2 => d=2; n log n is not a pure nd - flag it). 读出 f(n) 及其指数 d,使 f(n)∈日(n°)(常数工作⇒ d=0;线性⇒ d=1; n2⇒d=2; n log n 不是纯 nd -- 把它标出来)。 4 Compute bd and compare with a. 计算 bd 并与 a 比较。 5 Name the case and write the O. Done. 说出情形并写出 ⊙。完成。 i The four parameters the exam wants named 考试要你命名的四个参数 Sample-Q6 phrasing asks you to give a, b, c, d and the case. Here c is the recurrence's leading constant inside f(n)=c. nd (it does not affect the @ - only d and the a-vs-bd comparison do). State all four anyway; the marks are in showing the identification. 样卷 Q6 的措辞要你给出 a,b,c,d 和情形。这里 c 是递推中 f(n)=c·nd 里的首项常数(它不影响 ⊙ -- 只有 d 和 a- vs-bd 比较影响)。无论如何把四个都写出来;分数在于展示你做了识别。 - 5. 5 Master-Theorem worksheet

binary search：$C(n)=C(\lfloor n/2\rfloor)+1$。[15]Source: asksia-bible-comp90038-bilingual.pdf! An adjacency matrix blows the bound to O(V2) 用邻接矩阵会把界抬到 O(V2) If you flood-fill over a matrix, finding each node's neighbours scans a full row of n cells = O(V2), missing the target. The O(V+E) claim requires adjacency lists. Say so explicitly, or you forfeit the bound. 若你在矩阵上做洪泛填充,找每个结点的邻居要扫一整行 n 个单元⇒ O(V2),达不到目标。O(V+E)的论断要求用邻接表。明确说出来,否则你拿不到那个界。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 WEX 3. 2 Components of a fresh graph + the two-bound justification CH 3 . Q8 type . 5 marks Fresh undirected graph (re-numbered): nodes 1-8; edges 1-2, 2-3, 1-3, 4-5, 6-7, 7-8, 6-8. Flood-fill in node order: 新无向图(重新编号):结点1-8;边 1-2、2-3、1-3、4-5、6-7、7-8、6-8。按结点序做 flood-fill: 1 Node 1 ungrouped - gid 1: BFS reaches {1, 2, 3}. 节点 1 未分组 → gid 1: BFS 到达{1, 2, 3}。 2 Node 4 ungrouped - gid 2: BFS reaches {4, 5}. 节点 4 未分组 → gid 2: BFS 到达{4,5}。 3 Node 6 ungrouped - gid 3: BFS reaches {6, 7, 8}. 节点 6 未分组 → gid 3: BFS 到达{6, 7,8}。 Answer: 3 components - {1,2,3}, {4,5}, {6,7,8}. Justify: each of the 8 nodes is labelled once and each of the 7 edges is scanned twice (once per endpoint) = O(V+E) time; storage is the adjacency lists O(V+E) plus an O(V) group array plus an O(V) queue = O(V+E) space. 答案:3个分量 -- {1,2,3}、{4,5}、{6,7,8}。论证:8个结点各被标记一次,7条边各被扫描两次(每个端点一次)⇒ O(V+E)时间;存储是邻接表 O(V+E)加一个 O(V)的分组数组加一个 O(V)的队列⇒ O(V+E)空间。 Open book is a trap: you can't flip to 'your' graph. Bring the recipe - pick a structure, flood, then write both bounds in one breath. 开卷是个陷阱:你翻不到‘你的’那张图。带上配方 -- 挑一个结构、flood、然后一口气写出两个界。 COMP90038 . THE COMPONENTS RECIPE CARD COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 4 . DECREASE - AND - CONQUER - CHAPTER 4 . DECREASE - AND - CONQUER EXAM CORE Shrink the problem, reuse the answer 缩小问题,复用答案 Decrease-by-constant. by-constant-factor (-> log) . by-variable-size . insertion sort . binary search . quickselect 减常量 · 减常数因子(→ log) · 减可变量 · 插入排序 · 二分查找 · 快速选择 TL;DR. Decrease-and-conquer solves a problem by reducing it to one smaller instance, solving that, then extending the answer - unlike divide-and-conquer (Ch 5), which solves several sub-instances. Three flavours, each a different shrink rule: by a constant (insertion sort, peel one element), by a constant factor (binary search, halve => logarithmic), and by a variable size (Lomuto partition => quickselect). The open- book payoff: each is a one-card recipe - technique - steps - cost (state worst / best / expected) -+ hand-trace - trap. 太长不看。减治法通过把问题缩减为一个更小实例、求解之、再扩展答案来解决问题 -- 这不同于分治(Ch 5),后者求解若干子实例。三种口味,各有不同的缩减规则:减常量(插入排序,剥掉一个元素)、减常数因子(二分查找,对半⇒对数级)、减可变量(Lomuto 划分⇒快速选择)。开卷的收益:每个都是一张套路卡 -- 技术→步骤→代价(说清最坏/最好/期望)→手算→ 陷阱。 ★ What the exam asks here 这里考试问什么 (1) Solve C(n)=C([n/2])+1 for binary search and state the closed form [ log_n ]+1 (Q2 true/false-with-justification, Q6-style recurrence). (2) Hand-trace a Lomuto partition - give the array after the pivot lands and the returned split index s. (3) Run quickselect for the k-th smallest and state worst O(n2) vs expected O(n) - the marks are in naming which. (4) State insertion sort's three cases (best/worst/stable/in-place). Every cost answer must name the flavour: worst / best /expected. (1) 为二分查找解 C(n)=C(In/2])+1并陈述闭式 [log2n]+1(Q2 判断题须给理由、Q6式递推)。(2)手算追踪一次 Lomuto partition -- 给出枢轴落定后的数组和返回的分割下标 s。(3)为第 k小跑 quickselect 并陈述 worst O(n2) vs expected O(n) -- 分数在于点出是哪个。(4)陈述 insertion sort 的三种情况(best/worst/stable/in-place)。每个代价答案都要点出种类: worst / best / expected

quickselect：expected $O(n)$，worst $O(n^2)$。[8]Source: asksia-bible-comp90038-bilingual.pdfO(n) expected COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 EX 4C Quickselect for the 3rd-smallest (fresh array) L . k-selection trace Find the 3rd-smallest (k=3, 1-indexed rank) of A = [5, 3, 8, 1, 9, 2, 7], reusing EX 4B's first partition. 找出 A = [5, 3, 8,1, 9, 2, 7] 的第3小(k=3,1起始秩),复用 EX 4B的首次划分。 1 Partition the whole array (pivot 5) - [2, 3, 1 | 5 | 9, 8, 7], pivot rank s = 4 (1-indexed: three elements below it). We want rank k=3 < 4 => recurse into the left part {2, 3, 1} only - discard the right. 对整个数组划分(pivot 5)→ [2, 3, 1 | 5 | 9, 8, 7],pivot 的秩 s=4 (1-索引:其下有三个元素)。我们要秩 k=3<4⇒只递归进入左部{2,3,1} -- 丢弃右部。 2 Partition the left {2, 3, 1} (pivot 2): 1 < 2 goes left, 3 stays right - [1 | 2 | 3], pivot 2 has rank 2. We want k=3 > 2 => recurse right into {3}. 划分左部{2,3,1} (pivot 2): 1<2入左,3留右→[1 | 2 | 3],pivot 2 的秩为 2。我们要 k=3>2⇒ 向右递归进入{3}。 3 Single element {3} - its rank is exactly 3. Answer: 3rd-smallest = 3. We never sorted {9,8,7} - that whole side was thrown away after step 1. 单元素{3}其秩恰为 3。答案:第3小=3。我们从未排序{9,8,7} -- 那整一侧在第1步后就被丢弃了。 ! Quickselect worst case is O(n2), NOT O(n) 快速选择最坏情形是 O(n2),不是 O(n) Saying "quickselect is O(n)" unqualified is wrong - that is the expected (randomized / good-pivot) cost. The worst case is O(n2) when every pivot peels off one element (already-sorted input, first-element pivot). Always write O(n) expected, O(n2) worst - the marks live in that label. 不加限定地说“quickselect 是 O(n)”是错的 -- 那是期望(随机化/好枢轴)代价。当每个枢轴都只剥下一个元素时(已排序输入、首元素枢轴),最坏情况是 ⊙(n2)。永远写 O(n) expected, O(n2) worst -- 分数就在那个标签里。 "Halve it and it's log; peel one and sum the series; partition and pray for a good pivot. " “对半砍它就是 log;剥一个就把级数求和;划分后就祈祷有个好 pivot。” DECREASE - AND-CONQUER, IN ONE BREATH ★ Recipe-card recap - CH 4 in six lines 套路卡回顾 -- CH 4 六行速览 (1) Three patterns: decrease-by-constant (peel), by-constant-factor (halve -+ log), by-variable-size (partition). (2) Insertion sort: best @(n) sorted, worst/avg O(n2), stable + in-place, input-sensitive. (3) Binary search: C(n)=C([n/2])+1 = [log,n ]+1; 106 keys - 20 comparisons. (4) Fast exponentiation a": halve the exponent => O(log n) mults. (5) Lomuto: pivot=A[lo], s tracks last < p, final swap puts pivot at rank s - report (array, s). (6) Quickselect: O(n) expected / good-pivot, O(n2) worst - always name which. (1) 三种模式:减常数(剥)、减常数因子(对半→ log)、减可变量(划分)。(2) Insertion sort: 已排序最好 ⊙(n),最坏/平均 ⊙(n2),稳定+原地,输入敏感。(3)二分查找:C(n)=C(In/2])+1= [log2n]+1; 106 个键→20 次比较。(4) 快速幂 an: 对半指数⇒ O(log n)次乘法。(5) Lomuto:枢轴=A[lo],s跟踪最后一个<p 的位置,最终交换把枢轴放到名次 s -- 报告(array, s)。(6) Quickselect: O(n)期望 /好枢轴,O(n2)最坏 -- 永远点出是哪个。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 5 . DIVIDE & CONQUER + MASTER THM EXAM CORE CH 5 . DIVIDE & CONQUER Split in half, solve, combine 对半切分、求解、合并 Mergesort . quicksort . the Master Theorem . tree traversal . reconstruct-then-read-postorder Mergesort · quicksort · 主定理 · 树遍历 · 重建后读后序 TL;DR. Divide-and-conquer splits an instance into a sub-instances of size n/b, solves each recursively, then combines in f(n) work - giving the recurrence T(n)=a . T(n/b)+f(n). Two sorts live here (mergesort, quicksort) and one tool dominates the marks: the Master Theorem, which reads a recurrence's O off three numbers. The exam explicitly tells you to memorise and apply it - so this card is built to be flipped to in 30 seconds.

mergesort：$O(n\log n)$，merge 是三指针。[12]Source: asksia-bible-comp90038-bilingual.pdf太长不看。分治把一个实例切成 a 个规模 n/b 的子实例,递归求解各个,再用 f(n)的工作合并 -- 得到递推 T(n)=a· T(n/b)+f(n)。两种排序住在这里(mergesort、quicksort),而一个工具主宰分数:主定理,它从三个数读出递推的日。考试明确要你背诵并应用它 -- 所以这张卡片就是为 30秒翻查而做的。 ★ What the exam asks here 这里考试问什么 (1) Solve a recurrence two ways - by expansion (backward substitution) and by the Master Theorem, naming all four parameters and the case (the canonical Sample-Q6 type). (2) Identify the O of a given T(n) =aT (n/b)+0(nd) by the a vs bd comparison. (3) State the properties of mergesort / quicksort - worst vs expected, stable?, in-place? (4) Give the postorder of a tree, or reconstruct a tree from preorder + inorder then read off postorder. Always say which flavour of bound: worst / expected. (1) 用两种方法解一个递推 -- 展开法(向后代入)和主定理(Master Theorem),写出全部四个参数和情形(经典样卷 Q6 题型)。(2)通过 a vs bd 比较,判断给定 T(n)=aT(n/b)+(nd)的口。(3) 陈述 mergesort / quicksort 的属性 - worst vs expected、稳定吗?原地吗?(4)给出一棵树的后序,或从前序+中序重建一棵树再读出后序。永远说清是哪种界:worst / expected。 5. 1 The divide-and-conquer template 5. 1 分治模板 Three moves, every time: 三步,每次都一样: - Divide the size-n instance into a sub-instances of size n/b (usually a non-overlapping split, b ≥ 2). Divide把规模为n的实例分成a个规模为n/b的子实例 (通常是不重叠的划分,b≥2)。 - - Conquer each sub-instance by recursion (base case at small n). Conquer 用递归解每个子实例(小 n时为基础情形)。 - Combine the sub-answers into the full answer in f(n) extra work. Combine 以 f(n)的额外工作把子答案合并成完整答案。 THE D&C RECURRENCE D&C recurrence - a sub-instances, size n/b each: T(n) = a . T(n/b) + f(n) a = # sub-problems (branching factor) b = shrink factor (size divides by b) f(n) = divide + combine cost COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 The cost obeys a recurrence whose shape is fixed by the trio (a, b, f) - which is exactly what the Master Theorem consumes. 代价服从一个递推,其形状由三元组(a,b,f)固定 -- 而这正是主定理所消化的。 5. 2 Mergesort - the optimal comparison sort 5. 2 Mergesort –– 最优比较排序 Mergesort splits the array in half, sorts each half recursively, then merges the two sorted halves. The merge is the examinable mechanic: a three-pointer scan that walks both halves and the output in lock-step, in O(n) time. Mergesort 把数组对半切,递归排序每一半,再归并两个有序半。归并是可考的机制:一次三指针扫描,同步走过两个半和输出,时间 O(n)。 C(n) = 2C(n/2) +O(n), C(1) =0 => C(n) = O(nlogn) i The 3-pointer merge in one breath 一口气讲完的三指针归并 Pointers i (left half), j (right half), k (output). Compare L [ i] vs R[j], copy the smaller to out [ k ], advance that pointer and k; when one half empties, copy the rest of the other. To keep mergesort stable, break ties by taking from the left half (L [i] ≤ R [ j], not <). 指针 i (左半)、j(右半)、k (输出)。比较 L[i] 与 R[j],把较小者复制到 out [k],推进那个指针和 k;当一半空了,把另一半剩下的复制过去。要让 mergesort 稳定,平局时从左半取(L[i] ≤ R[j],而非<)。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经

heapify：$O(n)$，不是 $O(n\log n)$。[6]Source: asksia-bible-comp90038-bilingual.pdfAlways label which. Quickselect/quicksort: O(n2) worst but O(n)/O(n log n) expected - the good bound needs randomisation. Master case a vs b7 a < b7 => O(n7) (leaf-light); a = b7 => O(n7 log n); a > b7 => O(n^{log_b a}). Easy to flip the inequality. Matrix vs list traversal Adjacency matrix => O(V2); adjacency list => O(V+E). The single most-tested representation distinction. DFS topsort order Output in reverse pop/finish order, not push order; break ties alphabetically per the exam convention. Min vs max heap Read the question. Sample uses a MIN-heap; child(i)=2i,2i+1; heapify is O(n), not O(n log n). LR vs RL rotation Look at where the new key landed relative to the lowest unbalanced node, not just the shape; rotate the median up. 2-3 split promotes On overflow of a 3-node (3 keys), promote the middle key up; height grows only when the root splits. Chaining vs linear probing Same keys, different mechanics: chaining - longest chain length; probing - cell placement with wrap-around + clustering. Prim vs Dijkstra Same skeleton, different priority: Prim = lightest crossing edge; Dijkstra = smallest distance from source. MST # shortest-path tree. Warshall vs Floyd Warshall uses v/A on a 0/1 matrix (closure); Floyd uses min/+ on a weight matrix (co for no edge). k is the outermost loop in both. Greedy vs DP knapsack 0/1 knapsack by benefit-ratio is a classic wrong answer; the optimal method is the @(nW) DP table. COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ★ How examiners reward precision 阅卷怎么给分阅卷怎么给分 On every Q3-Q10 design question, state AND justify both the time and space bound - that is where the marks live. 〔每道设计题都要同时写出并论证时间与空间复杂度。〕 The exam rewards the exact wording: "O(n) expected", "non-negative weights only", "heapify is O(n)", "rotate at the lowest unbalanced node" - precision is marks. 在每道 Q3-Q10 设计题上,都要写出并论证时间与空间两个界 -- 分数就在那里。〔每道设计题都要同时写出并论证时间与空间复杂度。〕考试奖励精确的措辞:“O(n) expected"、"non-negative weights only"、"heapify is O(n)”、 "rotate at the lowest unbalanced node" -- 精确就是分数。 How to drill the glossary 用法 ✓ 用法 Cover the right two columns and recite the meaning from the English term - then flip and recall the English from the 中文. 〔遮住右两列、由术语复述释义;再由中文回想英文。〕 This is open-book paper exam kit: print it, no devices - confirm the rules on your own LMS. 遮住右边两列、由英文术语复述释义 -- 再反过来由中文回想英文。〔遮住右两列、由术语复述释义;再由中文回想英文。〕这是开卷纸笔考试的工具:打印出来,不带设备 -- 在你自己的LMS 上确认规则。[14]Source: asksia-bible-comp90038-bilingual.pdfFresh AskSia tree. Preorder = F . B . A . D . C . E . G . I . H; inorder = A . B . C . D . E . F . G . H . I. Reconstruct, then give the postorder. 新 AskSia 树。前序=F · B · A· D · C · E · G · I· H;中序=A · B· C· D· E · F · G· H· I。重建之,再给出后序。 1 Root = preorder[0] = F. Find F in inorder: it splits into left = A B C D E and right = G H I. 根 = preorder[0]= F。在 inorder 中找 F: 它把序列分为左= A B C D E 和右= G H I。 2 Left subtree - its preorder is the next 5 of the preorder stream (B A D C E). Root = B; in inorder A B C D E, B splits into left A (a leaf) and right C D E. Recurse on the right: root D, with leaf C left and leaf E right. 左子树 -- 其 preorder 是 preorder 流接下来的5 个(B A D C E)。根= B;在 inorder A B C D E 中,B 把它分为左 A(叶子)和右 C D E。对右部递归:根 D,左叶 C、右叶 E。 - 3 Right subtree - preorder G I H; root = G; inorder G H I => nothing left of G, H I right. Recurse: root I, with leaf H as its left child. 右子树 -- preorder G I H;根= G; inorder G H I ⇒ G 左侧无物,H I 在右。递归:根 I,以叶 H 为其左孩子。 4 Read off postorder (L, R, root) bottom-up: left subtree A C E D B, right subtree H I G, then root F. 读出 postorder (L, R, root),自底向上:左子树 A C E D B,右子树 H I G,最后是根 F。 ANSWER postorder = A . C . E . D . B . H . I . G . F ! Preorder gives the ROOT; inorder SPLITS L | R 前序给出根;中序把左 | 右分开 The classic mix-up is swapping the two roles. Preorder[O] is always the next subtree's root; you then locate that root in the inorder list to decide which keys go left and which go right. Off-by-one in the inorder split (or using preorder to split) corrupts the whole subtree. Cross-check: an inorder of a BST must come out sorted. 经典混淆是把两个角色弄反。前序[0]永远是下一棵子树的根;然后你在中序列表里定位那个根,以决定哪些键归左、哪些归右。中序拆分差一位(或用前序去拆分)会毁掉整棵子树。交叉核对:BST 的中序必须排出有序结果。 i §5. 4 closest-pair is NON-examinable (context only) §5. 4 最近点对不可考(仅作背景) Levitin §5. 4 (the 2D closest-pair divide-and-conquer, O(n log n)) is excluded from the examinable scope per the Week-6 reading and the slide note. Know that D&C also solves closest-pair (split by x-median, recurse, merge the strip) - but do not spend exam time rehearsing it; only §5. 1-5. 3 are tested. 按第 6 周阅读和讲义注记,Levitin $5. 4 (二维最近点对分治,O(n log n))不在考查范围。要知道 D&C 也能解最近点对(按 x 中位数划分、递归、合并那条带) -- 但不要在考试时间里排练它;只有 §5. 1-5. 3 被考。 - COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 6 . HEAPS & PQ CHAPTER 6 . HEAPS, HEAPSORT & PRIORITY QUEUES EXAM CORE The complete tree that lives in an array 活在数组里的完全二叉树 PQ ADT . 1-indexed layout . bubble-up / down . heapify O(n) . heapsort PQ ADT · 1 起始下标布局 · 上浮 / 下沉 · heapify O(n) · heapsort TL;DR. A priority queue hands you the most-urgent element on demand. The fast implementation is a binary heap: a complete binary tree stored in a plain array, so a node at index i finds its children at 2i, 2i+1 and its parent at [ i/2] - no pointers. push, pop and update-key are all O(log n) via a single sift; building a heap from a raw array (heapify) is O(n), not O(n log n); and heapsort sorts in O(n log n), in place, but not stably. Read the question for min vs max - the sample exam's heap question is a min-heap. 太长不看。优先队列按需把最紧急的元素递给你。快速实现是二叉堆:一棵完全二叉树存在普通数组里,于是下标 i 的结点在 2i,2i+1 找孩子、在 [i/2]找父亲 -- 无指针。push、pop 和 update-key 都靠一次筛动而为 O(log n);从原始数组建堆(heapify)是 O(n)而非 O(n log n); heapsort 以 O(n log n)原地排序,但不稳定。读题分清 min vs max––样卷的堆题是 min-heap。 ★ What the exam asks here 这里考试问什么

Dijkstra 只适用于 non-negative weights。[6]Source: asksia-bible-comp90038-bilingual.pdfAlways label which. Quickselect/quicksort: O(n2) worst but O(n)/O(n log n) expected - the good bound needs randomisation. Master case a vs b7 a < b7 => O(n7) (leaf-light); a = b7 => O(n7 log n); a > b7 => O(n^{log_b a}). Easy to flip the inequality. Matrix vs list traversal Adjacency matrix => O(V2); adjacency list => O(V+E). The single most-tested representation distinction. DFS topsort order Output in reverse pop/finish order, not push order; break ties alphabetically per the exam convention. Min vs max heap Read the question. Sample uses a MIN-heap; child(i)=2i,2i+1; heapify is O(n), not O(n log n). LR vs RL rotation Look at where the new key landed relative to the lowest unbalanced node, not just the shape; rotate the median up. 2-3 split promotes On overflow of a 3-node (3 keys), promote the middle key up; height grows only when the root splits. Chaining vs linear probing Same keys, different mechanics: chaining - longest chain length; probing - cell placement with wrap-around + clustering. Prim vs Dijkstra Same skeleton, different priority: Prim = lightest crossing edge; Dijkstra = smallest distance from source. MST # shortest-path tree. Warshall vs Floyd Warshall uses v/A on a 0/1 matrix (closure); Floyd uses min/+ on a weight matrix (co for no edge). k is the outermost loop in both. Greedy vs DP knapsack 0/1 knapsack by benefit-ratio is a classic wrong answer; the optimal method is the @(nW) DP table. COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ★ How examiners reward precision 阅卷怎么给分阅卷怎么给分 On every Q3-Q10 design question, state AND justify both the time and space bound - that is where the marks live. 〔每道设计题都要同时写出并论证时间与空间复杂度。〕 The exam rewards the exact wording: "O(n) expected", "non-negative weights only", "heapify is O(n)", "rotate at the lowest unbalanced node" - precision is marks. 在每道 Q3-Q10 设计题上,都要写出并论证时间与空间两个界 -- 分数就在那里。〔每道设计题都要同时写出并论证时间与空间复杂度。〕考试奖励精确的措辞:“O(n) expected"、"non-negative weights only"、"heapify is O(n)”、 "rotate at the lowest unbalanced node" -- 精确就是分数。 How to drill the glossary 用法 ✓ 用法 Cover the right two columns and recite the meaning from the English term - then flip and recall the English from the 中文. 〔遮住右两列、由术语复述释义;再由中文回想英文。〕 This is open-book paper exam kit: print it, no devices - confirm the rules on your own LMS. 遮住右边两列、由英文术语复述释义 -- 再反过来由中文回想英文。〔遮住右两列、由术语复述释义;再由中文回想英文。〕这是开卷纸笔考试的工具:打印出来,不带设备 -- 在你自己的LMS 上确认规则。[11]Source: asksia-bible-comp90038-bilingual.pdfThree ways to lose the 8 marks: (1) run Dijkstra once per depot (too slow by a factor k); (2) forget to justify k ≤n (so the +k terms vanish into O((n+m) log n)); (3) use negative weights - Dijkstra's greedy pick fails; that is Bellman-Ford territory. 三种丢掉这 8分的方式:(1)每个仓库各跑一次 Dijkstra(慢了k倍);(2)忘记论证 k ≤ n(这样 +k 项才并入 O((n+m) log n));(3)用负权 -- Dijkstra 的贪心选择失效;那是 Bellman-Ford 的地盘。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 12 . PRACTICE - PART C CLOSE . THE DECODER, THE TIMING, THE OPEN-BOOK REMINDER OPEN BOOK . PAPER ONLY Match the required bound to the technique - then write it 把所需的界匹配到技术 -- 然后写出来 The single most valuable card: complexity-target - technique, plus the 180-minute triage and the print-and- bring rule 单张最有价值的卡片:复杂度目标→技术,外加 180 分钟分诊和打印带入规则 FIG 12. 4 What does the problem look like? - > which TECHNIQUE Brute force solve straight from the definition; tiny n selection sort, string match O(n^2) Decrease & conquer shrink instance by 1 or by a factor binary search, insertion sort, topsort Divide & conquer split, recurse on parts, combine mergesort, quicksort T=aT(n/b)+f(n) Transform & conquer presort / change representation first presort+scan, AVL / 2-3, hashing Space-time tradeoff bounded universe |U|=O(n) -> spend space counting sort, Horspool, hash table Dynamic programming overlapping sub-problems + optimal substructure knapsack, coin-row, Floyd/Warshall Greedy locally-best step, provably global Prim/Dijkstra MST/SP, Huffman Fig 12. 4 - the design-technique decoder. Read the required complexity off the prompt and it names the technique: bounded universe + 0(n) - counting/direct-address; unbounded + 0(n log n) > presort + scan; 0(n) expected > universal hashing; single-source shortest path - Dijkstra + heap; min-cost spanning - Prim/Kruskal; all-pairs dense - Floyd/Warshall 0(n3); components - BFS/DFS flood-fill 0(n+m); overlapping subproblems - DP; recurrence aT(n/b)+0(na) - Master Theorem. Fig 12. 4 -- 设计技术解码器。从题干读出要求的复杂度,它便点出技术:有界全集+O(n)→ counting/direct-address; 无界+O(n log n) → presort + scan; O(n) expected → universal hashing; 单源最短路 → Dijkstra+ heap; 最小代价生成→ Prim/Kruskal;稠密全点对→ Floyd/Warshall e(n3);连通分量→ BFS/DFS flood-fill O(n+m);重叠子问题→ DP;递推 aT(n/b)+ (nd) → Master Theorem。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ★ 180-minute triage (15 min reading included) 180 分钟分诊(含 15分钟读题) Use the 15 min reading to triage: tick the Q1 traces you can do in your head, flag the high-mark Q3-Q10. Budget ~3 min per Q1 MCQ (do the full margin trace); on Q2 always show the constants / counterexample; on Q3-Q10 state AND justify the time AND space bound and label worst / expected / amortised - that is where the marks are.

Prim 求 MST，Dijkstra 求 shortest paths。[6]Source: asksia-bible-comp90038-bilingual.pdfAlways label which. Quickselect/quicksort: O(n2) worst but O(n)/O(n log n) expected - the good bound needs randomisation. Master case a vs b7 a < b7 => O(n7) (leaf-light); a = b7 => O(n7 log n); a > b7 => O(n^{log_b a}). Easy to flip the inequality. Matrix vs list traversal Adjacency matrix => O(V2); adjacency list => O(V+E). The single most-tested representation distinction. DFS topsort order Output in reverse pop/finish order, not push order; break ties alphabetically per the exam convention. Min vs max heap Read the question. Sample uses a MIN-heap; child(i)=2i,2i+1; heapify is O(n), not O(n log n). LR vs RL rotation Look at where the new key landed relative to the lowest unbalanced node, not just the shape; rotate the median up. 2-3 split promotes On overflow of a 3-node (3 keys), promote the middle key up; height grows only when the root splits. Chaining vs linear probing Same keys, different mechanics: chaining - longest chain length; probing - cell placement with wrap-around + clustering. Prim vs Dijkstra Same skeleton, different priority: Prim = lightest crossing edge; Dijkstra = smallest distance from source. MST # shortest-path tree. Warshall vs Floyd Warshall uses v/A on a 0/1 matrix (closure); Floyd uses min/+ on a weight matrix (co for no edge). k is the outermost loop in both. Greedy vs DP knapsack 0/1 knapsack by benefit-ratio is a classic wrong answer; the optimal method is the @(nW) DP table. COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 ★ How examiners reward precision 阅卷怎么给分阅卷怎么给分 On every Q3-Q10 design question, state AND justify both the time and space bound - that is where the marks live. 〔每道设计题都要同时写出并论证时间与空间复杂度。〕 The exam rewards the exact wording: "O(n) expected", "non-negative weights only", "heapify is O(n)", "rotate at the lowest unbalanced node" - precision is marks. 在每道 Q3-Q10 设计题上,都要写出并论证时间与空间两个界 -- 分数就在那里。〔每道设计题都要同时写出并论证时间与空间复杂度。〕考试奖励精确的措辞:“O(n) expected"、"non-negative weights only"、"heapify is O(n)”、 "rotate at the lowest unbalanced node" -- 精确就是分数。 How to drill the glossary 用法 ✓ 用法 Cover the right two columns and recite the meaning from the English term - then flip and recall the English from the 中文. 〔遮住右两列、由术语复述释义;再由中文回想英文。〕 This is open-book paper exam kit: print it, no devices - confirm the rules on your own LMS. 遮住右边两列、由英文术语复述释义 -- 再反过来由中文回想英文。〔遮住右两列、由术语复述释义;再由中文回想英文。〕这是开卷纸笔考试的工具:打印出来,不带设备 -- 在你自己的LMS 上确认规则。

adjacency list 下 flood-fill 为 $O(V+E)$；matrix 会变成 $O(V^2)$。[15]Source: asksia-bible-comp90038-bilingual.pdf! An adjacency matrix blows the bound to O(V2) 用邻接矩阵会把界抬到 O(V2) If you flood-fill over a matrix, finding each node's neighbours scans a full row of n cells = O(V2), missing the target. The O(V+E) claim requires adjacency lists. Say so explicitly, or you forfeit the bound. 若你在矩阵上做洪泛填充,找每个结点的邻居要扫一整行 n 个单元⇒ O(V2),达不到目标。O(V+E)的论断要求用邻接表。明确说出来,否则你拿不到那个界。 COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 WEX 3. 2 Components of a fresh graph + the two-bound justification CH 3 . Q8 type . 5 marks Fresh undirected graph (re-numbered): nodes 1-8; edges 1-2, 2-3, 1-3, 4-5, 6-7, 7-8, 6-8. Flood-fill in node order: 新无向图(重新编号):结点1-8;边 1-2、2-3、1-3、4-5、6-7、7-8、6-8。按结点序做 flood-fill: 1 Node 1 ungrouped - gid 1: BFS reaches {1, 2, 3}. 节点 1 未分组 → gid 1: BFS 到达{1, 2, 3}。 2 Node 4 ungrouped - gid 2: BFS reaches {4, 5}. 节点 4 未分组 → gid 2: BFS 到达{4,5}。 3 Node 6 ungrouped - gid 3: BFS reaches {6, 7, 8}. 节点 6 未分组 → gid 3: BFS 到达{6, 7,8}。 Answer: 3 components - {1,2,3}, {4,5}, {6,7,8}. Justify: each of the 8 nodes is labelled once and each of the 7 edges is scanned twice (once per endpoint) = O(V+E) time; storage is the adjacency lists O(V+E) plus an O(V) group array plus an O(V) queue = O(V+E) space. 答案:3个分量 -- {1,2,3}、{4,5}、{6,7,8}。论证:8个结点各被标记一次,7条边各被扫描两次(每个端点一次)⇒ O(V+E)时间;存储是邻接表 O(V+E)加一个 O(V)的分组数组加一个 O(V)的队列⇒ O(V+E)空间。 Open book is a trap: you can't flip to 'your' graph. Bring the recipe - pick a structure, flood, then write both bounds in one breath. 开卷是个陷阱:你翻不到‘你的’那张图。带上配方 -- 挑一个结构、flood、然后一口气写出两个界。 COMP90038 . THE COMPONENTS RECIPE CARD COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 4 . DECREASE - AND - CONQUER - CHAPTER 4 . DECREASE - AND - CONQUER EXAM CORE Shrink the problem, reuse the answer 缩小问题,复用答案 Decrease-by-constant. by-constant-factor (-> log) . by-variable-size . insertion sort . binary search . quickselect 减常量 · 减常数因子(→ log) · 减可变量 · 插入排序 · 二分查找 · 快速选择 TL;DR. Decrease-and-conquer solves a problem by reducing it to one smaller instance, solving that, then extending the answer - unlike divide-and-conquer (Ch 5), which solves several sub-instances. Three flavours, each a different shrink rule: by a constant (insertion sort, peel one element), by a constant factor (binary search, halve => logarithmic), and by a variable size (Lomuto partition => quickselect). The open- book payoff: each is a one-card recipe - technique - steps - cost (state worst / best / expected) -+ hand-trace - trap. 太长不看。减治法通过把问题缩减为一个更小实例、求解之、再扩展答案来解决问题 -- 这不同于分治(Ch 5),后者求解若干子实例。三种口味,各有不同的缩减规则:减常量(插入排序,剥掉一个元素)、减常数因子(二分查找,对半⇒对数级)、减可变量(Lomuto 划分⇒快速选择)。开卷的收益:每个都是一张套路卡 -- 技术→步骤→代价(说清最坏/最好/期望)→手算→ 陷阱。 ★ What the exam asks here 这里考试问什么 (1) Solve C(n)=C([n/2])+1 for binary search and state the closed form [ log_n ]+1 (Q2 true/false-with-justification, Q6-style recurrence). (2) Hand-trace a Lomuto partition - give the array after the pivot lands and the returned split index s. (3) Run quickselect for the k-th smallest and state worst O(n2) vs expected O(n) - the marks are in naming which. (4) State insertion sort's three cases (best/worst/stable/in-place). Every cost answer must name the flavour: worst / best /expected. (1) 为二分查找解 C(n)=C(In/2])+1并陈述闭式 [log2n]+1(Q2 判断题须给理由、Q6式递推)。(2)手算追踪一次 Lomuto partition -- 给出枢轴落定后的数组和返回的分割下标 s。(3)为第 k小跑 quickselect 并陈述 worst O(n2) vs expected O(n) -- 分数在于点出是哪个。(4)陈述 insertion sort 的三种情况(best/worst/stable/in-place)。每个代价答案都要点出种类: worst / best / expected

preorder 给 root，inorder 分左右。[14]Source: asksia-bible-comp90038-bilingual.pdfFresh AskSia tree. Preorder = F . B . A . D . C . E . G . I . H; inorder = A . B . C . D . E . F . G . H . I. Reconstruct, then give the postorder. 新 AskSia 树。前序=F · B · A· D · C · E · G · I· H;中序=A · B· C· D· E · F · G· H· I。重建之,再给出后序。 1 Root = preorder[0] = F. Find F in inorder: it splits into left = A B C D E and right = G H I. 根 = preorder[0]= F。在 inorder 中找 F: 它把序列分为左= A B C D E 和右= G H I。 2 Left subtree - its preorder is the next 5 of the preorder stream (B A D C E). Root = B; in inorder A B C D E, B splits into left A (a leaf) and right C D E. Recurse on the right: root D, with leaf C left and leaf E right. 左子树 -- 其 preorder 是 preorder 流接下来的5 个(B A D C E)。根= B;在 inorder A B C D E 中,B 把它分为左 A(叶子)和右 C D E。对右部递归:根 D,左叶 C、右叶 E。 - 3 Right subtree - preorder G I H; root = G; inorder G H I => nothing left of G, H I right. Recurse: root I, with leaf H as its left child. 右子树 -- preorder G I H;根= G; inorder G H I ⇒ G 左侧无物,H I 在右。递归:根 I,以叶 H 为其左孩子。 4 Read off postorder (L, R, root) bottom-up: left subtree A C E D B, right subtree H I G, then root F. 读出 postorder (L, R, root),自底向上:左子树 A C E D B,右子树 H I G,最后是根 F。 ANSWER postorder = A . C . E . D . B . H . I . G . F ! Preorder gives the ROOT; inorder SPLITS L | R 前序给出根;中序把左 | 右分开 The classic mix-up is swapping the two roles. Preorder[O] is always the next subtree's root; you then locate that root in the inorder list to decide which keys go left and which go right. Off-by-one in the inorder split (or using preorder to split) corrupts the whole subtree. Cross-check: an inorder of a BST must come out sorted. 经典混淆是把两个角色弄反。前序[0]永远是下一棵子树的根;然后你在中序列表里定位那个根,以决定哪些键归左、哪些归右。中序拆分差一位(或用前序去拆分)会毁掉整棵子树。交叉核对:BST 的中序必须排出有序结果。 i §5. 4 closest-pair is NON-examinable (context only) §5. 4 最近点对不可考(仅作背景) Levitin §5. 4 (the 2D closest-pair divide-and-conquer, O(n log n)) is excluded from the examinable scope per the Week-6 reading and the slide note. Know that D&C also solves closest-pair (split by x-median, recurse, merge the strip) - but do not spend exam time rehearsing it; only §5. 1-5. 3 are tested. 按第 6 周阅读和讲义注记,Levitin $5. 4 (二维最近点对分治,O(n log n))不在考查范围。要知道 D&C 也能解最近点对(按 x 中位数划分、递归、合并那条带) -- 但不要在考试时间里排练它;只有 §5. 1-5. 3 被考。 - COMP90038 · 算法与复杂度 · AskSia 双语考试圣经 CH 6 . HEAPS & PQ CHAPTER 6 . HEAPS, HEAPSORT & PRIORITY QUEUES EXAM CORE The complete tree that lives in an array 活在数组里的完全二叉树 PQ ADT . 1-indexed layout . bubble-up / down . heapify O(n) . heapsort PQ ADT · 1 起始下标布局 · 上浮 / 下沉 · heapify O(n) · heapsort TL;DR. A priority queue hands you the most-urgent element on demand. The fast implementation is a binary heap: a complete binary tree stored in a plain array, so a node at index i finds its children at 2i, 2i+1 and its parent at [ i/2] - no pointers. push, pop and update-key are all O(log n) via a single sift; building a heap from a raw array (heapify) is O(n), not O(n log n); and heapsort sorts in O(n log n), in place, but not stably. Read the question for min vs max - the sample exam's heap question is a min-heap. 太长不看。优先队列按需把最紧急的元素递给你。快速实现是二叉堆:一棵完全二叉树存在普通数组里,于是下标 i 的结点在 2i,2i+1 找孩子、在 [i/2]找父亲 -- 无指针。push、pop 和 update-key 都靠一次筛动而为 O(log n);从原始数组建堆(heapify)是 O(n)而非 O(n log n); heapsort 以 O(n log n)原地排序,但不稳定。读题分清 min vs max––样卷的堆题是 min-heap。 ★ What the exam asks here 这里考试问什么

COMP90038

一、先拆考试：你到底在和什么战斗

二、这门课最核心的“得分原则”

1）Q3–Q10 永远写 time 和 space，两者都要

2）一定标清复杂度口径

3）开卷不是救命，是陷阱

三、整门课的知识地图：按“技术家族”来复习

四、最重要的一张总卡：题型 → 技术 的 decoder

五、你必须背熟的基础定义与公式

1）Word-RAM 代价模型

2）渐近记号定义

3）对数规则

4）求和公式

六、递推与 Master Theorem：这是必考硬核

1）分治递推标准形

2）主定理最关键比较

3）三种情形

4）这部分最大陷阱

5）考试作答模板

6）展开法也要会

七、排序与减治 / 分治：你要会什么

1）Insertion sort

2）Binary search

3）Quickselect

4）Mergesort

5）Quicksort

八、树、堆、哈希：Q1 高频手算区

1）AVL tree

2）2-3 tree

3）Heap / Priority Queue

4）Hashing

九、图算法：这是 Q3–Q10 的高产区

1）DFS / BFS / components

2）Topological sort

3）Prim vs Dijkstra

4）Dijkstra

5）Warshall vs Floyd

十、Greedy 与 DP：要会辨认，不要乱套

1）Greedy

2）Dynamic Programming

3）一个特别爱考的陷阱

十一、字符串与范围说明：哪些该学，哪些别浪费时间

十二、Q1 手算题的“必练动作清单”

十三、Q2 判断题怎么拿满

如果是渐近命题

如果是 “always / never” 这类命题

常考判断点

十四、Q3–Q10 设计题答题模板

十五、这门课最常见的失误清单

十六、最后冲刺：你现在最该怎么复习

第 1 轮：把“题型 → 技术”背熟

第 2 轮：狂练 Q1 手算

第 3 轮：背复杂度标签

第 4 轮：练 Q2 justification

第 5 轮：练设计题模板

十七、如果我帮你压缩成“必背清单”，你至少要背这 20 条

十八、你现在最值得优先复习的模块排序

Let's Get in Touch

四、最重要的一张总卡：题型 → 技术的 decoder