...and with it, exams, and the end of this course. For my last blog entry, I thought it would be good to reflect on my experience in this course, and how it has (or not) met my expectations.
Coming fresh out of CSC165, I was looking forward to this course. I actually enjoyed most of CSC165 and wanted to dive deeper into the world of proofs and algorithms. The first section of the course, truthfully, I found overly simple, but that may be because I've seen induction in other courses prior to coming in.
Part 2, on recursion and complexity, offered more new material. The process of unwinding recurrences was new to me, but was intuitive enough that I was able to grasp it (and am surprised we never used it in CSC148). I was particularly interested on the Fibonnaci sequence; it was surprising that a sequence of natural numbers could have such a strange closed forms (that included irrational numbers). I plan to revisit this after I learn more about differential equations.
Part 3 of the course was the least enjoyable for me. I understand the use of program correctness, loop invariants, recursive correctness, but they all seem very tedious and not intuitive when deriving them. This made A3 the most difficult part of the course for me, particularly the question 4 with the binary search algorithm. This is something I'm going to have to work on for future CS courses.
The end of the course, on formal languages, actually turned out to be my favourite part. The process of generating and proving DFSAs and regular expressions takes a combination of logic and lateral thinking, and it was very rewarding when you finally find the solution. This part of the course has inspired me to want to take CSC448 and go deeper into these topics some point in my undergrad future.
This was definitely my favourite course of this semester. I found it helped me to think logically and aided me in my other math courses as well. As a bonus, I also learned some of the basics of LaTeX (although I mostly used LyX, sometimes it just didn't cut it, and so I switched to LaTeX). After taking 165 and 236, I am very much considering taking 3rd and 4th year courses on computational theory to go deeper into this challenging but interesting field.
If you've read up to this point, thanks! This will most likely be the final entry in my sLog. I hope it provided a decent insight into the experience of a student in CSC236.
On an unrelated note, take a look at this puzzle. It has a surprisingly logical solution that can be found inductively. (Here is a rough solution if you don't bother solving it).
Well, that's all for me. Peace out!
- Jake
Wednesday 5 December 2012
Problem Solving, Part IV
In my last post, I was attempting to prove that the statement found here was true, by assuming it was false and attempting to arrive at a contradiction.
For now, I will attempt to prove that it is impossible for a cycle of size n to exist.
Clearly, a 1-cycle cannot exist. For all natural numbers >0, n/2 != n and 3n + 1 != n. So f(n) != n, so a 1-cycle cannot exist.
2-cycle: There are 2 cases:
n is even: Then f(n) = n/2. Again, there are two cases to consider:
f(n) is even: Then f(f(n)) = n/4. Since n/4 != n. f(f(n)) != n.
f(n) is odd: Then f(f(n)) = 3(n/2) + 1 = 3/2n +1 != n. So f(f(n)) != n.
n is odd: Then f(n) = 3n+1 and is even.
So f(f(n)) = (3n+1)/2 = 3/2n + 1/2 != n. So f(f(n)) != n.
I could continue for 3,4,5 ... cycles, but the number of cases would become unmanageable, and I would never prove that a cycle cannot exist. There may be a way to solve this problem inductively, but it is difficult to relate an n-cycle to an (n+1)-cycle.
For now, this problem remains unsolved for me, but I at least gained a better understanding of the problem and why it is still unsolved.
Reflection
After attempting this problem, I decided to look it up and see what others have done with it. It turns out this is a famous unsolved problem from 1937 called the Collatz conjecture. Mathematicians have figured out the following:
- No cycle of size 68 or less exists that does not contain 1.
- All numbers up to 5 * 2^ 60 will eventually reach 1.
- The problem is algorithmically undecidable (similar to the halting problem).
So it seems the approach of analysing cycles is useful. From this page, it seems that many mathematicians believe that this problem is unsolvable with our current mathematics, but they remain confident that soon we will have the tools necessary to solve it.
For now, I will attempt to prove that it is impossible for a cycle of size n to exist.
Clearly, a 1-cycle cannot exist. For all natural numbers >0, n/2 != n and 3n + 1 != n. So f(n) != n, so a 1-cycle cannot exist.
2-cycle: There are 2 cases:
n is even: Then f(n) = n/2. Again, there are two cases to consider:
f(n) is even: Then f(f(n)) = n/4. Since n/4 != n. f(f(n)) != n.
f(n) is odd: Then f(f(n)) = 3(n/2) + 1 = 3/2n +1 != n. So f(f(n)) != n.
n is odd: Then f(n) = 3n+1 and is even.
So f(f(n)) = (3n+1)/2 = 3/2n + 1/2 != n. So f(f(n)) != n.
I could continue for 3,4,5 ... cycles, but the number of cases would become unmanageable, and I would never prove that a cycle cannot exist. There may be a way to solve this problem inductively, but it is difficult to relate an n-cycle to an (n+1)-cycle.
For now, this problem remains unsolved for me, but I at least gained a better understanding of the problem and why it is still unsolved.
Reflection
After attempting this problem, I decided to look it up and see what others have done with it. It turns out this is a famous unsolved problem from 1937 called the Collatz conjecture. Mathematicians have figured out the following:
- No cycle of size 68 or less exists that does not contain 1.
- All numbers up to 5 * 2^ 60 will eventually reach 1.
- The problem is algorithmically undecidable (similar to the halting problem).
So it seems the approach of analysing cycles is useful. From this page, it seems that many mathematicians believe that this problem is unsolvable with our current mathematics, but they remain confident that soon we will have the tools necessary to solve it.
Tuesday 4 December 2012
Problem Solving Part 3
I will attempt to prove the following claim by contradiction:
For each natural number n there exists a natural number m such that F(m,n) is a power of 2.
Using the definitions found in Part 1, originally from here.
Assume there exists some n such that F(m,n) is not a power of 2 for all m.
Then the set of natural numbers n that satisfy "F(m,n) is not a power of 2 for all m" exists and is non-empty. Call this set S.
By the Well-ordering principle, S has a smallest element. Call this number x.
Note that, if x is in S, then F(m,x) is also in x for any m.
The case that x is even can easily be ruled out. If x is even, then f(x) = x/2. Since we are not considering 0, Its clear x/2 < x. We also know that f(x) is in S. But x was chosen as the smallest element of S, f(x) cannot be in S. This is a contradiction; x can therefore not be an even number.
So x is an odd number. Proving that this leads to a contradiction would be a much more difficult task. I will assume that one of the following is true, and try to reach contradictions in both cases:
F(m,x) will eventually reach some cycle, which does not contain the number 1.
or
S has infinitely many elements.
Where to go from here stumps me for now. Tomorrow, I will try to advance at least 1 of the above.
For each natural number n there exists a natural number m such that F(m,n) is a power of 2.
Using the definitions found in Part 1, originally from here.
Assume there exists some n such that F(m,n) is not a power of 2 for all m.
Then the set of natural numbers n that satisfy "F(m,n) is not a power of 2 for all m" exists and is non-empty. Call this set S.
By the Well-ordering principle, S has a smallest element. Call this number x.
Note that, if x is in S, then F(m,x) is also in x for any m.
The case that x is even can easily be ruled out. If x is even, then f(x) = x/2. Since we are not considering 0, Its clear x/2 < x. We also know that f(x) is in S. But x was chosen as the smallest element of S, f(x) cannot be in S. This is a contradiction; x can therefore not be an even number.
So x is an odd number. Proving that this leads to a contradiction would be a much more difficult task. I will assume that one of the following is true, and try to reach contradictions in both cases:
F(m,x) will eventually reach some cycle, which does not contain the number 1.
or
S has infinitely many elements.
Where to go from here stumps me for now. Tomorrow, I will try to advance at least 1 of the above.
Problem Solving, Part 2
From my last post, I have decided to try to prove:
For each natural number n there exists a natural number m such that F(m,n) = 1.
Using the definition of F(m,n) found in the previous post.
It may help to analyze the behaviour of F right as it reaches 1. The only way for the f(x) = 1 is if x = 2. This is because there is no odd positive integer n such that 3n + 1 = 1. For the same reason, the only way for f(x) = 2 is if x = 4. It is also worthwhile to note that f(1) = 4, since 3(1)+1 = 4. So, once 1 is reached (if it ever is), the function F(m, n) will follow the sequence: {4,2,1,4,2,1,4,....} as m increases.
We've also established that in cases where n is not 1, 2 (and these cases are trivial anyways), F(m,n) will reach 4 before it reaches 1. But, since n != 1, the only way that f(x) = 4 is when x = 8. A pattern seems to be emerging based off the definition of the function. Note that, in the case that n is even:
f(n) = n/2.
All powers of 2, 2^x, can be expressed by 2*2*2....*2*1, where the number of 2s is x. Therefore, 2^x/2 will continue to be even, until the number 1 is reached. This leads to the following claim:
P(n): F(n, 2^n) = 1
Which can be proven for all n using induction:
Base case: n = 0
Then 2^0 = 1, so applying the function 0 times will yield 1.
Base case: n = 1
Then f(2^1) = 1. So F(1, 2^1) = 1.
Induction step: Assume P(n)
Note that 2^(n+1) is even, and f(2^(n+1)) = 2^(n+1)/2 = 2^n
So F(n+1, 2^(n+1)) = F(n, 2^n) , which, by the induction hypothesis, is equal to 1.
So the claim is true for all n.
From this, we can change the initial claim that we are trying to prove to:
For each natural number n there exists a natural number m such that F(m,n) is a power of 2.
Next, I will actually try to prove this statement indirectly by assuming the negation and attempting to produce a contradiction
For each natural number n there exists a natural number m such that F(m,n) = 1.
Using the definition of F(m,n) found in the previous post.
It may help to analyze the behaviour of F right as it reaches 1. The only way for the f(x) = 1 is if x = 2. This is because there is no odd positive integer n such that 3n + 1 = 1. For the same reason, the only way for f(x) = 2 is if x = 4. It is also worthwhile to note that f(1) = 4, since 3(1)+1 = 4. So, once 1 is reached (if it ever is), the function F(m, n) will follow the sequence: {4,2,1,4,2,1,4,....} as m increases.
We've also established that in cases where n is not 1, 2 (and these cases are trivial anyways), F(m,n) will reach 4 before it reaches 1. But, since n != 1, the only way that f(x) = 4 is when x = 8. A pattern seems to be emerging based off the definition of the function. Note that, in the case that n is even:
f(n) = n/2.
All powers of 2, 2^x, can be expressed by 2*2*2....*2*1, where the number of 2s is x. Therefore, 2^x/2 will continue to be even, until the number 1 is reached. This leads to the following claim:
P(n): F(n, 2^n) = 1
Which can be proven for all n using induction:
Base case: n = 0
Then 2^0 = 1, so applying the function 0 times will yield 1.
Base case: n = 1
Then f(2^1) = 1. So F(1, 2^1) = 1.
Induction step: Assume P(n)
Note that 2^(n+1) is even, and f(2^(n+1)) = 2^(n+1)/2 = 2^n
So F(n+1, 2^(n+1)) = F(n, 2^n) , which, by the induction hypothesis, is equal to 1.
So the claim is true for all n.
From this, we can change the initial claim that we are trying to prove to:
For each natural number n there exists a natural number m such that F(m,n) is a power of 2.
Next, I will actually try to prove this statement indirectly by assuming the negation and attempting to produce a contradiction
Problem Solving, Part 1
About 2 weeks ago, I began looking for a problem to solve, or at least attempt, for my blog. I hit a quick roadblock when I realized that I had no idea where to start looking. And so, I decided to attempt the first problem I found on Danny's problem solving wiki. The problem, in full, is as follows:
-------------------------------------------------------------------------------------------------------------------
Suppose n stands for some positive whole number. Define a function f(n) that associates n with another positive whole number, as follows:
For each natural number n there exists a natural number m such that F(m,n) = 1.
--------------------------------------------------------------------------------------------------------------------
This is a problem that was very briefly mentioned in my calculus textbook. The main thing I remember is that, at my time of writing, it still is unsolved. Nonetheless, I will attempt it, hoping that I can at least make some progress in this deceptively simple problem.
The first step in solving any problem is to understand it. The basic idea behind this problem is that, if I continually apply f(n) to any positive natural number n, the number 1 will be reached in a finite amount of applications. The problem asks to prove or disprove this statement. Therefore, the problem can be solved by either:
Proving that there for every natural numbers n, there exists an m such that F(m,n) = 1
or
Proving that there exists some specific n such that for any m F(m,n) != 0
To convince myself that this function even works, I wrote a simple Python function that took the number from 1-5000 and plugged them into function, repeating until 1 was reached. (It turns out, of course, that it always was. The number 3711 has the largest value for m, 237, but it still reached 1.)
My intuition would be that the statement is true. If the statement were false, then some computer would most likely have found the natural number and got caught in an infinite loop. After knowing this number, disproving the statement would be fairly easy, as one of the following would have to be true:
- There are infinitely many natural numbers n such that F(m,n) never reaches 0
or
- F(m,n) enters some sort of cycle that does not include 1.
So, my focus will be on proving that the statement is true. But first, I will try to find different forms of the statement that may be easier to work with.
-------------------------------------------------------------------------------------------------------------------
Suppose n stands for some positive whole number. Define a function f(n) that associates n with another positive whole number, as follows:
- If n is even, then f(n) is n/2
- If n is odd, then f(n) is 3n+1
For each natural number n there exists a natural number m such that F(m,n) = 1.
--------------------------------------------------------------------------------------------------------------------
This is a problem that was very briefly mentioned in my calculus textbook. The main thing I remember is that, at my time of writing, it still is unsolved. Nonetheless, I will attempt it, hoping that I can at least make some progress in this deceptively simple problem.
The first step in solving any problem is to understand it. The basic idea behind this problem is that, if I continually apply f(n) to any positive natural number n, the number 1 will be reached in a finite amount of applications. The problem asks to prove or disprove this statement. Therefore, the problem can be solved by either:
Proving that there for every natural numbers n, there exists an m such that F(m,n) = 1
or
Proving that there exists some specific n such that for any m F(m,n) != 0
To convince myself that this function even works, I wrote a simple Python function that took the number from 1-5000 and plugged them into function, repeating until 1 was reached. (It turns out, of course, that it always was. The number 3711 has the largest value for m, 237, but it still reached 1.)
My intuition would be that the statement is true. If the statement were false, then some computer would most likely have found the natural number and got caught in an infinite loop. After knowing this number, disproving the statement would be fairly easy, as one of the following would have to be true:
- There are infinitely many natural numbers n such that F(m,n) never reaches 0
or
- F(m,n) enters some sort of cycle that does not include 1.
So, my focus will be on proving that the statement is true. But first, I will try to find different forms of the statement that may be easier to work with.
Wednesday 21 November 2012
Where did November go?
Its been a while since my last post, but we U of T students all know that in October and November, midterms and assignments are unrelenting. On the bright side, there is no shortage of material to talk about since my last update, so without further ado, here's my take on program correctness.
Program correctness has always been my least favourite topic in CSC165, and unfortunately it still has that honour in 236. I find these proofs to be very rigid and cumbersome. There doesn't seem to be that moment of satisfaction that you get when you discover an elegant solution; rather, I just trudge along until the proof is done. I think my problem is that I take too much as assumption. As CS students, we can usually tell if a simple piece of code works, but there's a huge leap between 'I'm pretty sure it works' and 'I KNOW it works'. For that, I suppose the level of rigour we have been using is necessary. Maybe if I would appreciate it more if I tried it on an algorithm that I didn't understand, but for now, I'll just have to keep going.
On a lighter note, I've greatly enjoyed the work we've done so far on formal languages. Before knowing what the topic was, it sounded very dull to me in the course outline. And at first, it was a little difficult to sort through all the new definitions and notations. But behind all this, the problems turned out to be challenging and even fun. Attempting to convert a language described into a DFSA or regular expression is rewarding, almost like a puzzle. And even proving the validity of these languages seems like a useful and informative exercise. I look forward to whatver else we will do with formal languages in the coming weeks.
PS: If you're looking for a fun distraction, try Manufactoria. Its a game where you have to process binary strings, reading only one character at a time - essentially, building a physical DFSA. It gets difficult, but is also very rewarding when you come up with a solution.
Program correctness has always been my least favourite topic in CSC165, and unfortunately it still has that honour in 236. I find these proofs to be very rigid and cumbersome. There doesn't seem to be that moment of satisfaction that you get when you discover an elegant solution; rather, I just trudge along until the proof is done. I think my problem is that I take too much as assumption. As CS students, we can usually tell if a simple piece of code works, but there's a huge leap between 'I'm pretty sure it works' and 'I KNOW it works'. For that, I suppose the level of rigour we have been using is necessary. Maybe if I would appreciate it more if I tried it on an algorithm that I didn't understand, but for now, I'll just have to keep going.
On a lighter note, I've greatly enjoyed the work we've done so far on formal languages. Before knowing what the topic was, it sounded very dull to me in the course outline. And at first, it was a little difficult to sort through all the new definitions and notations. But behind all this, the problems turned out to be challenging and even fun. Attempting to convert a language described into a DFSA or regular expression is rewarding, almost like a puzzle. And even proving the validity of these languages seems like a useful and informative exercise. I look forward to whatver else we will do with formal languages in the coming weeks.
PS: If you're looking for a fun distraction, try Manufactoria. Its a game where you have to process binary strings, reading only one character at a time - essentially, building a physical DFSA. It gets difficult, but is also very rewarding when you come up with a solution.
Saturday 27 October 2012
To understand recursion, you must understand recursion
After what seemed like an endless stream of induction proofs and flavours, we have finally moved on to the second major topic of the course: Algorithm Analysis. In particular, we were working on the analysis of recursive algorithms.
As a precise person, the way we analyzed complexity in CSC165 didn't sit well with me. I couldn't always come to terms with us just dismissing all of the constant time operations with a wave of the hand. It seemed like a cheap trick to me, a simplification that ruined the usefulness of our answer.
I only began to understand when I looked at complexity in a new light: I compared it to limits in calculus. When you have a limit going to infinity, only the largest degree terms have an effect on the value of the limit. In a very similar way, as the size of the problem grows arbitrarily large, only the fastest growing term is going to have a major effect with how efficient our algorithm is. This connection helped me to rationalize 'throwing away' the constant terms.
As for recursive algorithms, I find the whole unwinding process to be a simple but powerful tool to get some intuition on closed forms and time complexity (I feel dumb for never thinking of it myself!). I'm still struggling with it somewhat, though. It seems pretty straightforward to do with recursions that cut the problem into parts (like mergeSort), but I'm having difficulty using it on problems with other types of recursions, like where the problem size is reduced by subtraction. I'm sure more practice will get me on the right track with this.
Everyday it seems a thorough understanding of recursion is becoming more and more important for success in CS. The folks at Google seem to agree!
As a precise person, the way we analyzed complexity in CSC165 didn't sit well with me. I couldn't always come to terms with us just dismissing all of the constant time operations with a wave of the hand. It seemed like a cheap trick to me, a simplification that ruined the usefulness of our answer.
I only began to understand when I looked at complexity in a new light: I compared it to limits in calculus. When you have a limit going to infinity, only the largest degree terms have an effect on the value of the limit. In a very similar way, as the size of the problem grows arbitrarily large, only the fastest growing term is going to have a major effect with how efficient our algorithm is. This connection helped me to rationalize 'throwing away' the constant terms.
As for recursive algorithms, I find the whole unwinding process to be a simple but powerful tool to get some intuition on closed forms and time complexity (I feel dumb for never thinking of it myself!). I'm still struggling with it somewhat, though. It seems pretty straightforward to do with recursions that cut the problem into parts (like mergeSort), but I'm having difficulty using it on problems with other types of recursions, like where the problem size is reduced by subtraction. I'm sure more practice will get me on the right track with this.
Everyday it seems a thorough understanding of recursion is becoming more and more important for success in CS. The folks at Google seem to agree!
Subscribe to:
Posts (Atom)