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.