Thanks for reading and marking my slog! :)

Problem Solving- Paper Folding

Problem:
Grasp one end of a strip of paper between the thumb and index finger of your right hand, and grasp the other end between the thumb and index finger of your left hand. Fold the strip of paper once, so that the end of the strip that was in your left hand now is on top of the end that was in your right hand, and the thumb and finger of your left hand now grips the fold at what was the middle. If you were to unfold the strip of paper now, it would have a single crease in a direction you might want to call “down.”
If you carry out the fold several times, always folding the strip so that the end of the strip that is in the left hand is placed over the end that is in the right hand, what pattern of “up” and “down” folds do you get? For example, if I make two folds, I get a left-to-right pattern of “up,” “down,” “down.”

Trying out and checking the sequence:

Number = How many half folds
U and D = Represents the direction of the crease

1: U
2: UUD
3: UUDUUDD
4: UUDUUDDUUUDDUDD
5: UUDUUDDUUUDDUDDUUUDUUDDDUUDDUDD
…

As we can see, it is evident that the pattern of the folds is reflected by after the middle of the fold. In the third pattern, we see that the folds leading up to the middle fold (which is always U) is reflected in the same sequence after the middle fold. UUD reflected is DUU. As well, I also created a table representing the difference between the number of folds each time I fold the paper in half. I was evident that the difference in the number of creases from on step to another doubles. The data is shown below:

Number              Difference in number of creases from
of half folds        one half fold to the next

1:                        0
2:                        2
3:                        4
4:                        8
5:                        16
6:                        32

Actual number of folds from one half fold
to the next

1
3
7
15
31

After observing this, we can say that the difference in the number of creases double everytime a half fold is done. They also seem to all be powers of 2. And everytime we subtract one from the difference in the number of folds, it produces the actual number of folds from the previous half fold. For example, in the second half fold if we take the difference in the number of creases (which is 2) and subtract one, we end up producing the number of actual creases from the previous half fold (which is 1 in this scenario)

Observing my results, it is possible to predict the crease pattern after a certian number of folds. It seems that the first half fold pattern continues onto the next fold pattern, except a center crease is added along with the reflected first pattern. For example:

U(this is the first half fold pattern) -> UUD(the second half fold pattern)

U(first pattern) + U(middle crease) + D(reflected first pattern)

This scenario seems to be true for my tests with the paper folding.

So, with these observations, we can calculate the number of folds (not the sequence) after each half fold:
n = number of folds
2^n is the difference in the number of folds in each half fold.
So 2^n – 1 should produce the number of folds.

To check if this is true:
if n = 2
# of folds = 2^2 – 1
= 4 – 1
= 3
3 is the number of folds when there are 2 half folds.
If we were to try to find the number of creases in n = 30:

# of folds = 2^30 – 1
= 1073741823

This calculation and solution is a prediction and we will never know if it will be true for all values of n because n can go to infinity.

Week 12 Update

During the last week of lecture, I continuously developed more knowledge on the topic of computability and counting. Through Cantor’s example, Cantor was able to prove that some functions are not countable. I personally do not quite understand the principle where a set is only countable when it can be displayed on a list. I will have to go into office hours or get aid from peers to fully understand this concept and its link to programming and also induction.

Throughout this week, majority of the third assignment was completed which greatly aided my understanding of the last 3 weeks of material taught in the lectures. I have many upcoming exams so I am hoping that I will be able to fully comprehend induction and counting soon.

Week 11 Update

throughout week 11 of lecture, I learned about how some programs can have non-computable programs. If we have a function that produces an output, but don’t know how to compute the output of the function, then the function is considered non-computable. This was in the same case as halt where the user may know the output, but the process of getting the output was impossible. This led to the introduction of reduction where if there is an non-computable function, f, then a function g, implemented into f must also be non-computable. For me, I found the topic of reduction very interesting, but difficult to grasp. But after discussing question 6 on the third assignment, I thoroughly understood the topic of computability.

On the contrary, I did not understand the idea of counting and how infinite sets are not equal to one another, even though their cardinality are the same. More specifically, I do not understand the difference between 1-1 and onto, although their definitions are given. To comprehend this idea of counting, I plan to head into office hours and receive some aid.

Week 10 Update

Throughout this week of lecture, the concept of Big-Oh was continued further and along with Big-Omega. To solve for Big-Oh of non-polynomial functions, it was taught that we must manipulate the definition of a limit to eventually equal to the definition of Big-Oh or Big-Omega. These proofs were fairly simple to conceptualize and comprehend since the concept remained the same as the previous Big-Oh proofs.

I found Big-Omega extremely similar to Big-Oh. The most obvious difference between the two is that Big-Omega states that a function is lower-bounded by another, while Big- Oh states the opposite. The definition of both these bounds are practically the same and therefore, it was easier for me to understand Big-Omega. As we approach the final weeks of the semester, I hope that we will learn more about upper and lower bounds since I these topics appeal to my interest.

On the tutorial quiz, I was very displeased with myself as a result of my misinterpretation of the question. I thought the question asked for the bound where the function is below and above another. However, the question was actually asking for Big-omega.

Week 9 Update

Throughout this week, I found that the concepts were extremely similar to those last week. It continued on the concept of Big-Oh and maximum slicing. Maximum slicing is another topic that was very difficult to understand for me. I understood that maximum slicing was much like worst-case scenario in programming; however,  I did not understand how to derive the equations that count the number of steps taken throughout the program. Specifically the use of ceilings confused me the greatest. On the contrary, I found the proofs helped clear more of my understanding of Big-Oh and how a function is bound by another. The Big-Oh proofs with polynomials were simple and only required basic algebra to solve. I hope throughout next week, this topic will be cleared and easier to comprehend as we progressively dive more in-depth with Big-Oh and program efficiency.

This week’s tutorial was based on maximum slicing and I found the quiz was very hard for me. I plan on coming into office hours and talking with fellow peers to clarify the concept.

Week 8 Update

This was an extremely challenging week for me and the concepts taught throughout the lectures were very difficult to grasp. The concept of Big-Oh was the most challenging to comprehend. I did not understand what Big-Oh exactly was and what was it’s purpose. As well, how does Big-Oh directly relate to programming? Many of my questions were answered during the time in tutorials and as well office hours. I was able to partially understand Big-Oh and its relation with programming.

As well, by understanding the concept of Big-Oh, I was able to also solve and comprehend the proof of Big-Oh during my tutorial. Throughout next week, I hope to clarify more on Big-Oh.

Week 7 Update

During this week of lecture, it was nice to overview the different methods in solving proofs depending on their specific cases. This includes conjunction, disjunction or implication statements which all have different outlines that are followed to prove them correctly. However, one idea that confused me very much was the idea of counting steps in code and worst-case scenarios. I did not understand why we were required to count each step in a given code. But I realized that the amount of steps taken in code tremendously impacts a programs efficiency. If there are less steps, then the program must take much less time to run. I was a bit more clarified on this topic when going in Professor Heap’s office hours.

Week 6 Update

Throughout this week of lecture, many new concepts were taught to me. This includes ideas such as the definition of a floor and proof by cases. Proof by cases was a very interesting concept and I thoroughly enjoyed solving proofs with different cases. Specifically the proof of a conjunction. For me, this week was also partially difficult for me as a result of the misunderstanding of the formal definition of limits. As a student taking only MAT135, I found this concept hard to grasp at first. However, eventually I came to realize that the definition of a limit taught in MAT135 is quite similar to MAT137. That is, both definitions state that a limit is a value in which x approaches as it shifts closer to that value. In the formal definition, it is portrayed much differently and therefore, it was at first difficult for me to comprehend. In this weeks tutorial, I enjoyed solving the given proofs with my peers.

Week 4 Update

Throughout this week, I was first introduced to the idea of proofs. Proofs is a way to communicate to another person on why you believe a certain claim is true or false. To begin the proof, we learned how to create and outline/template which allowed us to organize parts of the claim. For me, found it first quite difficult to think logically in order to solve a proof. This could possibly be caused by the fact I did not take the course MAT137, which revolves around the use of proofs. However, in this weeks tutorial when the TA explained the proof layout, I was able to comprehend the mechanics of proofs. By organizing the proof and understanding each component of it, I am now beginning to solve simple proofs.