辅导COMP-208语言、讲解Python设计编程、python程序语言调试
- 首页 >> Python编程 ASSIGNMENT - Week 10
COMP-208, Fall 2020, Section 001 - 002
Due: November 14th, 2020 (23:59)
Please read the entire PDF before starting. You must do this assignment individually.
It is very important that you follow the directions as closely as possible. The directions, while
perhaps tedious, are designed to make it as easy as possible for the TAs to mark the assignments by letting
them run your assignment, in some cases through automated tests. Following closely the instructions will
allow the TAs to provide better feedback and not waste time on administrative details. Plus, if the TA is
in a good mood while he or she is grading, then that increases the chance of them giving out partial marks.
:)
To get full marks, you must:
• Follow all directions below
• Code your solution using the template provided in mycourses.
• Make sure that your code compiles and it is correct.
– Non-compiling code (code with syntax error) will receive a very low mark
• Write your name and student number in a comment in each .py file you hand in
• Indent your code properly
• Name your variables appropriately
– The purpose of each variable should be obvious from the name
– Use a docstring in each function to comment and validate your program
• Submit your code in codePost
– Make sure that your code passes the given test cases.
1
Part 0
Before starting the assignment, it is important that you complete the following steps. These steps are
optional (and will not be graded), but we highly recommend you to go through them.
• For this assignment, we will use the online platform called codePost to facilitate the automatic grade
of your work and to provide high-qualilty feedback on your programming work. The following are the
basic steps that you will have to perform in codePost.
1. Accessing and Signing up codePost: Please make sure that you can access codePost. In
order to login, you must use the link in the content section of the “Resources” tab located in
mycourses. Please fully review this link to get extra information about this task. https://help.
codepost.io/en/articles/3655946-student-signup-instructions
2. Submitting work to codePost: Once you have finished the coding part of the assignment, you
will need to upload your .py file to codePost. Please fully review this link to get extra information
about this task.
https://help.codepost.io/en/articles/3851633-how-can-i-submit-work-to-codepost.
If you need information about how to re-submit your work, please fully review this link to get
extra information about this task.
https://help.codepost.io/en/articles/3734695-can-i-resubmit.
For this assignment, you will be able to receive automated test results with your submission.
Please double check that your code passes all the test cases. Finally, and in order to have
peace of mind, you can check if your submission went through codePost, please fully review
this link to get extra information about this task. https://help.codepost.io/en/articles/
3734625-how-can-i-tell-if-my-submission-worked
Part 1
The questions in this part of the assignment will be graded.
During this week lecture, we studied how to solve a system of linear equations through a method called
Gauss-Jordan elimination. This method involves common operations on matrices (i.e., stacking a matrix,
elementary row operations [row swap, scalar multiplication, row addition]). In this assignment, we will study
a highly related method that is based on finding the inverse of a matrix. A system of linear equations can
be written as AX = B where A is the coefficient matrix, X is a column vector containing the variables, and
B is the right hand side. If AX = B, then X = A−1B, where A−1
represents the inverse of A (see below for
the operations performed to obtain this result).
AX = B .... initial statement
A−1
(AX) = A−1
(B) .... pre-multiply both sides by A−1
(A−1A)X = A−1B .... use the associative property to regroup factors
IX = A−1B .... when you multiply inverses together, they become the identity matrix
X = A−1B .... the identity matrix is like multiplying by 1.
Finding the inverse of a matrix is not only important to solve systems of linear equations, but it represents an
extremely important concept used in a huge variety of applications to model physical systems and engineering
models. You must be aware that numpy and/or scipy could be used to solve many numeric computing
problems. Actually, this assignment could be easily solved using this modules; however, you are not allowed
to use those modules (or any other module). This assignment is about understanding the implementation
principles to be able in a future to know how to apply them. Remember what was mentioned during the
lectures, libraries are good because they make it so easy to program, but they are bad because I will never
know how to do that myself. Then, lets do this assignment without the help of the libraries.
Page 2
Solving a system of linear equations by computing the inverse
The Gauss-Jordan elimination method (seen during the recording lecture video) can be used to determine a
matrix inverse (only possible for a square matrix with non-zero determinant). The main idea is that we will
now perform a sequence of row transformations (i.e., interchange of rows, multiply a row by a constant, add
a multiple of one row to another) to transform the matrix A to the identity matrix (i.e., a square matrix
with ones on the main diagonal and zeros elesewhere) and simultaneously perform the same sequence of
operations on the identity matrix I (we can do that by creating an augmented matrix M = [A|I] between A
and the identity matrix I).
Then, it is clear that to find the inverse (and to solve the equation X = A−1B) we will need the following
functions
• A multiplication method to multiply two matrices (i.e., to compute A−1B).
• A stacking method to obtain an augmented matrix (e.g., in the recording lecture video we computed
the augmented matrix M = [A|b] by stacking b as the last column to the matrix A)
• An un stacking method to extract the stacking matrix from the augmented matrix (e.g., following the
example shown in the recording lecture video, this method must return (extract) b from the augmented
matrix M = [A|b])
• A gauss jordan method that implements the elementary row operations to convert an augmented
matrix into a row-echelon form.
• An inverse method that calls the other methods to compute the inverse of a matrix
As mentioned before, the objective of this assignment is to implement the above-mentioned functions without
the help of (numerical computation) libraries such as numpy and scipy.
Question 1: multiplication (12 points)
The method called multiplication takes two Matrix objects as input and returns a new Matrix object
representing the multiplication of the two input matrices. if X is an m × n matrix and Y is an n × p
matrix, their matrix product XY is an m × p matrix, in which the n entries across a row of X are
multiplied with the n entries down a column of Y and summed to produce an entry of AB.
The following is a view of how the function looks in the Matrix.py file.
def multiplication(self, other):
’’’Returns a new Matrix object with the result of the matrix multiplication between
self.matrix and other.matrix
pre-req: self.num_columns == other.num_rows
’’’
"""
For this method you can safely assume that self.num columns == other.num rows (i.e., the multiplication
can always be computed); however you can not assume that self.num rows == other.num rows
(i.e., both matrices have the same dimensions).
Page 3
Question 2: stacking (12 points)
Complete the stacking function, which takes two Matrix objects as input and returns a new Matrix
object representing the augmented matrix of the inputs (i.e., it stacks the matrix of the second parameter
at the end to the matrix of the first parameter). if X is an m × n matrix and Y is an m × n matrix,
the augmented matrix M = [X|Y ] is an m × (2n) matrix,
The following is a view of how the function looks in the Matrix.py file.
def stacking(self, other):
’’’Returns a new Matrix object that represent the augmented matrix between self.matrix
and other.matrix
pre-req: self.num_rows == other.num_rows and self.num_columns == other.num_columns and
self.num_rows == self.num_columns
’’’
For this method you can safely assume that the matrices of both input objects have the same dimensions
(i.e., self.num rows == other.num rows and self.num columns == other.num columns).
Furthermore, both square matrices are square matrices (i.e., self.num rows == self.num columns). These
pre-requisite is very important because it differs from the stacking method of the recorded video lecture.
Please remember that in the video we stacked the vector b as the last column of the matrix A. Here,
for this assignment (and in order to compute the inverse of the matrix), we need to stack the identity
matrix I to the matrix A.
Question 3: un stacking (12 points)
Complete the un stacking function, which takes one Matrix object as input and returns a new Matrix
object representing the matrix that was stacked in the augmented matrix. If M (M = [X|Y ]) is the
augmented matrix, the un stacking method must return a new Matrix object representing the matrix Y .
The following is a view of how the function looks in the Matrix.py file.
def un_stacking(self):
’’’Returns a new Matrix object that represent the matrix that was stacked in the
augmented matrix self.matrix.
pre-req: self.num_columns % 2 == 0
’’’
For this method you can safely assume that the number of columns in the augmented matrix is even
(i.e., self.num columns % 2 == 0 )
Question 4: gauss jordan (12 points)
The gauss jordan function, which takes one Matrix object (which represents an augmented matrix)
as input, compute the gauss jordan elimination method on that augmented matrix and returns a new
Matrix object with the result.
The following is a view of how the function looks in the Matrix.py file.
def gauss_jordan(self):
’’’Returns a new Matrix object that represent the resulted matrix of applying the
gauss_jordan elimination method on the augmented matrix self.matrix.
pre-req: self.num_columns % 2 == 0
’’’
a = [row[:] for row in self.matrix]
for i in range(self.num_rows):
if a[i][i] == 0.0:
sys.exit(’Divide by zero detected!’)
for j in range(self.num_rows):
if i != j:
ratio = a[j][i]/a[i][i]
for k in range(self.num_columns):
a[j][k] = a[j][k] - ratio * a[i][k]
#Start of ’I could not update this part, HELP!!!’
for i in range(n):
x[i] = a[i][n]/a[i][i]
#End of ’I could not update this part, HELP!!!’
return Matrix(a)
This method has been provided to you and it is a copy/paste version of the code mentioned in the
recorded video lecture. Please remember that in the slide 14 (of the recorded video lecture) we provided
a link with a sample program
https://www.codesansar.com/numerical-methods/gauss-jordan-method-python-program-output.
htm. We just copied that code and modify small details to accommodate it to our OOP model. However,
we run out of time in the preparation of this assignment and we were not able to modify all the code.
Particularly, the code that is inside the two comments “#Start of ’I could not update this part, HELP!!!”’
and “#End of ’I could not update this part, HELP!!!”’ was not fixed. Your job for this question is to
modify that part of the code to make it work on our augmented matrix. Please remember that the code
that you saw in the recorded video lecture works in an augmented matrix M = [A|b] where b is a vector
with one column. For this assignment, we are working with an augmented matrix M = [A|I], where I is
the identity matrix whose dimensions are the same than A. Please do not forget to comment the code.
Question 5: inverse (12 points)
Finally we have everything that is needed to compute the inverse of our matrix. Complete the inverse
function, which takes one Matrix object as input and returns a new Matrix object representing the
inverse of the input matrix. Please remember the protocol to find the inverse of a matrix.
1. Create an augmented matrix M = [A|I] by stacking the matrix I at the end of the matrix A. Please
Page 5
notice that we provided the function create identity and at this point you have already coded
the function stacking
2. Run the Gauss Jordan elimination method on the augmented matrix created in the previous step.
3. un stacking and return the result.
The following is a view of how the function looks in the Matrix.py file.
def inverse(self):
’’’Returns a Matrix object representing the inverse of self.matrix
’’’
Question 6: my test (0 points)
The function my test is there to give you a starting point to test your functions. Please note that this
function will not be graded, and it is there only to make sure that you understand what every function
is expected to do and to test your own code. Note: In order for you to test your functions one at a time,
comment out the portions of the my test() function that call functions you have not yet written.
What To Submit?
Attached to this assignment is a file called Matrix.py. PLEASE note that the code outside the body of the
function must not be modified. You have to submit only this Matrix.py file. Please DO NOT zip (or rar)
your files, and do not submit any other files.
Where To Submit?
You need to submit your assignment in postCode. Please review the Section 0 if you still have questions
about how to do that. Please note that you do not need to submit anything to myCourses.
When To Submit?
Please do not wait until the last minute to submit your assignment. You never know what could go wrong
during the last moment. Please also remember that you are allowed to have multiple submission. Then,
submit your partial work early and you will be able to upload updated versions later (as far as they are
submitted before the deadline). If you could not finish the assignment, also submit what you have, beside
of having partial marks, you will also get feedback from your T.A to avoid the same errors in future
submissions.
How will this assignment be graded?
Each student will receive an overall score for this assignment. This score is called the “Combined score”
and it is the combination of the correctness and style scores. For this assignment, the correctness and style
scores have a weight of 72% and 28%, respectively.
• Correctness score: This score is between 0% and 72% depending on how many test cases your code
passed. For the first three question, we have created 4 test cases (1 open case and 3 blind cases) each
with a weight of 4% each. For the fourth and fifth questions, we have created 3 test cases (1 open cases
and 2 blind cases) each with a weight of 4%. The open cases will be run with-in your submissions and
you will receive automated test results (i.e., the autograder output) for them. You MUST guarantee
Page 6
that your code passes these cases. The open cases for this assignment correspond to the function calls
found in the function my test. The blind test cases are inputs that you have not seen and they will
test the correctness of your algorithm on those inputs once the deadline of the assignment is over.
• Style score: This score is between 0% and 28%. Your submission will be reviewed by your assigned
T.A. The T.A will evaluate your coding style (e.g., indentation, variable naming, comments, coding
style etc.) and they will give you feedback on it.
Page 7
COMP-208, Fall 2020, Section 001 - 002
Due: November 14th, 2020 (23:59)
Please read the entire PDF before starting. You must do this assignment individually.
It is very important that you follow the directions as closely as possible. The directions, while
perhaps tedious, are designed to make it as easy as possible for the TAs to mark the assignments by letting
them run your assignment, in some cases through automated tests. Following closely the instructions will
allow the TAs to provide better feedback and not waste time on administrative details. Plus, if the TA is
in a good mood while he or she is grading, then that increases the chance of them giving out partial marks.
:)
To get full marks, you must:
• Follow all directions below
• Code your solution using the template provided in mycourses.
• Make sure that your code compiles and it is correct.
– Non-compiling code (code with syntax error) will receive a very low mark
• Write your name and student number in a comment in each .py file you hand in
• Indent your code properly
• Name your variables appropriately
– The purpose of each variable should be obvious from the name
– Use a docstring in each function to comment and validate your program
• Submit your code in codePost
– Make sure that your code passes the given test cases.
1
Part 0
Before starting the assignment, it is important that you complete the following steps. These steps are
optional (and will not be graded), but we highly recommend you to go through them.
• For this assignment, we will use the online platform called codePost to facilitate the automatic grade
of your work and to provide high-qualilty feedback on your programming work. The following are the
basic steps that you will have to perform in codePost.
1. Accessing and Signing up codePost: Please make sure that you can access codePost. In
order to login, you must use the link in the content section of the “Resources” tab located in
mycourses. Please fully review this link to get extra information about this task. https://help.
codepost.io/en/articles/3655946-student-signup-instructions
2. Submitting work to codePost: Once you have finished the coding part of the assignment, you
will need to upload your .py file to codePost. Please fully review this link to get extra information
about this task.
https://help.codepost.io/en/articles/3851633-how-can-i-submit-work-to-codepost.
If you need information about how to re-submit your work, please fully review this link to get
extra information about this task.
https://help.codepost.io/en/articles/3734695-can-i-resubmit.
For this assignment, you will be able to receive automated test results with your submission.
Please double check that your code passes all the test cases. Finally, and in order to have
peace of mind, you can check if your submission went through codePost, please fully review
this link to get extra information about this task. https://help.codepost.io/en/articles/
3734625-how-can-i-tell-if-my-submission-worked
Part 1
The questions in this part of the assignment will be graded.
During this week lecture, we studied how to solve a system of linear equations through a method called
Gauss-Jordan elimination. This method involves common operations on matrices (i.e., stacking a matrix,
elementary row operations [row swap, scalar multiplication, row addition]). In this assignment, we will study
a highly related method that is based on finding the inverse of a matrix. A system of linear equations can
be written as AX = B where A is the coefficient matrix, X is a column vector containing the variables, and
B is the right hand side. If AX = B, then X = A−1B, where A−1
represents the inverse of A (see below for
the operations performed to obtain this result).
AX = B .... initial statement
A−1
(AX) = A−1
(B) .... pre-multiply both sides by A−1
(A−1A)X = A−1B .... use the associative property to regroup factors
IX = A−1B .... when you multiply inverses together, they become the identity matrix
X = A−1B .... the identity matrix is like multiplying by 1.
Finding the inverse of a matrix is not only important to solve systems of linear equations, but it represents an
extremely important concept used in a huge variety of applications to model physical systems and engineering
models. You must be aware that numpy and/or scipy could be used to solve many numeric computing
problems. Actually, this assignment could be easily solved using this modules; however, you are not allowed
to use those modules (or any other module). This assignment is about understanding the implementation
principles to be able in a future to know how to apply them. Remember what was mentioned during the
lectures, libraries are good because they make it so easy to program, but they are bad because I will never
know how to do that myself. Then, lets do this assignment without the help of the libraries.
Page 2
Solving a system of linear equations by computing the inverse
The Gauss-Jordan elimination method (seen during the recording lecture video) can be used to determine a
matrix inverse (only possible for a square matrix with non-zero determinant). The main idea is that we will
now perform a sequence of row transformations (i.e., interchange of rows, multiply a row by a constant, add
a multiple of one row to another) to transform the matrix A to the identity matrix (i.e., a square matrix
with ones on the main diagonal and zeros elesewhere) and simultaneously perform the same sequence of
operations on the identity matrix I (we can do that by creating an augmented matrix M = [A|I] between A
and the identity matrix I).
Then, it is clear that to find the inverse (and to solve the equation X = A−1B) we will need the following
functions
• A multiplication method to multiply two matrices (i.e., to compute A−1B).
• A stacking method to obtain an augmented matrix (e.g., in the recording lecture video we computed
the augmented matrix M = [A|b] by stacking b as the last column to the matrix A)
• An un stacking method to extract the stacking matrix from the augmented matrix (e.g., following the
example shown in the recording lecture video, this method must return (extract) b from the augmented
matrix M = [A|b])
• A gauss jordan method that implements the elementary row operations to convert an augmented
matrix into a row-echelon form.
• An inverse method that calls the other methods to compute the inverse of a matrix
As mentioned before, the objective of this assignment is to implement the above-mentioned functions without
the help of (numerical computation) libraries such as numpy and scipy.
Question 1: multiplication (12 points)
The method called multiplication takes two Matrix objects as input and returns a new Matrix object
representing the multiplication of the two input matrices. if X is an m × n matrix and Y is an n × p
matrix, their matrix product XY is an m × p matrix, in which the n entries across a row of X are
multiplied with the n entries down a column of Y and summed to produce an entry of AB.
The following is a view of how the function looks in the Matrix.py file.
def multiplication(self, other):
’’’Returns a new Matrix object with the result of the matrix multiplication between
self.matrix and other.matrix
pre-req: self.num_columns == other.num_rows
’’’
"""
For this method you can safely assume that self.num columns == other.num rows (i.e., the multiplication
can always be computed); however you can not assume that self.num rows == other.num rows
(i.e., both matrices have the same dimensions).
Page 3
Question 2: stacking (12 points)
Complete the stacking function, which takes two Matrix objects as input and returns a new Matrix
object representing the augmented matrix of the inputs (i.e., it stacks the matrix of the second parameter
at the end to the matrix of the first parameter). if X is an m × n matrix and Y is an m × n matrix,
the augmented matrix M = [X|Y ] is an m × (2n) matrix,
The following is a view of how the function looks in the Matrix.py file.
def stacking(self, other):
’’’Returns a new Matrix object that represent the augmented matrix between self.matrix
and other.matrix
pre-req: self.num_rows == other.num_rows and self.num_columns == other.num_columns and
self.num_rows == self.num_columns
’’’
For this method you can safely assume that the matrices of both input objects have the same dimensions
(i.e., self.num rows == other.num rows and self.num columns == other.num columns).
Furthermore, both square matrices are square matrices (i.e., self.num rows == self.num columns). These
pre-requisite is very important because it differs from the stacking method of the recorded video lecture.
Please remember that in the video we stacked the vector b as the last column of the matrix A. Here,
for this assignment (and in order to compute the inverse of the matrix), we need to stack the identity
matrix I to the matrix A.
Question 3: un stacking (12 points)
Complete the un stacking function, which takes one Matrix object as input and returns a new Matrix
object representing the matrix that was stacked in the augmented matrix. If M (M = [X|Y ]) is the
augmented matrix, the un stacking method must return a new Matrix object representing the matrix Y .
The following is a view of how the function looks in the Matrix.py file.
def un_stacking(self):
’’’Returns a new Matrix object that represent the matrix that was stacked in the
augmented matrix self.matrix.
pre-req: self.num_columns % 2 == 0
’’’
For this method you can safely assume that the number of columns in the augmented matrix is even
(i.e., self.num columns % 2 == 0 )
Question 4: gauss jordan (12 points)
The gauss jordan function, which takes one Matrix object (which represents an augmented matrix)
as input, compute the gauss jordan elimination method on that augmented matrix and returns a new
Matrix object with the result.
The following is a view of how the function looks in the Matrix.py file.
def gauss_jordan(self):
’’’Returns a new Matrix object that represent the resulted matrix of applying the
gauss_jordan elimination method on the augmented matrix self.matrix.
pre-req: self.num_columns % 2 == 0
’’’
a = [row[:] for row in self.matrix]
for i in range(self.num_rows):
if a[i][i] == 0.0:
sys.exit(’Divide by zero detected!’)
for j in range(self.num_rows):
if i != j:
ratio = a[j][i]/a[i][i]
for k in range(self.num_columns):
a[j][k] = a[j][k] - ratio * a[i][k]
#Start of ’I could not update this part, HELP!!!’
for i in range(n):
x[i] = a[i][n]/a[i][i]
#End of ’I could not update this part, HELP!!!’
return Matrix(a)
This method has been provided to you and it is a copy/paste version of the code mentioned in the
recorded video lecture. Please remember that in the slide 14 (of the recorded video lecture) we provided
a link with a sample program
https://www.codesansar.com/numerical-methods/gauss-jordan-method-python-program-output.
htm. We just copied that code and modify small details to accommodate it to our OOP model. However,
we run out of time in the preparation of this assignment and we were not able to modify all the code.
Particularly, the code that is inside the two comments “#Start of ’I could not update this part, HELP!!!”’
and “#End of ’I could not update this part, HELP!!!”’ was not fixed. Your job for this question is to
modify that part of the code to make it work on our augmented matrix. Please remember that the code
that you saw in the recorded video lecture works in an augmented matrix M = [A|b] where b is a vector
with one column. For this assignment, we are working with an augmented matrix M = [A|I], where I is
the identity matrix whose dimensions are the same than A. Please do not forget to comment the code.
Question 5: inverse (12 points)
Finally we have everything that is needed to compute the inverse of our matrix. Complete the inverse
function, which takes one Matrix object as input and returns a new Matrix object representing the
inverse of the input matrix. Please remember the protocol to find the inverse of a matrix.
1. Create an augmented matrix M = [A|I] by stacking the matrix I at the end of the matrix A. Please
Page 5
notice that we provided the function create identity and at this point you have already coded
the function stacking
2. Run the Gauss Jordan elimination method on the augmented matrix created in the previous step.
3. un stacking and return the result.
The following is a view of how the function looks in the Matrix.py file.
def inverse(self):
’’’Returns a Matrix object representing the inverse of self.matrix
’’’
Question 6: my test (0 points)
The function my test is there to give you a starting point to test your functions. Please note that this
function will not be graded, and it is there only to make sure that you understand what every function
is expected to do and to test your own code. Note: In order for you to test your functions one at a time,
comment out the portions of the my test() function that call functions you have not yet written.
What To Submit?
Attached to this assignment is a file called Matrix.py. PLEASE note that the code outside the body of the
function must not be modified. You have to submit only this Matrix.py file. Please DO NOT zip (or rar)
your files, and do not submit any other files.
Where To Submit?
You need to submit your assignment in postCode. Please review the Section 0 if you still have questions
about how to do that. Please note that you do not need to submit anything to myCourses.
When To Submit?
Please do not wait until the last minute to submit your assignment. You never know what could go wrong
during the last moment. Please also remember that you are allowed to have multiple submission. Then,
submit your partial work early and you will be able to upload updated versions later (as far as they are
submitted before the deadline). If you could not finish the assignment, also submit what you have, beside
of having partial marks, you will also get feedback from your T.A to avoid the same errors in future
submissions.
How will this assignment be graded?
Each student will receive an overall score for this assignment. This score is called the “Combined score”
and it is the combination of the correctness and style scores. For this assignment, the correctness and style
scores have a weight of 72% and 28%, respectively.
• Correctness score: This score is between 0% and 72% depending on how many test cases your code
passed. For the first three question, we have created 4 test cases (1 open case and 3 blind cases) each
with a weight of 4% each. For the fourth and fifth questions, we have created 3 test cases (1 open cases
and 2 blind cases) each with a weight of 4%. The open cases will be run with-in your submissions and
you will receive automated test results (i.e., the autograder output) for them. You MUST guarantee
Page 6
that your code passes these cases. The open cases for this assignment correspond to the function calls
found in the function my test. The blind test cases are inputs that you have not seen and they will
test the correctness of your algorithm on those inputs once the deadline of the assignment is over.
• Style score: This score is between 0% and 28%. Your submission will be reviewed by your assigned
T.A. The T.A will evaluate your coding style (e.g., indentation, variable naming, comments, coding
style etc.) and they will give you feedback on it.
Page 7