logo

Two Approaches to Searching an Array

   

Added on  2019-09-16

2 Pages959 Words64 Views
 | 
 | 
 | 
Please use the file provided for coding.Note that the beginning of an array or list will have an index of 0. A file called ClassFile.py is provided containing classes. You should examine the classes so that you are aware of the attributes and methods available. Do not modify the classes unless asked to do so. All programming problems will go in the files Ex2Prog.py and ClassFile.py. Fill in the relevant function or method, do not change the parameters. The imports for these classes are contained at the top. Do not use these names for variables.1. Assume that we have an array containing n elements and we will search the array some number of times in the future. Now consider two possible approaches to searching this array. The1st approach simply performs a linear search through the array each time. The second approach sorts the array prior to searching for any element after which a binary search will be used for each search. Answer the following questions giving justification for your answer.a)Suppose that we perform O(lgn) searches. What are the worst case running times using both procedures? Which is better?b)Suppose that we perform Ω √n searches. What are the worst case running times of the two procedures? Which is better?c)If MergeSort is used for the sorting procedure what is the best case running time for the second approach?d)If InsertionSort is used for the sorting procedure what is the best case running time for thesecond approach?2. The following function determines whether or not a non-empty string S is a substring of some target string T. If it is the function returns True otherwise it returns False. The function works by considering every index for which T [index] == S[0] and index ≤ len(T) - en(S) as a possible start of a substring which matches S. The function begins at this character and proceeds checkingthe characters of T against S until either the entire string is matched or there is a miss at which point it moves to the next index where T matches the first character of S. Answer the questions below the following code. Note tm is an abbreviation for total matched. Below let n denote the length of the string Tdef search (S ,T): first char = S[0] matches = []len (S)+ for i in range (len(T) 1): if T[i] == first char: matches.append(i) for index in matches: tm = 0 while tm < len (S) and T[index + tm] == S [tm]: tm += 1 if tm == len (S): return True return False
Two Approaches to Searching an Array_1

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents