Unformatted text preview:

CS 6363: Algorithms − Spring 2022Homework #2 Due: Feb. 17Professor D.T. HuynhProblem #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 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 b e O(logn)). Using the decision tree metho d, sh ow that your algorithm is optimal.Problem #2. You have n coins that are supp osed 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 efficient algorithm to find 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 finds it.Problem #4. Consider the alphab et Σ = {a, b, c}, and the following multiplication table: (note that this multiplication is not asso ciative)a b ca c b bb a b ac b a aDesign 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 = 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 shuffle 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 shuffle 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 shuffle 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


View Full Document

UTD CE 6363 - Homework #2

Documents in this Course
Load more
Download Homework #2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework #2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework #2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?