Problem Solving Episode

Having the slides printed out for Friday's lecture was very helpful, so I'll be doing that from now on.

Earlier in the semester, we were given a paper folding problem to solve in class using Polya's problem solving method. Today I will write up the process I followed in solving this problem. A copy of the problem can be found on Professor Heap's problem solving wiki.

Step 1 is understand the problem. I need to find the pattern of "up" and "down" folds created by folding a strip of paper a number of times. The paper should always be folded exactly in half, so that the left side folds over the right. The exact number of folds to make is not specified; instead I should be able to answer for any number of folds. Therefore my solution should be in the form of a method or algorithm which can return the pattern based on any given number of folds.

Step 2 is to create a plan. My plan was to carry out a number of folds, then compare the sequence of creases for n folds to the sequence for n-1 folds. There should be a pattern since the sequence for n folds is formed by folding the sequence for n - 1 folds. The total number of creases for each n folds must be a function of n. Also, since the paper is initially folded in half, every subsequent fold will affect both halves of the unfolded paper. Hence, the half to the left of the initial "down" fold must have some relation to the half to the right.

Step 3 is to carry out the plan. I recorded the sequence of up and down folds in a table for each number of folds. First, I discovered that the number of creases for any number of folds n was equal to (2^n) - 1. It was also apparent that the initial "down" crease made by the first fold was always in the centre of the unfolded strip. Because there are always an odd number of creases, there are an equal number of creases on both sides of centre. Comparing the left side to the right side, I found that the left side was the same as the right side in reverse order, with the up and down folds interchanged. When I compared each sequence to the one before it, I found that the right half of the sequence for n is identical to the complete sequence for n - 1. Based on this, the method for finding the sequence of up and down folds for any number of folds n can be expressed by the following recursive algorithm:

def folds(n):
    if n == 1:
        sequence = ["down"]
    else:
        right_side = folds(n-1)
        left_side =  []
        i = len(right_side) - 1
        while i >= 0:
            left_side.append(right_side[i])
            i = i - 1
        left_side = invert(left_side) #for each word, change "down" to "up" and "up" to "down"
        sequence = left_side + ["down"] + right_side
    return sequence

Step 4 is to look back. The relationship between the two halves of a sequence for n folds makes sense, since when folding n - 1 times, the two halves overlap perfectly. I think a solution could also be derived by inserting new creases between each existing crease for the next fold.

Week 9; having some trouble.

The following SLOGs all mentioned delta-epsilon proofs when talking about assignment 2.

http://165timeslogically.blogspot.ca/

http://csc165wumeng.blogspot.ca/

http://csc165justinsong.blogspot.ca/

I didn't remember learning about this in class, so I looked it up online. It turns out we did learn about it after all during the lectures, but I didn't realize it was a particularly important type of proof. Sometimes it is hard to know what I should take notes on in class. I do not like Professor Heap's method of preparing slides before class and annotating them during the lecture. It is impossible to write down the important points from the slide and pay attention to the lecture at the same time, especially when he quickly passes over the slides with a lot of text in order to write on the more empty ones. If I don't write notes, I am not able to retain the information. I have tried reviewing the annotated slides on the website after class but they do not make as much sense without the context of what the professor was saying as he wrote them.

This problem is even worse now that we are analyzing program run time. There isn't time to copy down the code to paper, and the annotations on the slides are meaningless after the lecture. I need to print the slides before class and make my own annotations, but mine may not be any more useful on later review. I have already noticed I do not understand how to find big-O and big-Omega for an algorithm as clearly as I understood things at the beginning of the course. I hope I can find a way to follow along better because I really struggled with this week's quiz.

Week 8

In Wednesday's lecture, we wrote a proof of the upper bound on the worst-case performance of a sorting algorithm. It is often impossible to determine the exact worst-case, but we can approximate it by finding upper and lower bounds on the value.

I finished assignment 2 today. I had already completed most of the proofs but there was one that I couldn't solve until today. It seemed like the more obvious a claim was, the harder it was to prove. Next I need to prepare for the test next week. I feel confident about all the material covered so far but I need to make sure I haven't forgotten any information.

Week 7

Yesterday in class Professor Heap introduced the topic of the efficiency of sorting algorithms. Different algorithms may take vastly different amounts of time when sorting large amounts of data. The most significant factor is the number of steps involved in the sorting process. When we compare two algorithms, it is the most helpful to compare the number of steps involved in sorting the worst arrangement of items for that algorithm to sort, that is, the one that will take the longest. The worst arrangement is different for each algorithm, as they sort in different ways.

Week 6

I don't have much to talk about this week since there were no classes on Monday and no tutorial on Tuesday. Yesterday's class was on disproving claims using the proof format we learned in the last two weeks. To do this, one simply has to write a proof of the negation of the claim. Obviously, if the negation can be proven true, then the claim is false.

I checked the test solutions on the course website, and I believe my answers were all or mostly all correct, though my explanations were more detailed than required.

Week 5

I wrote my midterm test yesterday. I was given extra time thanks to accessibility services, which was good since I used almost all of it. Most of my time was spent explaining my answers, so I will need to be more concise next time. Nevertheless, I was able to finish the whole test and I think I did very well. There were no questions which I did not know the answer to. Completing Assignment 1 was excellent practise.

We began learning the structure of a proof last Friday and continued on Monday, and this week's tutorial exercises and quiz were on this topic. These were much simpler than the exercises from previous weeks since we were merely asked to write an outline for a proof, not to actually prove anything.

Week 4

Monday's lecture was on transitivity, that is, if P implies Q and Q implies, R, then we know that P implies R. As part of this discussion, we walked through simplifying a statement by turning implications into disjunctions. I'm glad we did this because I had been struggling to understand the relationship between implication and conjunction and disjunction. I learned that "P implies Q" has the same meaning as "not P, or Q". I compared these statements with a truth table and they are both true under the same conditions and false under the same conditions.

Understanding this relationship made my tutorial exercises and assignment much easier, since I had found it hard to understand the exact relationship between an antecedent and its consequent. Now, I can express complicated implication statements in a more familiar mathematical form.