: この文書について...
CSL102: Introduction to Computer Science
II semester 2004-05
Now that you have written the program and discovered that it takes too long to
gnerate all possible amicable numbers, the only way to convince some one that
your program is correct is to prove it and show that under reasonable assumptions of the capabilities of current digital computers, your program is not only correct, but is also efficient in terms of space and time complexity.
Submit a neat hand written report containing the following:
- A functional description of your algorithm. Also for ready
reference and for comparison, enclose a
printout of the actual program you have finally submitted as
assignment 2.
- Give a complete proof of your functional algorithm. In particular, you
need to state and prove relevant theorems which convince the reader that
- Every pair of numbers generated by your program
is indeed amicable.
- Your program generates every pair of amicable numbers in the
given range, i.e. no amicable pair in the range has been missed out.
- Assume some time complexity measure in terms of the operations on the
digital computer. You could assume that addition and subtraction are
insignificant compared to operations such as multiplication, div and
mod. You could also assume that multiplication, div and
mod take the same amount of time and space, to ease your
calculations.
- State your assumptions clearly.
- State and prove a theorem giving the complexity of your
algorithm in terms of the most signification operations used.
- Assume some space complexity measure for the numbers you consider.
Assume that recursive calls take up the largest amount of space. But each
recursive call for different functions may require different amounts of space. But each recursive call for the same recursive function takes the same amount of space.
- State your assumptions clearly.
- State and prove a theorem giving the space complexity of your
algorithm. in terms of the most signification operations used.
Note:
- You are not allowed to change any of the names given in
the signature. You are not even allowed to change upper-case letters
to lower-case letters or vice-versa.
- You may define any new functions you like in the structure besides those
mentioned in the signature.
- Your program should work with the given signature.
- You need to think of the most efficient way of implementing the
various functions given in the signature so that the function results
satisfy their definitions and properties.
- Since the evaluator is going to look at your source code before
evaluating it, you must explain your algorithms in the form of ML
comments, so that the evaluator can understand what you have implemented.
- Do not add any more decorations or functions or
user-interfaces in order to impress the evaluator of the program.
Nobody is going to be impressed by it.
- There is a serious penalty for copying. If it is felt that there is too
much similarity in the code between any two persons, then both are going
to be penalized equally. So please set permissions on your directories,
so that others cannot copy your programs.
: この文書について...
S Arun-Kumar
平成17年2月15日