The table below lists the height h (in cm), the age a (in years), the gender g (

Question

Explanation / Answer

y = [1,9,28,52,118,172,231,312,718,1400]T Output: A function p:N -> N such that p(n) is the best approximation (in the least squares sense) to the running time of the program on an input of length n. In Octave, we enter this as follows. n = [10,100,1000,2000,4000,6000,8000,10000,20000,40000]'; y = [1,9,28,52,118,172,231,312,718,1400]'; The idea is that there exists some underlying function for the running time of the program, f:N->N, where f(ai) = yi, for i = 1 .. 10. So, we know the values of this function at 10 sampled points. How do we approach finding an approximation? Let's suppose that, in examining the code (in the csc238 sense), we decide that the running time should look something like c1 +c2*log(n) + c3*n + c4*n*log(n), where all logarithms are base 2, and ci are real numbers. So then, our solution p(n) will look like: p(n) = c1 +c2*log(n) + c3*n + c4*n*log(n) So the problem is reduced to finding coefficients ci such that p(n) is a best approximation (in the least squares sense) to the unknown f(n). Now, at this point you may be wondering what all that 'best approximation', 'least squares sense' etc, means. And more importantly, how this amounts to a linear algebra problem, as we're dealing with functions! The key is noting that our p(n) will be a linear combination of the functions 1, log(n), n, n*log(n). You may have heard that certain types of functions constitute vector spaces - if not, don't worry about that part. But consider, say, the family of all polynomials of degree 3: they are all linear combinations of the functions 1, x, x2, x3 (convince yourself of this). In other words, any type of function which is a linear combination of other functions is well suited to this kind of approximation. And for those who aren't clear on the linear algebra terms here, a linear combination of some set of items {a,b,c,d .. } is a sum of those items, each times some real number coefficient, i.e c1*a + c2*b + c3*c + ... , where the ci's are real numbers. So how does p(n) being a linear combination help us? Well, multiplying a matrix times a vector yields a linear combination of the columns of the matrix. For example, for any n, we have: [ 1, log(n), n, n*log(n) ]* [ c1, c2, c3, c4 ]T = p(n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.