Tuesday, 2 December 2014
Problem in my blogger
Somehow some of the blogs that I wrote a while ago cannot be showed properly, just like the ones below, although it is perfectly fine when I reverted it into draft.
So I just deleted the original blogs, and wrote the new ones, thus the dates for some blogs is not correct.
Last week of class
Today is November 30th, and it's the last week of class, and after that we have exams coming up. Looking back to the beginning of this semester, I think I really learnt a lot about computer, and especially the material from last week will stick on my mind for a really long time.
This week, I am mainly focusing on the last assignment for this course, which about proving and disproving Big O and Big Omega as well as the halting problem. The assignments were always quite hard to do compared to the tests, quizzes and the material covered in class. However,I found this last assignment the hardest as we spent tremendous amount of time tackling down question 3, 4, 5 and 6 (almost every question in this assignment!).
In this week's lectures, we talked about countable and uncountable functions. And we also learnt a new proving technique called induction, which has two parts: base case and induction step. In the base case, we prove that P(0) or P(k) is true. Then in the induction step, we assume P(n) is true and try to prove P(n+1) is also true. This is a really powerful and wise-used proving technique in mathematics.
Since we will finish this course in a few days, so I would like to say some words: this course is a quite practical and useful course for computer science and I learnt a lot during this semester. We also have great TAs, professors and classmates, and I would like to thank them for their efforts and wish them all the best in the future!
This week, I am mainly focusing on the last assignment for this course, which about proving and disproving Big O and Big Omega as well as the halting problem. The assignments were always quite hard to do compared to the tests, quizzes and the material covered in class. However,I found this last assignment the hardest as we spent tremendous amount of time tackling down question 3, 4, 5 and 6 (almost every question in this assignment!).
In this week's lectures, we talked about countable and uncountable functions. And we also learnt a new proving technique called induction, which has two parts: base case and induction step. In the base case, we prove that P(0) or P(k) is true. Then in the induction step, we assume P(n) is true and try to prove P(n+1) is also true. This is a really powerful and wise-used proving technique in mathematics.
Since we will finish this course in a few days, so I would like to say some words: this course is a quite practical and useful course for computer science and I learnt a lot during this semester. We also have great TAs, professors and classmates, and I would like to thank them for their efforts and wish them all the best in the future!
Week 11: Halting Problems
This week, we were introduced to two totally new ideas: halting problems and computabillity. These were first introduced and proved by Alonzo Church(who introduced Lambda calculus) and Alan Turing(who described Turing machine) before they even had a computer.
Then prof showed us one function collatz:
def collatz(n):
#n is a natural number
while n>1:
if n%2 == 0:
n = n/2
else:
n= 3*n+1
return "Reach 1.."
Nobody on this planet know the answer that whether this function halts or just loops forever. Even mathematicians cannot do that -- they can only show that the function halts for n less than 2^58.
Then we turned to the function H(f, i), which takes in a function f and a variable i and output if the the function f(i) halts. For the proof of H(f, i), we need to use contradiction: If we assume that the function halts, then we will end up with the conclusion that it doesn't halt; if we assume that a function doesn't halt, then finally we conclude that it halts.
Then prof showed us one function collatz:
def collatz(n):
#n is a natural number
while n>1:
if n%2 == 0:
n = n/2
else:
n= 3*n+1
return "Reach 1.."
Nobody on this planet know the answer that whether this function halts or just loops forever. Even mathematicians cannot do that -- they can only show that the function halts for n less than 2^58.
Then we turned to the function H(f, i), which takes in a function f and a variable i and output if the the function f(i) halts. For the proof of H(f, i), we need to use contradiction: If we assume that the function halts, then we will end up with the conclusion that it doesn't halt; if we assume that a function doesn't halt, then finally we conclude that it halts.
Finally, we learnt computability, which says that if f is a well-defined function, i.e. we can say what f(x) is for every x in the domain, but we can't say how to compute f(x), then f is noncomputable. And we know that computability has to do with halting to some extent as the example functions prof showed in class all have H(f, i) within the codes.
In conclusion, this week's topic is the most staggering and impressing part of this course so far because it showed me something I've never been exposed before and it is also different from the usual material taught in class like algorithms and other stuff. Although I still don't really grasp everything prof said about this topic in class, but I really found this interesting and I will keep working on it!
Week 10: Proofs of Big Omega
This week,we shifted our focuses gradually from Big O to Big Omega. The proofs is kind of similar to that of Big O. And the main idea (and the hard part) of the proof is to find a magic breakpoint B and simplify the function without changing the highest degree, since the lower degrees are negligible compared to highest degrees and thus can be ignored.
Also, prof taught us a way of determining if the functions satisfy the Big O or Big Omega by calculating the limit of the division of two functions as N goes to infinity. The limit will tell us the answer because it tells us the behavior of two functions near infinity and thus we can speculate the validity of f <= cg or f >= cg.
Also, prof taught us a way of determining if the functions satisfy the Big O or Big Omega by calculating the limit of the division of two functions as N goes to infinity. The limit will tell us the answer because it tells us the behavior of two functions near infinity and thus we can speculate the validity of f <= cg or f >= cg.
Week 9: Proofs of Big O
This week, we had our second midterms and also second assignment due. What a busy week! Guess I will take a break from studying this weekend... Anyways, I think I did pretty well on the test as well as on the assignment. I personally think that the assignment is harder and it took me and my partner quite long to finish it, Question 2 is alright but Question 1 really got us, especially Claims 1.3 and 1.4. Because we never did this kind of proof: for example, we knew that Claim 1.4 was wrong however when we negate the statement, we didn't know how to prove x=y. Thanks to Google, and thanks to professor that we now know that we have to prove x >= y and x <= y in order to prove they are equal.
During this week's lectures, we continued talking about Big O and Big Omega (but mainly Big O) and we started learning the actual proofs of Big O. As I've mentioned before, we have to start from definitions for most of the proofs. So, for Big O, the key point is to find an c and an B that make satisfy the definition. The Big O proof is sort of like limit proof in which you will have to work backwards to find the right number in both cases.
We've also learnt how to disprove the Big O statement, which is just proving its negation. However, the problem for me is not how to prove/disprove it but figuring out if the function satisfies the Big O or not.Therefore, I usually assume the function is Big O, and try to find an c and B that works,and if I can't, I will then disprove it. I think my technique is time-consuming,especially on a test, but I cannot find a better way to do it. If any of you know, please tell me!
During this week's lectures, we continued talking about Big O and Big Omega (but mainly Big O) and we started learning the actual proofs of Big O. As I've mentioned before, we have to start from definitions for most of the proofs. So, for Big O, the key point is to find an c and an B that make satisfy the definition. The Big O proof is sort of like limit proof in which you will have to work backwards to find the right number in both cases.
We've also learnt how to disprove the Big O statement, which is just proving its negation. However, the problem for me is not how to prove/disprove it but figuring out if the function satisfies the Big O or not.Therefore, I usually assume the function is Big O, and try to find an c and B that works,and if I can't, I will then disprove it. I think my technique is time-consuming,especially on a test, but I cannot find a better way to do it. If any of you know, please tell me!
Week 8: Intro to Big O and Big Omega
In this week's lectures,we were introduced to the notation of Big-Oh and Big-Omega, which is merely the two assessment used to test how efficient an algorithm is. As I mentioned in last week's slog, it is extremely important for an programmer/software developer to know the running time and efficiency of his algorithms.
Big O specifically describes the worst-case scenario, and can be used to describe the execution time required by an algorithm. O(N), for example, describes an algorithm whose performance grows linearly and in direct proportion to the size of the input data. O(N2), on the other hand, represents an algorithm whose performance is directly proportional to the square of the size of the input data. The more formal definition, mentioned by professor in class, for O(n^2) is that beyond a breakpoint B, f(n) is upper bounded by cn^2, where c is a constant multiplier.Big Omega, which is completely the opposite of Big O, is used to describe the best case running time for a given algorithm.
Sometimes, people also describe Big O and Big Omega as bounds: Big O represents the upper bound running time for an algorithm, which is also the “worst case” whereas Big Omega is used to represent the lower bound, which is also the “best case” for that algorithm.
Sometimes, people also describe Big O and Big Omega as bounds: Big O represents the upper bound running time for an algorithm, which is also the “worst case” whereas Big Omega is used to represent the lower bound, which is also the “best case” for that algorithm.
Week 7: Running time
This week, we wrapped up the end of proving techniques and started talking about efficiency of different algorithms. To conclude the proof part, we learnt some inferences such as conjunction/disjunction elimination, existential instantiation, etc. These rules allow us to do proofs more efficiently by reducing some redundant steps. Then we moved on to calculating the running time for different functions, which refers to the number of steps that function takes.
Running time of an algorithm is an essential part of computer science, because every programmer or software developer has to present an algorithm that's as efficient as possible. Since programmers has to deal with huge amount of data, so we don't want the algorithm produced takes forever to output the result. And to make sure that we -- as starting programmers won't run into that trouble, we will have to first learn how to count the running time of a function. In this week's lectures, we compared bubble sort and merge sort. And we input some specific numbers into the function to determine how many steps each function takes, and then conclude that which one is faster and more efficient. Then we compare the growth factor of each function, i.e. if we double the number of data of input, how will the running time of each function change? Will the ratio of the running time of two functions stay the same? And we found that some functions do better (faster) when there's big amount of data, while some functions run faster if the data is small and run slower and slower as the data gets larger and larger.
Running time of an algorithm is an essential part of computer science, because every programmer or software developer has to present an algorithm that's as efficient as possible. Since programmers has to deal with huge amount of data, so we don't want the algorithm produced takes forever to output the result. And to make sure that we -- as starting programmers won't run into that trouble, we will have to first learn how to count the running time of a function. In this week's lectures, we compared bubble sort and merge sort. And we input some specific numbers into the function to determine how many steps each function takes, and then conclude that which one is faster and more efficient. Then we compare the growth factor of each function, i.e. if we double the number of data of input, how will the running time of each function change? Will the ratio of the running time of two functions stay the same? And we found that some functions do better (faster) when there's big amount of data, while some functions run faster if the data is small and run slower and slower as the data gets larger and larger.
Week 6: Proofs and Limits
Furthering our discussion on proofs, prof taught specifically how to use different proof techniques: under what kind of conditions we should use proof by cases or direct proofs etc.
We focused on the non-boolean functions, in which we are not allowed to apply quantifiers on them. So we will have to manipulate the expression a bit in a way that quantifiers are not used to functions and at the same time, our words have to be as precise as possible compared to the original definition. We also learnt limits this week, which is a tricky one because it involves thinking backwards to find the satisfying delta that makes the proof work. But I think the formal knowledge background from Mat137 will help me a bit on this part. Besides, we also tackle the disproof, which is totally the opposite of proving. Disproving involves finding counterexample which falsifies the statement, or we can negate the statement first and prove the negation.
We focused on the non-boolean functions, in which we are not allowed to apply quantifiers on them. So we will have to manipulate the expression a bit in a way that quantifiers are not used to functions and at the same time, our words have to be as precise as possible compared to the original definition. We also learnt limits this week, which is a tricky one because it involves thinking backwards to find the satisfying delta that makes the proof work. But I think the formal knowledge background from Mat137 will help me a bit on this part. Besides, we also tackle the disproof, which is totally the opposite of proving. Disproving involves finding counterexample which falsifies the statement, or we can negate the statement first and prove the negation.
Week 5: Proofs and Limits
We had our first test for this course during this week. I don't know what I should say about this test because it's not hard but one of the question (last one) I wasn't expect that to be on the midterm... So I think I didn't do as good as I expected, but it is not so bad. Guess I REALLY need to work on that type of question now: I didn't do it well on the assignment, and I screwed it up on the test. Ah, this is frustrating...
Getting back to the topic of this week's material, so basically we are continuing the topic of proof this week. We learnt how to prove ∃ and Ɐ: we only need to find one thing that satisfies the statement in order to prove the "there exists" quantifier, and we need to assume some generic numbers for the "for all" quantifier. Also, we learnt some different ways of proofs: direct proof, proof by contradiction and proof by cases. In addition, we now know the importance of a definition to one proof: we will most likely have to use the definition given to prove the statement and there's no other way to do it.
Getting back to the topic of this week's material, so basically we are continuing the topic of proof this week. We learnt how to prove ∃ and Ɐ: we only need to find one thing that satisfies the statement in order to prove the "there exists" quantifier, and we need to assume some generic numbers for the "for all" quantifier. Also, we learnt some different ways of proofs: direct proof, proof by contradiction and proof by cases. In addition, we now know the importance of a definition to one proof: we will most likely have to use the definition given to prove the statement and there's no other way to do it.
Monday, 1 December 2014
Week 4: Intro to Proofs
This week, we are starting to get a sense of proofs, which I believe is the main topic of this course.
We are just introduced to the structure pf the proof:
Introduce quantifiers, pick something for ∃ quantifier, then make use of transitivity of implications (in which P implies Q, and Q implies R is equivalent of saying P implies R) to prove the final statement which is usually an implication. These are all the easy parts, and the prof hasn't taught us the hard part which is how to figure a way to prove the final statement. Playing with those notations and finding a number that satisfying the condition that we need to prove is not my strong part, so I think I need to do some preview if I wanna do good on proofs.
In addition, our first midterm is coming up next week. I feel fortunate that we won't be tested on the proof stuff. However, I am still kind of nervous for this coming test since I did not start right from the beginning like others (see my first slog) and I feel that there's some kind of gap between the material I learnt later on in this course and the material that I learn by myself which is just the one that I've missed. But anyway good luck to myself.
We are just introduced to the structure pf the proof:
Introduce quantifiers, pick something for ∃ quantifier, then make use of transitivity of implications (in which P implies Q, and Q implies R is equivalent of saying P implies R) to prove the final statement which is usually an implication. These are all the easy parts, and the prof hasn't taught us the hard part which is how to figure a way to prove the final statement. Playing with those notations and finding a number that satisfying the condition that we need to prove is not my strong part, so I think I need to do some preview if I wanna do good on proofs.
In addition, our first midterm is coming up next week. I feel fortunate that we won't be tested on the proof stuff. However, I am still kind of nervous for this coming test since I did not start right from the beginning like others (see my first slog) and I feel that there's some kind of gap between the material I learnt later on in this course and the material that I learn by myself which is just the one that I've missed. But anyway good luck to myself.
Week 3: Implications
This week, we went deeper into the notations introduced from last two weeks. We've learnt implication, conjunction,disjunction, negation, tabulation, De Morgan's Law and some properties of logic operation such as associativity etc. This week's material is starting to be new now as I've never touched it before. But it is not that challenging as well, so I guess I won't be talking about it in detail.
Right now I am mainly focusing on the assignment that's due at the end of next week. It is quite consuming though it seems pretty easy at the first glance ( and luckily I've got a partner!). Questions 4 and 5 confuse me the most, even now I am writing this Slog, trying to take a break from finishing the last part of the assignment, I still cannot get it. For question 4, I personally think that there are many answers depending on the examples you are taking. If you take D, P and Q to be some numbers that are divisible to 2 or to 3, the answer will be different from the one if you take D, P and Q as the numbers of girls and guys in one school that are able to play piano and baseball. I might be (and probably am) wrong, but I just couldn't figure out the right answer. Guess I will just ask Prof Heap for help during his office hour then.
Right now I am mainly focusing on the assignment that's due at the end of next week. It is quite consuming though it seems pretty easy at the first glance ( and luckily I've got a partner!). Questions 4 and 5 confuse me the most, even now I am writing this Slog, trying to take a break from finishing the last part of the assignment, I still cannot get it. For question 4, I personally think that there are many answers depending on the examples you are taking. If you take D, P and Q to be some numbers that are divisible to 2 or to 3, the answer will be different from the one if you take D, P and Q as the numbers of girls and guys in one school that are able to play piano and baseball. I might be (and probably am) wrong, but I just couldn't figure out the right answer. Guess I will just ask Prof Heap for help during his office hour then.
Subscribe to:
Posts (Atom)