Polynomial regression

"Regression" consists in finding a function (typically a polynom) that passes by a set of points (x,y), and can be used to make "prediction" (e.g. find a y for a value x that is not in the points'set).

1. Encode the following polynom in C: $$p(x)=1+x+x^2+x^3$$
   Nb. You can define the power(x,n) function for x^n.
2. Define a program that returns an array xs=[0, 0.1, 0.2, ..., 1]
   To proceed, remind that an array is similar to a "pointer" that can be created by using the malloc function (from stdlib.h)
3. Define a program that return an array ys such as ys[i]=p(xs[i])
4. By considering that vectors are modeled with float arrays of size 4, define a program that return a vector X=[1,x,x^2,x^3].
5. Define a program called mult that multiply a vector by a constant value.
6. Define two programs to compute the sum of two vectors, and a another one that compute the dot product.
   Redefine p by using a dot product, ie. find W such as p(x)=W.X.
7. Now, the objective is to find W such as p(x) passes by all the values of (xs,ys). To proceed, encode the following algorithm:
   • Take a random value for W, eg. [0.1,-0.2,0.3,-0.4]
   • Take an index i from 0 to 50000
   • Compute the predicted output y=p(xs[i%10])
   • Compute the error e=ys[i%10]-y
   • Adapt the "weights": W = W+0.01*e*X
   • Re-compute output, error and adapt weights, etc.
8. Check that the result corresponds to the value of question 6.