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.
Subscribe to:
Posts (Atom)