Description
CECS 229: Programming Assignment 1
Objectives:
1. Find all integers in a given range that are congruent to an integer under some modulo .
2. Find the -representation of a given integer.
3. Apply numerical algorithms for computing the sum of two numbers in binary
representation.
4. Apply numerical algorithms for computing the product of two numbers in binary
representation.
Problem 1:
Complete the function equiv_to(a, m, low, high) that returns a list of all the integers in
the range such that .
EXAMPLES:
Finding all integers such that :
IN: equiv_to(3, 5, -10, 15)
OUT: [-7, -2, 3, 8, 13]
Finding all integers such that :
IN: equiv_to(12, 15, -29, -11)
OUT: [-18]
Finding all integers such that :
IN: equiv_to(-20, 4, 3, 21)
OUT: [4, 8, 12, 16, 20]
a m
b
x
[low, high] x ≡ a (mod m)
−10 ≤ x ≤ 15 x ≡ 3 (mod 5)
−29 ≤ x ≤ −11 x ≡ 3 (mod 5)
3 ≤ x ≤ 21 x ≡ −20 (mod 4)
HINT:
By definition, all integers that are equivalent to under modulo must satisfy that
Hence,
Notice that if all the values must to be in the range , then
What lower- and upper-bound does this place on ? How do these -values allow us to find the
goal -values?
Problem 2:
Complete the function b_rep(n, b) that computes the base -representation of an integer
n given in decimal representation (i.e. typical base 10 representation). Your implementation
must use ALGORITHM 1.2.1 of the “Integer Representations & Algorithms” lecture notes.
No credit will be given to functions that employ any other implementation. The function can not
use built-in functions that already perform some kind of base -representation. For example, the
function implementation can not use the functions bin() or int(a, base=2) .
The function should satisfy the following:
1. INPUT:
n – a positive integer representing a number in decimal representation
b – an integer representing the desired base
1. OUTPUT:
a string containing the -expansion of integer a .
EXAMPLES:
IN: b_rep(10, 2)
OUT: 1010
IN: b_rep(10, 8)
x a m
x − a = m ⋅ k for some integer k
x = mk + a
x [low, high]
low ≤ mk + a ≤ high
k k
x
In [ ]:
def equiv_to(a, m, low, high):
k_low = # FIXME: update k_low
k_high = # FIXME: update k_high
k_vals = list(range(k_low, k_high +1))
x_vals = # FIXME: update x_vals
return x_vals
b
b
b
OUT: 12
IN: b_rep(10, 16)
OUT: A
Problem 3:
Complete the function binary_add(a, b) that computes the sum of the binary numbers
and
using ALGORITHM 1.2.3 of the “Integer Representations & Algorithms” lecture notes.
No credit will be given to functions that employ any other implementation. The function can not
use built-in functions that already perform some kind of binary representation or addition of
binary numbers. For example, the function implementation can not use the functions bin() or
int(a, base=2) .
The function should satisfy the following:
1. INPUT:
a – a string of the 0’s and 1’s that make up the first binary number. Assume the string
contains no spaces.
b – a string of the 0’s and 1’s that make up the second binary number. Assume the
string contains no spaces.
1. OUTPUT:
the string of 0’s and 1’s that is the result of computing .
EXAMPLE:
IN: binary_add( ‘101011’ , ‘11011’) In [22]:
def b_rep(n, b):
digits = [] # stores the digits of the b-expansion
q = n
while q != 0:
digit = # FIXME: Update digit
if b == 16 and digit > 9:
hex_dict = {10: ‘A’, 11 : ‘B’, 12: ‘C’, 13: ‘D’, 14: ‘E’, 15 : ‘F’}
digit = # FIXME: Update digit
digits.append(digit)
q = # FIXME: Update q
return # FIXME: Return the string of digits
a = (ai−1
, ai−2
,…, a0)2
b = (bj−1
, bj−2
,…, b0)2
a + b
OUT: ‘1000110’
Problem 4:
Complete function binary_mul(a, b) that computes the product of the binary numbers
and
using ALGORITHM 1.2.4 of the “Integer Representations & Algorithms” lecture notes. No credit
will be given to functions that employ any other implementation. The function can not use builtin functions that already perform some kind of binary representation or addition of binary
numbers. For example, the function implementation can not use the functions bin() or
int(a, base=2) .
The function should satisfy the following:
1. INPUT:
a – a string of the 0’s and 1’s that make up the first binary number. Assume the string
contains no spaces.
b – a string of the 0’s and 1’s that make up the second binary number. Assume the
string contains no spaces. In [42]:
def binary_add(a, b):
# removing all whitespace from the strings
a = a.replace(‘ ‘, ”)
b = b.replace(‘ ‘, ”)
# padding the strings with 0’s so they are the same length
if len(a) < len(b):
diff = len(b) – len(a)
a = “0” *diff + a
elif len(a) > len(b):
diff = len(a) – len(b)
b = “0” *diff + b
# addition algorithm
result = “”
carry = 0
for i in reversed(range(len(a))):
a_i = int(a[i])
b_i = int(b[i])
result += # FIXME: Update result
carry = # FIXME: Update carry
if carry == 1:
result += # FIXME: Update result
return # FIXME return the appropriate string
a = (ai−1, ai−2,…, a0)2
b = (bj−1, bj−2,…, b0)2
1. OUTPUT:
the string of 0’s and 1’s that is the result of computing .
EXAMPLE:
IN: binary_mul( ‘101011’ , ‘11011’)
OUT: ‘10010001001’
a × b
In [75]:
def binary_mul(a, b):
# removing all whitespace from the strings
a = a.replace(‘ ‘, ”)
b = b.replace(‘ ‘, ”)
# multiplication algorithm
partial_products = []
i = 0 # tracks the index of the current binary bit of string ‘a’ beginning at 0, r
for bit in reversed(a):
if bit == ‘1’:
partial_products.append(“””FIXME: Append the correct object to partial pro
i += 1
result = ‘0’
while len(partial_products) > 0:
result = binary_add(“FIXME: Input the correct arguments”)
del partial_products[0]
return # FIXME: Return the appropriate result
CECS 229: Programming Assignment 2
Objectives:
1. Use the Sieve of Eratosthenes to find all primes in a given range.
2. Design a computational algorithm for finding the Bézout coefficients of two integers.
3. Use Bézout coefficients to calculate the GCD.
NOTE:
Unless otherwise stated in the FIXME comment, you may not change the outline of the
algorithm provided by introducing new loops or conditionals, or by calling any built-in functions
that perform the entire algorithm or replaces a part of the algorithm.
Problem 1:
Complete the function primes(a, b) which uses the Sieve of Eratosthenes to create and
return a list of all the primes satisfying .
INPUT:
a – a positive integer greater than or equal to 1 ( ValueError if an integer less than
1 is given); the lower bound
b – a positive integer greater than or equal to a ( ValueError if b < a ); the
upper bound
OUTPUT:
a set of all the primes satisfying a b
EXAMPLE:
>> primes(1, 10)
p a ≤ p ≤ b
p ≤ p ≤
{2, 3, 5, 7}
>> primes(50, 100)
{53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
NOTE: The order of the elements might be different in your output in comparison to the
expected output, and that is okay! Your output is correct as long as you have all the primes.
Problem 2:
Complete the function bezout_coeffs(a, b) that computes the Bezout coefficients s and
t of a and b .
1. INPUT:
a , b – distinct integers
2. OUTPUT: {a: s, b: t} – dictionary where keys are the input integers and values are
their corresponding Bezout coefficients.
EXAMPLE: >> bezout_coeffs(414, 662)
{414 : 8, 662 : -5}
NOTE:
In [1]:
def primes(a, b):
if a < 1 or b < a: # handling invalid range
raise ValueError(“Invalid range given”)
if a == 1: # handling starting point a = 1
a = 2 # this ensures 1 is not listed as a prime
# FIXME: initialize `stop` which is the stopping criteria for
# the loop in the Sieve of Eratosthenes
stop = “FIXME: Replace this string”
# FIXME: initialize a Python set called `P` that contains
# all integers in the range [a, b]
P = set(“FIXME: Replace this string”)
for x in range(2, stop):
# FIXME: use Python list comprehension to create a set
# of multiples of x in the range [2, b];
# HINT: the set of multiples of x can be expressed as
# k * x, where k is an integer; hence the comprehension should
# loop over values that satisfy k * x <= b
multiples_x = set(“FIXME: replace this string”)
P -= multiples_x # removing the multiples of x from the set P
return P
The algorithm for the function bezout_coeff(a,b) uses the logic employed in the following
example:
Suppose . We seek and such that gcd
Let’s begin by defining . At every round in attempting to
attain the gcd, we will refer to and as the current coefficients of 13 and 21, respectively.
Round 1:
We will call this EQN 1
NOTICE:
Round 2:
from EQN 1
NOTICE:
Round 3:
a = 13, b = 21 s t (13, 21) = 13s + 21t
s0 = 1, t0 = 0, a1 = 13, b1 = 21
si ti
21 = 1 ⋅ 13 + 8
⟹ 8 = 21 − 1 ⋅ 13
⟹ s1 = −1, t1 = 1
s1 = − ( b1 div a1 ) = −(21 div 13) = −1
a2 = 8, b2 = 13
13 = 1 ⋅ 8 + 5
⟹ 5 = 13 − 1 ⋅ 8
= 1 ⋅ 13 − 1(21 − 1 ⋅ 13)
= 2 ⋅ 13 − 1 ⋅ 21
⟹ s2 = 2, t2 = −1
s2 = s0 − s1 ( b2 div a2)
= 1 − 1 ( 13 div 8)
= 1 − (−1)(1)
= 2
t2 = t0 − t1 ( b2 div a2)
= 0 − 1 ( 13 div 8)
= 0 − 1 (1)
= −1
NOTICE:
Round :
For any round , the corresponding and values are given by
You should verify for yourself that for any ,
a3 = 5, b3 = 8
8 = 1 ⋅ 5 + 3
⟹ 3 = 8 − 1
b3 div a3
⋅ 5
= 1 ⋅ ( 1
t1
⋅ 21 −1
s1
⋅ 13) − 1
b3 div a3
( 2
s2
⋅ 13 −1
t2
⋅ 21)
= −3 ⋅ 13 + 2 ⋅ 21
⟹ s3 = −3, t3 = 2
s3 = s1 − s2 ( b3 div a3)
= −1 − (2)(1)
= −3
t3 = t1 − t2 ( b3 div a3)
= 1 − (−1)(1)
= 2
⋮
k
k ≥ 2 sk
tk
sk = sk−2 − sk−1 ( bk div ak)
tk = tk−2 − tk−1 ( bk div ak)
a, b
s0 = 1
t0 = 0
s1 = −( b div a)
t1 = 1
In [22]:
def bezout_coeffs(a, b):
“””
computes the Bezout coefficients of two given positive integers
:param a: int type; positive integer
:param b: int type; positive integer
:returns: dict type; a dictionary with parameters a and b as keys,
Problem 3:
Create a function gcd(a, b) that computes the greatest common divisor of a and b using
the bezout_coeff function you implemented for problem 2 lecture. No credit will be given to
functions that employ any other implementation. For example, using the built-in function
math.gcd() as part of our implementation will not receive any credit.
INPUT:
* `a`,`b` – integers
OUTPUT: d – the gcd
EXAMPLE:
>> gcd(414, 662)
and their corresponding Bezout coefficients as values.
:raises: ValueError if a < 0 or b < 0
“””
if a < 0 or b < 0:
raise ValueError(
f”bezout_coeffs(a, b) does not support negative arguments.”)
s0 = 1
t0 = 0
s1 = -1 * (b // a)
t1 = 1
temp = b
bk = a
ak = temp % a
while ak != 0:
temp_s = s1
temp_t = t1
# FIXME: Update s1 according to the formula for sk
s1 = “FIXME: Replace this string”
# FIXME: Update t1 according to the formula for tk
t1 = “FIXME: Replace this string”
s0 = temp_s
t0 = temp_t
temp = bk
# FIXME: Update bk and ak
bk = “FIXME: Replace this string”
ak = “FIXME: Replace this string”
# FIXME: Replace each string with the correct coefficients of a and b
return {a: “FIXME: replace this string”, b: “FIXME: replace this string”}
2
HINT
The GCD of any two numbers must be positive by definition.
Problem 4:
Complete the function mod_inv(a, m) that returns the inverse of a modulo m that is in the
range . If the gcd of a and m is not 1, then the function raises a ValueError
exception.
Example:
>> mod_inv(3, 11)
4
In [26]:
def gcd(a,b):
“””
computes the greatest common divisor of two given integers
:param a: int type;
:param b: int type;
:returns: int type; the gcd of a and b
“””
A = abs(a)
B = abs(b)
if A == B:
pass # FIXME: replace this pass with the correct return value
bez = bezout_coeffs(A, B)
return # FIXME: replace this pass with the correct return value
[1, m − 1]
In [ ]:
def mod_inv(a, m):
“””
computes the inverse of a given integer a under a given modulo m
:param a: int type; the integer of interest
:param m: int type; the modulo
:returns: int type; the integer in range [0, m) that is the inverse of a under mod
:raises: ValueError if m < 0 or if a and m are not relatively prime
“””
if m < 0:
raise ValueError(f”mod_inv(a, m) does not support negative modulo m = {m}”)
g = gcd(a, m)
if g != 1:
raise ValueError(f”mod_inv(a, m) does not support integers that are not relati
A = a
while A < 0:
A += “””FIXME: replace this string so that by the end of the loop, A is in ran
inverse = “””FIXME: replace this string with the inverse of a under modulo m”””
while inverse < 0:
inverse += “””FIXME: replace this string so that by the end of the loop, the i
Problem 5:
Complete the function solve_mod_equiv(a, b, m, low, high) that returns a set all
integers satisfying,
and,
If gcd , ValueError is raised.
INPUT:
a , b , low , high – integers
m – positive integer, greater than 1
OUTPUT: Python set {} of all integers satisfying the conditions above.
EXAMPLE:
>> solve_mod_equiv(3, 4, 7, -5, 5)
{-1}
return inverse
x
ax ≡ b (mod m)
low ≤ x ≤ high
(a, m) ≠ 1
In [3]:
def solve_mod_equiv(a, b, m, low, high):
“””
computes all solutions to the equivalence ax ≡ b (mod m)
that are in the range [low, high]
:param a: int type; the coefficient of the unknown value x
:param b: int type; the integer that ax is equivalent to
under modulo m
:param m: int type; the modulo
:param low: int type; the lower bound for the solutions
:param high: int type; the upper bound for the solutions
:raises: ValueError if high < low or if m < 0
“””
if high < low:
raise ValueError(f”solve_mod_equiv() does not support the upper bound {high} l
if m < 0:
raise ValueError(f”solve_mod_equiv() does not support negative modulo m = {m}”
a_inv = mod_inv(a, m)
k_low = “””FIXME: replace this string with the correct lower bound for k, if x = m
k_high = “””FIXME: replace this string with the correct upper bound for k, if x =
x = “””FIXME: replace this string with the Python list comprehension that uses x =
return set(x)
CECS 229 Programming Assignment 3
Objectives:
1. Encrypt and decrypt text using an affine transformation.
2. Encrypt and decrypt text using the RSA cryptosystem.
NOTES:
1. Unless otherwise stated in the FIXME comment, you may not change the outline of the
algorithm provided by introducing new loops or conditionals, or by calling any built-in
functions that perform the entire algorithm or replaces a part of the algorithm.
2. You may use the utility functions found in util.py.
3. You may use any functions you implemented in previous programming assignments for this
course. If you choose to use them, please make sure to copy and paste their
implementation into pa3.py file, so that they are uploaded to CodePost when you submit
your work.
Problem 1:
Complete the function affine_encrypt(text, a, b) that returns the cipher text encrypted
using key ( a , b ). You must verify that the gcd(a, 26) = 1 before making the encryption. If
gcd(a, 26) != 1, the function must raise a ValueError exception with message “The
given key is invalid.” .
In [ ]:
def affine_encrypt(text, a, b):
“””
encrypts the plaintext ‘text’, using an affine transformation key (a, b)
:param: text – str type; plaintext as a string of letters
:param: a – int type; integer satisfying gcd(a, 26) = 1
Problem 2:
Complete the function affine_decrypt(ciphertext, a,b) that decrypts the text given in
ciphertext which was encrypted using key ( a , b ). You must verify that the gcd(a, 26) = 1. If
gcd(a, 26) != 1, the function must raise a ValueError exception with message “The
given key is invalid.” .
:param: b – int type; shift value
:raise: ValueError if gcd(a, 26) is not 1.
:return: str type; the encrypted message as string of uppercase letters
“””
# FIXME: raise an error if the gcd(a, 26) is not 1
cipher = “”
for letter in text:
if letter.isalpha():
# FIXME: Use util.py to initialize ‘num’ to be
# the integer corresponding to the current letter
num = None
# FIXME: Encrypt the current ‘num’ using the
# affine transformation with key (a, b).
# Store the result in cipher_digits.
cipher_digits = ‘None’
if len(cipher_digits) == 1:
# FIXME: If the cipherdigit is 0 – 9,
# prepend the string with a 0
# to make it a two-digit number
cipher_digits = None
# FIXME: Use util.py to append to the cipher the ENCRYPTED letter
# corresponding to the current cipher digits
cipher += ‘None’
return cipher
In [ ]:
def affine_decrypt(ciphertext, a, b):
“””
decrypts the given cipher, assuming it was encrypted using an affine transformatio
:param: ciphertext – str type; a string of digits
:param: a – int type; integer satisfying gcd(a, 26) = 1.
:param: b – int type; shift value
:return: str type; the decrypted message as a string of uppercase letters
“””
a_inv = 0 # FIXME: complete this line so that a_inv holds the inverse of a under m
text = “”
for letter in ciphertext:
if letter.isalpha():
letter = letter.upper()
# FIXME: Use util.py to find the integer `num` that corresponds
# to the given letter
Problem 3:
Complete the function encryptRSA(text, n, e) which uses RSA to encrypt the string
text using key (n, e) .
EXAMPLE
>> encryptRSA(“REPEAT”, 2537, 13)
‘194319342299’
num = None
# FIXME: Decrypt the integer that corresponds to the current
# encrypted letter using the decryption function for an affine
# transformation with key (a, b) so that letter_digits holds
# the decrypted number as a string of two digits
letter_digits = ‘None’
if len(letter_digits) == 1:
# FIXME: If the letter number is between 0 – 9, inclusive,
# prepend the string with a 0
letter_digits = None
# FIXME: Use util.py to append to the text the decrypted
# letter corresponding to the current letter digits
text += ‘None’
return text
In [ ]:
def encryptRSA(plaintext, n, e):
“””
encrypts plaintext using RSA and the key (n, e)
:param: text – str type; plaintext as a string of letters
:param: n – int type; positive integer that is the modulo in the RSA key
:param: e – int type; positive integer that is the exponent in the RSA key
:return: str type; the encrypted message as a string of digits
“””
text = plaintext.replace(‘ ‘, ”) # removing whitespace
# FIXME: Use util.py to initialize ‘digits’ as a string of
# the two-digit integers that correspond to the letters of ‘text’
digits = ‘None’
# FIXME: Use util.py to initialize ‘l’ with the length of each RSA block
l = 0
# FIXME: Use a loop to pad ‘digits’ with enough 23’s (i.e. X’s)
# so that it can be broken up into blocks of length l
# creating a list of RSA blocks
blocks = [digits[i:i + l] for i in range(0, len(digits), l)]
cipher = “”
for b in blocks:
# FIXME: Initialize ‘encrypted_block’ so that it contains
Problem 4:
Complete the implementation of the function decryptRSA(cipher, p, q, e) which
decrypts cipher , assuming it was encrypted using RSA and key .
EXAMPLE:
>> decryptRSA(‘03412005’, 43, 59, 23)
STOP
# the encryption of block ‘b’ as a string
encrypted_block = ‘None’
if len(encrypted_block) < l:
# FIXME: If the encrypted block contains less digits
# than the block size l, prepend the block with enough
# 0’s so that the numeric value of the block
# remains the same, but the new block size is l,
# e.g. if l = 4 and encrypted block is ‘451’ then prepend
# one 0 to obtain ‘0451’
encrypted_block = None
# FIXME: Append the encrypted block to the cipher
cipher += ‘None’
return cipher
(n = p ⋅ q, e)
In [ ]:
def decryptRSA(cipher, p, q, e):
“””
decrypts the cipher, which was encrypted using RSA and the key (p * q, e)
:param: cipher – ciphertext as a string of digits
:param: p, q – prime numbers used as part of the key n = p * q to encrypt the ciph
:param: e – integer satisfying gcd((p-1)*(q-1), e) = 1
:return: str type; the decrypted message as a string of letters
“””
n = p * q
ciphertext = cipher.replace(‘ ‘, ”)
# FIXME: Use util.py to initialize `l` with the size of
# each RSA block
l = 0
# FIXME: Use a Python list comprehension to break the ciphertext
# into blocks of equal length ‘l’. Initialize ‘blocks’ so that it
# contains these blocks as elements
blocks = []
text = “” # initializing the variable that will hold the decrypted text
# FIXME: Compute the inverse of e
e_inv = None
for b in blocks:
# FIXME: Use the RSA decryption function to decrypt
# the current block
decrypted_block = ‘None’
if len(decrypted_block) < l:
# FIXME: If the decrypted block contains less digits
# than the block size l, prepend the block with
# enough 0’s so that the numeric value of the block
# remains the same, but the new block size is l,
# e.g. if l = 4 and decrypted block is ’19’ then prepend
# two 0’s to obtain ‘0019’
decrypted_block = None
# FIXME: Use util.py to append to text the decrypted block
# transformed into letters
text += ‘None’
return text
CECS 229 Programming Assignment 4
Objectives:
1. Apply vector operations to translate, scale, and rotate a set of points representing an
image.
2. Perform various operations with or on vectors: addition, subtraction, dot product, norm.
NOTES:
1. Unless otherwise stated in the FIXME comment, you may not change the outline of the
algorithm provided by introducing new loops or conditionals, or by calling any built-in
functions that perform the entire algorithm or replaces a part of the algorithm.
2. You may import and use the Python math module to obtain the value for and to
calculate sine, cosine, and tangent functions, if needed.
Problem 1:
Create a function translate(S, z0) that translates the points in the input set by
. The function should satisfy the following:
1. INPUT:
S – set S
z0 – complex number
2. OUT:
T – set T consisting of points in S translated by
e
S
z0 = a0 + b0i
z0
In [ ]:
def translate(S, z0):
“””
translates the complex numbers of set S by z0
:param S: set type; a set of complex numbers
:param z0: complex type; a complex number
Problem 2:
Create a function scale(S, k) that scales the points in the input set by a factor of :
1. INPUT:
S – set S
k – positive float, raises ValueError if k 0.
2. OUTPUT:
a set consisting of points in S scaled by .
Problem 3:
Create a function rotate(S, tau) that rotates the points in the input set by radians:
1. INPUT:
S – set S
tau – float. If negative, the rotation is clockwise. If positive the rotation is
counterclockwise. If zero, no rotation.
2. OUT:
a set consisting of points in S rotated by
:return: set type; a set consisting of points in S translated by z0
“””
# FIXME: Implement this function
# FIXME: Return correct output
return None
S k
≤
k
In [ ]:
def scale(S, k):
“””
scales the complex numbers of set S by k.
:param S: set type; a set of complex numbers
:param k: float type; positive real number
:return: set type; a set consisting of points in S scaled by k
:raise: raises ValueError if k <= 0
“””
# FIXME: Implement this function.
# FIXME: Return correct output
return None
S τ
τ
In [ ]:
def rotate(S, tau):
“””
rotates the complex numbers of set S by tau radians.
:param S: set type; – set of complex numbers
:param tau: float type; radian measure of the rotation value. If negative, the rot
If positive the rotation is counterclockwise. If zero, no rotation.
:returns: set type; a set consisting of points in S rotated by tau radians
“””
# FIXME: Implement this function.
# FIXME: Return correct output
return None
Problem 4:
Finish the implementation of class Vec which instantiates row-vector objects with defined
operations of addition, subtraction, scalar multiplication, and dot product. In addition, Vec
class overloads the Python built-in function abs() so that when it is called on a Vec object, it
returns the Euclidean norm of the vector.
In [ ]:
class Vec:
def __init__(self, contents = []):
“””
Constructor defaults to empty vector
INPUT: list of elements to initialize a vector object, defaults to empty list
“””
self.elements = contents
return
def __abs__(self):
“””
Overloads the built-in function abs(v)
:returns: float type; the Euclidean norm of vector v
“””
# FIXME: Implement this method
# FIXME: Return correct output
return None
def __add__(self, other):
“””
overloads the + operator to support Vec + Vec
:raises: ValueError if vectors are not same length
:returns: Vec type; a Vec object that is the sum vector of this Vec and ‘other
“””
# FIXME: Finish the implementation
# FIXME: Return correct output
return None
def __sub__(self, other):
“””
overloads the – operator to support Vec – Vec
:raises: ValueError if vectors are not same length
:returns: Vec type; a Vec object that is the difference vector of this Vec and
“””
# FIXME: Finish the implementation
# FIXME: Return correct output
return None
def __mul__(self, other):
“””
Overloads the * operator to support
– Vec * Vec (dot product) raises ValueError if vectors are not
same length in the case of dot product; returns scalar
– Vec * float (component-wise product); returns Vec object
– Vec * int (component-wise product); returns Vec object
“””
if type(other) == Vec: #define dot product
# FIXME: Complete the implementation
# FIXME: Return the correct output
return None
elif type(other) == float or type(other) == int: #scalar-vector multiplication
# FIXME: Complete the implementation
# FIXME: Return the correct output
return None
def __rmul__(self, other):
“””Overloads the * operation to support
– float * Vec; returns Vec object
– int * Vec; returns Vec object
“””
# FIXME: Complete the implementation
# FIXME: Return the correct output
return None
def __str__(self):
“””returns string representation of this Vec object”””
return str(self.elements) # does NOT need further implementation
CECS 229 Programming Assignment 5
Objectives:
1. Define a matrix data structure with relevant matrix operations.
2. Use a matrix as a transformation function to rotate a 2-dimensional vector.
Notes:
Unless otherwise stated in the FIXME comment, you may not change the outline of the
algorithm provided by introducing new loops or conditionals, or by calling any built-in functions
that perform the entire algorithm or replaces a part of the algorithm.
Problem 1:
Implement a class Matrix that represents matrix objects with attributes
1. cols -columns of the Matrix object, as a list of columns (also lists)
2. rows -rows of the Matrix object, as a list of rows (also lists)
The constructor takes a Python list of rows as an argument, and constructs the columns
from these rows. If a list is not provided, the parameter defaults to an empty list.
You must implement the following methods in the Matrix class:
Setters
set_row(self, i, new_row) – changes the i-th row to be the list new_row . If
new_row is not the same length as the existing rows, then method raises a ValueError
with the message Incompatible row length.
set_col(self, j, new_col) – changes the j-th column to be the list new_col . If
new_col is not the same length as the existing columns, then the method raises a
ValueError with the message Incompatible column length.
m × n
set_entry(self,i, j, val) – changes the existing entry in the matrix to val .
Raises IndexError if does not satisfy or does not satisfy , where
number of rows and number of columns.
Getters
get_row(self, i) – returns the i-th row as a list. Raises IndexError if does not
satisfy .
get_col(self, j) – returns the j-th column as a list. Raises IndexError if does not
satisfy .
get_entry(self, i, j) – returns the existing entry in the matrix. Raises
IndexError if does not satisfy or does not satisfy , where
number of rows and number of columns.
get_columns(self) – returns the list of lists that are the columns of the matrix object
get_rows(self) – returns the list of lists that are the rows of the matrix object
get_diag(self, k) – returns the -th diagonal of a matrix where returns the
main diagonal, returns the diagonal beginning at , and returns the
diagonal beginning at . e.g. get_diag(1) for an matrix returns [
]
Helper methods
_construct_rows(self) – resets the rows of this Matrix according to the existing list
of lists self.cols representing the columns this Matrix
_construct_cols(self) – resets the columns of this Matrix according to the existing
list of lists self.rows representing the rows of this Matrix
Overloaded operators
In addition to the methods above, the Matrix class must also overload the + , – , and *
operators to support:
1. Matrix + Matrix addition; must return Matrix result
2. Matrix – Matrix subtraction; must return Matrix result
3. Matrix * scalar multiplication; must return Matrix result
4. Matrix * Matrix multiplication; must return Matrix result
5. Matrix * Vec multiplication; must return Vec result
6. scalar * Matrix multiplication; must return Matrix result
aij
i 1 ≤ i ≤ m j 1 ≤ j ≤ n
m = n =
i
1 ≤ i ≤ m
j
1 ≤ j ≤ n
aij
i 1 ≤ i ≤ m j 1 ≤ j ≤ n m =
n =
k k = 0
k > 0 a1(k+1) k < 0
a(−k+1)1 n × n
a12
, a23
, a34
,…, a(n−1)n
In [ ]:
from Vec import Vec
“””——————– PROBLEM 1 ——————–“””
class Matrix:
def __init__(self, rows):
“””
initializes a Matrix with given rows
:param rows: the list of rows that this Matrix object has
“””
self.rows = rows
self.cols = []
self._construct_cols()
return
“””
INSERT MISSING SETTERS AND GETTERS HERE
“””
def _construct_cols(self):
“””
HELPER METHOD: Resets the columns according to the existing rows
“””
self.cols = []
# FIXME: INSERT YOUR IMPLEMENTATION HERE
return
def _construct_rows(self):
“””
HELPER METHOD: Resets the rows according to the existing columns
“””
self.rows = []
# FIXME: INSERT YOUR IMPLEMENTATION HERE
return
def __add__(self, other):
“””
overloads the + operator to support Matrix + Matrix
:param other: the other Matrix object
:raises: ValueError if the Matrix objects have mismatching dimensions
:raises: TypeError if other is not of Matrix type
:return: Matrix type; the Matrix object resulting from the Matrix + Matrix ope
“””
pass # FIXME: REPLACE WITH IMPLEMENTATION
def __sub__(self, other):
“””
overloads the – operator to support Matrix – Matrix
:param other:
:raises: ValueError if the Matrix objects have mismatching dimensions
:raises: TypeError if other is not of Matrix type
:return: Matrix type; the Matrix object resulting from Matrix – Matrix operati
“””
pass # FIXME: REPLACE WITH IMPLEMENTATION
def __mul__(self, other):
“””
overloads the * operator to support
– Matrix * Matrix
– Matrix * Vec
– Matrix * float
– Matrix * int
:param other: the other Matrix object
:raises: ValueError if the Matrix objects have mismatching dimensions
:raises: TypeError if other is not of Matrix type
:return: Matrix type; the Matrix object resulting from the Matrix + Matrix ope
“””
if type(other) == float or type(other) == int:
print(“FIXME: Insert implementation of MATRIX-SCALAR multiplication”
) # FIXME: REPLACE WITH IMPLEMENTATION
elif type(other) == Matrix:
print(“FIXME: Insert implementation of MATRIX-MATRIX multiplication”
) # FIXME: REPLACE WITH IMPLEMENTATION
elif type(other) == Vec:
print(“FIXME: Insert implementation for MATRIX-VECTOR multiplication”
) # FIXME: REPLACE WITH IMPLEMENTATION
else:
raise TypeError(f”Matrix * {type(other)} is not supported.”)
return
def __rmul__(self, other):
“””
overloads the * operator to support
– float * Matrix
– int * Matrix
:param other: the other Matrix object
:raises: ValueError if the Matrix objects have mismatching dimensions
:raises: TypeError if other is not of Matrix type
:return: Matrix type; the Matrix object resulting from the Matrix + Matrix ope
“””
if type(other) == float or type(other) == int:
print(“FIXME: Insert implementation of SCALAR-MATRIX multiplication”
) # FIXME: REPLACE WITH IMPLEMENTATION
else:
raise TypeError(f”{type(other)} * Matrix is not supported.”)
return
”’——– ALL METHODS BELOW THIS LINE ARE FULLY IMPLEMENTED ——-”’
def dim(self):
“””
gets the dimensions of the mxn matrix
where m = number of rows, n = number of columns
:return: tuple type; (m, n)
“””
m = len(self.rows)
n = len(self.cols)
return (m, n)
def __str__(self):
“””prints the rows and columns in matrix form “””
mat_str = “”
for row in self.rows:
mat_str += str(row) + “\n”
return mat_str
def __eq__(self, other):
“””
overloads the == operator to return True if
two Matrix objects have the same row space and column space
“””
if type(other) != Matrix:
return False
this_rows = [round(x, 3) for x in self.rows]
other_rows = [round(x, 3) for x in other.rows]
this_cols = [round(x, 3) for x in self.cols]
other_cols = [round(x, 3) for x in other.cols]
Problem 2:
Complete the implementation for the method rotate_2Dvec(v, tau) which returns the
vector that results from rotating the given 2D-vector v by tau radians.
INPUT:
v : a Vec object representing a 2D vector.
tau : a Python float representing the number of radians that the vector vec should
be rotated.
OUTPUT:
a Vec object that represents the resulting, rotated vector.
return this_rows == other_rows and this_cols == other_cols
def __req__(self, other):
“””
overloads the == operator to return True if
two Matrix objects have the same row space and column space
“””
if type(other) != Matrix:
return False
this_rows = [round(x, 3) for x in self.rows]
other_rows = [round(x, 3) for x in other.rows]
this_cols = [round(x, 3) for x in self.cols]
other_cols = [round(x, 3) for x in other.cols]
return this_rows == other_rows and this_cols == other_cols
“””——————– PROBLEM 2 ——————–“””
def rotate_2Dvec(v: Vec, tau: float):
“””
computes the 2D-vector that results from rotating the given vector
by the given number of radians
:param v: Vec type; the vector to rotate
:param tau: float type; the radians to rotate by
:return: Vec type; the rotated vector
“””
pass # FIXME: REPLACE WITH IMPLEMENTATION
In [ ]:
def rotate_2Dvec(v: Vec, tau: float):
“””
computes the 2D-vector that results from rotating the given vector
by the given number of radians
:param v: Vec type; the vector to rotate
:param tau: float type; the radians to rotate by
:return: Vec type; the rotated vector
“””
if len(v) != 2:
raise ValueError(f”rotate_2Dvec is not defined for {len(v)}-D vectors.”)
# FIXME: COMPLETE THE REST OF THE METHOD