attached
1) Assume that you are provided a sorted array of distinct integer values C[0,...,n−1], and your task is to figure out whether there is an index i for which C[i] = i. – Provide a pseudocode for a divide and conquer algorithm for this problem, which has O(logn) run time. You must clearly show why the algorithm’s run time is O(logn). – Empirically show that your algorithm is correct. Some sample results are shown below, where the recursive “FindPointIndex()” function performs the required task. C = [-3,0,1,5,7,9,11] FindPointIndex(C,0,len(C)) # returns False C = [-3,0,2,5,7,9,11] FindPointIndex(C,0,len(C)) # returns True because C[1] = 1 2) Consider an example of the Stable Matching problem with five medical-school students, named S1, S2, S3, S4 and S5, and five hospitals, named H1, H2, H3, H4 and H5, whose preferences are given in the tables below, respectively. (a) Is the following matching (shown in blue colors above) stable? (b) Is the following matching (shown in blue colors above) stable? 3. NP completeness problems (a) It is known that the decision version of the Knapsack problem is N P-complete: Now consider a version of the Knapsack problem in which the vector c is restricted to be c ∈ {0,1}^n. Do you think it is possible that we can solve this problem in polynomial time? Explain. (If you think it is possible that it can be done in polynomial time, you do not have to specify a polynomial-time algorithm, just an argument for why it is plausible such an algorithm might exist.) (b) Suppose that you have been able to prove that a problem H ∈ N P has no polynomial time algorithm, and hence you have proved P 6= N P. Interestingly, you have not been able to establish that H is N P-complete.Given what you do know can you conclude that if Q is an N P-complete problem, then ? Explain your answer either way. 4) An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. Examples include “arc = car”, “python = typhon”, and “eleven plus two = twelve plus one”. In this question, we will focus on the Anagram Detection Problem (ADP) for words only, given as strings, assuming that the two given strings are of equal length, n, and that they are made up of symbols from the set of 26 lowercase alphabetic characters. Our goal is to write a boolean function that will take two strings and return whether they are anagrams. We will consider alternative algorithms for the ADP. (a) (Alternative 1) The first solution algorithm for the ADP checks to see that each character in the first string actually occurs in the second. If it is possible to “checkoff” each character, then the two strings must be anagrams. Checking off a character is accomplished by replacing it with the special Python value “None”. Perform big-O analysis on ADP1. Show your work, i.e., mention the input size, define the elementary operations, compute On and then provide big-O complexity (i.e., do not just guess big-O). (Alternative 2) An alternative approach is provided below. Explain the main logic of ADP2. That is, explain clearly what this algorithm is doing, how exactly it is checking whether the two strings are anagrams. Also, guess its big-O complexity and provide an explanation. 5) Consider the following dynamic programming algorithm to find the shortest path between a source node and a target node in a given graph G = (V,E). (a) Find the shortest path and its value for the example in Figure 1 below using the provided dynamic programming algorithm. Your answer must include the dynamic programming table (you can manually calculate it or write a python program for it), and you are required to explain how you obtain the edges/vertices in the shortest path. (b) Provide a python program that takes the vertex set, edge set, source node, and the target node as an input and returns the shortest path value and the set of nodes on the shortest path as an output. Sample input and output is provided below.