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