Problem 2: Let Un, for n ≥ 0, be the number of binary strings of length n in which no two 0's are at distance two apart. (More precisely, the difference of their positions in the string cannot be equal 2.) For example, U4 = 9, because there are 9 binary strings of length 4 that satisfy this condition: 0011, 0110, 0111, 1001, 1011, 1100, 1101, 1110, 1111. Derive the recurrence equation for Un. You need to give a clear and complete justification for your equation. (You do not need to solve the recurrence.)

Problem 2: Let Un, for n ≥ 0, be the number of binary strings of length n in which no two 0's are at distance two apart. (More precisely, the difference of their positions in the string cannot be equal 2.) For example, U4 = 9, because there are 9 binary strings of length 4 that satisfy this condition: 0011, 0110, 0111, 1001, 1011, 1100, 1101, 1110, 1111. Derive the recurrence equation for Un. You need to give a clear and complete justification for your equation. (You do not need to solve the recurrence.)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

7. For n 2 1, in how many out of the n! permutations T = (T(1), 7(2),..., 7 (n)) of the numbers {1, 2, ..., n} the value of 7(i) is either i – 1, or i, or i +1 for all 1 < i < n? Example: The permutation (21354) follows the rules while the permutation (21534) does not because 7(3) = 5. Hint: Find the answer for small n by checking all the permutations and then find the recursive formula depending on the possible values for 1(n).
Let A be the set of all strings of decimal digits of length 5. For example 24157 and05189 are strings in A.(a) How many strings in A have exactly one 7?(b) How many strings in A have at least two 2’s?(c) How many strings in A have the digits in a strictly decreasing order? For example97643 and 54321 are such strings, but 14820 and 95421 are not.
Please answer this question in 10 mins i will surely rate your answer. Given an integer string, create all integer permutations of its digits. Determine if there is a permutation whose integer value is evenly divisible by 8, L.e. (permutation value) mod 8 = 0. For example, the possible permutations of 123 are p= (123, 132, 213, 231, 312, 321). Of these values, p[4]-312 is divisible by 8 because 312 mod 8=0. Function Description Complete the function checkDivisibility in the editor below. The function must return an array of result strings, either YES or NO, where each result[i] denotes whether a permutation of arr[i] is divisible by 8. checkDivisibility has the following parameter(s): arr[arr[0]...arr[n-1]): an array of integer strings Constraints • 1≤ns45 Osarris 10110 All characters of arr[i] € (0-9) Input Format for Custom Testing Input from stdin will be processed as follows and passed to the function. The first line contains an integer n, the size of the array arr. Each of the…
Find value of X: a) Among binary strings of length 6 there is at least X strings that are 4-incompressible. b) Among binary strings of length 4 there is at least X strings that are 2-incompressible. c) Among binary strings of length X (find minimum) there are at least 25 strings that are 3-incompressible.
For Listing 5.8, another solution to find the greatest common divisor of two integers n1 and n2 is as follows: First find d to be the minimum of n1 and n2, and then check whether d, d - 1, d - 2, ..., 2, or 1 is a divisor for both n1 and n2 in this order. The first such common divisor is the greatest common divisor for n1 and n2.
Algorithm: Weighted Interval Scheduling & Dynamic Programming (Knapsack, Edit Distance) We say that a string w is a 'braid' of strings u and v if w can be written as the catenation of strings w = x_1*y_1*x_2*y_2 · · · x_n*y_n, where x_i , y_i are (possibly empty) strings such that u = x_1 · · · x_k and v = y_1 · · · y_k. For example, the string drnonfamatiicction is a braid of the strings 'dramatic' and 'nonfiction'. Given strings u, v, w with lengths m, n, m + n respectively, give an algorithm in pseudocode that determines whether w is a braid of u and v. Give proofs of correctness and running time for your algorithm.
f(x)= 5/(2x+4) is continuous at OR O [0,1/2] O Non
Computer Science you are given a string X of length n and another string Y of length m ≤n. Say,the indexes p1, p2, p3, p4 and q1, q2, q3, q4 form two sub-sequences, i.e., 0 ≤ p1 < p2 < p3 < p4 < nand 0 ≤q1 < q2 < q3 < q4 < n; then, they are non-overlapping if p4 < q1.The task is to count the maximum number of non-overlapping sub-sequences of X that are thesame as Y . Thus, if X = GAXTYAWBGTAUGBTABGRGTAXB and Y = GTAB, then the answer is3 as shown by the red fonts. We cannot select the underlined GTAB as it overlaps with a red GTAB(i.e., among overlapping sub-sequences, you can select only one of them).Describe an O(m + n) time algorithm to obtain the count. Write a pseudo-code.
Let N = {0, 1, 2, . . .} be the set of Natural Numbers. Given an n ∈ N, which of the followingconditions are necessary, and which of these conditions are sufficient, for the Natural Number,n, to be a factor of 10.(a) 1 is a factor of n.(b) 1 is a factor of 2n.(c) −n is a factor of 10.(d) 10 is a multiple of n.(e) n is divisible by 2.(f) n^2 is divisible of 5.(g) n = 10.
3. Two 7-digit integers (leading zeros allowed) are considered to be equivalent if one can be obtained from the other by rearranging its digits. For example, 0012234, 0312042, 3220014 and 2100243 are all considered equivalent, whereas 0012234 and 0001234 are not equivalent. How many nonequivalent 7-digit integers are there in which the digits 0, 2, 4 and 6 can each appear at most once?
You are given a multiset S. Over all pairs of subsets A and B, such that: • BC A; |B| = |A| – 1; greatest common divisor of all elements in A is equal to one; - find the sum of ErEA r · EnER x, modulo 998 244 353. x€A x€B Input The first line contains one integer m (1 < m < 10°): the number of different values in the multiset S. Each of the next m lines contains two integers a;, freq; ( 1< a; < 10°, 1 < freq; < 10°). Element a; appears in the multiset S freq; times. All a; are different. Output Print the required sum, modulo 998 244 353.
Let E, be the same as in Problem 1.33. Consider each row to be a binary number and let D = {w € E the top row of w is a larger number than is the bottom row}. For example, [][:]H] € D, but [:][ H) < D. Show that D is regular.