Class 14: Invariant Principle (Thu, 13 Oct 2016)

Schedule

Problem Set 6 (is posted now) is due 21 October (Friday) at 6:29pm.

Exam 1 was returned Tuesday. If you did not pick yours up yet, you can get it after class today. I will start charging exponentially-increasing storage fees for inexcusably unclaimed exams starting tomorrow.

def power(a, b):
   x = a
   y = 1
   z = b
   while z > 0:
      r = z % 2 # remainder of z / 2
      z = z // 2 # quotient of z / 2
      if r == 1:
         y = x * y
      x = x * x
   return y

def slow_power(a, b):
   y = 1
   z = b
   while z > 0:
      y = y * a
      z = z - 1
   return y

Class 13: State Machines (Tue, 11 Oct 2016)

Schedule

Exam 1 Solutions are now posted.

Drop Date is today. If you have any concerns about whether you should stay in the class, please talk to me after class today.

There is no problem set due this week! Problem Set 6 (will be posted later this week) is due 21 October (Friday) at 6:29pm.

Exam 1 was returned during class today. (Exam grades will eventually make it into collab, but haven’t yet. When they do, please confirm that the score on your exam matches what is recorded in collab, and that PS1-5 are all recorded correctly.)

Exam 1 Solutions (Tue, 11 Oct 2016)

The solutions to Exam 1 are here: Exam 1 Solutions.

Problem Set 5 Comments (Sat, 1 Oct 2016)

The preliminary solutions and comments for PS5 are now posted in collab: PDF. (Problem 9 is not included, but will be added later.)

We are providing the PS5 solutions now before they are graded, so you have the solutions to read with plenty of time before the exam.

Three-Clause Challenge Refuted! (Fri, 30 Sep 2016)

Challenge 5 has been refuted by Henry Spece!

The challenge as stated was actually bogus! The four-clause solution isn’t the shortest possible equivalent 3CNF formula. Henry found a three-clause equivalent 3CNF formula, and proved that there is no two-clause equivalent 3CNF formula.

His answer is below:

The four-clause 3-CNF equivalent solution to the logical equation is not the smallest equivalent solution to the equation.

The following is the original formula: A ∨ ¬B ∨ C ∨ (¬D ∧ E).
Here is a two-clause solution: (A ∨ ¬B ∨ ¬x) ∧ (x ∨ C∨ ¬D) ∧ (x ∨ C ∨ E).

This can be shown to be equivalent to the original formula by constraining x to be A∨¬B and algebraically reducing:

(A∨¬B∨¬(A∨¬B))∧(A ∨ ¬B ∨ C ∨ ¬D)∧(A ∨ ¬B ∨ C ∨ E)
(A ∨ ¬B ∨ C ∨ ¬D)∧(A ∨ ¬B ∨ C ∨ E)
(A ∨ ¬B ∨ C) ∨ (¬D∧E)
A ∨ ¬B ∨ C ∨ (¬D∧E)

To further prove the equivalence, we can make the original formula unsatisfied and show that there is no satisfying assignment for x. To be unsatisfied, A must be F, B must be T, and C must be F. This reduces the formula to:

(F ∨ F ∨ ¬x)∧(x ∨ F ∨ ¬D)∧(x ∨ F ∨ E)

Because of the first term, x must be F if we want to satisfy the formula:

(F ∨ F ∨ T)∧(F ∨ F ∨ ¬D)∧(F ∨ F ∨ E) ≡ (¬D∧E)

This has the same satisfiability as the remaining variables in the original formula (if ¬D∧E is not satisfied, there is no satisfying assignment for x).

Proof that this is the shortest possible solution: There is no two or one clause solution because a new variable in addition to A, B, C, D, and E is required for each clause to have only three terms, and this variable must be repeated (by the rules we use to select that variable). Therefore, only 5 variables may be represented in a two-clause solution, while there are at least six variables required for equivalence to the original formula.

Proof that a new variable is required: The original formula reduces to (A ∨ ¬B ∨ C ∨ ¬D)∧(A ∨ ¬B ∨ C ∨ E) in CNF form, which has two clauses, each containing a unique combination of four variables. There is no way to reduce the number of variables per clause of a solution without adding a variable, therefore at least one variable must be added to form the 3-CNF equivalent of this formula.

Anonymous Feedback Comments (Thu, 29 Sep 2016)

This anonymous comment was submitted through collab:

A lot of my fellow classmates and I are concerned about this class because we feel that we aren’t provided with the resources necessary to be able to do the homework in a reasonable amount of time/effort. So many people spend hours and hours at office hours several times a week but even the TAs don’t understand our questions and are not able to help us understand any of the concepts. I understand that we’re supposed to be challenged by the class, but if we aren’t well-equipped to work through the challenges it becomes extremely frustrating. I feel like the class could be improved if the lectures were better structured so that we’re thoroughly taught the concepts and steps we can take to think through a problem rather than going through examples that are hard to understand because we’re only copying down things we don’t fully understand and that don’t apply to other problems we’re expected to solve. I don’t mean to be rude at all so I apologize if it comes off that way, it’s just that so many of the students and I are frustrated and stressed out about how much we don’t understand in the class even after seeking help repeatedly.

One of the drawbacks of anonymous comments, is I have no way to follow-up to better understand what is really going on here. I do appreciate the anonymous comments, but you shouldn’t be worried about making comments like this directly — I view any student making comments with the goal of improving their own learning and making things better for the class as a positive thing, and you shouldn’t be worried that I would count any thoughtful and respectful comment against you.

As for the content, as best as I’m able to interpret it, the perception that the problems are too hard does not fit with what I’m seeing in the assignments. For all of the problem sets so far, more than 90% of students have received grades at least 5 (the exception was for PS3, where it was 89%), which means nearly all answers correct (with some justifications that could be better). On all the assignments, fewer than 5% of the submissions have been 4 or below. So, either we are grading them too generously and students are getting 5+s without actually understanding much (which I don’t think is the case, but perhaps we are giving too much benefit of the doubt for unclear answers), or, more likely, people are acutally understanding things quite well, but it is taking more “pain” and effort to get there than you expect.

It doesn’t make sense to spend time in lecture copying down things you don’t understand. If there are things you don’t understand in lecture, please stop and ask questions, or if you aren’t comfortable doing that, at least post questions on slack. If you don’t ask questions, I don’t know what is confusing, or what should be explained. I make the slides and notes available so you can spend lecture time thinking instead of writing (that said, I think it is often helpful to write things down yourself as part of understanding them, or discovering what is unclear).

There are lots of resources available, but I think you are expecting the wrong kind of problems if you are looking for resources to tell you how to solve them. I understand why this is, since it is what you expect from most of your previous classes. You were all good students, and great at redoing things you saw in class, that’s why you got into UVA.

But, you shouldn’t expect most problems from now on (in this class, and in any worthwhile classes you take after this one) to be like this. You’re not learning anything (useful), if you are just re-solving problems you’ve already seen, or making straightforward symbol replacements in them.

Nearly all of the problems you did in previous math classes were problems you could type into Wolfram Alpha and it could solve instantly; this isn’t surprising - if a problem is something you can solve by following given rules in a straightforward way, it shouldn’t be a problem for humans to spend time on, the rules should be encoded in programs that can do it automatically. Sometimes its worthwhile for humans to learn what the rules are and get some experience following them, but the further along you get, and the more advanced computing systems get, the more ridiculous it is for humans to spend tons of time learning to do things computers already do well.

So, we do learn steps for solving problems in this class, both in lecture and in the book. And, all of the problems on the problem sets are related to things you learn in class. But, many of the problems also involve some creative step that isn’t a straightforward replication of something you’ve seen in class or the book. Without that, I wouldn’t really see the point in assigning them - I’m not assigning problem sets to check if you are doing the reading and coming to class, the point of the problem sets is to develop your understanding of the concepts by having you figure out how to apply them in new ways that go beyond things you’ve already seen and (more importantly) to develop your abilities as mathematical thinkers and problem solvers. You can’t do that by replicating problems you’ve already done, or by solving problems that are straightforward repetitions of problems you’ve already seen solved. But, before trying to solve new problems, you should make sure you understand the examples you’ve seen in the book and in class. It is usually much harder to come up with your own solutions to problems than to understand ones that are provided by others.

All that said, I would encourage anyone who feels like they are spending an unreasonable amount of time on this, or feeling frustrated and stressed out by it, to come to office hours to talk to me (or to make an appointment if you can’t make it then). My office hours have mostly been fairly empty, and the best sense I get of what is going on in the class is from students who come to talk to me during office hours, so I hope you’ll do that rather than just getting frustrated.

Class 12: Review (Thu, 29 Sep 2016)

Schedule

Problem Set 5 is due Friday at 6:29pm.

Exam 1 is in class on Thursday, 6 October. See Notes 11 for details. Remember to bring a good writing instrument (sharp pencil is recommended) and your page of notes to the exam.

See PDF Version for Notes.

Exam Review

Below are some notations you should understand. We use variables $P$ and $Q$ to represent logical propositions (with \T\ or \F\ value), $A$ and $B$ and $D$ (domain of discourse) to represent sets, and $x$ represents any mathematical object.

\begin{tabular}{cl} \multicolumn{2}{c}{\bf Logical Operators}
$P$ \smallcaps{implies} $Q$, $P \implies Q$ & Logical implication: when $P$ is \T, $Q$ must be \T
$P$ \smallcaps{iff} $Q$, $P \iff Q$ & Double implication: $P \implies Q \vee Q \implies P$
\smallcaps{not}$(P)$, $\neg P$, $\overline{P}$ & Logical negation
$P$ \smallcaps{and} $Q$, $P \wedge Q$ & Logical conjunction (\T\ when both $P$ and $Q$ are \T)
$P$ \smallcaps{or} $Q$, $P \vee Q$ & Logical disjunction (\T\ when $P$ or $Q$ is \T\ (or both)
$P$ \smallcaps{xor} $Q$, $P \oplus Q$ & Exlusive or (\T\ when either $P$ or $Q$ is \T, but not both
\multicolumn{2}{c}{\bf Quantifiers}
$\forall x \in A \ldotp P(x)$ & $P(x)$ for {\em every} element $x$ of the set $A$
$\exists x \in A \ldotp P(x)$ & $P(x)$ for {\em at least one} element $x$ of the set $A$
\multicolumn{2}{c}{\bf Set Operators}
$x \in A$ & Set membership, $A$ contains the element $x$
$x \notin A$ & Set non-membership, $A$ does not contain $x$
$A \subseteq B$ & $A$ is a subset of $B$: $\forall x \in A. x \in B.$
$A = B$ & set equality: $A \subseteq B \vee B subseteq A$
$A \cup B$ & Set Union: $\forall x. x \in A \cup B \iff x \in A \vee x \in B.$
$A \cap B$ & Set Intersection: $\forall x. x \in A \cup B \iff x \in A \wedge x \in B.$
$ A - B$ & Set Difference: $\forall x. x \in A - B \iff x \in A \wedge x \notin B.$
$ \overline{A}$ & Set Complement: $\forall x. x \in D. x \in \overline{A} \iff x \notin A.$
$ A \times B$ & Cartesian Product: $\forall a \in A, b \in B \ldotp (a, b) \in A \times B.$
$ \textrm{pow}(A)$ & Power Set: $S \in A \iff S \subseteq A$.
\end{tabular}

Well-Ordering Principle

Remember the well-ordering principle template from Class 3:

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
2. Assume for contradiction that $C$ is non-empty.
3. By the well-ordering principle, there must be some smallest element, $m \in C$.
4. Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
5. Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

Since we didn’t finish the winning strategy proof in class, I’ve written it out fully here.

Theorem. Player 1 has a winning strategy in Take-Away if the number of sticks, $n$ is not divisible by 4.

For any induction proof, the first thing we need to do is write the theorem as a predicate on the natural numbers.

$$\forall n \in \mathbb{N} \ldotp P(n) ::= \textrm{ Player 1 has a winning strategy if }\exists a \in { 1, 2, 3 }, \exists k \in \mathbb{N} \textrm{ such that } n = 4k + a.$$

Base cases: $P(1)$, $P(2)$, $P(3)$.

$P(1)$: If there is $1$ stick remaining, Player 1 wins by taking 1 stick.
$P(2)$: If there are $2$ sticks remaining, Player 1 wins by taking 2 sticks.
$P(3)$: If there are $3$ sticks remaining, Player 1 wins by taking 3 sticks.

Inductive case: Using strong induction, $\forall m \in \mathbb{N}, m \ge 4 \ldotp (\forall k \in \mathbb{N}, k \le m. P(k)) \implies P(m + 1)$.

Since $m \ge 4$ we can write $m = 4k + b$ for some $k \in \mathbb{N}^{+}$ and $b \in {0, 1, 2, 3}$.

We consider four cases for each value of $b$.

Case 3: $b = 3$. Since $m = 4k + 3$, $m + 1 = 4k + 4 = 4(k + 1)$. Since $m + 1$ is divisible by 4, $P(m+ 1)$ holds because the predicate makes no claims when $n$ is divisible by 4.

Cases 0, 1, 2: Since $m = 4k + b$ for $b \in {0, 1, 2}$, we know $m + 1 = 4k + c$ for $c \in {1, 2, 3}$ (since $c = b + 1$ to produce $m + 1$). We need to show $P(m+1)$, which means showing that player 1 has a winning strategy for $n = 4k + c$, $c \in {1, 2, 3}$. Player 1 takes $c$ sticks, leaving $4k$ sticks.

For the next turn, Player 2 can remove 1, 2, or 3 sticks, leaving $4k - d$ sticks, $d \in {1, 2, 3}$. This can be simplified to $4(k - 1) + e$ sticks where $e = 4 - d$ since $4k - 4 + (4 - d) = 4k - d = 4(k - 1) + e$. Hence, after Player 2’s turn it will be Player 1’s turn with $4(k - 1) + e$ sticks, $e \in {1, 2, 3}$. We know $4(k - 1) + e < m$ and it is not divisible by 4. So, Player 1 has a winning strategy from $P(m + 1)$ since she has a move to make such that no matter what move player 2 makes, it leads to a number that is not divisible by 4 and is less than $m$, which we know is a position where Player 1 has a winning strategy but strong induction.

Note that $4(k - 1) + e$ is $m - 1$, $m - 2$ or $m - 3$, so we need to know $m \ge 4$ for this to be valid. That’s why we needed three base cases!

Problem Set 4 Comments (Thu, 29 Sep 2016)

The solutions and comments for PS4 are now posted in collab: PDF

You should find your graded assignment as a new PDF attachment with markup on it in collab (if you submitted with teammates, please check with your partners).

The meaning of the scores is the same as for previous problem sets. A score of 6 means you got everything we expected out of this assignment, and 5 means you did well for the most part by had some answers that should have been better. Scores above 6 are reserved for excellent work that is above expectations. (In the gradebook, collab sometimes shows the grades scaled by 100 for some buggy reason. Although receiving a score of 100+ is possible in theory, no one received more than 8 points for this assingment. If you see a score about 100, the meaning is that score divided by 100.)

Satisfiable Formula Challenge (Wed, 28 Sep 2016)

Henry Spece has solved the challenge about proving the length of the longest satisfiable formula!

Challenge 6. (From PS3 Solutions) Provide a full and convincing proof for Problem 11.

The proof is here: PDF

Chicken vs. Egg Challenge (Tue, 27 Sep 2016)

The chicken/egg challenge:

Challenge 3. (From Class 8) Apparently, people were not entirely convinced by my proof sketch in class that the egg came before the chicken. So, we’ll make it a challenge problem to write the best proof that answers the question of “which came first, the chicken or the egg?” (That is, you can either prove the egg came first, or prove the chicken came first). A convincing proof would need to include clear definitions of “chicken” and “egg”, and use inference rules, as well as axioms based on biological assumptions (clearly stated), to make an irrefutable argument supporting your position.

The challenge remains a conundrum, but several promising answers have been received:

• Tony Yang’s Proof that the Chicken Came First (★ ★)
• Milan Bharadwaj’s Proof that Neither Came First (★ ★ ★)
• Jesse Alloy’s Proof that the Egg Came First (★)
• Brian Li’s Proof that the Egg Came First (★)

All of these are interesting answers, worthy of some bonus credit, but none completely close the debate. (I’ll provide my alternative proof in Class 11.)

«« « 1 2 3 4 5 6 7 » »»