### Module Details

 The information contained in this module specification was correct at the time of publication but may be subject to change, either during the session because of unforeseen circumstances, or following review of the module at the end of the session. Queries about the module should be directed to the member of staff with responsibility for the module.
 Title ADVANCED ALGORITHMIC TECHNIQUES Code COMP523 Coordinator Prof DR Kowalski Computer Science D.Kowalski@liverpool.ac.uk Year CATS Level Semester CATS Value Session 2017-18 Level 7 FHEQ First Semester 15

### Aims

• To provide a sound foundation concerning the design and analysis of advanaced discrete algorithms.

• To provide a critical rational concerning advanced complexity theory and algorithmics.
• To provide an in-depth, systematic and critical understanding of selected significant issues at the forefront of research explorations in the design and analysis of discrete algorithms.

• ### Learning Outcomes

Describe the following classes of algorithms and design principles associated with them: recursive algorithms, graph (search-based) algorithms, greedy algorithms, algorithms based on dynamic programming, network flow (optimisation) algorithms, approximation algorithms, randomised algorithms, distributed and parallel algorithms.

Illustrate the above mentioned classes by examples from classical algorithmic areas, current research and applications.

Identify which of the studied design principles are used in a given algorithm taking account of the similarities and differences between the principles.

Apply the studied design principles to produce efficient algorithmic solutions to a given problem taking account of the strengths and weaknesses of the applicable principles.

Outline methods of analysing correctness and asymptotic performance of the studied classes of algorithms, and apply them to analyse correctness and asymptotic performance of a given algorithm.

### Syllabus

• Core algorithmic primitives including: notation, standard (sequential) models of computation, algorithmic design methods, data structures, formal proofs and methods of analysis on the example of recent (up to date) research problems. [2 weeks]
• Advanced particular graph algorithms, string algorithms, randomised algorithms, approximation algorithms, on-line algorithms. [5 weeks]
• Crucial elements of probabilistic theory. [1 week]
• Non-standard computational models including: parallel, distributed, non-deterministic (incl. probabilistic), biologically motivated, and appropriate diverse measures of complexity. [2 weeks]

Lecture -

Tutorial -

### Teaching Schedule

 Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL Study Hours 30 10 40 Timetable (if known) Private Study 110 TOTAL HOURS 150

### Assessment

EXAM Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
Unseen Written Exam  150  Semester 1  75  Yes  Standard UoL penalty applies  Final Exam Notes (applying to all assessments) 2 Assessment Tasks This work is not marked anonymously. Re-sit arrangements: Each re-sit assessment task will be different from the original assessment, except in the case of a skills-based assessment task, but the type of assessment will be the same; the deadline for the submission of work for each re-sit assessment task will be set by the module co-ordinator and will be part of the description of the assessment task; the deadline will typically fall within the re-sit period; the description of a re-sit assessment task will be provided at least four weeks before the deadline for the submission of work for the the task. Written examination
CONTINUOUS Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
Coursework  36 hours expected fo  Semester 1  12.5  Yes  Standard UoL penalty applies  Assessment 1
Coursework  36 hours expected fo  Semester 1  12.5  Yes  Standard UoL penalty applies  Assessment 2