## 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