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. 

Week 8

Week 8 was an intense week for me, I had CSC165 assignment due on the 3rd of November, CSC165 term test on the 4th of November, CSC108 assignment due on the 4th of November and a MAT137 problem set due on the 3rd of November. So I was pretty much going crazy this week. In the week 8 lecture we started with the formal definition of O(n^2). Then we analysed a sort algorithm, we went through the insertion sort and Professor Larry showed us an animation of how the insertion sort works. We analysed another algorithm known as the maximum slice which is said to be very useful for stockbrokers. In the last hour of the lecture we had a problem solving session called penny piles. The problem said:
 You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains
nothing. Can you arrange things so that one of the drawers has exactly 48 pennies, using only the following
two operations?
L: If the left drawer has an even number of pennies, transfer half of them to the right drawer (if the left
drawer has an odd number of pennies, operation L is disallowed).
R: If the right drawer has an even number of pennies, transfer half of them to the left drawer (if the right
drawer has an odd number of pennies, operation R is disallowed).
What about arranging things so that one of the drawers contains other numbers in the range [0, 64]? What
about starting with a different number of pennies in the left drawer?

I did it with two of my friends and we pretty much figured out the problem, this session wasn't that hard. I found it quite easy. Today assignment 2 was due. We have the solutions for it already. Now we have a lecture tomorrow and a term test as well. I hope I do well in this one. 

Week 7

So, beginning of week 7, assignment 1 marks were out and the class average was 83 %. Exactly after this we got to know that assignment 2 was due on the 3rd of November. Our next term test is on the 4th of November. This week was full of bad news! Any ways, week 7 we started a new way to prove which is proof by cases. In this we split the argument into difference case and then prove each case. Basically, we cover all possibilities. Using the proof by cases we can also prove the four colour theorem, which I had never heard about before the week 7 lecture. The four colour theorem proof was the world's first computer assisted proof. We also learned about patterns of inference, there were several introduction rules like the negation introduction, conjunction introduction, disjunction introduction etc. We learned some elimination rules as well such as negation elimination, conjunction elimination disjunction elimination and so on. Elimination rules were basically the opposite of the introduction rules. After doing proofs we started with algorithms, we compared two sorting algorithms, bubble sort and merge sort. We observed that bubble sort was slower than merge sort, we did some examples of linear search also.

Week 6

Today in the lecture, we did some more proofs. Today's lecture was even for two hours because the other section missed their class due to the thanksgiving holidays so that was good for us. So, we did some more proofs today, we learned proofs of boolean and non-boolean functions and we also started proving limits. It's good for me that we are proving limits because we already did these in MAT137 and I was kind of confused about the concept. I didn't actually understand much of the concept so by doing them in this course also will sort of help me understand and go over the concept again. We learnt a new thing called a 'floor', I had never heard about this before so for me it was new. Floor is basically the largest integer which is less than or equal to the number. We did a few proofs which involved the concept of floor. Then we also started doing proofs about limits. Prof Larry included some proofs for fun, they were actually funny.This week we have no tutorial! So that is good news! but I'm still looking forward to the next class.

Week 5

Week 5 has been tough, we've been doing proofs! I found proofs really hard. This week, I was down with flu so I wasn't quite able to concentrate in class, due to this I didn't get a clear understanding of the concepts. We also had our term test this week. It wasn't either difficult or easy, it was some what in between. I was expecting an extremely hard test because assignment 1 was really difficult and after doing that I was pretty sure that I wasn't ready for the test and I would fail it, but now that we have our marks, its not that bad!

Well, because of the test, our lecture was for 2 hours and we learned about proving statements by proving that the contrapositive of the statement is false, we learned how to write a backward proof. Writing a proof backwards is a comparatively easy task. We also learned about proving by a contradiction. We did a proof which I found very interesting, it was:

There are 5 boxes in which there are in total 51 balls. Prove that there is box with at least 11 balls in it. 

I really liked this one. Then we did a proof related to prime numbers. This week was nice since we had only 2 hours of lecture but at the same time the week was tough for me too since I had a lot of work to do.