Programming Assignment 1: Representing, Managing and Manipulating Travel Options

You may NOT do any of the following:

• change any of the function names or signatures (parameter lists and types and return type)

• introduce any global or static variables

• use any arrays or vectors inside the TravelOptions class! Not for this assignment!! (You may use them as you see fit in any driver/tester programs you write)

You MAY do any of the following as you see fit:

• Introduce helper functions. But you should make them private.

Reminders: Some functions eliminate list entries (e.g., prune_sorted). Don't forget to deallocate the associated nodes (using the delete operator).

Please read the below code and complete the missing parts.

/**

* func: is_pareto_sorted()

* desc: returns true if and only if the list is:

* - STRICTLY INCREASING IN price AND

* - STRICTLY DECREASING IN time

*

* REQUIREMENTS:

* RUNTIME: linear in length of list n (i.e., O(n)).

*

* status: TODO

*

* COMMENTS: notice that because of the runtime requirement, you cannot simply do this:

*

return is_sorted() && is_pareto();

*/

bool is_pareto_sorted() const{

return false;

}

/**

* func: insert_sorted

* preconditions: given collection (calling object) must be sorted (but not necessarily

* pareto). If this is not the case, false is returned (code provided).

* (returns true otherwise, after insertion complete).

*

* desc: inserts option (given as parameters) into option list (calling object)

* while keeping it sorted. Recall: ordering by price; tie-breaker is time.

*

* RUNTIME: linear in length of list -- O(n).

*

* status: TODO

*

* NOTES/TIPS: do this before insert_pareto_sorted; it is easier! Remember, this one

* you don't have to think about pruning for this function -- just ordering.

*/

bool insert_sorted(double price, double time) {

if(!is_sorted()) return false;

return true;

}

/**

* func: insert_pareto_sorted

* preconditions: given collection (calling object) must be sorted AND pareto (pruned).

* if this is not the case, false is returned.

* (code segment for this test given).

* desc: (assuming the list is sorted and pareto): if the option given by the parameters

* price and time is NOT dominated by already existing options, the following results:

* - new option is inserted maintaining the sorted property of the

* list, AND

* - any pre-existing options which are now suboptimal (i.e., dominated by the

* newly added option) are deleted.

* If the new option is suboptimal, the list is simply unchanged.

* In either case, true is returned (i.e., as long as the preconditions are met).

*

* RUNTIME REQUIREMENT: linear in the length of the list -- O(n)

*

* REMEMBER:

* If the new option is useless (dominated by a pre-existing option), the list is unchanged

* (but you still return true if preconditions are met).

* You must maintain sorted order and don't forget to deallocate memory associated

* with any deleted nodes.

* status: TODO

*/

bool insert_pareto_sorted(double price, double time) {

if(!is_pareto_sorted()) return false;

// your code here!

return true;

}

/**

* func: union_pareto_sorted

* precondition: calling object and parameter collections must both be sorted and pareto (if not, nullptr is returned).

* desc: constructs "the sorted, pareto" union (as in set-union excluding dominated options) of the two collections and returns

* it as a newly created object.

* RUNTIME: linear in the length of the two lists (suppose one list is of length n and the other is of length m,

* then the overall runtime must be O(n+m))

* COMMENTS: REMEMBER: after this operation, the collection must be both pareto and sorted.

* TIPS: Think about what must be the FIRST option in the sorted union (bootstrap) -- then think about what is the

* candidate for the 2nd option (if any).

* Remember: a pareto-sorted list must be strictly increasing and price and strictly decreasing in time.

*

* status: TODO

*

*/

TravelOptions * union_pareto_sorted(const TravelOptions &other)const{

if(!is_pareto_sorted() || !other.is_pareto_sorted())

return nullptr;

return nullptr;

}