DTE-3611 Algorithms - Design and Analysis - 10 stp

A master-level course in algorithms that focuses on decidability and analysis, design and efficiency, and implementation.

Advanced algorithms in selected categories covering different complexities are analyzed, implemented, benchmarked, and reported utilizing scientific methods.

Determinability, NP-completeness, dynamic programming, network flow- and graph algorithms, matching, and selected advanced data structures are central topics.

A relevant undergraduate Bachelor degree in Engineering program in computer science or equivalent.

In addition, the following requirements must be met:

- minimum 25 credits in mathematics (equivalent to Mathematical Methods 1, 2 og 3), 5 credits in statistics and 7,5 ects i physics on a higher level is required.

Application Code: 9371

Recommended knowledge about and being able to apply basic object-oriented programming, algorithms and data structures. Recommended experience with basic C++ programming, compilers, build systems and debugging

Knowledge

• An overview of standard non-polynomial problems and problem settings.
• Basic understanding of polynomial, pseudo-polynomial, and non-polynomial problems, their differences, and some proofs.
• Basic understanding of solution strategies for pseudo-polynomial and non-polynomial problems.
• Basic knowledge of challenging tasks in research by understanding a scientific way of working.
• Special knowledge of theories, methods, and tools for determining, analyzing, and solving problems using computer programming.

Skills

• Design algorithms that can solve specific problems.
• Write technically secure and efficient source code that implements a given algorithm, its invariants, and bounds.
• Ability to check determinability, and perform performance analysis and benchmarking, for implementations of algorithms.
• Write a scientific report which communicates the applied methods, experiments, and results.

Competence

• Can apply the knowledge and skills to analyze problem settings, determine their solvability, and recognize and distinguish between polynomial and non-polynomial problems;
• Can apply the knowledge and skills to solve solvable problems, and propose solutions for some NP-complete problems;
• Can apply the knowledge and skills to communicate problems, challenges, properties, limitations, and results to other specialists in the field of computer science engineering.

The course is taught using an intensive teaching strategy during four non-consecutive weeks as a mixture of lectures and problem-based learning.

Problem-based learning, in this course, focuses on utilizing analysis- and programming skills to analyze problem settings, suggest strategies for solving, and then solve problems.

Efficient algorithms and their design and bounds are emphasized.