Final Exam

Due Thursday, December 9 at 3:30 pm Pacific

Solutions are available!

🔑 Solutions



Instructions

You have the full duration of this exam (2:30PM on December 3 through 3:30PM on December 9) to work on the final exam. There are no time limits on the exam other than that it has to come in before the deadline. That means that it’s fine to start working on the exam, take a break, go for a walk or hike in the area, get a good night’s sleep, come back, pick up where you left off, etc. This exam is designed to take roughly six hours to complete.

Please type your answers the way you type up your problem sets. There’s a $\LaTeX$ template available here if you’d like to use it, though it’s not required and you can use MS Word or Google Docs if you'd like.

đź–‹ Final Exam $\LaTeX$ Template

Exam-specific note: If you are using Overleaf to typeset your solutions, make sure your problem set partners are not shared on the document you use.

This exam includes three problems in which you will run a program through Qt Creator to enter your answers and submit online. The starter files are available here:

📦 Final Exam Starter Files

Once you’re finished, submit your written and coding answers on Gradescope. As with the problem sets, you will submit the written and coding components separately. Please leave appropriate buffer time to ensure your submission comes in by the deadline. As with the problem sets, we’ll grade the last version you submit before the deadline, so feel free to periodically submit what you have just in case something comes up.

Honor Code Policies

This exam is open-book and open-note, so you are free to make use of all course materials on the course website and on Canvas, including lecture slides and lecture videos. You are also permitted to search online for conceptual information (for example, by visiting Wikipedia). However, the final exam must be completed individually. It is a violation of the Stanford Honor Code to communicate with any other humans about the exam, to solicit solutions to the exam, or to share your solutions with others.

You are not permitted to communicate with other humans about the exam or to solicit help from others. For example, you must not communicate with other students in the course about the exam, and you must not ask questions on sites like Chegg or Stack Overflow.

If you have questions about this exam, you are welcome to post them in EdStem. We will not be able to offer much support other than clarifying questions about what is being asked of you in each problem. If you do post in EdStem, you must post privately; posting publicly violates the "do not communicate with other humans" rule.

All work done with the assistance of any material in any way (other than provided CS103 course materials) must include a detailed citation (e.g., “I visited the Wikipedia page for $X$ on Problem 1 and made use of insights $A$, $B$, and $C$”). Copying solutions is never acceptable, even with citation, and is always a violation of the Honor Code. If by chance you encounter solutions to a problem, navigate away from that page before you feel tempted to copy. If you’re worried you’ve done something you probably shouldn’t have and aren’t sure what to do, email the course staff before you submit and we’ll figure out how to proceed.

Words of Encouragement

Hi Everybody!

You've come quite a long way since the start of the quarter. Over the past ten weeks, we've gone through a whirlwind tour of discrete mathematics, computability theory, and complexity theory. Congratulations on making it this far!

For most of you, this has been your first time doing any sort of proof-based mathematics. You've worked hard to get where you are now, and we wanted to thank you for putting in that time and effort. We are incredibly proud of how well you’ve done so far.

The questions on this exam are designed for us to see how much you've learned over the past ten weeks. Ten weeks ago you wouldn't have been able to understand most of these questions, let alone answer them. Treat this exam as an opportunity to show us what you've learned over the course of this quarter. Give it your best shot – you can do this!

Good luck!

-Keith and the CS103 CAs

Problem One: Square and Triangular Numbers (8 Points)

On Problem Sets One and Two, you explored properties of natural numbers and techniques for writing direct proofs. This problem is designed to let you show us what you've learned in the process.

A natural number $n$ is called a square number if there exists a natural number $k$ where $n = k^2\text.$ The first few square numbers are $0, 1, 4, 9, 16, 25, \ldots \text.$ Intuitively, the square numbers count the number of squares in a square grid:

A 1x1 grid with one square, a 2x2 grid with four squares, a 3x3 grid with nine squares, a 4x4 grid with sixteen squares, and a 5x5 grid with twenty-five squares.

Now, a new definition. A natural number $n$ is called a triangular number if there exists a natural number $k$ where $n = \frac{k(k+1)}{2}\text.$ The first few triangular numbers are $0, 1, 3, 6, 10, 15, \ldots \text.$ Intuitively, the triangular numbers count the number of squares in these figures:

A figure made of a single square, which has one square in it. Next to it is a figure of squares made of two rows of squares. The top row has one square in it. The bottom row has two squares in it. Collectively, the figure has three squares. Next to this is a figure made of three rows of squares. The top row has one square in it. The second row has two squares in it. The third row has three squares in it. Colletively the figure has six squares in it. Next to that is a figure made of four rows of squares. The first row has one square in it. The second row has two squares in it. The third row has three squares in it. The fourth row has four squares in it. Collectively the figure has ten squares.

Prove that for all natural numbers $n$, the number $n$ is a triangular number if and only if $8n + 1$ is a square number. There's a lovely geometric intuition for this shown here:

A 3x3 grid that is covered as follows. There are eight copies of the 1x1 triangular figure around the border, and the middle square is left uncovered. Next to that is a 5x5 grid. It is covered by four 3x2 figures, each of which is broken apart into two copies of the triangular figure with two rows. They are arranged in a pinwheel around the center square, which is left uncovered. Similarly, a 7x7 grid is tiled with four 3x4 rectangles in a pinwheel, leaving the center square uncovered, and the center square is left uncovered.

Just to make sure you didn't miss it, the statement to prove is a biconditional rather than a standard implication.

Feel free to make use of the following theorem, which we proved in the first week of class: for all natural numbers $n$, the number $n$ is even if and only if $n^2$ is even.

Problem Two: Cantor's Theorem Revisited (8 Points)

On Problem Set Three, you explored functions and set cardinality. This problem explores that topic in more depth.

In lecture, we proved Cantor's theorem by using the famous diagonal argument. We assumed we had a function from a set $S$ to its power set $\powerset{S}$, then showed that this function couldn't be surjective. But there's actually another way to prove Cantor's theorem. Imagine we have a function $f : \powerset{S} \to S$ for some set $S$. We can show, using a modified diagonal argument, that $f$ can't be injective.

Fill in the blanks below to complete the following proof. As usual, the amount of space in each of the blanks is not necessarily representative of how much you need to write. For full credit, the resulting proof should be "self-contained" in that it does not reference results proved elsewhere.

Theorem: For any set $S$, if $f : \powerset{S} \to S$ is a function, then $f$ is not injective.

Proof: Assume for the sake of contradiction that $\blank$. Now, define the set $D$ as

\[D = \Set{ x \in S \suchthat \exists T \in \powerset{S}. (x = f(T) \land x \notin T) }\text,\]

and let $y = f(D)$. We consider two cases:

  • Case 1: $y \notin D$. $\blank$. This contradicts the fact that $\blank \text.$

  • Case 2: $y \in D$. $\blank$. This contradicts the fact that $\blank \text.$

In either case, we reach a contradiction, so our assumption was wrong. Therefore, for any set $S$, if $f : \powerset{S} \to S$ is a function, then $f$ is not injective. $\qed$


Problem Three: Multiplicative Graphs (8 Points)

On Problem Set Four, you explored graph theory and properties of graphs specified with formal definitions. This problem continues that exploration.

Let $n$ be a natural number. The multiplicative graph of order n is the undirected graph $G_n = (V_n, E_n)$ defined as follows:

  • $V_n = \Set{k \in \naturals \suchthat 1 \le k \le n}\text.$
  • $E_n = \Set{\Set{x, y} \suchthat x \in V_n\text{, }y \in V_n\text{, }x \ne y\text{, and } \exists z \in \naturals. y = xz }\text.$

This problem explores properties of multiplicative graphs.

  1. (1 Point) What is the size of the largest independent set of $G_{10}$? No justification is required.

  1. (1 Point) What is the size of the smallest dominating set of $G_{137}$? No justification is required.

  1. (1 Point) What is the smallest natural number $n$ where $G_n$ contains a 5-clique? No justification is required.

  1. (5 Points) Prove there is a natural number $n$ where, for all natural numbers $k \ge n$, the graph $G_k$ is not bipartite.

Problem Four: Graph Strain (14 Points)

On Problem Set Four, you explored graphs and the pigeonhole principle. On Problem Set Five, you played around with induction. And on Problem Sets Six and Seven, you explored induction involving multiple variables. This problem is designed to let you show what you've learned in the process.

Let's begin with a new definition. Given a graph $G$, we can color each node of $G$ one of three different colors (ecru, puce, and zomp). We'll say that an edge of $G$ is strained if its endpoints are given different colors.

  1. (1 Point) Across all possible coloring of the nodes of a $5$-clique, what is the minimum number of edges strained? No justification is required.

  1. (1 Point) Across all possible coloring of the nodes of a $5$-clique, what is the maximum number of edges strained? No justification is required.

Your task is to prove the following theorem:

Theorem: Let $G = (V, E)$ be a graph with $m$ edges. Then there is a way to color the nodes of $G$ that strains at least $\frac{2m}{3}$ edges of $G$.

This shows that it's always possible to strain a large fraction of the edges of any graph.

  1. (12 Points) Let $P(n)$ be this predicate:

    $P(n)$ is "for any natural number $m$ and for any graph $G = (V, E)$ with $n$ nodes and $m$ edges, there is a way to color the nodes of $G$ that strains at least $\frac{2m}{3}$ edges."

    Prove the theorem by induction, using the predicate given above.

    Depending on the approach you take, you may find the following inequalities helpful:

    \[x + \floor{y} \le x + y \le x + \ceil{y}\] \[x - \floor{y} \ge x - y \ge x - \ceil{y}\]

Problem Five: Coins in a Bowl (3 Points)

On Problem Sets Six and Seven, you explored finite automata. This problem is here to let you show us what you've learned about DFA design.

I have a bowl that can hold up to four coins. Initially, the bowl begins with four coins in it. At the start of every minute, assuming the bowl isn't full, I'll add one more coin to the bowl. At any time, you can take as many coins out of the bowl to use as you see fit.

Let $\Sigma = \Set{\mathtt{0}, \mathtt{1}, \mathtt{2}, \mathtt{3}, \mathtt{4}}$. We can model your withdrawals from the bowl as a string over $\Sigma$ that says, for each minute, how many coins you take out of the bowl. For example, the string 311202 corresponds to the following scenario:

  • The first minute begins with four coins in the bowl. In that minute, you take 3 coins out of the bowl, leaving one behind.
  • The second minute begins with two coins in the bowl (one from before, plus one more). In that minute, you take 1 coin out of the bowl, leaving one behind.
  • The third minute begins with two coins in the bowl (one from before, plus one more). In that minute, you take 1 coin out of the bowl, leaving one behind.
  • The fourth minute begins with two coins in the bowl (one from before, plus one more). In that minute, you take 2 coins out of the bowl, leaving none behind.
  • The fifth minute begins with one coin in the bowl (zero from before, plus one more). In that minute, you take 0 coins out of the bowl, leaving one behind.
  • The sixth minute begins with two coins in the bowl (one from before, plus one more). In that minute, you take 2 coins out of the bowl, leaving none behind.

Here are some other strings corresponding to legal scenarios:

  • 400040004
  • 111111
  • $\varepsilon$
  • 000000

However, the following strings represent illegal scenarios, where at some point you attempt to take more coins out of the bowl than exist:

  • 33333333
  • 22220
  • 42
  • 000000044

Let $L$ = { $w \in \Sigma^\star \suchthat w$ represents a series of withdrawals that never withdraws more coins from the bowl than are present }. Using the DFA editor, design a DFA for $L$. Save your answer in the file res/Coins.automaton, and submit that file on Gradescope. You are welcome to use the DFA debugger and DFA tester bundled with the starter files to check your work.

Problem Six: Flightless Birds (3 Points)

On Problem Set Seven, you learned to write regular expressions. This problem explores writing a regular expression for a new language.

Let $\Sigma = \Set{\mathtt{m}, \mathtt{o}, \mathtt{a}}$. Write a regular expression for the language

$L =$ { $w \in \Sigma^\star \suchthat w$ does not contain moa as a substring }.

For example, the following strings are in $L$:

  • mooooooa
  • $\varepsilon$
  • momomomo
  • oomaomao

On the other hand, these strings are not in $L$:

  • $\underline{\texttt{moa}}$
  • $\texttt{mo}\underline{\texttt{moa}}\texttt{mo}$
  • $\texttt{o}\underline{\texttt{moa}}\texttt{o}$
  • $\texttt{momomomo}\underline{\texttt{moa}}$

Save your answer in the file res/FlightlessBirds.regexes, and submit that file on Gradescope. You are welcome to use the regex tester bundled with the starter files to check your work.

Problem Seven: The Lava Diagram (6 Points)

On Problem Set Seven, you explored distinguishability. On Problem Set Eight, you explored context-free grammars. On Problem Set Nine, you learned to classify languages according to their difficulties. This problem explores all of these ideas.

Run the starter files and select the Lava Diagram option. For each of the languages given below, place that language at the appropriate spot in the Lava Diagram. Each answer is worth one point. There is no penalty for an incorrect guess.

  1. The language of the following context-free grammar:

    \[\begin{array}{rcl} S & \to & VS \cfgor \mathtt{c}T \\ T & \to & VT \cfgor \mathtt{c}U \\ U & \to & \varepsilon \cfgor VU \\ V & \to & \mathtt{a} \cfgor \mathtt{b} \end{array}\]

  2. The language of the following context-free grammar:

    \[\begin{array}{rcl} S & \to & T \cfgor U \\ T & \to & \mathtt{a}T\mathtt{a} \cfgor \mathtt{b}T\mathtt{b} \cfgor \varepsilon \\ U & \to & \mathtt{a}U\mathtt{b} \cfgor \mathtt{b}U\mathtt{a} \cfgor \varepsilon \end{array}\]

  3. The language of the following context-free grammar:

    \[\begin{array}{rcl} S & \to & \mathtt{a}S\mathtt{a} \cfgor \mathtt{a}S\mathtt{b} \cfgor \mathtt{b}S\mathtt{a} \cfgor \mathtt{b}S\mathtt{b} \cfgor \varepsilon \end{array}\]

  4. A language that has $\Sigma^\star$ as a distinguishing set and whose complement is decidable.

  5. { $\encoded{M} \suchthat M$ is a TM and $M \rejects \encoded{M}$ }

  6. { $\mathtt{a}^n \suchthat n \in \naturals$ and the hailstone sequence terminates for $n$ }, under the assumption that the Collatz Conjecture is true.

Problem Eight: Uncomputable Functions (3 Points)

On Problem Set Nine, you explored undecidability and how to prove certain problems are undecidable. This problem explores what happens if we generalize those ideas into a slightly broader setting.

Your task in this problem is to prove it's not possible to implement a function

string precompute(string function, string input)

with the following behavior:

  • If function is the source code of a function that takes in a string and whose return type is string, and if function(input) halts, then precompute(function, input) returns function(input).
  • Otherwise, precompute(function, input) returns the empty string.

To do so, fill in the three blanks in the trickster function defined below. No justification is required.

____ trickster(____ input) {
    string me = /* source code of trickster */;
    return ____;
}

You should make our standard simplifying assumptions about computer programs - they don't get user input, they don't involve randomness, they don't crash, etc. After all, the point of this problem is to let you show what you've learned about decidability.