#1




*ANSWER* q5
I see why i, ii, v are possible formulae for growth functions: We have seen examples in class.
But I don't see why iii and iv are not possible formulae for growth functions too, since both this quantities are smaller than the maximum i.e. 2^N (obviously in the case of iv for all N; and in the case of iii for N large  ok, I have not checked for all N). Of course I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ? I must have missed something.. Even if this type of consideration has little practical consequences, I would be interested to know. 
#2




Re: *answer* q5
Quote:
The reason is that we proved that the growth function is either identically or else it has to be bounded above by a polynomial. The two excluded cases are faster than any polynomial, but still short of .
__________________
Where everyone thinks alike, no one thinks very much 
#3




Re: *ANSWER* q5
Argh !!
And you spent the whole of lecture 6 showing it ! And I followed.. Thank you for repeating ! It helps me learn.. By the way, I received the book and so far it is very good. 
#4




Re: *ANSWER* q5
Enjoy!
__________________
Where everyone thinks alike, no one thinks very much 
#5




Re: *ANSWER* q5
Is the following solution also correct?
(iii) cannot be a growth function. For N=1, the formula gives the growth function = 1. This means that the max number of dichotomies for a single point x, is 1 which implies for a given point x, the number of dichotomies is 1 which means h(x) is the same for all h. Now take any two points, x & y, (h(x), h(y)) will be the same for all h (because h(x) is the same for all h and h(y) is the same for all h). The number of dichotomies for a given x & y is therefore 1 so the max number of dichotomies as we vary x & y over X is also 1. But substituting N=2 in the formula gives 2. If the above is true, the same logic can be applied to prove (iv) also cannot be a growth function. 
#6




Re: *ANSWER* q5
Is the following solution also correct?
(iv) cannot be a growth function because for N=1, growth function according to the formula is 1. This means the number max number of dichotomies for all x is 1. Which implies for a given x the number of dichotomies is 1. Which implies for a given x, h(x) is the same for all h. Therefore for a given x & y, (h(x), h(y)) is the same for all h i.e. the cardinality of the dichotomy for any pair of values is 1 and hence the max. cardinality as we vary x & y is also 1. But substituting N = 2 in the formula gives the growth function = 2. If the above is correct, then the same logic can be applied to determine (iii) also cannot be a growth function because, based on the formula, growth function for N=1 is 1 and for N=2, it is 2. 
#7




Re: *ANSWER* q5
Quote:
I am traveling and I only have primitive Internet access so I don't have the homework with me, but your argument sounds correct!
__________________
Where everyone thinks alike, no one thinks very much 
#8




Re: *ANSWER* q5
I'm having a hard time proving that functions iii) and iv) are not bounded by any polynomial in N (any idea or suggestion, would be appreciated). I found a very similar solution (I would like to know if it is correct):
If there exist a finite breakpoint k, then (a) m_H(N) = 2^N for all N<k, and m_H(N) < 2^N for all N>=k otherwise, (b) m_H(N) = 2^N for all N Functions iii) and iv) do not satisfy (b), so there must exist a finite k>=1 such that (a) is satisfied. Whatever this k be, we can check that for k>1, (a) is violated for N=1. And for k = 1 we must have a constant growth function, which is also not satisfied. 
Thread Tools  
Display Modes  

