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.