[SOLVED] CPTS350-Homework 1

Description

1. In cpts317, we learned that a problem is a language. Such a statement builds a link from 317 to 350. For instance, consider the following problem:

Given: a graph G, Question: is G connected?

This problem corresponds to the language that puts all the string encodings of the positive instances of the problem into: {hGi : G is a connected graph}, where hGi is the string encoding of G. Please indicate the laguages corresponding to the following four problems:

Given: a number n and two primes p and q, Question: is it the case that n = p · q?

Given: a number n,

Question: is it the case that n = p · q for some primes q and q?

Given: an NFA A and a word w, Question: Does A accept w ?

Given: an NFA A,

Question: Is there a word w such that A accepts w?

2. Prove why the following statements are true:

(1). Function 2n³ − 18n is O(n³) and also it is O(n⁴) but is it not O(n² logn).

(2). Function 3n²2²ⁿ is 2^O(n).

3. (You MUST do this problem since your TA, very likely, may choose to grade this problem only. It is also good excercise to think through real world problems while learning algorithms.) In designing an algorithm for a real world complex problem, probably the most difficult part is to figure out (a) input to your algorithm including its data structure so that you may bring the input in your memory and feed it to your algorithm; (b) what the problem really is (without understanding the problem, you can’t even design an algorithm). In class, I went through a small example. Now, you are going to work on one more example and write an essay about it. First, stare at a protein 3D structure (which is one big molecule) shown in the following link for 5 minutes https://www.rcsb.org/3d-view/4hhb/1

You may move your mouse over the picture to see the forming atoms and bonds. Now, write to answer the following questions — herein, the final goal for you is to design an algorithm M to compute a similarity metric (which is a number and you define it!) between two protein molecules. A. Read from the Internet and write a not-so-short paragraph on why such an algorithm M (or related ideas) could help scientists to develop new medical drugs to fight with tough diseases in the future.

1. Since the input to your similarity algorithm M is of two protein molecules as shown in the link above, as computer scientists, we first need consider how to represent a protein molecule in computer memory; i.e., choosing a data structure for it. Of course, you have many ways to do it. For instance, we can represent it as a text string, as a graph, or even as a jpeg picture. You describe a way on how to represent a protein molecule.
2. You sketch two definitions of the similarity metric between two protein molecules and also describe the Pros and Cons of the two definitions. You also need sketch two algorithms (and intuitively analyze their efficiencies) M (over the data structure that you descibed in B above) for the two definitions, respectively.