The course’s core topics supply representations and several algorithms. This optional extension asks how to design another algorithm: what state is needed, which alternatives can be discarded, and what justifies the choice?
Reading route¶
Choose a strategy: distinguish exhaustive search, divide-and-conquer, greedy choice and state reuse.
Greedy design: prove an earliest-finish choice and find counterexamples to plausible alternatives.
Dynamic programming: define subproblems, memoise or tabulate them, and reconstruct a result.
Backtracking: enumerate constrained choices with safe pruning and reversible state.
Sequence patterns: use prefix sums, two pointers and fixed sliding windows.
Complexity and practical limits: relate output size, numeric input magnitude and tractability.
This material extends the syllabus; it does not change the assessment scope of CS2040HS. Read Topics 1–4 first. DAG relaxation and MST exchange reasoning provide additional connections. Topic 16 integrates the graph algorithms in a complete transport-network case.
These are introductions, not a claim to cover every dynamic program, string algorithm or advanced data structure. The coverage review distinguishes implemented material from the remaining roadmap.
A common design route¶
Across six readings, specify the problem/output contract, define sufficient state, justify each commitment or prune, trace the code, then count preprocessing, working state and returned data. Cost claims use the stated numeric/word model, with preprocessing and output counted explicitly. Trace the candidate schedule, subproblem, partial subset or window before comparing strategies. The examples introduce these design patterns; further DP families and complexity theory are listed in the coverage review.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.