Applied Algorithmics (COMP526)

Small software projects in relation to the studied material

Assignment 1 (Properties of Trees and Heaps)

The programming exercise focuses on good understanding of rooted trees and the two properties of Heaps. The global property refers to the fact that the values stored in the priority queue form an almost complete binary tree. The local property says that the value stored in a parent is not larger than the values stored in its children. More information on priority queues and Heaps can be found on pages 38-48 inweek 2 handouts.

For the purpose of this assignment we adopt the array representation of a Heap H, in which n values of H are stored in an array H[0..k-1], for some (possibly large) integer k>n. Please note that since the index in H starts from 0, the value stored in the root of H is located at H[0], and the children of a parent with the value located at H[i-1] have their values stored at locations H[2i-1] and H[2i], for any i>0.

We assume that all valid values in H are positive, and -1 stands for the null value. For example, array H[0..14] containing values 3,5,4,8,6,11,7,9,10,-1,-1,-1,-1,-1,-1 represents a Heap with n=9 values:

Example 1

            3
        /       \
       5         4
     /  \       /  \  
    8    6     11   7
   / \  / \   / \   / \
  9 10 -1 -1 -1 -1 -1 -1

Given k,n and H[0..k-1] as the input you are asked to perform the following 3 tasks:

Task 1: verify whether H represents a Heap with n values, and if it does not return value -1, otherwise
Task 2: return the hight of the subtree rooted in the third smallest value in the Heap.
Task 3: Comment briefly on the time complexity of your solution to Task 2.

In Example 1 the Heap structure is correct and the hight of the subtree rooted in the third smallest value (5) is 2.

Deadline: Friday, February 24th, 2011, 4PM (noon)

Marking scheme: <60% a failed test, all tests passed 60%< .. <90% (depending on the speed of your and other solutions to Task 2), extra up to 10% for the note on the time complexity of the solution to Task 2, -5% for each day of delay.

[This assessment covers learning outcomes 4, i.e., ability to undertake small software project with the algorithmic flavour. This assessment contributes 1/4 of the total coursework mark, which translates to 6.25% of the total mark]

Assignment 2 (Frequency of Fibonacci Subwords)

Recall that Fibbonacci words are defined recursively as: w(0)=a, w(1)=b, and w(i)=w(i-1)w(i-2), for any integer i>1. The input to your procedure is formed of a Fibonacci word w(n), where the index n is known in advance. Let S(k,n) be the set of all distinct subwords of w(n) of a fixed length k, where k is also known. The frequency of a subword s from S(k,n) refers to the total number of full occurrences of s in w(n).

Task 1: Given positive integers n<30 and k<4, find the frequency of the most frequent subword in S(k,n). Important In your algorithmic solution tabling precomputed values is not allowed!
Task 2: Comment briefly on the time complexity of your solution to Task 1. For the answer use either a plain ASCII file, MS Word or PDF document.

Example 2 Assume that the input is formed of n=5 and k=2. We are asked to find the frequency of the most frequent subword in S(2,5) where w(5)=babbabab. There are 3 distinct subwords in S(2,5). Namely: ba, ab and bb, with the respective frequencies 3,3,1. Thus the answer in this case is 3.

Deadline: Friday, March 9th, 2012, 4PM

IMPORTANT Submitted work must contain 3 components: (1) *.java file, (2) *.jar file and (3) text/pdf/msword file with explanation of the time complexity of the adopted solution. Work submitted without ANY of these integral comonents will not be assessed and marked nill (0).

Assignment 3 (Burrows-Wheeler Transform)

Consider an infinite language L that contains certain finite words based on characters drawn from a binary alphabet {a,b}. All words in L are formed of an arbitrary number k>0, i.e., k=1,2,3,4..., of pairs bb followed by non-empty and non-decreasing in size runs of symbol a. For example bba, bbabbaa, bbaabbaa, bbaabbaaaabbaaaa, belong to L but abb, bb, bbaabb, bbaaaabba do not belong to L.

Assume that a word w belongs to L and |w|=n. Consider also another word u which refers to the result of the Burrows-Wheeler Transform applied to w, i.e., u=BWT(w). Let #a1(w), #a2(w) stand for the lengths of the longest run and the second longest run respectively of as in w, where #a1(w)>0 , #a1(w) = #a2(w) when the two longest (rightmost) runns are the same, and #a2(w)=0 if there is only one run of as in w.

The input to our problem is formed of the known content of u and its length n.

Task 1: decide whether |#a1(w) - #a2(w)|> 1, and if yes set a variable s to 1, otherwise set s to -1
Task 2: compute the number k of pairs of bs residing in w,
Task 3: return (s * k)
Task 4: Comment briefly on the time complexity of your solutions to Task 1 and Task 2. For the answer use either a plain ASCII file, MS Word or PDF document.

Example 3
The input word u=bbaaabbaa corresponds to the original word w=bbaabbaaa, where u=BWT(w).
In this case #a1(w)=3,#a2(w)|=2, i.e., |#a1(w) - #a2(w)|= 1 and s=-1.
And since there are 2 pairs of bs in w your procedure should return -2.

If, however, the input word u=bababbaa corresponds to the original word w=bbabbaaa, where u=BWT(w).
In this case #a1(w)=3,#a2(w)|=1, i.e., |#a1(w) - #a2(w)|> 1 and s=1.
And since there are 2 pairs of bs in w your procedure should return 2.

Deadline: Friday, March 23rd, 2012, 4PM

Assessment 4 (Error correcting codes)

A code C used for transmission of long messages across a (noisy) communication channel is formed of distinct binary sequences of fixed length 8 built over alphabet A={a,b}. The length of each message M[0..n-1] communicated over the channel is a multiple of 8. The content of the code C is not known in advance, however, we know that all code words from C must occur in the first half of the file. We also assume that the communication channel is entirely reliable during transmission of the first half of the message. And only then it breaks occasionally flipping either a=>b or b=>a, but not more frequently than one character in any consecutive 8 characters. In other words, only one character can be flipped in each occurence of a code word.

Note that if during transmission a single character is flipped in a codeword c the resulting word c' is at distance 1 from c. Furthermore, if c' is at distance at least 2 from any other code word in the code (as it happens, e.g., in 1-error correcting codes), c' can be safely corrected to c. Otherwise, correction is not feasible.

Task: For a long message M[0..n-1] transmitted across the communication channel compute the exact number of occurences of code words that can be safely corrected.

Deadline: Friday, April 27th, 2012, 4PM

IMPORTANT Submitted work must contain 3 components: (1) *.java file, (2) *.jar file and (3) text/pdf/msword file with the clear explanation of the time complexity of the adopted solution. Work submitted without ANY of these integral comonents will not be assessed and marked nill (0).

Marking scheme: 0% if any of the requested files is missing <60% a failed test but requested files are submited, >60% all tests passed + all files submitted (about 80% for a quadratic solution), ..., and 100% fast (linear) solution all ccompanied by requested files, -5% for each day of delay.

Further instructions

The students are expected to submit (via the departmental submission system), consult for further detail SUBMISSION INSTRUCTIONS their executable JAVA software (*.class or *.jar), the source code (*.java) and a short document (plain text or pdf) with a short description of the adopted solution including discussion on the time complexity. The electronic version of the software will be kept by the lecturer until the end of the semester for future reference.