Given a problem, is it clear where to begin?
If not, then would it be clear after some thought?
How long would it be until the approach is clear?
Indeed, many problems are of this nature, where it is unclear where to begin.
Perhaps, the Riemman Hypothesis.
Perhaps, Fermat's last Theorem
Perhaps, the Poincare Conjecture.
...
However, what if the approach is clear?
If it is, please start to solve the problem.
How long would it take to solve the problem?
Are we able to estimate the time needed to solve the problem?
Perhaps. Perhaps not.
How long would it take to discover the next prime number?
Or perhaps the next pair of twin prime?
Or perhaps the next Mersenn prime?
It is not clear how we would analytically attach an estimate to these questions.
In fact, it is not even clear whether the aforementioned things actually exist.
If it doesn't exist, then are we able to say it would be impossible for us to find one, even given
infinite amount of time?
We can not attach an estimation on infinity.
...
Although this can not be done for many problems,
but for some, we can indeed estimate the time needed to solve the problem.
Then, how can we characterize these estimates?
If we can, perhaps we can improve our understanding on the problems at hand.
What will be the estimate be dependent upon?
perhaps the difficulty of the problem?
or the size?
or the actually nature of the problem?
...nature?
...
Perhaps one way to characterize the estimate can be based on the size of the problem.
Intuitively, a 'larger' problem would require more time in general.
Then, can we take the abstract notion of 'large'ness, and give a precise interpretation
for the estimates?
Perhaps we can.
We can describe the 'largeness' of the problem, by using a number.
The larger the number, the 'larger' the problem is.
Seems intuitive.
Then, perhaps we can give a meaningful estimate based on the this number.
Well, what would be the logical question to ask?
Perhaps,
How does the estimate change as this number changes?
It seems like we are trying to find a relationship between the 2 objects.
Perhaps we can try to use mathematical functions to give the precise relationship.
Then, which mathematical function would best describe the relationship?
Well, we first agreed that as the number gets large, our estimate should also get large.
How many functions have such behaviour?
Well, sinusoidal functions surely do not, since they tend to oscillate, and does not become large.
What about rational functions of polynomials?
Some of them do tend toward infinity with an asymtote, but then what happens beyond that point?
Surely we can require the size of the problem to be just a bit bigger,
in which case, how do we understand the behaviour of the estimate?
Fortunately, there are a whole range of functions that do have the properties we are looking for.
1. Polynomials
2. Exponential
3. Logarithm
4. Factorial
...
In all cases,
we would expect the function value to become large, as the size of the problem increases.
Well, this seems easy.
We have found 4 very well understood functions to characterize our problem.
However, they indeed behave very differently.
The 4 functions have distinctive ways to grow large as the size increases.
From slowest to fastest, we have
Logarithm -> Polynomial -> Exponential -> Factorial
Interesting.
By asking the naive question of estimating the time, we actually arrive naturally at a point where
the problems seems to be split into 4 categories, with comepletly different behaviour.
But, are the problems really fundamentally different from each other?
If so, does the 'nature' of the problem in itself decide the category of the problem?
Astounding.
Just be doing some simple time estimation, we have perhaps arrived at a position to say that
there are indeed 'harder' problems than others, since some problems do seem to take more time
to solve.
However, are we really at a position to claim such things?
Do we understand the problems well enough to categorize them?
We started the analysis to improve our understanding in the first place.
...
Perhaps we can.
Then, for some problems perhaps, we can estimate the time using one of the functions.
Perhaps polynomial for one problem
and exponential for another.
Then, the estimation of time it takes grows much faster for the exponential problem,
compared to the polynomial problem.
It would be nice if we can solve a problem in less time.
Then, should we prefer to solve a polynomial problem?
But wait.
How did we decide that the other problem has to be exponential?
Is it clear how we would attempt to assign such lables to problems?
Perhaps, we can argue that we have indeed found a way to actually solve the problem.
We can manually solve the problem, then correlate the time used, to a mathematical function.
This seems very logical.
However, are there only one way to solve the problem?
Perhaps not.
Then, is there some other way to solve the problem, that we are not aware of?
Seems very likely.
If there is, is it likely to have the same behaviour for the time needed?
If the problem has a true 'nature', then we would presume that it would be the same behaviour.
However, if it does not follow the same behaviour, then what?
Did we change the 'nature' of the problem by finding a better solution?
Surely not, right?
Then, what have we done?
Does it mean that we have came to a better understanding to the problem?
Then is there a true 'nature' to the problem that is distinct to itself?
If so, then how can we understand such things.
Perhaps, by finding better solutions.
Then, can we know for certain whether we have attained a best solution?
...
We could start with the BOGO sort algorithm, which would have an estimate of factorial.
Do we naively believe that the 'sorting' has a charateristic of having a time dependence of factorial?
Then, we may discover bubble sort.
Would we say that the problem actually has a time dependence of polynomial?
Then, if we were to discover merge sort,
would we say now it's actually logarithmic dependence?
What next?
If we can only verify the 'nature' of problems through solutions,
then our verification is solely based on our knowledge of the solution.
Perhaps, we do not know every possible solution.
Then, can we claim without proof that some problems indeed have different time dependence
compared to others?
Can we claim we understand the 'nature' of problems, simply based on our current knowledge?
Perhaps.
Monday, March 31, 2014
Monday, March 3, 2014
Recursion, not as simple as it seems
Many things may seem trivial at the start, but may actually have deep interesting results.
One of the stunning example is the Game of Life, created by John Conway.
"Death by isolation"
"Death by overcrowding"
"Birth by companionship"
Simple rules, that can be understood by closely everyone, actually has more than it meets the eye.
Having not only the fact that the game is unpredictable, it also strikes at the behavior of humanity.
Although as a game, it has limited applications.
Similarly, recursion also run by simple rules.
"Functions calling itself"
It indeed seems simple.
At first glance, it may seem that the coder is too lazy to write the duplicate codes inside another separate function.
Instead, he decided to call the function itself.
Seems trivial. In fact, it seems to be bad practice to be lazy to such degree.
At first glance.
Of course.
First impressions may be deceiving.
Given a recursive definition, is there always an analytical solution?
How is the natural numbers defined?
Do we say 1 + 1 = 2, because we generalize by our everyday interaction?
Surely, it would seem so, yet it is not.
Certainly, almost nobody deal with addition of gigantic numbers daily,
yet how did we come up with the answer to:
perhaps 1 million + 1 million?
It wouldn't seem likely that we can GENERALIZE this result by our interaction with the environment.
Surely not.
One way is to define the natural number, as a recursive structure.
We define 1 + 1 to be the number 2.
We add 1 onto 2:
2 + 1
to create the next number in the sequence.
Thus, to attain the number 1 million, we would need to start the recursive definition,
to show the result of 1 million + 1 million.
If there was not the invention of arithmatic, would there be any other way to solve the problem?
Perhaps.
Yet there are problems upon recursive structures that are unable to be solved analytically.
If that is true, then what are we left with?
Perhaps, only the recursive definition itself.
Thus, we must work with the definition, somehow.
This is the important result of recursive function, being able to use the recursive definition
to its advantage.
Consider the Fibonacci sequence
Is there an analytical solution to the Fibonacci sequence?
Perhaps.
Is it trivial to attain? Very much so.
This is because of the very nature of Fibonacci sequence being a recursive structure.
In order to attain the next number in the sequence, the definition requires the previous ones to
be attained already.
Thus, if we pick an arbitrary point in the sequence, we would be unable to use the definition at all.
Since, we have not been able to attain the previous numbers.
Then, how would we be able to calculate, perhaps
the 1 million-th number of the Fibonacci sequence?
Perhaps, we could use the recursive definition to our advantage.
Take the first 2 fibonacci numbers.
Start the recursive definition.
Repeat the definition for a set amount of time.
We would be able to attain our answer.
This seems decidedly trivial, since we have the tool of recursive functions at our disposal
which takes advantage of the recursive structure itself when attaining the solution.
If there was no analytical solution, then would we just give up on solving the problem?
Surely not.
We have the recursive formula at our disposal, and to attain the result, we are more than welcome
to use it.
The fact that recursion can solve problems that are unable to be solved otherwise is already
an indicator of its importance.
Yet from the beginning, it is not clear from the rule of recursion:
"functions calling itself"
would have profound applications.
It is indeed not as simple as the rule suggests, and given an arbitrary problem,
if there are recursive definition, then, perhaps
we are better off using the recursion to our advantage.
Xiao
One of the stunning example is the Game of Life, created by John Conway.
"Death by isolation"
"Death by overcrowding"
"Birth by companionship"
Simple rules, that can be understood by closely everyone, actually has more than it meets the eye.
Having not only the fact that the game is unpredictable, it also strikes at the behavior of humanity.
Although as a game, it has limited applications.
Similarly, recursion also run by simple rules.
"Functions calling itself"
It indeed seems simple.
At first glance, it may seem that the coder is too lazy to write the duplicate codes inside another separate function.
Instead, he decided to call the function itself.
Seems trivial. In fact, it seems to be bad practice to be lazy to such degree.
At first glance.
Of course.
First impressions may be deceiving.
Given a recursive definition, is there always an analytical solution?
How is the natural numbers defined?
Do we say 1 + 1 = 2, because we generalize by our everyday interaction?
Surely, it would seem so, yet it is not.
Certainly, almost nobody deal with addition of gigantic numbers daily,
yet how did we come up with the answer to:
perhaps 1 million + 1 million?
It wouldn't seem likely that we can GENERALIZE this result by our interaction with the environment.
Surely not.
One way is to define the natural number, as a recursive structure.
We define 1 + 1 to be the number 2.
We add 1 onto 2:
2 + 1
to create the next number in the sequence.
Thus, to attain the number 1 million, we would need to start the recursive definition,
to show the result of 1 million + 1 million.
If there was not the invention of arithmatic, would there be any other way to solve the problem?
Perhaps.
Yet there are problems upon recursive structures that are unable to be solved analytically.
If that is true, then what are we left with?
Perhaps, only the recursive definition itself.
Thus, we must work with the definition, somehow.
This is the important result of recursive function, being able to use the recursive definition
to its advantage.
Consider the Fibonacci sequence
Is there an analytical solution to the Fibonacci sequence?
Perhaps.
Is it trivial to attain? Very much so.
This is because of the very nature of Fibonacci sequence being a recursive structure.
In order to attain the next number in the sequence, the definition requires the previous ones to
be attained already.
Thus, if we pick an arbitrary point in the sequence, we would be unable to use the definition at all.
Since, we have not been able to attain the previous numbers.
Then, how would we be able to calculate, perhaps
the 1 million-th number of the Fibonacci sequence?
Perhaps, we could use the recursive definition to our advantage.
Take the first 2 fibonacci numbers.
Start the recursive definition.
Repeat the definition for a set amount of time.
We would be able to attain our answer.
This seems decidedly trivial, since we have the tool of recursive functions at our disposal
which takes advantage of the recursive structure itself when attaining the solution.
If there was no analytical solution, then would we just give up on solving the problem?
Surely not.
We have the recursive formula at our disposal, and to attain the result, we are more than welcome
to use it.
The fact that recursion can solve problems that are unable to be solved otherwise is already
an indicator of its importance.
Yet from the beginning, it is not clear from the rule of recursion:
"functions calling itself"
would have profound applications.
It is indeed not as simple as the rule suggests, and given an arbitrary problem,
if there are recursive definition, then, perhaps
we are better off using the recursion to our advantage.
Xiao
Thursday, January 23, 2014
Starting in CSC148
Much has been slow recently, which is actually very nice, compared to the overarching responsibilities of other courses.
It would be great if this would continue, however, i doubt that it would.
Much of the current material is based on prior-knowledge of CSC108, which is exceedingly easy to grasp for the second time around.
Although recursion definitely requires much more time for complete comprehension, I somehow has enough confidence in myself on this particular subject.
The most-recent lab on running-efficiency was very insightful indeed.
Although I have not encountered any mass data structure to significantly affect running time, I do believe that I definitely will in the future.
Even though I could not comprehend the reason behind why the queue was exceedingly slow, the lab experience definitely emphasized the importance of organized data structure for me.
I know I am not a seasoned programmer, but I definitely would attain more experience as I proceed.
Someday, I shall understand the subtleties behind running time, and I hope when that day comes, I would be able to pick the best data structure for every situation.
Assignment 1 has been introduced. It seems fairly interesting but exceedingly difficult to grasp.
The thought of considering n pieces of cheese has not been a pleasant experience for me.
Fortunately, I am not expected to attain the general solution to the problem anyways.
As the pace picks up here, and elsewhere, I am not sure how the course will turn out for me.
Maybe next week.
It would be great if this would continue, however, i doubt that it would.
Much of the current material is based on prior-knowledge of CSC108, which is exceedingly easy to grasp for the second time around.
Although recursion definitely requires much more time for complete comprehension, I somehow has enough confidence in myself on this particular subject.
The most-recent lab on running-efficiency was very insightful indeed.
Although I have not encountered any mass data structure to significantly affect running time, I do believe that I definitely will in the future.
Even though I could not comprehend the reason behind why the queue was exceedingly slow, the lab experience definitely emphasized the importance of organized data structure for me.
I know I am not a seasoned programmer, but I definitely would attain more experience as I proceed.
Someday, I shall understand the subtleties behind running time, and I hope when that day comes, I would be able to pick the best data structure for every situation.
Assignment 1 has been introduced. It seems fairly interesting but exceedingly difficult to grasp.
The thought of considering n pieces of cheese has not been a pleasant experience for me.
Fortunately, I am not expected to attain the general solution to the problem anyways.
As the pace picks up here, and elsewhere, I am not sure how the course will turn out for me.
Maybe next week.
Subscribe to:
Posts (Atom)