Last modified:
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not attempted" (not applicable). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Whether we have completely specified the subroutine algorithm in class or not, you should assume that you have a complete, correct and working version of the subroutine at your disposal. You may not modify the subroutine in any way.
Argue that your algorithm using the subroutine is correct, and analyze its running time and space requirements. Don't forget to include any pre- and/or post-processing you perform. (In order to analyze the running time and space requirements of your overall solution, you will now need to ``peek inside'' the ``subroutine.'')
Note: Using a subroutine in such a way is often referred to as using a ``black box.'' You can think of a ``black box'' as a Java library routine that someone else has written, and which you simply link into your code. You only know that the ``black box'' correctly solves a particular problem; however, you cannot ``peek inside'' the ``black box'' to see how it works nor can you modify the ``black box'' in any way (it's in binary or byte-code format).