Last Problem Solving

We were handed the last problem sheet on Friday during lecture. It was about diagonals.

Understand the problem:

Suppose we have an m x n rectangular(m rows, n columns), then we draw a line from the upper left to the lower right corner. And the question is to find a formula to calculate how many squares the diagonal will meet.


Devise a plan:

1. Do a little analysis to avoid unnecessary work and to make sure every possible case will be covered. 
We found out that the case for an m x n rectangular and that for an n x m rectangular are the same. Thus, we can fix the number of rows or columns and change the other. We chose to fix the number of rows as m. Then for the number of columns, we start from m and add 1 to it every time. 

2. Start from small cases. Draw pictures and count.

3. Try to conclude something from the data we get. Make a guess for the formula.

4. Try to prove the formula works for every possible case.


Carry out the plan:

We started from small cases and counted the number of squares crossed in each case. 

During the process, we found out that the rectangular is symmetrical, so before we counted the number of squares, we drew a "middle point" in the rectangular, and we only needed to count the number of squares left above the point.

In some cases, when the number of columns in a rectangular is m plus an even number, and m is even (i.e. the rectangular has an even number of columns and rows), we can scale down to smaller rectangles.










Drawing the conclusion:

Suppose the rectangular has m rows and m+n columns(same cases if the rectangular has m columns and m+n rows).

Case1: n is even, m is even
for all k in natural numbers, n = 2k
then the number of squares met is 2(m + k - 1)

Case2: n is even, m is odd
for all k in natural numbers, n = 2k 
then the number of squares met is 2(m + k - 1) + 1

Case3: n is odd
for all k in natural numbers, n = 2k + 1
then the number of squares met is 2(m + k) 

This is so far I have figured out.


Problems to be solved:  

1. How to prove the formulas?
The first idea occurred to me is to prove by inductions. Assume the formula works when n = 2k, but I am right now stuck at how to prove that n = 2(k + 1) still works. 
I'd really appreciate it if someone could offer me a hint!

2. Since my examples are quite limited, I am not sure that the formulas I have concluded are correct.  
And I saw this kind of problem occurred on another student's post.
http://bryanlimycs.blogspot.ca/2014/11/week-11.html


                  

A2 and Test 2 ---- Two Waves

Last week was busy. I had several tests and two assignments due during the weekdays including test 2 and assignment 2 for csc165. Thankfully, we started on assignment 2 early this time and finished almost everything days before the assignment due. But when the deadline approached, I couldn't help checking the assignment over and over and kept sending my partners new versions, which must have driven them crazy. LOL.

Then came the test on Wednesday. I didn't prepare at all this time, so I just hoped that I wouldn't make unnecessary mistakes and for those difficult problems---let it go! There were only three proofs on the paper, and all of them were similar to problems on assignment 2. Since I did devote some time to the assignment, I worked out the proofs without much difficulty. Hope minor mistakes can be avoided this time.

One thing made me happy was that the " big-Oh " finally made sense to me! I was totally confused last week and I tried really hard but still didn't know what the instructor's talking about in class. So I downloaded both Larry's and Danny's lecture slides and read through the course notes. And I totally get it now!

More on computability

This week we continued on computability and introduced proving by inductions. I still got quite confused during the lectures when we were discussing about the "computability and infinity". But at least some newly introduced concepts like"one to one" and "onto" were taught in MAT223 earlier this  semester, so they look familiar to me. For the section of computability and halting problems, I went through the slides posted on the course website and related pages in course notes. It seemed to make sense, but when I came across a certain problem( Q6 on assignment 3), I still found difficulty solving it.  So I went to office hours on Thursday, and finally understood the whole thing.

For the inductions part, I missed the Friday lecture on it. And I will go to the course website to see if I could understand what I missed. 
Meanwhile I will go to other students' slog to see if someone has post something valuable about it.

Halting problems and computability

We focused on halting problems and computability this week. Some functions are not computable. To illustrate, if a function returns whether a program will halt, then it is not computable.  Since we can never determine whether a running program will keep running forever. And we learned to prove a function is not computable by showing that we could write a working halting program for it if it were computable.

Unfortunately, I don't think I have fully grasped what the instructor taught. During this week's lectures I always found myself kind of dizzy, maybe it's because I have been staying up late these days. And this has led to a less effective in-class learning. I hope there will be tutorial exercises proving functions are non-computable.

Brief Summary on Big-oh and Big-Omega

We continued on asymptotic proofs the past week, and did more proofs on combined statements of big-Oh and big-Omega. Though the proofs look longer and there come more restrictions when picking values for the fixed variables, the whole proof process is the same.

Here is a brief summary:

To begin with, write down the structure including the comments. Not until last Wednesday did I realize the importance of writing comments for the structure part. I got my term test 2 paper that day and found I  lost half a mark for not writing the comments for the last two lines in a proof. Otherwise I would make perfect this time. But the good thing is I learned some comments are not optional to write and will not forget them for the structure part again. 

Then, find restrictions for variables to be picked. To do this, we start from the antecedent towards the consequent as before. The only difference is we need to take different restriction for every step into consideration. We should be especially careful when doing the combined-statements proofs and guarantee all the requirements are met. 

So far,  CSC165 has always been my favourite course. And I hope I will enjoy it till the end of this term.

Proofs Summary

We covered the basic rules for proofs and did the "penny piles" problem during lectures. The list of basic rules was kind of like a summary on Chapter 3 --- Proof. Accompanied with tutorial exercises and quizzes, it gave me a deeper and more systematic understanding on this chapter.

Basically, I divided my working on proofs into four steps: 

1. Determine whether the statement is true of false. If the statement is false, write down the negation of it.

Sometimes it's a good idea to draw a graph when the whole statement seems too abstract. And I found   this method really helpful when I was doing 1.2 and 1.3 on assignment 2.
To prove a statement is true, instead of proving itself, we choose to prove the contrapositive occasionally. To write a negation for the original statement, first we change the quantifiers, then we negate the if-then statement. Be careful when using De Morgan's law. And parentheses are always helpful.

2. Write down the assumptions.
These include universal quantifiers and the antecedent.

3.Start from the antecedent. Reach the consequent.
If we come across an existential quantifier, we will need to give specific names and then continue the proofs. As for me,  make sure to complete the whole structure for each different case in the proof.(examples are Week 6 Tut Q3 and Q4).

4. Complete the whole structure.
These include introducing the =>, quantifiers , etc.

More on Proofs

There were only two lectures this week and we've been talking about proofs in class.

During this week's lectures, I learned that when we are working on a proof, we don't have to know what to write from the beginning to the end at first. Instead, we can write down the assumptions and conclusions first, then go inward until we have to give an explanation on a statement. This method applies to problems from MAT137 as well.

Also, I found proving the contrapositive of a statement quite helpful sometimes, especially when I apply this method to problems in my Linear Algebra course.

The midterm results were announced this week. Though I got a good mark, I'm not satisfied because I made an unnecessary mistake in the paper. Maybe I should keep a record of my past mistakes so that I can do better next time.