طراحي الگوريتم

---

شرح پروژه

1-You are given two sorted lists of size m and n. Give an O(logm + log n) time algorithm for computing the kth smallest element in the union of the two lists. -------------------------------------------------------------------------------------------------------- 2-The basic intuition behind Huffman's algorithm, that frequent blocks should have short encodings and infrequent blocks should have long encodings, is also at work in English, where typical words like I, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer. However, words like fire!, help!, and run! are short not because they are frequent, but perhaps because time is precious in situations where they are used. To make things theoretical, suppose we have a le composed of m different words, with frequencies f1; : : : ; fm. Suppose also that for the ith word, the cost per bit of encoding is ci. Thus, if we nd a prex-free code where the ith word has a codeword of length li, then the total cost of the encoding will be P i fi
ci
li. Show how to modify Huffman's algorithm to nd the prex-free encoding of minimum total cost. --------------------------------------------------------------------------------------------------------- 3-. Reconstructing evolutionary trees by maximum parsimony. Suppose we manage to sequence a particular gene across a whole bunch of different species. For concreteness, say there are n species, and the sequences are strings of length k over alphabet  = fA;C; G; Tg. How can we use this information to reconstruct the evolutionary history of these species? Evolutionary history is commonly represented by a tree whose leaves are the different species, whose root is their common ancestor, and whose internal branches represent speciation events (that is, moments when a new species broke off from an existing one). Thus we need to nd the following:  An evolutionary tree with the given species at the leaves.  For each internal node, a string of length k: the gene sequence for that particular ancestor. For each possible tree T, annotated with sequences s(u) 2 k at each of its nodes u, we can assign a score based on the principle of parsimony: fewer mutations are more likely. score(T) = Sigma (u;v)2E(T) (number of positions on which s(u) and s(v) disagree): Finding the highest-score tree is a difcult problem. Here we will consider just a small part of it: suppose we know the structure of the tree, and we want to ll in the sequences s(u) of the internal nodes u. Here's an example with k = 4 and n = 5: 0 / \ 0 0 / \ / \ 0 CGCG AGGA ATCA / \ ATTC AGTC (a) In this particular example, there are several maximum parsimony reconstructions of the internal node sequences. Find one of them. (b) Give an efcient (in terms of n and k) algorithm for this task. (Hint: Even though the sequences might be long, you can do just one position at a time.)

مهارت ها و تخصص های مورد نیاز

---

---