### 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 COMPLEXITY OF ALGORITHMS Code COMP202 Coordinator Prof PJ Krysta Computer Science P.Krysta@liverpool.ac.uk Year CATS Level Semester CATS Value Session 2017-18 Level 5 FHEQ Second Semester 15

### Aims

• To demonstrate how the study of algorithmics has been applied in a number of different domains.
• To introduce formal concepts of measures of complexity and algorithms analysis.
• To introduce fundamental methods in data structures and algorithms design.
• To make students aware of computationally hard problems and possible ways of coping with them.

### Learning Outcomes

At the conclusion of the module students should have an appreciation of the diversity of computational fields to which algorithmics has made significant contributions.

At the conclusion of the module students should  have fluency in using basic data structures (queues, stacks, trees, graphs, etc) in conjunction with classical algorithmic problems (searching, sorting, graph algorithms, security issues) and be aware of basic number theory applications, etc.

At the conclusion of the module students should  be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness.

1

## A) Efficiency of Algorithms and Complexity Measures

1. Examples of algorithmic problems and introduction of complexity measures in terms of various resources (time, space, power consumption, number of exchanged messages, etc).  (1 lecture)
2.  Asymptotic complexity and notation in conjunction with a discussion on the worst-case versus the average-case complexity. Also recurrence equations and master method. (2 lectures).

B)   Algorithms and Data Structures

1.  Introduction and analysis of basic data structures with their efficient implementation, including: stack (array), queue (cyclic buffer), and priority queue (heap). (3 lectures)
2. Rooted trees - efficient data structu res with implementation, from: tree traversal, binary search trees, balanced trees – AVL and 2-3 trees, Graphs and their implementations. (4 lectures)
3. Advanced graph algorithms, including: network flow algorithms and bipartite matchings. (5 lectures)
4.  Elementary number theory, Euclid’s GCD algorithm, cryptography (from: symmetric encryption, public-key cryptosystem, RSA). (4 lectures)
5. Greedy algorithms and divide-and-conquer algorithms, dynamic programming (8 lectures)
6. Text processing, including pattern matching (from: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp), longest common subsequence (dynamic programming). (3 lectures)

C)   Computational Intractability and NP-Completeness

1.   Introduction:  Comparison of two ‘similar’ problems (Euler and Hamiltoni an cycle);  other example problems:  3-Colouring, Satisfiability, k-Clique, etc;  Common features of the problems. (1 lecture)
2.  TheComplexity Class NP:  formulation of computational problems in terms of questions about witnesses to solutions; completeness; background to Cook’s Theorem and its significance, intuitions behind Cook’s Theorem (2 lectures)
3. Selected standard reductions:  SAT to 3-SAT, SAT to Clique (1 lecture)

### Teaching and Learning Strategies

Lecture -

3 per week for 1 semester

Laboratory Work -

### Teaching Schedule

 Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL Study Hours 36 12 48 Timetable (if known) 3 per week for 1 semester Private Study 102 TOTAL HOURS 150

### Assessment

EXAM Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
Written Exam  120  80  Yes  Standard UoL penalty applies  Written Exam Notes (applying to all assessments) 1 in-class test - this work is marked anonymously. 1 programming assignment. This work is not marked anonymously. Written examination Learning outcomes covered by CA tasks will be covered within resit exam also: this obviates the need for explicit reassessment of these components. The resit exam will replace failed CA1 component. Practical assessment is employed for both formative assessment and summative assessment. Students will get short formative feedback on a weekly basis from the module demonstrators during tutorial / lab sessions. More detailed summative and formative feedback will be returned following assessment of the continuously assessed (CA) work.
CONTINUOUS Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
Coursework  1 hours  10  Yes  Standard UoL penalty applies  Class Test
Coursework  3 hours  10  Yes  Standard UoL penalty applies  Programming Assignment