代写CS 234、代做Python编程设计、代写programming留学生、代做Python代写

日期：2019-06-03 11:04

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

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

4