CM2303: Algorithms and Data Structures
| School | Cardiff School of Computer Science and Informatics |
| Department Code | COMSC |
| Module Code | CM2303 |
| External Subject Code | 100956 |
| 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) |
|---|---|---|---|
| Exam - 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.