Fall break was last Monday and Tuesday and I definitely still do not feel 100% in the zone. I had fun for my long weekend and it's just dreadful thinking about school work again.
For last week's lectures, we discussed about Big-Oh applying to general statements, where a set of functions is not growing faster than another set. These are proven roughly the same way as specific functions, but different in the way that there can be more than one c and B now (which we label B' or B sub f, etc). Also there can be disproofs as well as proofs, such as
f ∈ O (1/n) ⇒ f ∈ O (1/n²) for example is not true.
We're also learning computability and why some problems cannot be coded. Some questions look easy to compute, but in actuality there exists no algorithm for it. In fact, the halt(f, n) function is one that is impossible to write, and it can be proven by contradiction. Halt's purpose is to detect whether or not a program stops or goes into an infinite loop somewhere along the line. However, if the program goes into an infinite loop, a response is never reached by halt, therefore it is not computable.
Assignment 3 has also been posted and I really don't want to start on it..
No comments:
Post a Comment