CM2303: Algorithms and Data Structures

School Cardiff School of Computer Science and Informatics
Department Code COMSC
Module Code CM2303
External Subject Code I100
Number of Credits 20
Level L5
Language of Delivery English
Module Leader Dr Bailin Deng
Semester Double Semester
Academic Year 2017/8

Outline Description of Module

This module introduces a variety of algorithmic techniques and aims to provide an understanding of the use and importance of data structures. It introduces the idea of classifying data according to its abstract behaviour, as distinct from its representation. A range of well-established data types is examined and their properties are described so that it becomes clear which representations are appropriate under which circumstances. An understanding of the basic skills needed in the design of algorithms and the interaction between algorithm and data structure in creating efficient code is emphasised.

On completion of the module a student should be able to

1. Understand the design of various fundamental data structures and know their advantages and disadvantages.

2. Explain the difference between various fundamental algorithmic techniques and employ these for simple algorithm design.

3. Understand and analyse the resource requirements of various algorithms and data structures.

4. Identify the most appropriate data structure and algorithm to solve a particular problem.

5. Implement, test and evaluate fundamental data structures and algorithms.

How the module will be delivered

The module will be delivered through a combination of lectures, supervised lab sessions, example classes and tutorials as appropriate.

Skills that will be practised and developed

Implement fundamental data structures and algorithms

Design simple algorithms

Analyse resource requirements of algorithms and data structures

Test and evaluate performance of algorithms and data structures

How the module will be assessed

Coursework: The coursework will allow the student to demonstrate their knowledge and practical skills and to apply the principles taught in lectures.

Exam: A written exam (2 h) will test the student's knowledge and understanding as elaborated under the learning outcomes.

Assessment Breakdown

Type % Title Duration(hrs)
Examination - Spring Semester 70 Algorithms And Data Structures 2
Written Assessment 10 Performance Evaluation Of Some Data Structures And Algorithms For A Particular Problem N/A
Written Assessment 10 Implementation Of Some Of The Data Structures And Algorithms To Solve Some Problem N/A
Written Assessment 10 Short Open Book Online Tests Covering Syllabus (Best Scoring 5 Out Of 8 Tests Will Be Used.) N/A

Syllabus content

Design of data structures and algorithms, abstract data types

Analysis of data structures and algorithms, complexity

Testing and measuring performance   

Influence of data layout, algorithms and hardware on performance.

Data structures and basic algorithms:

   Arrays and lists

   Stacks and queues

   Maps and dictionaries

   Trees and graphs

Algorithms and algorithmic techniques:

   Iteration and recursion

   Backtracking, divide-and-conquer, branch-and-bound, greedy algorithms

   Sorting and searching

   String processing

   Dynamic programming

   Discrete optimisation and heuristics

Essential Reading and Resource List

Data structures and algorithms in Java, Michael T. Goodrich, Roberto Tamassia. 6th edition, Wiley, 2014

 

Background Reading and Resource List

Not applicable.


Copyright Cardiff University. Registered charity no. 1136855