Week 10 + 11

If f is in big O of g, it means that g is an upper bound of the function f. In Week 10 we were introduced to big Omega, which means that if f is in big Omega of g, then g is a lower bound of the function f, and big theta, which means if f is in big theta of g, then g is a upper and lower bound of the function f. Proving that f is or is not in big theta/omega of g is really similar to proving big omega of something, so it was all quite straight forward. Proving things using limits and l'Hopital's rule is also really straight forward to me.

This week (week 11), we started a new topic - halting problem and computability.During lectures, I had no idea what the professor was saying and found the content extremely difficult to follow. I had to do a lot of studying myself after lectures to understand it, but I think I get it now. I've looked at some past CSC165 final exam papers and it seems that reduction is tested a lot. At the moment, I feel like I only barely grasped the concept, and so I will be trying to find more questions to do and practice until I feel more confident about it. 

Week 9

I've had a bad week and I fell behind slightly on the content of the course. I may not have done as well as I could have on the test and the tutorial quiz this week. However, this did show me what my weaknesses were and what I have to work more on. I am perfectly fine with getting the structure of a proof down, however I had some difficulty with the actual content on the proofs in the test. I've looked over all of the proofs we have done in lectures/tutorial exercises/the assignment and I have figured out how to do the questions I couldn't do properly on the test. I think with a little more practice, I should be fine. As for this week's tutorial quiz, I discovered that I am not too confident about counting steps. I have been working on that by doing the practice questions in the course notes pdf on the course website.

On the other hand, I've been finding the things we are currently learning in lectures quite easy to follow. I am very confident in proving something is in big O of something else.

Week 7+8

We have began learning about algorithm analysis, and have been introduced to big O. We looked at sorting algorithm complexity, counting steps, and worst case. Unlike translating symbols, which has pretty much become second nature to me, and proofs,  which I have done a lot of in high school, big O was something new and interesting. It feels like we've taken a step deeper into computer science. I actually had a little trouble keeping up with the content during lectures, but after looking over lecture slides and notes and doing a little extra studying, I think I've established a decent understanding of what we've been doing. I've realized that it may look scary, but is actually not that hard once you get into it.

Assignment 2 was fairly easy. 1.2 and 1.3 gave me a little trouble, but I think I have it figured out. Everything else went quite smoothly and I didn't come across any difficulties.

Penny Piles (Problem Solving)

Understand the problem: 

There are two drawers. The left drawer contains 64 pennies, and the right drawer is empty. With the following two operations:

L: if the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.

R: if the right pile has an even number of pennies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

Devise a plan:

To find out if it is possible to have 48 pennies in a drawer, we can carry out the two operations and see if we can make 48.

To try out if other numbers in the range of [0,64] are possible, we can draw a tree diagram to investigate all the different possibilities. Once an operation is carried out, it opens up two new possibilities. This kind of branching is perfect for a tree diagram. 

Carry out the plan: 
How to make 48:
Carry out L: 32  32
Carry out L again: 16  48 or Carry out R: 48  16

Other numbers in the range of [0,64]"

Note: I accidentally started the tree diagram off with no pennies in the left and 64 in the right instead of the other way around as presented in the problem. This does not affect the result because either way, the same numbers will be made. 

To check if all the numbers in the range of [0,64] are included, we only have to go through and check that the numbers in the range [0,32] are present in the tree diagram, as these numbers will pair up with a number in the range [32,64] because the total number of pennies in the drawer is always 64.

Conclusion:
It is possible to make 48, and all the other numbers in the range of [0,64].

Week 6

So last week we learned how to break down statements with universal and existential quantifiers and structure proofs for them. When there is a universal quantifier, we write 'Assume that *insert universal quantifier part here*' and when there is an existential quantifier, we try to assign a value to the variable, although sometimes we may have to think through the proof contents before we can go back and assign the value.

This week, we learnt more types of proof. We learned how to prove something false, first by negating the statement, and then proving that the negation is false. We also learned how to structure proofs by cases. An example we worked on in class was to prove that n^2 + n is even. The first step is to figure out all the possible cases. For the example I just mentioned, there are two cases: n is even , and n is odd. Then we have to prove the statement for each case.

Like I said in my blog post for last week, everything is pretty straightforward. Lectures have been quite dull and because we've just been working through specific proof examples in class. Everything has just blurred and mixed together in my head, which is why I wrote the above two paragraphs to summarize things so they can get filed away neatly in my brain rather than float around in a huge scattered mess.

I think proofs are fun in a way, because a lot of the time, it requires you to be creative and approach a proof from different angles in order to figure out a functional, clear way to show something, but it can also be quite annoying sometimes for the same reason.

Week 5

In lectures, we are still going through different types of proofs. Everything is pretty straightforward and there isn't very much to say about it.
We had our test this week. I prepared for the test by looking through old lecture slides, notes that I have made, assignment 1 and tutorial exercise. I also looked at the old test paper that was posted on the course website. However, the answers on the paper were very vague and although I knew how to determine whether each one would be True or False, I was not entirely confident with my explanations as to why they were True or False, and the answers on the sample test did not really help. But overall, for the actual test, I felt that I did okay and there weren't any questions that I had trouble with.

Week 4

From doing the assignment, I was stuck on question 2d) for a while, because I could not identify if the statement was the converse, contrapositive or negation of the original statement. It looked like the contrapositive of the converse. However, after a while I remembered that the contrapositive is equivalent to the original statement, so the contrapositive of the converse is equivalent to the converse. This is something I will keep in mind for future use.

In class, we have started learning about proofs. I have done some mathematical proofs during high school, but those were more focused on the content of the proof, and we were never taught proper structure. So learning to structure proofs was something new to me. I can see how the structure can help you find a starting point and directions to work in, and also make it clear and easy for somebody else to understand your proof.

Overall, I'm feeling quite comfortable with material that was covered this week and am still finding the course rather enjoyable.