This capstone synthesises the major topics of CS 121 into an applied portfolio. Complete each section in writing, showing your work. These are the types of problems that appear on the CS 121 final exam and in technical interviews.
Part A — Logic & Proofs
Negate and simplify: ¬(∀x ∃y (x · y = 1)) over the integers.
Prove by induction: ∑i=0n 2i = 2n+1 − 1.
Prove by contradiction: there are infinitely many prime numbers.
Proof that infinitely many primes exist (Euclid's proof):
Assume finitely many primes: p⊂1;, p⊂2;, …, pk.
Let N = p⊂1; · p⊂2; · … · pk + 1.
N is not divisible by any pi (remainder 1 each time).
So N is either prime itself, or has a prime factor not in our list.
Either way, our list was incomplete — contradiction. □
Part B — Counting & Graph Theory
A 6-character password uses lowercase letters and digits. How many passwords have at least one digit?
A graph has 7 vertices all of degree 3. How many edges? (Use the Handshaking Lemma.)
Does a graph where every vertex has degree 3 have an Euler circuit? Explain.
Answers:
1. Total = 36&sup6;. None with digit = 26&sup6;. At least one digit = 36&sup6; − 26&sup6; ≈ 2.17 billion.
2. Sum of degrees = 7·3 = 21. But 21 is odd. Impossible! A degree-3 graph on 7 vertices cannot exist (Handshaking: sum must be even).
3. If such a graph existed: all degrees even (3 is odd → back to the contradiction above). If we take n=8 vertices, all degree 3: sum=24=2·12 → 12 edges. All even degree → Euler circuit exists (if connected).
Part C — Automata & Complexity
Design a DFA over Σ={a,b} that accepts strings with an even number of a’s.
Explain why bubble sort is O(n²) and merge sort is O(n log n).
Give an example of an NP-complete problem. Why can’t we solve it efficiently today?
Study tip: For the DFA problem, draw the state diagram first. Label each state with what it "remembers" about the input so far.
Reflection
Which topic surprised you most in this course? Write 2–3 sentences connecting it to something in your daily life or another CS course. Good answers often link: graph theory → social networks / GPS routing; FSMs → regex / compilers; Big-O → why some apps feel slow on large data.
Knowledge Check
The sum 1 + 2 + 4 + … + 2^n (geometric series) equals
Linear; the series grows exponentially.
Correct — ∑2i from i=0 to n = 2n+1−1. Provable by induction.
Polynomial; this series is exponential.
Still linear; incorrect.
Recap: geometric series ∑0n 2i = 2n+1−1. Induction: base n=0 gives 1=2−1. Step: assume at k, add 2k+1, get 2k+2−1.
Euclid's proof that infinitely many primes exist is a proof by
It starts by assuming the opposite.
Correct — assume finitely many primes, construct a number divisible by none of them.
No inductive step; it's a one-shot contradiction argument.
Contrapositive changes P⇒Q to ¬Q⇒¬P; Euclid's proof doesn't fit that structure.
Recap: assume finite primes p⊂1;,…,pk. Form N = p⊂1;·…·pk+1. N is divisible by none of them (remainder 1). Contradiction.
A graph where every vertex has degree 3 must have
Handshaking: sum of degrees = 2|E| is always even.
Correct — sum of degrees = 3n must be even, so n must be even.
Edge count depends on n; it's 3n/2 edges.
Even if degrees work out even, the graph also needs to be connected.
Recap: Handshaking sum = 3n = 2|E|, so n must be even. 7 vertices each of degree 3 is impossible.
A DFA recognising 'even number of a's' over {a,b} needs
One state can't distinguish even from odd count.
Correct — toggle between states on each 'a'; 'b' keeps the same state.
FSMs have fixed, finite states regardless of input length.
That would make it a pushdown or Turing machine, not an FSM.
Recap: even/odd parity of a count = 2 states. qeven (start, accept), qodd. On 'a': swap. On 'b': stay. Accept in qeven.
The greatest open question in theoretical CS is
Interesting, but not the central open problem.
Correct — unsolved since 1971; one of the Millennium Prize Problems worth $1 million.
This is settled: O(n log n) is optimal for comparison-based sorting.
That's the halting problem, which is proved undecidable — already settled.
Recap: P vs NP — open since Cook's 1971 paper. Most believe P ≠ NP but no proof. A proof either way would be the most important result in CS history.