# CAS CS 232 Geometric Algorithms A1

## Homework 4 Due: March/25/2004

• [1.] What is the complexity of the Least Square approximation algorithm for finding the best fitting line for n input-output pairs?
• [2.] Problem 19 and 20 [Page 204] (Postponed from HW3]
• [3.] Problem 30 [Page 205] (postponed from HW3]
• [4.] Problem 2 [Page 215]
• [5.] Problem 6 [Page 216]
• [6.] Problem 10 [Page 216]
• [7.] Problem 12 [Page 217]
• [8.] Problem 24 [Page 218]
• [9.] Problem 27 [Page 218]
• [10.] Problem 10 [Page 228]
• [11.] Problem 12 [Page 229]
• [12.] Problem 23 [Page 230]
• [13.] Problem 24 [Page 230]
• [14.] Problem 31 and 32 [Page 231]
• [15.] Problem 34 [page 232]
• [16.] 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?
• [17.] 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?