Computer Science 15-100 (Sections T & U), Spring 2008
Notes:  Bonus Lecture #2

2d Arrays, Matrix Inversion, Power Sums

Logistics

1. Bonus points
   • 2 hours of bonus for attending first 1/2 of lecture (4:30 - 6:30)
   • 4 hours of bonus for attending full lecture (4:30 - 8:30)
   • Up to 10 total hours (6-8 more hours) for the bonus projects listed below
2. Due date
   • These bonus projects are due by Tuesday, 25-March.
3. What to submit
   • A timesheet recording all the time invested in the project.
     • Note that there is not a 1-to-1 correspondence between hours reported and hours credited.
     • You are expected on the honor code to report your time accurately.
   • A list of names of anyone with whom you collaborated on the project.
     • Note that the collaboration policy is relaxed for bonus projects, and you can work with one or two other students as a group.  You may even submit a single group project, though you must submit one timesheet for each student.  Note that you still should not consult students outside of your group.  Of course, you may consult the instructor or CA's as always.
   • The actual project itself.
4. Project quiz
   • Depending on the nature of your project, you may be asked to take a short quiz (either written or oral) to demonstrate that you sufficiently mastered the material to warrant the given bonus hours.

Bonus Projects

You may do any, or all (or, of course, none!) of these.  Actual hours credited will depend on the amount and quality of work submitted, and to some extent on the timesheets.  In any case, there is a limit of 10 hours total bonus for this activity, and that includes the 2-to-4 hours of bonus you already received for attending the lecture.

The main project for this lecture is just to reproduce the code we wrote during the bonus lecture, along with test code to verify it works properly.

Part 1:  Write a Java program that takes a square array "a" and returns a new array "aInverse", where "a" times "aInverse" equals the identity matrix I.  If "a" is not invertible, return null.

Part 2:  Using part 1, write a Java program that takes N linear equations and N unknowns, and returns an array of size N with the unique solution to these equations, or null if no such unique solution exists.  Note that the parameters to this method should be an n-by-n array, "A", and an n-by-1 array "b", so you are solving the matrix equation Ax = b.  Recall that you do this by finding A^-1  (A's inverse).  Then if Ax = b, then x = A^-1b.

Part 3:  Using part 2, write a Java program that takes N points (represented as two arrays of doubles, x and y, both of size N), and returns an array holding the coefficients of a degree (N-1) polynomial that fits those N points.  For example, given 2 points, return the line (that is, the degree 1 polynomial) that fits the two points.  Given three points, return the coefficients of the quadratic that fits the 3 points.  And so on.

Part 4:  Using part 3, write a Java program that takes a small positive integer p, and returns an array containing the coefficients of the (p+1)-degree polynomial f such that f(n) = 1^p + 2^p + ... + n^p.  For example, if p=1, you should return the array {0.5, 0.5}, as 1¹ + 2¹ + ... + n¹ = 0.5n² + 0.5n.

Part 5:  Even more bonus: modify the preceding programs so that they operate over exact-valued Ratios rather than approximate-valued doubles.  To do this, create a Ratio class that has instance variables "numerator" and "denominator".  Then your answers will be given as ratios rather than approximate doubles.  So, in the previous example, given p=1, you should return the array {1/2, 1/2}, as 1¹ + 2¹ + ... + n¹ = (1/2)n² + (1/2)n.

Finally, there is always the option to create your own bonus project on this material.  Just be sure to run it by the course instructor first, to ensure that it is bonus-worthy!

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem