:
Let R ⊆ S × S be any binary relation on a set S. Consider the sequence of relations R0, R1, R2, . . ., defined as follows:
R0 := I = {(x, x) : x
∈ S}, and Rn+1 := Rn ∪
(R; Rn) for n ≥ 0
(a) Prove that for all i, j ∈ N, if i ≤ j then Ri ⊆ Rj. Hint: Let Pi(j) be the proposition that Ri ⊆ Rj and prove
A binary tree is a data structure where each node is linked to at most two successor nodes:
If we include empty binary trees (trees with no nodes) as part of the definition, then we can simplify the description of the data structure. Rather than saying a node has 0, 1, or 2 successor nodes, we can instead say that a node has exactly two children, where a child is a binary tree. That is, we can abstractly define the structure of a binary tree as follows:
• (B): An empty tree, τ
• (R): An ordered pair (Tleft, Tright) where Tleft and Tright are trees.
So, for example, the above tree would be defined as the tree T where:
T = (T1, T2), where
T1 = (T3, T4) and T2 = (T5, τ), where
T3
= T4 = T5 = (τ, τ)
That is,
T
A leaf in a binary tree is a node that has no successors (i.e. it is of the formEmail: (τ, τ)). A fully-internal node in a binary tree is a node that has exactly two successors (i.e. it is of the form (T1, T2) where T1, T2 ̸= τ). The example above has 3 leaves (T3, T4, and T5) and 2 fully-internal nodes (T and T1). For technical reasons (that will become apparent) we assume that an empty tree has 0 leaves and −1 fully-internal nodes.
(a) Based on the recursive definition above, recursively define a function count(T) that counts the number
(b) Based on the recursive definition above, recursively define a function leaves(T) that counts the number
(c) Based on the recursive definition above, recursively define a function internal(T) that counts the num-
sum(A,B):product(A,B): for i ∈ [0, n):for i ∈ [0, n):
for j ∈ [0, n):for j ∈ [0, n):
C[i, j] = A[i, j] + B[i, j]C[i, j] = add{A[i, k] ∗ B[k, j] : k ∈ [0, n)}
Assuming that adding end for end for and multiplying matrix elements can be carried out in O(1) time, and add end for end for will add the elements of a set S in O(|S|) return C return C time:
When n is even, we can define a recursive procedure for multiplying two n × n matrices as follows. First, break the matrices into smaller submatrices:
S T W X
A = B = U V Y Z
where S, T,U, V,W, X,Y, Z are matrices. Then it is possible to show:
SW + TY SX + TZ
AB
UW + VY UX + VZ
where SW + TY, SX +: TZ, etc. are sums of products of the smaller matrices. If n is a power of 2, each
smaller product (SW, TY, etc) can be computed recursively, until the product of 1 × 1 matrices needs to be computed – which is nothing more than a simple multiplication, taking O(1) time.
Assume n is a power of 2, and letAssignment Project Exam HelpT(n) be the worst-case running time for computing the product of two n × n matrices using this method.
(c) With justification, give a recurrence equation for T(n).
(d) Find an asymptotic upper bound forEmail: 4
T(n).
2
Problem 4
(a) Formulate this problem as a problem in propositional logic. Specifically:
Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five binary trees with three nodes:
(a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for
A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is a fullyinternal node) or two empty children (i.e. is a leaf).
(c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving
A well-formed formula is in Negated normal form if it consists of just ∧, ∨, and literals (i.e. propositional variables or negations of propositional variables). For example, (p ∨(¬q ∧¬r)) is in negated normal form; but (p ∨ ¬(q ∨ r)) is not.
Let F(n) denote the number of well-formed, negated normal form formulas there are that use precisely n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360.
Remark :
The T(n) are known as the Catalan numbers. As this question demonstrates they are very useful for counting various tree-like structures.
Consider the following directed graph:
3
1 2 5
and consider the following process:
• Initially, start at 1.
• At each time step, choose one of the outgoing edges from your current location uniformly at random, and follow it to the next location. For example, if your current location was 2, then with probability you would move to 3; with probability you would move to 4; with probability you would move to 5; and with probability you would stay at 2.
Let p1(n), p2(n), p3(n), p4(n), p5(n) be the probability your location after n time steps is 1, 2, 3, 4, or 5
respectively. So p1(0) = 1 and p2(0) = p3(0) = p4(0) = p5(0) = 0.
(a) Express p1(n + 1), p2(n + 1), p3(n + 1), p4(n + 1), and p5(n + 1) in terms of p1(n), p2(n), p3(n), p4(n), and p5(n).
(b) Prove ONE of the following:
Note
Remark
This is an example of a Markov chain – a very useful model for stochastic processes.:
Advice on how to do the assignment
• Assignments are to be submitted via inspera.
• When giving answers to questions, we always would like you to prove/explain/motivate your answers. You are being assessed on your understanding and ability.
• Questions have been given an indicative difficulty level:
Pass Credit Distinction High distinction
