EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.Attention mechanismML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.Boolean algebra calculatorTools · A Boolean expression simplifier that names the law used at every step.K-map solverTools · Fill in a Karnaugh map and see the groups, the minimal SOP and POS, and the essential terms.Logic gate simulatorTools · Wire up gates, flip the switches, and get the truth table and expression of your circuit.Regex to NFA converterTools · Type a regular expression and watch Thompson’s construction build its NFA, fragment by fragment.NFA to DFA converterTools · Enter an NFA or a regex and step through the subset construction, then minimise the DFA.DFA simulatorTools · Edit a DFA, run strings through it step by step, batch-test them and share the machine as a link.Regular expressions to automataTheory · Regex to NFA to DFA to minimal DFA, worked through on one example with every set shown.The halting problemTheory · Why no program can tell whether every program halts, with the paradox program played out.Pigeonhole principleDiscrete maths · n pigeons, k holes: why some hole gets ⌈n/k⌉, and the surprising things that follows from it.Dijkstra’s algorithmAlgorithms · Shortest paths with a priority queue: a worked table, a proof, and a graph you can redraw.Hash functionsAlgorithms · Keys in, buckets out: hash a word four ways, then watch chaining and probing handle collisions.Sorting algorithm visualizerTools · Up to seven sorts race on the same data, then step through any one of them line by line.LaTeX table generatorTools · Type or paste a table, merge cells, pick booktabs, and copy clean tabular code.Combination calculatorTools · Exact nCr with the cancelling shown, combinations with repetition, and a full list for small n.Permutation calculatorTools · nPr, nʳ, anagrams like MISSISSIPPI and round-table seatings, with exact working.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal, Dijkstra’s algorithm, hash functions and Big-O growth, with pseudocode that follows along.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, the pigeonhole principle and Boolean algebra, explained with worked examples and interactive checkers.TheorySection · Finite-state machines, regular expressions and automata, the halting problem, and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · Free browser tools: truth tables, Boolean simplification, K-maps, logic gates, nCr and nPr, regex to NFA to DFA, sorting and graph visualisers, and LaTeX tables.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
Free tool

K-map solver: Karnaugh maps for 2 to 5 variables

Fill in a Karnaugh map by clicking cells, typing minterms and don’t-cares, or entering an expression. The solver draws the groups on the map, including the ones that wrap round the edges, and gives the minimal sum of products, the minimal product of sums and the essential prime implicants, for 2 to 5 variables.

Interactive: Clickable Karnaugh map with don’t-cares and drawn groupsUpdated

K-map solver

Variables
Show groups for
Click a cell to cycle 0 → 1 → X (don’t care).
    Minimal sum of products (SOP)
    Minimal product of sums (POS)

    Prime implicants

    Every largest group of 1s (don’t-cares allowed). Essential ones cover a 1 that no other group covers.

      LaTeX

      How to use the K-map solver
      • Pick the number of variables (2 to 5) and, if you like, rename them. Changing the count clears the map.
      • Fill the map. Click a cell to cycle it through 0, 1 and X. Each cell shows its minterm number in the corner. Or type a list such as Σm(1, 3, 7, 11, 15) + d(0, 2, 5) and press “Set minterms”; the Σ, the m and the brackets are optional, so 1 3 7 11 15 works too. Or type an expression such as AB' + CD and the solver fills the map from its truth table.
      • Read the groups. Each coloured outline is one product term of the answer. A dashed edge means the group continues on the other side of the map. Hover over or tab to a term in the list below the map to highlight just that group.
      • Switch to POS to group the 0s instead. The groups then show the sum terms of the minimal product of sums.
      The address bar records the map, so you can bookmark a problem or send it to someone.
      How a Karnaugh map works
      A Karnaugh map is a truth table folded into a grid so that neighbouring cells differ in exactly one variable. For four variables, the rows are labelled with ABAB and the columns with CDCD, both in Gray-code order: 00, 01, 11, 10. Because 10 and 00 also differ in one bit, the left edge is adjacent to the right edge and the top to the bottom. The map is really drawn on a torus.
      Minterm numbers in a four-variable map. Note the order 0, 1, 3, 2 along each row.
      AB \ CD00011110
      000132
      014576
      1112131514
      10891110
      Two adjacent 1s differ in one variable, so by the combining law XA+XA‾=XXA + X\overline{A} = X they merge into one product without that variable. Four 1s in a 2×2 square or a line lose two variables, eight lose three. Simplifying a function becomes covering every 1 with as few rectangles as possible, each as large as possible, with sides that are powers of two.
      The rules for grouping
      1. Groups are rectangles of 1, 2, 4, 8 or 16 cells. L-shapes and diagonals are not allowed.
      2. Every 1 must be in at least one group. Groups may overlap.
      3. Make each group as large as possible: a group that cannot grow is a prime implicant.
      4. Use as few groups as possible. Start with essential prime implicants, the groups that are the only way to cover some 1, then cover what is left.
      5. Don’t-cares (X) may be included in a group when they make it bigger, but need not be covered.
      6. Groups wrap round the edges, and the four corners of a four-variable map are one group of four.
      To read a group as a product, keep the variables that are constant across it: write AA if it is 1 throughout and A‾\overline{A} if it is 0 throughout. Variables that change inside the group drop out.
      Worked example: the four corners
      Take F=Σm(0,2,5,7,8,10,13,15)F = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15). The 1s at minterms 0, 2, 8 and 10 sit in the four corners. Across all four, B=0B = 0 and D=0D = 0, while AA and CC change, so the group is B‾ D‾\overline{B}\,\overline{D}. The 1s at 5, 7, 13 and 15 form a 2×2 square in the middle, where B=D=1B = D = 1: the group is BDBD.
      The solver gives F = BD + B′D′, with 2 essential prime implicants. This is the function “BB equals DD”, an XNOR of two variables, though it started as eight minterms over four.
      Worked example: don’t-cares
      A circuit only ever sees some inputs, so the output for the others does not matter. Here F=Σm(1,3,7,11,15)+d(0,2,5)F = \Sigma m(1, 3, 7, 11, 15) + d(0, 2, 5):
      AB \ CD00011110
      00X11X
      010X10
      110010
      100010
      The column CD=11CD = 11 holds 3, 7, 15 and 11: the group CDCD. That leaves minterm 1. On its own it would need a long product, but with the don’t-cares 0 and 2 it fills the whole top row (minterms 0, 1, 3 and 2), A‾ B‾\overline{A}\,\overline{B}. The answer is F = A′B′ + CD. Without the don’t-cares the best is A′B′D + CD, which has 5 literals instead of 4.
      Load this example into the solver with “Example with don’t-cares”. There is a second minimal answer, CD+A‾DCD + \overline{A}D, which groups minterm 1 with 3, 5 and 7 instead; both have two terms and four literals.
      Product of sums from the 0s
      Grouping the 0s instead of the 1s gives the complement F‾\overline{F} as a sum of products. Applying De Morgan turns each product into a sum with every literal complemented, and the whole into a product of sums. In the solver, switch “Show groups for” to POS: a group of 0s where A=0A = 0 and C=1C = 1 becomes the sum term (A+C‾)(A + \overline{C}), because it must be 0 exactly on that group.
      Five variables
      A five-variable map is drawn as two four-variable maps, one for A=0A = 0 and one for A=1A = 1, placed side by side. Cells in the same position on the two maps are adjacent, as if one map were stacked on top of the other. A group that appears in the same place on both maps drops AA. Beyond five variables, maps stop being practical by hand, and the Boolean algebra calculator or the Quine–McCluskey method is the better tool.
      When there is no essential prime implicant
    Some functions have none. The 3-variable function with 1s at minterms 0, 1, 2, 5, 6 and 7 has 6 prime implicants, each pair of neighbouring 1s around a ring, and every 1 is covered by two of them, so none is essential. The solver tries the possibilities and finds a cover with 3 terms: AC + A′B′ + BC′. A different choice of three works equally well.
  
      Common mistakes
      • Binary order instead of Gray order. Labelling columns 00, 01, 10, 11 puts 01 next to 10, which differ in two bits, and groups across them are wrong. Always use 00, 01, 11, 10.
      • Groups of three or six. Only powers of two give a single product. Three 1s in a row need two overlapping groups of two.
      • Missing the wrap-around. The leftmost and rightmost columns are neighbours, and so are the top and bottom rows. The four corners make one group.
      • Covering the don’t-cares. An X never has to be in a group. Include it only if it makes a group larger.
      • Too many groups. A group whose 1s are all covered by other groups is redundant and should be dropped, even if it is a prime implicant.
      For the algebra behind the map, step through the same simplification in the Boolean algebra calculator. To check a result row by row, use the truth table generator, and to build the circuit, the logic gate simulator.
      References
      1. M. Karnaugh, “The map method for synthesis of combinational logic circuits”, Transactions of the AIEE, Part I 72(5), 1953. doi:10.1109/TCE.1953.6371932
      2. E. W. Veitch, “A chart method for simplifying truth functions”, Proceedings of the ACM National Meeting, 1952.
      3. M. M. Mano and M. D. Ciletti, Digital Design, 6th ed., Pearson, 2018. Chapter 3.
      4. “Karnaugh map”, Wikipedia.