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.