Programming Assignment 1 Solution

Representing, Managing and Manipulating Travel Options













Summary​: you have been given a partially implemented C++ class called TravelOptions​​(file: TravelOptions.h)​. The class implements an ADT using singly-linked lists for which some functions are already written and some are not. Your job is to complete the unwritten functions.




Partially implemented ​TravelOptions.h​and a toy driver program can be found in the ​src​folder.










IMPORTANT NOTE:​we will be using the C++11​​standard for all programming assignments this semester. When running g++,​​this means you want to use the -std=c++11​flag. If you are using some other environment/IDE, spend some

time to make sure it is configured to compile with the C++11​​standard.







Contents




Contents




Conceptual Background




Comparing two Options




Collections of Travel Options




Assignment Details




Nested Types




Data Members (private)




Given Functions




TODO Functions: comparison and checker functions




TODO Functions: modification/construction operators (harder?)




More Pre-Written Functions




Additional Rules, Degrees of Freedom and Reminders




Recommendations




Sample Toy Driver Program




Scoring




Submission Details

Conceptual Background




Suppose you are planning a trip and have gathered a number of different options. Each option has two traits which you care about (and these are the only traits you care about -- who cares about comfort and stuff like that?):




Price




Travel time




Let us represent an option as an ordered-pair ​<price, time. ​Now consider two options:




<100, 120 : ​for $100, you can get to your destination in 120 minutes.
<200, 90 : ​for $200, you can get to your destination in 90 minutes.



Which one should you pick? In this case, it might depend on how rich, impatient and cheap you are. Why? Because, for these two options, we can see there is a tradeoff: there is a reduction in travel time by spending more than $100.




On the other hand, consider these two options C and D:




<100, 110 : ​for $100, you can get to your destination in 110 minutes.
<105, 130 : ​for $105, you can get to your destination in 130 minutes.



Option C is both cheaper ​and​faster than option D. Thus, nobody in their right mind would select option D over option C (again, price and time are the only criteria being considered). In this situation, we say ​"C dominates D"​.




Comparing two Options

Suppose we have two options A and B: ​<pA, tA ​and​ <pB, tB​. If we ask ​"How does A relate to

B?",​ there are four possible answers:




equal
A and B are identical in both price and time.
better
A is better/preferred over B (A dominates B):


A and B are not equal/identical ​and​option A is no more expensive than


option B ​and​option A is no slower than option B.
worse
A is worse than B (B dominates A):


A and B are not equal/identical ​and​option B is no more expensive than


option A ​and​option B is no slower than option A.
incomparable
everything else -- one option is cheaper and the other is faster



(One of your first tasks will be to write a function which takes two options and determines which of the above cases holds.)




Aside: the "dominates" relation among a set of options is a ​partial order​which you may recall from CS151.

Collections of Travel Options




Now consider a list of options -- i.e., a list of ​<price, time​pairs. Such a list may or may not have certain properties.




sorted​: we will say a list of options is sorted if the elements are

in non-decreasing order of price



elements with identical price are ordered according to time -- i.e., time is used as a tie-breaker.
(if two entries are identical in both price and time, of course, they just have to appear adjacent to each other).



​pareto/non-dominated: ​If a collection of options has the following properties, we will say it is "pareto" or is a "pareto-frontier"1:




It contains no duplicates -- i.e., it is a set



It contains only ​non-dominated​solutions -- i..e., for every option A in the collection, there does not exist another option B which dominates it.



Example: Consider the plot of a collection of 10 options below. This collection (of all ten options, both black and red) would be considered non-pareto because of the existence of the four dominated options (colored red).












































































If our collection included only the black options, we would say that the collection is pareto/non-dominated.




You can see that the black options form a "tradeoff curve" -- sometimes called a "pareto curve".




General Observation: In general, a list of options must be in of these "states":




not sorted and not pareto



sorted, but not pareto



not sorted, but pareto






For an idea of where the term "pareto" comes from: ​http://en.wikipedia.org/wiki/Pareto_efficiency
both sorted and pareto



Many functions/operations have "preconditions" on the lists they operate on. Some functions operate on any old list of options; others require one or more option list to be both sorted and pareto; others may take a sorted, but not necessarily pareto list and turn it into a sorted, pareto list. And so on...







Assignment Details




You will complete the implementation of a C++ class called ​TravelOptions​which uses linked lists to represent individual options. Some basic operations have been provided to you, but you will have to complete the implementation of several functions (for which "skeletons" are given).




The following sections give an overview of the class, pre-implemented functions and functions you will need to implement.




Nested Types




Type
Description and Comments




Relationship
public enumerated type capturing the possible relationships


between two options.
Values:




{better, worse,
equal, incomparable}


comment: return type
for the
compare functions




Node
private struct for singly-linked list node; represents a single


option (fields: price, time,
next)














Data Members (private)




Member
Description and Comments




Node *front;
pointer to first node in option list (null if list is empty).




int _size;
tracks list length (note: many of your functions will have to


set/update this data member).




Given Functions




These functions have already been implemented for you! They are ready to use.




Function
Short Description (see banner comments for details)




clear
empties the option list (the object still exists)




size
returns the number of options in the calling object






push_front
adds new option to front of list. Price and
time of option


are passed as parameters. simple utility function for


building lists.






from_vec
utility function for creating an TravelOptions object from a


vector of <price,time pairs. Uses the pair class from the


C++ STL.




Note: this is a static function -- no calling object.


See banner comment for more info..






to_vec
Inverse of from_vec. Returns pointer to vector of STL pairs


populated from the calling object.






display
prints the options to the terminal (of course, in the order


they appear in the list).








checksum
you are not allowed to touch this function!
See banner


comment if interested.








TODO Functions: comparison and checker functions




This first group of functions shouldn't be too terrible! Start with these.




Function


Short Description (see banner comments
Comments
Points










for details)






























compare


static function (no calling object)
Should be an easy one
10




which takes two options (via four
to knock out first!






parameters) and determines their










relationship. Returns one of the four
Runtime: constant






possibilities (see enumerated










Relationship​ type above).
































is_sorted


determines if calling object is sorted
Runtime:
linear
10




according to rules laid out ​above
































is_pareto


determines if travel options are
Runtime:
quadratic
10




pareto
































is_pareto_sorted


determines if options are both ​pareto
Runtime:
linear
10




and sorted




Can't just call the












































two previous






















functions because of






















a runtime
























requirement!






















Still not that hard.




























TODO Functions: modification/construction operators (harder?)




Function
Short Description (see banner
Comments
Points


comments for details)














insert_sorted
inserts new option (passed via
precondition: calling
15


parameters) into a sorted
object must be sorted




option list.
(returns false if not).






Runtime: linear














insert_pareto_sorted
Takes new option and, if it is
precondition:
list must
20


not dominated by a
be both sorted and pareto




pre-existing option, inserts
(returns false if not).




it and, in turn deletes any








pre-existing options which
Runtime: linear






have become dominated.














union_pareto_sorted
Takes two lists (calling
preconditions: both
20


object and a parameter) and
calling object and




constructs their "pruned
parameter must be pareto




union" as a new list. Returns
and sorted (returns null




new TravelOptions object as a
if not)






pointer.
postcondition:
returned












object must also be






pareto and sorted. In






general, it will be a






subset of the traditional






set-union of the two






lists.








Runtime: Linear.












prune_sorted
takes sorted option list and
precondition:
calling
20


deletes all dominated elements
object must be sorted




(if any). Of course only
(returns false if not).




deletes dominated options.
postcondition:
calling












object is both sorted AND






pareto.








Runtime: Linear.












Function
Short Description (see
Comments
Points


banner comments for








details)
















join_plus_plus
Takes two option lists
preconditions:
both lists must
20


(calling object and a
be sorted and pareto (if not,




parameter).
One list
null is returned).




gives options for the








first leg of a trip;
Not as bad as it sounds... see




the other gives options
banner comments!






for the second.
No runtime requirement.




Constructs and returns












a pareto-sorted option








list for the entire








trip.




















join_plus_max
Takes two option lists
preconditions:
both lists
30


(calling object and a
expected to be pareto-sorted




parameter).
One list
(null returned if not).




gives options for








traveler A and the
postconditions:
returned list




other gives options for
is pareto-sorted.




traveler B.


Runtime: linear(!)




Constructs and returns












the pareto sorted
This one may take some thought!




option list for A and B
Some tips given in banner




traveling concurrently
comment.






and so "time" is the








maximum (latest) of A's








time and B's time.








Read banner comment for








details.




















split_sorted_pareto
takes max_price as a
preconditions:
calling object
15


parameter.
Splits
expected to be sorted and




option list into
pareto (null returned if not).




options with price no








greater than max_price
postconditions:
both calling




and those greater than
object and returned option list




max_price.


are sorted and pareto.




The cheap options are
Runtime: linear






retained
in the calling








object.
The expensive
Additional Requirement: No




options are used to
allocation of new nodes




populate a new
allowed!






TravelOptions object








with is returned as a








pointer.
























More Pre-Written Functions




These functions have been written, however, they depend on one or more of the functions that are your responsibility.




Function
Short Description (see banner comments for


details)












compare(Node*,Node*)
This is a private, static function
which


compares the options stored in two
Nodes by


calling ​your​ compare ​function​.














You might find it convenient...












sorted_clone
creates a new TravelOptions object
with exactly


the same entries as calling object
but in sorted


order.




Returns new options list as a pointer.


Calls ​your​ insert_sorted function.




Might be handy...especially for writing test


cases.















Additional Rules, Degrees of Freedom and Reminders







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).



cheat.



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).

Recommendations




Start with the easier functions.



The assignment is very modular -- you can write and test most functions independently. In other words, don't try to implement ​all​functions before doing any testing. Write a function then test and debug it before moving on.



Do lots of testing! Write multiple driver programs which perform lots of stress tests on the TravelOptions​class. Think carefully about boundary cases, etc.! Leverage the given functions in writing your test cases (for example, from​_vector ​should make it pretty easy to hard-code some test cases -- see toy​.cpp ​for a simple example).



Test programs should be in separate files (not inside TravelOptions​.h​).



Try to be systematic about your testing -- for example, even if you think a test case has been satisfied, do not simply overwrite that test program with another! Keep it so you can re-test as you continue to develop. Make as many independent test programs as you need (and give them meaningful names!)



Look out for memory leaks!



Sample Toy Driver Program




As stated above, you will be writing driver programs to test your implementation. For reference a toy driver program has been given (filename: ​toy.cpp​). It is just a pretty random sequence of invocations of ​TravelOptions​functions, just so you have an idea of how to write a driver program. Compilation is simple:




g++ toy.cpp




Scoring




The individual functions have been assigned points in the tables above. The points received will be determined via testing and include runtime tests! Some of these tests will be released prior to the submission deadline.




The point total over all functions is 180. In addition, each submission will receive up to 90 points for




having made an "honest effort." This does ​not​mean you can simply turn in the TravelOptions​.h ​file as it has been given to you and expect to receive these 90 points! Similarly, ​if your code does not even compile, don't expect to get many of those 90 points.​But, if you submit compilable code but end up with some functions that fail all/most test cases despite your best efforts, all is not lost!







Submission Details




Your only deliverable will the your TravelOptions​.h​file. Stay tuned for submission details (it will be done either via blackboard or gradescope...)