Well That`s Gonna Be A Problem

Slog Week 12

     This week’s material covering multiple infinities is different from the understanding I had before. I did not use the concept of having infinities being mapped out on a one to one scale before. I did not even realize that rational numbers could be even compared to natural numbers. In my mind the set of rational numbers and the set of natural numbers has such an immense gap they could not possibly be mapped out. As for the induction, as I mentioned in a previous Slog, this course is actually quite similar to MAT137. I’ve already had a experience in highschool with induction actually as well as in MAT137. I feel like it’s somewhat repetitive however, I do not mind it.

I like this week’s problem and seeing that I have not done a problem solving slog yet I will seize this opertunity and do it.

Understanding the problem:

To my understanding the question is asking me to draw a rectangle (squares count as rectangles technically) with squares inscribed into them which have the sides m and n such that they represent the number of squares inscribed on each side. Now given sides m and n, I am tasked to be able to predict the number of squares which are crossed when a line is drawn from one corner to the opposite corner.

Planning a Solution:

When I first looked at this problem, I thought of listing the various situation which can happen and then thought of ways which the problem could be solved. Then I made a description of what would happen in each case.

Carrying Out the Plan:

To start off I first drew several practice examples and tried how the relation of similar triangles behaved in various cases. Then I made several observations about how the triangles react when given different lengths then I came convinced myself of the properties which I have observed and tested them and reason them out to convince myself they work, and then I listed all the properties out.

For the sake of ease whenever we are given numbers I am going to refer to the longer side as m, and the shorter side as n. Also the rectangle will be rotated such that the long side is horizontal such that side m is the length of the bottom or top and side n is the side of the right or left.

Property 1:

If side m is can be divided by n then the number of boxes is m

Property 2:

If the if both m and n are even then they will meet at the mid-corner of the triangle before crossing over.

Property 3:

If m is odd and n is even then the middle square will always cross twice

Property 4:

If m and n have common factors then they will make a series of smaller rectangles within the bigger rectangle. The smaller rectangles will have the dimensions of what’s left after m and n have their greatest common factor factored out. The number of boxes will equal the number of

Property 5:

If m and n are both odd then the middle square is only crossed once.

Case 1:

M = N then squares = m

Case 2:

M and N have a greatest common factor, then treat m and n as a series of smaller rectangles with the number being the greatest common factor. And the smaller rectangles have side’s m and n such that they are divided by the greatest common factor.

Case 3:

1)      M is even and n is odd

Boundary crosses = celling ( m/ n ) * n

2)      M is even and n is even

(Does not exist because of Case 2 Greatest common factor)

3)      M is odd and n is even

Remove middle block so then m = (m-1) n = n treat it as an m = even and n = even case and factor the greatest common factor out.  And plus 2 to the final result.

4)      M is odd and n is odd

Remove middle block and apply the M is even and n is odd case and plus 2 to the final result.

Reflection:

I treated this as a program but then I’m not even sure if this works for all cases. I did not come up with an elegant way of solving this and instead used a very brute force method which I’m not even sure works with all the cases.

Halt In The Name Of The Law

Slog Week 11

     I found this week’s material very conceptually challenging, the halting problem not only confuses me but also bugs me. I mean I get the concept of why it works, it’s just that I don’t fully understand why it works. It arrives at a contradiction because if the program halts then it returns False that it does not end and if it doesn’t end then it returns True that is ends. The trouble I have is digesting all of this and convincing myself of it. Whenever I feel like I run through the process of fully understanding it my brain halts and urges me to go watch youtube instead, where it can comfortably halt in peace. I’ll try to watch some youtube videos about the problem to concrete my understanding, especially for reductions.

     I’ve actually had some introduction with the concept of multiple variances of infinity before. However, I fail to make the connection of how useful this is with regard to programming. Different levels of infinity caused by infinite sets being parts of other infinite sets. My only guess at the relevance of this it might have something to do with input and output of functions. I mean I love learning about mathematical concepts and ideas it’s just that it would be nice to see why this is relevant for me. Perhaps all will be more clear in due time. I experienced this thought process before when the connection with computer science wasn't as intuitive as it was. Logic is a vital part of computer science I can see why it is taught but I was unsure about why proofs were being taught. But as the course progressed and Big O was introduced with time complexity I saw why it was relevant. My hopes is that I will have the same realization next week when 165 sadly has to come to an end.

Wombo Combo

Slog Week 10

     I like how this course synergizes a lot with MAT 137. Had I not taken MAT 137 I feel like I would not be doing as well in this course. Although I have not seen the definition of a limit organized into this format before, I feel like I’ve been given a lot of food for thought. I’m really curious how the rigours definition of a limit can be rearrange so that it is similar to the Big O. As I am seeing more and more examples I’m starting to think about the problem more intuitively than before. In terms of concepts covered, I do not see anything really different from the previous weeks. The only difference being the examples. The concept of big Theta is an intuitive step since every function needs a lower and upper bound. Thinking about it as a function which represents the entirety of the time complexity of the program seems sort of daunting. However, with the way it was presented to us as the combination of Big O and Omega doesn’t make it seem so bad. The concept of time complexity seems very useful for optimizing programs which I no doubt will have to do eventually in the future. A few weeks ago if I was asked a question about the time complexity of program I would have just nodded said yes and proceed on with what other tasks I had.

http://kimjohnlim.blogspot.ca/2014/12/slog-week-10.html?showComment=1417638686444

One of my friend`s week 10 also talked about thinking intuitively. I think this is a key element in problem solving and thinking about computational tasks in general, especially on a test.

Sheltering The Storm.

Slog Week 9

     Ahhh... do not think I got nearly as high as I did last time. Even though all of the questions were very similar to the assignment, I think I got the first two no problem but then the last question I didn’t remember how to prove it. I personally contribute this to the fact that I did not know we could bring an aid sheet like we did last time, if I could just see the proofs for assignment 2 then I would have no problem for the test. Moreover, I divided the work with my partners in a manner such that I only vaguely remembered each proof and I knew one really well. I feel unsure about the questions given to me. I feel that if someone did not see the questions like we did by doing assignment two before then they would have an incredibly difficult time solving them in the time frame given. Not entirely sure how I feel about this. This makes the course material seem as if I’m regurgitating something I saw beforehand. I’m sure I've learned from the process but I feel somewhat unsatisfied. Not the romanticized kind of experience I was expecting from this course. Other students also seem to mention that some of the questions on the test were very similar to the one’s on the exam paper. One of my fellow peers even admitted on their slog they used virtually the exact same proof!
http://kbslog.blogspot.ca/2014/11/she-wants-big-o.html

     I still a bit lost when the proofs are being done in class. Maybe it's cause I'm not good at listening, but just writing down how the proofs are done is not helping me. I saw some of the notes from the other lecture and I feel that it explains it in a much better way. I'm sorry professor Heap. However, I do find these useful as quick references on how to do specific cases.

Lost In The Forest Staring Down The Storm

Slog Week 8

     To be completely honest, I thought being exposed to the big O problems more would help me see the forest for the trees but I just feel like I’m lost in the woods. If I was asked to do the proofs we covered I feel like I wouldn't intuitively understand what to do. I feel like I would know what to do by filling out the cookie cutter structure given to me but I do not feel satisfied enough with this. I didn't think the lecture helped me understand the concept more but helped me understand what to write and get by if given a problem to solve. I’ll read over the course notes and Wikipedia some articles to try to understand the concept better and understand why it is written the way it is. Although I have a vague idea about it, I really need it spelled out to me. 

     With the assignment two due and the term test coming up to be honest I have not been thinking a great deal about the material covered in class. I hope that once the storm of work blows over I have the opportunity to properly reflect on this new material which will no doubt be important to the final and possibly assignment three.

The Taste You Can Prove

Slog Week 7

     I found this week’s material about sorting algorithm complexity and the big-Oh very interesting. I haven’t really thought about what causes programs to run faster or slower. This week’s lecture really give me some food for thought. Although the concept is pretty straight forward, on the second last slide the notation for the upper bound Big O and the lower bound omega is somewhat lost upon me. Perhaps it’s just because I do not fully understand why the two are written that way that I do not understand this definition. Sort of like how initially the rigorous definition for limits using epsilon and delta was lost upon me. I think as I see more relating to the definition I will finally see the forest from for the trees. I feel an adult who can’t understand the reason why kids love the taste of cinnamon toast crunch. The taste you can see.

     I found the problem given to us on Friday to be very stimulating. At first I thought that there would be a great deal of numbers which would not be possible. However as I went through notating the possibilities of outcomes that the drawers of pennies could be to my surprise I found that they were all possible. At the moment I realized I was actually so dumbstruck that it aligned so perfectly. I also was very impressed at the person who realized this property so that I could see it as well. Not quite a common problem people have rearranging pennies in a drawer. I wonder how this can be useful.

Turkey Week

Slog Week 6

   Due to thanksgiving this week has been quite uneventful, Most of my tutorial were canceled so there was not a lot of immediate work to do. We are going into further depth in the proofs this week however I feel like we are reiterating over past material which we have covered already in previous weeks. Perhaps that's just the effect that the thanksgiving weekend had. Normally I write the slogs right after the week is done but I've been growing more lazy lately. This slog is suppose to be for the week after the test yet it is written a few days late. Hmm, this is something which I will try to make more consistent. I do not have much to say about the material covered this week since I feel it is so similar to last week's material. The break really gave this entire week a lazy vibe. After the assignment and midterm I haven't really been thinking much about this course since I've been preoccupied with other courses.