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 EFFICIENT SEQUENTIAL ALGORITHMS
Code COMP309
Coordinator Dr I Potapov
Computer Science
Potapov@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2016-17 Level 6 FHEQ First Semester 15

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.

Learning Outcomes

At the conclusion of the module students should have an understanding of the role of algorithmics within Computer Science;

have expanded their knowledge of computational complexity theory;

be aware of current research-level concerns in the field of algorithm design.

Syllabus
1  1

* 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 approx imation 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 example, 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 ex ample):

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 complexity 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.


Teaching and Learning Strategies

Lecture -

3 per week for 1 semester


Teaching Schedule
  Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
Study Hours 30

           30
Timetable (if known) 3 per week for 1 semester
  		           
Private Study 120
TOTAL HOURS 150

Assessment
EXAM Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
Written Exam  150  Semester 1  80  No reassessment opportunity  Standard UoL penalty applies  Final Exam There is no reassessment opportunity, No resit opportunity for final year modules. Notes (applying to all assessments) 2 (sets of) assessment tasks This work is not marked anonymously. Written examination No resit opportunity for final year modules.  
CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
Coursework  10 hours  Semester 1  10  No reassessment opportunity  Standard UoL penalty applies  Assessment 1 There is no reassessment opportunity, No resit opportunity for final year modules. 
Coursework  10 hours  Semester 1  10  No reassessment opportunity  Standard UoL penalty applies  Assessment 2 There is no reassessment opportunity, No resit opportunity for final year modules. 

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: