Final Exam Questions
She’s been relabeling her collection of chro- mosomesequences and has found three different sequences that were displaced from their original locations in the lab. She knows that two of the sequences represent two chromosomes from a human (Homo Sapiens) and the other sequence represents a chromosome from a soybean (Glycine Max).
Help Doctor Jean by parsing in the following sequences into memory (be careful of new- lines!) and applying the Longest Common Subsequence algorithm learned in recitation to each unique pair of sequences.
Unzip the ”sequence data.zip” file located on Canvas to access the data. When back- tracing through the computed two dimensional matrix to find the longest common
subsequence, break ties uniformly at random. Compare the results from your imple- mentation to determine which species the sequences pertain to (try to come up with a sensible metric that will compare the results).
(a)Showa table that maps the sequence to the species.
(b)Submit your separate python (.py) file along with your PDF
Note: the data provided is minified data (first 50 lines of each sequence) from the National Center for Biotechnology Information. The data was originally in FASTA format but it was modified when removing the descriptions of sequences from the files. You can treat the file as a text file. Below are useful links for information relating to this question.
with the problem of making change for n cents usingthe smallest number of Malfoy has coin values of v1 < v2 < · · · < vr for r coins types, where each coin’s value vi is a positive integer. His goal is to obtain a set
of counts {di}, one for each coin type, such that Σr di = k and where k is minimized.
(a)A greedy algorithm for making change is the wizard’s algorithm, which all youngwizards Malfoy writes the following pseudocode on the whiteboard to illustrate it,Algorithms代写
Hermione snorts and says Malfoy’s code has bugs. Identify the bugs and explain why each would cause the algorithm to fail.Algorithms代写
(b)Sometimesthegoblins at Gringotts Wizarding Bank run out of coins,1 and make change using whatever is left on Identify a set of U.S. coin denominations
1It’s a little known secret, but goblins like to eat the coins. It isn’t pretty for the coins, in the end.
for which the greedy algorithm does not yield an optimal solution. Justify your answer in terms of optimal substructure and the greedy-choice property. (The set should include a penny so that there is a solution for every value of n.)
(c)Onthe advice of computer scientists, Gringotts has announced that they will be changing all wizard coin denominations into a new set of coins denominated in powers of c, e., denominations of c0, c1, . . . , cA for some integers c > 1 and A 1. (This will be done by a spell that will magically transmute old coins into new coins, before your very eyes.) Prove that the wizard’s algorithm will always yield an optimal solution in this case.
Hint: first consider the special case of c = 2.
an even number of cards are laid out in a row, face up. On each card, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. One strategy is to use a greedy approach and simply pick the card at the end that is the However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 4 instead of the 5.)
4 2 10 5
(a)(10 pts) Write a dynamic programming algorithm for a strategy to playPandas Peril. Player 1 will use this strategy and Player 2 will use a greedy strategy of choosing the largest
(b)(10 pts) Prove that your strategy will do no worse than the greedy strategy for maximizing the sum of each
(c)(10pts) Implement your strategy and the greedy strategy in Python and simulate a game, or two, of Pandas Peril. Your simulation should include a randomly generated collection of cards and show the sum of cards in each hand at the end of the game.
is to approximate a complex shape with a bounding For a set, S, of n points in 2-dimensional space, the idea is to find the smallest rectangle, R. with sides parallel to the coordinate axes that contains all the points in S. Once S is approximated by such a bounding box, computations involving S can be sped up. But, the savings is wasted if considerable time is spent constructing R, therefore, having an efficient algorithm for constructing R is crucial.
(a)(10pts) Design a divide and conquer algorithm for constructing R in O( 3n) com-parisons.Algorithms代写
(b)(10pts) Implement your algorithm in Generate 50 points randomly and show that your bounding box algorithm correctly bounds all points generated. Your code should output the list of points, as well as the coordinates of R. You should include an explanation of the results in your pdf file with your algorithm.