Jahziah.
العربية

STUDY GUIDE · GKU 1

Algorithms, computability and complexity study guide (Artificial Intelligence)

Every AI system is, underneath, a set of algorithms running on data structures: a search over states, a table of learned values, a queue of nodes to expand, a hash map from words to counts. This unit gives you the tools to judge such code before you run it. The first half is analysis and design: how the cost of an algorithm depends on the input it gets (best, worst and average case), how to state that cost with big O, how the standard growth classes and the classes P and NP separate the feasible from the hopeless, which design method fits which problem, and how to predict running time on bigger inputs. The second half is the toolbox: lists, stacks and queues; searching, sorting and numerical algorithms; hash tables; graph algorithms; and string matching. Each section opens with a quick-revision card, and the worked examples run from easy to exam level.

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 · Algorithms

  1. Case behaviour of an algorithm

    Why one algorithm has a best, a worst and an average running time, how each is computed, and what insertion sort and linear search teach about inputs that are easy or hard.

  2. Big O notation and the complexity of algorithms

    The definitions of , and , the rules that let you read a complexity off code, counting loops, and solving divide-and-conquer recurrences with the master theorem.

  3. Standard complexity classes

    The ladder of growth classes from constant to factorial, the line between polynomial and exponential time, and the classes P, NP, NP-complete and NP-hard — with what they mean for search and planning problems in AI.

  4. Algorithmic methods: greedy, divide and conquer, backtracking, dynamic programming and heuristics

    Five ways to design an algorithm, the property of a problem each one needs, how to choose among them, and each applied by hand to a small problem.

  5. Algorithm performance on inputs of different sizes

    Predicting running time on a larger input from one measurement, finding where a faster-growing algorithm overtakes a slower one, and reading the growth class off a doubling experiment.

SKU 1.2 · Data structures

  1. Lists, stacks and queues and their implementations

    Array lists and linked lists, stacks (last in, first out) and queues (first in, first out), what each operation costs in each implementation, a circular buffer, and a queue built from two stacks.

  2. Numerical, search and sorting algorithms

    Euclid's algorithm and fast modular exponentiation; linear and binary search and the exact number of probes; the main sorting algorithms, their costs and stability, and how to choose one for given data.

  3. Hash tables and their implementation

    How a hash function turns a key into a slot, the two ways to handle collisions (chaining and open addressing), the load factor and the expected cost of a lookup, and problems that become linear with a hash table.

  4. Fundamental graph algorithms

    Representing a graph, breadth-first and depth-first search, Dijkstra's shortest paths, minimum spanning trees, topological order and maximum flow — what each solves, what it costs, and how to pick the right one.

  5. String-matching algorithms

    Finding every occurrence of a pattern in a text: the naive method and its worst case, the Knuth–Morris–Pratt prefix function, and Rabin–Karp hashing with its spurious hits.

MORE ARTIFICIAL INTELLIGENCE GUIDES

All study guides

Read the full guide beside your practice questions.

Open the app