La lista è una sequenza di strutture, ognuna contiene un elemento della lista e l'indirizzo della struttura successiva.

struct elemento {
  	int valore;
  	struct elemento *prossimo;
};

La lista contiene due elementi, quindi servono due strutture. La prima contiene l'intero 2 e l'indirizzo della seconda. La seconda contiene l'intero 14 e l'indirizzo nullo che indica la fine della lista.

int main() {
	struct elemento *a, *b;

		/* creazione strutture */     
	a = malloc(sizeof(struct elemento));
	b = malloc(sizeof(struct elemento));

		/* prima struttura */
	a->valore = 2;
	a->prossimo = b;

		/* seconda struttura */
	b->valore = 14;
	b->prossimo = NULL;
}

La funzione vale 1 quando due o tre dei bit di ingresso valgono 1.

Le righe con valore 1 sono 011 101 110 e 111. La prima 011 dice che la funzione è vera quando gli ingressi valgono a = false, b = true e c = true. È lo stato degli ingressi quando è vera l'espressione booleana ¬a∧b∧c.

Nello stesso modo, si vede che le altre tre righe producono le congiunzioni a∧¬b∧c, a∧b∧¬c e a∧b∧c.

La formula è la loro disgiunzione:

¬a∧b∧c ∨
a∧¬b∧c ∨
a∧b∧¬c ∨
a∧b∧c

Un ciclo hamiltoniano è un ciclo che contiene tutti i nodi del grafo. Un ciclo è un percorso che finisce dove inizia.

Il grafo di quattro nodi richiesto deve contenere un ciclo perché un suo sottografo deve averne uno, ma non deve essere un ciclo hamiltoniano. Per esempio, può mancare un nodo.

Il ciclo è 2 → 3 → 4 → 2. Non è hamiltoniano perché non contiene uno dei nodi del grafo, il nodo 1.

Un sottografo indotto si ottiene selezionando alcuni nodi e tutti gli archi che li collegano. In questo caso, i nodi 2, 3 e 4 sono collegati da archi che compongono un ciclo hamiltoniano:

L'asterisco permette anche stringhe vuote, mentre il segno di somma no.

bbbbbaaaa

La prima parte a* corrisponde alla stringa vuota, la seconda b* alla stringa bbbbb e la terza a+ a aaaa. La stringa collima con l'espressione regolare.

aaab

La prima parte a* corrisponde a aaa, la seconda b* alla stringa b, manca una parte per a+, che non collima con la stringa vuota. La stringa non collima con l'espressione regolare.

aaa

Prima parte a* vuota, seconda parte b* vuota, terza parte a+ collima con aaa. La stringa collima con l'espressione regolare.

bbbbbbba

Prima parte a* vuota, seconda parte b* collima con bbbbbbb, terza parte a+ collima con a. La stringa collima con l'espressione regolare.

ab

Prima parte a* collima con a, seconda parte b* collima con b, terza parte a+ non collima con la stringa vuota. La stringa non collima con l'espressione regolare.

a

Prima parte a* vuota, seconda parte b* vuota, terza parte a+ collima con a. La stringa collima con l'espressione regolare.

La notazione O-grande fornisce una stima di massima dell'andamento del tempo di esecuzione quando la grandezza dell'input aumenta. Si ottene calcolando quante istruzioni vengono eseguite, trascurando moltiplicatori e addendi che crescono meno di quelli più grandi. La definizione formale è che un programma ha tempo di esecuzione O(n²) se esistono due costanti a e b tali per cui il programma esegue meno di a × n² + b istruzioni quando ha n dati di ingresso. In pratica, le istruzioni sono in numero quadratico ripetto alla grandezza dell'input.

Qualsiasi programma che esegue un ciclo nidificato su un vettore ha questo tempo di esecuzione. Un esempio è la verifica se un vettore contiene elementi ripetuti. Per ogni elemento del vettore si effettua una scansione per cercare un elemento uguale in tutto il vettore. Il numero di istruzioni esegito è quindi il quadrato della lunghezza del vettore.

#!/bin/python

vettore = [1, 2, 9, 3, 2, 4]

l = len(vettore);

for i in range(l):
    for j in range(l):
        if i != j and vettore[i] == vettore[j]:
            print("elemento ripetuto: ", vettore[i]);
            print("indici", i, j);
            exit()