← Computer Science syllabus

SingaporeComputer Science

Algorithms and Problem Solving

6 dot points across 6 inquiry questions. Click any dot point for a focused answer with worked past exam questions where available.

How do we measure and compare the efficiency of algorithms independently of the machine they run on?

Analyse the time and space complexity of an algorithm using Big-O notation, and compare common growth rates
A focused answer to the H2 Computing outcome on algorithmic complexity. Big-O notation, deriving the order of growth from loops and recursion, the common complexity classes, and the trade-off between time and space.
9 min answer →

How do simple comparison sorts work, and why are they quadratic?

Implement and trace bubble sort and insertion sort, analyse their complexity, and compare their behaviour on nearly sorted data
A focused answer to the H2 Computing outcome on elementary sorts. Bubble sort and insertion sort, tracing each on an example, their O(n squared) worst case, and why insertion sort excels on nearly sorted input.
9 min answer →

How do we systematically visit every node in a graph, and when do we use breadth-first versus depth-first search?

Implement and trace breadth-first and depth-first traversal of a graph, and contrast the two strategies and their applications
A focused answer to the H2 Computing outcome on graph traversal. Breadth-first search with a queue and depth-first search with a stack or recursion, tracing each on a graph, and choosing between them for shortest paths and exploration.
9 min answer →

How do we find an item in a collection, and why is a sorted list so much faster to search?

Implement and trace linear search and binary search, state their complexities, and justify when each applies
A focused answer to the H2 Computing outcome on searching. Linear search and binary search, tracing each on an example, their O(n) and O(log n) complexities, and the precondition that binary search needs sorted data.
8 min answer →

How do divide-and-conquer sorts achieve O(n log n), and how do merge sort and quicksort differ?

Explain and trace merge sort and quicksort as divide-and-conquer algorithms, analyse their complexity, and compare their trade-offs
A focused answer to the H2 Computing outcome on efficient sorts. Merge sort and quicksort as divide-and-conquer, their O(n log n) behaviour, quicksort's worst case, and the trade-off between stability, memory and speed.
9 min answer →

How does a function that calls itself solve a problem, and when is recursion the right tool?

Define recursion in terms of base and recursive cases, trace recursive calls, and compare recursion with iteration
A focused answer to the H2 Computing outcome on recursion. Base and recursive cases, tracing the call stack, the divide-and-conquer pattern, and the trade-offs between recursion and iteration.
8 min answer →