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. 

Week 4

Assignment 1 was due this week.  My group and I spent a few hours after tutorial on Tuesday adding explanations and making sure our answers were correct.  After submitting our answers, we felt fairly confident that we had correctly answered many of the questions, although there were a few that we were unsure of. 

This week finished off the implication / disjunction / quantifiers material and we started proofs.  I was a bit nervous because I had heard that proofs were essential, but difficult.  In lecture we were introduced to the basic structure of a proof and solved some "simple" proofs, such as proving that n squared is odd if n is odd.  I had no trouble with the structure or the math of the proof, but was at a complete loss as to where to start solving the proof.  One day, I had a revelation while studying for the upcoming midterm.  I realized that you start solving the proof from the assumptions you make at the start.  This epiphany made me much more comfortable with solving proofs, although I was still relieved when I found out they were not going to be on the midterm.

Week 3

Usually, I don't like group work because the random selection of members results in many incompatibilities.  With assignment 1, I was able to choose to work with people I knew I would not have any conflicts with.  My group members and I have similar work habits and all participate equally in group discussions.  As a result we were able to create a rough copy of the answers after two hours of concentrated work.  We plan to finish the assignment after our tutorial on Tuesday.

In lecture this week, we covered the rules of Boolean algebra and were introduced to truth tables.  The problems started out fairly straightforward, but the tutorial exercises were nothing like the examples.  I decided to solve the tutorial exercises using truth tables because it was the more familiar option.  However, in tutorial, it became clear to me that using Boolean algebra was faster and the better approach for more complex problems.  Although truth tables are more straightforward and are valid approaches to solving the problems, as more variables are added, the truth tables get larger and the likelihood of making an error and the time it takes to solve the problem increases. 

Week 2

The main topic this week was writing english statements using symbols.  At first I thought that this would be fairly straightforward, but once the tutorial exercise was posted, I realized that I was confused as to what to do for most of the first question.  I asked my friends how they answered the questions, but they and many other people were as confused as I was, so I decided to wait for Monday's lecture to see if it would be explained.  Unfortunately, on Monday, we moved on to new material, and I remained confused.  As such, I decided to focus on other subjects and wait for the tutorial to clear up any questions I had.  On the morning of my tutorial, I was contemplating the tutorial questions while commuting to campus and came up with what I believed was the only possible answer to one of them.  The only problem was that I was unsure if my solution was within the rules as no similar type of question had been covered in lecture.  It turned out that the answer I reached while on the TTC was the correct answer to the question and was part of the basis for answering later questions.  Sometimes, when I am stuck on a particular problem, I switch to another topic or activity and many times the answer comes to me in the most unexpected places. 

Week 1

Welcome to my CSC 165 Course Log.  As of the writing of this entry, I've been attending this class for almost two weeks.  Last week, we discussed existential and universal claims.  An exercise was posted that required us to depict the truth of  such a claim (or lack thereof) by drawing venn diagrams.  I attempted to solve the question, but found that I was confused about this concept.  The next day, it was explained in lecture and we went through a number of examples, after which I felt I had a better grasp on the material.  Later, at home, I reattempted the exercise and was able to complete it with a fair degree of confidence.  When we took up the answers in tutorial, I was pleased that I had correctly answered the question.