COMP 410 (F'09). HW 3 (Prog assignment)

Handed out on Sept 16; Due back on Sept 28 in class

A linked-list implementation of the STACK data structure, enhanced with an additional min( ) operation, may be found here, and an example of its use here

It should be evident that this implementation of min( ) takes time linear in the number of items in the stack. You are to modify this implementation to obtain a constant-time implementation of min( ).

You are to provide a complete working implementation of this enhanced stack. You may use any of the code provide in the text, but be sure to unambiguously attribute all such use -- failure to do so is a violation of the honor code.

Rules for submitting this (and all future) programming assignments:

You are not permitted to work in groups: other than the instructor and the TA, no-one may help you.
Include a complete listing of all your code, input files, and output files.
Your code must be appropriately commented -- if we don't usderstand your code with reasonable effort, you get no credit for it.
Include a test plan detailing how you tested your program, and why you believe it is correct.
Include a neatly typed (not handwritten) explanation of your proposed solution, and general comments on the structure and layout of your submission.

All of the above should be placed i an envelope with your name on the outside, and submitted at the beginning of the class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class. Late submissions will not be accepted without documented reasons.