Applied Algorithmics (COMP526)

Continuous Assessment - Winter 2019

PART A: Video presentation on algorihtms/research related material

Students will be allocated to teams (of 3) in the first few weeks of the term. Teams will be bidding for topics from the proposed list by providing the ranked list of 3-5 topics in order of preference. The papers will be made avalialble on

=== Wednesday February 27 @ noon ===

and allocated to teams on the first come (email received by the lecturer) first serve basis. The list of topics will be available towards the end of week 4 of the term from here. This will be followed by the bidding stage wrapped 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:

Provide good introduction to and explanation of the studied problem/area [10%]
Discuss the research, political or commercial context of the studied problem/area [10%]
What is the main contribution including findings, problems solved and awaiting solution [30%]
Are there any algorithmic (if not explain the proper context) issues discussed directly or indirectly in the article [5%]
Follow up including reading further articles on this or related topics [10%]
Clarity of the presentation including: structure, good argument, visual and sound quality [25%]
Extra effort [10%]

Deadline: Monday May 13th 2019 @ 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) upload your video presentation to a platform/repository (e.g., Youtube, Dropbox, GoogleDrive, etc) from which I can access the presentation. Please create a short (preferably PDF) file which includes the title of the presentation, the names of the presenters and the link to the presentation, and submit this file via the regular submission site.

(2) If you have problems with adopting solution (1) please contact the lecturer asap (well before May 13th).

Please make sure the submission is done by !!! noon on Monday May 13th !!!

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.]

PART B: 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 GrowthRate[i] which is a positive integer. We assume GrowthRate[1] < GrowthRate[2] < .. < GrowthRate[n]. 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=GrowthRate[0]+...+GrowthRate[n-1] (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 GrowthRate[0] through GrowthRate[n-1]).

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

               2               3               5              PerQue =[0,1,2]    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 =[1,2,0]    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 =[2,0,1]    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 =[0,1,2]    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 =[1,2,0]    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 =[2,0,1]    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=[0,2,1,2] the returned quality factor will be 1.2 < 1.5.

Task 1: Design the content of Perque with the goal of returning the quality factor as small as possible,
Task 2: Comment briefly in separate document (with your name on and a short paragraph on each data set) on the strategy behind your solution.

Your strategies will be executed with 3 different bamboo sets:

Distribution 1: GrowthRate[0..7]= [3,3,3,5,5,7,7,9];
Distribution 2: GrowthRate[0..7]= [1,1,2,3,5,8,13,21];
Distribution 3: GrowthRate[0..7]= [3,6,12,24,48,96,192,384].

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.
Please make your submission through this link .

Deadline: Monday February 25th 2019 @ 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 (Shortest Common Superstring Problem) In the shortest common superstring problem (SCSP) one receives as the input a finite collection of words S[0],S[1]..,S[n-1] and the challenge is to find the shortest string Solution which contains all S[i], for all i=0,..,n-1, as substrings.

Example: Assume the input strings are S[0]=abaa, S[1]=baaa, and S[2]=aaaab.

A string aaaabaaa (of length 8) is a superstring of S[0], S[1], and S[2], however there is a shorter superstring abaaaab (of length 7) which is a better candidate for the shortest super string.

Below you will find java codes with three instances of shortest super string problem with the input sequences S[0], S[1],... In the first two instances the input strings are fixed, i.e., they are exactly the same during every execution of the software. In the third instance during every execution of the code the content of the input strings is drawn at random. Your tasks are

Task 1: compute the shortest you can manage supersting of S[0], S[1],.., S[19] on store it on variable Solution in this part of the code.

		// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		// YOU ARE ALLOWED TO INTRODUCE DEFINITIONS AND NEW METHODS ABOVE THIS LINE
		// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

		// Insert your solution below
		// In the current solution all strings from S[i] are simply concatenated.
		// Try to improve this solution. Go as close as possible with quality quotient to (or even below) 1

		Solution=S[1]+S[2]+..;

		// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		// DO NOT CHANGE ANYTHING BELOW THIS LINE
		// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Please note that this time you can (in fact in the third instance you have to) instert some java code in this fragment too.

IMPORTANT Do not change names (in your submission) of the files provided.

Task 2: Attach a PDF document with your name, a paragraph on each data set containing explanation of the strategy, the actual solution and its efficiency.

The three separate codes for your use can be downloaded from here.
Please note that depending on the content of the input strings you may have to use a different strategy to cut the length (reflected in the quality quotient) of your superstring.
Please make your submission through this link .

Deadline: Monday March 25th 2019 @ 12 noon

Marking scheme: 0% if any of the requested files is missing <40% a failed test but requested files are submitted, >40% files are executable, up to 35% for efficiency of (including lower/upper bound arguments supporting) your solution, up to 15% for the quality of the document, and 10% for an extra step. -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.]