Applied Algorithmics (COMP526)

Continuous Assessment - Winter 2017


PART1: Video presentation on algorihtms/research related material


Students will form (or will be allocated in) teams of 2 or 3 in the first few weeks of the term. Each team will be asked to bid for papers from the list of about 20 papers by providing the ranked list of 3-5 papers in order of preference. The papers will be allocated to teams on the first come (email received by the lecturer) first serve basis. The papers will be available towards the end of week 4 of the term from here. This will be followed by the bidding stage wrap it up with the final allocation done by the lecturer.

Students teams: here

While preparing your video presentation please make sure to address the following aspects:

Deadline: Tuesday May 2nd 2017 @ 12 noon

The presentation is expected to take about 15 minutes. You are allowed to use any video recording environment, however, we recommend to use OBS Studio which is a free software available on major (Windows, OS and Linux) platforms and it provides functionality meeting the requirements of this exercise. You can download the relevant installation pack from here.
Please make sure that you (1) provide the lecturer either with the link to your presentation stored in some repository, e.g., your Youtube channel, Vimeo account, Dropbox directory, or a web page; or (2) transfer the video from your memory stick, card, etc. Please make sure this is done by the deadline.

The top presentations will be made available (with the consent of the authors) via the COMP526 web pages.

[This assignment refers to learning outcomes 3 and 5, i.e., ability to understand and assimilate research literature as well as ability to communicate advances in the field of algorithms. This assessment contributes 0.4 of the total coursework mark, which translates to 10% of the total mark.]


PART2: Two programming assignments


All programming assignments have to be submitted via the departmental submission system. Please note that you can submit your work multiple times, subject to the relevant deadlines.



Programming assignment 1 (Bamboo Fence Trimming Problem, BFTP)

The first programming assignment refers to periodic use of queues, one of the basic types of data structures. In the Bamboo Fence Trimming Problem the gardener (represented by your program) has the goal of keeping the fence made of n bamboos B1,...,Bn as low as possible. Each bamboo Bi has its daily growth Hi which is a positive integer. We assume H1 < H2 < .. < Hn. The gardener is allowed to cut only one bamboo at the end of each day.

Your task is to create a periodic queue with the indices of bamboos that would tell the gardener which bamboos need to be cut every day indefinitely. Each day the daily height DH (the height of the currently tallest bamboo) of the fence is compared to the value H=H1+...+Hn (the lower bound on the daily height in the limit) in the form of a quotient DH/H. The maximum observed quotient will be returned as the quality factor of your solution. Please note that this factor is always greater or equal to 1 (where 1 is achievable for some distributions of H1 through Hn).


Example Consider BFTP with three bamboos with daily growth rates H1=2, H2=3, and H3=5.
One can consider a simple periodic queue PerQue =[1,2,3] which use would result in the following execution:

               2               3               5              PerQue =[1,2,3]    H=10  DH=5  DH/H=0.5
Day 1     Height of B1    Height of B2    Height of B3        Action cut B1 and put index 1 at the of PerQue

               2               6               10             PerQue =[2,3,1]    H=10  DH=10  DH/H=1
Day 2     Height of B1    Height of B2    Height of B3        Action cut B2 and put index 2 at the of PerQue

               4               3               15             PerQue =[3,1,2]    H=10  DH=15  DH/H=1.5
Day 3     Height of B1    Height of B2    Height of B3        Action cut B3 and put index 3 at the of PerQue

               6               6               5              PerQue =[1,2,3]    H=10  DH=6  DH/H=0.6
Day 4     Height of B1    Height of B2    Height of B3        Action cut B1 and put index 1 at the of PerQue

               2               9               10             PerQue =[2,3,1]    H=10  DH=10  DH/H=1.0
Day 5     Height of B1    Height of B2    Height of B3        Action cut B2 and put index 2 at the of PerQue

               4               3               15             PerQue =[3,1,2]    H=10  DH=15  DH/H=1.5
Day 6     Height of B1    Height of B2    Height of B3        Action cut B3 and put index 3 at the of PerQue

Day 6 looks like Day 3, and from now on each Day 3*i looks like Day 3, Day 3*i+1 looks like Day 4, and Day 3*i+2 like day 5

Conclusion: the maximum observed quotient DH/H=1.5 which is the returned quality factor of the solution.

Note, however, if we use a slightly redesigned queue Perque=[1,3,2,3] the returned quality factor will be 1.2 < 1.5.

  1. Task 1: Design the content of Perque with the goal of returning the quality factor as small as possible,
  2. Task 2: comment briefly (short paragraph on each data set) on the strategy behind your solution.
Your strategies will be executed with 3 different bamboo sets:
  1. Distribution 1: Hi=i, for i=1,2,3,4,5,6,7,8;
  2. Distribution 2: Hi=2^i, for i=1,2,3,4,5,6,7,8;
  3. Distribution 3: Hi=Pi, where Pi is the ith prime number, i.e., P1=2, P2=3, P3=5, etc, for i=1,2,3,4,5,6,7,8;
for which three separate codes for your use can be downloaded from
here.
Please note that depending on the type of the data used in each test you may have to use a different strategy to minimise the quality factor.

Deadline: Tuesday February 28th 2017 @ 12 noon

Marking scheme: 0% if any of the requested files is missing <50% a failed test but requested files are submitted, >50% files are executable, up to 35% for efficiency of your solution, and up to 15% for good explanation (separate text) -5% for each day of delay.



Programming assignment 2 (Encoding - Move-to-Front rank list)

The MTF transform rewrites long sequences built over arbitrary alphabets into sequences in which symbols drawn from the input alphabet are replaced by their dynamic ranks. For more information please consult the slides from week 6.

Assume you have an input alphabet A formed of 16 symbols stored in the list Q= and the original rank r() of the symbols reflect the order in the alphabet, i.e., r(a)=0, r(b)=1, r(c)=2, r(d)=3, r(e)=4,..., r(p)=15.

When the next symbol x from the input sequence is read its current rank r(x) in Qis stored in the output sequence, the ranks (of all symbols in Q) smaller than r(x) are increased by 1 and r(x)=0.

For example, if in the initial configuration the symbol read from the input sequence x=a, the rank 0 is stored and the ranks of the symbols do not change in Q;
and if x=d, the rank 3 is stored, r(d)=0, r(a)=1, r(b)=2, r(c)=3 and the remaining ranks remain unchanged in Q.

You are asked to:

  1. Task 2: write a fast (Java or Python) code that rewrites (with MTF method, only encoding part), symbol by symbol, sequences based on 16 symbols drawn from the alphabet A.
  2. Task 2: comment briefly in a separate document on the strategy behind your solution.

Deadline: Tuesday March 21st 2017 @ 12 noon

Marking scheme: 0% if any of the requested files is missing <50% a failed test but requested files are submitted, >50% files are executable, up to 35% for efficiency of your solution, and up to 15% for good explanation (separate text) -5% for each day of delay.



[The two programming assignment cover the learning outcome 4, i.e., the ability to undertake small software project with the algorithmic flavour. The marks for this assignment contribute 2 x 0.3 = 0.6 to the total coursework mark, which translates to 2 x 7.5% = 15% of the total mark.]