Solved-Programming Assignment 1- Solution

Description

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:

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

2. <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:

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

4. <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”¹:

• 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

• 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…)