代写AIC2100、Python设计编程代做

日期：2024-05-30 09:39

AIC2100 AI Programming with PythonLab 5 AIC2100

2

You must follow the specifications thoroughly!

• Any typos (including whitespace and linebreak) will result in a point deduction.

• If you’re asked to write the comment or docstring, you must add them.

• If some Python libraries are prohibited, importing them will result in 0 points.

• Depending on the lab content, additional rules can be added.

• Please read the specification document carefully and submit your code.

• We won't accept appeals for point deductions based on misinterpreting the lab specification

documentation.

• If any specification is unclear, please post your question on the Q&A board.Lab 5 AIC2100

3

Please refer to the guidelines noted in previous labs. They remain applicable for this and

subsequent labs.

Any updates in guidelines will be announced again.

Coding guidelineLab 5 AIC2100

4

Notation

• To clearly instruct the lab specifications, (1) we use “˽” to depict a whitespace (blank)

character and (2) “¤” for a “\n” (newline) character.

• Underlined text refers to the user input (will be demonstrated again in a further lab).

• New notations will be demonstrated additionally on there first mention.Lab 5 AIC2100

5

Reminder: Comment rule

• A 20% score will be deducted per lab problem with missing or insufficient comments.

• Please put brief comments (#...) with all your code (including functions).

• We will not inform you exactly how many comments are “sufficient”.

• But it won’t be an unreasonably large number. Our threshold is reasonable!

• Even if your code is very short (like 2~3 lines), please add at least 2 (line) comments!Lab 5 AIC2100

6

Reminder: Docstrings rule

• A 20% score will be deducted per lab problem with missing or insufficient docstrings in all

functions (including your custom ones and function in function too).

• Please provide docstrings with all functions.

• A docstring should briefly explain:

• The purpose of each parameter (if any).

• What the function computes.

• What the function returns to the caller (if anything).

def your_function(*your_args):

"""Your docstring"""

(your code continues…)Lab 5 AIC2100

7

Reminder: Importing modules/libraries

You may be asked or permitted to use some specific modules/libraries. You are allowed to use

only specified ones in each problem. For example, if math module is mentioned in problem 1 but

not in problem 2, you are not allowed to use math module in problem 2.

Some custom modules may be required to use in the implementation (like, stack module in

Chapter 7 of the lecture). We will provide such module python codes via LearnUs if necessary.Lab 5 AIC2100

8

Class

In this lab, you will be asked to implement class. If you are asked to implement

the class only, you should not include the main program in your code, just like

the function.

Unexpected execution of the main program during the grading can result in 0

points, so please be careful!!Lab 5 AIC2100

9

Class Docstring

You must put the docstring inside the class itself and all class methods, just

like you did in the function (including your custom ones!)

• A 20% score will be deducted per lab problem with missing or insufficient docstrings.

• Don't forget to fill in the docstrings in the provided template code, too!

class MyClass:

"""Class docstring"""

def __init__(self):

"""Method docstring"""

(your code continues…)

def method1(self, a, b):

"""Method docstring"""

(your code continues…)Lab 5 AIC2100

10

Problem 1

Download the provided lab5_p1_template.py. Inside the file, TA wrote the template code of class

Fraction. This class is a basic implementation of mathematical fractions that were already discussed in

Lecture 10. Some methods are already completed. Your job is to complete or modify some incomplete

methods of class Fraction as requested.

Method __init__: Initialization. This method is already completed. At the initialization stage, the reduce

method is called!

Method reduce: It reduces the self fraction to simplest terms by dividing both numerator and denominator by

their greatest common divisor (GCD). Recall that you already implemented GCD (with LCM) in the previous

lab. We already completed the docstring of this method. This method will not change the self when it is

already in the simplest term (including the numerator is 0 or the denominator is 1).

Method __str__: It returns a string that represents the fraction object (self). Currently, it returns

{numerator}/{denominator} form. Modify this method to return the integer (numerator) string if the

denominator (to be represented) is 1 (like 1/1, 2/1, 3/1, …), and '0' if the numerator is 0.Lab 5 AIC2100

11

Problem 1

Methods __add__ and __mul__ implements the operations between Fraction variables, like F1 + F2 or F1 * F2. You should

extend these two methods and complete 7 additional operation methods: subtraction, division, and five comparisons.

Method __add__: Addition. Extend the method to work when the other parameter is of type int.

Method __mul__: Multiplication. Extend the method to work when the other parameter is of type int.

Method __sub__: Subtraction. The other parameter can be either int or Fraction.

Method __truediv__: Division. The other parameter can be either int or Fraction (and non-zero).

The above four methods must return the reduced fraction!

Method __lt__: Comparison (<). Return boolean. The other parameter can be either int or Fraction.

Method __le__: Comparison (≤). Return boolean. The other parameter can be either int or Fraction.

Method __gt__: Comparison (>). Return boolean. The other parameter can be either int or Fraction.

Method __ge__: Comparison (≥). Return boolean. The other parameter can be either int or Fraction.

Method __eq__: Comparison (==). Return boolean. The other parameter can be either int or Fraction.Lab 5 AIC2100

12

Problem 1

Note 1. If you’re adding your custom method like GCD in the class, you must put the docstring in such

methods, too.

Note 2. Assume that the numerator and denominator (parameters n, d in method __init__) are integers. We

will not use faulty inputs during the grading although the exception handling is already implemented.

Note 3. You don’t have to consider any types of faulty inputs (like non-fraction or non-integer (in add/mul)

type operation)

Note 4. Set the denominator to always be a positive integer before/after any operations (i.e., the negative

fraction has a negative numerator and positive denominator). The sign of the fraction must be controlled by

the sign of the numerator.

Caution. Be careful with the file name; you should change the filename to lab5_p1.py before archiving.Lab 5 AIC2100

13

Problem 1

Here's the template code.

You need to modify these methods.

You need to complete this method.

Initialization is already done.Lab 5 AIC2100

14

Problem 1

Here's the template code.

You need to complete these methods.Lab 5 AIC2100

15

Problem 1

Here's the template code.

You don't have to modify this part! What these methods do is define

the operation when the integer is at the left of the Fraction. For instance, if you

only complete __add__ but not __radd__, operation int + Fraction (e.g., 1 +

Fraction(1, 2)) will still raise an error (same for subtraction, multiplication, and

division).

Hint. In this code snippet, we already showed how to handle the case

when the other is Fraction or is int.

Negation operation (-Fraction), already done!

GCD method, already done!Lab 5 AIC2100

16

Problem 1

Here's the template code.

You don't have to modify this part too! This method defines the power

operation: Fraction ** int. This will be used in the problem 3 later.

But please read this code and try to understand how this works.Lab 5 AIC2100

17

Problem 1

Validate your class

with the script file.

Also, modify the script file and try your own test cases.Lab 5 AIC2100

18

Problem 2

In computer science, a tree is a data structure that represents a hierarchical tree structure with a set of

connected nodes.

A

B C D

E F G

The left figure is an example of a tree. Each circle is usually called a node and has

some specific representation. Naming them as A ~ G, A has child nodes B, C, and D

(or you can say B, C, and D’s parent node is A). B also has child nodes E and F. C

has no child node. A is called the root node, with the highest hierarchy (at the top). C,

E, F, and G are called leaf nodes with no child node.

A binary tree is a special tree that all nodes can have two child nodes

at maximum (i.e., there could be only 0, 1, or 2 child nodes for each

parent node). The right figure is an example of a binary tree. We call D

is the left child of B and E is the right child of B. F is the left child of C.

A

B C

D E F

If the tree has the structure like the left figure, all nodes except leaf nodes have two

child nodes. We call such a tree a full binary tree (i.e., every node has either 0 or 2

children).

A

B C

D E F GLab 5 AIC2100

19

Problem 2

It is known that a binary tree can be represented as a list. The position of each node can be determined by

the index in the list. Look at the below example. Try to find the relationship between the indices of parentchild

nodes (easy to figure out!). The answer is that the left and right child of the parent node at i-th index is

located at 2i+1 and 2i+2 indices, respectively. If a node does not exist, you should use None as an element.

Our provided template code is implemented based on a list representation.

0

1 2

3 4 5 6

7 8 A B C E

['0', '1', '2', '3', '4', '5', '6', '7', '8', None, 'A', 'B', 'C', None, 'E']Lab 5 AIC2100

20

Problem 2

Complete the provided template code (lab5_p2_template.py) with a class BinaryTree that implements the

explained data structure “binary tree”. The following methods should be completed.

insert, isLeaf, delete, editNode, numOfChild, isFull

Now, let's delve into the functionality of each of these methods. In the following slides, we will provide you

with an example of each method's execution in the Python interactive shell.

*Here are the already provided methods: __init__, height, __str__, and __remove_trailing_none.Lab 5 AIC2100

21

Problem 2

Here's the template code.

You need to complete these methods.

This is a provided initialization. Do not modify this unless you want to use

the non-list implementation.Lab 5 AIC2100

22

Problem 2

Here's the template code.

These are already completed. However, if you want to customize

them, you can freely modify them, but the class should still follow the

requested specifications.Lab 5 AIC2100

23

Problem 2

Method __init__(self, root_e): Initialization. root_e is a root node. Hereafter, assume that all nodes

will be represented by a one-letter character, including lower case, upper case, and digits 0-9 (in string, like

'1').

>>> from lab5_p2 import BinaryTree

>>> bt = BinaryTree('a')

>>>

(continues on next section …)

a

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

24

Problem 2

Method insert(self, e, parent, pos): Node insertion. e is a node name to be inserted, parent is a parent node of e,

and pos is a string flag where 'l' refers to left and 'r' refers to right. For instance, bt.insert('b', 'a', 'l') refers to

“insert node ‘b’ as a left child of ‘a’.”. This method should include duplicate checking, (parent) node existence checking,

and position collision. In such cases, the error message should be printed, and the tree should not be edited. Proceed

duplicate checking first, parent node checking second, and then position collision last.

>>> bt.insert('b', 'a', 'l')

>>> bt.insert('c', 'a', 'r')

>>> bt.insert('b', 'b', 'l') # Name already used!

Insertion˽refused:˽Node˽'b'˽already˽exists¤

>>> bt.insert('k', 'x', 'l') # No such parent node!

Insertion˽refused:˽Node˽'x'˽does˽not˽exist¤

>>> bt.insert('d', 'a', 'l') # Position colliding with 'b'!

Insertion˽refused:˽Left˽child˽of˽node˽'a'˽already˽occupied˽by˽'b'¤

>>> bt.insert('d', 'a', 'r') # Position colliding with 'c'!

Insertion˽refused:˽Right˽child˽of˽node˽'a'˽already˽occupied˽by˽'c'¤

>>> bt.insert('b', 'a', 'r') # Duplicate name will be detected first

Insertion˽refused:˽Node˽'b'˽already˽exists¤

>>>

(continues on next section …)

a

b c

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

25

Problem 2

Method isLeaf(self, e): Check if a node e is a leaf node (i.e., no child node) and return a boolean flag. If

given node e does not exist, print an error message and return None.

>>> flag_a = bt.isLeaf('a')

>>> flag_b = bt.isLeaf('b')

>>> flag_c = bt.isLeaf('c')

>>> print(flag_a, flag_b, flag_c)

False˽True˽True¤

>>> flag_e = bt.isLeaf('e')

Error:˽Node˽'e'˽does˽not˽exist¤

>>> print(flag_e is None)

True

>>>

(continues on next section …)

a

b c

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

26

Problem 2

Method delete(self, e): Check if a node e (1) exists and (2) is a leaf node, and then delete it. If such a

node does not exist or exists but is not a leaf node, deletion should not occur. If deletion occurs, no message

should be printed. Otherwise, print the error message like the below example.

>>> bt.insert('d', 'b', 'l')

>>> bt.insert('e', 'c', 'l')

>>> bt.insert('f', 'c', 'r')

>>> bt.delete('a')

Deletion˽refused:˽Node˽'a'˽is˽not˽a˽leaf˽node¤

>>> bt.delete('A')

Deletion˽refused:˽Node˽'A'˽does˽not˽exist¤

>>> bt.delete('d')

>>>

(continues on next section …)

a

b c

d e f

a

b c

e f

Node 'd' deleted

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

27

Problem 2

Method editNode(self, e_old, e_new): Change the node name e_old to e_new, if e_old exists and no

node has a name e_new. If e_old does not exist or e_new is already used in another node, the error

message should be printed. Check the existence of e_old first and then check e_new collision.

>>> bt.editNode('a', 'A')

>>> bt.editNode('q', 'x') # No such parent node!

Edit˽refused:˽Node˽'q'˽does˽not˽exist¤

>>> bt.editNode('b', 'e') # Name already used!

Edit˽refused:˽Node˽'e'˽already˽exists¤

>>> bt.editNode('q', 'e') # Both, but parent node existence will be checked first

Edit˽refused:˽Node˽'q'˽does˽not˽exist¤

>>>

(continues on next section …) A

b c

e f

a

b c

e f

Node 'a'

edited

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

28

Problem 2

Method numOfChild(self, e): Returns the number of child nodes of given node e. If e does not exist, print

the error message and return None. Otherwise, an integer should be returned without any message.

>>> childn_of_A = bt.numOfChild('A')

>>> print(childn_of_A)

2¤

>>> bt.insert('g', 'e', 'l')

>>> childn_of_e = bt.numOfChild('e')

>>> print(childn_of_e)

1¤

>>> childn_of_b = bt.numOfChild('b')

>>> print(childn_of_b)

0¤

>>> childn_of_x = bt.numOfChild('x')

Error:˽Node˽'x'˽does˽not˽exist¤

>>> print(childn_of_x is None)

True¤

(continues on next section …)

A

b c

e f

Node 'g' inserted

A

b c

e f

g

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

29

Problem 2

Method isFull(self): Returns the boolean flag of whether the tree (self) is a full binary tree or not (i.e., the

number of child nodes on all nodes is 0 or 2).

>>> is_full_before = bt.isFull()

>>> print(is_full_before)

False¤

>>> bt.delete('g')

>>> is_full_after = bt.isFull()

>>> print(is_full_after)

True¤

>>>

(continues on next section …)

A

b c

e f

Node 'g' deleted

A

b c

e f

g

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

30

Problem 2

Method height(self): Returns integer value of tree's height (the longest path from the root note to the leaft

node).

>>> height_before = bt.height()

>>> print(height_before)

3¤

>>> bt.insert('h', 'e', 'r')

>>> height_after = bt.height()

>>> print(height_after)

4¤

>>>

(continues on next section …)

A

b c

e f

Node 'h' inserted

A

b c

e f

h

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

31

Problem 2

Method __remove_trailing_none(self): Remove the trailing empty nodes (None), like the below

example.

['0', '1', '2', None, '3', None, None, None]

→

['0', '1', '2', None, '3']

This method may not be necessary, depending on your implementation.

Remove!Lab 5 AIC2100

32

Problem 2

Method __str__(self): Represent the tree as a string in the below format (this method is completed!)

1. No trailing blank

2. Nodes with the same hierarchy will be on the same line.

3. Each node will be shown as its value.

4. Empty nodes or empty spaces will be shown as a center dot special character (use '\u00B7').

5. There is one center dot between leaf nodes (including empty nodes) in the lowest hierarchy (bottom line)

6. Parent nodes are aligned to their left child node (even if the left child is empty!)

Please refer to the next slide example for the actual string output.Lab 5 AIC2100

33

Problem 2

>>> print(bt)

A¤

b·······c¤

········e···f¤

··········h¤

>>>

A

b c

e f

h

More examples in the next slides.

※ We used the whitespace (˽) and new line (¤)

notation for command outputs only.Lab 5 AIC2100

34

Problem 2

lab5_p2_script.py content omitted in the document (a bit lengthy)… please download and read it on your own.Lab 5 AIC2100

35

Problem 2

lab5_p2_script2.py content omitted in the document (a bit lengthy)… please download and read it on your own.

a

b c

1 2 x y

A

B C

D E F G

H I J K L

M

N

O

Tree 1

Tree 2

A

B C

D E Q

H K N

O

Tree 3Lab 5 AIC2100

36

Problem 2

Note 1. You can assume that all node name parameters are always one-letter characters.

Note 2. Unless specified in the description, any type of faulty input will not be used during the grading (e.g.,

using other than 'l' and 'r' as pos parameters in insert method).

Note 3. You can use math module in this problem.

Hint. Test cases (during the grading) will include very few inputs that activate (specified) exception handling.

Q. Is it mandatory to use a list to implement the binary tree structure?

A. No, it is not mandatory. However, we highly encourage you to use it because the methods already

completed in the template are implemented based on the list. If you're gonna use another way, like defining

the class Node with the instances left and right child Node, you need to revise our provided ones together to

ensure the requested output format (the string representation of binary tree) remains consistent.Lab 5 AIC2100

37

Problem 3

Review lab 2 problem 4. We used the list to represent the polynomial equation, like [6, 2, -1,

0, 7] represents 6 + 2𝑥 −  

2 + 7  

4

. In problem 3, you have to write the class Polynomial,

which supports the evaluation, addition, multiplication, differentiation, and integration, where the

polynomial is represented by the integer list, like lab 2 problem 4. We first explain the assumptions

and notes of this problem before we delve into the class.

Note 1. The coefficient value is either an integer (int) or Fraction class from problem 1 (which

means you should import Fraction from lab5_p1.py.

Note 2. You can use the math module in this problem.

Note 3. You can assume that the last element of the coefficient list is non-zero.

Note 4. You can assume that the coefficient list is not empty.Lab 5 AIC2100

38

Problem 3

Method __add__: Addition. Return another Polynomial.

Method __sub__: Subtraction. Return another Polynomial.

Method __mul__: Multiplication. Return another Polynomial.

In the above three methods, you can assume that the other parameter is also Polynomial.

Method evaluate: For a given integer x, return the polynomial equation value. You can assume that x is

always an integer (this is already completed).

Method derivative: Return another Polynomial, which is the derivative of the self polynomial.

Method integral: Return another Polynomial, which is the integral of the self polynomial. In this method,

the parameter C (with the default value 0) refers to the integration constant.Lab 5 AIC2100

39

Problem 3

Here's the template code.

You need to complete these methods.

We provided the solution code's initialization method as

comments.

Exception handling in case that you failed to implement

Fraction classLab 5 AIC2100

40

Problem 3

Here's the template code.

We already completed the evaluation and string representation

method. Utilize these to debug your Polynomial setting.Lab 5 AIC2100

41

Problem 3

Example scriptLab 5 AIC2100

42

Problem 3

Additional notes!

Note 1. Suppose your __str__ of Fraction class is incorrect. In that case, you may not receive

points on the integration method (even if your implementation is correct) since our grading is

based on the "output" of the program execution.

Note 2. Fraction will be necessary only in one test case during the grading (i.e., all coefficients

will be an integer in the other cases). Therefore, if you failed to make Polynomial compatible with

Fraction, you can assume that the coefficients contain only integer(s), and this will still ensure a

sufficiently high score on successful implementation.Lab 5 AIC2100

43

Common notes and recaps

1. Provided codes are just templates, so it is free to customize them on your own. However, your

modification should still follow the specifications!

2. Please pay particular attention to the file name. The format of the provided code's filename is

lab5_p{X}_template.py. You should rename this correctly before you archive your codes.

3. Please don't forget to fill in the docstrings (including your methods and our provided methods).Lab 5 AIC2100

44

Marking Criteria

• Score is only given to programs that compile and produce the correct output with Python version 3.

• No points for programs that are named wrongly. Please refer to the following slide for the required file

names.

• Points are deducted for programs that produce warnings.

• Please pay particular attention to the requested output format of your programs. Deviating from the

requested output format results in points deductions.Lab 5 AIC2100

45

Plagiarism

• Plagiarism (Cheating)

– This is an individual assignment. All or some submissions are checked for plagiarism.

• We will not inform you which problems will be checked.

– Once detected, measures will be taken for all students involved in the plagiarism incident

(including the "source'' of the plagiarized code).Lab 5 AIC2100

46

• Please prepare the files for the programming problems. The names of the files, their due dates, and the

archive file names are given in the table above.

• Please upload your archive file by the stated due date on LearnUs.

• Please pay attention to file names.

• Putting files into archives has been explained in the Lab 0 specification and additional document.

Deliverables, Due Date and Submission

Problem File name Due Archive name

1 lab5_p1.py

Saturday

June 8, 2024,

19:00

2 lab5_p2.py lab5_<student id>.zip

3 lab5_p3.py