Week 12

This is my last post.  This week was focused on completing assignment 3.  My group and I tried to finish early so we could review our answers and ask questions.  We made full use of office hours, going three times to confirm that our approach was valid.  In lecture we concluded the course material and learned some techniques that would be helpful in the follow-up course.  At first, the concept of diagonalization confused me, but after working through the example with real numbers, I understood this topic better. Our exam is coming up next week and it's hard to believe that the term is coming to an end. 

Week 11

This was a shortened week due to the fall break, so there were only two lectures and no tutorials.  Assignment 3 was emailed to us a system continues to be unavailable.  My group members and I started to work on the assignment this Friday.  We had some questions about parts of the assignment and went to office hours to get clarification.  Unfortunately, the office hours conflict with one of my classes and I had to leave one of my group members alone to deal with the questions. 
In lecture this week, we started to learn about halting.  This subject is somewhat abstract, but I saw the logic behind the concepts, for example that infinity can be not equal to infinity. 

Week 10 and Problem Solving Episode

This week we continued with big-O and big-Omega proofs.  I found that I was able to understand the material well.  There were no real confusing aspects of the proofs.  This weekend Assignment 3 was to be assigned, however, all the computer science websites were down, so we were unable to access it.  As a result, the due date was delayed by three days.

Below is my problem solving episode.
----------------------------------------------------------------------------------------------------------------------------------------------
On October 24th, we had our second in-class problem solving session.  This problem involved manipulating piles of pennies in two drawers.  The problem read:

You are sitting in front of two drawers.  The left drawer contains 64 pennies, the right drawer contains nothing.  Can you arrange things so that one of the drawers has 48 pennies, using combinations of the following two operations, l and r?
l: If the left drawer has an even number of pennies, you may transfer half of them to the right drawer.  If the left drawer has an odd number of pennies, operation l is disallowed.
r: If the right drawer has an even number of pennies, you may transfer half of them to the left drawer.  If the right drawer has an odd number of pennies, operation r is disallowed.
Choose another number in the range [0,64].  Starting from the same initial position, can you arrange things so that one of the drawers has that number of pennies? Are there any numbers in that range that are impossible to achieve? What about starting with a different number of pennies in the left drawer?

1. Understand the Problem
This problem has multiple parts:

• starting with 64 pennies in the left drawer, can you use operations l and r so that there are 48 pennies in one of the drawers?
• in the range [0,64] are there any numbers that are impossible to achieve?
• How does the answer to question 2 change if there are a different number of starting pennies?

2. Devising a Plan
I decided to start with the first question as it seemed the easiest and a precursor to question 2.  My original plan was to create a table with the two columns being the right and left drawers and keep track of which operations I performed to reach 48 pennies.  I would then extend this plan to include all the numbers between 0 and 64.

3. Carry out the Plan
I was able to answer the first question quickly as it only took three utilizations of operation l.  My first table looked like this:
Right Drawer                     Left Drawer
64                                       0
Operation l
32                                       32
Operation l
16                                       48

I then attempted to answer question 2 using this same format.  I started at 0 and worked my way up eventually reaching 25 before I realized that my plan was too time consuming and that there was a better and faster way to solve this problem.  So, back to step 2.

2. Devising a New Plan
My second plan entailed constructing a tree of all the possible combinations of numbers from all possible combinations of operations.  From my first plan, I noticed that all the pairs of numbers summed to 64, so this would be a good way to check my answers and ensure that I have covered all the numbers.

3. Carry out the New Plan
The number tree was much faster and after completing it I found that (as I had predicted), it was possible to have one of the drawers hold all the numbers between 0 and 64 inclusive.  My tree for 64 starting pennies looked like this:

4. Looking Back
I was able to check my answer by checking that all the numbers between 0 and 64 were in my tree.  Since the last question is an extension of the one just answered, I have included my solution to it here.  Based on the results with 64 pennies, my original prediction was that the results would be the same for all even numbers (odd numbers wouldn't work because they are not all divisible by some common number, like evens are).  So I decided to try some other even numbers.  I started with 32:

 

 32 worked fine.  What about 8?

 

8 also works.  But then I tried starting with 12 pennies:

 And I got stuck at 9 and 3.  So it seems my original prediction was wrong.  So why do some even numbers work and others do not? What do 8, 32, and 64 have in common?  I noticed that those three numbers are all powers of 2, whereas 12 is not.  A quick check of other powers of 2 (like 4 and 16) and non-powers of 2 (like 10) confirmed my theory.  This answer raised another question: what is the relationship between the most number of steps it would be necessary to perform and the starting number?  Well, with my knowledge that the numbers that work are powers of two, and based on the trees that I drew, it became apparent that the log base 2 of the starting number corresponds with the final tier of numbers in each tree.  Finally, it is also interesting to note that all the numbers in this final tier are odd and that odd numbers only show up in the final tier.  With this information, it is possible to predict whether or not a number follows the same pattern as 64 and how many operations it would take to obtain an odd number of pennies in one of the drawers if given only the starting number of pennies.

Weeks 8 and 9

Over the past two weeks a number of important things happened.  My group and I worked on Assignment 2, which was due last week.  Of the eight proofs we had to write, three were challenging.  We completed the five easier proofs quickly and spent most of the remainder of our time focusing on the other three proofs.  Although we knew why one of these proofs was true, we weren't sure how to explicitly prove it.  However, by using proof by contradiction, we were able to convert our reasoning into a properly structured proof.  For the second proof, we came close to finding values that would work, except for one special case.  A slight modification of our values produced the correct answer.  The last difficult proof, however, had us stumped.  We knew that it was false, but we struggled to find values that would prove the negation.  Finally, less than an hour before the deadline, we found a set of values that worked. 

Also this past week we had our second and final term test.  Like Assignment 2, the test was difficult.  The first question was fairly straightforward, but the second and third questions were challenging.  I was able to solve the third question fairly quickly as I had a similar proof written down on my aid sheet.  This left me most of the test time to focus on the second question.  After negating the statement, I realized it would be easier to solve by taking the contrapositive.  I then looked for a value that would staisfy the statement, and found one fairly quickly.  I verified my answer by testing both cases of the statement and this gave me an idea as to how to structure the middle of the proof.  I finished the test with about fifteen minutes remaining, which allowed me to check over my proof structures and  add comments where necessary.

In lecture these past two weeks, we have been learning algorithm analysis.  This topic is completely new to me so I was excited to find out what it was about.  In the beginning I found it very confusing, especially the part about finding the number of steps that a function executes.  However, over these two weeks, I have become more comfortable with proving the upper and lower bound expressions. Luckily, in CSC 108, we are starting searching and sorting which has some overlap with algorithm analysis. Hopefully, this will help me better understand counting the steps of a function.

Week 7

We finished proofs this week and were given a brief introduction to sorting algorithms.  I'm excited to learn about algorithm analysis as I have no prior experience with it and it seems interesting.  The tutorial quiz this week required us to solve a proof using the structure and techniques taught in class.  Prior to this, we only had to write out the proof structure.  I was pleased that I felt comfortable solving the given proof as at the beginning of the proofs component of the course, I was daunted by how to solve proofs.  Also, our assignment 1 marks were posted and my group and I were happy and pleasantly surprised with our mark.  As well, assignment 2 was posted and we plan to start working on it on Tuesday.  Finally, on Friday, we spent the class working on a thought-provoking problem regarding pennies in two drawers and whether or not it was possible to create every number from 0 to the starting number of pennies by repeating two steps.  I'll go into more detail about solving this problem in future blog posts.

Week 6

For all my American readers, we celebrated Thanksgiving this past Monday, October 13.  As a result we had a shortened week and all my tutorials were cancelled so it was a light week.  Nevertheless, I still had two thirds of my 165 lectures.  We continued with proofs, and the more we did, the more my confidence increased.  The highlight of the week was getting back our term test.  I was very pleased with my mark as it was exactly as I had predicted because I realized my mistake after the exam.  This places me in a good position for writing the next term test, which will probably be harder, because my better test mark will have a greater weighting. 

Week 5

The first midterm was this week.  I read over the course notes, the annotated lecture slides and went over all the tutorial exercises, quizzes and the sample test that was posted.  Despite having an aid sheet with equations and examples of harder topics, I was still nervous about the test.  Luckily, our test was based fairly closely upon the sample test given, and I had written down the interpretations of the python code for the first question on my aid sheet.  I feel fairly confident that I did reasonably well on this test and I think I was well prepared.  This was my last midterm for a week, and I was looking forward to the long weekend.