Closing Thoughts

I would like to comment on Assignment 3 in a little more detail now that the deadline has passed.
I think the key to question 6 of Assignment 3 was to take the description of function meaning_of_life as literally as possible: "Return True if f(I) returns True, False otherwise." It can supposedly analyze function f and determine whether f will return 42 without needing to execute f. If meaning of life works exactly as described, then it should return false on a function like this:

def procrastinate(I):
    while True:
        pass
    return 42

If procrastinate could reach line 4, it would return 42, and meaning_of_life would return True. However, meaning_of_life can see that procrastinate will never reach line 4, and so meaning_of_life returns False. From here it is trivial to invent  a working halting function using meaning_of_life, and since we know a halting function can't exist, we also know that meaning_of_life can't exist.

I'm glad to be finished writing these SLOGs every week. I have benefited from reading other people's posts but it's been a chore writing my own. I really wish the rubric had been posted at the beginning of the semester because I would have done things a bit differently if I actually knew what I was being graded on. I don't think it's fair to give vague instructions for most of the year and then go "Surprise! Here's what you should have been doing all along!"

Overall, this has been a good semester for me. Even though I've complained a bit about the course, the concepts we learned are interesting and taught clearly enough to understand.  Here are links to the other SLOGs I've read and left comments on :

http://99bugsbutaglitchaintone.blogspot.ca/

 http://andylslog165.blogspot.ca/

http://minhuihuangcsc165slogweek2.blogspot.ca/

http://fast10930.blogspot.ca/

http://patslogs.blogspot.ca/
 

Week 12

I completed assignment 3 this week. It wasn't too hard since I understand the material we learned recently very well. I do need to review the course notes on complexity of algorithms for the exam.

Our final lecture was about induction. If we can prove p(n) implies p(n+1), and we can prove p(n) for some n, then for all x greater than n, p(x). It is often best to prove p(n) implies p(n + 1) by assumption of p(n) before actually finding an n for which p(n) is true.

Week 11

This week we discussed functions that can't be computed. One such function is one which returns whether a program will halt. It is impossible to determine while a program is running whether it will continue running forever or whether it simply takes a long time. We can prove that this can't be done by logical contradiction: if such a function existed, then we could use it to write a recursive function which halts when the halting program says that the function does not halt (and vice versa).

Knowing that the halting program is non-computable, we can then prove that other functions are non-computable by showing that they would allow us to write a working halting program if they were computable.

Week 10

I'm following along much better now with printed slide.

This week we are continuing with big-O and big-Omega. Yesterday, instead of proving whether function f is in big-O of function g, we worked from the assumption that it is and proved other claims. For example, the claim f is in O(g) and g is in O(h) implies f is in O(h). The values for c and B for the consequent are generally dependent on the c and B values from the antecedent rather than being precise numbers. After all, we assume that a positive real number c and a natural number B  exist which fulfill f in O(g) without needing to specify what those numbers are.

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.