CSC165H1F - 12th week

We first started learning about Cantor's example. Even though it was hard to understand I understood his argument after reading 3-4 times.  It did make sense to me and when you think about it it's actually a true argument. To summarize, the argument means the set of real numbers has more elements than the elements of set of the natural numbers. I also think it is true because between 0 and 1 there are infinite real numbers but there are only two natural numbers that are 0 and 1. Then we continue talking about countability.  We learned that number of functions in python is equal to the elements of natural numbers because every letter we write in python has a value in the set of natural numbers. The 'ord' function finds the value of the string. Then we talked about diagonalization. It means that there are more of behaviours than python functions. Behaviours means that if a function halts(gives output) or not.  We also talked about simple induction even though it won't appear on the final exam. I really liked the topic. We proved some arguments with induction and it wasn't that hard. We proved P(n) : 3**n >= n**3 by induction and it was fun. On Friday, we did some problem solving exercises it was tough. We tried solving it with the person sitting next to me even though we couldn't't solve it. While solving first we understood the problem. The input was 2 natural numbers and the output would be a natural number. Then our plan was to try it with small numbers, while the difference of row and columns was 1. As long as we started to carry out the plan the class ended. That's why we didn't finish it. I also got really happy when I learned I got 100 on A2. I hope I'll get that grade on A3 and the final exam!

@Hoyoung Lee: I agree with you. I hope I will be like them, getting good marks acing the course. I also think this course is kind of hard!

CSC165H1F - 11th week

This week was actually a short week because we didn't have tutorials and Monday, Tuesday was holiday and there weren't any classes. In the lectures we did on Wednesday and Friday, we mostly talked about interesting things. Firstly we talked about halting problems. I learned that all of the functions don't always halt(give output). Danny wrote a function which determines given two functions that it will halt or not and showed to us. It does work correctly most of the time but sometimes it returns the wrong output. On Friday we talked about computability and countability. I learned the terms "extends" and "reduces to". I was really surprised when heard about that the size of the set of the natural numbers and rational numbers are the same. It didn't make any sense to me, but since I'm in this course there should've been a logical explanation for it.

CSC165H1F - 10th week

I learned a lot about the big-o in my tutorials and I think I did well on my quiz. On the tutorial we worked on proving Big-O for the polynomials. I thought proving these were hard before coming to tutorial but thanks to my TA I understood that they're easy, you just have to think about it. Also I learned disproving the Big-O for the polynomials and most of the disproofs are similar to each other, thats why its easy to learn them. In the first lecture of the week, we learned about using L'hopital's rule to prove 2^^n is not in the Big-O of n^^2. L'hopital's rule is saying that if the limit of the numerator and denominator is both going to infinity or 0 you can solve it by taking the derivative of the both numerator and denominator. In other lectures we proved ∀f,g,h ∈ F, (f∈O(g) and g∈O(h)) -> f∈O(h). At first I got complicated and didn't know how to solve it when I first saw it, but as we started doing similar proofs to this implication I got the idea. Finally, I was expecting higher on my Term Test#2. I got 2 points lower than my expectation but I'm still above the average so I'm happy about my result.

@HermanKeiley: I agree with you, I also prefer the use of examples over theoretical teaching practices.

CSC165H1F - 9th week

In this week, we mostly did examples about proving the big o for the worst case. We can write it in a logical notation as : ∃c  ℝ+ , ∃B N, ∀nN, n>=B => f(n) <= c times n squared. Danny told us that when they want you to prove something, you should first write the structure of the proof. Writing the structure is very important because it will reduce the thinking. The term test was not that easy. I hope I will get a good grade. The first question was the easiest question in the exam and the second question was the hardest. In the first question they gave us an implication where in antecedent they would give a value of m and n, and in the consequent they would want us to add them and prove the implication. The third question was a similar question from Assignment 2. Instead of writing +1 , they wrote +z on the test. I mostly thought about the second question in the exam I wrote something but I'm not sure if it is right. Also with the examples we did today I understood the logic of proving the big o of the polynomial equation. I'm going to review what we did this week to learn it.

I don't agree with mycaranaway's post of this week. He says "Probably didn't do too well, the practice questions made me underestimate the range of questions that they could give us causing me to just study simple proofs." I think it's a bad way to study for tests like this. It doesn't mean that if practice questions are easy the test will be easy. If practice questions are easy, study from the harder questions. Solve questions from other books. This is the best way of studying I think.

CSC165H1F - 8th week

In the first lecture of the week, we talked about time complexity and running times of programs. As an example Danny gave us some programs including a while loop in it. We calculated the steps of each line in program in terms of length. It was really a fun work. We also found how many steps will happen if the first index where x is found is j. I think I understood most of the work we did in the first lecture of the week. Then in the second lecture we started talking about the upper and lower bound of the worst case. The worst case is at least as bad as the lower bound and the worst case is no worse than the lower bound. It wasn't that hard to understand the definition of the lower and upper bound and write it in terms of logic. Then we proved the logical definition of the lower and the upper bound.  It took us time to prove these two and I had really hard time understanding the proofs because they are so long and they require so much thinking.

As Junru Shao wrote on his Slog: "When Proving Big Omega, proof structure looks like this.

Let c = __
Let B = __
Assume n ∈ N
     Assume n >= B
        
                  .
                  .    #playing around number until I get f(n)>=c g(n)

          Then f(n)>=c g(n)
     Then n>= B  ->f(n)>=c g(n)
Then  ∃ c ∈ R+    ∃ B ∈ N     ∀n ∈ N    n>=B  ->  f(n)>=c g(n)"

I think its a long proof and its hard to memorize it.

CSC165H1F - 7th week

In this week we mostly talked about proofs. We proved the limits of a function, learned about the floor of x. Also I learned how to disprove a function. You should negate the implication and you should prove the negation of the implication because if the implication is false the negation will be true and if the implication is true the negation will be false. Also the contrapositive of the implication is equal to the implication so if you have a hard time proving the implication you can take the contrapositive of the implication and prove it. There are different methods for proving. As an example if you know A and B, you can conclude A or B separately. This method is called conjunction elimination. Additionally, we talked about some algorithms for sorting a 5 card euchre hand. These are insertion and selection sort. All quadratic equations are same for computer scientists. On Friday, we did a problem-solving question. According to the Polya's problem solving techniques, first we have to understand the problem. Then, devise a plan, carry out the plan and look back. Me and my group members understood the problem which was given a number of pennies they ask us to find the last amount of pennies. Our plan was to find a pattern and working with small amount of pennies but even we carried out the plan we only concluded how to get 48 from 64 pennies but we haven't finished solving the problem. Thus, we didn't have a time to look back.

I finally got where we did wrong after reading my friend(Starreyes24)'s slog. We had to work backwards to solve the problem. I realized that it is not that hard exercise after looking to starreyes24's slog.

CSC165H1F - 6th week

We only had 2 hours of lecture in the 6th week because it was thanksgiving and the university was closed on Monday. Also we didn't do any tutorials this week! In the 2 hours we worked on proving some of the implication and we learned how to disprove some implication. If we want to disprove something we take the negation of it and prove the negation of it.  The structure of the proof is more than the content. For example even you leave some blank lines and you feel like you can't solve the proof , the TA's will likely to give you points. I think proofs are difficult because you have to think a lot and you need to have a great mathematical knowledge. In the exam also there will be a time pressure. I'm working on to understand the contents of proofs. I should understand to prove things because in the other half of the course we will be doing proofs about everything.

I disagree with A.M. In this weeks slog she wrote that the hardest thing about limits is devising a plan  to find the values. I don't think it is that hard. It's all about calculus stuff. I think the hardest thing about limits is memorizing the equation with logical symbols. I'm saying that because I'm really bad at memorizing stuff both in real life and school life!