Efficient Algorithms, 7.5 credits

Contents

The course covers techniques for constructing effective algorithms and typical data structures used in these. Special consideration is given to the fact that efficiency depends not only on the inherent asymptotic behavior of the algorithms but also on the specific problem instances on which it is applied. Standard algorithms and data structures need therefore often be chosen and adapted to solve the problem as effectively as possible.

Part 1, Algorithmic techniques and data structures, 3 credits

Deals with effective algorithmic techniques (divide-and-conquer, greedy, dynamic programming), their usages, pros, and cons, illustrating these techniques using central algorithms, and discussing examples of effective data types (Eg heaps, red-black trees, union-find) and their implementation.

Part 2, Problem solving and algorithm analysis, 4.5 credits

Consists of the student, both theoretically and empirically, examining variants of a known algorithm with respect to efficiency and writing a report on this. The entire chain from initial, usually unclear specified research questions to the completed algorithmic solution and its theoretical and empirical analysis are included. The part trains the student's ability to go from an unclearly formulated problem specification to an exact formulation, develop an appropriate algorithmic solution, if possible improve it by adapting it to the problem's particularities, as well as analyzing and discussing its effectiveness.

Expected learning outcomes

Knowledge and understanding

After completing the course, the student should be able to

• (FSR 1) explain and analyze various advanced data structures and account for their pros and cons with regard to efficiency,
• (FSR 2) critically account for the most important techniques for creating effective algorithms.

Competence and skills

After completing the course, the student should be able to

• (FSR 3) analyze an algorithm with repsect to efficiency,
• (FSR 4) adapt an algorithmic technique or data structure to a specific problem to increase efficiency,
• (FSR 5) describe a problem and its effective solution in a written report in a scientific manner.

Judgement and approach

After completing the course, the student should be able to

• (FSR 6) scientifically evaluate the pros and cons of different solutions of a problem,
• (FSR 7) critically evaluate practical results and compare them with theoretical expectations.

Required Knowledge

At least 90 ECTS, including 60 ECTS Computing Science, or at least 120 ECTS within a study programme. At least 7.5 ECTS programming; 7.5 ECTS data structures and algorithms; 7.5 ECTS discrete mathematics; and 7.5 ECTS formal languages. Proficiency in English equivalent to the level required for basic eligibility for higher studies.

Form of instruction

Teaching consists of three different elements: Teacher-led lessons, tutorial meetings where problem statements and the suggested solutions or identified problems are discussed, as well as feedback on draft reports submitted at predefined times. In addition to scheduled activities, individual work with the material is also required. It is the student's responsibility to get into the material in time and to prepare any questions to get appropriate feedback.

Examination modes

Part 1 is examined though an oral exam. If the number of students on the course exceeds 25, then the oral exam is replaced with a written exam in halls. The grades given are Fail (U) or Pass (G).

Part 2 is examined by a written report submitted by the student at the end of the course. The grading scheme is Fail (U), Pass (3) or Pass with Merit (4), or Pass with Distinction (5).

The grading scheme on the course as a whole is Fail (U), Pass (3) or Pass with Merit (4), or Pass with Distinction (5). The grade is determined by the grade on Part 2.

Adapted examination

For a student who has a decision regarding recommended support due to a disability, the examiner may decide to deviate from the course syllabus examination format. Individual adaptation of the examination format should be considered based on the student's needs and the expected learning outcomes of the course. For more information, see the Procedures for Support for Students with Disabilities and the Rules for Grading and Examination.

Other regulations

This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If indoubt, consult the student counselors at the Department of Computing Science and / or the program director of your program.

Transitional provisions

If the syllabus has expired or the course has been discontinued, a student who at some point registered for the course is guaranteed at least three examinations (including the regular examination) according to this syllabus for a maximum period of two years from the syllabus expiring or the course being discontinued.