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. 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
The examiner can decide to deviate from the specified forms of examination. Individual adaptation of the examination shall be considered based on the needs of the student. The examination is adapted within the constraints of the expected learning outcomes. A student that needs adapted examination shall no later than 10 days before the examination request adaptation from the Department of Computing Science. The examiner makes a decision of adapted examination and the student is notified.

Other regulations

This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If in
doubt, consult the student counselors at the Department of Computing Science and / or the program director of your
program. In particular, this course can not, in whole or in part, be used in a degree together with 5DV170 Efficient algorithms.

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.