Corrected practice final exam: Mathematics for Computer Science (201-N11)

The first block gathers the four cells where $A=0$ and $C=0$, that is minterms 0, 1, 4 and 5: it gives the term $\overline{A}\,\overline{C}$. The second gathers the cells where $A=1$ and $C=1$, minterms 10, 11, 14 and 15: it gives $AC$. In both blocks, $B$ and $D$ take every value, so they DISAPPEAR. Hence $f=\overline{A}\,\overline{C}+AC$. Both blocks of four are shaded in the figure.

The complete disjunctive normal form lists one term for each row equal to 1 in the table, that is EIGHT terms of four literals each: $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}+\overline{A}\,\overline{B}\,\overline{C}D+\overline{A}B\overline{C}\,\overline{D}+\overline{A}B\overline{C}D+A\overline{B}C\overline{D}+A\overline{B}CD+ABC\overline{D}+ABCD$. The simplification in part a) took us from 8 terms of 4 literals to 2 terms of 2 literals, that is from 32 literals to 4: this is exactly what the saving in gates of a circuit measures.

The function depends only on $A$ and $C$: it equals 1 when $A=C=0$ and when $A=C=1$, that is when $A$ and $C$ are EQUAL, and 0 otherwise. This is the XNOR gate, also called the equivalence or coincidence gate. We write $f=A\odot C=\overline{A\oplus C}$, where $\oplus$ is the exclusive or.

The negation swaps the quantifiers and negates the predicate: “there EXISTS a user $u$ such that FOR EVERY file $f$, $u$ can NOT read $f$”. In other words, at least one user cannot read any file. The rule is mechanical: every “for every” becomes “there exists”, every “there exists” becomes “for every”, and the final property is negated. Skipping a single swap produces a statement that has nothing to do with the original.

$P\Rightarrow Q$ is NOT equivalent to its converse $Q\Rightarrow P$: with $P$ true and $Q$ false, the first is false and the second is true. It IS equivalent to its contrapositive $\overline{Q}\Rightarrow\overline{P}$, as the table shows: both equal 0 only when $P$ is true and $Q$ is false, and 1 in the other three cases. This is what justifies proof by contrapositive, and it is also why confusing the converse with the contrapositive is the most expensive mistake in logic.

Successive divisions by 2: $202=128+64+8+2$, so $202=11001010_{2}$. For hexadecimal, we group the bits in nibbles of four: $1100$ is C and $1010$ is A, so $202=\mathrm{CA}_{16}$. Check: $12\times 16+10=202$ ✓. Going through hexadecimal saves recounting every bit.

First write $75=01001011_{2}$, since $75=64+8+2+1$. INVERT every bit: $10110100$. ADD 1: $10110101$. This is $-75$ in two's complement, that is $\mathrm{B5}_{16}$, or 181 if it were read as an unsigned number. Check: $181+75=256=2^{8}$ ✓, which is the very definition of two's complement.

$0111$ is $+7$, the largest positive value on 4 bits. Adding 1 gives $1000$, which is $-8$ and not $+8$: the sign bit has turned on. On the wheel, we have gone from the highest position of the positive half-circle to the first position of the negative half-circle, crossing the only discontinuity of the scale. This is a signed OVERFLOW, and the binary addition did not flag it.

$100=01100100$ and $50=00110010$. Their binary sum is $10010110$, which is $150$ unsigned but $-106$ in two's complement, since $150-256=-106$. So there is a signed OVERFLOW: the exact result, 150, exceeds the largest representable value, 127. We detect it from the fact that two POSITIVE operands produced a result with a negative sign, which no carry out indicates here.

Because two's complement is designed for exactly that: addition modulo $2^{n}$ is the same operation whichever way we read the codes, and only the NAME given to the codes changes. Overflow, on the other hand, means leaving the representable RANGE, and that range differs: $[0, 255]$ unsigned, $[-128, 127]$ signed. So we detect it with the carry out for unsigned numbers, and with the unexpected change of sign for signed numbers. A processor computes both flags at the same time and lets the program pick the one that matters to it.

REFLEXIVE: every $x$ has the same remainder as itself ✓. SYMMETRIC: if $x$ and $y$ have the same remainder, so do $y$ and $x$ ✓. TRANSITIVE: if $x$ and $y$ have the same remainder and so do $y$ and $z$, then $x$ and $z$ do too ✓. So this is an equivalence relation, and its classes are the three sets $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$, corresponding to the remainders 0, 1 and 2.

$E$ has 9 elements, so $2^{9}=512$ subsets, each element being either in or out. The subsets with exactly 3 elements number $\binom{9}{3}=\frac{9\times 8\times 7}{6}=84$. We check consistency with the sum of the binomial coefficients of row 9, which is indeed 512.

$A=\{0,2,4,6,8\}$ has 5 elements, $B=\{0,3,6\}$ has 3, and $A\cap B=\{0,6\}$, the multiples of 6, has 2. So $\left|A\cup B\right|=5+3-2=6$, and we check directly: $A\cup B=\{0,2,3,4,6,8\}$, six elements ✓. Without the subtraction, we would count 0 and 6 twice.

REFLEXIVE: every integer divides itself ✓. ANTISYMMETRIC: if $a$ divides $b$ and $b$ divides $a$ with $a,b>0$, then $a=b$ ✓. TRANSITIVE: if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$ ✓. So it is an ORDER relation, but it is NOT total: 2 and 3 are not comparable, since neither divides the other. We call it a PARTIAL order, and it is the most common situation in computer science, for example for dependencies between modules.

These are two descriptions of the same object, and we can pass from one to the other in both directions. From an equivalence relation, the CLASSES form a partition: they are non-empty, pairwise disjoint, and their union is $E$. From a partition, we define a relation by declaring two elements equivalent when they lie in the same piece, and we check that it is reflexive, symmetric and transitive. The three properties of an equivalence thus correspond exactly to the three properties of a partition, which explains why none of them can be dropped.

From the displayed matrix: $A$ points to $B$ and $C$, degree 2; $B$ to $C$ and $D$, degree 2; $C$ to $D$, degree 1; $D$ to $E$, degree 1; $E$ to $A$, degree 1. Sum of the out-degrees: $2+2+1+1+1=7$, which is indeed the number of EDGES (arcs) of the graph. In a directed graph, this sum always equals the number of arcs, and not twice that number as in the undirected case.

The $(i,j)$ entry of $M^{2}$ is $\sum_{k}M_{ik}M_{kj}$: each term equals 1 if and only if there is an arc from $i$ to $k$ AND an arc from $k$ to $j$. The sum therefore counts the PATHS OF LENGTH 2 from $i$ to $j$. From $A$ to $D$: through $B$, since $A\to B\to D$ ✓, and through $C$, since $A\to C\to D$ ✓. The entry is therefore 2.

The paths of length 2 starting at $A$ first go through $B$ or $C$. From $B$: $A\to B\to C$ and $A\to B\to D$. From $C$: $A\to C\to D$. Total: THREE paths. This is the sum of the row of $A$ in $M^{2}$, and we can compute it without writing the whole matrix, by adding the out-degrees of the successors of $A$, that is $2+1=3$.

Yes: $A\to B\to C\to D\to E\to A$ is a cycle of length 5 through every vertex, that is a Hamiltonian cycle. There is a second, shorter one: $A\to C\to D\to E\to A$, of length 4. A graph with a cycle has no topological sort, which rules out using it as a dependency graph between modules, for example.

Its $(i,j)$ entry counts the total number of paths of length 1, 2, 3 or 4 from $i$ to $j$. Such an entry is non-zero if and only if there is a path from $i$ to $j$, because in a graph with 5 vertices, any path with no repeated vertex has at most 4 arcs. This matrix therefore lets us read REACHABILITY, and its Boolean version is the transitive closure of the graph.

$2026=26\times 77+24$, so $2026\bmod 26=24$. For $-45$: the remainder must be non-negative, so we take $q=-2$ and $-45=26\times(-2)+7$, hence $-45\bmod 26=7$. The reflex $-45=26\times(-1)-19$ would give $-19$, which is not a valid remainder.

$y=5\times 12+8=68$, and $68=26\times 2+16$, so $y=16$. The letter of rank 12 is M, the letter of rank 16 is Q: M becomes Q. We always reduce AFTER the addition, never between the two operations, which is allowed because congruence is compatible with both operations.

The coefficient must be INVERTIBLE modulo 26, that is coprime to 26. We have $\gcd(5,26)=1$ ✓, so 5 is suitable. On the other hand $\gcd(13,26)=13$: with 13, the function $x\mapsto 13x+8$ is not injective, it sends all the letters to only two values, and the message becomes undecipherable even for its recipient. CRITERION: $a$ is suitable if and only if $\gcd(a,26)=1$, which leaves 12 possible coefficients out of 26.

We look for $u$ such that $5u\equiv 1\pmod{26}$. By trial: $5\times 21=105=26\times 4+1$ ✓, so the inverse is 21. Decryption: from $y=5x+8$ we get $5x=y-8$, then $x=21\left(y-8\right)\bmod 26$. We can expand: $x=21y-168$, and $-168\bmod 26=14$ since $-168=26\times(-7)+14$, so $x=21y+14\bmod 26$.

$x=21\times 3+14=63+14=77$, and $77=26\times 2+25$, so $x=25$. Check by encrypting: $5\times 25+8=133$, and $133=26\times 5+3$ ✓, we do get 3 back. The two functions are therefore inverses of each other, which is exactly what the invertibility of 5 modulo 26 guarantees.

BASE CASE at $n=1$: on the left $1^{3}=1$, on the right $\left(\frac{1\times 2}{2}\right)^{2}=1$ ✓. INDUCTIVE STEP: suppose the formula holds for $k$. Then the sum for $k+1$ is $\left(\frac{k(k+1)}{2}\right)^{2}+(k+1)^{3}=\frac{k^{2}(k+1)^{2}+4(k+1)^{3}}{4}=\frac{(k+1)^{2}\left(k^{2}+4k+4\right)}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}=\left(\frac{(k+1)(k+2)}{2}\right)^{2}$ ✓. The hypothesis was used to replace the sum of the first $k$ cubes, and the decisive step is factoring out $(k+1)^{2}$. Check at $n=4$: $1+8+27+64=100$ and $\left(\frac{4\times 5}{2}\right)^{2}=10^{2}=100$ ✓.

The sum of the cubes is the SQUARE of the sum of the integers: $1^{3}+\dots+n^{3}=\left(1+2+\dots+n\right)^{2}$. This is a remarkable identity, often attributed to Nicomachus, and it is far from obvious: nothing in the definition of cubes announces that they add up to a perfect square. It also gives an instant check: the sum of the cubes is always a perfect square.

BASE CASE at $n=0$: $7^{0}-1=0$, divisible by 6 ✓. INDUCTIVE STEP: suppose $7^{k}-1=6m$. Then $7^{k+1}-1=7\times 7^{k}-1=7\left(7^{k}-1\right)+7-1=7\times 6m+6=6\left(7m+1\right)$ ✓. The trick is to write $7\times 7^{k}$ as $7\left(7^{k}-1\right)+7$, so as to force the expression for $k$ to appear. We could also have concluded directly by congruence: $7\equiv 1\pmod 6$ so $7^{n}\equiv 1$.

BASE CASE: $u_{0}=2\geq\sqrt 2\approx 1.414$ ✓. INDUCTIVE STEP: suppose $u_{k}\geq\sqrt 2$, so $u_{k}>0$. We study $u_{k+1}-\sqrt 2=\frac{u_{k}}{2}+\frac{1}{u_{k}}-\sqrt 2=\frac{u_{k}^{2}-2\sqrt 2\,u_{k}+2}{2u_{k}}=\frac{\left(u_{k}-\sqrt 2\right)^{2}}{2u_{k}}$. The numerator is a square, hence non-negative, and the denominator is strictly positive: the difference is non-negative, so $u_{k+1}\geq\sqrt 2$ ✓. Recognizing a perfect square is what makes the proof immediate.

This is exactly NEWTON's method applied to $f(x)=x^{2}-2$, whose iteration is $u_{n+1}=\frac{1}{2}\left(u_{n}+\frac{2}{u_{n}}\right)$, which is the given relation. Part d proves that the sequence stays above the root from the very first step, which is the property observed in the chapter on recursion: the error $e_{n+1}=\frac{e_{n}^{2}}{2u_{n}}$ is always positive. Computations: $u_{1}=1.5$, $u_{2}\approx 1.41667$, $u_{3}\approx 1.414216$, against $\sqrt 2\approx 1.414214$.

We start at the root 50: $40<50$, so we go left to 30. Then $40>30$, so we go right to 40. Finally $40=40$, found. The path is $50\to 30\to 40$ and it cost THREE comparisons, against seven in the worst case of a sequential search on the seven keys. The path is highlighted in the figure.

The tree in the figure has height 2, counting the root at level 0. A binary tree of height $h$ holds at most $2^{h+1}-1$ keys, since level $k$ holds at most $2^{k}$ and $\sum_{k=0}^{h}2^{k}=2^{h+1}-1$. Here $2^{3}-1=7$ ✓, the tree is PERFECTLY full. We recognize the formula of the Towers of Hanoi, which is no accident: both count a structure that doubles at every level.

A balanced tree of $n$ keys has a height of about $\log_{2}n$, so we need at most $\log_{2}(1000)+1\approx 10.97$, that is 11 comparisons. Sequential search would need up to 1000, about 91 times more. This is the same gain as binary search, which makes sense: a balanced binary search tree IS a binary search laid out in memory.

Each new key being larger than all the previous ones, it systematically goes right: the tree DEGENERATES into a linked list of height 6. The search cost becomes LINEAR again, up to 7 comparisons. This is the worst case of the structure, and it occurs precisely on data that is already sorted, a frequent situation in practice. This is what motivates automatically balanced trees, such as red-black trees.

There are $7!=5040$ possible insertion orders, all equally likely. Exactly one gives the strictly increasing chain, and exactly one the strictly decreasing chain, that is 2 degenerate orders in this sense. The probability is therefore $\frac{2}{5040}=\frac{1}{2520}\approx 0.0004$, about 0.04 percent. The worst case is thus extremely rare on random data, which explains why the AVERAGE height of a randomly built tree is of order $1.39\log_{2}n$, very close to the optimum. We find exactly the trade-off of quicksort: a catastrophic but unlikely worst case.

FALSE, implication is not symmetric. $P\Rightarrow Q$ is false in the single case $P$ true and $Q$ false, whereas $Q\Rightarrow P$ is false in the symmetric case: they therefore differ on two of the four rows. What IS equivalent to $P\Rightarrow Q$ is its CONTRAPOSITIVE $\overline{Q}\Rightarrow\overline{P}$. Example: “if it rains, the ground is wet” does not imply “if the ground is wet, it rains”.

FALSE if we work with SIGNED INTEGERS. On 8 signed bits, the representable range is $[-128, 127]$, and 150 exceeds it: the resulting bit pattern, $10010110$, reads as $-106$. So there is a silent OVERFLOW. The claim is only correct for unsigned numbers, where the range goes up to 255. Specifying the convention is not a vocabulary detail, it is what decides the result.

FALSE, it is a PARTIAL order. It is indeed reflexive, antisymmetric and transitive, but it is not TOTAL: 2 and 3 are not comparable, since neither divides the other. A total order requires any two elements to be always comparable, which is the case for the usual order but rarely for the orders that come up in computer science, such as dependencies between tasks.

FALSE. Euclidean division requires $0\leq r<26$, so $-19$ is not a valid remainder. We take $q=-2$: $-45=26\times(-2)+7$, so $-45\bmod 26=7$. This is also what Python returns. In C or Java, the operator does give $-19$, but it does not compute the Euclidean remainder: we then have to correct it with $((a\ \%\ n)+n)\ \%\ n$.

FALSE without an assumption of BALANCE. If the keys are inserted in increasing order, the tree degenerates into a linked list and the search becomes linear again, with $n$ comparisons instead of $\log_{2}n$. The logarithmic guarantee only exists for trees that are kept balanced, such as red-black trees or AVL trees. With RANDOM insertions, the average height stays close to $1.39\log_{2}n$, but an average is not a guarantee.

Because a leak of the database would immediately hand over every account, and not only those of the site: users reuse their passwords elsewhere. REVERSIBLE encryption is no better, since the decryption key is necessarily present on the server and will be stolen along with everything else. Only a one-way function will do, that is a hash function: the server verifies by recomputing the hash, without ever being able to go back to the password.

With $N=65{,}536$ slots, the 50 percent threshold is reached at about $1.18\sqrt{N}=1.18\times 256\approx 302$ keys. The figure confirms it: the curve crosses $0.5$ just after 300. The result is striking, 302 keys in 65,536 slots are enough, a fill rate below half of one percent. This is the birthday paradox applied to hashing.

$\frac{200{,}000}{65{,}536}\approx 3.05$ accounts per slot on average. The PIGEONHOLE principle guarantees that at least one slot holds at least $\left\lceil 3.05\right\rceil=4$ of them, which is a very weak bound; in practice, with a good hash function, the most heavily loaded slot holds a dozen. The important conclusion is that collisions are UNAVOIDABLE, so the structure must handle overflow lists.

$26^{8}=208{,}827{,}064{,}576\approx 2.09\times 10^{11}$, so about $21$ seconds to exhaust the space. Without salt, this effort breaks EVERY account at once, since the same password gives the same hash everywhere, and the attacker can even settle for a precomputed table. With a random SALT for each user, the hash depends on the account: the attacker has to redo the 21 seconds FOR EACH user, that is about 48 days for 200,000 accounts, and no precomputed table is of any use. Salt does not make a weak password stronger, it prevents the attack from being shared across accounts.

ONE, only ever store hashes, produced by a one-way function. TWO, salt every password with a random value specific to the user, to prevent any shared attack or precomputed-table attack. THREE, choose a SLOW, tunable hash function, of the bcrypt or Argon2 kind, so that the $10^{10}$ attempts per second of part d drop to a few thousand. These three rules depend on no particular technology, they follow directly from the counting in this course.

Yes. The path $A\to B\to D\to E$ works, of length 3, and so does $A\to C\to D\to E$. We can check it on the matrix: the entry of $M^{3}$ at the corresponding position is non-zero. Since the arc $E\to A$ also exists, the two machines are mutually reachable and therefore belong to the same strongly connected component.

In an undirected network, linking every pair takes $\binom{n}{2}=\frac{n(n-1)}{2}$ links. For $n=5$: $\frac{5\times 4}{2}=10$ links. For $n=100$: $\frac{100\times 99}{2}=4950$. The number grows like the SQUARE of the number of machines, which makes a full mesh impractical beyond a few hundred nodes and explains the use of hierarchical topologies.

We run a DEPTH-FIRST traversal, marking each vertex with one of three states: unvisited, in progress, finished. If we meet an arc leading to a vertex that is IN PROGRESS, we have found a cycle. The traversal visits each vertex once and examines each arc once, so its cost is $O(V+E)$, linear in the size of the graph. This is also the algorithm that produces a topological sort when no cycle is found.

The two conditions are to have a BASE CASE, here a vertex with no unvisited successor, and to make the amount of remaining work DECREASE, which is ensured by MARKING the vertices already seen. If we forget the marking, the recursion runs forever as soon as the graph contains a cycle, since we keep passing through the same vertices. This is exactly the second termination condition of the chapter on recursion, transposed to graphs: the argument must get closer to the base case.

DEPTH-FIRST TRAVERSAL: $O(V+E)=100+300=400$ elementary operations, a matter of a microsecond. NAIVE TEST of all paths: the number of simple paths can reach the order of $99!$, a number with 156 digits, completely out of reach. The ratio is not a factor but a change of nature, from linear to factorial. This is the general lesson of the course: the right data structure and the right traversal turn an impossible problem into a trivial one, and no hardware makes up for choosing a bad algorithm.