Module Specification
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.
1. Module Title Complexity of Algorithms
2. Module Code COMP202
3. Year Session 2023-24
4. Originating Department Computer Science
5. Faculty Fac of Science & Engineering
6. Semester Second Semester
7. CATS Level Level 5 FHEQ
8. CATS Value 15
9. Member of staff with responsibility for the module
Dr NS Mande Computer Science Nikhil.Mande@liverpool.ac.uk
10. Module Moderator
11. Other Contributing Departments  
12. Other Staff Teaching on this Module
Mrs J Birtall School of Electrical Engineering, Electronics and Computer Science Judith.Birtall@liverpool.ac.uk
13. Board of Studies
14. Mode of Delivery
15. Location Main Liverpool City Campus
    Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
16. Study Hours 36

     12

     48
17.

Private Study

 102
18.

TOTAL HOURS

 150
 
    Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other
19. Timetable (if known)            
 
20. Pre-requisites before taking this module (other modules and/or general educational/academic requirements):

 
21. Modules for which this module is a pre-requisite:

 
22. Co-requisite modules:

 
23. Linked Modules:

 
24. Programme(s) (including Year of Study) to which this module is available on a mandatory basis:
25. Programme(s) (including Year of Study) to which this module is available on a required basis:
26. Programme(s) (including Year of Study) to which this module is available on an optional basis:
27. 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.
 
28. Learning Outcomes
 

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

(LO2) 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.
 

(LO3) 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.
 
29. Teaching and Learning Strategies
 

Teaching Method 1 - Lecture
Description:
Teaching Method 2 - Tutorial
Description:

Standard on-campus delivery
Teaching Method 1 - Lecture
Description: Mix of on-campus/on-line synchronous/asynchronous sessions
Teaching Method 2 - Tutorial
Description: On-campus synchronous sessions
 
30. Syllabus
   

1 A) Efficiency of Algorithms and Complexity Measures 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)  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  Introduction and analysis of basic data structures with their efficient implementation, including: stack (array), queue (cyclic buffer), and priority queue (heap). (3 lectures) Rooted trees - efficient data structures with implementation, from: tree traversal, binary search trees, balanced trees – AVL and 2-3 trees, Graphs and their implementations. (4 lectures) Advanced graph algorithms, including: network flow algorithms and bipartite matchings. (5 lectures)  Elementary number theory, Euclid’s GCD algorithm, cryptography (from: symmetric encryption, public-key cryptosystem, RSA). (4 lectures) Greedy algorithms and divide-and-conquer algorithms, dynamic programming (8 lectures) 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   Introduction:  Comparison of two ‘similar’ problems (Euler and Hamiltonian cycle);  other example problems:  3-Colouring, Satisfiability, k-Clique, etc;  Common features of the problems. (1 lecture)  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) Selected standard reductions:  SAT to 3-SAT, SAT to Clique ( 1 lecture)
 
31. Recommended Texts
  Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.
 

Assessment
32. EXAM Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
  (202) Written Exam There is a resit opportunity: Resit exam will replace failed CA components, the Learning Outcomes will be covered in the resit exam. Standard UoL penalty applies for late submiss 120 70
33. CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
  (202.1) Class Test There is a resit opportunity: Resit exam will replace failed CA components, the Learning Outcomes will be covered in the resit exam. Standard UoL penalty applies for late submissi 0 15
  (202.2) Programming Assignment There is a resit opportunity: Resit exam will replace failed CA components, the Learning Outcomes will be covered in the resit exam. Standard UoL penalty applies for l 0 15