Due: April/12/2005

- [1.] What is the complexity of the Least Square
approximation algorithm for finding the best
fitting line for n input-output pairs?
What is the complexity of the Least Square approximation algorithm for finding the best fitting degree d curve for n input-output pairs?

- [2.] Problem 10 [Page 228]
- [3..] Problem 12 [Page 229]
- [4.] Problem 23 [Page 230]
- [5.] Problem 24 [Page 230]
- [6.] Problem 31 and 32 [Page 231]
- [7.] Problem 34 [page 232]
- [8.] What is the complexity of the projection of a given vector b in m
space onto the subspace defined by n vectors a
_{1}, a_{2}, ..., a_{n}in m space? - [9.]
What is the complexity of the projection of s given vectors
b
_{1}, b_{2}, ..., b_{s}in m space onto the subspace defined by n vectors a_{1}, a_{2}, ..., a_{n}in m space? Can it be faster than just s times the complexity of the previous problem?

[Hint: think of QR decomposition] - [10.] Problem 19 [page 242]
- [11.] Problem 25 [page 257
- [12.] Problem 1 [Page 269]]
- [13.] Problem 15 [Page 271]
- [14.] Problem 21 [Page 271]
- [15.] Problem 29 [Page 272]
### Start early, and good luck.

Stop by my or the TF's office hour if your have questions