tag:blogger.com,1999:blog-78604987921484212662024-03-20T01:18:38.904-07:00Twirling Like a Computer Scientist: My Makeover in CSC165Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-7860498792148421266.post-45004989696575041982014-12-02T20:43:00.000-08:002014-12-07T11:02:01.495-08:00Week 12: A Fun Induction Problem<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Introducing a Fellow Slogger:</span></b></h4>
<br />
Please note that this is <span style="color: magenta; font-weight: bold;">not </span>a problem solving episode (see Week 9). This final week,
the instructors introduce <span style="color: magenta;"><b>simple induction</b></span>.
A fellow slogger gives a nice induction post under Week 12 here.</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<a href="http://pythoncodeshark.wordpress.com/">http://pythoncodeshark.wordpress.com/</a></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br />
<div style="text-align: left;">
You can also find my comments to the following slog under Week 3:</div>
</div>
<div class="MsoNormal">
<br />
<div style="text-align: center;">
<a href="http://sosocompsci.blogspot.ca/">http://sosocompsci.blogspot.ca/</a></div>
<br />
What is
really cool about the induction post is that the slogger talks about how induction is
used in a proof of the following statement: the determinant of any $n \times n$ identity matrix is
$1$. In fact, I am so excited that a fellow slogger uses CSC165 concepts for greater and better
things that I feel compelled to follow the slogger's footsteps. I will also
use <span style="color: magenta;"><b>CSC165 concepts</b></span> as a guide for a problem that is outside the scope of
this course:</div>
<div class="MsoNormal">
<br />
<h4>
<b><span style="font-size: large;">The Fun Problem:</span></b></h4>
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Problem</span></b>: Is the following statement true: the determinant of any upper
triangular matrix is<br />
the product of its
diagonal entries?</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The truth is I have no clue. In my Problem Solving Episode under Week 9
(under the heading Step 1: Understand the Problem), I work out examples of an
idea that I do not fully understand to gain intuition. We should work out examples for this problem
too.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
First we know that an <b><span style="color: magenta;">upper triangular matrix</span></b> is a $n \times n$ matrix $A$ that is
defined by:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$A_{ij} = \begin{cases} a_{ij}
& i \leq j \\ 0 & i > j \end{cases}$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Then the following matrices satisfy the definition nicely:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<div style="text-align: center;">
$\begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}, \begin{bmatrix}
4 & 5 & 6 \\ 0 & 7 & 8 \\ 0 & 0 & 9 \end{bmatrix}$.</div>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Secondly, let $A$ be a $n \times n$ matrix and $F$ be a field. Then the <span style="background-color: white;"><span style="color: magenta;"><b>determinant</b></span></span> is a function $det:
M_{n \times n}(F) \to F$ that is defined by:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(A) = \begin{cases}
A_{ij} & n = 1 \\ \sum\limits_{j= 1}^n (-1)^{i + j} A_{ij} det(\bar{A_{ij}})
& n \geq 2 \end{cases}$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
There is some fancy notation here but it is not difficult to
understand. For simplicity sakes, think
of $F$ as the set of real numbers. Also,
the strange bar on top of $A_{ij}$ just means $A$ with both row $i$ and column $j$ removed. We see that the determinant is
recursively defined. This may be useful
later.<br />
<br />
<div class="MsoNormal">
To find the
determinant of the above matrices, use the definition. For the $2 \times 2$ matrix, we have:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(\begin{bmatrix}
1 & 2 \\ 0 & 3 \end{bmatrix}) = (-1)^{1 + 1}(1)(3) + (-1)^{1 + 2}(0) =
3$.</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
For the $3 \times 3$ matrix, we have:</div>
<div style="text-align: left;">
<br /></div>
</div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(\begin{bmatrix} 4
& 5 & 6 \\ 0 & 7 & 8 \\ 0 & 0 & 9\end{bmatrix}) = $</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$(-1)^{1 + 1}(4)det(\begin{bmatrix}
7 & 8 \\ 0 & 9 \end{bmatrix}) + (-1)^{1 + 2}(5)det(\begin{bmatrix}
0 & 8 \\ 0 & 9 \end{bmatrix}) + (-1)^{1 + 3}(6)det(\begin{bmatrix}
0 & 7 \\ 0 & 0 \end{bmatrix}) = $</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$(4)(-1)^{1 +
1}(7)(8) + (-1)(5)(-1)^{1 + 1}(0)(9) + (5)(-1)^{1 + 1}(0)(0) =$</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$(4)(7)(8) + 0 + 0 =
224$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
It seems like the statement is true and that we should try
proving it. Something interesting in the calculation is that the determinant of a matrix with a column of $0$s is $0$. Again, this may be useful later.<br />
<br />
<h4>
<b><span style="font-size: large;">The Attempt at a Solution:</span></b></h4>
<div>
<div class="MsoNormal">
<div class="MsoNormal">
<br />
How should
we prove the statement? A direct proof
comes to mind but remember that the determinant is recursively defined. This makes it difficult to work with unless we
know the determinant of a previous recursive case. Proof by simple induction sounds attractive here. The induction hypothesis may give us the
determinant of a previous recursive case.
Let us try it.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Since a $0
\times 0$ matrix is undefined, then we show that $\forall n \in N, n \geq 1
\implies$ the determinant of an upper triangular $n \times n$ matrix is
the product of its diagonal entries. By
<span style="color: magenta;"><b>simple induction</b></span> on $n$, we show that this statement is true. The CSC165 proof
structure for induction is our guide.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
For the
<b><span style="color: magenta;">base case</span></b>, assume that $n = 1$. Let $A$
be a $1 \times 1$ upper triangular matrix.
By the definition of the determinant, then $det(A) = A_{ij}$. Since $A_{ij}$ is the only diagonal entry,
then statement is true for $n = 1$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
For the
<span style="color: magenta;"><b>induction step</b></span>, assume that $n \in N, n \geq 1$ and that the statement is true for
$n$. That will be our <span style="color: magenta;"><b>induction
hypothesis</b></span>. We need to show that the
statement is true for $n + 1$. Let $A$
be a $(n + 1) \times (n + 1)$ upper triangular matrix. By the definition of the determinant, we have
that </div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(A) = \sum\limits_{j = 1}^{n + 1} (-1)^{1 + j}A_{1j}
det(\bar{A_{1j}})$.</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div class="MsoNormal">
Remember
this observation: the determinant of a matrix with a column of $0$s is
$0$? Turns out, that is because a square
matrix with a column of $0$s is not invertible and some fancy theorem tells us
that the determinant of such a matrix is $0$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Luckily, we
make the following observation:</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(A) = \sum\limits_{j
= 1}^{n + 1} (-1)^{1 + j} A_{1j} det(\bar{A_{1j}}) = (-1) ^{1 + 1}A_{11} det(\bar{A_{11}}) + \sum\limits_{j = 2}^{n + 1} (-1)^{1 +
j}A_{1j} det(\bar{A_{1j}})$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Notice that the matrix $\bar{A_{1j}}$ is $A$ without row $1$
and without a column $j \geq 2$. Minus the first element, column $1$ of
$A$ is a column of $0$s So the matrix $\bar{A_{1j}}$
also has a column of $0$s. Thus, $det(\bar{A_{1j}})
= 0$ and</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(A) = (-1) ^{1 +
1}A_{11} det(\bar{A_{11}}) + \sum\limits_{j
= 2}^{n + 1} (-1)^{1 + j}A_{1j} det(\bar{A_{1j}}) = (-1) ^{1 + 1}A_{11} det(\bar{A_{11}})$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The matrix $\bar{A_{11}}$
has both row $1$ and column $1$ removed but it is still an upper triangular $n \times n$ matrix. By the induction hypothesis, then $det(\bar{A_{11}})$
is the product of its diagonal entries. Notice
that the diagonal entries of $det(\bar{A_{11}})$ are the diagonal entries of $A$ without
$A_{11}$. Since </div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$det(A) = (-1) ^{1 +
1}A_{11} det(\bar{A_{11}}) = A_{11} det(\bar{A_{11}})$,</div>
<div class="MsoNormal">
<br /></div>
<br />
<div class="MsoNormal">
then we have $det(A)$ as the product of its diagonal entries. Since $A$ is a $(n + 1)
\times (n + 1)$ upper triangular matrix, then the statement is true for $n +
1$. By simple induction, then $\forall n
\in N, n \geq 1 \implies$ the statement is true for $n$. So that is my attempt is at this fun problem.</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-35699866075788008992014-11-26T17:12:00.004-08:002014-12-03T21:42:10.002-08:00Week 11: Harder Time Complexity Problems<div class="MsoNormal">
There is no class this week so for fun, we go over a few harder time complexity problems. Consider the
sequences $f(n) = n^4 - 165n^3 - 240n^2 - 265n - 373$ and $g(n) = 157n^3 + 257n^2 + 337n + 457$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Problem 1</span></b>: Show that $f \notin O(g)$ without using any limit definitions.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Problem 2</span></b>: Show that $f \in
\Omega (g)$ without using any limit definitions.<br />
<br />
<h4>
<b><span style="font-size: large;">Problem 1 Tips:</span></b></h4>
<div>
<br /></div>
<div>
<div class="MsoNormal">
The definition
that we have is $f \in O(g)$, which is defined as:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$\exists c \in R^+,
\exists B \in N, ( \forall n \in N, n \geq B \implies f(n) \leq g(n))$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Thus, its negation is:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$\forall c \in R^+,
\forall B \in N, ( \exists n \in N, n \geq B \wedge f(n) > g(n))$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
We must choose $n$.
Using the recommended strategies of my instructors, we get:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n^4 - 165n^3 -
240n^2 - 265n - 373 \geq$</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n^4 - 1043n^3$</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$???$</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$c(1208n^3) \geq$</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$c(157n^3 + 257n^2 + 337n
+ 457)$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The $???$ part indicates the area where the strategies of
my instructors do not cover. So I think hard here (like really hard) and I come up with this. All we must do is find a $n$ that satisfies the inequality $n^4 - 1043n^3
> c(1208n^3)$. We have:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n^4 - 1043n^3 >
c(1208n^3)$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Move $ -1043n^3$ on the left side to the right and factor
out $n^3$ from the resulting right: </div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n^4 > n^3(c1208 +
1043)$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
It looks like we will choose $n > 0$. That way, we can divide both sides by $n^3$:</div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n > c1208 + 1043$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
Our choice of $n$ is then $max(\lceil c1208 + 1043 \rceil +
1, B)$.</div>
<div class="MsoNormal">
<br /></div>
</div>
<h4>
<b><span style="font-size: large;">Problem 2 Tips:</span></b></h4>
<br />
<div>
<div class="MsoNormal">
Likewise,
we show that $f \in \Omega (g)$, which is defined as:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$\exists c \in R^+,
\exists B \in N, ( \forall n \in N, n \geq B \implies f(n) \geq g(n))$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
We must choose $c, B$.
We have a similar inequality to problem 1:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n^4 - 1043n^3 \geq
1208n^3$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Again, we choose $B >0$ so that we can divide both sides by $n^3$. Then add both sides by $1043$ to yield:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$n \geq 2051$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Of course, to choose $B = 2051$, we must choose $c = 1$. Otherwise, the first step is irreversible.</div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-72240986524630787232014-11-18T19:44:00.001-08:002014-12-03T01:30:22.571-08:00Week 10: Computability and Confusion<div class="MsoNormal">
Computability
is the first topic in CSC165 that is new to me. It is both interesting and somewhat confusing. Unfortunately, any confusion is undesirable at this point in the course. After thinking about my confusion, I realize that the halting problem is the culprit. Why is this?</div>
<div class="MsoNormal">
<br /></div>
<h4>
<b><span style="font-size: large;">Elementary Definitions and Theorems:</span></b></h4>
<div class="MsoNormal">
<o:p><br /></o:p></div>
<div class="MsoNormal">
First, the stuff that makes sense. Consider a
set of inputs $I$ and a set of outputs $O$.
Computability begins with three relatively simple definitions and a single
theorem.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Definition 1</span></b>: Let $f:
I \to O$ be a function. Then $f$ is well-defined $\iff$ for each $x \in I$,
there is a unique $y \in O$ such that $f(x) = y$.</div>
<div class="MsoNormal">
<br />
<br /></div>
<div class="MsoNormal">
For remaining definitions and theorems, let $g, h: I \to O$ be well-defined functions.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="color: magenta;"><b>Definition 2</b></span>: Then $g$
is computable $\iff$ there is a
program $P$ such that $\forall x \in I, g(x) = P(x)$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="color: magenta;"><b>Definition 3</b></span>: Then
$g$ reduces to $h \iff g$ can be
implemented with $h$. Below is what $g, h$
look like in Python code if $g$ reduces to $h$.
Let $P$ be the implementation of $g$ and $Q$ be the implementation of $h$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def P():<br />
"""An implementation of the function f."""</div>
<div class="MsoNormal">
Q():</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="color: magenta;"><b>Theorem 1</b></span>: Let $g$
reduce to $h$. Then $h$ is computable
$\implies g$ is computable.<br />
<br />
<h4>
<b><span style="font-size: large;">The Confusing Part:</span></b></h4>
<div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Now, the stuff that is not so clear. The function
halt(f, i) tells us if a function $f$ with an input $i$ halts. The halting function is not
computable. The proof of this statement starts simple
enough: Assume to the contrary that
there is an implementation of halt(f, i) that works for all functions and
inputs. Then consider the function
what_is_love(f):</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def
what_is_love(f):</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if
halt(f, f):</div>
<div class="MsoNormal">
while
True:</div>
<div class="MsoNormal">
print(“Look
to the skies.”)</div>
<div class="MsoNormal">
else:</div>
<div class="MsoNormal">
print(“Nobody
knows.”)</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The <span style="color: magenta;"><b>“while True”</b></span> statement <span style="background-color: white;">is the incomprehensible part</span> of
the proof. I ask in lecture why it is
there. The instructor lets a classmate several rows ahead of
me answer my question. The explanation
takes nearly half a minute. I did not
get any of it. Apparently, the
instructor did not have any problems with the explanation nor did my other
classmates.</div>
</div>
<div>
<b><span style="font-size: large;"><br /></span></b></div>
<div>
<h4>
<b><span style="font-size: large;">The Comprehending Part:</span></b></h4>
</div>
<div>
<b><span style="font-size: large;"><br /></span></b></div>
<div>
<div class="MsoNormal">
It takes
several days for me to understand why the “while True” statement is there. Eventually, I look at what we are
proving. We assume that
there is an implementation of halt(f, i) that works for <b><span style="color: magenta;">all</span></b> functions and inputs. To
disprove, we only have to show that <b><span style="color: magenta;">one</span></b>
function and input does not work for halt(f, i). This is a classic existential proof. We are free to construct the function what_is_love(f) however we want to so long as it disproves the computability of halt(f, i).</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The “while
True” statement guarantees that what_is_love(what_is_love) goes into an
infinite loop if halt(what_is_love, what_is_love) returns True. Likewise, what_is_love(what_is_love) halts if
halt(what_is_love, what_is_love) returns False.
This is the contradiction and it disproves the computability of halt(f,
i). I wonder why that classmate who answered my question did not explain it like this....</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-82957200697860789452014-11-12T04:50:00.000-08:002014-12-02T20:45:24.422-08:00Week 9: Problem Solving Episode: The Stockbroker's Algorithm<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Context</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
So you graduate from UofT and land your dream job. You work a few years and realize there is this thing called inflation. So you get a brokerage firm to invest your savings.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
To guide its investment decisions, the firm uses the <b><span style="color: magenta;">Stockbroker’s algorithm</span></b>, which inputs a list of real numbers and outputs the max sum over a slice of the list. </div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Unfortunately, the firm uses the following implementation of the algorithm, which is called <b><span style="color: magenta;">John Smith’s Sum</span></b> as nobody knows the name of the employee who wrote it:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def john_smith_sum(L: list) -> int:</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
Return the maximum sum over a slice of L in cubic time.</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
max = front_index = 0</div>
<div class="MsoNormal">
n = len(L)</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while front_index < n:</div>
<div class="MsoNormal">
end_index = front_index</div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
while end_index <= n:</div>
<div class="MsoNormal">
middle_index = front_index</div>
<div class="MsoNormal">
sum = 0</div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
while middle_index < end_index:</div>
<div class="MsoNormal">
sum += L[middle_index]</div>
<div class="MsoNormal">
middle_index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if sum > max:</div>
<div class="MsoNormal">
max = sum</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
end_index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
front_index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
return max</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The runtime of john_smith_sum is cubic. This means that it is agonizingly slow for large inputs and that you will miss out on great investments. So you decide to do the following:</div>
<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: .5in; margin-top: 0in;">
<br /></div>
<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: .5in; margin-top: 0in;">
<b><span style="color: magenta;">Main Problem</span></b>: Come up with an implementation of the Stockbroker’s algorithm with a linear runtime.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
You will then give it to the firm because you are very generous person. First things first; how will you come up with an implementation?</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Step 1: Understand the Problem</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Polya’s <i>How to Solve It</i> recommends understanding the problem first. We have to meet two goals: our implementation should be correct and linear in its runtime. Let us answer the following to see if we know what these goals mean:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
(1) What does an iterative algorithm with a linear runtime look like?</div>
<div class="MsoNormal">
(2) What is the correct output of the Stockbroker’s algorithm for different inputs?</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
For (1), a single loop and a monotone loop index should suffice. For (2), work out examples: Consider the list $[3, 1, 4]$. The max sum is $8$ so that is what our implementation should return. How about $[1, -2, 3, -4, 5, -6]$? Each negative number makes all the preceding partial sums negative so the max sum is $5$ here. What about $[3, -1, 4, -1, 5]$?. We may be tempted to look only at positive numbers but we see that adding $-1$ after $3$ and $4$ still keeps the partial sum positive. Hence, the max sum is $10$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Step 2: Devise a Plan</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span class="apple-converted-space"><span style="background: white; color: #545454;"> </span></span>“No plan survives contact with the enemy” – The Desert Fox</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
There are a couple of approaches to this problem. One is to assume an arbitrary list of real numbers as the input. We write a single implementation for that input. However, this is a little hard as we have to juggle negative and non-negative numbers simultaneously.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
A second approach is to implement by cases through the lists in (1). Then combine them into a single implementation. However, we are lazy and we do not want to write multiple unrelated implementations.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Check out this approach. We write a single implementation that works for a simple input and then extend it to all inputs. This may be the best approach as there appears to be only a few cases. Hopefully, this assumption is correct. Then this approach is our plan.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Step 3: Carry out the Plan</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
This is the part where we execute the plan so try not to lose your head. Of the three lists in (1), the easiest one to write an implementation for is $[3, 1, 4]$ as all the elements are non-negative. By delegating a variable to store the max sum, then we have version one of our implementation:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">My Sum Version 1</span></b>:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def my_sum(L: list) -> int:</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
Return the maximum sum over a slice of L in linear time.</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
n = len(L)</div>
<div class="MsoNormal">
sum = max = index = 0</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while index < n:</div>
<div class="MsoNormal">
element = L[index]</div>
<div class="MsoNormal">
sum += element </div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if max < sum:</div>
<div class="MsoNormal">
max = sum</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
return max</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
This version features a single loop with a monotone increasing loop index so we satisfy the linear runtime component. Unfortunately, this version only works if all the elements are positive. It falters for lists of the following nature: $[1, -2, 3, -4, 5, -6]$. So we break down each iteration into two cases: one for negative and one for nonnegative. This leads to version two of our implementation:</div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
<b><span style="color: magenta;">My Sum Version 2</span></b>:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def my_sum(L: list) -> int:</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
Return the maximum sum over a slice of L in linear time.</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
n = len(L)</div>
<div class="MsoNormal">
sum = max = index = 0</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while index < n:</div>
<div class="MsoNormal">
element = L[index]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if element >= 0:</div>
<div class="MsoNormal">
sum += element</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
else:</div>
<div class="MsoNormal">
sum = 0 </div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if max < sum:</div>
<div class="MsoNormal">
max = sum</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
return max</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
This version resets the sum once it iterates over a negative number. The linear runtime is still preserved. However, consider the following list: $[3, -1, 4, -1, 5]$. The element $-1$ is not enough to reduce the sum to below zero. Then we should not reset the sum unless it is below zero. This also allows us to eliminate some code: the negative and non-negative checks and the memoization step where L[index] is assigned to the variable element:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">My Sum Version 3</span></b>:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
def my_sum(L: list) -> int:</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
Return the maximum sum over a slice of L in linear time.</div>
<div class="MsoNormal">
"""</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
n = len(L)</div>
<div class="MsoNormal">
sum = max = index = 0</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while index < n:</div>
<div class="MsoNormal">
sum += L[index]</div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
if sum < 0:</div>
<div class="MsoNormal">
sum = 0 </div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if max < sum:</div>
<div class="MsoNormal">
max = sum</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
index += 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
return max</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Step 4: Look Back</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Version three</span></b> is our final version but our obsessive tendencies force us to double check its correctness and runtime. Consider the test code below. It checks that my_sum and john_smith_sum have matching outputs for each input.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Verify this by running the code from the link on Python. It contains the code for john_smith sum, the final version of my_sum and the test cases:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<a href="https://drive.google.com/file/d/0BxsBGbDy-BSGOEotZWRpRHFWcW8/view?usp=sharing">https://drive.google.com/file/d/0BxsBGbDy-BSGOEotZWRpRHFWcW8/view?usp=sharing</a></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b><span style="color: magenta;">Test Cases:</span></b></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
if __name__ == "__main__":</div>
<div class="MsoNormal">
L = [[3, 1, 4], [3, -1, 4, 1], [3, -1, 4, -1, 5], [3, 1, -4, 1, -5, -9],</div>
<div class="MsoNormal">
[-3, -1, -4], [1, -2, 3, -4, 5, -6], [3, -5, 7, 1, -2, 0, 3, -2, 1]]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
for x in L:</div>
<div class="MsoNormal">
assert john_smith_sum(x) == my_sum(x)</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Likewise for the runtime, the loop executes $7$ steps for each iteration in the worst case so that is $7n$ steps in total. Add the steps outside the loop plus the loop guard and we have $7n + 4$ as the runtime, which is linear. Hence, we have a credible implementation of the Stockbroker's algorithm. </div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com2tag:blogger.com,1999:blog-7860498792148421266.post-91722567731178038472014-11-04T20:13:00.000-08:002014-12-15T06:22:53.164-08:00Week 8: Time Complexity<div class="MsoNormal">
<div class="MsoNormal">
The post in Week 7 talks about algorithms being linear, quadratic or cubic. Such descriptions are neither precise nor fancy enough keep computer scientists satisfied. So we have this thing called the <b><span style="color: magenta;">time complexity </span></b>of an algorithm, which describes the growth in runtime over the growth in input size.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<b><span style="font-size: large;">Here Comes the Notation!</span></b></h4>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Time complexity is described in <span style="color: magenta;"><b>Big O</b></span>. It looks something like this. Let $f: N \to R^{\geq 0}$ be a sequence that describes the runtime of an algorithm $P$ and $g: N \to R^{\geq 0}$ be a sequence that describes an arbitrary runtime (i.e. linear, quadratic, cubic, etc). If we say that $f \in O(g)$, then we mean that:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\exists c \in R^+, \exists B \in N, (\forall n \in N, n \geq B \implies f(n) \leq cg(n))\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Intuitively, what these little symbols say is that as the input becomes arbitrarily large, then the runtime of $P$ performs better than or as well as $g$. Likewise, if we say that $f \in \Omega (g)$, then we mean that:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\exists c \in R^+, \exists B \in N, (\forall n \in N, n \geq B \implies f(n) \geq cg(n))\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Again, this is just a fancy way of saying that as the input becomes arbitrarily large, then the runtime of $P$ performs worse than or as well as $g$.<br />
<br />
<h4>
<strong><span style="font-size: large;">A Fun Problem</span></strong></h4>
<br /></div>
<b style="mso-bidi-font-weight: normal;"> </b><span style="mso-ansi-language: EN-CA;">Let $f: N \to R^{\geq 0}$ be a polynomial sequence of degree $m$ and </span>$g: N \to R^{\geq 0}$ be a polynomial sequence of <span style="mso-tab-count: 1;"></span>degree $n$ with $m, n \in R$.<span style="mso-spacerun: yes;"> </span>Find all $m, n$ such that $f \in O(g)$ and $(f \times g) \in \Omega(f)$.</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-53950058357664348272014-10-27T10:27:00.002-07:002014-12-03T01:39:24.093-08:00Week 7: Nice Mathematical Toys in Algorithm Analysis<div class="MsoNormal">
Constant,
linear, quadratic, logarithmic or linearithmic are terms that vaguely describe the worst case runtime of algorithms in CSC148 but they are not precise enough in CSC165. We need the exact number of steps. This calls for
some nice mathematical toys, which we introduce with the following algorithm:</div>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
<div class="MsoNormal">
def mystery_sort(L: list):</div>
<div class="MsoNormal">
“””</div>
<div class="MsoNormal">
Sort the elements of L in mysterious
order.</div>
<div class="MsoNormal">
“”” </div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
n = len(L)</div>
<div class="MsoNormal">
outer_index = 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while outer_index < n:</div>
<div class="MsoNormal">
value = L[outer_index]</div>
<div class="MsoNormal">
inner_index = outer_index</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
while inner_index > 0 and
A[inner_index – 1] < value:</div>
<div class="MsoNormal">
A[inner_index] = A[inner_index
– 1]</div>
<div class="MsoNormal">
inner_index = inner_index – 1</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
A[inner_index]
= value</div>
<div class="MsoNormal">
outer_index = outer_index + 1</div>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Since mystery_sort has a nested loop with monotone loop indexes, then its worst-case runtime is quadratic. What is less obvious is the exact number of
steps that it takes for mystery_sort to run in the worst case. Our procedure to count mystery_sort is as
follows:<br />
<br />
(1) Assume that each line represents one step to make the analysis easier.<br />
(2) Count from the inner loop to the outer loop.<br />
(3) Add up the steps that are outside
the outer loop.<br />
<br />
So assume (1). Then do (2) and (3).<br />
<h4>
<b><span style="font-size: large;">Inner Loop</span></b></h4>
<br /></div>
<div class="MsoNormal">
To count the
steps of the inner loop, our first mathematical toy comes into play: <b><span style="color: magenta;">abstraction</span></b>. It helps us determine the number of times that
the inner loop executes. Observe that
the inner loop depends on the outer_index.
However, the outer_index is not concrete since it changes each time the
outer loop executes. So we must think
abstractly; use an arbitrary integer $i$ to represent the outer_index. Then $i$ becomes the number of times
that the inner loop executes. Now the easy
part: the inner loop performs three steps for each iteration. Since the inner loop executes $i$ times, then
the number of steps of the inner loop is $3i$.</div>
<br />
<h4>
<b><span style="font-size: large;">Outer Loop</span></b></h4>
<br />
<div class="MsoNormal">
In addition to the number of steps of the inner loop, we
have the following steps inside each outer loop:<br />
<br />
<div class="MsoNormal">
(1) while
outer_index < n</div>
<div class="MsoNormal">
(2) value
= L[outer_index]</div>
<div class="MsoNormal">
(3) inner_index
= outer_index</div>
<div class="MsoNormal">
(4) loop
guard of the inner loop</div>
<div class="MsoNormal">
(5) A[inner_index]
= value</div>
<div class="MsoNormal">
(6) outer_index
= outer_index + 1</div>
<br />
<div class="MsoNormal">
This is $6$ steps in total.
Add it to the steps of the inner loop and you see that each iteration of
the outer loop executes $3i + 5$ steps.
We still have to add up the steps for each iteration so here our second
mathematical toy comes into play: <b><span style="color: magenta;">summation</span></b>. Since the outer loop runs $n - 1$ times, then
the total steps of the outer loop is the following summation:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\sum_{i = 1}^{n -
1} (3i + 6)\].</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
To find the
sum of this series, our mathematical final toy comes and it is <b><span style="color: magenta;">Euler’s trick</span></b>. This is a technique for finding the sum of an arithmetic series. First decompose the
summation:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\sum_{i = 1}^{n -
1} (3i + 6) = 3 \sum_{i = 1}^{n - 1} i + \sum_{i = 1}^{n - 1} 6\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Then perform the following calculation:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\sum_{i = 1}^{n -
1} i = 1 + 2 + 3 + … + (n - 3) + (n - 2) + (n - 1) =\]</div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\frac{1}{2}(1 + 2 +
3 + … + (n - 3) + (n - 2) + (n - 1) + \]</div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[(n - 1) + (n - 2) +
(n - 3) + … + 3 + 2 + 1) =\]</div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\frac{n(n - 1)}{2}
= \frac{n^2 - n}{2}\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Substitute back into the series and we get the number of steps that outer loop executes:<br />
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\frac{3n^2 - 3n + 12n - 12}{2} = \]</div>
<div align="center" class="MsoNormal" style="text-align: center;">
\[\frac{3n^2 - 9n - 12}{2}\]<br />
<div class="MsoNormal">
<div style="text-align: left;">
<h4>
<b><span style="font-size: large;">Outside Both Loops</span></b></h4>
</div>
<div style="text-align: left;">
<br /></div>
</div>
<div class="MsoNormal" style="text-align: left;">
There are still the following steps to
consider:</div>
<div class="MsoNormal" style="text-align: left;">
<br /></div>
<div class="MsoNormal" style="text-align: left; text-indent: 0.5in;">
(1) n = len(L)</div>
<div class="MsoNormal" style="text-align: left; text-indent: 0.5in;">
(2) outer_index = 1</div>
<div class="MsoNormal" style="text-align: left; text-indent: 0.5in;">
(3) loop guard of the outer loop</div>
<div class="MsoNormal" style="text-align: left;">
<br /></div>
<div class="MsoNormal" style="text-align: left;">
This is $3$ steps so the total number of steps that the algorithm
performs is:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="text-align: left;">
</div>
<div align="center" class="MsoNormal">
\[\frac{3n^2 - 9n - 6}{2}\]</div>
</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-10376547454996739172014-10-20T07:20:00.002-07:002014-12-03T01:02:07.857-08:00Week 6: $\epsilon - \delta$ Definition of Limit<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
As someone who has no prior experience with the $\epsilon - \delta$ definition of limit, I
will teach myself about them with the help of my favourite math textbook and some creativity. This is what I gleaned so far.<br />
<br /></div>
<div class="MsoNormal">
In high school, we calculate limits. In university, we like to think that we are <b><span style="color: magenta;">sophisticated thinkers</span></b>. Knowing how to calculate is not enough for us. We must know why our calculation is correct. Then we need a definition to work with. This is where the the $\epsilon - \delta$ definition
of limit comes in:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Let $f:X \to R$ be a function, $L \in R$, $a \in X$ and $X \subseteq R$. Then<br />
<br />
<div align="center" class="MsoNormal" style="text-align: center;">
\[\lim_{x \to a} f(x)
= L \iff\]</div>
</div>
<div class="MsoNormal" style="text-align: center;">
\[\forall \epsilon \in R^+, \exists \delta \in R^+, (\forall x \in R, |x - a| < \delta \implies |f(x) - L| < \epsilon).\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
After digesting this definition, we can prove or disprove
statements about the limits of functions.</div>
<div class="MsoNormal" style="text-indent: .5in;">
For example, consider the following statement:</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
\[\lim_{x \to 2} x^2 = 4\]</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<div class="MsoNormal" style="text-align: justify;">
By substituting two into $x$, we
discover that this statement should be true.
To show that our hunch is correct, we plug in $a = 2$ and $L = 4$ into
the $\epsilon - \delta$ definition and prove it:</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
\[\forall \epsilon \in R^+,
\exists \delta \in R^+, (\forall x \in R, |x - 2| < \delta \implies |x^2 – 4|
< \epsilon)\]</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
Our value for $\epsilon$ will be
arbitrary but our value for $\delta$ must be concrete since $\epsilon$ has a
$\forall$ quantifier but $\delta$ has a $\exists$ quantifier. The hard part is choosing $\delta$. How do we do it?</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
<h4>
<b><span style="font-size: large;">Where to Start</span></b></h4>
</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
Think
of $\epsilon$ as a distance from $L$ on the vertical axis and $\delta$ as a
distance from $2$ on the horizontal axis.
Once the distance of $x$ from $2$ is less than $\delta$ on the
horizontal, then the $\epsilon – \delta $ definition of limit guarantees
that the distance of $x^2$ from $4$ is less than $\epsilon$ on the vertical. Hence, our choice of $\delta$ must satisfy
the definition for all $\epsilon$. To
achieve this, we express $\delta$ in terms of $\epsilon$, which is done by working backwards from the definition.</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
<h4>
<b><span style="font-size: large;">How to Work Backwards</span></b></h4>
</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
Since the definition is an implication, then working backwards begins with the
consequent:</div>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$|x^2 - 4| <
\epsilon$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Since we operate in $R$, then we can manipulate
the left side of the inequality:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$|x + 2||x - 2| =
|x^2 - 4| < \epsilon$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
</div>
<div class="MsoNormal">
We see that the $|x - 2|$ in $|x + 2||x - 2| < \epsilon$ will be useful in getting the antecedent of the definition, which is $|x - 2| < \delta$. However, there is still a bit of baggage to unload.<br />
<br />
<h4>
<b><span style="font-size: large;">The Creative Step</span></b></h4>
<br />
<div class="MsoNormal">
Since we choose
our $\delta$, then we can give it an upper bound. For simplicity, we choose $1$ as an upper
bound for $\delta$. So if $|x - 2| < d$, then $|x - 2| < 1$.<br />
<br />
From $|x - 2| < 1$, the absolute value definition gives $-1 < x - 2 <
1$. By adding $4$ to all sides of the
inequality, then we have $3 < x + 2 < 5$.
Use the absolute value definition again, which gives us $|x + 2| < 5$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="text-indent: .5in;">
Now we can unload $|x + 2|$ from $|x
+ 2||x - 2| < \epsilon$. Since $|x + 2|
< 5$, then $|x + 2||x - 2| < 5|x - 2|$.
Then $5|x - 2| < e$ is equivalent to $|x - 2| < \frac{\epsilon}{5}$.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<h4>
<o:p><b><span style="font-size: large;">Endgame</span></b></o:p></h4>
<o:p><b><br /></b></o:p></div>
<div class="MsoNormal" style="text-indent: .5in;">
We can now chose $\delta$. If $|x - 2| < \frac{\epsilon}{5}$ is true,
then its equivalent statement $5|x - 2| < e$ guarantees that $|x - 2||x + 2|
= |x^2 - 4| < \epsilon$ since $|x - 2| < 5$. Yet we chose $1$ as an upper bound for $\delta$. So if $\frac{\epsilon}{5}>1$,
then $\delta = 1$. Hence our choice of $\delta$
is $min(1, \frac{\epsilon}{5})$. The
proof follows naturally from the scratch work so it will be omitted.</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-6926192489409028592014-10-13T20:31:00.001-07:002014-11-22T17:02:03.373-08:00Week 5: The Pros and Pitfalls of CSC165 Proofs<style>
body {
font-size: 14px;
}
</style><br />
<div class="MsoNormal" style="text-indent: .5in;">
Many of my classmates have
their first exposure to proofs in CSC165 so this class caters towards them. I think this is fair but I am sure that at least some of my classmates did proofs in
other classes. I become used to the essay-like
proofs of my previous proof-oriented math classes: MAT138 (Intro to Proofs) and MAT240 (Algebra I). So when the first proofs in
CSC165 presented themselves in mainly logical sentences instead of mainly English sentences, I
was pleasantly surprised. Their aesthetic appearance reminds me of
programming code. Why are the proofs in CSC165 presented this way?</div>
<div class="MsoNormal">
<br />
<h4>
<b><span style="font-size: large;">The Pros</span></b></h4>
<br /></div>
<div class="MsoNormal" style="text-indent: .5in;">
After thinking about it for a few days,
I arrive at two justifications. Proofs can seem
overwhelming to those of us who are new it; this certainly was the case for
me. Presenting the proofs in the style of programming code can make it
less intimidating to those us who are comfortable with programming.
In addition, the use of mainly logical sentences instead of mainly
English sentences can make it easier to catch logic errors.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsMT8dNAxjAkzOmlL0PwliA5Xz8l7UMbyz-P9PUwocdoqS3NLntrwUyANtujvTlz0x4dU8xWO4Ni6kz4STVZtRFzRMKlsjtSg8I_uskM_SbJ_CQd3s4v9TaqX5qipZrpeZ_1-ZC5twPww/s1600/Up.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsMT8dNAxjAkzOmlL0PwliA5Xz8l7UMbyz-P9PUwocdoqS3NLntrwUyANtujvTlz0x4dU8xWO4Ni6kz4STVZtRFzRMKlsjtSg8I_uskM_SbJ_CQd3s4v9TaqX5qipZrpeZ_1-ZC5twPww/s1600/Up.jpg" height="246" width="400" /></a></div>
</div>
<div class="MsoNormal" style="text-indent: .5in;">
<br />
<br />
<div class="MsoNormal" style="-webkit-text-stroke-width: 0px; color: black; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px;">
<h4>
<b><span style="font-size: large;">The Pitfalls</span></b></h4>
<div style="margin: 0px;">
<br /></div>
</div>
<br />
However, there is a downside to the CSC165 way of writing the proofs. Where is the intuition? There is emphasis on
annotating the logical sentences correctly but not much focus on the how to prove a claim. How do we decide between a direct proof or proof by
contradiction if we are looking for a sound and efficient way to prove? Do we memorize the cases for when one proof strategy works
better than another? Experience tells me that this is a bad idea because
we will be at a loss if we see a new, unfamiliar claim to prove.<br />
<br /></div>
<div class="MsoNormal" style="text-indent: .5in;">
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqF7XXdJhPVXv5EMbB3Ixu19QsIRFIgpkfCVVaaiOhhFd9-PBA_EElA1mskcNgyNIBuLK9wixzEMtamOgWbI9hg7XJitAbI3zRVYpfVYh6Jp9b3bQq1D6mhltnPzRiGo0HhwiaiKYbBbE/s1600/Down.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqF7XXdJhPVXv5EMbB3Ixu19QsIRFIgpkfCVVaaiOhhFd9-PBA_EElA1mskcNgyNIBuLK9wixzEMtamOgWbI9hg7XJitAbI3zRVYpfVYh6Jp9b3bQq1D6mhltnPzRiGo0HhwiaiKYbBbE/s1600/Down.jpg" height="185" width="400" /></a></div>
<br />
<br /></div>
<div class="MsoNormal">
</div>
<div class="MsoNormal" style="text-indent: .5in;">
So what is the best way to gain
intuition? My opinion is to try things out. We should think way
about different ways to prove a claim. We should think how the
mathematical structures in a claim make a specific proof strategy efficient or
inefficient. Unfortunately, the focus on annotating the logical sentences
correctly and making the aesthetics of a proof comparable to programming code is contrary to the goal of gaining intuition. If CSC165
can focus more on the strategies for approaching proofs, then we might benefit
more from the logical rigour through which the course presents its proofs.<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com2tag:blogger.com,1999:blog-7860498792148421266.post-752940995732938052014-10-03T11:57:00.001-07:002014-12-09T18:35:18.746-08:00Week 4: Logical Cameleons<style>
body {
font-size: 14px;
}
</style><br />
<div class="MsoNormalCxSpFirst" style="text-align: justify; text-indent: .5in;">
<span lang="EN-CA">Suppose that you walk into the forest today
and see a purple chameleon. Then next
week, you walk by into same forest and see an orange chameleon. The orange chameleon looks similar to the purple chameleon except for its colour. Surely
they are not the same chameleon, right?<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzGncdvhWZZcEQdtEa3nPIgHL0LmKu5vjSCjWO6MgqPdO5SK7o7j8XDHk4TdnMcy4s0V0FWKjRLuehrI800Qd7lGRACVxK2ZMdLkdbSomfzyJ1QYvJ7bYBVu8DiVTicKjwjc-R-61Bv78/s1600/2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzGncdvhWZZcEQdtEa3nPIgHL0LmKu5vjSCjWO6MgqPdO5SK7o7j8XDHk4TdnMcy4s0V0FWKjRLuehrI800Qd7lGRACVxK2ZMdLkdbSomfzyJ1QYvJ7bYBVu8DiVTicKjwjc-R-61Bv78/s1600/2.jpg" height="238" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
A Purple Panther Chameleon</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5_c2VJdMNxtyaEOhQKRjMXhWprojTkIkwTZnGTXGFtW6FPSc4MEy_ZJ2_J6noEDCeB9DJMfb-n6lK5RTn4QuRj99pqGmjmIX_5Z5_t8uRob__mt2TgWpqgq1srW_BjWZAIK55_QzGH5Q/s1600/1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5_c2VJdMNxtyaEOhQKRjMXhWprojTkIkwTZnGTXGFtW6FPSc4MEy_ZJ2_J6noEDCeB9DJMfb-n6lK5RTn4QuRj99pqGmjmIX_5Z5_t8uRob__mt2TgWpqgq1srW_BjWZAIK55_QzGH5Q/s1600/1.jpg" height="240" width="320" /></a></div>
<div style="text-align: center;">
An Orange Panther Chameleon<br />
<br /></div>
<br />
<span style="text-align: justify;"> </span><span style="text-align: justify;"> </span>In
logic, a similar problem occurs.
Consider these two logical sentences.
Let $D $ be a set and $P, Q$ be sentences:</div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<br /></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<span lang="EN-CA"> (1)
$\exists x \in D, P(x) \implies Q(x)$</span></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<span lang="EN-CA"> (2) $( \forall x \in D, P(x)) \implies ( \exists
x \in D, Q(x))$<o:p></o:p></span></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<br /></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<span lang="EN-CA">These two sentences look very different. Surely they are not the same sentence,
right? <o:p></o:p></span></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<br /></div>
<div class="MsoNormalCxSpMiddle" style="text-align: justify;">
<span lang="EN-CA"> For chameleons, you are out of luck but for logic, we can use logical axioms,
which link together logical statements that are equivalent, to determine if
two logical sentences are saying the same thing. Let
$S$ be a set and $P, Q, R$ be sentences.
These are our axioms:</span><br />
<span lang="EN-CA"><br /></span><b style="color: magenta; text-align: start;">Table of Logical Axioms for Dummies</b><br />
<div class="MsoNormalCxSpFirst">
<div class="MsoNormalCxSpFirst">
<div class="MsoNormalCxSpFirst">
<div class="MsoNormalCxSpFirst">
<div class="MsoNormalCxSpFirst">
<table border="1" cellpadding="0" cellspacing="3" class="MsoTableWeb1">
<tbody>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpFirst" style="mso-yfti-cnfc: 1; text-align: center;">
<span lang="EN-CA">Axiom<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="mso-yfti-cnfc: 1; text-align: center;">
<span lang="EN-CA">Result<o:p></o:p></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Commutativity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$P \vee Q \iff Q \vee P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$P \wedge Q \iff Q \wedge P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Associativity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$P \vee (Q \vee R) \iff (P \vee Q)
\vee R$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$P \wedge (Q \wedge R) \iff (P \wedge
Q) \wedge R$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Distributivity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$P \vee (Q \wedge R) \iff (P \vee
Q) \wedge (P \vee Q)$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$P \wedge (Q \vee R) \iff (P \wedge
Q) \vee (P \wedge Q)$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Implication<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$(P \implies Q) \iff (\neg P \vee
Q)$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Bi-implication<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$(P \iff Q) \iff ((P \implies Q) \wedge
(Q \implies P))$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Identity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$P \wedge (Q \vee \neg Q) \iff P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$P \vee (Q \wedge \neg Q) \iff P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Idempotency<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$P \wedge P \iff P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$P \vee P \iff P$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">DeMorgan’s Law<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA"><br /></span>
<span lang="EN-CA">$\neg (P \wedge Q) \iff \neg P \vee
\neg Q$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\neg (P \vee Q) \iff \neg P \wedge \neg Q$<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Quantifier Commutativity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\forall x \in S, \forall y \in S,
P(x, y) \iff$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\forall y \in S, \forall x \in S,
P(x, y)$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\exists x \in S, \exists y \in S,
P(x, y) \iff$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\exists y \in S, \exists x \in S,
P(x, y)$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 2.05in;" valign="top" width="197"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">Quantifier Distributivity<o:p></o:p></span></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\forall x \in S, P(x) \wedge Q(x)
\iff$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$(\forall x \in S, P(x)) \wedge
(\forall x \in S, Q(x))$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$\exists x \in S, P(x) \vee Q(x)
\iff$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<span lang="EN-CA">$(\exists x \in S, P(x)) \vee
(\exists x \in S, Q(x))$<o:p></o:p></span></div>
<div align="center" class="MsoNormalCxSpMiddle" style="text-align: center;">
<br /></div>
</td>
</tr>
</tbody></table>
</div>
<div class="MsoNormalCxSpFirst">
<br />
Our job is determine if (1) and (2) are equivalent with these axioms. Start with (1):<br />
<br />
<div align="center" class="MsoNormal" style="text-align: center;">
$\exists x \in D,
P(x) \implies Q(x)$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
By the implication axiom, then (1) has the same meaning as this sentence:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$\exists x \in D, \neg
P(x) \vee Q(x)$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
By the quantifier distributivity axiom, then (1) camouflages into this sentence :</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$(\exists x \in D, \neg
P(x)) \vee (\exists x\in D, Q(x))$</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Use the implication axiom again so that (1) looks like this sentence:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$(\forall x \in D, P(x))
\implies (\exists x\in D, Q(x))$</div>
<div class="MsoNormal">
<br /></div>
<br />
<div class="MsoNormal">
We see that sentences (1) and (2) are equivalent even though they look different. Appearances are always deceiving!</div>
<br /></div>
</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-21436726471474089172014-09-26T09:49:00.003-07:002014-11-18T20:17:24.948-08:00Week 3: Fancy Translations from English to Logic<style>
body {
font-size: 14px;
}
</style><br />
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">Last week, we saw that a sentence in a natural
language can be represented in the formal language of logic through predicates,
implications and quantifiers. Yet we can be a little fancier with our representations
by introducing two new members to our zoo of logical symbols. <o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">Suppose that we want to represent these English
statements in logic:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<br /></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">(1) Some student that is in CSC165 is both cool and likes
math.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA"><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a>(2) All
students that are CSC165 are either cool or like math.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Let $U$ be the set of all students.
Let $C(x)$ mean $x$ is in CSC165, $K(x)$ mean $x$ is cool
and $M(x)$ mean $x$ likes math. The conjunction symbol, which
represents the English word “and”, and the disjunction symbol, which represents
the word English “or”, allows the translation of statements (1) and (2) into
logic:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">
(1) $\exists x \in U, C(x)
\implies (K(x) \wedge M(x))$.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">
(2) $\forall x \in U, C(c)
\implies (K(x) \vee M(x))$.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Now let us play a game of I-Spy. See
these statements:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">
(3) $\exists x \in U, C(x)
\implies (K(x) \implies M(x))$.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">
(4)
$\forall x \in U, C(x) \implies (K(x) \implies M(x))$.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">I spy a nuance between
statements (3) and (1) and statements (4) and (2). What is this
nuance? It is the relation between predicates $K(x)$ and
$M(x)$. Replacing either the conjunction or disjunction symbol in a statement with
an implication symbol changes the meaning of that statement. Let us
illustrate the difference between statements (1) and (3) and statements (2) and
(4) with a CSC165 student named Bobby.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">Bobby wants to take up the burden of satisfying
statement (1). Then he needs be cool and he has to like math. Later
Bobby decides that this is too much of a burden for him so he decides to
satisfy statement (3) instead. From last week`s post about implications,
we know that he has a choice of either being uncool or keeping his fondness for
math. Hence, the implication is much more flexible than the conjunction.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<br /></div>
<div align="center" style="margin-bottom: .0001pt; margin: 0in; text-align: center; text-indent: .5in;">
<img src="https://singersworld.wikispaces.com/file/view/cartoon-student.gif/260394988/cartoon-student.gif" /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">Now Bobby wants to take up the burden of satisfying
statement (2). He campaigns to convince all his CSC165 classmates to
either be cool or like math. His classmates rebel and decide to
neither be cool nor like math. Yet Bobby is enterprising. He
decides to satisfy statement (4) instead. Then he needs to get all his
classmates to either be uncool or like math. However, his CSC165
classmates are just as adept at defying Bobby and they decide to be both cool
and dislike math. Poor Bobby! Hence, the implication and
disjunction are different in how they are satisfied but they are the same in
their flexibility.<o:p></o:p></span></div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0tag:blogger.com,1999:blog-7860498792148421266.post-10966561508361725432014-09-19T10:45:00.001-07:002014-12-09T18:34:40.108-08:00Week 2: Introducing... the Logical Zoo<h4>
<span style="font-size: large;">The English Language</span></h4>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA"><br /></span><span lang="EN-CA"> Currently the most
commonly used language in the developed world, the English language has a diverse
vocabulary, a sophisticated grammar system and a rich history that dates back
to the end of the <st1:place w:st="on">Roman Empire</st1:place>. Like all
natural languages, English allows for ambiguity of expression. Take a
look at this sentence:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA"> <o:p></o:p></span></div>
<div align="center" style="margin-bottom: .0001pt; margin: 0in; text-align: center;">
<span lang="EN-CA">Panda mating fails: veterinarian takes over.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Either one of two things is being said:<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA"><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a><o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">(1) The veterinarian will investigate the pandas.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA"><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a><a href="https://www.blogger.com/blogger.g?blogID=7860498792148421266"></a>(2) The
pandas will have to mate with the veterinarian.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Common sense is enough here to determine what
the sentence-writer meant. Yet there are occasions in which both
interpretations are plausible. What if you have a weird friend who said
this to you:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div align="center" style="margin-bottom: .0001pt; margin: 0in; text-align: center; text-indent: .5in;">
<span lang="EN-CA">"People are fashionably
hungry unless they eat Satsumas"<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Your friend means either one of two things:<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">(1) People that are fashionably hungry do not eat Satsumas.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin-bottom: 0in; margin-left: .5in; margin-right: 0in; margin-top: 0in; text-align: justify; text-indent: .5in;">
<span lang="EN-CA">(2) People that do not eat Satsumas are fashionably hungry.<o:p></o:p></span></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA">Neither common sense nor the semantics of the English
language tells us beyond doubt what your friend meant. We need some other
tool.<o:p></o:p></span><br />
<span lang="EN-CA"><br /></span>
<br />
<h4>
<span lang="EN-CA" style="font-size: large;">The Language of Logic</span></h4>
</div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: .0001pt; margin: 0in; text-align: justify;">
<span lang="EN-CA"> Logic can solve the riddle of what your friend said. The language of logic uses symbols to represent meaning just
like English uses the alphabet the represent words. Yet unlike English, logic communicates
everything in terms of whether something is true or false. The following table introduces common logical symbols:</span><br />
<span lang="EN-CA"><br /></span>
<span lang="EN-CA" style="color: magenta;"><b>Table of Logical Symbols for Dummies</b></span></div>
<table border="1" cellpadding="0" cellspacing="3" class="MsoTableWeb1">
<tbody>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="mso-yfti-cnfc: 1; text-align: center;">
Symbol</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="mso-yfti-cnfc: 1; text-align: center;">
Meaning</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div align="center" class="MsoNormal" style="mso-yfti-cnfc: 1; text-align: center;">
Comments</div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$x, y, z, …$<u><o:p></o:p></u></div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
Variable</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A variable represents some real-world object. It can be a person, word, number or any
object you like.</div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$S, T, U, …$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
Set</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A set is an ordered collection of unique objects. It can be a set of people, numbers, cars or
any object you like.</div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$P(x), Q(x), R(x),
…$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
Predicate</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A predicate is a function that maps some variable to the
value “true” or the value “false”.
Think of it as telling the reader whether or not some real-world
object has some attribute.</div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$\exists$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
There Exists</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A quantifier that conveys that at least one member of some
set has some attribute. </div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$\forall$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
For All</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A quantifier that conveys that all members of some set
have some characteristic.</div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$\implies$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
If... then...</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A composition of two sentences. The first is an assumption, which is called the antecedent. The second is a conclusion, called the consequent. Its structure is as follows: if antecedent
is true, then the consequent is true. </div>
</td>
</tr>
<tr>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
$\neg$</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 73.8pt;" valign="top" width="98"><div align="center" class="MsoNormal" style="text-align: center;">
Negation</div>
</td>
<td style="padding: 0in 5.4pt 0in 5.4pt; width: 4.1in;" valign="top" width="394"><div class="MsoNormal">
A negation is an operation that can be applied to a
sentence. A negated sentence is false
if the original sentence is true and vice-versa.</div>
</td>
</tr>
</tbody></table>
<div class="MsoNormal" style="text-align: justify;">
<br /></div>
<div class="MsoNormal" style="text-align: justify;">
These are all the symbols that we
need to translate what your weird friend said from English to logic. There is two mores hoops to jump however. The English word “unless” is translated to
logic as an implication that has a negated antecedent. Additionally, since "unless" is in the middle of the sentence, then the overall sentence is in the form of "then... if...". Now, we can translate the sentence:<br />
<br />
<div class="MsoNormal">
<div class="MsoNormal">
<div class="MsoNormal">
Let $P$ be a set of all people and $H(x), S(x)$ be
predicates with the following definitions:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$H(x): x$ is
fashionably hungry</div>
<div align="center" class="MsoNormal" style="text-align: center;">
$S(x): x$ eats
Satsumas</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Then the sentence “People are fashionably hungry unless they
eat Satsumas” is translated to logic as:</div>
<div class="MsoNormal">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
$\forall x \in P,
\neg S(x) \implies H(x)$</div>
<div class="MsoNormal">
<br /></div>
<br />
<div class="MsoNormal">
The meaning of this logical statement in English is “People
that do not eat Satsumas are fashionably hungry" so therefore, your weird friend
meant (2).</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/07351387970026858321noreply@blogger.com0