Week 12 - last post

The semester is finally drawing to a close, wrapping up CSC165. Our last week covered useful topics like induction and countability. On Friday, we got to work on another problem (about diagonals in a rectangular grid). I always enjoy wondering about these, as they really are a unique chance to engage my intuition in such an open way.

After submitting the third and last assignment, the last hurdle is the final exam. For this, we are again able to bring in an aid sheet. Creating this sheet will be an effective means of reviewing all of the information we have learned, way back from the beginning of the course. I am curious to see how much of the early material I remember easily and which parts will take more studying. It feels that all we have learned has built on top of the fundamental principles we were taught in September and early October. For example, formulating proper proof structure was directly linked to implication, negation, etc. from the beginning of the course. To prepare for the test, I plan to go over the tutorial questions again, as well as our two term tests. As a final check of what I have learned, I would like to do some practice exams; these can help me gauge the structure, length, and concepts that may be tested on our exam next week.

Keeping track of my progress in the course with this SLOG has been a mixed experience. While it is a weekly chore, it is interesting to look over the posts from each week and see my development in understanding the concepts. CSC165 has given me a different outlook on logic - I can now believe that if I see a problem, I have the necessary tools to make a valiant attempt at solving it.

Week 11

CSC165 definitely saved the most mind-stimulating (and simultaneously completely mind-boggling!) topic for last - computability.
In their slog (http://csc165f1.blogspot.ca/), a fellow student from the class describes why it is impossible to create a function that will tell you whether or not any input function will halt. Although creating this "magical" function does not, at first glance, seem particularly complicated, delving into it further makes it clear why checking if something halts by making it un-haltable while it halts is a paradox.
This student was not sure on the meaning and application of reductions. Based on their explanation, I believe they are on the right path. In direct relevance to the halt function: if some function f(n) can be reduced to g(n) and it is known that g(n) halts, then the function f(n) must halt. With the contrapositive, if the function f(n) does not halt, then the function g(n) must not halt.
These concepts definitely require some time for deep consideration. Once you get used to the complexity, it becomes possible to apply the understanding to many problems, including those on our assignments and tests.

Week 10

This week, we worked on proofs of whether or not certain functions were in big-Oh and big-Omega of other functions. Each step is clear once the definitions of big-Oh and big-Omega are well understood. Writing out the proof structure is a great guide to completing the proof, as it lays out each step neatly and is useful for staying on-track.
CSC165 has shown me how to approach problems and proofs without fearing them. I now feel that I have a solid base of knowledge and tricks with which to tackle these questions. With just a few weeks left in the course, I am interested to see the last concepts that are taught to us.

Week 9 - problem-solving episode

This week, I came across a problem from a 2009 International Mathematics Tournament of Towns, held at the University of Toronto. I decided to solve it following Polya's approach. The problem is as follows:

Is it possible to cut a square into nine squares and colour one of them white, three of them grey and five of them black, such that squares of the same colour have the same size and squares of different colours will have different sizes?

(1) Understanding the problem: To prove that it is possible, an example must be provided. Otherwise, it is necessary to prove that there can be no possibilities.
(2) Devising a plan: Try to find an example. If this fails, consider why it is failing in order to prove why it is not possible to find an example.
(3) Carrying out the plan: An example was found, shown below.

(4) Looking back: Check to make sure that all requirements of the question were fulfilled (yes).

Week 8

Now, in CSC165, we are finding algorithm "speeds" for linear and quadratic functions. This is based on the number of "steps" that the algorithm takes in order to properly sort the given list. We are learning to calculate the worst case scenario by giving it an upper bound (big-oh) and a lower bound. Of course, we are using a neat proof outline to clearly show how we get our results.
Besides moving on to these new concepts, we have our second assignment due this week, as well as our second test to write on Wednesday. Both of these assessments unsurprisingly cover proofs with proper notation. We have been doing a lot of practice with proofs, allowing us to gain some more insight as to how to approach various kinds of problems. Doing a past test as a summary and extra practice of what we have learned thus far will be my final preparation for this upcoming test.

Week 7

After a long focus on proofs, we are shifting gear to study sorting algorithms. While we have not yet begun to learn the common methods, I am eager to add more skills to my repertoire.
Last class, we again got a chance to spend an hour working on on a problem. This one was about moving pennies between two piles, starting from an initial position (64 in one pile, 0 in the other) and ending at some other number in the range [0, 64]. We first had to understand the problem, then devise a plan and carry it out, looking back to figure out when and how we got stuck (if this happened). Within my group of 3, we considered multiple possible approaches, including working backwards from a number to find a pattern, and working forwards in terms of variables (to be able to see connections between the results). Even after the class was over, I couldn't stop thinking about the problem! I am continuing to pursue the idea of using a variable to connect the results, and seem to see a pattern. However, I have not yet fully understood where this pattern comes from, how it works, or how to predict it. So, there is more work left to be done!

Week 6

The CSC165 classes continue to cover proofs. We are learning various methods of irrefutably demonstrating that a statement is true, or false. In class, we do sample proofs to show us the different techniques.
The two stages for a proof are: convincing yourself that the statement is either correct or incorrect, and then explaining why in a properly ordered form. To be able to solve the problems, it is necessary to thoroughly understand and apply each technique where appropriate. While preparing the methods for creating a solution is important, each of the solutions also requires some insight. Without creativity, as well as trial and error, the proof will not be robust and its presentation will not be optimal.