Reference no: EM131417221
1. Consider the following coin changing problem. You are given a value N and an infinite supply of coins with values d1, d2, . . . , dk. Give an O(Nk) algorithm for finding the smallest number of coins that add up to the value N.
2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. "ace?' is a subsequence of "abcdef." Consider the problem of finding the longest common subsequence of two sequences - this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct.
3. String C is considered to be an interleaving of strings A and B if it contains all (and only) the characters of both A and of B and their respective order is preserved in C. For example, C = aacabbaa is an interleaving of A = aaba and B = caba (demonstrated as follows: aacabbaa). Give an algorithm that, given strings A, B, and C, decides whether C is an interleaving of A and B in polynomial time. Prove your answer correct.
4. What would it mean to add memoization to Strassen's matrix multiplication algorithm?
What asymptotic improvement (if any) does it yield in the worst case? Explain your answer.
|
What confidence level would you assign to the procedure
: What confidence level would you assign to the procedure in your example; that is, what percentage of the time do you think it produces your desired result?
|
|
Is a confidence interval appropriate for given situation
: The university had information for all students showing that 3900 of the 5000 graduates were state residents. Is a confidence interval appropriate for this situation? If so, compute the appropriate interval. If not, explain why not.
|
|
Calculate the confidence interval
: Suppose that we collect data on "hours of sleep last night" from 64 students who are present at an 11:00 A.M. statistics class.- Calculate the confidence interval.
|
|
Discuss five factors that led to further westward expansion
: Before the American Revolution, England had prohibited colonists from migrating westward beyond the Appalachian Mountains. Explore this week's Webtext materials.Discuss five (5) factors that led to further westward expansion.
|
|
Algorithm for finding the smallest number of coins
: Consider the following coin changing problem. You are given a value N and an infinite supply of coins with values d1, d2, . . . , dk. Give an O(Nk) algorithm for finding the smallest number of coins that add up to the value N
|
|
What are hr laws that organization can use to develop policy
: What are some HR laws that organizations can use to develop and implement policies, procedures, and practices? Name and describe at least three laws that would drive policies, procedures, and practices.
|
|
What are the key points or facts presented in the article
: Why is the author writing about the subject? What is the thesis of the article? What are the key points/facts presented in the article? What are the conclusions and recommendations?
|
|
Top three internet issues of today
: Do research to identify the top three Internet issues of today. Write a paragraph on each issue and why it is considered significant.
|
|
Comment on the statisticians conclusion
: An environmental group is suing a manufacturer because chemicals dumped into a nearby river may be harming fish.- Comment on the statistician's conclusion.
|