CS 234 Spring 2019 — Assignment 1
Due date: May 31, 2019, at 5:00pm
Coverage: Python review; Modules 1, 2, and 3
This assignment consists of a programming component and a written component. Please read the course website
carefully to ensure that you submit each component correctly.
Description:
For this assignment, you will be programming with four ADTS: Set, Clothing, Pile, and Outfit.
An implementation of the Clothing ADT has been provided in a file that should be saved as Clothing.py. You can
use this file for your own testing purposes, but it should not be submitted as part of the assignment. The methods

代写CS 234作业、代做Python编程设计作业、代写programming留学生作业、代做Python实验作业
of the Clothing ADT interface are described below. In your solutions, you should only use these methods, since out
automatic testing may use a different implementation of the Clothing ADT.
Name Returns
Clothing(a, m, c) a new Clothing, where a represents the article of clothing,
m represents the material, and c represents the colour
== True when two values represent the same piece of clothing,
i.e. all of the article, material, and colour match, and False
otherwise
!= True when two values have different type or represent different
pieces of clothing, i.e. at least one of article, material,
or colour does not match, and False otherwise
same article(self, article) returns True when self is an article, and False otherwise
same material(self, material) returns True when self is made of material, and False
otherwise
same colour(self, colour) returns True when self is colour, and False otherwise
str(self) A string representation of a Clothing
article(self) returns the article type of self
material(self) returns the material type of self
colour(self) returns the colour of self
Note: the last three methods, article, material, and colour, were added after the assignment was
released for your convenience. Make sure you download the most recent implementation of clothing
for your testing.
The string representation for a Clothing is (colour material article). For example, Clothing("pants",
"denim", "blue") is represented as "(blue denim pants)".
The Outfit ADT represents a potential outfit of clothing items. An outfit consists of required articles and allowed
types of materials and colours. An Outfit must contain all required objects of Clothing for the outfit to be complete,
and each item Clothing must match one of the materials and one of the colours.
1
Name Returns Modifies
Outfit() an empty Outfit
add article(self, article) adds article as a required article
in self
add material(self, material) adds material as a possible material
for Clothing in self
add colour(self, colour) add colour as a possible colour for
Clothing in self
articles(self) a Set containing all required articles
of Clothing for self
colours(self) a Set containing all possible colours
of Clothing for self
materials(self) a Set containing all possible materials
of Clothing for self
add(self, clothing) True if clothing can be added to
self, otherwise False
Adds clothing to self if all of
clothing’s article, material, and
colour are listed in the outfit and
there is no clothing of article type
in the outfit yet
is complete(self) True if the outfit contains all required
articles, otherwise produces
a Set of the articles that are missing
str(self) A string representation of an Outfit
The string representation of an Outfit states whether the outfit is complete, followed by the specifics of the outfit.
If the Outfit is complete, print(outfit) would print:
Complete Outfit:
clothing1
clothing2
...
clothingN
where each of clothing1, clothing2, ..., clothingN is the string representation of a Clothing item.
For example, if an outfit is complete and consists of blue cotton pants and a red cotton shirt, print(outfit) would
print:
Complete Outfit:
(red cotton shirt)
(blue cotton pants)
If the Outfit is not complete, print(outfit) would print:
Incomplete Outfit:
where each of article1, article2, ..., articleN a missing article from the Outfit, displayed in no particular order.
For example, if an outfit is missing pants, a tie, and a shirt, print(outfit) would print:
Incomplete Outfit:
Missing:
pants
2
tie
shirt
The Pile ADT represents a pile of unique Clothing items. Pile contains methods to find all items of clothing in a
pile that match either a provided article, material, or colour and returns a new Pile of all such items.
Name Returns Modifies
Pile() a new empty Pile
is empty(self) True if self has no items, otherwise
False
add(self, clothing) Adds clothing to self
clothing in self True if clothing is in self, False
otherwise
find article(self, article) A Pile of objects from self that
match article
find material(self, article) A Pile of objects from self made
of material
find colour(self, colour) A Pile of colour objects from
self
combine piles(self, other) Adds all objects in other to self
str(self) A string representation of a Pile
1 Programming component
For the programming component you will need to submit the following list of files:
pile.py, outfit.py, and findOutfit.py.
P1. [20 marks] Complete the implementation of the methods included and described in the Outfit and Pile
interfaces. Your implementations of Outfit and Pile must use a Set ADT. An implementation of Set is
provided in Set.py that you can use for your implementation. The interface for this implementation is listed
at the end of this assignment. Note: we may use a different implementation of Set when testing your code.
Only use the methods in the interface that is given.
P2. [10 marks] You have been provided with a file called findOutfit.py.
Complete the function make pile(filename). The filename is a string representing the name of a text
file that contains information about items of Clothing. The function will use that file to create a Pile
of Clothing.
Each line of the file contains the information about an item of clothing in the form:
article material colour
All items of clothing listed in the file need to be added to the Pile. The example file pile.txt has been
supplied.
Complete the function make outfit(filename). The file filename will contain three lines. The first line
contains all items required in the outfit, the second line contains possible materials, and the third line
contains possible colours. Each line will contain at least one attribute. If multiple attributes are present,
they will be separated by a whitespace.
2 Written component
W1. [3 marks] In a sentence or two, explain what the pseudocode function find produces. P is a Pile, and O is an
outfit
function find(P, O)
matches <- Pile()
3
for colour in colours(O)
foundPile <- find_colour(P, colour)
combine_piles(matches, foundPile)
return matches
W2. [8 marks] In this question, you will analyze the worst-case running time of the pseudocode function find from
W1. Let n represent the number of items in P and c represent the number of colours in O. Justify your answers.
(a) Express the worst-case running time of find in terms of the running times of methods used.
(b) For each of the following, give the worst-case running time of find in terms of n and c, where each method
has the following run-time.
i. Pile() is Θ(1), colours is Θ(1), find colour is Θ(n), and combine piles is Θ(n).
ii. Pile() is Θ(n), colours is Θ(c), find colour is Θ(n), and combine piles is Θ(n).
iii. Pile() is Θ(1), colours is Θ(c), find colour is Θ(n
2
), and combine piles is Θ(1).
W3. [4 marks] Each subquestion gives information about two different implementations of the same operations. In
each case, either specify which implementation is preferable and briefly explain why, or explain why there is
not enough information available to determine which is a better choice.
(a) A has a worst-case running time in Θ(n) and B has a best-case running time in O(n log n).
(b) C has a best, worst, and average-case running time in ?(log n) and D has a best, worst, and average-case
running time in (n2).
Set ADT
For this assignment, you are provided with the modified implementation of a Set that excludes the delete operation
for implementing Outfit and Pile. A set is a collection of items where no item is repeated. The implementation has
the following interface.
Name Returns Modifies
Set() an empty Set
elem in self True if elem exists in self, otherwise
False
add(self, item) True if item is successfully added
into self, otherwise False
adds item to self if it is not in
self
len(self) The number of items in self
We also provide an implementation of the special method iter which allows looping over all elements in the Set
using the following syntax:
for elem in self:
body

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 

微信：codinghelp