What is the solution of recurrence relation

Assignment Help Engineering Mathematics
Reference no: EM131012897

Assignment

1. A nuclear reactor has created 18 grams of a particular radioactive isotope. Every hour 1% of this radioactive isotope decays.

a) Set up a recurrence relation for the amount of this isotope left n hours after its creation.

b) What are the initial conditions for the recurrence rela-tion in part (a)?

c) Solve this recurrence relation.

2. Suppose that every hour there are two new bacteria in a colony for each bacterium that was present the previous hour, and that all bacteria 2 hours old die. The colony starts with 100 new bacteria.

a) Set up a recurrence relation for the number of bacteria present after n hours.

b) What is the solution of this recurrence relation?

c) When will the colony contain more than 1 million bac-teria?

3. A small post office has only 4-cent stamps, 6-cent stamps, and 10-cent stamps. Find a recurrence relation for the number of ways to form postage of n cents with these stamps if the order that the stamps are used mat¬ters. What are the initial conditions for this recurrence relation?

4. Find the solutions of the simultaneous system of recurrence relations

an = an-1 + bn-1

bn = an-1 - bn-1

with a0 = 1 and b0 = 2.

5. Let L(i, j) denote the length of a longest common subsequence of a1, a2,....... ai and b1, b2,......bj, where 0 ≤ i ≤ m and 0 ≤ j ≤ n. Use parts (a) and (b) of Exercise 15 to show that L(i, j) satisfies the recurrence relation L(i, j) = L(i -1, j - 1) + 1 if both i and j are nonzero and ai = b1, and L(i, j) = max(L,(i, j - 1), L(i - 1, j)) if both i and j are nonzero and ai ≠ bi, and the initial condition L(i, j) = 0 if i = 0 or j = 0.

6. Develop an algorithm for finding a longest common subsequence of two sequences a1, a2,....... , am and b1, b2,...... bn, using the values L(i, j) found by the algorithm in Exercise 17.

In Exercises find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices.

1766_Pendant vertices.jpg

7. Find the sum of the degrees of the vertices of each graph in Exercises 1-3 and verify that it equals twice the number of edges in the graph.

In Exercises determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the given directed multigraph.

1457_Pendant vertices1.jpg

8. What does the degree of a vertex in the Hollywood graph represent? What does the neighborhood of a vertex repre¬sent? What do the isolated and pendant vertices represent?

9. Draw these graphs.

a) K1,8

b) C7

c) W7

10. How many subgraphs with at least one vertex does K2 have?

11. How many subgraphs with at least one vertex does W3 have?

12. If G is a simple graph with 15 edges and G- has 13 edges, how many vertices does G have?

In Exercises determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism or provide a rigorous argument that none exists.

2474_Graphs2.jpg

14. How many nonisomorphic simple graphs are there with n vertices, when n is

a) 2? b) 3? c) 4?

15. How many nonisomorphic simple graphs are there with six vertices and four edges?

In Exercises determine whether the given pair of di-rected graphs are isomorphic.

1593_Graphs.jpg

17. How many nonisomorphic directed simple graphs are there with n vertices, when n is

a) 2? b) 3? c) 4?

18. Does each of these lists of vertices form a path in the following graph? Which paths are simple? Which are suits? What What are the lengths of those that are paths?

a) a, b, e, c, b      b) a, d, a, d, a

c) a, d, b, e,a      d) a, b, e,c, b, d, a

587_Graphs1.jpg

19. In Exercises determine whether the given graph is connected.

738_graph3.jpg

20. How many connected components does each of the graphs in Exercises 3-5 have? For each graph find each of its connected components.

21. Determine whether each of these graphs is strongly con-nected and if not, whether it is weakly connected.

2400_graph4.jpg

22. Find the number of paths of length n between any two ad-jacent vertices in K3,3 for the values of n in Exercise.

Exercise- Find the number of paths of length n between two different vertices in K4 if n is

a) 2. b) 3. c) 4. d) 5.

23. In Exercises determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists.

1940_graph5.jpg

24. Can someone cross all the bridges shown in this map ex-actly once and return to the starting point?

1044_graph6.jpg

25. For which values of n do these graphs have an Euler circuit?

a) Kn b) Cn c) Wn d) Qn

26. In Exercises determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

1417_graph7.jpg

Reference no: EM131012897

Questions Cloud

Identify important legal issues that casemanagers must aware : Identify important legal issues that casemanagers must be aware of when supervising cases and providing services to a client
Real gas have finite volumes : T/F: The molecules in a real gas have finite volumes and do exert forces on each other, thus real gases do not conform to some of the assumptions of an ideal gas as stated by thekinetic molecular theory.
Construct and properly label the beam shear : Include the weight of the beam in ALL considerations (Hint: the above beam designation specifies the distributed weight of the beam as 130 lbf/ft of length) Construct and properly label the beam shear and moment diagrams. Be certain to Indicate all..
Calculate the directional derivative of f at the given point : Calculate the directional derivative of f at the point (3.0) in the direction (2, -3). What is the maximum directional derivative of f and in what direction does this occur?
What is the solution of recurrence relation : Set up a recurrence relation for the number of bacteria present after n hours - What is the solution of this recurrence relation?
Define the contemporary level of democratic institutionalism : Is it a logical outcome of the evolution of the U.S. constitutionalism or, rather, its unintended by-product?
Philosophical themes of the us constitution : Prepare a 2-3 page paper comparing three similar provisions in the U.S. Constitution and the Articles of Confederation. Outline the major philosophical themes of the U.S. Constitution and the Articles of Confederation
What is the position of the ball when it lands : What is the position of the ball when it lands? How far is the ball from the origin? (This is a distance, use proper units of measurement) At what speed is the ball moving when it impacts the ground?
What are the monthly payments : What are the monthly payments? How much principal is repaid in the first 6 months?

Reviews

Write a Review

 

Engineering Mathematics Questions & Answers

  What is the distribution of the time till the next epoch

What is the distribution of the time till the next epoch of N2(t) and what is the probability that the next epoch of N (t) is an epoch in N1(t)?

  Find the standard deviation in the given problem

Find the standard deviation. Using the information in the table on home sale prices in the city of Orlando for the month June, find the mean for the grouped data.

  Structure of equilibrium as a function

Sketch a phase diagram corresponding to each of these cases. Try to make some general statements about the structure of equilibrium as a function of the parameters.

  Determine the airspeed of an airplane

A Pitot tube (Figure) is used to determine the airspeed of an airplane. It consists of an outer tube with a number of small holes B (four are shown) that allow air into the tube; that tube is connected to one arm of a U-tube.

  Mcdonald and thomas advertising agency

McDonald and Thomas Advertising Agency has been hired to put together an advertising plan for the Healthy Heart Charity Banquet. The advertising media under consideration are listed in the table below:

  Obtain the laplace transform of the given function

Solve the following differential equations where the input is f(t) = 5t and the initial conditions are zero. Plot the response of the following models for 0 ≤ t ≤ 1.5. Obtain the Laplace transform of the following function

  Improper integral to evaluate the integral

Problem 1: Use the definition of an improper integral to evaluate the integral below:

  Maximum permitted rate of water flow

Water is to be transported through a network of pipelines from the big dam to the low valley for irrigation. A network is shown where arcs represent pipelines and the number on each arc represents the maximum permitted rate of water flow in cubic-..

  Programming formulation that minimizes average travel time

Write a programming formulation that minimizes the average travel time for each person - Determine the best model type(s) for each(linear, nonlinear, or integer), and then building the model(s) to meet the needs of the scenarios.

  Draw the corresponding transition diagram

Draw the corresponding transition diagram (digraph). Provide 5 strings that are in the language generated by the automaton.

  Providing unlimited free telephone technical support

Many software companies, after years of providing unlimited free telephone technical support for their products, began to charge for these services (typically after an initial start-up period of 90 days). Most companies offer two pricing plans.

  Write complete addition and multiplication tables for field

You should give sufficient detail for the arithmetic operations to be carried out but you do not need to write down the complete addition and multiplication tables for the field.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd