Week 11 & 12 – Halting! & Computability

Halting is the problem of figuring out whether an arbitrary computer program will finish executing or stop. This difficult yet fascinating problem is what we’ve been learning in the past week.

This topic is actually the one that is making the least to me in the entire course so far. I basically did understand almost nothing in the lecture, and I had to do a lot of extra reading in order to just grasp the basic idea of this computability theory problem.

We were presented with some examples in class, all written in the Python programming language. It is really cool the fact that there exists some program that is going to run forever and we are unable to prove them.

In the end, it all comes to this: we have a problem that we know the implementation, but we will never be able to prove it, and this is the truly compelling nature of this problem. Just as Neel said in his Slog:

It’s the computer programming equivalent of saying “I always lie”: if it’s true, then it’s not true, and if it’s not true, then it’s true.

In the last week, we were introduced to the last topic of the entire course, which is computability. It is an extension from the halting problem, and I learned a really useful tenique Reduction, that is, to reduce a computer program using halt to determine whether it is computable or not. Basically, the idea is to reach a contradiction: if we reach a contradiction that halt is computable, then by the fact that halt is not computable, we can prove that the original program is non-computable as well. How fascinating! I hope I can get more practice in tutorials, but sadly there weren’t any halting related problems in this week’s tutorial. Hopefully I can understand it better by working on questions in A3.

Week 10 – Big-Oh, Big-Omega, Big-Theta

This week we were introduced to some other notations for complexity, including Big-Omega and Big-Theta. They are only slightly different from Big-Oh, which I think I have a pretty solid understanding in.

However, we were presented with a lot of examples that involved limits, in which many of the techniques used in calculus have to be applied in order to complete the proof. For example, L’Hopital’s rule had to be used in some question to determine the limit of the function, hence giving us insight on which c and b values to pick. I found this really intriguing, as it is yet another overlapping material with the calculus I am currently taking.

Moreover, we have advanced to proving Big-Oh and its variations with general statements, which turned out to be very different from proving specific statements. Proving them involves a little bit of more thinking process, as it is really abstract. I believe I will have to practice more, as it is an extremely important topic. Hopefully doing  assignment No.3 can help me get a clearer understanding of problems of this sort.

Week 9 – More Big-Oh

This week we did more proving regarding complexity, this time involving more polynomials. I didn’t really find it that hard, as I feel that as long as I could understand the definition of Big-Oh and know the basic structure of the proof, I will be able to do proof questions. The basic idea is just to overestimate and then find the suitable c and b value. By now I am already quite familiar with the proof structure and comments, so it is not a concern.

However, the tutorial was quite a bit of challenge to me. It covered course material from the previous week, which involved counting steps. I still didn’t understand completely after the TA went through the question during the tutorial, and on the quiz, I don’t think I got a correct answer. I think steps counting is something that I really have to understand as soon as possible.

Also, we had our second term test this week, which was about chapter 3 mainly. There were 3 questions on the test, all of which were not hard, and I think i did pretty good. Hopefully it will turn out to be as good as I have expected.

Week 8 – Complexity (Big-Oh)

This week we were finally introduced to complexity and the formal definition of Big-Oh. I felt like we’ve learned enough proof techniques to finally be able to do something more serious and more computer-science related.

Week 7 – Sorting and searching

This week we were introduced to some searching sorting algorithms, for instance, binary search and bubble sort. We were taught on how they work precisely and were introduced to techniques used to analyze their efficiency.

Also, we received our grade for the first test back, and it was quite disappointing. First of all, I got confused by the python expression of for all and any, therefore I lost half of the marks for question 1. Furthermore I made a silly mistake when solving the last question too, which made the Venn digram completely wrong. So in general, I was really disappointed and I hope I can do better next time.

Week 6 – MOAR PROOFs

The past week was still about proofs. We were introduced to proof by cases and some more proofs on the definition of limit.

I really like the way Danny illustrates examples in lectures. When presenting examples about proving the limit of a function he exists, he would say that an enemy picks a value E and we have to find a D value such that the limit of the function is true, which made the problem more interesting to work on. However, it is not easy when you are actually doing it. Especially, when the function given is very complex, it takes a great deal of thinking to do the actual proof.

For proof by cases, we did some questions in tutorial and it helped me a lot in terms of giving me enough practice so that I could understand this technique. The quiz at the end of the tutorial was pretty easy too, and I feel like I understand most of the stuff that I’ve learned.

Week 5 – Proofs

Another week of school has passed, and we were given more and more proofs. The goal is to finish up universal quantifiers and get introduced to proofs with existential quantifiers. Also, we were introduced to the notion of some fundamental proof techniques, such as direct proof, proof by contrapositive, and proof by contradiction, of which proof by contradiction is the hardest to me.

I get it that it is generally easier to prove by contradiction when we want to prove a conclusion without any suitable hypothesis as implication. One example used in lecture and is shown in the course notes is the proof that there exist an infinite number of prime numbers, which is also called Euclid’s method. To prove this by reaching a contradiction, we first assume that there exists a finite number of primes, then let P be the product of the primes in the list plus one. Now P is either a prime or not. If it is a prime, then it is not in the list of prime we previously defined; if it is not a prime, then it is divisible by some prime number p that cannot be in the list we previously defined (otherwise p will divide 1 which is not possible), which shows that this prime number p is not in the list we defined. Therefore, we have reached a contradiction that there exists more prime numbers than our original list.

Another big thing happened this week was the first term test. I did the practice test and was shocked by how similar the actual test was compared to the practice test. I am just gonna hope I did okay on the test.

Week 4 – Assignment 1

This week’s content is basically about more proofs with more than one quantifiers. This bit overlaps with what I have been learning in MAT137. It is really nice how taking these courses simultaneously help me understand the course material better.

A good example of a proof involving multiple quantifiers is the proof on the delta-epsilon definition of a limit. As I have already seen a lot of examples in my MAT137 course, these were no longer a trouble to me anymore.

Also in this week, we’ve been working very hard toward our first assignment for CSC165. The questions seemed hard at first, especially the ones involving drawing Venn diagrams and providing with suitable examples for every situation. It took me some time before I became comfortable with Venn diagram questions, and I think the tutorial sections helped me a lot in understanding these questions better.

Anyways, my teammates and I went to Danny and Larry’s office hours and got a lot of questions clarified. It is also great to see how piazza is really useful in terms of getting questions answered, and also you learn a great deal by even looking at other people’s questions.

Week 3 – Folding (Problem Solving session)

During lectures this week, we were introduced to some basic concepts in logic: conjunction, disjunction, negation, and implication. I had already learned some kind of logic in previous mathematical courses in high school, so I was not totally unfamiliar with them.

We also learned about some laws that could be applied to manipulating logic. The idea of using associative laws and distributive laws is pretty intuitive, but not other laws like De Morgan’s. De Morgan’s laws allowed us to express conjunction and disjunction via each other’s negation. It is really magical how these laws work.

But the most interesting thing of the week is what we did on Friday. We were given a seemingly simple problem, which is to find out the how many ceases there are and the pattern of the direction the ceases are facing (ups and downs) after folding a strip of paper certain times.

My partner and I decided to approach the problem using G. Polya’s method, which is to understand the problem first, and then to devise a plan by connecting the unknown with the known, carry out the plan afterwards, and then reflect on the entire problem solving process.

We began the problem by folding the paper once, and then twice, until 5 times. Below are the results of folding (note here the letter ‘U’ is used to represent a crease facing upward and the letter ‘D’ represents a downward facing crease):

1. D
2. UDD
3. UUDDUDD
4. UUDUUDDDUUDDUDD
5. UUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

My partner has posted a video on his slog on the folding part.

Then we started looking for possible patterns, after a while we discovered that the pattern builds up around the central ‘D’, the pattern around the central ‘D’ is the reverse of each other, and that each fold adds   folds (n is the number of folds in the paper strip). The data below indicates the pattern:

1. D
2. UDD
3. UUDDUDD
4. UUDUUDDDUUDDUDD
5. UUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

Now we are able to predict the pattern of the next folding!

My friend Qasim has done something truly amazing, in that he live-coded a python function that generates the pattern.

CSC165 Introductory SLOG

This is a course blog for The Mathematical Expression and Reasoning for Computer Science, which is also known as CSC165. The course is run by professor Daniel Heap at the University of Toronto, St. George campus. The main purpose of this blog is to record my weekly experience in this course. The publications will vary from what I have learned to what I have struggled with during the week.

The course, CSC165, deals with general mathematical logic. The purpose of CSC165 is to provide students with a set of skills in problem solving and logical reasoning. The overall material is different from other classes in the sense that it deals more with expressing mathematical ideas more precisely.

The past two weeks of CSC165 has been a mixture of interesting and challenging elements as well as unique problems. I encountered sets, quantifiers, symbols, logical connectives and expressing mathematical statements in the python programming language. To say the least, the course has offered a variety of problems.

I want to note that one interesting topic is the conversion of natural languages to mathematical statements. I realized how mathematical statements are more precise, in that they eliminate common ambiguities and vagueness found in natural languages. However I find the translation very difficult and I plan to read through the Wikipedia article on Logical Connective, as it gives a much more comprehensive overview on the subject matter. Also the CSC165 course is linked to my CSC148 course in that it involves representing statements using the python programming language. The course is helping me getting a better understanding in the python programming language, which is beneficial for future computer programming skills.

Furthermore, I found that CSC165 was connected to MAT137. MAT137 is the calculus course I am taking and both of the courses were connectible in that they both dealt with expressing mathematical statements precisely and rigorously.

Apart from the lecture, I had my first tutorial session for this course. We were given an exercise problem that was confusing at the beginning. I had a difficulty with incorporating a statement dealing with Venn Diagrams. The TA went throughout the entire exercise. At the end of the exercise, I understand the concept. Towards the end of my first tutorial, there was a quiz that was similar to the question on the exercise. I found the tutorial beneficial in terms of teaching students about a question first followed by a test.

Overall, I truly enjoyed the first two weeks of the course. It is extremely difference from my previous mathematical classes. I cannot wait to see what is in store for the future.