Discrete Mathematics And Its Applications

8th Edition

ISBN: 9781260091991

Author: NA

Publisher: Mc graw hill

See similar textbooks

Videos

Textbook Question

Chapter 8, Problem 17SE

In Exercises 15-18 we develop a dynamic programming algorithm for finding a longest common subsequence of two sequences a 1 , a 2 , .... , a m and b 1 , b 2 , .... , b n , an important problem in the comparison of DNA of different organisms.

Use Exercise 16 to construct a dynamic programming algorithm for computing the length of a longest common subsequence of two sequences a 1 , a 2 , .... , a m and b 1 , b 2 , .... , b n , storing the values of L(I,J) as they are found.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 8, Problem 16SE

Chapter 8, Problem 18SE

Students have asked these similar questions

Problem 11 (a) A tank is discharging water through an orifice at a depth of T meter below the surface of the water whose area is A m². The following are the values of a for the corresponding values of A: A 1.257 1.390 x 1.50 1.65 1.520 1.650 1.809 1.962 2.123 2.295 2.462|2.650 1.80 1.95 2.10 2.25 2.40 2.55 2.70 2.85 Using the formula -3.0 (0.018)T = dx. calculate T, the time in seconds for the level of the water to drop from 3.0 m to 1.5 m above the orifice. (b) The velocity of a train which starts from rest is given by the fol- lowing table, the time being reckoned in minutes from the start and the speed in km/hour: | † (minutes) |2|4 6 8 10 12 14 16 18 20 v (km/hr) 16 28.8 40 46.4 51.2 32.0 17.6 8 3.2 0 Estimate approximately the total distance ran in 20 minutes.

- Let n = 7, let p = 23 and let S be the set of least positive residues mod p of the first (p − 1)/2 multiple of n, i.e. n mod p, 2n mod p, ..., p-1 2 -n mod p. Let T be the subset of S consisting of those residues which exceed p/2. Find the set T, and hence compute the Legendre symbol (7|23). 23 32 how come? The first 11 multiples of 7 reduced mod 23 are 7, 14, 21, 5, 12, 19, 3, 10, 17, 1, 8. The set T is the subset of these residues exceeding So T = {12, 14, 17, 19, 21}. By Gauss' lemma (Apostol Theorem 9.6), (7|23) = (−1)|T| = (−1)5 = −1.

Let n = 7, let p = 23 and let S be the set of least positive residues mod p of the first (p-1)/2 multiple of n, i.e. n mod p, 2n mod p, ..., 2 p-1 -n mod p. Let T be the subset of S consisting of those residues which exceed p/2. Find the set T, and hence compute the Legendre symbol (7|23). The first 11 multiples of 7 reduced mod 23 are 7, 14, 21, 5, 12, 19, 3, 10, 17, 1, 8. 23 The set T is the subset of these residues exceeding 2° So T = {12, 14, 17, 19, 21}. By Gauss' lemma (Apostol Theorem 9.6), (7|23) = (−1)|T| = (−1)5 = −1. how come?

Chapter 8 Solutions

Discrete Mathematics And Its Applications

Ch. 8.1 - Use mathematical induction to verify the formula...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - A vending machine dispensing books of stamps...Ch. 8.1 - A country uses as currency coins with values of 1...Ch. 8.1 - How many was are there to pay a bill of 17 pesos...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

Solution Summary: The author explains the dynamic programming algorithm for finding a longest common subsequence of two sequences using the values L(i,j) found by The algorithm in exercise 16.

Videos

Want to see the full answer?

Chapter 8 Solutions