Week 12

Last week we had no class because of the fall break. This was the last week of class, we had our last lecture. It's sad that the semester is almost over. Time went way too fast. This week we got our assignment 2 marks. Class average was around 75%. Luckily, I got a better mark than that. Now assignment 3 is due on the 1st of December. So, the lecture started off with some tips for assignment 3. Then we started countability, we compared the size of two sets, we also worked with a real life example and then wrote the proof for that. We studied about countability and computability together. We learned that to enumerate all python functions we should make a table of halt. We made an argument named 'diagonalization'. Given a list of countably many functions, we can always construct an fx that is outside the list. There are uncountably many functions that cannot be programmed in Python or in any other computer language. In this lecture we also learned about mathematical induction which is a proof technique. I had already done this in MAT137 so I didn't have much difficulty understanding the concept. We did 2-3 proofs with this method. The last hour of the lecture was spent on the final exam review. Prof Larry told us the structure of the exam and the important topics which we could be tested on. This is the end of this course, I hope I get a good grade on the final exam.

Week 10

This week was our second last lecture. We received term test 2 back. I did quite well compared to the previous test. Assignment 3 is also going to be out now. In this week's lecture, we started off by recalling the definitions of Big-Oh and Big-Ω. We went through one Big-Oh proof then we started Big-Ω. We learned the concept of the magic break point. We learned about proving general Big-Oh statements in which we pick a B and a c. In this week's lecture, we finished chapter 4 and started chapter 5 which is 'Introduction to Computability'. We learned about the concept of halt, whether or not a python function halts or not. We had to devise algorithms to check if the function halts or not. Halt basically means if the function stops or not. It is impossible to write one halt that works for all python functions. We proved this statement. One thing added to my knowledge was that computers cannot solve the halting problem. The professor showed us that the halt proof was first done by Alonzo Church and Alan Turing, independently in 1936. Halt is well-defined and non-computable. In this course, given any function, we decide whether it is computable or not using reductions. The meaning of reduction basically is that if a function f(n) can be implemented by extending another function g(n), then we say that f reduces to g. To prove a function computable, we show that a function f reduces to g that is computable. To prove a function non-computable, we show that a non computable function f reduces to this function. This is all that we learned in this week's lecture. Next week we have no lecture and the week following is our last lecture for this course and also the last week of classes for this semester.

Week 9

This week we had our term test 2, it consisted of three proofs. They weren't that hard. In this weeks lecture we started off with the definition of Big-Oh, we did the notation O(n^2) being a set of functions. We went over some proofs and learned about how to choose c and B. Starting from easy proofs went on to doing harder and harder proofs. Then we learned how to disprove, which is done by first negating the statement and then proving the negation. We did a few proofs about that. We talked about picking c and B by showing the bounding relation. Up till now we had only talked/learned about polynomial functions. With polynomials its comparatively easy to figure out the Big-Oh just by looking at the highest degree term.

After polynomials we started proving non-polynomials, which are proven by the concept of limits. I am actually sick of limits now, we have been doing them since the start of MAT137 and I find them quite hard. The definition of limit is used to prove the Big-Oh of the non-polynomials. So when proving Big-Oh of non-polynomials, the first step is to compute the limit by some calculus, the L'Hopital's rule is used, then we translate the limit into its definition. We then relate the definition of Big-Oh and the definition of limit and then we write the proof according the proof structure. This is all what we learned in this week's lecture. Next week we will be doing some more proofs.