Overview
Aims
Develop algorithmic thinking and skills for developing complex algorithms
Learning basic tools for developing fundamental algorithms.
Knowledge of different types of fundamental algorithms and their development methods.
Use of an advanced programming language for implementing the studied algorithms.
Course contents
- General principles for algorithm development.
- Complexity of algorithms. Asymptotic analysis of worst case scenario.
- Numerical algorithms. Optimization of numerical algorithms. Primality. Bell numbers. Stirling numbers. Catalan numbers. Numbers with special properties.
- Sorting: HeapSort, QuickSort, RadixSort, Median-Algorithms, Lower Bounds.
- Analysis of sorting and searching algorithms complexity.
- Parallel sorting: enumeration sort, odd-even transposition sort. • Parallel sorting: bitonic sort, quicksort on a hypercube. • Binary search trees. • AVL trees. Red-black trees. B-trees. • Hash tables. Collision resolution. Hash functions. • Graph algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees.
- Branch&Bound algorithms. Exemples of problems solved with the Branch&Bound method.
- NP-complete algorithms. • Analysis, evaluation, and feed-back.
Learning outcomes
• acquisition of basic and specific knowledge about the concept of fundamental algorithms; • the ability to identify the applicability of the studied algorithms in real problems; • understanding the need of using advanced methods to create efficient algorithms when addressing problems from an specific domain; • Acquiring advanced knowledge of algorithms complexity and apply efficient methods to solve different practical problems.
Assessment
Written exams – 50%; Continuous assessment and laboratory practical works – 50%.