Halting problem.....SO CoNfUsiNg

we have finished the running time calculations and algorithms complexity section of the course and we are now working on the last section of the course: uncomputable functions, which is really confusing. 

we first started talking about the halting problem which is really one of these mathematical paradoxical situations which makes you very confused just by talking about it.

so here is what it is all about in a nutshell:

We know that some algorithms/programs halt while others don't. (halt meaning that the algorithm/program either give an outcome or raise an exception; in other words, it just stop working at some point while an algorithm that doesn't halt will loop forever.) and no one was ever able to implement an algorithm that checks if the function halts or not and turns out that no one would ever be able to find one (it is proved!). That makes halt a non-computable function.

Interestingly, halt is not the only non-computable function; there are many more and you can prove that they are not computable by using them to implement halt.

This section is getting even more complicated. (I really need to keep up with the material)

Moving on....

We got the results for both Test 2 and assignment 2 ( I did pretty well on both J) so now we are moving on with the course material and I have to admit, it is getting harder again. 

I find it especially hard, when we are given a function and are asked to know its performance at worst case. 

It was also confusing that we were introduced to a way for solving these problems in tutorial that was different than the way we learnt in class.  

As for the tutorial quizzes, they are getting harder as well; I really need to keep up with the material. 

ALL you need to know about assignment 2

Hey again

I know it is sort of late to talk about assignment 2. However, I just noticed that while other blogs have intensively discussed assignment 2, I have only briefly mentioned it in the previous post and thus figured out that I should give the assignment more credit so here you go,

EVERYTHING YOU MAY (or may not) WANT TO KNOW ABOUT ASSIGNMENT 2:

• BEFORE:

In general, I think most students in this course (including me) prefers proofs to the first part of the course; they are challenging, fun, and you feel pretty smart once you have finished one.

However, most of us (again, including me) were worried that we won't be able to solve proofs we have never seen before.

• DURING:

Luckily, I think the assignment was quite fair in terms of easiness especially that tons of office hours were available.

However, it is important to note that this assignment was our first major course work regarding proofs. And as you might expect, different people had different opinions about the assignment. 

Here are some I quote from other blogs/slogs:

http://165uoft.blogspot.ca/ :I found this assignment wasn't as bad as the first. I'm finding this one more concise in terms of its statements. The hardest question I would have to say is number 6 as it utilizes a small trick

http://annakovale.blogspot.ca/: I think Assignment 2 was great practice for proofs and I liked it more than the first assignment (I like proofs)...... I feel like it deserves a separate post.

http://slogjourney.blogspot.ca/:Oppose to watching the professor write the proofs and unanimously agreeing, this assignment was great practice in independently building up my proofs.

So, overall, the assignment was a great chance to practice for the test.

and as you might expect lots of questions were asked:

Here are couple of questions posted by http://1d10terror.blogspot.ca/:

is if there is a statement that I know a counter example for, can I state the counterexample and reach the conclusion thatP(x) -> notQ(x) for all values? Will that be enough to invalidate the entire statement? Also if I have a statement that has a for all assertion in the consequent, what on earth do I do? For example x in D, P(x) -> ( y in D, Q(y) ^ P(y)), is there anything I can do to solve this or am I completely boned and should view the statement from a different angle?

again, I know I am answering these after the assignment but I guess, it is better than never (we still have an exam to write anyway).
So here is my attempt at answering these questions:

1.     If you are trying to negate P(x) -> q(x), you shouldn't prove that p(x)-> not q(x) since this (as discussed in class) is proving "too much" than what you actually need to prove all you need is one example in which P(x) is true and q(x) is not 

2.     proving a for all in the consequent should be treated as any for all: by assuming that y is a generic element of D and then trying to prove that the predicates p and q apply to every single element in D (by proving that they evaluate as True to the generic element y). It might have been confusing due to the many /for alls/ . Personally, what I do to minimize confusion is to go over the statement from left to right in order, writing assume...... for every for all or implication, pick... for each there exists. This way by just building the "skeleton" of the proof, you have given yourself a head start to how your proof will look like and what exactly do you need to find out (to fill in the blanks).    

• AFTER:

I think the assignment was a really good exercise and an awesome preparation for midterm 2. Proof: most people did well on term test 2. 

Test 2 coming up :(

Only one week has passed since the reading week (more or less) and we have already finished the second assignment and are currently preparing for the second term test :( 

The second assignment was "less ambiguous" than the first one. I actually prefer proofs to the first part of the course. However, that does not mean that I have done any better on this. Hopefully, I didn't do so bad. I guess I will just have to wait for the results.

Back to the test. I am really nervous about the second test. The reason is while proofs are easier than the first part of the course in the sense that you know whether you "got it" or not and that you can get part marks by just writing the proof structure,  it usually takes me time to come up with a good proof (depending on what I am required to prove though) but I am only given 50 min to write the whole test. Another problem is that sometimes I skip steps because I think "it is too obvious anyway" and that usually causes me to lose marks since every thing (EVERY THING) has to be explicitly justified and stated. 

 

Midterm 1

Hey again

Last Friday has sure been a remarkable one. Not only, because of the storm that caused all schools and universities except ours to close, but also because last Friday has witnessed my first csc165 test. The test was not so bad (at least, not as bad as I thought it would be). You see, once the sample answers for assignment one were posted, I discovered many hidden mistakes I didn't even consider.
One main problem, that I discovered after comparing my answers to the sample answers, was that I translate literally from English to symbols without taking in consideration the ambiguity in English wording which might require extra quantifiers to disambiguate.

Here is a concrete example:

S1: There is one developer more important than code finger

my answer (which is not quite right) was:

 ∃x ∈X, ∃y∈X, I(x, Codefinger) ∧ I(y, Codefinger) ⇒ E(x,y)

What this is saying is: 

if you pick two developers who are more important than Code finger, they will be the same person. Which is fine, except it doesn't quite say the same thing as S1. 

I had this problem of not being able to precisely translate English into symbols until I decided to use the friend-enemy game we used in defining limits. 

Here is what S1 mean unambiguously:

If you pick a developer who is more important than code finger then any developer you pick after that if he is more important than Code finger, I guarantee you that he will be the same person you originally picked. 

I know it might not seam as a huge change from the first explanation but it actually is: interpreting it this way means that you will introduce an existential quantifier then a universal quantifier instead of having two existential quantifiers.

This technique really helped me to determine when to introduce quantifiers.

News so far......

I know it has been a long time since the first post but that’s because I was preparing some cool program Danny had challenged us to do but since I am still not done yet (have not started actually J, it has been a busy week) and haven’t posted anything new, I figured it is time for me to post something before I actually tell you about the cool mental experiment we did in class (probably, I will have enough time by the reading weak). So wait for that, but for now, here is what has been happening in csc165 so far:

we have had our 3^rd tutorial this week and OUR FIRST ASSIGNMENT. I can’t describe the assignment as hard but I can’t describe it as easy either. Well, that’s the weird thing about this course. You might think your answer is right just because it makes sense to you and turns out it is completely wrong. That is why you must read what you have written from many different angles and try to prove yourself wrong (which is a common thing between all sciences). I hope I did well on the assignment.

As for the lectures, I really loved the part when we try to prove that one statement is equivalent to another statement (since now, you can actually know if your answer is right or wrong). We are starting proofs so I guess that should be fun and I am looking forward to it.