Midterm Exam II

Due Sunday, November 7 at 2:30 pm Pacific

Solutions are available!

🔑 Solutions



Instructions

You have the full 49 hours to work on the midterm. 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. Although you have the full 49 hours to complete the exam, the exam itself is designed to take around three 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 us MS Word or Google Docs if you'd like.

đź–‹ M2 $\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 one problem in which you will run a program through Qt Creator to enter your answers and submit online. The starter files are available here:

📦 M2 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 midterm 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

You have made amazing progress since the start of the quarter. Seriously - take a minute to reflect on how much you've learned! This exam is designed to let you show us what you've learned since we started our journey into Theoryland a little over seven weeks ago.

We're all cheering you on! Best of luck - you can do this.

Problem One: Idempotent Contractions (8 Points)

On Problem Set Three, you explored idempotent functions. As a reminder, a function $f : A \to A$ is called idempotent if the following is true:

\[\forall a \in A. f(f(a)) = f(a)\text.\]

On Problem Set Five, you explored contractions. To refresh the definition, a function $f : \naturals \to \naturals$ is a contraction if $f(0) = 0$ and the following is true:

\[\begin{aligned} & \forall n \in \naturals. (n \ge 1 \to \\ & \quad f(n) \le n - 1 \\ &) \end{aligned}\]

This problem explores how these definitions overlap.

Prove by induction that if $f : \naturals \to \naturals$ is an idempotent contraction, then $f(n) = 0$ for all $n \in \naturals$.

Problem Two: Pantone Graphs (10 Points)

On Problem Set Four, you explored different classes of graphs, different structures within graphs, and what happens when you color parts of a graph. This problem continues that exploration.

A graph $G = (V, E)$ is called a pantone graph if there is way to color the nodes of $G$ one of three different colors (ecru, puce, and zomp - yes, those are all colors) such that every node $v \in V$ is adjacent to exactly one node of each color.

  1. (2 Points) Run the provided starter program and choose the “Graph Editor” option. Open the file res/Pantone.graph and draw a graph with the following properties:

    • The graph is a pantone graph.
    • The graph has at least one node.
    • Of pantone graphs with at least one node, yours uses the fewest possible number of nodes.

    Since this is a midterm, you will not be able to run automated tests to check if your answer is correct. Similarly, when you upload your answer to Gradescope, you will not be able to see your score until after the midterm comes due.

    You may submit online to the autograder as many times as you'd like. We'll only take the last submission.

As a refresher from Problem Set Four, a dominating set in a graph $G = (V, E)$ is a set $D \subseteq V$ such that the following is true:

\[\forall v \in V. (v \not\in D \to \exists u \in D. \Set{u, v} \in E)\text.\]

Pantone graphs have relatively small dominating sets.

  1. (8 Points) Prove that if $G = (V, E)$ is a pantone graph with exactly $3n$ nodes, then there exists a dominating set of $G$ containing at most $n$ nodes.

    The generalized pigeonhole principle says that if you distribute $x$ objects into $y$ bins, then some bin has at least $\ceil{\frac{x}{y}}$ objects in it and some bin has at most $\floor{\frac{x}{y}}$ objects in it.

Problem Three: Pushes and Pulls (12 Points)

On Problem Sets Three, Four, and Five, you explored different classes of functions and different operations on them. On Problem Sets Four and Five, you played around with graphs and their structures. This problem is designed to let you show us what you've learned along the way.

Let's begin with some new definitions that we'll use in this problem. Let $G = (V, E)$ be an arbitrary (undirected) graph. A push of $G$ is a function $p : V \to E$ such that the following is true:

\[\forall v \in V. v \in p(v)\text.\]

Similarly, a pull of $G$ is a function $q : E \to V$ satisfying this requirement:

\[\forall e \in E. q(e) \in e\text.\]

And finally, if $p$ is a push of $G$ and $q$ is a pull of $G$, we say that $q$ balances $p$ if the following is true:

\[\forall v \in V. (q \circ p)(v) = v\text.\]

As is often the case with new definitions, it's usually easiest to understand what those definitions mean by working through some concrete examples.

  1. (2 Points) Consider the graph $G = (V, E)$ shown below. Fill in the blanks below to define a push $p : V \to E$ of $G$ and a pull $q : E \to V$ of $G$ such that $q$ balances $p$. Express your answers as piecewise functions rather than as pictures.

    An undirected graph with four nodes: 0, 1, 2, and 3. 0 has edges to 1 and 2. 1 has edges to 0, 2, and 3. 2 has edges to 0 and 1. 3 has an edge to 1.

    \[p(v) = \begin{cases} \blank & \text{if } v = 0 \\ \blank & \text{if } v = 1 \\ \blank & \text{if } v = 2 \\ \blank & \text{if } v = 3 \\ \end{cases} \qquad \qquad q(e) = \begin{cases} \blank & \text{if } e = \blank \\ \blank & \text{if } e = \blank \\ \blank & \text{if } e = \blank \\ \blank & \text{if } e = \blank \\ \end{cases}\]

Here's a useful fact about pushes and pulls.

  1. (4 Points) Let $G = (V, E)$ be a graph and let $p : V \to E$ and $q : E \to V$ be an arbitrary push and an arbitrary pull of $G$, respectively. Prove that if $q$ balances $p$, then $p$ is injective.

As a refresher from lecture, a vertex cover of a graph $G = (V, E)$ is a set $C \subseteq V$ such that

\[\begin{aligned} & \forall u \in V. \forall v \in V. (\Set{u, v} \in E \to \\ & \quad u \in C \lor v \in C \\ & )\end{aligned}\]

Vertex covers are closely related to pulls.

  1. (6 Points) Let $G = (V, E)$ be a graph and let $q : E \to V$ be a pull of $G$. Define the set $C = \Set{ v \in V \suchthat \exists e \in E. q(e) = v }$. Prove that $C$ is a vertex cover of $G$.

    This problem is independent of part (ii), and we don't expect you to use that result here.