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.

Midterm's over Yippee!

I was upset about the midterm and finally it's over!

In fact, what made me upset before the test was the solution to assignment 1. I did spend time on it, but I still noticed some stupid mistakes when I went through the posted solution. So I was worrying that I would make a lot of mistakes without even knowing. When the result for the test came out, once again I found that I lost marks on mistakes due to carelessness, but much less this time. But how can I avoid such errors? Checking is not enough for me. 

The good thing is at least I've become more confident for everything we've covered after reviewing for the test. 

This week we learned the structure of proofs and the tutorial was quite helpful for me. We talked about how to write a proof and how to make comments. 

Working on Assignment 1

I focused on Assignment 1 the past whole week. Having discussed with my partner, I found there were some problems I thought I had understood actually  puzzled me. The discussion with my friends was quite meaningful, it revealed some problems I had barely noticed and gave me a hint what to review for the midterm. Having my answers refined, I went to Danny's office hour to make sure I was clear about the problems. It shocked me when I saw about thirty students waiting outside, but it made sense since the assignment due the day after. So, I went to see Larry and fortunately there were a few students then. He was so patient and explained clearly to me about my questions. And he also pointed out some details I had overlooked, like the "three sets" in question 4.  Now I totally get it and feel much better!

Midterm is coming, I had better work harder now. Hope everyone will get a good grade!

First Problem Solving

There was a change on Friday's class, we worked with peers on a Folding problem. We were asked to take out a strip of paper and fold it with its left end on top of right end, then repeat this several times trying to find the creases pattern. I folded the strip, and my partner recorded the creases. At the beginning, the problem seemed complicated and the record of ups and downs wasn't that helpful. After a brief discussion, we decided to change our way  to record how exactly each fold added creases to the strip like this:

It's easy to find the pattern now.
Copy the arrows from the previous row and there will always be an up, a down, an up, a down, an up, a down... in the intervals. Besides, the left side and right side is symmetrical.

We predicted the pattern after the fifth fold first,  then folded again. And it turned out as we expected.  When we saw the hints on the other side, we knew our method was correct.

The experience of working with a peer in class was valuable. I hope there will be more classes like that.

I've been trying to write a program in python this weekend, but with only a few week's python classes, I found it really challenging. Maybe I'll drop in office hours next week.

Week 1 and Week 2

 I loved those mathematical logics we've discussed in class so far! This course went beyond my expectation. Though I had been admitted into computer science program, I was worried about the coming computer science courses.  To my surprise, I found myself kind of immersed.

       
 In the first week, we talked about sets, quantifiers and proofs for universal statements and existential statements. Those were pretty easy. And in this week we learned implications and negations which also been taught in MAT137.  

        
To be honest, I've already learned the above things in junior high and senior high. However,  I still felt uncomfortable occasionally during classes. Since English is not my mother tongue,  I'm not that familiar with some English terms and some logics behind the language. Besides,  the "if only" and "unless" statements indeed frustrated me for quite a long time, but I actually enjoyed the process of trying to understand it. To learn more efficiently, I plan to set aside some time to preview, maybe just go over the course notes for next period. I'll start this weekend and see if it will work.