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, based on the assignment tasks included in Part0 1, writing a report on an algorithmic problem and its solution that covers all the way from the initial, usually unclearly specified problem to the final algorithm and its analysis. Here, experimental evaluations based on implementations made by the student can be included. The moment trains the student's ability to go from an unclear formulated problem specification to an exact wording, develop an appropriate algorithmic solution, if possible improve it by adapting it to the problem's particularities, as well as analyze and discuss its effectiveness in reporting form.

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

Univ: To be admitted you must have (or equivalent) 90 ECTS-credits including 60 ECTS-credits in Computing Science or two years of completed studies within a study programme (120 ECTS-credits). In both cases, the studies must include at least 7.5 ECTS-credits with in discrete mathematics (e.g. 5MA143), at least 7.5 ECTS-credits within formal languages (e.g. 5DV037 or 5DV169 together with 5DV162), and at least 7.5 ECTS-credits within data strutuces and algorithms (e.g. 5DV149, 5DV150 ort 5DV169).  A Bachelor's degree with a major in Computer Science is considered to be equivalent.

Proficiency in English equivalent to Swedish upper Secondary course English A/5. 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 the students in small groups get feedback on the problem solving they have worked out, as well as the teacher's feedback on draft reports that can be submitted at predefined times. In addition to scheduled activities, individual work with the material and assignments also requires minor implementations and computer experiments. Tutorial meetings and submission of drafts are voluntary. It is the student's responsibility to prepare material for them in time to receive 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.