ECS 32B: Winter 2022 Homework Assignment 1 Rubric
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
ECS 32B: Winter 2022
Homework Assignment 1 Rubric
1. For each of the following code fragments, do the following:
• Calculate T(n), making sure not to discard constants or low-order terms yet
• Give what you think is the Big-O performance for the code fragment
• Use the technique shown in lecture to confirm that your proposed Big-O for the code fragment is correct (i.e., show your work)
1a: for i in range(1,n):
for j in range(1,n+1):
x = 3 * 4
T(n) = 2n(n-1) = 2n2 - 2n 3 points
valid reasoning for T(n) 2 points
O(n) is n2 3 points
valid proof for O(n) 2 points
1b: for i in range(n):
x = 2 * 3 - 1
T(n) = 3n 3 points
valid reasoning for T(n) 2 points
O(n) is n 3 points
valid proof for O(n) 2 points
1c: i = n
while i > 0:
x = 2 * 3 - 1
i = i - 1
T(n) = 5n + 1 3 points
valid reasoning for T(n) 2 points
O(n) is n 3 points
valid proof for O(n) 2 points
1d: for i in range(1,n+1):
for j in range(1,n+1):
for k in range(1,n+1):
x = 4 + 3 // 2 * 5
T(n) = 4n3 3 points
valid reasoning for T(n) 2 points
O(n) is n3 3 points
valid proof for O(n) 2 points
2. Suppose an algorithm solves a problem of size n in at most the number of steps listed for each T(n) given below. Calculate the Big-O for each T(n). Show your work, including values for c and n0 along the way.
2a: T(n) = 2
O(n) = 1 or k 6 points
valid proof for O(n) 4 points
2b: T(n) = 4n - 3
O(n) = n 6 points
valid proof for O(n) 4 points
2c: T(n) = 5n3 + 5 + 5n2
O(n) = n3 6 points
valid proof for O(n) 4 points
3. Create a Python function called encoder which expects two arguments. The first argument is a string representing a message to be translated into a coded message. The second argument is a list of lists serving as the key to be used to convert the original string to its coded equivalent. Each two-element list in the key represents a character that might be found in the original message paired with the character that will be substituted for the original character while building the coded message. The function returns a new string created by replacing every character in the message with its counterpart. Thisfunction does not print anything. Your function must be able to work with any code key passed as the second argument as long as it has the same list of lists structure described above. Use only the list of lists format described above and as shown in the examples below. Do not convert the second argument to some other data structure such as a dictionary....
Here's a program that works...
## this function takes a string and a code key (a list of two
## element lists)...it then builds a new string by looking up
## each character from the input string in the code key,
## retrieving the character associated with the character from
## the input string, and then concatenating the retrieved
## character to the end of the string being build. the function
## returns the new string
def encoder(message, key):
codedmessage = ""
for char in message:
codedmessage = codedmessage + findchar(char, key)
return codedmessage
## this function takes a character and a code key (a list of
## two element lists)...it looks up the character in the code
## key, retrieves the character associated with the input
## character, and returns that character
def findchar(target, key):
for pair in key:
if pair[0] == target:
return pair[1]
return("\\")
First, test with some of the data given in the prompt
e.g.
>>> code1 = [['a', 'n'],['b', 'o'],['c', 'p'],['d', 'q'],
['e', 'r'],['f', 's'],['g', 't'],['h', 'u'],
['i', 'v'],['j', 'w'],['k', 'x'],['l', 'y'],
['m', 'z'],['n', 'a'],['o', 'b'],['p', 'c'],
['q', 'd'],['r', 'e'],['s', 'f'],['t', 'g'],
['u', 'h'],['v', 'i'],['w', 'j'],['x', 'k'],
['y', 'l'],['z', 'm'],[' ', ' ']]
>>> test1 = "the quick brown fox jumped over the lazy dog"
>>> test3 = "we can't stop!"
>>> test4 = ""
>>> encoder(test1, code1)
'gur dhvpx oebja sbk whzcrq bire gur ynml qbt'
>>> encoder(test3, code1)
'jr pna\\g fgbc\\'
>>> encoder(test4, code1)
''
Second, test with a code key that is not in the prompt (your choice)
If all the results are correct, then award all 30 points.
If some of the results are incorrect, then award only 15 points.
If none of the results are correct, then award only 0 points.
In either case, there are some possible deductions:
-5 points if the program prints the string instead of returning the string (check the code)
-5 points if the program modifies the code key (list of lists)...for example, if the program converts the original data structure to a dictionary
-5 points if the program uses more than two loops
but don't let the point total go below 0
2022-01-22