Design algorithm that computes how many steps it will take

Assignment Help Data Structure & Algorithms
Reference no: EM131232199

Algorithm

Problem 2.17

There are n bacteria and 1 virus in a Petri dish. Within the first minute, the virus kills one bacterium and produces another copy of itself, and all of the remaining bacteria reproduce, making 2 viruses and 2 · (n - 1) bacteria. In the second minute, each of the viruses kills a bacterium and produces a new copy of itself (resulting in 4 viruses and 2(2(n - 1) - 2) = 4n - 8 bacteria; again, the remaining bacteria reproduce. This process continues every minute. Will the viruses eventually kill all the bacteria? If so, design an algorithm that computes how many steps it will take. How does the running time of your algorithm depend on n?

Problem 4.13

Given a long text string T, one shorter pattern string s, and an integer k, find the first occurrence in T of a string (if any) s such that dH(s, s ) ≤ k. What is the complexity of your algorithm?

Problem 4.14

Given a long text string T, one shorter pattern string s, and an integer k, find the first occurrence in T of a string (if any) s such that dH(s, s ) ≤ k. What is the complexity of your algorithm?.

All these qustion are from the book (Introduction to Bioinformatics Algorithms. Neil C. Jones and Pavel A. Pevzner, The MIT Press (ISBN: 0-262-10106-8)).

Reference no: EM131232199

Questions Cloud

Why ethics and confidentiality play an integral role : Differences between community setting and correctional setting case management, How the process will need to be altered for various special populations and Potential clients in need of case management at both settings.
Why has there been no movement to initiate such a proposal : An ongoing debate about the Superfund program is the determination of the optimal abatement level, characterized as the "how clean is clean" problem. Choose one of the risk management strategies, and propose how it might be used to resolve this is..
Why does riordan need a strategic plan : Address the following questions in your strategic plan: Why does Riordan need a strategic plan? What role should ethical and social responsibility considerations have in Riordan's strategic management plan
Determine the bit line voltages v1 and v2 : Determine the bit line voltages v1 and v2 after the cells are addressed for the case when (a) a logic 1 is stored and (b) a logic 0 is stored.
Design algorithm that computes how many steps it will take : Will the viruses eventually kill all the bacteria? If so, design an algorithm that computes how many steps it will take. How does the running time of your algorithm depend on n?
List the factors for rating the product quality : Create a rating tool for the product or service. List the factors for rating the product's quality and then rate your product or service from 1 to 10 (1 as the lowest, 10 the highest) for each factor
Create and describe a comprehensive security policy : Identify possible network infrastructure vulnerabilities. Address network vulnerabilities with the appropriate security measures. Ensure that consideration is given to virtualization and cloud technology.
Advantages and disadvantages of the swot analysis : Explain the purpose of a SWOT analysis. What are the alternatives? Discuss the advantages and disadvantages of the SWOT analysis
Discuss the likely impact on the health care industry : Analyze the two working models for understanding different health care systems and determine which model would be most useful to you in your current (or future) position in the health care industry. Provide specific examples to support your respon..

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Compute the subgame perfect nash equilibriua in given game

Compute the subgame perfect Nash equilibriua in the game below. Identify the path through the tree that each one represents, and the utilities of each player.

  Write an algorithm, using pseudo code, "consensus algorithm"

Write an algorithm, using pseudo code, "Word Search": Given a string of letters, identify all substrings that create one of five given words.

  Greedy strategy for finding a shortest path

Think about the given greedy strategy for finding a shortest path from vertex start to vertex goal in a connected graph.

  Draw the recursive process of quicksort

Draw the recursive process of Quicksort and Mergesort for sorting the sequence {5, 1, 2, 9, 7}. You will get a recursion tree for Quicksort and Mergesort respectively. What are their depths?

  Write a pseudocode for divide-and-conquer algorithm

Write a pseudocode for divide-and-conquer algorithm for finding the position of the largest element in an array of n numbers

  Find all the words hidden in the grid

Introduction A Word Search Puzzle consists of a grid of letters, with words hidden inside horizontally, vertically and diagonally. The player's task is to find all the words hidden in the grid.

  Create a detailed uml class diagram in astah

For each method that you identify, write the post-conditions and then write the associated unit tests. The post-conditions are to be written in the report. Ensure that they are clearly identified.

  Create a binary search tree program

Creating a Binary Search Tree program - Finding the largest and smallest values in the tree Add two class methods

  Design a program that asks user to enter a series of numbers

Design a program that asks the user to enter a series of 20 numbers. The program should store the numbers in an array and then display the following data.

  Design a relational database so that it is at least in 3nf

Design a relational database so that it is at least in 3NF

  Write algorithm to calculate the median using queries

Calculate the median using as few queries as possible. Provide an algorithm which determines the median value using at most O(lg n) queries.

  Draw a flowchart for the algorithm

Compute the final answer by rounding the last value to 4 decimal places type the computed value at the bottom of the list and Draw a flowchart for the algorithm below and have it checked by the TA

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