Compsci 225 Lecturer:
Exam: Revision Guide (Solutions)
Wednesday, October 28th, 5:00-7:30pm UoA 2021
For almost everyone enrolled in Compsci 225, Exams has announced that our exam will take place on October 28th at 17:00 time. You should verify this for yourself on Student Services Online in case your exam timetable is different (due to e.g. a clash), but for almost everyone If you have an issue with this exam time, please contact Exams as soon as possible to try to get things fixed! In particular, please note that Amal and I cannot reschedule or otherwise do anything about the timing of your exams: these things are entirely under the control of the University’s central Exams office, who typically ask for considerable lead time to process exceptions.
The exam is open book / open notes / open to Internet search, and will consist of 5-7 free-response problems, covering weeks 1-12 of the course, with about a 30/70 split between weeks 1-6 and weeks 7-12. To help you revise, I’ve written this revision guide: it contains a set of practice problems we’ve written to model the kinds of tasks you’re likely to face!
Specifically, you’ll find nine problems in this guide. These problems are not as polished as your exam tasks would be: i.e. some problems here will be much longer than reasonable exam problems would be, some might be a bit too short, etc. Note that your exam may mix and match concepts on some problems: like you saw in the test, you could have a problem that has some induction and some RSA mixed together, or some graph theory combined with error-correcting codes, so that we can cover most of the course without asking a ton of questions.
Solutions to these exercises can be found on the same Canvas page where you found this document. If you’re stuck, post to Piazza, or stop by the drop-in sessions and office hours!
1. (Graphs.)
(a) Suppose that G is a connected simple planar graph containing V vertices, E edges and F faces. Suppose further that each of V,E and F are prime numbers.
Prove that exactly one of V,E or F must be equal to 2.
(b) Suppose that G = (V, E) is a graph on n vertices, where each vertex has degree at least n/2. Prove that G must be connected.
(c) Let G be the set of all planar simple graphs. Given a planar graph G, let #V (G) denote
the number of vertices in G, and similarly let #E(G),#F(G) denote the number of edges
and faces in G. Define the function f : G → Z as follows:
f(G)=χ(G)·3−#V(G)+#E(G)−#F(G)+ deg(v) %2
v∈V (G) What is the range of f: i.e. what integers are possible outputs of f?
(a) The key observation to make here is that 2 is the only even prime number; all other primes are odd. Therefore, because the Euler characteristic tells us that V − E + F = 2, we cannot have all three of V, E and F be odd (as the sum/difference of three odd numbers is odd, not even!)
Indeed: the only way for V −E +F to be even is if either exactly one of V,E,F is 2, or if all three are 2.
In the case where all three are 2, this would mean in particular that we have a two-vertex two-edge graph. But G is simple, and so can contain at most one edge if it has just two vertices! This leaves us with just the case where exactly one of V, E, F is two, as claimed.
(b) Take any graph G in which the degree of every vertex is at least n/2, and pick any two vertices x, y ∈ V .
x has degree at least n/2, so it’s connected to n/2 other vertices. In particular, because there are n − 1 vertices other than x, it’s connected to over half of the vertices in G. So, because y has degree at least n/2, it’s also connected to over half of the vertices in G. In particular, this means that x and y have a neighbor in common, and so there’s a path of length 2 from x to y!
(c) First, we note that by the degree-sum formula, the sum of all degrees in G is 2#E(G), and thus that the degree sum modulo 2 is always 0; as such, we can ignore the last term. Next, we note that V − E + F for any planar graph is 1+ the number of connected components of G: i.e. if G is connected, V − E + F = 2, if G has two connected components, V −E+F = 3, and so on/so forth. As a result, we can see that 3−V +E−F is either 1, 0, or negative for all planar graphs.
Finally, we can note that if G is planar, χ(G) is at most 4, by the four-colour theorem. As a result, the range of f is clearly at most Z ∩ (−∞, 4]; we cannot output a value greater than 4, as the maxima of the individual functions that make up f cannot combine to yield a value greater than 4.
To conclude, we simply note that this range is actually attainable. K4, K3 and K2 are all connected planar graphs with chromatic numbers 2-4, and so generate the values 2,3,4 when plugged into f.
Now, to conclude, consider G = K1 ∪ K1 ∪ . . . ∪ K1, i.e. n isolated vertices in a graph. This has V −E +F = n+1, as we have n vertices and the one outside face; it also has χ(G) = 1, as we can give all vertices the same colour. Therefore, we have f(G) = 3−(n+1)=2−n,andthuscangetanyinteger≤1asanoutputoff aswell.
2. (Automata.)
(a) Suppose that we are working over the alphabet Σ = {a,b}. Draw an automata that recognizes the language of all strings that contain exactly two a’s and two b’s (in any order.)
(b) Let p be a prime, and let L be the set of all strings over the alphabet {a} whose lengths are multiples of p. Prove or disprove the following claim: “If M is a DFA over the alphabet {a} whose language of accepted strings is L, then the number of states in M is a multiple of p.”
(c) In class, we proved that you cannot create a DFA over the alphabet {a} that accepts precisely the language L of strings with prime lengths. Prove that you cannot create a DFA over the language L = {a} that accepts precisely the set of strings with nonprime lengths.
(a) Here is one (of many) possible DFA! In this diagram, the blue states are the accepting states, and the red dashed lines are labeled with any letters not used on other edges leaving the state they originate from.
initial ab
ab bababa bba baa
To expand a bit on how you’d get this: If you want to accept any string with 2 a’s and 2 b’s, you want to accept precisely the strings aabb,abab,abba,baab,baba,bbaa, and no others (as those are the only strings with 2 a’s and 2 b’s.)
So: how would you recognize just one of these strings, like say aabb? Well: one way to do it is via the left path on the diagram above. That is:
Draw four vertices in a row.
Make it so that you go from the initial vertex to the first one if your DFA sees an
Similarly, go from the first to the second if your DFA sees another ”a”.
Go from the second to the third if your DFA sees a ”b”.
Go from the third to the fourth if your DFA sees a ”b”.
If your DFA sees anything after that fourth state, it should go to the ”garbage” state
at bottom, from which it cannot leave: this is because we want to not accept any
strings with more than two a’s or b’s.
Aswell,ifyourDFAseesanythingotherthanthea→a→b→bpath,itshould
leave this path as well, as we’re trying to detect only aabb.
You can do the same thing for all of the other strings! Combining these paths together
gives you the DFA above, and finishes the problem.
(b) This is false! Consider the following 3-state automaton:
init, 0 a odd a
This automaton accepts all strings of length 0 because the initial state is an accepting state, as well as any string whose length is a positive multiple of 2, because of the length- 2 loop that cycles between the even and odd states. 3 is not a multiple of 2, so we’ve disproven our claim by finding a counterexample.
(c) You could create an argument here that parallels the “no DFA exists that accepts only prime-length strings” from the typeset notes, or you could consider the following quick proof by contradiction: assume that such a DFA could exist, and call it M.
Now, consider M, defined by taking M and reversing which states are accepting and which are not. If M accepts a string, it’s a string that M rejects; conversely, if M rejects a string, it’s a string that M accepts.
This means that M accepts precisely the language of all prime-length strings. We know this is impossible from lecture, and thus have arrived at a contradiction, as desired.
3. (Error-correcting codes.)
(a) Find a ternary length 4 code C with distance 3, containing at least 4 elements.
(b) A Latin square (introduced briefly at the end of Lecture 15) is a n × n grid in which every square contains a number from 1,2,…n, with no repeats in any row or column. Two 4 × 4 Latin squares are drawn below.
1234 1234 2143 4321 3412 2143 4321 3412
i. Describe how to make a n × n Latin square, for every n.
ii. Given a Latin square, you can make a table of its cells by listing the row, column,
and symbol for each:
111 −→ 122 212 221
By thinking of the rows of this table as a code, prove that An(3, 2) ≥ n2. Solution:
(a) Here’s an example with nine words, which is the biggest code possible (as we’ll see in the last exercise proof!) {0000, 0111, 0222, 1012, 1120, 1201, 2021, 2102, 2210} .
You only need four codewords here, so any four of the above (or any other set of four words that you’ve found!) can work.
(b) For (i), there are many ways to go. The simplest is probably to list the numbers 1, 2, . . . n at the top row, and then shift this row one over repeatedly n times:
1 2 3 … n-2 n-1 n 2 3 4 … n-1 n 1 345…n12
. . . . . . .
n 1 2 … n-3 n-2 n-1
For (ii), just observe that our “no repeats” property means that if we have any two distinct triples (r1, c1, s1), (r2, c2, s2) in our code, we know that if r1 = r2, we must have c1 ̸= c2 (each cell shows up once) and s1 ̸= s2 (no repeated symbols in any row). Similarly, if we have c1 = c2, we must have s1 ̸= s2 by the same logic. As such, it is impossible for (r1, c1, s1) and (r2, c2, s2) to agree in more than one place, and thus the distance of the code generated by these tables is at least 2.
This, along with (i), proves that An(3,2) ≥ n2: we’ve made a table with n2 rows, and those rows are a length-3 n-ary code with distance 2.
4. (Number theory and RSA.)
(a) In class, we said when we choose the public exponent e, we tended to reuse the same values: i.e. e = 3 or e = 65537 are common choices.
Suppose that you instead picked e by taking a uniformly-chosen random value from 1 to φ(n), where n = pq is your public base. Show that at least 50 % of the time, the value of e you choose is one for which the RSA algorithm cannot be ran.
(b) In the RSA algorithm, our first step involves choosing a pair of large prime numbers p, q. Suppose you picked p = q: i.e. you reused the same large prime for q, and believed1 that this would make φ(n) = φ(p2) = (p − 1)2.
Will the RSA process still work: i.e. will you always be able to find a value of d, and will (Me)d = M mod n always hold? Or will it fail (and if so, why?)
(a) This one is pretty quick. Observe that in RSA, p and q are a pair of distinct prime numbers. In particular, this means that at least one of p, q must be odd, as there is only one even prime (namely, 2.) Therefore, φ(n) = (p − 1)(q − 1) is always even.
If we choose a value of e uniformly from 1 to φ(n), we have a 50 % chance of choosing an even value of e. If we do so, then e−1 mod φ(n) will not exist: for any integers d, k, we have that ed + kφ(n) is an even number, and thus we cannot find a value of d such that ed ≡ 1 mod φ(n). But this means that we cannot find the private exponent d = e−1 mod φ(n) needed for RSA!
(b) This will often not work. The process of finding d will still function just fine: as long as eisnotafactorofp−1,thend=e−1 modφ(n)willexist.
However, the decryption step can go wrong. Note that if φ(n) = (p − 1)2 and n = p2, thenbecauseed≡1 modφ(n),wecanwriteed=1+k(p−1)2.Thismeansthat
e d ed 1+k(p−1)2 kp2−2kp+k+1 k(p2−1)−2kp+2k+1 p2−1k 2k(p−1) (M)=M=M=M=M =MMM.
This, sadly, is not equal to M for most values of M, p. You can try to simplify it down further, but Fermat’s little theorem won’t be of too much use (it only tells you that Mp−1 = 1 mod p; i.e. you don’t get information about M mod p2 − 1), and if you experimentally try out a few values you’ll see that this frequently doesn’t work. To illustrate this by randomly picking values: let’s choose p = 4, e = 2, M = 3. This means thatp2 =16,(p−1)2 =9,d=5andthusthatMed modp2 =310 mod16=9. Thisis not 3, so this doesn’t work here!
There are occasions where this will accidentally work out, but in general this process isn’t going to lead you to M, and thus this is not a good implementation of RSA.
1Note that this calculation isn’t right: if you look up the definition of φ, you can see that φ(p2) = p(p − 1), as φ(n) should be “the number of positive integers relatively prime to and less than n.” You don’t need to know how to calculate φ(n) for any values other than n = pq in this class, as we haven’t gone through this definition: this footnote is just a FYI for future studies!
5. (Logic and proofs.)
(a) Let f : R → R be a function. Express the negation of the following statements without
using any words of negation or the symbol ¬. (̸= is fine, though!) A:∀x∈R,∃y∈Rsuchthatf(x)=y.
B:∃y∈R,∀x∈Rsuchthatf(x)=y.
Prove that B implies A. Does A imply B?
(b) Create a truth table for the compound proposition (p → q) ∧ (r ↔ (¬r)). Is this propo-
sition logically equivalent to (p ∧ q) ∧ r?
(a) We first write down the negations of these statements here:
A translates as follows: “Not(For any real number x, there is a real number y such that f(x) = y.)” This simplifies to “There is some real number x such that for all real numbers y, f(x) ̸= y,” because negating a quantifier “flips” it (i.e. the ∃,∀’s flip)
B similarly translates to “For any real number y, there is a real number x such that f(x) ̸= y.”
We now return to the original statements, and prove that B implies A. This is not too hardtosee: Bsaysthatthereisonevalueofy,suchthatforallx∈R,f(x)=y. Ifthis is true, let’s write down that one value of y, and call it “Special-Y” so we don’t forget what it is.
Now, let’s look at A, which says that for any x in R, we want a value of y such that f(x) = y. This is now true! Take any x ∈ R. We know that f(x) = our “Special-Y” value from earlier, so if we let y be that “Special-Y” value, we’ve proven that A holds! The other direction, however, fails. Consider the function f : R → R given by f(x) = x2. For any x ∈ R, there is a y ∈ R, namely y = x2, such that f(x) = y; however, there is no single y ∈ R that you can pick out ahead of time such that for every x, f(x) = y; this is because f(x) takes on multiple values, as f(0) = 0,f(1) = 12, and y cannot have multiple values!
(b) As described in class, we create a truth table:
p q r p→q ¬r r↔(¬r) FFFTTF FFTTFF FTFTTF FTTTFF TFFFTF TFTFFF TTFTTF TTTTFF
Notice that this proposition always outputs false, no matter what inputs it is given! Therefore, it cannot be equivalent to any proposition that can output true values, like (p∧q)∧r (which is true when p,q,r are all true.)
(p → q) ∧ (r ↔ (¬r))
6. (Induction and recurrence relations.)
(a) Two difference equations (i.e. recurrence relations) are given below. Find the general
solutions to each.
i. xn +2xn+1 −3xn+2 =4
ii. 3yn − yn+1 = n · 9n
(b) Define the values an recursively by setting a0 = 0, a1 = 1 and an = an−1 − an−2 for all n ≥ 2.
Use induction to prove that if n is a multiple of 3, then an is even.
(c) Find every logical flaw in the following proof. Explain why the flaws you’ve found are
indeed logical flaws.
Claim: Take any positive integer n. Then, if x, y are a pair of positive integers such that max(x,y) = n, then x = y.
Proof. We proceed by induction on n.
Our base case is when n = 1. In this case, the only two positive integers x, y such
that max(x,y) = 1 are precisely x = 1,y = 1, in which case our claim that x = y holds.
We proceed to the inductive step. Here, we assume that our claim holds for all values up to some n, and seek to prove that it holds for n+1 as well.
To be specific: our claim for n + 1 is that if we take any two positive integer x, y suchthatmax(x,y)=n+1,thenx=ymusthold. Toseewhythisistrue,lookat x − 1, y − 1. Because we’ve decreased both x, y by 1, their maximum has decreased by 1 as well; therefore max x − 1, y − 1 = n.
But we know by our inductive hypothesis that if the maximum of two numbers is n, then they must be equal! In other words, the inductive assumption tells us that x − 1 = y − 1, and thus that x = y as desired.
(a) We use the methods from class (see Amal’s lectures for week 9 and Monday, week 10, the practice problems posted in week 9, and also this link for many more worked examples! Specifically: let’s start with (i) Here, we have xn + 2xn+1 − 3xn+2 = 4. To begin, we solve the “homogeneous” form of this equation, i.e. the one in which we have all of our sequence terms on the left, the other bits on the right, and replace those other bits with 0: i.e. xn + 2xn+1 − 3xn+2 = 0. We do this by “guessing” that our equation will have a solution of the form xn = Kxn for some constants K,x. If we make such a guess and plug it in, our equation is
0 = Kxn + 2Kxn+1 + 3Kxn+2 ⇒0=3×2 −2x−1
if we divide by Kxn and then multiply by −1. This equation has roots given by the √
quadratic equation 2± 4+12 = 1,−1. As such, K1(1)n +K2−1n is our solution 633
to the homogeneous part of our equation (if we get multiple possible values of x through this process, the overall solution is the sum of those individual solutions.)
Now, we solve the “particular” part of our solution. When we do this, we look at the right-hand-side and guess a form for the solution that matches it. Amal gave a table for these correspondences in class; you can also find it here. In this case, our RHS is
a constant, so we would guess a constant solution: i.e. xn = D for some constant D. Plugging this in yields D + 2D − 3D = 4, i.e. 0 = 4; a problem! In general, you cannot try a particular solution that is also one of the homogeneous solutions (as we saw above, K2 is a homogeneous solution) because plugging that in yields 0.
Instead, if you’re in this situation, try multiplying your guess by n. In our case, this means that we’re guessing xn = Dn, and thus have Dn+2D(n+1)−3D(n+2) = 4, i.e. 2D − 6D = 4, i.e. D = −1, and thus have −n as a particular solution.
To finish, just add your homogeneous and particular solutions together. This gives you
as your general solution, for any constants K1,K2.
For (ii), we proceed in the same way. The homogeneous form of 3yn − yn+1 = n · 9n is 3yn − yn+1 = 0. If we guess that the solution here is Kyn, we get 3(Kyn) − Kyn+1 = 0, which is just 3 − y = 0 if we divide by Kyn. This gives us K3n as our homogeneous solution.
Now, we look at the particular part of our solution. Here, our right-hand-side is n9n, and thus a solution that would “match” this in form is one of the form 9n(An + B). If we plug this in to our equation, we get
n9n =3·9n(An+B)−9n+1(A(n+1)+B) ⇒n9n =n9n(3A−9A)+9n(3B−9A−9B)
⇒ −6A = 1, −6B − 9A = 0
from which we can conclude that A = − 1 , B = 1 , and thus that our particular solution
In total, then, our overall general solution is , for any constant K.
(b) We proceed by induction, where our claim P(n) is the statement “a3n is even.” For our base cases, we check the first few entries of our sequence:
0isamultipleof3;inthiscase,a0 =0isindeedeven.
1,2, are not multiples of 3, so we don’t necessarily care about what happens here.
Still,outofcuriosity,wecancheckandseethata1 =1anda2 =a1−a0 =1−0=1
are both odd.
At3,wehavethata3 =a2−a1 =1−1=0,andsoisindeedeven.
At4,5,wehavethata4 =a3−a2 =0−1=−1,a5 =a4−a3 =(−1)−0=−1are
At 6, we have that a6 = a5 −a4 = (−1)−(−1) = 0 is again even (and indeed is again
At7,8,wehavethata7 =a6−a5 =0−(−1)=1anda8 =a7−a6 =1−0=1;so
they’re again odd.
It looks like our sequence has