Module Catalogues, Xi'an Jiaotong-Liverpool University   
 
Module Code: CSE204
Module Title: Complexity of Algorithms
Module Level: Level 2
Module Credits: 5.00
Academic Year: 2017/18
Semester: SEM2
Originating Department: Computer Science and Software Engineering
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 
On successful completion of the module, students are expected

1.to have an appreciation of the diversity of computational fields to which algorithmics has made significant contributions;

2.to 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.;

3.to be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness;

4.to be able to apply the knowledge gained in this module to the specification and analysis of data structures and algorithms.
Method of teaching and learning 
Students will be expected to attend three hours of formal lectures as well as to participate in one hour of supervised problem classes in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while problem classes will allow students to practice those skills.

In addition, students will be expected to devote three hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading.

Continuous assessment will be used to test to what extent practical skills have been learnt. A written examination at the end of the module will assess the academic achievement of students.
Syllabus 
Lectures 1-4 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).


Lectures 5-9 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).


Lectures 10-14 Rooted Trees

efficient data structures with implementation, from: tree traversal, binary search trees, balanced trees – AVL and 2-3 trees, Graphs and their implementations.


Lectures 15-16 Advanced Graph Algorithms

Shortest paths (from: Dijkstra’s algorithm, Bellman-Ford algorithm), MST construction (Kruskal’s algorithm, Prim’s algorithm and Baruvka's algorithm).


Lectures 17-20 Introduction to Cryptography

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


Lectures 21-24 Heuristic Methods

Greedy algorithms and divide-and-conquer algorithms, dynamic programming


Lectures 25-28 Text Processing

This includes pattern matching (from: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp), longest common subsequence (dynamic programming).


Lectures 29-31 Networks

Complexity measures, broadcast , unicast, leader election problem.


Lectures 32-42 Computational Intractability and NP-Completeness

Introduction of the notion of hard computational problems, and an in-depth discussion of why certain problems are 'easy' and others are 'hard'. The Complexity Class NP: formulation of computational problems in terms of questions about witnesses to solutions; completeness; Approaches to hard optimisation problems: approximation methods
Delivery Hours  
Lectures Seminars Tutorials Lab/Prcaticals Fieldwork / Placement Other(Private study) Total
Hours/Semester 42     14      94  150 

Assessment

Sequence Method % of Final Mark
1 Final Exam 80.00
2 Assessment Task 5.00
3 Assessment Task 5.00
4 Assessment Task 10.00

Module Catalogue generated from SITS CUT-OFF: 10/22/2017 10:36:18 AM