Recurrence, Relations (RR) and Cellular Automata (CA)
4 Pages1536 Words231 Views
Added on 2019-09-26
Recurrence, Relations (RR) and Cellular Automata (CA)
Added on 2019-09-26
ShareRelated Documents
Recurrence, Relations (RR) and Cellular Automata (CA)1.Find a RR for the number of ways to climb n stairs if the allowed steps are 1 or 2 staircases. What are the initial conditions for this RR? Solve the problem. In how many ways can one climb 50 stairs?2.Find the fix points for the tent map. Then g(x) = aMin(x, 1-x), 0 ≤x ≤1, 0 ≤a ≤2. Plot the location of the right fix point as function of a andthe derivative there. When is this fix point stable? Can you find a 2-cyclein the tent map?3.Consider the following 1D CA: A cell is black in next generation if and only if either of it neighbours, but not both, was black on the step before. What is the rule number? Do 5 iterations using one black cell as seed.4.Consider the rule B25/S4. B denotes birth and S survival. Game of Life is B3/S23. What is the rule number for B25/S4? Do 3 iterations for the first one. Note that we have up-down symmetry. It is called a replicator. Do one iteration for the second one. It is called a photon.5.Use the inclusion-exclusion (IE) method to calculate the number of integers between 1 and 60 that are coprime with 60. The primes 2, 3 and 5 are the prime factors in 60 since 60 = 22 · 3 · 5. The integers, i, that are coprime with 60 are not divisible with 2, 3 and 5 so GCD(i, 60) =1 for them. GCD stands for greatest common divisor. You can count them directly but here you have to use the IE-method.6.The girth of a graph G is the number of edges of the shortest cycle it is possible to find in G and it is denoted g (G). Let, from now on, the graphs G have e = v + 1 For such graphs with v ≥ 4 it is possible to show that The floor function [x] gives the largest integer ≤ x. a) Explain why in this type of graphs there must be at least two cycles. Draw a case where the cycles are edge disjoint for v = 7 and e = 8.b) If the two cycles are edge disjoint what is the maximum girth in a graph with e = v+ 1? c) Draw a graph with maximal girth for v = 7 and e = 8
7.What is the maximal number of edges in a planar graph when the regions have degree 3 or more? Use for example 2e = Σdeg(Ri) and Euler’s formula.b) Let G be a graph with 11 vertices and let G ̄ be its complement graph. G ̄ has the same 11 vertices but the edges from K11 that are not edges in G. Use the result in (a) above to show that not both G and G ̄ can be planar.8.Consider passwords with three symbols. Allowed symbols are the 26 letters in the English alphabet and the ten digits 0 to 9. We put the following restrictions on the passwords: i) There must be both letters and digits.ii) There must be both upper- and lower-case letters. So K8k and 4zL are examples of allowed passwords. How many such passwords can be constructed?9.Let X = {1, 2, 3, 4} and A = X × X. Define a relation R on A by (a, b)R(c, d) if and only if ab = cd. This relation, R, is an equivalence relation. Determine the equivalence classes.10.You have to buy 27 bagels. They are of four types: plain, onion, tomato and blueberry. The restrictions are: At least three of each sort. Not more than five with onions. In how many ways can you do this? (a) Solve the problem with inclusion-exclusion method. (b) Give the generating function for the problem.11.Consider all the 4-digit numbers from 1000 to 9999. (a) How many of them have a strictly increasing or decreasing sequence? Two examples are 3589 (strictly increasing) and 9760 (strictly decreasing). Strictly increasing means next digit to the right is greater than the previous one. Strictly decreasing means next digit to the right is smaller than the previous one.(b) How many of them have an increasing or decreasing sequence? Two examples are 3556 (increasing) and 6661 (decreasing). Increasing means next digit to the right is ≥ the previous one. Decreasing means next digit to the right is ≤ the previous one.12.The odd graph Ok, k is an integer ≥ 2, is defined in the following way: The vertices represent the subsets with k − 1 elements that can be obtained from a set with 2k −1 elements. Two vertices are joined with an edge if and only if the corresponding subsets are disjoint. O2 is a triangle so it is isomorphic to C3. (a) Draw O3
End of preview
Want to access all the pages? Upload your documents or become a member.