CS 6363 Algorithms Spring 2022 Homework 2 Due Feb 17 Professor D T Huynh Problem 1 Given an array of integers A 1 n such that A i A i 1 1 for all i 1 n 1 That is the values of adjacent elements di er by at most 1 Let x A 1 and y A n and assume that x y Design an e cient search algorithm to nd 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 logn Using the decision tree method show that your algorithm is optimal Problem 2 You have n coins that are supposed to be gold coins of the same weight but you know that one coin is fake and weighs 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 e cient algorithm to nd the fake coin Determine the number of weighings as a function of n using the O notation Problem 3 Let A 1 n be an array of n elements An element x is called a majority 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 nds it Problem 4 Consider the alphabet a b c and the following multiplication table note that this multiplication is not associative a c a b a b c b b b a c b a a Design an e cient 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 bbbba then your algorithm should return Yes since b bb ba a Hint Use dynamic programming Problem 5 Let X Y Z be strings over the alphabet Z is said to be a shu e of X and Y if Z can be written as Z X1Y1X2Y2 XnYn where Xi and Yj are strings in such that X X1X2 Xn and Y Y1Y2 Yn For example cchocohilaptes is a shu e of chocolate and chips but chocochilatspe is not Devise a dynamic programming algorithm that determines for X Y Z in the input whether Z is a shu e of X and Y Analyze the complexity of your algorithm Hint Construct a Boolean table Problem 6 Do Problem 15 4 5 on page 397 in CLRS