Data Structures And Algo

1. Provide the asymptotic growth of the following recurrence relations. Assume that they all have base cases of 7(0) = T(1) = 0(1). Justify your answers. • la. T(n) = 31(n/1) +0(n) • 1b. 7(n) = 2T (n/5) + 6(1) • 1c. T(n)=21(2n/3) + (n²) • 1d. T(n) = T(n/2)+T(2n/5)+ 0(n) • le. T(n)= T(3n/5)+7(1/5)+8(n²)

3. The Stirling numbers of the second kind, S(n, k), is a collection of numbers important in combinatorics. For example, they count the number of ways to group n items into k sets. They can be defined recursively as follows. • S(0,0)=1 S(1,0) = S(0,n) = 0 ifn>0 S(n, k) = k-S(n − 1,k) + S(n − 1, k − 1) if n>0 and k>0 2 For example, S(3,2)=2S(2, 2)+S(2, 1), where we can recursively compute S(2,2)= 1 and S(2,1)= 1, therefore S(3,2) = 3 (and there are three different ways to group three items into two sets). • 3a. Give a recursive algorithm for computing S(n, k) based on the above recurrence. • 3b. Explain and show how to turn the recursive algorithm into a memo- ization algorithm. 3c. Explain and show how to compute S(n, k) via a dynamic programming algorithm.

4. The following equation describes the recurrence underlying our dynamic programming algorithm for Edit Distance for the case of operations COPY (cost 0), INSERT (cost 2), DELETE (cost 2) and REPLACE (cost 3). Here, as in the course, c[i,j] describes entry (i.j) of the dynamic programming table, 7₂ is character number i of the input string and y; is character number j of the output string, 1 <i<m and 1≤j≤n. ci-1.j-1] c[i,j] = min 3+ci-1.j-1] if i = 0 and j = 0 if i > 0, j>0 and z = 95 ifi>0 and j> 0 if i > 0 if j > 0 2+ci-1.j (2+ci.j-1] Describe a modification of the equation to incorporate the following operation:

1 Functional Dependencies The following set of questions attempts to answer the question of where functional de pendencies come from. In this case, they may come from application's requirements. You are given the following relation: Purchase (CustomerID, Product ID, ShopID, Price, Date) Your task is to identify the precise functional dependencies for each of the specification. By "precise", it means that the functional dependencies satisfies the requirement and do not add unnecessary constraints.

2 Functional Equivalence In the following set of questions, we will define a new terminology. Your task is to understand the terminology and apply it to the concepts you have learnt in this module. Consider a relation R. We say that two sets of attributes a and B (e.g., we can have a = {A, B} or a = {A,B,C} or even a = {4}) are functionally equivalent if and only if the two following two functional dependencies holds in R: • a → B • B+a NOTE: This is different from two sets of functional dependencies being equivalent. Using the given definition above, answer the following questions. There may be more than one correct answers, you are to select ALL of them.

3 Normalization The following set of questions is part of the process of schema refinement. We want to find a normalization (BCNF or 3NF) of the given relation with the given set of functional dependencies. Consider a relation R(A, B, C, D, E) with the set of functional dependencies Σ = { } {A, C, E} → {B}, {B,C} → {D, E}, Page 4 {C, D} {B, E} {A, C, D}, {A, B, C'} Answer the following questions. There may be more than one correct answers, you are to select ALL of them.

2. Find the max-flow in the flow network shown above using the Ford-Fulkerson algorithm, starting from the flow indicated in the figure. The notation used is: An are with a label a/b has current flow a and a maximum capacity of b. (Thus, the existing flow has a flow value of 3 units.) Draw the residual network after every augmentation.

1. Consider the digraph shown above. 1a. Give its strongly connected components. 1b. Draw its component graph.

4. Consider the following problem. The input is a target string T of length n and a set of words W = {₁,...,} of total length L (i.e., if | denotes the length of word w, then L = as a sequence of words from W. -1 ₁|w₂]). We want to know if T can be written For example, the target string T-abbababa with W = {abba, ab, aba, bab} can be written as ab+bab+aba. But the target string T-abbaba cannot be written in such a way. (These two examples have m=4, L=12, and n = 8 for the first one and n = 6 for the second one.) Show an algorithm that decides in polynomial time whether T can or cannot be written as a sequence of words from W. Hlint: Try a dynamic programming approach. Also state the worst-case running time of your algorithm as a function of n, m and/or L.

3. Consider the following 2-CNF formula: F = (-a V b)^(-bVc) ^ (cV b) ^ (bV-d) ^ (e Vb) ^ (Ve) • 3a. Draw the digraph corresponding to F. •3b. Use the digraph to prove that F is satisfiable, and find a satisfying assignment to F. • 3c. Further use the digraph to list all satisfying assignments to F.