# 作业Homework | Python | 代写Algorithm – Algorithms Final Exam Questions

#### CSCI3104: Algorithms Final Exam Questions

• You should not ask about the exam during the office hours or post any question about it on Piazza. However, classes on Wednesday, November 28 and Wednesday, December 5 will be reserved for questions about the exam.
• All work on this exam needs to be independent. You may consult the textbook, the lecture notes and homework sets, but you should not use any other resources. If we suspect that you collaborated with anyone in the class or on the Internet, we will enforce the honor code policy strictly. If there is a reasonable doubt about an honor code violation, you will fail this course.

Problems:

1. (15 pts) Doctor Jean needs your help! Shes been relabeling her collection of chro- mosome sequences 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 sequencedata.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) Show a table that maps the sequence to the species.
(b) Submit your separate python (.py) file along with your PDF submission.
``````
``````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.
NCBI Genome Data: ftp://ftp.ncbi.nlm.nih.gov/genomes/
FASTA Format Specification: http://genetics.bwh.harvard.edu/pph/FASTA.html
``````
1. (15 pts) Draco Malfoy is struggling with the problem of making change forncents using the smallest number of coins. Malfoy has coin values ofv 1 < v 2 << vrforr coins types, where each coins valueviis a positive integer. His goal is to obtain a set of counts{di}, one for each coin type, such that
``````r
i=1di=kand wherekis minimized.
(a) A greedy algorithm for making change is thewizards algorithm, which all
young wizards learn. Malfoy writes the following pseudocode on the whiteboard
to illustrate it, wherenis the amount of money to make change for andvis 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 Malfoys 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
``````

(^1) Its a little known secret, but goblins like toeatthe coins. It isnt 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 ofn.)
(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 ofc, i.e., denominations ofc^0 , c^1 ,... , c`for some integersc >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 wizards algorithm will always yield
an optimal solution in this case.
Hint: first consider the special case ofc= 2.
``````
1. 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 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 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.
``````
1. A common problem in computer graphics is to approximate a complex shape with a bounding box. For a set,S, ofnpoints 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 inS. OnceSis approximated by such a bounding box, computations involving Scan be sped up. But, the savings is wasted if considerable time is spent constructing R, therefore, having an efficient algorithm for constructingRis crucial.
``````(a) (10 pts) Design a divide and conquer algorithm for constructingRin O(^32 n) 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 ofR. You
should include an explanation of the results in your pdf file with your algorithm.
``````
1. (10 pts) Professor Voldemort has designed an algorithm that can take any graphG withnvertices and determine inO(nk) time whetherGcontains a clique of sizek. Has the Professor just shown thatP=N P? Why or why not?
2. (10 points) Consider the special case of TSP where the vertices correspond to points in the plane, with the cost defined 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.