CS6363 Fall 2023 HW2 Solution 1 Problem 1 15 pts Problem Given an array of integers A 1 n such that A i A i 1 1 for all i 1 n That is the values of adjacent elements differ by at most 1 Let x A 1 and y A n and assume that x y Design an efficient search algorithm to find j such that A j z for a given value z with x z y Estimate the number of comparisons required by your algorithm it should be O log n Using the decision tree method show that your algorithm is optimal From the conditions we know that the array is a continuous function w r t integer Therefore we can apply binary search to find the value z Answer Consider the following two conditions 1 A i A i 1 1 2 x z y Algorithm 1 b search A i j 1 if j i 1 and z A i and z A j then return z does not exist return k 2 3 end 4 k i j 2 5 if x A k then 6 7 else if x A k then 8 9 else 10 11 end return b search A k 1 j return b search A i k 1 We assume that z is a global variable and initial values of i and j are 1 and n respectively There are n leaves in the tree and its height is log2 n Thus we need O log n computations and this is an optimal time complexity for comparison based search algorithm 1 2 2 Problem 2 15 pts Problem You have n coins that are supposed to be gold coins of the same weight but you know that one coin is fake and weights less than the others There is available a balance scale so that you can put any number of coins on each side of the scale at one time and it will tell you whether the two sides weigh the same or which side weigh less than the other Outline an efficient algorithm to find the fake coin Determine the number of weighings as a function of n using the O notation Answer 1 Divide n coins into two piles of n 2 coins each leaving one extra coin apart if n is odd 2 Put the two piles on the scale If the piles weigh the same the coin put aside must be fake otherwise we can continue with the lighter pile containing the fake coin Time Complexity T n T n log2 n 2 1 for n 1 and T 1 0 Thus T n 3 3 Problem 3 15 pts Problem Let A 1 n be an array of n elements An element x is called a ma jority element in A 1 n if Card i A i x 2n 3 Give an O n algorithm that decides whether A 1 n contains a majority element and if so finds it Answer Solution 1 Idea If there exists a majority element that appears more than 2n 3 times in a given array then the majority must the median of the input array of n 1 distinct elements Algorithm 1 Given an unsorted input array A 1 n we use SELECT algorithm to de termine the median x of A 2 Then we pass over the array and count the number of times C that x ap pears If C 2n 3 then a majority element exists and it is x Otherwise there is no majority element Time Complexity SELECT algorithm runs in O n Counting the number of times that a majority element appears takes O n Therefore the algorithm runs in O n Solution 2 We will first try to eliminate as many elements as we can from being can didates for majority It runs out that we can eliminate all but one element Finding this one candidate is helped by the following observation which allows us to reduce the problem to a smaller one If xi xj and we eliminate both of these elements from the list then the majority in the original list remains a majority in the new list Notice that the opposite is not true the list 1 2 5 5 3 5 has no majority but if we remove 1 and 2 then 5 becomes a new majority So if we find two unequal cards we eliminate both find the majority in the smaller list and check whether it is a majority in the original list What if we do not find unequal cards If we scan the cards and they are all equal then we have to keep track of only one possible candidate once we find a vote that is not equal then we have to check only one candidate This is the seed of the idea we now show how to implement it The cards are scanned in the order they appear We use two variables C candidate and M multiplicity We we consider xi C is the only candidate for majority among x1 x2 xj 1 and M is the number of times that C appeared so far excluding the times C was eliminated 4 Algorithm 2 Find Majority A 1 C A 1 2 M 1 3 first scan eliminate all but one card C 4 for i 2 to n do if M 0 then C A i M 1 5 6 7 else if C A i then M M 1 M M 1 else end end 14 15 end 16 second scan check whether C is a majority 17 if M 0 then 18 19 else 20 M ajority 1 Count 0 for i 1 to n do 21 if A i C then Count Count 1 end if Count 2n 3 then M ajority C M ajority 1 else end 28 29 end 30 return M ajority 8 9 10 11 12 13 22 23 24 25 26 27 Time Complexity We used n 1 comparisons to find a candidate and n 1 comparisons in the worst case to determine whether this candidate is majority Thus overall there are at most 2n 2 comparisons In any case since there are constant number of other operations per comparison the overall running time is O n 5 4 Problem 4 20 pts Problem Consider the alphabet a b c and the following multiplication table note that this multiplication is not associative a c a b b b b a b b a a a b c Design an efficient algorithm that examines an input string w w1 wn and decides whether or not it is possible to parenthesize w in such a way that the value of the resulting expression is a For instance if w bbba then your algorithm should return Yes since b bb ba a Hint Use dynamic programming Answer symbols that could be generated with wij Let wij wiwi 1 wj and Vij denote the set of the possible If a V1n then the algorithm returns Yes Algorithm 3 Non Associative Multiplication Input String w1w2 wn …
View Full Document
Unlocking...