Fibonacci Sequences

let (f_k) be the Fibonacci sequence, show that: a) For every integer n>= 0, we have f_4(n+1) = 3f_4n+1 + 2f_4n b) Use a) in order to prove by induction that ∀n Є N, 3 | f_4n

Discrete Mathematics: Boolean Products

2. For the zero-one matrix | 1 0 0 | B= | 0 1 1 | | 1 0 1 | A) Find B[2] = B ...continues

Solve the system of congruence

Solve the system: 2x ≡ 1 (mod 3) 3x ≡ 2 (mod 5) 5x ≡ 3 (mod 2)

Discrete Structures

1) If f is the mod-5 function, compute each of the following. a) f(17) b) f(48) c) f(169) 3) Convert (1011101)2 to base 16 (i.e., hex) 4) Find the sum of products expansion of this Boolean function F(x,y) that equals 1 if and only if x = 1. Note: one can write out the phrase “y complement” to represent the notation f ...continues

Show, how the given binary search algorithm executes in case of given key value.

Given algorithm looks for a value in a nondecreasing sequence and returns the index of the value if it is found or 0 if it is not found. Input: A sequence si, ...... ,sj (j >= i >= 1) sorted in nondecreasing order, a value key, i, and j Output: The output is an index k for which sk = key, or if key is not in the sequence, t ...continues

Combinations

2. A seven-person committee composed of Adam, Betty, Cameron, David, Edward, Fritz, and Grace is to select a chairperson, secretary, and treasurer. How many selections are there where Betty is the chairperson, and Adam and Edward are not officers? 12 20 24 210 None of the above ...continues

Discrete Structures Questions

1. By using the Pigeonhole Principle, we can show that if you take six classes in a term and classes do not meet on the weekend, then at least three of the classes must meet on the same day. True False 2. By using the Pigeonhole Principle, it can be shown that if you are paid bi-weekly (every two weeks) duri ...continues

Find level numbers and ancestors of vertices in the given tree.

Attached figure [lib1312061.jpg] shows a subtree rooted at vertex p. Given that the level number for vertex u is 37, (a) What are the level numbers for vertices p, s, t, v, w, x, y and z? (b) How many ancestors do vertices u and y have?

List the vertices of given tree under Preorder and Postorder traversals.

List the vertices of tree in attachment lib1312062.jpg, when they are visited in a preorder traversal and in a postorder traversal.

Draw the splitting and merging trees obtained during sorting of given sequence of numbers using merge sort.

Sort the given sequence of numbers using merge sort. Draw the splitting and merging trees for each application of the procedure. -1, 0, 2, -2, 3, 6, -3, 5, 1, 4