Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Python Expert

Assignment: Introduction to Computer Science for Life Scientists

Exercise 1 (Dynamic Programming)

Searching for the longest common subsequence (LCS) of biosequences is one of the most important tasks in Bioinformatics. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example given a sequence S =\AGGTACCCGATC", all \AGT", \TAGAT", \GGG", and ... are subsequences of S.. In Bioinformatics the length of the longest commen subsequence between two biosequences is a good measure for the similarity of the two sequences.

a) Write a recursive function to and the LCS of two input string of size n and m. (3P)

b) For two sequences of size n, what is the running time complexity of your function in part a), where all possible subsequences are computed for both sequences? Brie y explain your answer. (2P)

c) This time use dynamic programming to nd the LCS of two input string of size n and m. (5P)

d) Write a python function that uses your idea in part c) to nd the LCS of two input strings S1 and S2. Test your function with the following sequences: (3P)

S1=\AGGTACCCGATC", S2=\GTAAGAGTACCGATTGATC"
S1=\AGATTCCCCACCTTAGA", S2=\AGGAATCCCCAACCTGA"

e) Briefly explain what is the running time complexity of LCS function in part d)? (2P)

Exercise 2 (Sorting)

a) Suggest an algorithm with O(n) average running time complexity to nd the ith smallest value in set S of size n. For example for S = f5; 3; 1; 7; 2; 3; 1g the third smallest element is 2. You are not allowed to use counting or radix sort. Hint: Think how you could make use of the idea of quick sort for searching. (5P)

b) Suggest an algorithm with O(nk) running time complexity to sort a list of n strings, where the strings may have di erent lengths with k being the length of the longest string. For example for [\b",\cda",\db",\da",\ab",\a"], the sorted list must be [\a",\ab",\b",\cda",\da",\db"]. (5P).

Python, Programming

  • Category:- Python
  • Reference No.:- M92556057
  • Price:- $30

Priced at Now at $30, Verified Solution

Have any Question?


Related Questions in Python

Sieve of eratosthenes in pythonthe goal is to find all the

Sieve of Eratosthenes (in Python) The goal is to find all the prime numbers less than or equal to some natural number maxn. We have a list that tells us if any of the numbers 0..maxn are "marked". It can be an array of b ...

The second task in this assignment is to create a python

The second task in this assignment is to create a Python program called pancakes.py that will determine the final order of a stack of pancakes after a series of flips.(PYTHON 3) Problem Task In this problem, your input w ...

A software company sells a package that retails for 99

A software company sells a package that retails for $99. Quantity discounts are given according to the following table: Quantity Discount 10 - 19 20% 20 - 49 30% 50 - 99 40% 100 or more 50% Write a program using python t ...

Question write a python program with a graphical user

Question: Write a python program with a graphical user interface that will allow a user to create a custom pizza which they wish to order. At minimum, the user should be able to choose the size of the pizza, the type of ...

Quesiton write a python script that counts occurrences of

Quesiton: Write a python script that counts occurrences of words in a file. • The script expects two command-line arguments: the name of an input file and a threshold (an integer). Here is an example of how to run the sc ...

Question write a simple python program that takes use

Question: Write a simple python program that takes use inputs as non-zero digits and converts them into binary form. The response must be typed, single spaced, must be in times new roman font (size 12) and must follow th ...

Question why is software configuration management

Question : Why is software configuration management considered an umbrella activity in software engineering? Please include examples and supporting discussion. The response must be typed, single spaced, must be in times ...

Tasksdemonstrate data scraping of a social network of

Tasks Demonstrate data scraping of a social network of choice. Develop technical documentation, including the development of the code & detailing the results. Provide a report on the findings, that includes research into ...

Simple python traffic lightswrite a program that simulates

Simple Python (Traffic lights) Write a program that simulates a traffic light. The program lets the user select one of three lights: red, yellow, or green. When a radio button is selected, the light is turned on, and onl ...

Homework -this homework will have both a short written and

Homework - This homework will have, both a short written and coding assignment. The problems that are supposed to be written are clearly marked. 1) (Written) Make heuristics Describe two heuristics for the slide problem ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As