Please note: Due to alternative arrangements for teaching and
assessment in place from 18 March 2020 to mitigate against the restrictions in
place due to COVID-19, information shown for 2019/20 may not always be accurate.
Please note: you are viewing unit and programme information
for a past academic year. Please see the current academic year for up to date information.
Unit name |
Data Structures and Algorithms |
Unit code |
COMS21103 |
Credit points |
20 |
Level of study |
I/5
|
Teaching block(s) |
Teaching Block 1 (weeks 1 - 12)
|
Unit director |
Dr. Clifford |
Open unit status |
Not open |
Pre-requisites |
COMS10007
|
Co-requisites |
None
|
School/department |
Department of Computer Science |
Faculty |
Faculty of Engineering |
Description including Unit Aims
This unit aims to provide a solid foundation in the theory of computation, algorithms and data structures.
Intended Learning Outcomes
On successful completion of this unit, students will:
- Understand the foundations of asymptotic analysis and know how to prove the correctness of algorithms Be able to formulate and solve simple recurrence relations Recall standard string matching algorithms and be able to analyse their complexities.
- Know how to use dynamic programming to solve algorithmic problems.
- Recall standard graph algorithms, be able to analyse their time complexities and be able to apply them appropriately.
- Recall the fast Fourier transform algorithm and know how to apply it to combinatorial problems.
- Know how to build, use and analyse Bloom filters Be able to compare different dynamic search structures, analyse their complexities and understand their relative strengths.
Teaching Information
36 hours of lectures. A further 164 hours are nominally set aside for problems classes and private study.
Assessment Information
5% coursework (consisting of six equally-weighted online worksheets) and 95% exam.
Reading and References
The unit textbook is Introduction to Algorithms by Charles E.
Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen.
Recommended reading: Algorithm Design by J. Kleinberg and E. Tardos; Algorithms by S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani.