We started halting problems this week. Halt means to stop, so halting problems are related to if a function will stop running.
Of course, if we have to test if a function halts, we won't be able to test it by running the function directly, since if the function doesn't halt, then it will keep running and not return anything. What we do is to make another function by predicting if the function halts or not. My confusion is that is there always a function that can predict if the other function halts or not? Does the function always work for all the parameters for the other function, or it only works for some of the cases?
Like the open problem that we talked about in class. Takes a natural number, halves it if it's even, and multiply it by 3 and add 1 if it's odd, and continues this operation until this number reaches 1. How can one proves this other than trying out all the cases?
I think this halting problem and computability is a more advanced part of Computer Science, and it contains many unsolved problems.
Saturday, 22 November 2014
Week 10 (Problem Solving)
Not much happened this week, so I decided to do a problem solving episode on a problem in the tutorial exercise.
Prove 5n^4 - 3n^2 + 1 is in O(6n^5 - 4n^2 + 2n )
First by looking at this question, you know it's probably true because 6n^5 has a higher degree than 5n^4, so it will eventually outgrow the other function.
The idea is to make the first function larger and second function smaller to prove that F1 <= C (F2) and prove it by transitivity since F2 is smaller than 6n^5 - 4n^2 + 2n and the F1 is larger than 5n^4 - 3n^2 + 1, so 5n^4 - 3n^2 + 1 <= C(6n^5 - 4n^2 + 2n)
So to make 5n^4 - 3n^2 + 1 larger we can remove the -3n^2, and make +1 to be +1(n^4), which is true for all n >= 1. So the F1 we are looking for is (5+1) n^4 = 6n^4
To make 6n^5 - 4n^2 + 2n smaller we can remove the +2n, and make -4n^2 to be -4n^5, which is true for all n >= 0. So the F2 we are looking for is (6-4) n^5 = 2n^5
To make them easier to compare we can make F1 to be 6n^5 since 6n^5 > 6n^4 for all n>=0. So
6n^5 <= C 2n^5 by choosing C to be 3
So this is the rough work for that question, and then we can write the detailed proof.
Prove 5n^4 - 3n^2 + 1 is in O(6n^5 - 4n^2 + 2n )
First by looking at this question, you know it's probably true because 6n^5 has a higher degree than 5n^4, so it will eventually outgrow the other function.
The idea is to make the first function larger and second function smaller to prove that F1 <= C (F2) and prove it by transitivity since F2 is smaller than 6n^5 - 4n^2 + 2n and the F1 is larger than 5n^4 - 3n^2 + 1, so 5n^4 - 3n^2 + 1 <= C(6n^5 - 4n^2 + 2n)
So to make 5n^4 - 3n^2 + 1 larger we can remove the -3n^2, and make +1 to be +1(n^4), which is true for all n >= 1. So the F1 we are looking for is (5+1) n^4 = 6n^4
To make 6n^5 - 4n^2 + 2n smaller we can remove the +2n, and make -4n^2 to be -4n^5, which is true for all n >= 0. So the F2 we are looking for is (6-4) n^5 = 2n^5
To make them easier to compare we can make F1 to be 6n^5 since 6n^5 > 6n^4 for all n>=0. So
6n^5 <= C 2n^5 by choosing C to be 3
So this is the rough work for that question, and then we can write the detailed proof.
Sunday, 9 November 2014
Week 9
The second(and the last) term test was on this Wednesday. We were tested on proofs, but not including the proofs for big O. I found the test decently fair because it was quite similar to the assignment we did, for instance, question 3 on the test was exactly like 1.4 in assignment 2. Question two looked a bit tricky first, but once I negated it and rewrote it as an implication statement, it turned out to be pretty straight forward.
The big O and big theta are getting easier to understand when I start to trace the code. I can just do a specific example of n first, and then generalize it into a generic natural number n. Also, we started doing proofs of a function of polynomial belongs to another function of polynomial. One confusion is that if for example a function ax^2- bx where b = a, and if we maximize bx to bx^2, then the entire function would be 0 since ax^2 = bx^2, does it still belong to O(n^2)? In my opinion it should because ax^2 is the highest degree and it belongs to O(n^2).
The big O and big theta are getting easier to understand when I start to trace the code. I can just do a specific example of n first, and then generalize it into a generic natural number n. Also, we started doing proofs of a function of polynomial belongs to another function of polynomial. One confusion is that if for example a function ax^2- bx where b = a, and if we maximize bx to bx^2, then the entire function would be 0 since ax^2 = bx^2, does it still belong to O(n^2)? In my opinion it should because ax^2 is the highest degree and it belongs to O(n^2).
Saturday, 1 November 2014
Week 8
This week we started big O and big theta. I have learned big O in high school, but not this specific. What we did was given a block of code, we had to find out its average case efficiency. We only had more general answers like 1, log(n), n, n^2, 2^n because we only cared the highest degree. However, in this course we have to find everything. The definition of over and underestimate are really abstract and complicated in terms of symbols; however, when I put them in simple English, they are much more comprehensible.
I feel like overestimate is easier to do than underestimate because it's easier to assume for the worst. When overestimating the insertion sort algorithm, all we had to do was to assume every while loop will run n time and one loop guard. However, we had to add an arithmetic sequence (from 1 to n-1) when evaluating the nested loop when we were doing an underestimate. Is it easier to assume the worst of the worst than the best of the worst?
I feel like overestimate is easier to do than underestimate because it's easier to assume for the worst. When overestimating the insertion sort algorithm, all we had to do was to assume every while loop will run n time and one loop guard. However, we had to add an arithmetic sequence (from 1 to n-1) when evaluating the nested loop when we were doing an underestimate. Is it easier to assume the worst of the worst than the best of the worst?
Saturday, 25 October 2014
Week 7
Assignment 2 is finally posted, and all the problems are proofs. The first question is a bit tricky for me because it involves proof using non-Boolean function and its definition. Question two is a bit simpler because those are the questions we did in class and tutorial. I will keep in mind that proving contra-positive is easier than directly proving sometimes when doing proofs.
The penny pile problem we did on Friday was also pretty interesting. We were given two pile and two operations to move pennies and a 64 pennies in total to see if we can get a number of pennies in any pile. My guess was that we can get any numbers that's in range because I have tested a few odd and even numbers and they all worked. However, I have no idea how to prove or disprove such a problem other than testing out all the cases.
The penny pile problem we did on Friday was also pretty interesting. We were given two pile and two operations to move pennies and a 64 pennies in total to see if we can get a number of pennies in any pile. My guess was that we can get any numbers that's in range because I have tested a few odd and even numbers and they all worked. However, I have no idea how to prove or disprove such a problem other than testing out all the cases.
Sunday, 19 October 2014
Week 6
I only had one class this week. Monday was a holiday and I missed the class on Wednesday.Anyway, we started doing proofs in class. I feel like proof is a very hard to start, but once you find where to start, the rest comes in easy. I am still not exactly confident about my proof format, but the content of the proof should be good. One thing that frustrates me is that when proving something with an existential sign, I have to do the work to find an example. If the example is really hard to find, then we will need to take many trial-on-errors to prove the claim.
Hopefully assignment 2 will be posted soon because I need a relatively long time to do questions involve proofs.
Hopefully assignment 2 will be posted soon because I need a relatively long time to do questions involve proofs.
Saturday, 11 October 2014
Week 5
The first test of this course was on Wednesday. There weren't a lot of practice problems first, so I had to look at the exam from previous years in the exam repository. I got stuck on question one for a fairly long time. The question was to find the area that must not exist in a Venn diagram given a statement. I had a really hard time to find out the area until I tried to negate it first. After negation, the statement becomes three statements joined by disjunction, so I know that none of the three statements could exist since they would make the negation true. A lot of problems are easier if you approach from a different perspective, like by proving if n^2 is odd then n is odd; if you try using contrapositve, the question would become much simpler.
Anyway, the real test was much easier than I thought it could be, since most of the questions on the test resemble the sample test on the course website. The only problem I had was giving an example to question four, because I have a hard to think about these questions in term of the real life examples instead of just plain variables.
Anyway, the real test was much easier than I thought it could be, since most of the questions on the test resemble the sample test on the course website. The only problem I had was giving an example to question four, because I have a hard to think about these questions in term of the real life examples instead of just plain variables.
Sunday, 5 October 2014
Week 4
The very first assignment was due on Friday. Most of the problems were straight forward, since they were similar to the exercises in classes and tutorials. But I struggled a bit in the explanation part and giving out real life examples because I cannot express myself very well and I have a hard time to connect this course to the real world.
Also, the definition of limit expressed by logic symbols and the position of quantifiers were very interesting. I learned in high school that if a person chooses any number first, then the second person can always choose a number that's bigger than the first number. However, if the second person chooses first, that would not be the case. I can see the connection between this statement and the position of quantifiers.
Also, the definition of limit expressed by logic symbols and the position of quantifiers were very interesting. I learned in high school that if a person chooses any number first, then the second person can always choose a number that's bigger than the first number. However, if the second person chooses first, that would not be the case. I can see the connection between this statement and the position of quantifiers.
Saturday, 27 September 2014
Week 3
I was pretty confused when we were talking about converse and contrapositive. The question was if n is a multiple of four, then n^2 is a multiple of four. I got confused when the converse is if n^2 is multiple of four then n is a multiple of four because I knew that's not true since there are counter examples. The problem was solved when I realize that I have to pretend that the converse is true.. although it was painful to do so.
Another thing I found interesting was the paper folding problem. I had a very hard time to identify if a vertex was up or down, so I had to use the data that was given on the board. The number of vertices was not that hard to find since each folds increases the number of vertices by two times, so it's going to be 2^n -1 (exclusive of the edges). However, the pattern was much harder to see and I had to guess it. Luckily, after guessing a few patterns( or seeing the hint) I saw the pattern was recursive, and each folds adds a up and down vertices besides each of every other vertices.
Another thing I found interesting was the paper folding problem. I had a very hard time to identify if a vertex was up or down, so I had to use the data that was given on the board. The number of vertices was not that hard to find since each folds increases the number of vertices by two times, so it's going to be 2^n -1 (exclusive of the edges). However, the pattern was much harder to see and I had to guess it. Luckily, after guessing a few patterns( or seeing the hint) I saw the pattern was recursive, and each folds adds a up and down vertices besides each of every other vertices.
Wednesday, 17 September 2014
LOG week 1-2
Before coming into this class, I thought I would have a great advantage over others since I have been using python for three years. However, I was stunned in the first lesson because I could not figure out the ambiguity of any of the five cases. At that moment I realize this course is not what I thought it would be- a completely dull coding class, but rather a class where I can build up my fundamental logical thinking to enhance my programming skill in the future courses.
Subscribe to:
Posts (Atom)