CS 5010: Problem Set 08
Out: Monday, 30 October 2017
Due: Monday, 6 November 2017 at 6pm local time
This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the WorldWide Web or in other resources that might otherwise have been available to you.
The main purpose of this problem set is to give you practice designing functions with general recursion and halting measures.
You must use Racket's Intermediate Student Language + Lambda for this problem set.
For these problems, download a copy of
extras.rkt
and put it in the directory with your solutions.
Then import rackunit
and this library
by including the lines
(require rackunit) (require "extras.rkt")
at the top of your file. Then, for each problem, put in lines that say
(provide function)
for each deliverable function, as you have done on previous
problem sets.
This will allow our testing framework to import your file
and do automated testing on it.
You can use checklocation
to doublecheck
that your solutions are in the right place.
Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.
Be sure to fill out a
work session report
at the end of each work session.
Be sure to report only the hours
spent in that work session;
do not report the cumulative time.
Tell git
to add your work session report
to the files you will commit,
and then commit and push (sync) that report in addition to
committing and pushing your entire set06set08
directory.
Do this at the end of every work session.
Remember to include a copy of extras.rkt
racket
in your set08
directory along with your
q1.rkt
and q2.rkt
files.
For both parts, you should require rackunit
and
"extras.rkt"
but nothing else.
This problem set deals with the problem of ranking individuals or teams in a sport such as chess whose contests result in a win or tie (draw).
Unlike most ranking systems, the ranking system you will implement treats a tie as a win for both competitors and also as a loss for both competitors. (This problem set may help to explain why most ranking systems don't do that.)
We will use strings to name competitors:
;;; A Competitor is represented as a String (any string will do).

(Outranking)
For this first part of Problem Set 08, you will design data types named
Tie
andDefeat
. ATie
represents a tie (draw) between two competitors. ADefeat
represents the outcome of a contest in which one competitor wins and the other loses. The outcome of a contest is either aTie
or aDefeat
:;;; An Outcome is one of ;;;  a Tie ;;;  a Defeat ;;; ;;; OBSERVER TEMPLATE: ;;; outcomefn : Outcome > ?? #; (define (outcomefn o) (cond ((tie? o) ...) ((defeat? o) ...)))
The ranking system specified below uses this definition:
Given a list of outcomes, a competitor A outranks a competitor B if any of the following are true:
 One of the outcomes shows that A has defeated B.
 One of the outcomes shows that A and B have tied.
 There is a competitor C that outranks B according to the list of outcomes, and there is an outcome that shows A has defeated or tied C.
You are to deliver a file named
q1.rkt
that
defines the
Competitor
,Tie
,Defeat
, andOutcome
types; theCompetitor
andOutcome
types must be defined as shown above  defines and provides all 5 of the functions specified below
 gives halting measures for all functions that may call themselves directly or indirectly
The 5 functions you must define and
provide
are:;;; tie : Competitor Competitor > Tie ;;; GIVEN: the names of two competitors ;;; RETURNS: an indication that the two competitors have ;;; engaged in a contest, and the outcome was a tie ;;; EXAMPLE: (see the examples given below for defeated?, ;;; which shows the desired combined behavior of tie ;;; and defeated?) ;;; ;;; defeated : Competitor Competitor > Defeat ;;; GIVEN: the names of two competitors ;;; RETURNS: an indication that the two competitors have ;;; engaged in a contest, with the first competitor ;;; defeating the second ;;; EXAMPLE: (see the examples given below for defeated?, ;;; which shows the desired combined behavior of defeated ;;; and defeated?) ;;; ;;; defeated? : Competitor Competitor OutcomeList > Boolean ;;; GIVEN: the names of two competitors and a list of outcomes ;;; RETURNS: true if and only if one or more of the outcomes indicates ;;; the first competitor has defeated or tied the second ;;; EXAMPLES: ;;; (defeated? "A" "B" (list (defeated "A" "B") (tie "B" "C"))) ;;; => true ;;; ;;; (defeated? "A" "C" (list (defeated "A" "B") (tie "B" "C"))) ;;; => false ;;; ;;; (defeated? "B" "A" (list (defeated "A" "B") (tie "B" "C"))) ;;; => false ;;; ;;; (defeated? "B" "C" (list (defeated "A" "B") (tie "B" "C"))) ;;; => true ;;; ;;; (defeated? "C" "B" (list (defeated "A" "B") (tie "B" "C"))) ;;; => true ;;; ;;; outranks : Competitor OutcomeList > CompetitorList ;;; GIVEN: the name of a competitor and a list of outcomes ;;; RETURNS: a list of the competitors outranked by the given ;;; competitor, in alphabetical order ;;; NOTE: it is possible for a competitor to outrank itself ;;; EXAMPLES: ;;; (outranks "A" (list (defeated "A" "B") (tie "B" "C"))) ;;; => (list "B" "C") ;;; ;;; (outranks "B" (list (defeated "A" "B") (defeated "B" "A"))) ;;; => (list "A" "B") ;;; ;;; (outranks "C" (list (defeated "A" "B") (tie "B" "C"))) ;;; => (list "B" "C") ;;; ;;; outrankedby : Competitor OutcomeList > CompetitorList ;;; GIVEN: the name of a competitor and a list of outcomes ;;; RETURNS: a list of the competitors that outrank the given ;;; competitor, in alphabetical order ;;; NOTE: it is possible for a competitor to outrank itself ;;; EXAMPLES: ;;; (outrankedby "A" (list (defeated "A" "B") (tie "B" "C"))) ;;; => (list) ;;; ;;; (outrankedby "B" (list (defeated "A" "B") (defeated "B" "A"))) ;;; => (list "A" "B") ;;; ;;; (outrankedby "C" (list (defeated "A" "B") (tie "B" "C"))) ;;; => (list "A" "B" "C")
We will be doing automated testing of your solution, so be sure your solution is in the right place (
set08/q1.rkt
in your privatecs5010f17/pdpYOURUSERNAME
repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after yourrequire
declarations:(checklocation "08" "q1.rkt")

(Power Ranking)
For this second problem, your job is to implement a powerranking system based on the types and functions you defined in part 1.
Given a list of outcomes, the nonlosing percentage of a competitor A is the number of outcomes in which A defeats or ties another competitor divided by the number of outcomes that mention A.
The powerranking system you will implement has the following characteristics:
 If competitor A is outranked by fewer competitors than competitor B, then the powerranking of A is higher than the powerranking of B.
 If competitor A is outranked by the same number of competitors as competitor B, but competitor A outranks more competitors than competitor B, then the powerranking of A is higher than the powerranking of B.
 If competitor A is outranked by the same number of competitors as competitor B, and competitor A also outranks the same number of competitors as competitor B, and competitor A has a higher nonlosing percentage than competitor B, then the powerranking of A is higher than the powerranking of B.

If competitor A is outranked by the same number of competitors
as competitor B, and competitor A also outranks the same number
of competitors as competitor B,
and competitor A has the same nonlosing percentage as
competitor B,
and Racket's
string<?
function considers the name of competitor A to be less than the name of competitor B, then the powerranking of A is higher than the powerranking of B.
You are to deliver a file named
q2.rkt
that defines all of the data types from part 1, defines and provides all 5 of the functions specified in part 1 above, and also defines and provides thepowerranking
function specified below (so you will provide 6 functions in all). As in part 1, you are to give halting measures for all functions that may call themselves directly or indirectly.;;; powerranking : OutcomeList > CompetitorList ;;; GIVEN: a list of outcomes ;;; RETURNS: a list of all competitors mentioned by one or more ;;; of the outcomes, without repetitions, with competitor A ;;; coming before competitor B in the list if and only if ;;; the powerranking of A is higher than the power ranking ;;; of B. ;;; EXAMPLE: ;;; (powerranking ;;; (list (defeated "A" "D") ;;; (defeated "A" "E") ;;; (defeated "C" "B") ;;; (defeated "C" "F") ;;; (tie "D" "B") ;;; (defeated "F" "E"))) ;;; => (list "C" ; outranked by 0, outranks 4 ;;; "A" ; outranked by 0, outranks 3 ;;; "F" ; outranked by 1 ;;; "E" ; outranked by 3 ;;; "B" ; outranked by 4, outranks 12, 50% ;;; "D") ; outranked by 4, outranks 12, 50%
Instead of copying most of your
q1.rkt
file intoq2.rkt
, we suggest you have yourq2.rkt
filerequire
yourq1.rkt
file. Remember, however, that yourq2.rkt
file must stillprovide
all 6 functions.Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (
set08/q2.rkt
in your privatecs5010f17/pdpYOURUSERNAME
repository), and that it provides all of the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after yourrequire
declarations:(checklocation "08" "q2.rkt")