ESC190 EXAM, April 20, 2021 =========================== Start time: 9:00am (unless otherwise specified). You have 2.5 hours to write the exam, and 30 minutes to submit it. You may continue writing the exam during the 30-minute submission window, but it is your responsibility to make sure that the exam is submitted on Gradescope on time. A penalty of 5 points (out of 105 possible points) will be subtracted for every minute of lateness. You may submit late with no penalty if you were approved by Accessbility Services. Aids allowed: you may consult the course textbooks, and course website and the ESC180 course website (http://www.cs.toronto.edu/~guerzhoy/180f20/). You may not consult other internet resources, books, or your notes. You may not communnicate with anyone about the exam apart from the course instructor on Piazza. You may find the files posted here useful: http://www.cs.toronto.edu/~guerzhoy/190/exam1234564/ You must monitor the course Piazza for announcement during the exam. You must submit all of Q1.c, Q2.c, Q3.py, Q4.py, and Q5.py togerther. It is your responsibility yo ensure the autograder ran on them. Problem 1 -- 20 pts (10 of 20 autograded) ======================================== In C, we can define an array of strings as follows: char *strs[] = {"ESC", "MAT", "MSE", "CIV"}; strs[0] would then be the pointer to "ESC". Write a function that allocates space for, and then returns the concatenated version of strings stored in an array of string. The function would look as follows: char* concat_all(char **strs, int strs_sz0){ //concatenate all strs_sz strings in strs, and return the resultant string } int main(void){ char *strs[] = {"ESC", "MAT", "MSE", "CIV"}; char *all = concat_all(strs, 4); printf("%s\n", all); //ESCMATMSECIV free(all); } You must make sure that there are no memory errors when the code is run. Autograder cases: char *strs[] = {"ESC", "MAT", "MSE", "CIV"}; char *all = concat_all(strs, 4); //all is ESCMATMSECIV Submit Q1.c, which contains the function, and does not contain a main function. Problem 2 -- 20 pts (8 of 20 autograded) ======================================== Write a C program that takes in an array of strings and the number of strings in the array, and returns 1 if there are repetitions in the array, and 0 otherwise. The function *must* run in average O(n) time, where n is the number of strings and must use hashing. The function siganture must be: int repeats(char **strs, int strs_sz); Briefly justify why the function runs in O(n) overage time in the comments. Autograder test cases: char *strs[] = {"ESC", "MAT", "MSE", "CIV"}; repeats(strs, 4) // 0 char *strs[] = {"ESC", "MAT", "MSE", "CIV", "ESC"}; repeats(strs, 5) // 1 Submit Q2.c, which contains the function, and not a main function. Problem 3 -- 20 pts (8 of 20 autograded) ======================================== A BST is defined as follows class BST: def __init__(self, value): self.value = value self.left = None self.right = None def insert(self, value): ''' node.insert(5) is the same as BST.insert(node, 5) We use this when recursively calling, e.g. self.left.insert ''' if value < self.value: if self.left == None: self.left = BST(value) else: self.left.insert(value) else: if self.right == None: self.right = BST(value) else: self.right.insert(value) def __repr__(self): '''The string representation of a node. Here, we convert the value of the node to a string and make that the representation. We can now use a = BST(4) print(a) # prints 4 ''' return str(self.value) Write a function def third_largest(node) that finds the value of the third-largest element in the BST. The function must run in O(h) time, where h is the height of the BST rooted in node. Sample autograder case: root = BST(1) root.insert(2) root.insert(3) third_largest(root) # 1 Submit Q3.py, which should contain the (unaltered)definition of the BST, and the implementation of the function third_largest(node) Problem 4 -- 20 pts (not autograded) ======================================== Write a python function def min_dist(u1, u2, u3) the functions takes in 3 lists of floats, each of length k, representing k-dimensional vectors. The function returns a list representing a k-dimensional vector v, such that |v-u1|^2 + |v-u2|^2 + |v-u3|^2 is as small as possible. (Recall that the norm of a vector |w| is sqrt(w1^2+w2^2+...+wk^2).) You MUST use gradient descent in order to complete this task. Make any reasonable algorithmic choices. Submit Q4.py, along with the sample output of Q4 that shows what minimum was achieved and at what value. This function will not be autograded. Problem 5 -- 25 pts (5 of 25 autograded) ======================================== In this problem, you will write a funciton that computes a particular definition of a distance between two lists, using dynamic programming, and returns the set of transformations that correpond to that distance. A element can be transformed by 1) Substituting one element with another 2) adding an element 3) removing an element The distance between two lists is the number of transformations required to transform one list into another. For example, the distance between [1, 1, 2, 3] and [2, 2, 3] is 2: [1, 1, 2, 3] (remove element) -> [1, 2, 3] -> (substitute 1 with 2) -> [2, 2, 3]. The elements of the list are given in a particular order. [1, 2, 3] and [3, 2, 1] are not the same list. To solve this problem using dynamic programming, for lists L1 and L2, define a 2-D array D s.t. D[i][j] is the distance between L[:i] and L[:j]. Hint: D[i][0] = i, since it takes i removals to get from L[:i] to the empty list. Part A ====== Write the function with the signature def construct_D_arr(L1, L2) which returns the 2D array D, such that D[i][j] is the distance between L1[:i] and L2[:j]. For example, construct_D_arr([1, 2], [1, 3]) should return D = [[0, 1, 2], [1, 0, 1], [2, 1, 1]] Your algorithm must be of complexity O(mn) where m = len(L1) and n = len(L2) Part B ====== Write a function def min_dist(L1, L2) which returns a length of the shortest sequences of transformations from L1 to L2. For example, min_dist(L1, L2) should return 1 since there is only one substitution needed in the sequence [1, 2]->[1, 3]. Your algorithm must be of complexity O(mn) where m = len(L1) and n = len(L2) Part C ====== Write a function def recover_path(L1, L2) which returns the shortest path between L1 and L2 via substitutions, deletions, and additions. For example, recover_path([1, 2], [1, 3]) can return [[1, 2], [1, 3]] (If there are multiple possible paths, return one of them.)