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 Efficient Sequential Algorithms
2. Module Code COMP309
3. Year Session 2023-24
4. Originating Department Computer Science
5. Faculty Fac of Science & Engineering
6. Semester First Semester
7. CATS Level Level 6 FHEQ
8. CATS Value 15
9. Member of staff with responsibility for the module
Professor I Potapov Computer Science Potapov@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 30

        6

36
17.

Private Study

114
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):

COMP202 Complexity of Algorithms
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 learn some advanced topics in the design and analysis of efficient sequential algorithms, and a few key results related to the study of their complexity.

 
28. Learning Outcomes
 

(LO1) At the conclusion of the module students should have an understanding of the role of algorithmics within Computer Science.

 

(LO2) Have expanded their knowledge of computational complexity theory.

 

(LO3) Be aware of current research-level concerns in the field of algorithm design.

 

(S1) Problem Solving - Numeracy and computational skills

 

(S2) Problem solving – Analysing facts and situations and applying creative thinking to develop appropriate solutions.

 
29. Teaching and Learning Strategies
 

Teaching Method 1 - Lecture
Description:
Attendance Recorded: Yes
Notes: 3 per week for 1 semester

Teaching Method 2 - Tutorial/Workshop
Description: Tutorial/Workshop are designed to help students to explore the subject in depth based on various active learning techniques
Attendance Recorded: Not yet decided

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

 
30. Syllabus
   

Advanced Topics in Algorithms (6 weeks) Algorithmic paradigms with applications: greedy algorithms with applications to scheduling and dynamic programming with applications to matrix-chain multiplication and the longest-common subsequence problem. Pattern-matching algorithms including the Knuth-Morris-Pratt algorithm. String algorithms. Text compression including Huffman coding and Lempel-Ziv Welch compression.

NP-Completeness (1 week) NP-completeness including a detailed look at polynomial-time reductions, showing that several problems are NP-complete: 3-Conjuctive Normal Form Satisfiability, Clique, Vertex Cover, and Subset Sum.

Approximation Algorithms and Complexity (2 weeks) Optimisation problems. The complexity class NPO. Methods for designing efficient approximation algorithms, and for showing that some problems do not have efficient approximation algorithms (assuming P is not NP). The design of absolute approximation algorithms. The study of some problems (for ex ample, planar graph colouring and edge colouring) for which there are absolute approximation algorithms. Showing that Maximum Clique does not have an absolute approximation algorithm. Constant-factor approximation algorithms.

Sequential vs. parallel algorithms (1 week) Introduction to parallel algorithmics and its relations to sequential computations. The complexity classes NC and P. How to compute things faster in parallel and solve larger problems without resorting to larger computers; what kind of parallel speedup is required and whether a problem is amenable at all to a parallel attack.

Selected Further Topics: Selected topics may vary from year to year, drawn from (for example):

Algorithms for finding maximum matchings in bipartite graphs, Algorithms for finding maximum matchings in general graphs, the proof of the Cook-Levin Theorem, Randomised Algorithms, advanced topics in complexity theory, number-theoretic algorithms and computational geometry. The complexit y class APX. The study of several problems (Multiprocessor Scheduling, Minimum Vertex Cover and Maximum Satisfiability) in APX. How to show that a problem is not in APX,assuming P is not NP. The complexity class PTAS. The design of a PTAS for MultiProcessor Scheduling and Knapsack. How to show that a problem does not have a PTAS, assuming P is not NP. Hardness of approximation for Maximum Clique.

 
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
  (309) Final Exam Standard UoL penalty applies for late submission. This is an anonymous assessment. Assessment Schedule (When) :Semester 1 150 70
33. CONTINUOUS Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
  (309.1) Assessment 1 Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Semester 1 0 15
  (309.2) Assessment 2 Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Semester 1 0 15