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
Upon completion of the course, the student should be able to

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

Skills and Abilities
Upon completion of the course, the student should be able to

• Analyze an algorithm with repsect to efficiency (FSR 3)
• Choose an appropriate algorithmic technique to solve a specific problem (FSR 4)
• Adapt an algorithmic technique or data structure to a specific problem to increase efficiency (FSR 5)
• Concretize an informally formulated problem in a way that makes it possible to process the problem algorithmically. (FSR 6)
• Describe a problem and its effective solution in a written report in a scientific manner. (FSR 7)

Values ​​and approaches
Upon completion of the course, the student should be able to

• Scientifically evaluate the pros and cons of different solutions of a problem (FSR 8)
• Critically evaluate practical results and compare them with theoretical expectations. (FSR 9)

Required Knowledge

Entry requirements include either a bachelor's degree in Computer Science or at least 90 ECTS of which at least 60 ECTS in Computer Science.

The following courses (or equivalent) are required:
- Introduction to discrete mathematics, 7.5 ECTS
- at least 7.5 ECTS in formal languages (e.g., CS3: Computations and Languages or Fundamentals of Computer Science)
- at least 7.5 ECTS in data structures and algorithms

Proficiency in English equivalent to Swedish upper secondary course English B/6. Where the language of instruction is Swedish, applicants must prove proficiency in Swedish 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 grades given, on part 2 and the course as a whole, are Fail (U), Pass (3) or Pass with Merit (4), or Pass with Distinction (5). The final grade of the course is a summary assessment of the results on the course and is decided after both mandatory parts are passed.

For all students who do not pass the regular examination there is another opportunity to do the examination. A student who has passed an examination may not be re-examined. A student who has taken two tests for a course or segment of a course, without passing, has the right to have another examiner appointed, unless there exist special reasons (Higher Education Ordinance Chapter 6, section 22). Requests for new examiners are made to the head of the Department of Computing Science.

Examination based on this syllabus is guaranteed for two years after the first registration on the course. This applies even if the course is closed down and this syllabus ceased to be valid.

TRANSFER OF CREDITS
Students have the right to be tried on prior education or equivalent knowledge and skills acquired in the profession can be
credited for the same education at Umeå University. Application for credit is submitted to the Student Services / Degree.
For more information on credit transfer available at Umeå University's student web, www.student.umu.se, and the Higher
Education Ordinance (Chapter 6). A refusal of crediting can be appealed (Higher Education chapter 12) to the University
Appeals Board. This applies to the whole as part of the application for credit transfer is rejected.

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.

Course connections to programmes and degrees
The course is a basic course for the Master's Programme in Computing Science.
The course can be part of the fulfilment of 45 credits (at least 37.5 of these on advanced level) within Computer Science when pursuing the specialization in Computer Science within a degree of Master of Science (Two Years) with Computing Science as Main Field of Study.