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.

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.

Week 3

This week I learned how to transform logical expressions using negation. Applying negation to a statement means to reverse the truth of it. This is similar to what we did in week 2 with falsifying implications.

I was able to solve most of the questions on the tutorial exercise easily, but I did not know how to symbolically represent statements such as "more than one element has a given property", or "No more than two elements have this property". I will need to review my TA's solutions. Regardless, I am confident that I did well on the quiz at the end of the tutorial. For the most part I am very comfortable with logical notation. My previous experience with programming helps me break down complex statements.

Week 2

This is my course log, or SLOG, where I will be recording the things I learn  and challenges I encounter in CSC 165.

This week I learned about universal and existential claims. A universal claim is a statement about every element of a set, and an existential claim states that at least one element of a set has a given property. I found it interesting to logically analyze statements made in plain English to identify precisely what claims are being made. I also learned how to prove or disprove these kinds of statements.

This is the first course I have taken that has explored set theory in detail. I have previously used arrays and lists when writing programs, which are a similar concept, but at first I was confused by the notation used in class. I found it useful to refer to the section on set theory and notation in chapter 1 of the course notes. Now, when I encounter set notation, I first make sure I understand the meaning in English before continuing.