Main topic of week 7: function correctness Definition
A function is being correct if when precondition holds, after executing the function, post condition follows. So, in order to prove a function is correct, we generally assume the precondition is true, and use induction to exam each step what happend there. Gerneralize all the result and compare it with the post condition. When proving it, we usually divide our proof into different cases, and form them we derive the postcondition.
2008年10月20日星期一
Week 6
Main topic of week 6: complexity analysis As introduced in week 4.
Function complexity is the sum of the time complexity in each child function. Obvioulsy, "child function" makes sense when the function calls himself somewhere, meanning the function is recursive. Then the function's time complexity may be based on quantities like length of the list or string. If the child function calling himself with shorter or longer length of the list or string, then it makes some progress towards the base, and we can design our recusive time complexity T(n) based on the length. One thing worth to mention here is that the complexity analysis is based on the worest case scenario, which will simplify the caculation quiet a bit.
Idea how to prove the "uncontinous" recursive function. Because, for example, the length of a list in a recursive function may not stricly decrease or increase by one in each child function call. In the mergeSort(), we find the length of the list to be considered in child function is half to the length of the list in it's parent function. That will make our Time complexity function in a series of discrete points n. So in order to prove it, we could first prove the list of length n = 2^k(in mergeSort() example), thus we know k is decreased by one during each subfunction call. And then prove the function is monotonic, meaning either non-increasing, or non-decreasing. Finally we prove all the possible length lies between each 2^k and 2^k+1 length list.
After finding the time complexity function, we can bounded function by some other functions. Thus big O and big omega is introduced here agian.
Function complexity is the sum of the time complexity in each child function. Obvioulsy, "child function" makes sense when the function calls himself somewhere, meanning the function is recursive. Then the function's time complexity may be based on quantities like length of the list or string. If the child function calling himself with shorter or longer length of the list or string, then it makes some progress towards the base, and we can design our recusive time complexity T(n) based on the length. One thing worth to mention here is that the complexity analysis is based on the worest case scenario, which will simplify the caculation quiet a bit.
Idea how to prove the "uncontinous" recursive function. Because, for example, the length of a list in a recursive function may not stricly decrease or increase by one in each child function call. In the mergeSort(), we find the length of the list to be considered in child function is half to the length of the list in it's parent function. That will make our Time complexity function in a series of discrete points n. So in order to prove it, we could first prove the list of length n = 2^k(in mergeSort() example), thus we know k is decreased by one during each subfunction call. And then prove the function is monotonic, meaning either non-increasing, or non-decreasing. Finally we prove all the possible length lies between each 2^k and 2^k+1 length list.
After finding the time complexity function, we can bounded function by some other functions. Thus big O and big omega is introduced here agian.
2008年10月13日星期一
Week 5
Main topic of week 5: closed form of recursive function and induction definition.
We further navigated some example on how to get the closed form of a function. Here is the idea:
1. Make a general conjecture of a closed form format
2. Build a linear equation based on the closed form.
3. Solve the equation by using different n values.
Then we talked about the definition of recursive set, for example, a binary tree can be defined recursively. In this sense, the most powerful tool to prove the correctness based on a recursive defined set would be induction, because they have very similarly structure.
2008年10月5日星期日
Week 4
Main topic of week 4: recursive definition.
Recursion is a special naming processing, and it is similar to induction, which gives you a general body and a base on which the body will be built on. It is easy to define a recursive function, simply by control it's domain and range. But not all of the function are expressed good enough in recursive way, for example f(n) = f(n-1) surely is not a well defined recursive function, because there is no base case here to tell where the function should end.
Now, given a recursive function. we have a way to guess what the function will look like in closed form by a process called unwinding. Because the recursive way of def, the function can be substitute by it's child function, which makes the function approach to it's base. An interesting recursive function would be the Fibonacci sequence, in which not only one base case, but two of them, need to be provided. We often need to calculate the sum of the first n term of the function, for example, we need to remember the total number of rabbits raised before would be the sum of the Fibonacci sequence. Similarly, if a time complexity function is provided, we could use the sum of the function to indicate how many steps we need to complete on function.
In summary, we learnt recursive definition in this week and a powerful tool--"unwinding" to get closed form of recursive function, and how to find the time complexity function and complexity evaluation.
订阅：
评论 (Atom)