Algorithms Final Exam Questions

Problems:


    1. (15 pts) Doctor Jean needs your help! She’s been relabeling her collection of chro-mosome sequences and has found three di erent 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" le located on Canvas to access the data. When back-tracing through the computed two dimensional matrix to nd the longest common


1





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) Show a table that maps the sequence to the species.

    (b) Submit your separate python (.py)  le along with your PDF submission.

Note: the data provided is mini ed data ( rst 50 lines of each sequence) from the National Center for Biotechnology Information. The data was originally in FASTA format but it was modi ed when removing the descriptions of sequences from the les. You can treat the le as a text le. Below are useful links for information relating to this question.

NCBI Genome Data: ftp://ftp.ncbi.nlm.nih.gov/genomes/

FASTA Format Speci cation: http://genetics.bwh.harvard.edu/pph/FASTA.html

    2. (15 pts) Draco Malfoy is struggling with the problem of making change for n cents using the smallest number of coins. 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 fdig, one for each coin type, such that Pri=1 di = k and where k is minimized.

        (a) A greedy algorithm for making change is the wizard’s algorithm, which all young wizards learn. Malfoy writes the following pseudocode on the whiteboard to illustrate it, where n is the amount of money to make change for and v is a vector of the coin denominations:

wizardChange(n,v,r) :

d[1 .. r] = 0 // initial histogram of coin types in solution while n > 0 {

k = 1

while ( k < r and v[k] > n ) { k++ } if k==r { return ’no solution’ } else { n = n - v[k] }

}

return d

Hermione snorts and says Malfoy’s code has bugs. Identify the bugs and explain why each would cause the algorithm to fail.

        (b) Sometimes the goblins at Gringotts Wizarding Bank run out of coins,1 and make change using whatever is left on hand. 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.

2





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) On the 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, i.e., denominations of c0; c1; : : : ; c‘ for some integers c > 1 and ‘ 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:  rst consider the special case of c = 2.

    3. In the two-player game \Pandas Peril", 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 largest. However, this is not always optimal, as the following example shows: (The rst player would win if she would rst pick the 4 instead of the 5.)

42105

        (a) (10 pts) Write a dynamic programming algorithm for a strategy to play Pandas Peril. Player 1 will use this strategy and Player 2 will use a greedy strategy of choosing the largest card.

        (b) (10 pts) Prove that your strategy will do no worse than the greedy strategy for maximizing the sum of each hand.

        (c) (10 pts) 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.

    4. A common problem in computer graphics is to approximate a complex shape with a bounding box. For a set, S, of n points in 2-dimensional space, the idea is to nd 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 e cient algorithm for constructing R is crucial.



3





        (a) (10 pts) Design a divide and conquer algorithm for constructing R in O(32n ) com-parisons.

        (b) (10 pts) Implement your algorithm in Python. 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 le with your algorithm.

    5. (10 pts) Professor Voldemort has designed an algorithm that can take any graph G with n vertices and determine in O(nk) time whether G contains a clique of size k. Has the Professor just shown that P = NP ? Why or why not?

    6. (10 points) Consider the special case of TSP where the vertices correspond to points in the plane, with the cost de ned for an edge for every pair (p, q) being the usual Euclidean distance between p and q. Prove that an optimal tour will not have any pair of crossing edges.




































4