Module Catalogues, Xi'an Jiaotong-Liverpool University   
 
Module Code: DTS203TC
Module Title: Design and Analysis of Algorithms
Module Level: Level 2
Module Credits: 5.00
Academic Year: 2021/22
Semester: SEM2
Originating Department: Shool of AI and Advanced Computing
Pre-requisites: N/A
   
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 
A Describe the different classes of algorithms and design principles associated with them; Illustrate these classes by examples from classical algorithmic areas, current research and applications.

B Identify the design principles used in a given algorithm, and apply design principles to produce efficient algorithmic solutions to a given problem

C Have fluency in using basic data structures in conjunction with classical algorithmic problems

D Be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness.
Method of teaching and learning 
This module will be delivered by a combination of formal lectures and tutorials.
Syllabus 
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 lectures)

2. Asymptotic complexity and notation in conjunction with a discussion on the worst-case versus the average-case complexity. Recurrence equations and master method. (2 lectures).


B) Algorithms and Data Structures


1. Core algorithmic primitives including: notation, standard (sequential) models of computation, algorithmic design methods, formal proofs and methods of analysis on the example of recent research problems.(4 lectures)

2. Introduction and analysis of basic data structures with their efficient implementation, including: stack (array), queue (cyclic buffer), and priority queue (heap). (3 lectures)

3. 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)

4. Advanced graph algorithms, including: network flow algorithms and bipartite matchings. (5 lectures)

5. Elementary number theory, Euclid’s GCD algorithm, cryptography (from: symmetric encryption, public-key cryptosystem, RSA). (4 lectures)

6. Greedy algorithms and divide-and-conquer algorithms, dynamic programming (8 lectures)

7. 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 Hamiltonian cycle); other example problems: 3-Colouring, Satisfiability, k-Clique, etc; Common features of the problems. (2 lectures)

2. The Complexity 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 (3 lectures)
Delivery Hours  
Lectures Seminars Tutorials Lab/Prcaticals Fieldwork / Placement Other(Private study) Total
Hours/Semester 39      13    98  150 

Assessment

Sequence Method % of Final Mark
1 Formal Examination 60.00
2 Coursework 40.00

Module Catalogue generated from SITS CUT-OFF: 6/5/2020 5:39:29 PM