4) Brute Force Algorithm Create the Difference cI' Twe Sets Given two arrays of integers A with len[A] = n and Ien[E} = m, create a third array C that includes all elements of A that are not in B. We write this operation as "A B"; we call the operation set difference; and we call the result "the difference ofthe two sets A and B" or simply "A minus B". Assume that in each array, each element is listed only once (there are no duplicates within the same array}, but the elements are not sorted. a} Write a brute force function that uses nested for loops to repeatedly check if each element in A matches any of the elements in B. If the element from A does not match any element in B, then copy it into the next available slot ofarray C. Do not sort any oftbe arrays at any time. Example: 1|With .4 = [2, 4, 6] and B = [3, 4, 5], your algorithm should pmduce C = [2, ti]. b) Trace the algorithm with A = sit], 4|], Tl], 3|], 1|], 3|], 5|], 9|], till} B = {35, 45, 55, t], 5t], 4U} c} Perfo rm asymptotic analysis to determine the maximum number of comparisons of array elements that are needed. What is the BigOh class for this algorithm in terms of m and n? 5) Master Method Use the master method to determine the Big-Oh class for an algorithm whose worst-case performance is given by each of these recurrence relations. a) (n) = 4T + n3 b) T(n) = 4T 2 + n2 c) T(n) = 4T + nE] Breadth First Search and Depth First Search a) Represent this graph using adjacency lists. Arrange the neighbors of each vertex in alphabetical order. b] Show the steps of a breadth first search with the graph using the technique given in the class notes. Use the adjacencyr lists representation that you created. Start at vertex A. As part of' your answer1 produce a graph that has the vertices numbered according to the order in which they were processedfvisited. c) Show the steps of a depth first search with the graph using the technique given in the class notes. Use the adjacency lists representation that you created. Start at vertex A. As part of' your answer1 produce a graph that has the vertices numbered according to the order in which they were processedfvisited

Transcribed Image Text:

Given two arrays of integers A with len(A) = n and len(B) = m, create a third array C that includes all elements of A that are not in B. We write this operation as "A-B"; we call the operation set difference; and we call the result "the difference of the two sets A and B" or simply "A minus B". Assume that in each array, each element is listed only once (there are no duplicates within the same array), but the elements are not sorted. a) Write a brute force function that uses nested for loops to repeatedly check if each element in A matches any of the elements in B. If the element from A does not match any element in B, then copy it into the next available slot of array C. Do not sort any of the arrays at any time. Example: With A = [2, 4, 6] and B = [3, 4, 5], your algorithm should produce C = [2, 6]. b) Trace the algorithm with A <20, 40, 70, 30, 10, 80, 50, 90, 60> B <35, 45, 55, 60, 50, 40> c) Perform asymptotic analysis to determine the maximum number of comparisons of array elements that are needed. What is the Big-Oh class for this algorithm in terms of m and n? Given two arrays of integers A with len(A) = n and len(B) = m, create a third array C that includes all elements of A that are not in B. We write this operation as "A-B"; we call the operation set difference; and we call the result "the difference of the two sets A and B" or simply "A minus B". Assume that in each array, each element is listed only once (there are no duplicates within the same array), but the elements are not sorted. a) Write a brute force function that uses nested for loops to repeatedly check if each element in A matches any of the elements in B. If the element from A does not match any element in B, then copy it into the next available slot of array C. Do not sort any of the arrays at any time. Example: With A = [2, 4, 6] and B = [3, 4, 5], your algorithm should produce C = [2, 6]. b) Trace the algorithm with A <20, 40, 70, 30, 10, 80, 50, 90, 60> B <35, 45, 55, 60, 50, 40> c) Perform asymptotic analysis to determine the maximum number of comparisons of array elements that are needed. What is the Big-Oh class for this algorithm in terms of m and n?