SLOG Week 11

So after 11 long weeks of SLOGing, I have finally finished learning all the concepts that this course has to offer. To be honest, I will really miss taking this course since it introduced me to many new ways of thinking which will help me out in the long run on my journey to get a specialist in computer science.

During this last week of classes, we wrapped up everything on computability and we were also introduced to the concept of induction. After listening to the lectures, my previous understanding of induction from MAT 137 was strengthened quite a bit however, the way to go about doing induction was slightly different. Instead of starting with a base case, we do the inductive hypothesis first and only after that do we prove the base cases which are the cases that are not covered by the inductive hypothesis.


As I was going through some other Slogs, I came across a slog that definitely helped me.

Through reading Abhinav's blog, it reminded me greatly about how complex proofs can be and how one simple step to make all calculations much easier. I will definitely keep this method of thinking with me as I go into my exam for this course.

http://ace165.blogspot.ca/2014/10/proof-can-be-tricky.html?showComment=1417660930106#c6828251752445604463

SLOG Week 10

Sort of late with this entry this week since I completely forgot about SLOG. I should probably manage my time better next time to get this in on time, although I think this is sort of the last SLOG seeing as how there is only like one week left of class.

This week we only had two classes due to reading week and so we didn't cover much. In these two lectures, we moved on from Big-Oh to halting and computability. Turns out it is impossible to determine whether a function halts or not using a halt function because it means it will half only if it doesn't halt which is a contradiction.

Also, something I found interesting was the problem that could not be solved for 70 years even by the professor. It showed that something that looked like it could be proved very easily actually turned out to be super complicated. Maybe one day I'll be able to solve it and become a millionaire.

SLOG Week 9

There's only about two weeks of classes left and I can't believe I've made it this far. This week has been less hectic for me since I finished all my tests and assignments and I even get some time to relax since we have no class Monday.

This week we learned about Big-Omega and Big-Theta. Big-Omega is roughly the same as Big-Oh except that its definition has the equality sign flipped at the end of the consequent whereas Big-Theta is basically when something is bounded both above and below by the same function. I found this weeks lecture to be easier since we didn't have to count any steps to prove any of the statements which is something I still need to work on. Also I particularly enjoyed proving general statements because the structure of the proof flowed very linearly (didn't require going backwards) and made a lot of sense logically.

On another note, I'm planning to start reading the other sections lecture slides in order to enhance my understanding of the material since they provide some different examples that I could try out and then check whether I'm right or wrong.


I especially liked Albert's blog which showed that there are people who struggle with proofs like me and despite that, can still keep a very positive attitude as demonstrated by his very interesting blogs.
http://99bugsbutaglitchaintone.blogspot.ca/2014/11/week-9-more-on-big-oh.html?showComment=1417660757626#c5659481090157877391

SLOG Week 8

This week we had our second term test. Oh how gruesome it was :(. I discovered that I write way too slowly with a pen since I try not to make any mistakes as pens aren't erasable. I ended up probably spending 3/4 of the test writing while only using the rest of the time to think about how to do the questions. Hopefully I won't do this again on the exam since that would be pretty brutal on my mark. Also this week I found out a neat trick about proof structures that was pretty obvious but I somehow ended up missing it; that is you don't have to write out the entire statement at the end as you can just use some sort of indication to show that it follows from the rest of the statements.

We also continued with Big-Oh this week. I'm having a hard time coming up with the equations through counting steps despite having programming experience and I'm trying to resolve this issue by constantly reviewing the notes everyday. However, when they give me the polynomial to work with, I'm having little to no trouble which I suppose is a good thing. Hopefully I'll have everything cleared up before our third and final test.

SLOG Week 7

Through each topic we cover, I initially find it extremely challenging and then by the end, I find that it becomes second nature to me. With the introduction of big-Oh  and bounds however, I'm a bit sceptical that this pattern will continue. The amount of thought needed to be put into the proof of different cases is just mind blowing and I don't see how I'll ever get used to it.

On another note, I've just finished assignment 2 and found that I learned quite a bit more about how to conduct proofs, such as indentation and how linear proofs are. However, this wasn't without cost as I just spent literally 18 hours without sleep trying to figure out what value to take for an existential proof.


After reading Quinn's slog, I feel more comfortable that other people are in the same situation as me for counting steps in order to successfully do big-Oh proofs. I will indeed do my very best in order to make sure that I fully understand this concept by the time of exams through studying and practising many problems everyday.
http://quinn165.blogspot.ca/2014/10/week-7.html?showComment=1417661682781#c8808796752548769768

SLOG Week 6

This week we were introduced to a problem called penny piles.

Understand the problem

You start with two side by side drawers. The left one contains 64 pennies while the right one contains zero pennies.

- If the left drawer has an even number of pennies, you may transfer half of them to the right drawer. YOU CANNOT DO THIS IF THE LEFT DRAWER HAS AN ODD NUMBER OF PENNIES.

- If the right drawer has an even number of pennies, you may transfer half of them to the left drawer.
YOU CANNOT DO THIS IF THE RIGHT DRAWER HAS AN EVEN NUMBER OF PENNIES.

Thus we can conclude that you may are unable to do take away pennies from any drawer that has an odd number of pennies.

WHAT WE WANT TO KNOW:

- Can we arrange things so that one of the drawers has 48 pennies using the 2 methods available above?

- Starting from the same initial position (left drawer: 64 pennies, right drawer 0 pennies) can you pick any number in the range [0,64] and obtain that number on one of the drawers using the two methods given? If not, which ones are impossible to achieve?

- What happens when you start with a different number of pennies in the left drawer?

Devise a plan

During class, I tried many different approaches to this question. This included trying to find a pattern in which I could relate to with a mathematical formula which could get me any number which worked.

What I got was two formulas which would calculate the number of pennies needed to be on each side to achieve a number.

( Even or Odd Number, Other side)  aka (what we want, what the other side needs to be)

Where n is a generic integer number

Even Number: ( 2^n , 64 - 2^n)
Odd Number: (2^n + 1, 64 - 2^n - 1)

This approach did not really lead me to an answer since it didn't answer any of the questions above.

Thus, I decided to make a tree diagram because that would should all the possible results and would be able to answer to first two questions.

Carry out the plan

As shown from the above tree diagram, every even number in the range [0,64] even number is achievable and will eventually become an odd number. When this happens both sides of the drawer will become odd since even + odd = odd.

Therefore we have found out that since all numbers in the range [0,64] exists on the tree diagram, you can pick any number in the range [0,64] and arrange things so that one of the drawers has that number of pennies using the two methods of arrangement available to us. Since this is true, we can also arrange things so that one drawer has 48 pennies.

However, this is not the case if we started with a different number of pennies in the left drawer. This is because if we start with an odd number of pennies in the left drawer, there will be an odd number of pennies in the right drawer. Since both drawers have an odd number of pennies, it is impossible to use either of the methods of arrangements given to us.

We have thus answered the three things we want to know.

Looking Back

The tree diagram looks as if it has effectively solved the problem. However, this method would prove to be very tedious and inefficient had we been given a bigger range such as [0,1000]. A better way of doing this may be to write a program to compute all the combinations for you or maybe to actually use a mathematical proof.

OTHER SLOGS

I really liked how John could find  a way to determine whether the statement is true or false. From it, I learned that it is probably best to do this first rather than mindlessly diving in to discover every possible solution like I did previously.
http://kimjohnlim.blogspot.ca/2014/12/slog-week-11.html?showComment=1417660528863

SLOG Week 5

After a very enjoyable thanksgiving weekend, I received my marks for my first CSC165 midterm. Thankfully I received a few marks for my answer despite it being rushed and probably unreadable to the T.A. However, I am a bit disappointed in myself since I knew what conditions had to be met to falsify one statement while making the other statement true but, due to my lack of sleep, I wasn't able to think of examples.

On another note, this weeks lecture's on proofs escalated to a greater difficulty quite fast. The structure of proofs is straightforward but coming up with everything to put into the body of the proof is just mind boggling. With 3 midterms coming up, I'm having trouble finding the time to review and understand the material but since I commute, I'm going to try to go over the notes everyday to and from school to ensure I don't lag behind the rest of the class.