Algorithm Assignment - Knapsack, LCS, Spellchecker, Huffman Coding

Knapsack Problem

You are encouraged to work in groups (but not more than 2 persons in a group).Show all your computation to get full credit. Please put comments in your code. I will deduct points for uncommented codes. This assignment is for 200 points; double that of assignment 1. Knapsack Problem (60)

1. Consider a collection of K items out of which n items cannot be subdivided (0-1 knapsack) and m items can be divided into fractions (fractional knapsack), K = n + m. For each item, we are given the weight in pounds and the total cost. Given a maximum weight limit V , design an algorithm that selects the set of elements that will give the maximum value. Note that the problem is a combination of 0-1 and fractional knapsack problem.

(a) Give the pseudocode of your algorithm.

(b) Show how the algorithm works, step by step, for the given example in Table 1. The maximum weight, V, is 10 pounds. W (whole) indicates for the items that cannot be subdivided and F(fractional) stands for items whose fractional value can be taken.

(c) Prove the correctness of your algorithm.

(d) Compute the complexity of your algorithm.

(e) Let the weight of all the items be W and the cost of all the items be C. Let n=m=K/2. Let the limit of the weight be V = K/2W. Prove that in this case, taking any subset of half the items will provide the maximum value.

2. Longest Common Subsequence 

(a) Submit a clear and well commented code. We will test your code on some other sequences

(b) Find the LCS for each sequence to every other sequence

(c) Based on the length of the LCS to create groups of organisms, where organisms in the same group will have longer LCS. Describe clearly the algorithm/software that you used to compute the groups. Show the groups.

(d) Go to this website ” https://www.ebi.ac.uk/Tools/msa/clustalo/”. Under the space for enter your input sequence cut and paste the entire files. Then press submit. Once the processing is done, click on phylogenetic tree. The tree also groups the organisms. Compare this grouping with the one you obtained.

3. Spellchecker

Consider an editor that compares a typed in word say of length n and changes it to the nearest word in the dictionary, which can be of size m. For example, if you mistyped ”floyre”, it can change the word to ”flower” or ”flow” or ”floe” or ”floor”. To judge the best word, the spell checker computes the minimum number of changes between the typed word and the words in its dictionary. The changes can be as follows; (i) inserting a character, (ii) deleting a character or (iii) changing a character. All the change operations have equal weightage. 

(a) Describe an algorithm to find the minimum number of changes between two given words. This is a well known problem in dynamic programming, so you can take help of other resources. Just explain the process in your own words

(b) Using this method show step by step how to determine to which word ”sdimnas” should be changed. The candidates are (i)dynast, (ii) summer, (iii)dismal, (iv)dimmer, (v)sadden.

(c) Suggest two other criteria to select the most appropriate word, excluding the minimum number of changes. Gives reasons for why you selected the criteria 

4. Huffman Coding

The Latin alphabet is used in many European languages such as English, Spanish, French, German, etc. Show that the Huffman coding depends on the language used as well as the content. To do so apply Huffman coding on texts from different languages and different subjects, as follows; Compress, using Huffman coding, the first 2000 words from Chapter 1 of the following novels in their original language; (Moby Dick; Don Quixote, Three Musketeers).

Translate the exact 2000 words into English, Spanish and French (whichever of the two is not the original language), using an online translator. Compress these using Huffman coidn as well 

Create a histogram comparing of the lenght of the code per letter for (i) the three novels in the same languages and (ii) the same novel in different languages. Discuss your results (10+10)