Data Structures and AlgorithmsKey to Homework 1January 31, 20051.5 Define an ADT for a set of integers (remember that a set may not contain duplicates). YourADT should consist of the functions that can be performed on the sets, with each functiondefined in terms of its input and output.Here are some possible operations.(a) Insert. Input: a set A and an integer n. Output: the set A ∪ {n}.(b) Delete. Input: a set A and an integer n. Output: the set A − {n}, if n ∈ A, and theset A together with a message to the effect that n isn’t in A, if n 6∈ A.(c) Member. Input: a s et A and an integer n. Output: true if n ∈ A, and false otherwise.(d) Union. Input: two sets A and B. Output: their union A ∪ B. Note that implementingthis may involve searching for duplicates.(e) Intersection. Input: two sets A and B. Output: their intersection A ∩ B.(f) Set difference. Input: two sets A and B. Output: their difference A − B. That is,the output is{a ∈ A : a 6∈ B}.Note that in an object-oriented setting (e.g., Java), the set (or one of the sets in the case ofunion, intersection, and set difference) will probably be an implicit input, since the operationwill most likely be a method on a set object.1.13 A common problem for compilers and text editors is to determine if the parentheses (or otherbrackets) in a string are balanced and properly nested. For example, the string ”((())())()”contains properly nested pairs of parentheses, but the string ”)()(” does not; and the string”())” does not contain properly matching parentheses.(a) Give an algorithm that returns true if a string contains properly nested and balancedparentheses, and false otherwise. Hint: At no time while scanning a legal string fromleft to right will you have encountered more right parentheses than left parentheses.The algorithm should scan the string from left to right, keeping track of the number ofunmatched left parentheses. If, at any time, the number is negative, there’s an unmatchedright parenthesis and the algorithm can terminate w ith an error message. If, after the entirestring has been scanned, the number of unmatched left parentheses is positive, there’s anunmatched left parenthesis and the algorithm should terminate with an error. If, after theentire string has been scanned, the number is 0, the string is OK. See Parens.java on theclass website for details.1Data Structures and Algorithms, Homework 1 23.3 Arrange the following expressions by growth rate from slowest to fastest.4n2log3(n) 3n20n 2 log2(n) n23Where does n! fit into this ordering?2 < log3(n) ≤ log2(n) < n23< 20n < 4n2< 3n.You can directly calculate that 6! = 720, 36= 729, 7! = 5040, and 37= 2187. So for n ≥ 7,n! > 3n.3.4 (a) Suppose that a particular algorithm has time complexity T (n) = 3·2n, and that exe cutingan implementation of it on a particular machine takes T seconds for n inputs. Nowsuppose that we are presented with a machine that is 64 times as fast. How many inputscould we process on the new machine in T se conds?(b) Suppose that another algorithm has time complexity T (n) = n2, and that executing animplementation of it on a particular machine takes T seconds for n inputs. Now supposethat we are presented with a machine that is 64 times as fast. How many inputs couldwe process on the new machine in T seconds?(c) Suppose that a third algorithm has time complexity T (n) = 8n, and that executing animplementation of it on a particular machine takes T seconds for n inputs. Now supposethat we are presented with a machine that is 64 times as fast. How many inputs couldwe process on the new machine in T seconds?The key to working these problems is observing that the runtime T tells you roughly thenumber of instructions executed. For example, suppose T = 1000 seconds and the old machinewill execute 106instructions/second. Then in T seconds, the old machine will execute 106×103= 109instructions, and the new machine will execute 64 × 109instructions. Thus, inany given period of time the new machine will do 64 times as much work as the old machine.Hence, if Told(n) is the runtime of a program on the old machine, its runtime will beTnew(n) =164Told(n)on the new machine.In the following discussion suppose that n0is the problem size on the old machine, and n1isthe problem size on the new machine.(a) We have Told(n) = 3 · 2n, and Told(n0) = T. We want to know for what value of n = n1will we have Tnew(n1) = T. Using our formulas, we have3 · 2n0=1643 · 2n1.So64 · 2n0= 2n1,and since 64 = 26, we have26+n0= 2n1.Thus, n1= 6 + n0. If, for example, we could previously solve a problem of size 100, wecan now solve a problem of size 106.Data Structures and Algorithms, Homework 1 3(b) Using reasoning similar to that in part (a), we haven20=164n21.So64n20= n21,and8n0= n1.So we can solve a problem 8 times larger on the new machine.(c) Reasoning as in part (a) again, we have8n0=1648n1,and64n0= n1.So we can solve a problem 64 times larger on the new machine.3.6 Using the definitions of big-Oh and Omega, find the upper and lower bounds for the followingexpressions. Be sure to state appropriate values for c and n0.(a) c1n(b) c2n3+ c3Since we’re interested in runtimes, I’ll assume that c1and c2are positive.(a) c1n is O(n) and Ω(n). For if we let c = c1and n0= 1, then we have thatc1n ≤ cn,for all n > n0, andc1n ≥ cn,for all n > n0.(b) c2n3+ c3is O(n3) and Ω(n3). First consider the case in which c3≥ 0. In this case wehavec2n3≤ c2n3+ c3≤ (c2+ c3)n3.for all n. The sec ond inequality holds because n ≥ 1 and hence n3≥ 1. So c3n3≥ c3.If c3< 0, then clearly c2n3+ c3≤ c2n3, for all n. So we only need to find c and n0sothatcn3≤ c2n3+ c3,for all n ≥ n0. To make things a little clearer, let c4= |c3|. Thenc2n3+ c3= c2n3− c4,and let T (n) = c2n3− c4.Now observe that if we choose c > 0 so that at some point n1> 0, we havecn31< c2n31− c4,Data Structures and Algorithms, Homework 1 4then we’ll havecn3< c2n3− c4,for all n ≥ n1. We know this because of the following observations. Consider the functionh(n) = c2n3− cn3− c4= (c2− c)n3− c4.• Then h(n) > 0 iff cn3< c2n3− c4.• So if cn31< c2n31− c4, h(n1) > 0.• But since n1> 0, n31> 0, in order for h(n1) > 0, we must have that c2− c > 0.• But c2− c is constant, and if n2> n1, then n32> n31.• So if n > n1, we must have h(n) > 0.• In other words, cn < c2n3− c4, for all n > n1.So we only need to find a point n1where T (n1) is positive, and then