辅导 AIC2100、Python设计编程讲解
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_.zip
3 lab5_p3.py