Final Week

This week is the final week of lecture, except that we didn't have lecture this week. We didn't have lecture on "Make-up Monday" on Wednesday, and we wrote our last quiz on Monday. The quiz involved determining a regular expression given an NFSA. I found this quiz relatively easy and I hope I didn't make any mistakes on this one! I also received my quiz from 2 weeks ago, since I missed last week's quiz so I didn't get it back then, and I did well on it! 

I also finished the problem solving question that is required as part of the slog assignment, and posted a link to a page with my solution on the wiki provided by Professor Heap. Here is my solution:

1.       UNDERSTANDING THE PROBLEM

What is the unknown?

The unknown, in this case, is whether or not you can arrange two drawers of pennies so that one of the drawers contains 48 pennies.

What are the data?

The data is that the left drawer contains 64 pennies and the right drawer contains 0 pennies.

What is the condition?

The condition is that you can solve this problem using only 2 operations; L if the left drawer has an even number of pennies then transfer half of them to the right drawer, and R if the right drawer has an even number of pennies transfer half of them to the left drawer. Neither of these operations is possible if the drawer contains an odd number of pennies.

Is it possible to satisfy the condition?

It is possible to satisfy the condition since the left drawer contains 64 pennies, which is an even number, so you can begin the problem by transferring half of these pennies to the right drawer. However, if the left drawer began with a different number of pennies, namely an odd number of pennies, then it would not be possible to satisfy the condition so you cannot solve the problem. The problem can only be solved if either drawer begins with an even number of pennies, otherwise not even a single operation can be performed.  

Is the condition sufficient to determine the unknown?

The condition is sufficient to determine the unknown because every time we perform an operation, there are only 2 possibilities for the number of pennies in the each drawer; either the drawer contains an even number of pennies or an odd number of pennies. Since the condition is based on this, we can perform these operations repetitively to determine whether the unknown can be satisfied, that is, whether one drawer can contain 48 pennies.  

Draw a figure. Introduce suitable notation.

Let D_L represent the number of pennies contained in the left drawer, and D_R represent the number of pennies contained in the right drawer.

Separate the various parts of the condition.

Operation L: If D_L % 2 = 0, then D_L = D_L / 2 and D_R = D_R + D_L / 2.

Operation R: If D_R % 2 = 0, then D_R = D_R / 2 and D_L = D_L + D_R / 2.

2.       DEVISING A PLAN

Find the connection between the data and the unknown. You should obtain eventually a plan of the solution.

Since during each operation we are dividing the number of pennies by 2 and transferring the resulting number to the other drawer, and the resulting number of pennies that we want to achieve in one of the drawers is a multiple of 2 (48), then by intuition we should be able to achieve this number by a sequence of these operations.

Could you restate the problem? Could you restate it still differently?

You can restate the problem in mathematical terms: Can you determine two different values, x and y, where 2x or 2y is equal to 48, and 2x + 2y = 64?

Could you solve a part of the problem?

It is easier to first solve the problem when the left drawer begins with 64 pennies and the right drawer begins with 0 pennies, and you are trying to achieve 48 pennies. After solving this problem, it will be easier to solve the problem of whether it is possible to achieve other numbers in the range [0,64] and starting with a different number of pennies in the left drawer.

3.       CARRYING OUT THE PLAN

Carrying out your plan of the solution, check each step.

D_L = 64  D_R = 0                    Operation: none

D_L = 32  D_R = 32                  Operation: L

D_L = 16  D_R = 48                  Operation: L

Therefore it is possible to achieve 48 pennies in one of the drawers.

If we perform continued L operations then we have:

D_L = 64  D_R = 0                    Operation: none

D_L = 32  D_R = 32                  Operation: L

D_L = 16  D_R = 48                  Operation: L

D_L = 8     D_R = 56                  Operation: L

D_L = 4     D_R = 60                  Operation: L

D_L = 2     D_R = 62                  Operation: L

D_L = 1     D_R = 63                  Operation: L

We can perform different sequences of these operations to determine a pattern:

D_L = 64  D_R = 0                    Operation: none

D_L = 32  D_R = 32                  Operation: L

D_L = 16  D_R = 48                  Operation: L

D_L = 40  D_R = 24                  Operation: R

D_L = 52  D_R = 12                  Operation: R

D_L = 58  D_R = 6                    Operation: R

D_L = 61  D_R = 3                    Operation: R

D_L = 64  D_R = 0                    Operation: none

D_L = 32  D_R = 32                  Operation: L

D_L = 16  D_R = 48                  Operation: L

D_L = 40  D_R = 24                  Operation: R

D_L = 20  D_R = 44                  Operation: L

D_L = 10  D_R = 54                  Operation: L

D_L = 5     D_R = 59                  Operation: L

From these different sequences of operations, we can see that each sequence can have at most 6 operations. This is because 2⁶ = 64. Therefore, it takes 6 operations to reach an odd number.

Since the left drawer begins with 64 and the right drawer begins with 0, then any sequence of operations that begins with the operation R (dividing the number of pennies the right drawer by 2 and transferring that amount to the left drawer) is senseless.

Therefore there are only 5 operations that can vary, since the first operation must always be L. For each operation there are only 2 possibilities; L or R, therefore there are 2⁵ different possible sequences of operations.

Then there are a total of 32 (2⁵) possible combinations of the number of pennies in each drawer. Since there are two different amounts of pennies to consider, one for each drawer, then there are 32 * 2 different numbers of pennies possible for the 32 possible combinations. This means that there are 64 different numbers of pennies possible that can appear in both drawers.

Since the left drawer began with 64 pennies, and there are 64 possible values for the number of pennies that can be seen in both drawers, then any number in the range [0,64] can be achieved.

4.       LOOKING BACK

Can you check the result? Can you check the argument?

You can check the solution by determining the values in each drawer after performing the 32 different sequences of operations; however this will be rather tedious.

Can you derive the solution differently? Can you see it at a glance?

You can solve this problem by examining the equation 2x + 2y = 64, and letting either 2x or 2y equal to some number less than 64 that you are trying to achieve in either drawer. Since there are 64 different possible combinations of values for each x and y that will satisfy the equation 2x + 2y = 64, then you can determine that there are 64 possible values that you can achieve in both drawers. Therefore any value in the interval [0,64] can be achieved.  

Can you use the result, or the method, for some other problem?

You can use these results to solve the related problems of whether it is possible to achieve 48 pennies in either drawer or any number in the range [0,x] where x is the number of pennies you start with in the left drawer.

First, we must note that x must be an even number; otherwise no operations can be performed. Also, in order to achieve any number in the range [0,x], x must be a power of 2, otherwise it will not be possible to achieve 1 penny in either drawer, and therefore the appropriate number of operations will not be possible to achieve all of the values in this range.

For example, assume that the left drawer starts with 30 pennies. Then as soon as we perform a single operation we are done since both drawers will now contain 15 pennies and no further operations can be performed. Then in this case, only the values 0, 15, and 30 can be achieved, and only 1 operation is possible.

And that concludes the semester for the course CSC236! The only thing left to do is study for and write the exam. Overall I enjoyed this course, and I found the material interesting and the work challenging, and I'm looking forward to courses that are built on the material covered in this course, or the continuation of this course. I hope I do well on the exam!

Week 12

This week, the last full week of lecture, did not start too great. I slept in on Monday and ended up missing my quiz. I was really discouraged about this because I actually understand and enjoy the material we are covering now, and after doing the tutorial exercise for this week I wasn't expecting the quiz to be difficult.

Also, our last assignment was due this week, and it was the longest assignment of the semester for this course! It took me many hours to do and it ended up being 10 pages in length typed. I put a lot of time and effort into this assignment and I hope it pays off in the end, especially since this assignment would make up for the other assignments that I did mediocre on, as well as the midterms. In either case, I will be sure to study extra hard for the final exam since that counts for most of the final mark.

This week we continued looking at regular expressions, languages, and FSAs, and we learned how to combine regular expressions and FSAs using union, concatenation, and multiplication (*). We also learned state elimination in FSAs which is a great way to determine a regular expression for a language that is represented by the FSA. This is the opposite of what we have been doing for the past 2 weeks, namely determining FSAs to represent a language given a description of a language or a regular expression representing it. I find it very interesting to study the reverse processes of solving certain problems or formulas.

Now that the final assignment is over with, and with only 1 quiz left to go, I can finish the problem solving question required as part of the slog assignment.

Week 11

The semester is almost over! Our last assignment is due next week and we only have 1 more full week of class left. It's amazing how fast time flies when every week is so busy with assignments, quizzes and tests, and lots of studying. The second semester will probably fly by just as quickly, and then I'll already be done half of my undergraduate education. I still feel like I just started university last month.

This week's quiz was about determining FSAs given a language. I find this is a very systematic approach, which is nice because the method to solving the problem is the same for every problem. These kinds of problems can become tedious and repetitive, but they are also fairly easy.

We learned regular expressions and NFSAs this week. Regular expressions, which conveniently we are also studying in CSC207 at the moment, are a way to represent languages and the strings that are accepted by a language. NFSAs are similar to FSAs except that they are non-deterministic. The previous FSAs that we looked at were DFSAs, which are deterministic finite state automatons, where each state can only have 2 transitions for binary strings; the transition of a single digit 1, and a single digit 0. NFSAs differ in the sense that every state can have multiple transitions; it can have multiple transitions for the digit 1, multiple transitions for the digit 0, and even a transition for the empty string ε. So far, I find these concepts fairly easy to understand, and it really helps that we learned regular expressions in CSC207 recently. 

Also, regarding the problem solving question, we are required to use G. Polya's approach to sovling the problem. I know that some students have written algorithms or programs to help them solve the problem, but I think that this problem can be solved without them, and that is the approach I will take. 

Week 10

This week was another short week since we had Monday and Tuesday off as part of our reading "week". I find it ironic that our reading week for first semester is only 2 days, but to be fair it is called a break by the university rather than a week. So, since we did not have school on Monday, we also didn't have a quiz this week, and we didn't get our quizzes from last week returned.

This week we learned formal languages and FSAs, also known as Finite State Automatons. FSAs represent "machines" that accept a certain "language". I use quotation marks here because these names represent things other than what they usually represent. A language accepts only a certain set of strings, so we are dealing with sets and subsets once again. Having lots of experience with sets and properties of sets in the past from last year's course, CSC165, and this year's course statistics course, STA247, I feel comfortable with this material and I think I am grasping it fairly well from the very beginning.

I also find FSAs are very logical and systematic in the way that you draw them and analyze them. It is fairly easy if you approach each problem involving an FSA by taking it step by step, either through the the strings that a language accepts, or through the FSA to determine a language that it represents. Another new concept we learned this week was transition functions, which I will have to read some more about because I have to admit, I did not pay complete attention in lecture when this was taught.

Week 9

I wasn't here this week for the midterm on Monday, so I wrote the midterm on Thursday instead. The midterm was not what I expected whatsoever, and I was not prepared for the material that it covered. Since I wrote the evening section's midterm, I expected the evening section to cover similar material as the morning section at the same pace, however, the midterm covered material that was ahead of what the day section midterm was supposed to cover. So once again, I don't think I will do too well on this midterm.

The reason I missed class was because I flew out to Seattle to due several interviews for a summer internship. I got the internship so now I have no regrets about missing class. I also missed lecture on Friday, and when I look over the notes from the day section's class, they were not very descriptive. So I think I'm going to study the evening section's notes for this week.

This week we learned proving partial correctness of an algorithm that determines an nth power of an integer. Really all that this involves is proving the loop invariant, but in most cases we must determine this loop invariant by tracing through the algorithm and noticing what is consistent at the end of every iteration of the loop in the algorithm.

I also look at the problems that Professor Heap posted on his problem solving wiki, and I think I will solve the Penny Piles problem. Here is the problem:

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 the following two operations:

L

If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.

R

If the right pile has an even number of pennies  transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?

You may record your problem-solving excursion below the horizontal line.

My intuition tells me that it is impossible to achieve odd numbers of pennies in either drawer, except for 1 penny in one drawer and 63 pennies in the other, since 64 is a power of 2 and you can only divide by 2 if the drawer contains an even number of pennies. I will think some more about this problem, and I will start the problem-solving excursion this week. 

Week 8

This week we started one of my favourite concepts from last year; proving correctness of algorithms! It involves proving preconditions, loop invariants, post-conditions, and termination for different algorithms, and this week we did binary search. We learned how to prove these for both iterative and recursive binary search algorithms, and once again, recursive is more complicated than iterative.

Also, our second assignment was due this week, and I know I didn't do as well on this one because after I submitted the assignment, I learned that we were not supposed to use the master theorem to answer the last question. I thought the question was rather easy if we used master theorem to prove it, but at the same time I don't see reason to learn a concept if we can't use it in the course. I guess since the master theorem is a shortcut, it is considered "cheating" to use it in certain proofs.

This week's quiz involved the master theorem, so I found it fairly easy. I lost marks on last week's quiz since I made some mistakes. I need to be more careful in avoiding making silly mistakes that cost me marks. I should also start working on the problem we're supposed to solve as part of this slog assignment.

Week 7

This week we continued learning the master theorem, and we also learned a new concept developed by Guass which helps reduce the time complexity of a function. We have been looking at a lot of divide and conquer algorithms which are more complicated to determine the time complexity, but a lot more efficient.

It really helps to have learned these algorithms last year and to know the time complexity for each, because it makes it easier to understand how to solve proofs of equations representing these time complexities. I find these proofs a little tricky since they involve recursion, and I'll need to read more about them or look at examples in the textbook.

One thing I forgot to mention in last week's post is that we received our graded midterms, and as I expected I lost marks on the second question. I'll be sure to be more prepared for the second midterm. Also, I did well on last week's quiz, and I think I did well on this week's quiz as well. This week's quiz was on developing a closed form using unwinding, which I don't have difficulty with.

Week 6

This week we continued learning time complexity and unwinding to develop general equations for time complexity, but with more complicated problems. We applied these concepts to merge sort, and we also learned a new concept; the master theorem.

So far the master theorem is one of my favourite concepts in this course because it allows you to determine the time complexity by plugging in values into a formula, and these values are easy to determine as well. It's times like these when I am extremely grateful for the people who came up with these formulas and short cuts to solving problems, but it also amazes me at the fact that they developed these formulas. I also wonder how they came up with them and how much time it required.

Our quizes from last week were returned this week, and I did well on last week's quiz although I was a bit unsure about the material we learned last week. I spent some time reading about the concepts and now I am more familiar and comfortable with these concepts. I think I did well on this week's quiz as well.

Week 5

This week was short since Thanksgiving was on Monday and we only had one lecture this week since our first term test was on Wednesday. I found the term test relatively easy for the most part, I believe I did well on the first two questions, but I wasn't sure about how to solve the last question so I probably lost marks there.

This week we started learning time complexity for recursive functions. We also learned the concept of unwinding to develop a general formula for the time complexity of a recursive function, and then how to use induction to prove that the formula is correct. I'm having a bit of trouble trying to grasp these concepts, and I've never fully understood the concepts of time complexity in relation to log functions. I'll have to do some more reading about these concepts in the textbook and practice problems.

I feel like this will eventually lead to proofs about constants and breakpoints, which I didn't enjoy too much last year. However, if it does lead to those topics then I'll do the reading and become completely familiar and confident with the material.

Week 4

The second tutorial and quiz was not as great as the first. We have a different TA for our section, and although this TA explains the questions and concepts well, I prefer the teaching styles of the previous one. I don't think I did well on this quiz because I was expecting a different type of question, and now all I can do is hope for the best!

This is unrelated to the course itself and course material, but it's already been a month since university started! I can't believe I am already done with one third of the semester and exams are only 2 months away. One of my favourite things about university is that the semesters themselves are shorter, but the amount of learning we do is the same if not greater.

And back to CSC236. This week we learned Structural Induction and how it can be used to solve problems with sets (number of variables and number of operators). This theory uses Mathematical Induction so I find it relatively simple. We also did an example about the Fibonacci sequence, which is a recursive sequence so it relates to concepts we learned in computer programming last year. At first I found it difficult to grasp the concept of recursion, especially when it comes to finding the base case to solve the problem, but given a formula in this course for the Fibonacci sequence it is much easier to find the base case. I'm going to try and apply this strategy in the future when trying to find a base case for a recursive method in programming. 

Once again, this course directly relates to programming and I can't complain! I think that is one of the reasons why I didn't enjoy CSC165 last year too much; it involved proving a lot of theories about math rather than programming concepts. 

Week 3

Tutorials started this week, and with the first quiz out of the way, we're moving on to well-ordering. I found the quiz easy, and I like that we take the time to go over the tutorial problems and answer questions before we right the quiz.

I missed parts of lecture this week because I showed up late to class, so I don't fully understand well-ordering. The theory seems simple but I have not practiced any problems with well-ordering myself, so I will be sure to do that next week. We also did more examples with mathematical induction this week.

What I find interesting is that many problems, including some on the assignment, can be solved using either complete induction or mathematical induction, or even some other form of induction according to the professor. At first I thought each theory only worked for certain types of problems, but in the end they are all following the same basic concept (induction) with a different approach and equation.

I'm also happy about the fact that all of the formulas we learned so far are not hard at all to remember. I find it helpful to understand what the formula actually means or is trying to prove as a way of remembering it.

Week 2

Tutorials were supposed to start this week, but there was a change in the schedule so we don't have a quiz this week. I think that also means we will have only 8 quizzes this semester instead of 9. This week we learned Complete Induction. One of the examples that the professor did in class this week was with full binary trees. It's much different, and in a way more complicated I find, proving theories about programming concepts than mathematical concepts. With math it's easier to prove an equation by manipulating the equation, whereas with programming you have to grasp the idea of the programming concept and visualize it, such as in the case of trees.

I'm happy to see proofs about programming concepts, since I did take Computer Science to learn how to program, because it better helps me understand the concepts themselves and I can find an extra use of and benefit from this course. 

Back to Complete Induction, although the structure of the theory is quiet different from Mathematical Induction, I think they are actually quiet similar, especially when it comes to proving mathematical equations through algebraic manipulation. 

Introductory Week

I was going into CSC236, feeling skeptical about how well I would do in this course and how much I would enjoy all of the rigorous proofs where great portions of the proof seem redundant. But after the first lecture and taking a look at the course outline and marking scheme, I have a good feeling about this course.

The first concept we learned this week was Simple Induction (aka Mathematical Induction), and it holds true to its name because it is simple. I must admit I like algebra, so a lot of the proofs we do with Mathematical Induction I actually find enjoyable. I never though I'd say this about any kind of proofs. I'm actually looking forward to next week's tutorial and quiz, and it doesn't hurt that we don't have lecture on Wednesday.