4. Given two lists A of size m and B of length n, our goal is...

   

Transcribed Image Text:

4. Given two lists A of size m and B of length n, our goal is to construct a list of all elements in list A that are also in list B. Consider the following two algorithms to solve this problem. procedure Search1 (List A of size m, List B of size n) Initialize an empty list L. SORT* list B. 1. 2. 3. 5. 6. for each item a A, if BinarySearch(a, B) #0 then Append a to list L. return L *Note: Assume that the SORT algorithm used in Search1 takes time proportional to k log k on an input list of size k, and that BinarySearch(a, B) matches the procedure binary search (x: integer, al, a2, an increasing integers) from lecture slides. procedure Search 2 (List A of size m, List B of size n) Initialize an empty list L. for each item a A, if Linear Search(a, B) #0 then Append a to list L. 1. 2. 3. 4. 5. return L (a) (2 points) Determine the runtime of Search1 in (b) (2 points) Determine the runtime of Search2 in (c) (2 points) When m (d) (2 points) When m notation, in terms of m and n. notation, in terms of m and n. (1), which algorithm has an asymptotically faster runtime? (n), which algorithm has an asymptotically faster runtime? (e) (2 points) Find a function f(n) so that when m e(f(n)), both algorithms have equal runtime asymptotically. 4. Given two lists A of size m and B of length n, our goal is to construct a list of all elements in list A that are also in list B. Consider the following two algorithms to solve this problem. procedure Search1 (List A of size m, List B of size n) Initialize an empty list L. SORT* list B. 1. 2. 3. 5. 6. for each item a A, if BinarySearch(a, B) #0 then Append a to list L. return L *Note: Assume that the SORT algorithm used in Search1 takes time proportional to k log k on an input list of size k, and that BinarySearch(a, B) matches the procedure binary search (x: integer, al, a2, an increasing integers) from lecture slides. procedure Search 2 (List A of size m, List B of size n) Initialize an empty list L. for each item a A, if Linear Search(a, B) #0 then Append a to list L. 1. 2. 3. 4. 5. return L (a) (2 points) Determine the runtime of Search1 in (b) (2 points) Determine the runtime of Search2 in (c) (2 points) When m (d) (2 points) When m notation, in terms of m and n. notation, in terms of m and n. (1), which algorithm has an asymptotically faster runtime? (n), which algorithm has an asymptotically faster runtime? (e) (2 points) Find a function f(n) so that when m e(f(n)), both algorithms have equal runtime asymptotically.

Answer rating: 100% (QA)

The image provided contains two procedure definitions Search1 and Search2 both of which are designed to find common elements between two lists A and B ... View the full answer