# CAS CS 232 Geometric Algorithms A1

## Homework 4 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 a1, a2, ..., an in m space?
• [9.] What is the complexity of the projection of s given vectors b1, b2, ..., bs in m space onto the subspace defined by n vectors a1, a2, ..., an 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]