This week, I had my second term test in CSC 165 and I think I did pretty well with it. Although I had some difficulty with Question #3 of the test, I understood that question after few minutes of struggling as I already practiced prove/disprove using many practice problems, assignments and previous tests. I hope to achieve A in this test as well. Achieving great marks on both test is one of my goals in CSC 165 as these scores represent how much effort and interest I have put in CSC 165.
This week, we learnt about proving worst case and it was quite easy as it was similar to proof I have done before during the last week to prepare for the test.
Paper Folding (Problem-solving Episode)
This week, I would like to demonstrate my Polya's Method on Paper Folding problem that we did previously during the lecture. This is done to reinforce and check my understanding and approach to solve the problem.
1. Understanding the Problem
What we know is that using a paper strip, as we fold one by one, we have to find a pattern on how crease points being vertex up or down differ. I decided to label vertex up crease point as u and vertex down crease point as d. In this question, the condition is that when we fold the paper strip, one end of the strip has to meet the other end of the paper strip. If this condition is not met properly, then the result for the problem would become messed up. We have to come up with a method where we can exactly predict the fold pattern just by looking at the number of fold it has been done on the paper strip. To do that, I first thought that I could try some of the very first few folding to analyze the pattern. The unknown is the pattern that corresponds to the specific number of fold.
2. Devising a Plan
The first plan I came up with is that I try folding up to 4 times and observe whether there is any similar patterns among all these folds I have done. Next, I will record crease point vertex up and down for every folding I did. With the data collected, I will organize the data in a way that I can analyze its pattern. Then, I will try what I need to put in addition in the sequence from the first fold to the second fold. Then I will do the same thing with the second fold and the third fold and so on. Also, I will also count the number of d and u for every fold I do to analyze the pattern.
3. Carrying out the Plan
I exactly carried out the plan I devised and got the results shown below.
1st fold: d
2nd fold: d d u
3rd fold: d d u u d u u
4th fold: d d u d d u u d d d u u d u u
Just with this information that is organized like this, I was not able to find out whether these folds even have patterns or not.
I tried approaching the problem by counting the number of d and u present for each folding.
1st fold: 1d
2nd fold: 2d 1u
3rd fold: 3d 4u
4th fold: 8d 7u
However, I quickly realized that my devised plan is wrong for this part as counting the number of d and u present in the fold does not tell us anything about the patterns.
Hints for this question were given. Hint #1 was thinking recursively. Surprisingly, hint #1 was exactly what I did up until now. I approached the problem recursively. However, the problem with my approach was that I only thought that d and u would be added up to the start and end point of the folding patterns. Hint #2 was thinking symmetrically. This hint sparked my mind. With hint #2, I started to look symmetrical pattern, I immediately organized the above information like below.
Numbers 1, 2, 3, 4 represent the number of fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
With the information organized like above, I was able to find that the very first d we got for 1st fold was present in the middle section of each of the folding we did up to 4th folding. From the first to the second fold, we see that adding d in front of d (from 1st fold) and u after d (from 1st fold). Likewise, from the second fold to the third fold, we add d in front of d and u(from 2nd fold) and u after d and u(from 2nd fold). But I realized that it is hard to explain in words. Colouring d and u to represent my explanation of the work was a better way.
Red d represents d from 1st fold
Orange d and u represent d and u that were added during 2nd fold
Green d and u represent d and u that were added during 3rd fold.
Black d and u represent d and u that were added during 4th fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
As we go on, we add d in front of d and u that were added just before and add u after d and u that were added just before.
With this approach, we can find the d, u patterns for 5th fold, 6th fold, 7th fold and so on. But then, it is really hard to find the d, u pattern for 100th fold or 250th fold just with thinking recursively and thinking symmetrically. However, using Python 3 program, we can write the code and execute to get the patterns for 100th fold and 250th fold. Of course, human can get the patterns for 100th fold and 250th as well, but it takes much time and errors may occur during the process. So I tried my best to come up with mathematical expression for this pattern. However, I was not able to as this gets more complicated as the number of fold increases.
4. Looking Back
My solution for this question is correct as this clearly demonstrates the approach and the result. My argument for this claim is correct as I have tried number of folds from 1 to 4. With these as supporting evidence, we can conclude that the patterns for the next fold follows just like what I demonstrated above. I can also check the result for 5th fold and compare the result with the expected 5th fold value I generated using the patterns I found.
Expected Values for 5th fold generated using the patterns I found
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
Result I got by folding and recording for 5th fold:
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
These two shows exactly same patterns. With this, we can conclude that my argument is correct.
The problem with this approach is that it is very difficult to generate the pattern for 1000th fold as we have to do this starting from 1st fold and go on to reach 1000th fold. We cannot use this solution for other problem. This solution is only for the paper folding problem. However, the approaches I took can be used in various Computer Science problems.
Solving this problem has enabled me to review Polya's Method once again to analyze and approach the problem in Computer Science.
No comments:
Post a Comment