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]


    Teaching and Learning Strategies

    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 

    Recommended Texts

    Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.
    Explanation of Reading List: