Concept map · the backbone
Every concept, with its prerequisites
Each concept has a unique ID and is mapped to the official syllabus lines it covers. Prerequisites define the learning order and the knowledge graph. Review this before any subject is written.
Concepts mapped
304
Tier 1 (full depth)
256
Tier 2 (lighter)
48
Pages written
232
Programming and Data Structures
33 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Data types, operators and expressions pds.c-types-operators | T1 | Programming in C | none |
| 2 | Control flow and loops pds.c-control-flow | T2 | Programming in C | Data types, operators and expressions |
| 3 | C memory layout: text, data, heap, stack pds.c-memory-layout | T1 | Programming in C | Data types, operators and expressions |
| 4 | Functions and parameter passing pds.functions-parameter-passing | T1 | Programming in C | Control flow and loops |
| 5 | Scope, lifetime and storage classes pds.scope-storage-classes | T1 | Programming in C | Functions and parameter passing |
| 6 | Evaluation order, sequence points and undefined behaviour pds.undefined-behaviour-sequence-points | T1 | Programming in C | Data types, operators and expressions |
| 7 | Bitwise operations pds.bitwise-operations | T2 | Programming in C | Data types, operators and expressions |
| 8 | Preprocessor and macros pds.preprocessor-macros | T2 | Programming in C | Data types, operators and expressions |
| 9 | Arrays and indexing pds.arrays | T1 | Arrays | Data types, operators and expressions |
| 10 | Pointers and pointer arithmetic pds.pointers | T1 | Programming in C | C memory layout: text, data, heap, stack, Arrays and indexing |
| 11 | Arrays, strings and pointers together pds.pointers-arrays-strings | T1 | Arrays; Programming in C | Pointers and pointer arithmetic |
| 12 | Multidimensional arrays and address calculation pds.array-2d-address-calculation | T1 | Arrays | Arrays and indexing |
| 13 | Dynamic memory: malloc, free and leaks pds.dynamic-memory | T1 | Programming in C | Pointers and pointer arithmetic |
| 14 | Structures, unions and memory alignment pds.structs-unions | T2 | Programming in C | Pointers and pointer arithmetic |
| 15 | Function pointers pds.function-pointers | T2 | Programming in C | Pointers and pointer arithmetic, Functions and parameter passing |
| 16 | Recursion and the call stack pds.recursion-call-stack | T1 | Recursion | Functions and parameter passing, C memory layout: text, data, heap, stack |
| 17 | Recursion patterns: tracing and output questions pds.recursion-patterns | T1 | Recursion | Recursion and the call stack |
| 18 | Stack (ADT) and its implementations pds.stack-adt | T1 | Stacks | Arrays and indexing, Pointers and pointer arithmetic |
| 19 | Stack applications: expression evaluation and matching pds.stack-applications | T1 | Stacks | Stack (abstract data type) |
| 20 | Queue, circular queue and deque pds.queue-adt | T1 | Queues | Arrays and indexing |
| 21 | Queue applications and queue using stacks pds.queue-applications | T2 | Queues | Queue (abstract data type), Stack (abstract data type) |
| 22 | Singly linked lists pds.linked-list-singly | T1 | Linked lists | Pointers and pointer arithmetic, Dynamic memory: malloc, free and leaks |
| 23 | Doubly and circular linked lists pds.linked-list-variants | T2 | Linked lists | Singly linked lists |
| 24 | Reversal, cycle detection and merging pds.linked-list-operations | T1 | Linked lists | Singly linked lists |
| 25 | Trees: terminology and properties pds.trees-basics | T1 | Trees | Singly linked lists |
| 26 | Binary tree traversals pds.binary-tree-traversals | T1 | Trees | Trees and binary trees, Stack (abstract data type), Recursion and the call stack |
| 27 | Constructing trees from traversals pds.tree-construction-from-traversals | T1 | Trees | Binary tree traversals |
| 28 | Counting binary trees and tree properties pds.binary-tree-counting | T1 | Trees | Trees and binary trees, Counting: permutations and combinations |
| 29 | Binary search trees pds.bst | T1 | Binary search trees | Binary tree traversals |
| 30 | AVL trees and rotations pds.avl-trees | T2 | Binary search trees | Binary search trees |
| 31 | Binary heaps and heap operations pds.binary-heap | T1 | Binary heaps | Trees and binary trees, Arrays and indexing |
| 32 | Priority queues and building a heap pds.heap-applications | T1 | Binary heaps | Binary heaps and heap operations |
| 33 | Graph representations pds.graph-representations | T1 | Graphs | Arrays and indexing, Singly linked lists |
Digital Logic
23 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Number systems and conversion dl.number-systems-conversion | T1 | Number representation and arithmetic: fixed point | none |
| 2 | Sign-magnitude, 1's and 2's complement dl.signed-number-representation | T1 | Number representation and arithmetic: fixed point | Number systems and conversion |
| 3 | Fixed-point arithmetic and overflow dl.fixed-point-arithmetic | T1 | Number representation and arithmetic: fixed point | Sign-magnitude, 1's and 2's complement |
| 4 | BCD, Gray and parity codes dl.codes | T2 | Number representation and arithmetic: fixed point | Number systems and conversion |
| 5 | IEEE 754 floating point dl.ieee754 | T1 | Number representation and arithmetic: floating point | Sign-magnitude, 1's and 2's complement |
| 6 | Floating-point arithmetic and precision dl.floating-point-arithmetic | T2 | Number representation and arithmetic: floating point | IEEE 754 floating point |
| 7 | Boolean algebra and identities dl.boolean-algebra | T1 | Boolean algebra and minimization: algebraic technique | none |
| 8 | SOP, POS, minterms and maxterms dl.boolean-functions-forms | T1 | Boolean algebra and minimization: algebraic technique | Boolean algebra and identities |
| 9 | Functional completeness and duality dl.functional-completeness-duality | T2 | Boolean algebra and minimization: algebraic technique | Boolean algebra and identities |
| 10 | Logic gates and universal gates dl.logic-gates-universal | T1 | Design of combinational circuits | Boolean algebra and identities |
| 11 | Karnaugh maps dl.kmap | T1 | Boolean algebra and minimization: Karnaugh map | SOP, POS, minterms and maxterms |
| 12 | Tabular method (Quine-McCluskey) dl.quine-mccluskey | T2 | Boolean algebra and minimization: tabular method | Karnaugh maps |
| 13 | Design of combinational circuits dl.combinational-design | T1 | Design of combinational circuits | Karnaugh maps, Logic gates and universal gates |
| 14 | Adders and subtractors dl.adders-subtractors | T1 | Design of combinational circuits | Design of combinational circuits |
| 15 | Multiplexers and demultiplexers dl.mux-demux | T1 | Design of combinational circuits | Design of combinational circuits |
| 16 | Decoders, encoders and comparators dl.decoders-encoders | T1 | Design of combinational circuits | Design of combinational circuits |
| 17 | ROM, PLA and PAL dl.rom-pla | T2 | Design of combinational circuits | Decoders, encoders and comparators |
| 18 | Static and dynamic hazards in logic dl.logic-hazards | T2 | Design of combinational circuits | Karnaugh maps |
| 19 | Latches and flip-flops dl.latches-flipflops | T1 | Design of sequential circuits | Logic gates and universal gates |
| 20 | Excitation tables and flip-flop conversion dl.flipflop-conversion | T1 | Design of sequential circuits | Latches and flip-flops |
| 21 | Registers and shift registers dl.registers-shift | T1 | Design of sequential circuits | Latches and flip-flops |
| 22 | Synchronous and asynchronous counters dl.counters | T1 | Design of sequential circuits | Excitation tables and flip-flop conversion |
| 23 | FSM design: Mealy and Moore dl.state-machines | T1 | Design of sequential circuits | Excitation tables and flip-flop conversion |
Computer Organization and Architecture
27 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Instruction cycle coa.instruction-cycle | T1 | Instruction set | Registers and shift registers |
| 2 | Instruction set architecture and formats coa.isa-design | T1 | Instruction set | Instruction cycle |
| 3 | Instruction formats and expanding opcodes coa.instruction-formats-opcodes | T1 | Instruction set | Instruction set architecture and formats |
| 4 | Addressing modes coa.addressing-modes | T1 | Addressing modes | Instruction set architecture and formats |
| 5 | RISC versus CISC coa.risc-cisc | T2 | Instruction set | Instruction set architecture and formats |
| 6 | Procedure calls and stack frames in hardware coa.stack-frames-calls | T1 | Instruction set | Addressing modes, Recursion and the call stack |
| 7 | ALU design coa.alu-design | T1 | Design of arithmetic and logic unit (ALU) | Adders and subtractors |
| 8 | Multiplication: shift-add and Booth coa.multiplication-booth | T1 | Design of arithmetic and logic unit (ALU) | ALU design, Fixed-point arithmetic and overflow |
| 9 | Division algorithms coa.division-algorithms | T2 | Design of arithmetic and logic unit (ALU) | ALU design |
| 10 | Single-bus datapath and register transfer coa.datapath | T1 | Design of control unit: hardwired | Registers and shift registers, ALU design |
| 11 | Hardwired control unit coa.control-hardwired | T1 | Design of control unit: hardwired | Single-bus datapath and register transfer, FSM design: Mealy and Moore |
| 12 | Microprogrammed control unit coa.control-microprogrammed | T1 | Design of control unit: microprogrammed | Single-bus datapath and register transfer |
| 13 | Memory hierarchy and performance (AMAT) coa.memory-hierarchy | T1 | Memory hierarchy: performance | none |
| 14 | Memory interfacing and address decoding coa.memory-interfacing | T1 | Memory interfacing | Decoders, encoders and comparators |
| 15 | RAM, ROM and DRAM refresh basics coa.ram-rom-technology | T2 | Memory interfacing | Memory hierarchy and performance (AMAT) |
| 16 | Cache memory mapping coa.cache-mapping | T1 | Cache memory mapping | Memory hierarchy and performance (AMAT) |
| 17 | Cache replacement and write policies coa.cache-replacement-write | T1 | Cache memory mapping | Cache memory mapping |
| 18 | Cache performance and multilevel caches coa.cache-performance | T1 | Memory hierarchy: performance | Cache memory mapping |
| 19 | Disk structure and access time coa.secondary-storage-disk | T2 | Memory hierarchy: performance | Memory hierarchy and performance (AMAT) |
| 20 | I/O interface and programmed I/O coa.io-interface | T1 | I/O interface: interrupt | none |
| 21 | Interrupts and vectoring coa.interrupts | T1 | I/O interface: interrupt | I/O interface and programmed I/O |
| 22 | Direct memory access coa.dma | T1 | I/O interface: DMA | I/O interface and programmed I/O |
| 23 | Instruction pipelining coa.pipelining | T1 | Instruction pipelining | Instruction cycle |
| 24 | Pipeline speedup and CPI calculations coa.pipeline-performance | T1 | Instruction pipelining | Instruction pipelining |
| 25 | Structural, data and control hazards coa.pipeline-hazards | T1 | Pipeline hazards | Instruction pipelining |
| 26 | Forwarding, stalls and branch prediction coa.pipeline-forwarding-branch | T1 | Pipeline hazards | Structural, data and control hazards |
| 27 | Performance: CPI, MIPS and Amdahl's law coa.amdahl-performance | T1 | Instruction pipelining | Instruction pipelining |
Operating Systems
32 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | System calls and kernel mode os.system-calls | T1 | System calls | Interrupts and vectoring |
| 2 | Process model and PCB os.process-model | T1 | Processes | System calls and kernel mode |
| 3 | Process states, fork and exec os.process-states-creation | T1 | Processes | Process model and PCB |
| 4 | Context switching os.context-switch | T1 | Processes | Process model and PCB |
| 5 | Threads and multithreading models os.threads | T1 | Threads | Process model and PCB |
| 6 | Inter-process communication os.ipc | T2 | Inter-process communication | Process model and PCB |
| 7 | Critical section and race conditions os.critical-section | T1 | Concurrency and synchronization | Process model and PCB |
| 8 | Peterson, Dekker and software solutions os.sync-software-solutions | T1 | Concurrency and synchronization | Critical section and race conditions |
| 9 | Test-and-set, swap and atomic instructions os.sync-hardware | T2 | Concurrency and synchronization | Critical section and race conditions |
| 10 | Semaphores os.semaphores | T1 | Concurrency and synchronization | Critical section and race conditions |
| 11 | Producer-consumer, readers-writers, dining philosophers os.classic-sync-problems | T1 | Concurrency and synchronization | Semaphores |
| 12 | Monitors and condition variables os.monitors | T2 | Concurrency and synchronization | Semaphores |
| 13 | Deadlock: conditions and resource allocation graphs os.deadlock-conditions | T1 | Deadlock | Process model and PCB |
| 14 | Deadlock avoidance and the Banker's algorithm os.deadlock-avoidance-bankers | T1 | Deadlock | Deadlock: conditions and resource allocation graphs |
| 15 | Deadlock detection and recovery os.deadlock-detection-recovery | T2 | Deadlock | Deadlock: conditions and resource allocation graphs |
| 16 | CPU scheduling: criteria, FCFS, SJF and SRTF os.cpu-scheduling | T1 | CPU scheduling | Process states, fork and exec |
| 17 | Priority and round robin scheduling os.scheduling-priority-rr | T1 | CPU scheduling | CPU scheduling: criteria, FCFS, SJF and SRTF |
| 18 | Multilevel queues and real-time scheduling os.scheduling-multilevel-realtime | T2 | CPU scheduling | Priority and round robin scheduling |
| 19 | Disk scheduling os.disk-scheduling | T1 | I/O scheduling | Disk structure and access time |
| 20 | I/O subsystem, buffering and spooling os.io-systems | T2 | I/O scheduling | Direct memory access |
| 21 | Memory management: partitioning and fragmentation os.memory-management-basics | T1 | Memory management | none |
| 22 | Process address space os.process-address-space | T1 | Memory management | C memory layout: text, data, heap, stack, Memory management: partitioning and fragmentation |
| 23 | Paging and address translation os.paging | T1 | Memory management | Memory management: partitioning and fragmentation |
| 24 | Segmentation and segmented paging os.segmentation | T1 | Memory management | Paging and address translation |
| 25 | Multilevel, inverted and hashed page tables os.page-table-structures | T1 | Virtual memory | Paging and address translation |
| 26 | Virtual memory and demand paging os.virtual-memory-paging | T1 | Virtual memory | Paging and address translation |
| 27 | TLB and effective access time os.tlb-effective-access | T1 | Virtual memory | Paging and address translation, Memory hierarchy and performance (AMAT) |
| 28 | Page replacement algorithms os.page-replacement | T1 | Virtual memory | Virtual memory and demand paging |
| 29 | Thrashing and the working set os.thrashing-working-set | T1 | Virtual memory | Page replacement algorithms |
| 30 | File systems: concepts and directories os.file-systems | T1 | File systems | none |
| 31 | File allocation methods and inodes os.file-allocation | T1 | File systems | File systems: concepts and directories |
| 32 | Free-space management and file system performance os.free-space-fs-performance | T2 | File systems | File allocation methods and inodes |
Compiler Design
29 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Phases of a compiler cd.compiler-phases | T1 | Lexical analysis | none |
| 2 | Lexical analysis cd.lexical-analysis | T1 | Lexical analysis | Phases of a compiler, Regular expressions |
| 3 | Ambiguity, left recursion and left factoring cd.grammar-ambiguity-transformations | T1 | Parsing | Context-free grammars and derivations |
| 4 | FIRST and FOLLOW sets cd.first-follow | T1 | Parsing | Ambiguity, left recursion and left factoring |
| 5 | Top-down parsing and LL(1) cd.parsing-ll1 | T1 | Parsing | FIRST and FOLLOW sets |
| 6 | Recursive descent and predictive parsing cd.parsing-recursive-descent | T2 | Parsing | Top-down parsing and LL(1) |
| 7 | Shift-reduce parsing and handles cd.parsing-shift-reduce | T1 | Parsing | Ambiguity, left recursion and left factoring |
| 8 | Bottom-up parsing and LR cd.parsing-lr | T1 | Parsing | Shift-reduce parsing and handles |
| 9 | LR(0) and SLR(1) construction cd.parsing-lr0-slr | T1 | Parsing | Bottom-up parsing and LR, FIRST and FOLLOW sets |
| 10 | CLR(1) and LALR(1) cd.parsing-clr-lalr | T1 | Parsing | LR(0) and SLR(1) construction |
| 11 | Operator precedence parsing cd.parsing-operator-precedence | T2 | Parsing | Shift-reduce parsing and handles |
| 12 | Parser power hierarchy and conflicts cd.parser-comparison | T1 | Parsing | CLR(1) and LALR(1), Top-down parsing and LL(1) |
| 13 | Syntax-directed definitions: synthesized and inherited cd.sdt-attributes | T1 | Syntax-directed translation | Bottom-up parsing and LR |
| 14 | S-attributed, L-attributed and evaluation orders cd.sdt-evaluation-orders | T1 | Syntax-directed translation | Syntax-directed definitions: synthesized and inherited attributes |
| 15 | Translation schemes and semantic actions cd.sdt-translation-schemes | T1 | Syntax-directed translation | S-attributed, L-attributed and evaluation orders |
| 16 | Runtime environments and activation records cd.runtime-activation-records | T1 | Runtime environments | Recursion and the call stack |
| 17 | Storage organisation: static, stack and heap cd.runtime-storage-organisation | T2 | Runtime environments | Runtime environments and activation records |
| 18 | Parameter passing modes and access links cd.runtime-parameter-passing | T1 | Runtime environments | Runtime environments and activation records |
| 19 | Intermediate code generation cd.intermediate-code | T1 | Intermediate code generation | Translation schemes and semantic actions |
| 20 | Three-address code, quadruples and triples cd.three-address-code | T1 | Intermediate code generation | Intermediate code generation |
| 21 | Translating expressions and control flow, backpatching cd.control-flow-translation | T1 | Intermediate code generation | Three-address code, quadruples and triples |
| 22 | Basic blocks and control flow graphs cd.basic-blocks-cfg | T1 | Local optimisation | Three-address code, quadruples and triples |
| 23 | Local optimisation cd.local-optimisation | T1 | Local optimisation | Basic blocks and control flow graphs |
| 24 | DAG representation of basic blocks cd.dag-basic-block | T1 | Local optimisation | Basic blocks and control flow graphs |
| 25 | Data flow analysis framework cd.dataflow-framework | T1 | Data flow analyses: constant propagation | Basic blocks and control flow graphs |
| 26 | Reaching definitions and constant propagation cd.dataflow-reaching-constprop | T1 | Data flow analyses: constant propagation | Data flow analysis framework |
| 27 | Liveness analysis cd.dataflow-liveness | T1 | Data flow analyses: liveness analysis | Data flow analysis framework |
| 28 | Available expressions and common sub-expression elimination cd.dataflow-available-cse | T1 | Data flow analyses: common sub expression elimination | Data flow analysis framework |
| 29 | Code generation and register allocation (outside syllabus, used in the journey) cd.code-generation-registers | T2 | outside syllabus | Basic blocks and control flow graphs, Addressing modes |
Algorithms
30 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Asymptotic notation algo.asymptotic-notation | T1 | Asymptotic worst case time and space complexity | none |
| 2 | Analysing loops, time and space algo.algorithm-analysis | T1 | Asymptotic worst case time and space complexity | Asymptotic notation |
| 3 | Solving recurrences: substitution, tree and Master theorem algo.recurrence-solving | T1 | Asymptotic worst case time and space complexity | Asymptotic notation, Recurrence relations |
| 4 | Amortized analysis algo.amortized-analysis | T2 | Asymptotic worst case time and space complexity | Analysing loops, time and space |
| 5 | Linear and binary search algo.searching-linear-binary | T1 | Searching | Analysing loops, time and space, Arrays and indexing |
| 6 | Bubble, selection and insertion sort algo.sorting-elementary | T1 | Sorting | Analysing loops, time and space |
| 7 | Divide and conquer algo.divide-and-conquer | T1 | Algorithm design technique: divide-and-conquer | Solving recurrences: substitution, tree and Master theorem, Recursion and the call stack |
| 8 | Divide and conquer applications algo.dc-applications | T1 | Algorithm design technique: divide-and-conquer | Divide and conquer |
| 9 | Merge sort algo.sorting-merge | T1 | Sorting | Divide and conquer |
| 10 | Quicksort algo.sorting-quick | T1 | Sorting | Divide and conquer |
| 11 | Heap sort algo.sorting-heap | T1 | Sorting | Priority queues and building a heap |
| 12 | Lower bound and linear-time sorts algo.sorting-lower-bound-linear | T1 | Sorting | Merge sort, Quicksort |
| 13 | Stability, in-place and comparison of sorts algo.sorting-properties | T1 | Sorting | Bubble, selection and insertion sort |
| 14 | Hashing: functions and collisions algo.hashing-basics | T1 | Hashing | Arrays and indexing |
| 15 | Chaining and open addressing algo.hashing-chaining-open | T1 | Hashing | Hashing: functions and collisions |
| 16 | Load factor and expected probes algo.hashing-analysis | T1 | Hashing | Chaining and open addressing, Random variables, expectation and variance |
| 17 | Greedy method and exchange argument algo.greedy-method | T1 | Algorithm design technique: greedy | Analysing loops, time and space |
| 18 | Activity selection and fractional knapsack algo.greedy-scheduling-knapsack | T1 | Algorithm design technique: greedy | Greedy method and exchange argument |
| 19 | Huffman coding algo.huffman-coding | T1 | Algorithm design technique: greedy | Greedy method and exchange argument, Binary heaps and heap operations |
| 20 | Dynamic programming and memoization algo.dp-memoization | T1 | Algorithm design technique: dynamic programming | Recursion and the call stack, Solving recurrences: substitution, tree and Master theorem |
| 21 | LCS, edit distance, knapsack and matrix chain algo.dp-classic-problems | T1 | Algorithm design technique: dynamic programming | Dynamic programming and memoization |
| 22 | DP on sequences: LIS and coin change algo.dp-sequences | T1 | Algorithm design technique: dynamic programming | Dynamic programming and memoization |
| 23 | BFS and DFS algo.graph-traversals-bfs-dfs | T1 | Graph traversals | Graph representations, Queue (abstract data type) |
| 24 | DFS edge types, topological sort and SCC algo.dfs-classification | T1 | Graph traversals | BFS and DFS |
| 25 | Spanning trees and the cut property algo.mst-basics | T1 | Minimum spanning trees | Greedy method and exchange argument, BFS and DFS |
| 26 | Kruskal and Prim algo.mst-kruskal-prim | T1 | Minimum spanning trees | Spanning trees and the cut property |
| 27 | Dijkstra's algorithm algo.sssp-dijkstra | T1 | Shortest paths | BFS and DFS, Binary heaps and heap operations |
| 28 | Bellman-Ford algo.sssp-bellman-ford | T1 | Shortest paths | Dijkstra's algorithm |
| 29 | Floyd-Warshall algo.all-pairs-floyd | T1 | Shortest paths | Dynamic programming and memoization |
| 30 | P, NP and NP-completeness (outside syllabus, appeared in earlier papers) algo.complexity-classes-np | T2 | outside syllabus | Analysing loops, time and space |
Theory of Computation
29 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Alphabets, strings and languages toc.alphabets-strings-languages | T1 | Finite automata | none |
| 2 | Deterministic finite automata toc.dfa | T1 | Finite automata | Alphabets, strings and languages |
| 3 | DFA design patterns and counting states toc.dfa-design-patterns | T1 | Finite automata | Deterministic finite automata |
| 4 | NFA and epsilon-NFA toc.nfa | T1 | Finite automata | Deterministic finite automata |
| 5 | Subset construction toc.nfa-dfa-conversion | T1 | Finite automata | NFA and epsilon-NFA |
| 6 | DFA minimisation toc.dfa-minimisation | T1 | Finite automata | Subset construction |
| 7 | Mealy and Moore machines toc.finite-state-transducers | T2 | Finite automata | Deterministic finite automata |
| 8 | Regular expressions toc.regular-expressions | T1 | Regular expressions | NFA and epsilon-NFA |
| 9 | Regex to automata and back toc.regex-fa-conversion | T1 | Regular expressions | Regular expressions, Subset construction |
| 10 | Closure properties of regular languages toc.regular-closure-properties | T1 | Regular languages | DFA minimisation |
| 11 | Pumping lemma for regular languages toc.pumping-lemma-regular | T1 | Pumping lemma | Closure properties of regular languages |
| 12 | Myhill-Nerode theorem toc.myhill-nerode | T2 | Regular languages | DFA minimisation |
| 13 | Decision problems for regular languages toc.regular-decision-problems | T2 | Regular languages | Closure properties of regular languages |
| 14 | Context-free grammars and derivations toc.context-free-grammars | T1 | Context-free grammars | Alphabets, strings and languages |
| 15 | Ambiguity in grammars toc.cfg-ambiguity | T1 | Context-free grammars | Context-free grammars and derivations |
| 16 | Simplification, CNF and GNF toc.cfg-normal-forms | T1 | Context-free grammars | Context-free grammars and derivations |
| 17 | Pushdown automata toc.pda | T1 | Push-down automata | NFA and epsilon-NFA, Stack (abstract data type) |
| 18 | PDA and CFG equivalence toc.pda-cfg-equivalence | T1 | Push-down automata | Pushdown automata, Context-free grammars and derivations |
| 19 | Deterministic versus nondeterministic PDA toc.dpda-vs-npda | T1 | Push-down automata | Pushdown automata |
| 20 | Closure properties of CFLs toc.cf-closure-properties | T1 | Context-free languages | PDA and CFG equivalence |
| 21 | Pumping lemma for CFLs toc.pumping-lemma-cfl | T1 | Pumping lemma | Closure properties of CFLs |
| 22 | Decision problems for CFLs toc.cfl-decision-problems | T2 | Context-free languages | Closure properties of CFLs |
| 23 | Chomsky hierarchy toc.chomsky-hierarchy | T1 | Context-free languages | Closure properties of CFLs, Closure properties of regular languages |
| 24 | Turing machines toc.turing-machines | T1 | Turing machines | Pushdown automata |
| 25 | TM variants and the Church-Turing thesis toc.tm-variants-church | T1 | Turing machines | Turing machines |
| 26 | Linear bounded automata and context-sensitive languages toc.lba-context-sensitive | T2 | Turing machines | Turing machines, Chomsky hierarchy |
| 27 | Decidable and recognisable languages toc.decidable-recognisable | T1 | Undecidability | TM variants and the Church-Turing thesis |
| 28 | Halting problem and reductions toc.undecidability-halting | T1 | Undecidability | Decidable and recognisable languages |
| 29 | Rice's theorem toc.rice-theorem | T1 | Undecidability | Halting problem and reductions |
Databases
28 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | ER model dbms.er-model | T1 | ER-model | none |
| 2 | ER to relational mapping dbms.er-to-relational | T1 | ER-model | ER model, Relational model and keys |
| 3 | Relational model and keys dbms.relational-model-keys | T1 | Integrity constraints | Relations and their properties |
| 4 | Relational algebra dbms.relational-algebra | T1 | Relational model: relational algebra | Relational model and keys, Sets and set identities |
| 5 | Joins, division and expression trees dbms.relational-algebra-advanced | T1 | Relational model: relational algebra | Relational algebra |
| 6 | Tuple relational calculus dbms.tuple-relational-calculus | T1 | Relational model: tuple calculus | Relational algebra, First order logic |
| 7 | Safe expressions and domain calculus dbms.domain-calculus-safety | T2 | Relational model: tuple calculus | Tuple relational calculus |
| 8 | SQL: DDL and basic queries dbms.sql-basics | T1 | Relational model: SQL | Relational algebra |
| 9 | Joins, grouping and aggregates dbms.sql-joins-aggregates | T1 | Relational model: SQL | SQL: DDL and basic queries |
| 10 | Nested queries, views and NULL dbms.sql-nested-views | T1 | Relational model: SQL | Joins, grouping and aggregates |
| 11 | Integrity constraints and triggers dbms.sql-constraints-triggers | T1 | Integrity constraints | SQL: DDL and basic queries |
| 12 | Functional dependencies and closure dbms.functional-dependencies | T1 | Normal forms | Relational model and keys |
| 13 | Finding candidate keys dbms.candidate-keys | T1 | Normal forms | Functional dependencies and closure |
| 14 | 1NF to BCNF dbms.normal-forms | T1 | Normal forms | Finding candidate keys |
| 15 | Lossless join and dependency preservation dbms.decomposition-lossless-dp | T1 | Normal forms | 1NF to BCNF |
| 16 | Canonical cover and 3NF synthesis dbms.canonical-cover-3nf-synthesis | T2 | Normal forms | Lossless join and dependency preservation |
| 17 | Multivalued dependencies and 4NF dbms.multivalued-4nf | T2 | Normal forms | 1NF to BCNF |
| 18 | File organisation and blocking factor dbms.file-organisation | T1 | File organization | Disk structure and access time |
| 19 | Ordered, primary, clustering and secondary indexes dbms.indexing-ordered | T1 | Indexing (e.g., B and B+ trees) | File organisation and blocking factor |
| 20 | B trees dbms.b-tree | T1 | Indexing (e.g., B and B+ trees) | Ordered, primary, clustering and secondary indexes, Binary search trees |
| 21 | B+ trees dbms.b-plus-tree | T1 | Indexing (e.g., B and B+ trees) | B trees |
| 22 | Hash-based file organisation dbms.hash-file-organisation | T2 | Indexing (e.g., B and B+ trees) | File organisation and blocking factor, Hashing: functions and collisions |
| 23 | Transactions and ACID dbms.txn-acid | T1 | Transactions | none |
| 24 | Log-based recovery and checkpoints dbms.recovery-logging | T2 | Transactions | Transactions and ACID |
| 25 | Schedules, conflict and view serializability dbms.schedules-serializability | T1 | Concurrency control | Transactions and ACID |
| 26 | Recoverable, cascadeless and strict schedules dbms.recoverability | T1 | Concurrency control | Schedules, conflict and view serializability |
| 27 | Two-phase locking and its variants dbms.two-phase-locking | T1 | Concurrency control | Schedules, conflict and view serializability, Deadlock: conditions and resource allocation graphs |
| 28 | Timestamp ordering dbms.timestamp-ordering | T2 | Concurrency control | Schedules, conflict and view serializability |
Computer Networks
25 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Layering: OSI and TCP/IP cn.layering-osi-tcpip | T1 | Principles of layering | none |
| 2 | Circuit, packet and virtual-circuit switching cn.switching-types | T1 | Basics of switching (circuit, packet and virtual circuit) | Layering: OSI and TCP/IP |
| 3 | Delay, throughput and bandwidth-delay product cn.performance-metrics | T1 | Performance metrics | Circuit, packet and virtual-circuit switching |
| 4 | Error detection: parity, checksum and CRC cn.error-detection-crc | T1 | Data link layer: error detection | Layering: OSI and TCP/IP |
| 5 | Hamming code (error correction, extra) cn.error-correction-hamming | T2 | outside syllabus | Error detection: parity, checksum and CRC |
| 6 | Medium access: ALOHA, CSMA and CSMA/CD cn.mac-protocols | T1 | Data link layer: Medium Access Control | Delay, throughput and bandwidth-delay product |
| 7 | Ethernet, frames and minimum frame size cn.ethernet | T1 | Data link layer: Ethernet | Medium access: ALOHA, CSMA and CSMA/CD |
| 8 | Switches, learning bridges and VLANs cn.switches-bridges-vlan | T2 | Data link layer: Ethernet | Ethernet, frames and minimum frame size |
| 9 | IPv4 addressing and classful addressing cn.ipv4-addressing | T1 | IPv4: CIDR notation | Layering: OSI and TCP/IP |
| 10 | CIDR and subnetting cn.cidr-subnetting | T1 | IPv4: CIDR notation | IPv4 addressing and classful addressing |
| 11 | IPv4 header and fragmentation cn.ipv4-fragmentation | T1 | IPv4: fragmentation | IPv4 addressing and classful addressing |
| 12 | Network address translation cn.nat | T1 | IPv4: Network Address Translation | IPv4 addressing and classful addressing |
| 13 | ICMP, ARP and DHCP (supporting) cn.icmp-arp-dhcp | T2 | outside syllabus | IPv4 addressing and classful addressing |
| 14 | Distance vector routing cn.routing-distance-vector | T1 | Distance vector routing | CIDR and subnetting |
| 15 | Link state routing cn.routing-link-state | T1 | Link state routing | CIDR and subnetting, Dijkstra's algorithm |
| 16 | RIP, OSPF and BGP overview cn.routing-protocols-overview | T2 | Link state routing | Distance vector routing, Link state routing |
| 17 | TCP: segments, handshake and teardown cn.tcp-basics | T1 | TCP: flow control | IPv4 header and fragmentation |
| 18 | Sliding window: stop-and-wait, Go-Back-N, Selective Repeat cn.sliding-window-protocols | T1 | TCP: flow control | Delay, throughput and bandwidth-delay product |
| 19 | TCP flow control cn.tcp-flow-control | T1 | TCP: flow control | TCP: segments, handshake and teardown, Sliding window: stop-and-wait, Go-Back-N, Selective Repeat |
| 20 | TCP congestion control cn.tcp-congestion-control | T1 | TCP: congestion control | TCP flow control |
| 21 | RTT estimation and retransmission timers cn.tcp-rtt-timers | T2 | TCP: congestion control | TCP: segments, handshake and teardown |
| 22 | UDP and ports cn.udp-ports | T2 | Socket API | TCP: segments, handshake and teardown |
| 23 | Socket API cn.socket-api | T1 | Socket API | TCP: segments, handshake and teardown, System calls and kernel mode |
| 24 | DNS cn.dns | T1 | DNS | UDP and ports |
| 25 | HTTP cn.http | T1 | HTTP | Socket API, DNS |
Engineering Mathematics
34 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Propositional logic math.logic-propositional | T1 | Propositional logic | none |
| 2 | First order logic math.logic-first-order | T1 | First order logic | Propositional logic |
| 3 | Sets and set identities math.sets-operations | T1 | Sets | none |
| 4 | Relations and their properties math.relations | T1 | Relations | Sets and set identities |
| 5 | Equivalence relations and partitions math.equivalence-relations | T1 | Relations | Relations and their properties |
| 6 | Functions: injective, surjective, bijective math.functions | T1 | Functions | Relations and their properties |
| 7 | Partial orders, Hasse diagrams and lattices math.posets-lattices | T1 | Partial orders and lattices | Relations and their properties |
| 8 | Semigroups, monoids and groups math.algebraic-structures | T1 | Monoids; Groups | Functions: injective, surjective, bijective |
| 9 | Subgroups, cyclic groups and Lagrange's theorem math.group-theory-subgroups | T1 | Groups | Semigroups, monoids and groups |
| 10 | Graph connectivity and trees math.graph-connectivity | T1 | Graphs: connectivity | Sets and set identities |
| 11 | Euler and Hamiltonian paths math.graph-euler-hamilton | T1 | Graphs: connectivity | Graph connectivity and trees |
| 12 | Matching math.graph-matching | T1 | Graphs: matching | Graph connectivity and trees |
| 13 | Graph colouring math.graph-colouring | T1 | Graphs: colouring | Graph connectivity and trees |
| 14 | Planar graphs and degree sequences math.graph-planarity | T1 | Graphs: connectivity | Graph connectivity and trees |
| 15 | Counting: permutations and combinations math.counting-principles | T1 | Combinatorics: counting | Sets and set identities |
| 16 | Pigeonhole and inclusion-exclusion math.counting-inclusion-exclusion | T1 | Combinatorics: counting | Counting: permutations and combinations |
| 17 | Recurrence relations math.recurrence-relations | T1 | Combinatorics: recurrence relations | Counting: permutations and combinations |
| 18 | Generating functions math.generating-functions | T1 | Combinatorics: generating functions | Recurrence relations |
| 19 | Matrices and operations math.matrices-basics | T1 | Matrices | none |
| 20 | Determinants math.determinants | T1 | Determinants | Matrices and operations |
| 21 | Systems of linear equations and rank math.linear-systems | T1 | System of linear equations | Determinants |
| 22 | Eigenvalues and eigenvectors math.eigen | T1 | Eigenvalues and eigenvectors | Determinants |
| 23 | LU decomposition math.lu-decomposition | T1 | LU decomposition | Systems of linear equations and rank |
| 24 | Limits math.limits | T1 | Limits | none |
| 25 | Continuity and differentiability math.continuity-differentiability | T1 | Continuity and differentiability | Limits |
| 26 | Maxima and minima math.maxima-minima | T1 | Maxima and minima | Continuity and differentiability |
| 27 | Mean value theorems math.mean-value-theorems | T1 | Mean value theorem | Continuity and differentiability |
| 28 | Integration math.integration | T1 | Integration | Continuity and differentiability |
| 29 | Probability axioms and counting-based probability math.probability-basics | T1 | Random variables | Counting: permutations and combinations |
| 30 | Conditional probability and Bayes' theorem math.conditional-probability-bayes | T1 | Conditional probability and Bayes theorem | Probability axioms and counting-based probability |
| 31 | Random variables, expectation and variance math.random-variables-expectation | T1 | Random variables | Probability axioms and counting-based probability |
| 32 | Binomial and Poisson distributions math.discrete-distributions | T1 | Binomial distribution; Poisson distribution | Random variables, expectation and variance |
| 33 | Uniform, exponential and normal distributions math.continuous-distributions | T1 | Uniform distribution; Exponential distribution; Normal distribution | Random variables, expectation and variance, Integration |
| 34 | Mean, median, mode and standard deviation math.descriptive-statistics | T1 | Mean, median, mode and standard deviation | none |
General Aptitude
14 concepts| # | Concept | Tier | Syllabus lines | Prerequisites |
|---|---|---|---|---|
| 1 | Grammar and usage ga.verbal-grammar-usage | T1 | Verbal aptitude | none |
| 2 | Vocabulary: synonyms, antonyms, idioms ga.verbal-vocabulary | T1 | Verbal aptitude | none |
| 3 | Reading comprehension ga.verbal-reading-comprehension | T1 | Verbal aptitude | none |
| 4 | Sentence completion and ordering ga.verbal-sentence-completion-ordering | T1 | Verbal aptitude | Grammar and usage |
| 5 | Percentages, ratio and proportion ga.quant-percent-ratio-proportion | T1 | Quantitative aptitude | none |
| 6 | Time, speed, distance and work ga.quant-time-speed-work | T1 | Quantitative aptitude | Percentages, ratio and proportion |
| 7 | Number system and algebra ga.quant-algebra-numbers | T1 | Quantitative aptitude | none |
| 8 | Data interpretation ga.quant-data-interpretation | T1 | Quantitative aptitude | Percentages, ratio and proportion |
| 9 | Geometry and mensuration ga.quant-geometry-mensuration | T1 | Quantitative aptitude | none |
| 10 | Logical reasoning and deduction ga.analytical-logical-reasoning | T1 | Analytical aptitude | none |
| 11 | Number series and patterns ga.analytical-series-patterns | T1 | Analytical aptitude | none |
| 12 | Seating arrangements and puzzles ga.analytical-arrangements | T1 | Analytical aptitude | Logical reasoning and deduction |
| 13 | Paper folding and cutting ga.spatial-folding-cutting | T1 | Spatial aptitude | none |
| 14 | 3D visualisation and rotations ga.spatial-3d-visualisation | T1 | Spatial aptitude | none |