Friday 28 November 2014

The Penultimate Post - A Paper Puzzle

My SLOG entry this will be my problem-solving entry. I am going to be writing about the paper folding problem we talked about back in week 3. I will try my best to follow George Pólya's steps to problem solving.

The problem statement:

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."

Step 1: Understand the problem
The problem is to try and predict the sequence of ups and downs for a given number of times you fold a strip of paper in half. The paper should always be folded so that the end that was in your left hand is now on top of the end that was in your right hand because this will affect the results.

Step 2: Plan a solution
To solve this problem I folded the paper and wrote down the sequence for the first few folds. I then tried to see if there was a pattern in the sequence.

Step 3: Carry out your plan
Below are the sequences for the first 4 folds.

Folds Sequence
1 D
2 UDD
3 UUDDUDD
4 UUDUUDDDUUDDUDD

Using 1 fold as our base case, the formula for this sequence would be to first take the previous sequence and mirror and flip it (the sequence backwards and D's become U's and vice-versa) and then append a 'D', and then append the previous sequence to the end.

The following is my implementation using recursion in Python.

def fold_sequence(folds):
    """ (int) -> str

    Return the sequence of the folds for a number of folds.

    Parameters:
    - folds: the number of times the paper is folded in half
    """

    if folds == 1:
        return 'D'
    else:
        prev_seq = fold_sequence(folds - 1)

        # reverse the previous sequence
        prev_seq_rev = prev_seq[::-1]
        prev_seq_rev = prev_seq_rev.replace("U", "d")
        prev_seq_rev = prev_seq_rev.replace("D", "U")

        # change the U's into D's and D's into U's
        prev_seq_rev = prev_seq_rev.replace("d", "D")
        return prev_seq_rev + 'D' + prev_seq


if __name__ == '__main__':

    while True:
        num_folds = input('Enter number of folds: ')

        # Convert into int
        num_int = int(num_folds)

        if num_int >= 1:
            print(fold_sequence(num_int))

You can test out the code at the following link: http://repl.it/1nu/4

Step 4: Review any solution you achieve
I think my solution is a correct one and the program I wrote should be able to convince someone that it gives the correct output.

To further extend this problem and further convince any more skeptics, I wrote a program in Python utilizing the ImageDraw module that takes an input for the number of folds and outputs the visual representation of the folds. The following are a few examples of the outputs from the program.

1 fold

4 folds
6 folds

8 folds (Dropbox link)
10 folds (Dropbox link) Note: the original image is over 40,000 pixels long

To see the source code click here: https://pastee.org/k222h

Thank you for reading.

EDIT: I had a look around at a few other SLOGs to find some posts that others had made on this puzzle. I found a few posts here and here, and these posts all made the same solution I made so it is good to see that my solution seems to be the correct one.

Friday 21 November 2014

Week 11

So this weekend CDF was down so the course website and MarkUs could not be accessed which was inconvenient. We also got a break from classes on Monday and Tuesday which was a pleasant surprise. It was back to lectures on Wednesday where learned about the halting problem as well as countability.

I think the halting problem is the one of the most interesting topics we have learned so far. The halting problem is the problem of determining whether given a function and an input, will the function halt or continue to run forever. One would think to just run the function and if it halts then you know it will halt. The problem is that if it doesn't halt, you cannot tell if it will eventually halt or continue running forever.

I think this post here http://soohamrafizslog165.blogspot.ca/2014/11/week-11-halting-problem-and.html gave an interesting explanation and visualization for the halting problem.

Countability was also an interesting topic. A set is countable if it has a one-to-one correspondence with the set of natural numbers and it is onto the natural numbers, which means every number in that set can be reached from at least one natural number. We used this to show that the size of the set of even natural numbers is equal to the size of the set of natural numbers, which is not very intuitive. There are also some sets that are not countable. Cantor used diagonalization to show that there are infinite sets such as the set of rational numbers that are not countable.

Friday 14 November 2014

Week 10

So this week we got our second midterm back. I managed to get perfect once again so I am happy about that. In class this week, we looked at proving big O for non-polynomial functions. We used L'Hôpital's rule to help prove that 2^n was in big O of n^2. L'Hôpital's rule uses derivatives to evaluate limits and is defined as:

Two other bounds we talked about were big Omega and big theta. A function f is in big Omega of function g  (f(x) = Ω(g(x))) if it is bounded below by function g. A function f is in big theta of function g (f(x) = Θ(g(x))) if it is bounded both above and below by function g.

Another interesting thing I learned this week were some of the properties of big O.

The reflexivity property says that a function is in big O of itself, which makes sense since we can easily see that if we multiply a function by a constant, then the original function will always be less than the new function. Reflexivity also means that a function is in big Omega, as well as big theta of itself.
The transitivity property says that if function f is in big O of g and function g is in big O if h, then function f is in big O of h. We can prove this by choosing the constant to be the product of the two constants for the first two functions and the breakpoint to be the maximum of the two breakpoints for the first two functions.
That's it for this week. I have one midterm left for one of my courses and so far I have done well on them. After that it will be on to exams, something I am definitely looking forward to!

Friday 7 November 2014

Week 9

So this week we had our second midterm. I found it to be average in terms of difficulty. The last two questions were very similar to the assignment questions, (the last one was near identical), so I think as long as you went over the solutions, it was very easy to prepare and do well on this midterm. Again, I ended up using very little of what I put on my cheat sheet but I guess it served its purpose of helping me get prepared.

This week's tutorial was very helpful in clearing up some of the problems I had with counting the number of steps for the sorting algorithms. I think the way our TA explained it was easier to understand than the way explained during lecture. With the midterm over, we only have one more assignment and the final exam left, but so far I think I have learned the most from this course out of all of my courses and the methods of problem solving I learned from this course can be carried over into my future courses.

One of the more interesting SLOGs I have found so far is here http://www.reddit.com/r/journeythrough165/. I think I find blogs that aren't hosted on blogspot (who even does that?) are easier to read just because of the change in layout.