SLOG #10: Assignment 3, Induction, and Goodbyes...

Sadly, all good things must come to an end, with this course being no exception. It's really shocking how three months just flew by! And here I am, writing my last SLOG post for the semester. I'll just briefly cover thoughts on assignment #3, and new concepts we learned in class.



Thoughts: Assignment #3
I definitely thought this third assignment was the most challenging. It was a mash-up of all the material we covered up until Week 11. There were proofs involving limits, proofs involving big-Oh, and proofs involving the dreaded halting function. One of the toughest problems was halting. Even after reading page 71 in the course notes we still didn't know what we supposed to do.

Induction
With everything due in the final week before exams, I found myself ignoring week 12 material. We learned a new proof technique called induction. Apparently it's not required to know this topic for the exam since this proof technique will be covered in detail in CSC236. With being said, countability and diagonalization will also not be covered in the final exam.

Exam
All that is left to complete now is the final exam! Despite this course causing me many sleepness nights and extreme anxiety before every assignment deadline, I'm really glad I made it till the end. I'm also definitely grateful for all the help received from profs, TA's, and classmates. Srsly, thank you guys. Since this is the last post, might as well end it with a lovely proof!

SLOG #9: Problem-Solving (Diagonals)

Before I begin my problem-solving episode, I would like to first mention that the problem-solving section on http://zanecsc165.blogspot.ca/ was one of the most detailed (and awesome) post I've read.
But back to my problem...

Understanding the Problem:

I have a rectangular grid made up of m rows and n columns, where m and n are whole numbers. Problem: If I draw a line from the upper left to the lower right corner, how many grid squares does the diagonal line meet?

Given information: values for m and n

Unknown: number of squares the line passes

Devising a Plan:

-          The first thing to do is to try a couple of examples. Consider the following cases:

Ø  m and n are both even

Ø  m and n are both odd

Ø  m = n

Ø  m is even and n is odd (and vice versa)

-          Take note of any patterns that seem to appear

-          Try using a hint from the back of the worksheet

→ What happens in special cases, such as n = m + 1, or when m and n are both even?

→ Are there cases when the problem scales down to some smaller rectangle?

-          From the patterns, try coming up with a universal formula that works for all cases

Carrying out the Plan:

We can see that in this special case (m = n), the number of boxes filled equal m (or n).

What about when m and n are both even?

When m and n are both even, notice that the pair (m, n) can be reduced to a multiple of some numbers. For example: (2, 4) = 2(1, 2), (2, 6) = 2(1, 3), and (8, 4) = 4(2, 1).

This means that whenever we see a pair of number that have a common factor other than 1, we can factor out a number and scale down the rectangle. 

In the case where (m, n) = (3, 9): notice that 3 can be factored out 3(1, 3). 

Now let's consider when one variable is even, and the other is odd: 

In the sets of numbers that I used, none of them could be factored. This means that when devising a formula, we have to take into account large rectangles that cannot be broken down into smaller ones.


Now that I have drawn sample rectangles, there are some prominent re-occurring patterns.
1. Large rectangles can be broken down into smaller ones if the set of numbers have a common factor that is not 1. When we factor out a some integer, let's name it variable k, we have k number of small rectangles with the dimensions (m/k, n/k). What does this mean? This means that by knowing how many grids the diagonal passes on the rectangle with dimensions (m/k, n/k), we can know how many grid boxes the line passes in the non-scaled rectangle (by multiplying the number of grids found in scaled-down rectangle by the integer k).

2. In special cases, such as n = m, we can automatically conclude that the number of grid boxes the diagonal goes through is equal to m or n. This makes sense visually as well.

3. There are rectangles where dimensions are not-so-friendly. We need a method where it would work ANY type of rectangle. Here is my method:


Assign x = n and y = m, then treat them as coordinates and plot them on a Cartesian plane. Draw a line starting from (0, 0) to (x, y). Now that we know two points, we can get the slope of the line. Put the line in y = mx + b form.

Plug in values for x = 1, x = 2, ..., x = n - 1, and get the corresponding y-values.

Now, take the ceiling of the y-value. Whatever the value the ceiling is, shade in the box to the right of the x-value (for clarification, refer to the example below). Notice that when x = 2, we shade in two boxes. This is because when x = 3, the ceiling of y increases one step to two. This means that there is one grid the diagonal is crossing in order to connect the two boxes.

We can now add up the number of boxes shaded in (and also add 1 to account for the box at (0, 0)). This gives us 6. In order to get the number of grids for the rectangle (4, 10), multiply 6 by 2 to get 12.


Looking Back: 
I know that my method is not efficient. I'm having difficulty putting this method into a nice, one-step formula. In terms of correctness... so far it has worked for all examples that I have tried (including all of the cases mentioned in the planning stage). However, since I do not have a formula to sum this up, it would be extremely tiresome to calculate something like m = 150 and n = 200. I could possibly implement a python function using this line of thinking though.

SLOG #8: Finally Understanding Big-Oh, but New Confusion with Halting

I haven't written in about two weeks so this post is going to be longer than usual.

Last Monday and Tuesday was reading break. Hooray for long weekend! I was planning to get some studying done for CSC165, but other assignments and midterms kept me busy.

Last Tutorial: 
We covered proofs with big-Oh.

Steps to proving big-Oh:

1. Write out the definition of what it means for a function to be in big-Oh. In words, the definition basically means that there is a c in the set of positive real numbers, and there is a B in the set of natural numbers, such that for all natural numbers (n), if n is greater than or equal to B, then beyond B (the break point), function f(n) is upper-bounded by c multiplied by the other function.  
2. Do some rough work to find values for c and B. Try to play with manipulating inequalities until you have the result you want. 
3. Write the proof structure, and fill in the body of the proof with the information gathered from rough work. 

Lectures and New Information

For the past week in class, we've been talking about the halting problem. I have to say this is the most confused I've been all semester. All I know is that Church and Turing first proved the halting problem. And my job is to reduce halt to a function (not even sure what that means). Literally, that's all I know about it. I did go visit the CS aid center but the TA there didn't learn about so he couldn't help much. I'm planning to read over both Danny's and Larry's class notes on it, and definitely go through the course notes. And then after that, visit office hours. I'm really worried I won't understand this in time for the assignment though. In our assignment, it's asking us to reduce halt to meaning_of_life. The only information we're given is "return True if f(I) return 42, False otherwise". I'm not quite sure what I'm supposed to do with that piece of information.

However, I'm glad to find that I'm not the only person with this confusion. http://celinasopiniononcsc165.blogspot.ca/ expressed similar confusion. She did do a blog post on a halting problem, but after reading her post, I'm still confused as ever. 

SLOG #7: Thoughts on Test 2 and New Challenges

Thoughts on Test # 2: 
I'm so glad this stressful week is finally over (assignment due on the Monday, and a term test on the Wednesday!). Generally, I thought the test was not as bad as what I was expecting. There was definitely enough time to finish. The only question I struggled with was the second one. Guess I still haven't mastered limit proofs. However, the first and last question were surprisingly similar to assignment 2.

What I'm having trouble with...
I've been having difficulty understanding lecture for the past week. I think most of the fault lies on me, as I haven't had the time or energy to look over my notes. But good news is, I finally took the time to study big Oh proofs, and counting steps over the weekend, and I think I finally understand what's going on (yay!). Once you get past all the Greek letters and variables, it's not too bad.

The trickiest part about it is picking values for c and B. The general idea to take out of doing these proofs is to leave the values for c and B blank when writing the structure. Then go on to do the proof body. Also, don't be scared to overestimate! For example: 3n² + n ≤ 3n² + n² = 4 n². You're trying to simplify the inequality so that the right side can be expressed in terms of the variable of the highest degree. After doing this, you have the value for c, and you can go back and assign a value for c.

 . 

SLOG #6: Big-Oh Confusion

We have moved on from general proofs to proofs including big-Oh. I'm still trying to master proofs, let alone proofs that include more Greek symbols. I feel terrible for admitting this, but I've just been blindly copying notes in class. And all the calculations with inequalities involve grossly overestimating or underestimating (why do we do that?). 

In terms of proof techniques, I think I can finally say 'I get most of it'.  http://csc165wendezhou.blogspot.ca/  summarizes the different proof techniques (under week 6) pretty well. Before reading their blog, I forgot about proof by contradiction. So far I haven't been able to prove one of the questions on the assignment yet. Perhaps I should give proof by contradiction a try. 

Proof techniques: 

- direct proof

- proof by contradiction

- proof by contrapositive

- proving a negation

- proof by cases 

SLOG #5: Proofs, and general thoughts on progress of the course so far

For the past couple of weeks, we've been learning about proofs and proof structure. I’m guessing that correct structuring of proofs is very important in this class because we've been focusing on that in tutorial as well. It’s actually not too bad once you learn and apply the structure rules. There’s a certain symmetry to it.  There's too much information on proof structuring to type out in this blog. I find that chapter 3 in the course notes nicely summarizes everything learned in class.

Self-Reflection

Boy, does time fly! Now’s a pretty good time to do some self-reflecting so that I can make the remaining month I have left in this course meaningful and productive.

To start on a positive note: I've been able to get perfect on the past few tutorial quizzes. It may not seem to be much to most people, but considering that I failed the first couple quizzes, it's very reassuring to see that at least I'm making improvement. 

The bad news: I’m starting to get really confused again in class. Ever since we started sorting strategies and bounding and the ‘worst case’, I've been pretty lost. I know that I should probably go to prof office hours to get help, but professor Heap’s office always has a long line-up and I have class during half of office hours. Perhaps asking the TA’s in the CS help center is a more reasonable approach.

Midterm AND assignment due next week! I’m actually really stressing out… Not sure how I’m going to manage so much work. My goal is to work on CSC165 for at least four hours a day until the midterm. Doing the practice problems and reading over notes is a good way to prepare. 

    

SLOG #4: Epsilons and Deltas

I don’t really enjoy epsilon-delta proofs (mainly because I find them to be confusing), but I find that the process of breaking it up into parts to be helpful in understanding them. Technically, we were supposed to know these for the first midterm, but I realized that I didn’t quite fully have a good grasp on it walking into the test. Thankfully, these were not tested (phew). But who knows, it might be on the exam!

In class we did an example where the lim (as x → 0.6) of x^2 = 0.36

In epsilon-delta terms, this is written as:

∀ e ∈ ℝ⁺, ∃ d ∈ ℝ⁺, ∀ x ∈ ℝ, |x – 0.6 | < d ⇒ | x² – 0.36| < e

The definition of a limit of a function is as follows:

Let f be a function defined at least on an open interval (c – p, c+p) except possibly at c itself.

lim (as x→ c) of f(x) = Lif for each e > 0, there exists a d > 0 s.t. if 0 < |x – c| < d, then |f(x) – L| < e.

1.       First we should find a d. Let e > 0. We want a d > 0 s.t. if 0 < |x – 0.6| < d, then |x² – 0.36| < e.

Find a connection between |x² – 0.36| and |x – 0.6|:

x² – 0.36 = (x + 0.6)(x – 0.6)

|x² – 0.36| = |x + 0.6| |x – 0.6|

2.       Take x within 0.1 of 0.6 (So let your enemy choose an e)

If |x – 0.6|< 0.1, then 0.5 < x < 0.7 and |x + 0.6| ≤ |x| +|0.6| = x + 0.6 < 1.3

Thus if |x – 0.6|< 0.1, then |x² – 0.36|< 1.3|x – 0.6|

3.       If, in addition, |x – 0.6|< e/1.3, then |x² – 0.36|< 1.3(e/1.3) = e

This means that d = min{1, e/1.3}

4.       To see that d works:

Let e > 0. Choose d = min{1, e/1.3} and assume 0 < |x – 0.6|< d

Then |x – 0.6|< 1 and |x – 0.6|< e/1.3

Then |x² – 0.36| < 1.3|x – 0.6|

Since |x – 0.6| < e/7, |x² – 0.36|< 1.3(e/1.3) = e

I also found khanacademy videos on epsilon and delta to be pretty helpful (link: https://www.khanacademy.org/math/differential-calculus/limits_topic/epsilon_delta/v/proving-a-limit-using-epsilon-delta-definition).

We also discussed in class that the order of the quantifiers in this proof cannot be switched around.

SLOG #3: Review of Test 1 Material

REVIEW OF TEST 1 MATERIAL

·         Universal claims (") - claim about all objects

®     to verify: consider every element in the domain and show that they satisfy the claim

®     to falsify: provide a single counter-example

·         Existential claims ($) - claim about some objects

®     to verify: show at least one example

®     to falsify: show there are no examples

·         SETS:

®     P Í Q "P is a subset of Q", "Every P is a Q"

-        To prove: show every element of P is an element of Q

-        To disprove: Find at least one element of P that is not an element of Q

®     P Ë Q "Some P is a Q"

-        To prove: find one P that is a Q

-        To disprove: Show that every P is not in Q

·         IMPLICATIONS:

®     IF antecedent, THEN consequent

®     can also be shown by antecedent Þ consequent

®     to disprove, show an example where P is True and Q is False.

®     note: "If...then..." tells you nothing about causality. For example, "If it rained yesterday, then the sun rose today" is true, but rain did not cause the sun to rise.

®     for antecedent, look for words such as: if, when, enough, sufficient

®     for consequent, look for words such as: then, requires, must, need, necessary, only if, when

·         CONTRAPOSITIVE:

®     the contrapositive of (P Þ Q) is (¬Q Þ ¬P)

®     "all non-Q are non-P"

·         CONVERSE:

®     the converse of (P Þ Q) is (Q Þ P)

·         NEGATION:

®     negation inverts the truth value

®     When negating a statement:

-        Existential quantifiers turn into universal quantifiers, and universal quantifiers turn into existential quantifiers

-        use manipulation rules, such as DeMorgan laws and distributive laws (for full list see Course notes pg.29)

®     Example: ¬($ xÎD, P(x) Ù Q(x)) Û (" xÎD, ¬P(x) Ú ¬ Q(x))

·         VACUOUS TRUTH:

®     Whenever the antecedent is false, and the consequent is either true or false, the implication as a whole is TRUE

®     the set where the antecedent is true is empty(vacuous), and hence a subset of every set

·         TAUTOLOGY, SATISFIABILITY, UNSATISFIABILITY

®     Tautology: you can't dream up a domain, or a meaning for predicates P and Q that provides a counter-example, since the truth tables are identical

®     Satisfiable: true for some choice of domain, predicates P and Q, and values of domain elements, ex: (P Þ Q) Û (Q Þ P). Saying that a statement is satisfiable only tells us that it is possible for it to be true, without saying anything whether or not it is also possible for it to be false

®     Unsatisfiable (or Contradiction): something for which no domains, predicates, or values can be chosen to make it true

***note: This SLOG was supposed to be posted before the test, but I ran into some password and username trouble with my account for the past couple weeks. 

SLOG #2: Thoughts on Assignment 1

Assignment one is finally completed (thank goodness). Overall, I found the assignment to be a fair representation of the concepts we have learned so far. When I say fair, I mean that it was all based on material that we were supposed to know. But that doesn't mean I found it easy...

I found myself struggling (a lot) with a select few questions. I don't think I'm speaking for myself when I say that question four was one of the most challenging questions. In fact, it was a three-day process for me.  The first day I just tried to understand what the question was asking me to do. Eventually I had some kind of a vague idea but I was too tired to act upon it. The next day I came up with a solution for 4(a), which I thought was correct until I went to see a TA in the CS help centre, and he pointed out a major flaw in my reasoning. Darn. But turns out I was close to the answer, because inspiration came while I was in the subway. I tried switching around the sets I assigned to D, P, and Q, and my example worked! The frustrating problem came when I started part (b). I couldn't think of any examples that made one statement true and the other false. My examples either made both true or both false. I went to prof office hours but I still had trouble thinking of an example. Finally on the third day, I went through the course notes again to see if I had missed any information. It then occurred to me that maybe I didn't know the truth table as well as I thought. Here's the piece of information that is now drilled in my head: if P is false and Q is true, P Þ Q is TRUE, and PÙQ is FALSE. I have to admit, it felt pretty good finally checking off that question.

Progress so far: I still find every week to be a challenge. But because of that, I find myself dedicating more time to study for this course. Let's see, what else... OH, I still have to figure out the paper-folding problem. 

1st Post (Introduction)

            Weeks ago, when I had first signed up for this course and read the course title, "CSC165: Mathematical Expression and Reasoning for Computer Science", my brain interpreted that as "PROOFS, PROOFS, AND PROOFS...for Computer Science". I'm pretty wary of doing more proofs after previously taken a math course that involved various kinds of dreadful proofs. I remember being extremely confused after my math professor had first completed a proof for us. In fact, even after an hour of trying to dissect it I was still confused. I mean, how did my professor know to begin by stating this variable? How did he know which order to go in? Why did proving this, imply that? I guess if it's one thing I learned this week, it's that proofs are carefully constructed pieces of art. I imagine that all the eloquent, beautiful, long proofs presented in textbooks are the result of days of planning, trial and error, and editing. Some proofs have taken mathematicians years to develop (talk about dedication). Anyways, I'm actually looking forward to the next couple months because maybe after this course, A={feelings of anxiety} will no longer be a subset of B={feelings experienced when doing proofs}. 

           As for the material we are currently learning in this course, I don't think that I'm very confident about it (yet). I'm hoping that with enough effort and studying, this will change. I'll admit that I'm the type of person who has difficulties when it comes to 'wordy' problems. I had some trouble figuring out what I was supposed to do for question two from tutorial exercise #1. Nonetheless, I still attempted it, and went to tutorial. After seeing a couple examples in tutorial and discussing it with a friend, I finally understood the question. I remember professor Heap saying something about how attempting a problem, getting stuck, then getting help with it, is the best way to learn. Well, what do you know, it's true.

            Since this is my first SLOG entry, I'll include an optimistic list of to-do's in order to succeed in this course: read the course notes, review lecture slides, attempt tutorial problems before going to tutorial, and most importantly, get help when needed.