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!