Data structures and algorithms
- Class 30
- Practice 30
- Independent work 120
Course title
Data structures and algorithms
Lecture type
Obligatory
Course code
22-00-506
Semester
2
ECTS
6
Lecturers and associates
Course overview
This module introduces students to data structures and algorithms from two perspectives: the concepts they are built on and how to apply them to solve everyday programming problems.
This module is core to Software Engineering subspecialisation and it builds on and extends knowledge, understanding and skills learned in the Programming module in first semester to enable students to solve more complex programming problems and to provide further foundational learning for future modules. Skills learnt in this module will contribute significantly to students’ development as professionals in respecting fields.
Students will learn:
• abstract data types such as lists, linked lists, stacks, queues, hash tables, tree-based dictionaries and similar.
• concrete implementations in STL library.
• algorithms related to data structures such as modification, searching, sorting, iterating and similar.
• how to express and interpret algorithm complexity.
The module is taught in C++ programming language. The module assessment is based on solving a series of smaller practical tasks in C++ programming language and software development tool.
Literature
Essential reading:
1. Stroustrup, B. (2013) C++ Programming Language. 4th edn. Boston: Addison-Wesley Professional.
Recommended reading:
1. O'Dwyer, A. (2017) Mastering the C++17 STL: Make full use of the standard library components in C++17. Birmingham: Packt Publishing.
Further reading:
1. Cormen, T. (2009) Introduction to Algorithms. 3rd edn. Cambridge: MIT Press.
Bachelor of Computer Engineering, sub-specialization in Software Engineering
Minimal learning outcomes
- Determine and argue the time complexity a priori and a posteriori for a given algorithm derived in a programming language.
- Construct a solution using linear data structures (list, linked list, stack, queue) and associated algorithms.
- Construct a solution using hierarchical data structures (tree, heap, priority queue) and associated algorithms.
- Construct a solution using tree-based dictionaries and associated algorithms.
- Describe sorting and search algorithms and construct a solution based on sorting and search algorithms.
- Create a solution using addressing techniques and argue their time complexity.
Preferred learning outcomes
- Create more complex software solutions using multi-file projects and user-defined data types.
- Construct a more complex solution using linear data structures (list, linked list, stack, queue) and associated algorithms.
- Construct a more complex solution using hierarchical data structures (tree, heap, priority queue) and associated algorithms.
- Construct a more complex solution using tree-based dictionaries and associated algorithms.
- Describe sorting and search algorithms and construct a more complex solution based on sorting and search algorithms.
- Create a more complex solution using addressing techniques and argue their time complexity.