Jahziah.
العربية

STUDY GUIDE · GKU 1

Algorithms, computability and complexity study guide (Computer Science)

This unit asks two kinds of question. The first is practical: given a problem, which method solves it, how fast, and with how much memory — answered by counting operations, solving recurrences, timing real runs, and choosing among divide and conquer, greedy rules, dynamic programming, backtracking and heuristics. The second is theoretical: what can a machine compute at all, and what can it compute efficiently — answered by finite automata and grammars, Turing machines and the halting problem, and the classes P and NP. The two halves meet in the last section, where knowing that a problem is NP-complete changes which algorithm you should write. Each section opens with a quick-revision card; worked examples run from easy to exam level, and every trace and number in them was checked by running it.

Continue in the app

Structured by the official ETEC subject standard for this topic: every listed topic and learning outcome, with formulas, figures and worked examples. The full sections are available to members in the app.

SKU 1.1 · Basic analysis and algorithmic methods

  1. Case behaviour, asymptotic notation and growth classes

    Best, worst and average case of one algorithm; the formal definitions of , and ; counting the operations of a loop nest; and what the standard growth classes mean for the largest input a machine can handle.

  2. Recurrences, amortised cost and empirical timing

    The full three-case master theorem with the recursion-tree argument behind it, amortised analysis of a sequence of operations, and how to test a complexity claim by timing a program at doubling input sizes.

  3. Divide and conquer, and the greedy choice

    Splitting a problem into independent parts and combining the answers, with fast exponentiation and inversion counting implemented; and committing to the locally best choice, with the exchange argument that proves when that is safe.

  4. Dynamic programming, backtracking and heuristics

    Filling a table of overlapping subproblems (0/1 knapsack), searching a state space with pruning (n-queens), accepting a good-enough answer when exact search is too slow (nearest-neighbour tour), and deciding which method a problem calls for.

SKU 1.2 · Data structures, automata and computability

  1. Searching, sorting and numerical algorithms

    Implementing partition-based sorting and Euclid's algorithm, the time and memory each principal algorithm needs, the lower bound for comparison sorting, and how to pick a method for a stated situation.

  2. Implementing hash tables and heaps, and choosing a structure

    How a hash table is built — hash function, load factor, chaining or open addressing with linear probing or double hashing, deletion and resizing — how a binary heap lives in an array, and how to pick the structure a problem needs.

  3. Graph algorithms: traversal, ordering, shortest paths and spanning trees

    Breadth-first and depth-first search, topological sorting of a dependency graph, Dijkstra's shortest paths and Prim's minimum spanning tree, all traced on one small network, with their costs and the conditions they need.

  4. String matching: naive, KMP and Rabin–Karp

    Finding every occurrence of a pattern in a text: the brute-force method and its worst case, the Knuth–Morris–Pratt prefix function that never re-reads the text, and Rabin–Karp's rolling hash.

  5. Finite automata, regular languages and grammars

    Designing a deterministic finite automaton for a stated language, turning a nondeterministic one into a DFA, the limits of finite memory (the pumping lemma), and the step up to context-free grammars and the Chomsky hierarchy.

  6. Turing machines, decidability and the halting problem

    The computability part of the unit: what a Turing machine is, the Church–Turing thesis, decidable and undecidable problems, the diagonal proof that no program can decide halting, and why that limits every compiler and analyser.

  7. Computational complexity: P, NP, reductions and NP-completeness

    The classes P and NP defined through certificates, polynomial-time reductions and their direction, NP-complete and NP-hard problems, and what to do in practice when a problem turns out to be NP-hard.

MORE COMPUTER SCIENCE GUIDES

All study guides

Read the full guide beside your practice questions.

Open the app