CSC36000 Programming Project #3
Due: Monday, April 14, 2025, 11:59PM
Objectives
• working with greedy algorithms
• working with divide and conquer algorithms
Problem Statement
Maximal Electronic Dating Services (MEDS) is a ( ctional) dating service that asks all of its
clients to ll out two surveys. These two surveys are then scored and given a resulting positive
real number value. The service then proceeds to nd the closest match amongst all of its
clients in one of three ways:
• one way is to just choose the two clients whose rst scored surveys have the closest value.
• another way is to just choose the two clients whose second scored surveys have the
closest value.
• the third way would be to nd the two clients whose combination of scores are the closest.
To measure this, suppose client p scored p1 and p2 on survey 1 and survey 2 respectively;
further suppose client q scored q1 and q2 on survey 1 and survey 2 respectively. Then the
“closeness” of the clients p and q is evaluated as:
( p1 − q1)2 + ( p2 − q2)2
You will be writing a program that takes two command line arguments.
• The rst (required) argument will be the name of an input le. This input le will contain a
sequence of name and two survey score combinations (i.e. client data.) The name will be a
string with no spaces in it, while the survey scores will be real numbers. For example:
Steve 0.11 42
Emily 2.7183 3.1415927
Jones 1.2 3.4
Note that all names will be unique, and there will be no more than 1,000,000 clients in
the input le.
• The second (required) argument will be one of the following strings: “1”,”2”, or “b".
• If the argument is 1, then the closest pair of clients should be found based only on the
rst survey scores.
• If the argument is 2, then the closest pair of clients should be found based only on the
second survey scores.
• If the argument is b, then the closest pair of clients should be found based on both survey
scores, as outlined above.
• As output, print both of the client names that are closest to each other and how far apart
this two clients are.
VERY IMPORTANT ADDITIONAL CONSTRAINT: Your program must run in better than n 2
time. Anything that runs in Θ(n 2 ) or worse time will lose signi cant points!
fi fi fi fi fi fifi fi fi fi
Due: Monday, April 14, 2025, 11:59PM
Objectives
• working with greedy algorithms
• working with divide and conquer algorithms
Problem Statement
Maximal Electronic Dating Services (MEDS) is a ( ctional) dating service that asks all of its
clients to ll out two surveys. These two surveys are then scored and given a resulting positive
real number value. The service then proceeds to nd the closest match amongst all of its
clients in one of three ways:
• one way is to just choose the two clients whose rst scored surveys have the closest value.
• another way is to just choose the two clients whose second scored surveys have the
closest value.
• the third way would be to nd the two clients whose combination of scores are the closest.
To measure this, suppose client p scored p1 and p2 on survey 1 and survey 2 respectively;
further suppose client q scored q1 and q2 on survey 1 and survey 2 respectively. Then the
“closeness” of the clients p and q is evaluated as:
( p1 − q1)2 + ( p2 − q2)2
You will be writing a program that takes two command line arguments.
• The rst (required) argument will be the name of an input le. This input le will contain a
sequence of name and two survey score combinations (i.e. client data.) The name will be a
string with no spaces in it, while the survey scores will be real numbers. For example:
Steve 0.11 42
Emily 2.7183 3.1415927
Jones 1.2 3.4
Note that all names will be unique, and there will be no more than 1,000,000 clients in
the input le.
• The second (required) argument will be one of the following strings: “1”,”2”, or “b".
• If the argument is 1, then the closest pair of clients should be found based only on the
rst survey scores.
• If the argument is 2, then the closest pair of clients should be found based only on the
second survey scores.
• If the argument is b, then the closest pair of clients should be found based on both survey
scores, as outlined above.
• As output, print both of the client names that are closest to each other and how far apart
this two clients are.
VERY IMPORTANT ADDITIONAL CONSTRAINT: Your program must run in better than n 2
time. Anything that runs in Θ(n 2 ) or worse time will lose signi cant points!
fi fi fi fi fi fifi fi fi fi
