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