#### FUNDAMENTAL ALGORITHMS

###### Domain: Computer Science • Field of study: Computer Science
 Type of course: Compulsory Language of instruction: English Erasmus Language of instruction: English Name of lecturer: Ovidiu Domsa Seminar tutor: Adriana Bîrluțiu Form of education Full-time
 Form of instruction: Class Number of teaching hours per semester: 56 Number of teaching hours per week: 4 Semester: Autumn Form of receiving a credit for a course: Grade Number of ECTS credits allocated 5

#### Course 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 Entry Requirements:

Imperative and procedural programming Algorithms and data structures Graph 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.

#### Teaching methods:

Lecture, conversation, exemplification, problem solving, documentation.

#### 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.

#### Learning outcomes verification and assessment criteria:

Written exams – 50%; Continuous assessment and laboratory practical works – 50%.

#### Recommended reading:

-, • Adriana Bîrluțiu, Maria Muntean, Ovidiu Domsa, Fundamental Algorithms, Course notes and applications, Seria Didactică, 2015., - , - , - , -
-, • Cormen T.H., Leiserson E.C., Rivest R.R., Introduction in algorithms, MIT Press, 2001., - , - , - , -
-, • Dahl O.J., Dijkstra E.W., Hoare C.A.R., Structured Programing, Academic Press, 1972., - , - , - , -