Efficient Algorithms and Problem Complexity, 7.5 Credits

Contents

Part one (4,5 ECTS credits) studies central notions and results concerning efficient algorithmic techniques on the one hand and problem complexity on the other hand. Algorithmic techniques that are studied and analyzed with respect to efficiency are divide-and-conquer, greedy methods, and dynamic programming. When it comes to problem complexity, the course mainly discusses the classes P and NP, reduction and NP-completeness. The main focus of the course is on worst-case analyses of sequential algorithms using time as a measure of efficiency, but even average case efficiency and space requirements are briefly considered.

Part two (3 ECTS credits) consists of a number of supplementary areas that the student may choose among. Areas offered may be subject to change. However, typical areas include the following.
* The analysis of concrete programs by means of profiling software.
* Efficient algorithms and problem complexity in the area Automata and Formal Languages.
* Efficient parallel and distributed algorithms, and corresponding complexity classes.

Expected learning outcomes

After having completed the course the student will be able to:
* explain central algorithmic techniques such as divide-and-conquer, greedy methods and dynamic programming, analyze them in terms of effectiveness and describe typical problems they can be applied to
* describe, discuss and give examples of the classes P and NP and the concepts of time complexity, reductions and NP-completeness
* discuss the difference between worst and average case and the complexity measures ’time’ and ’space’
* demonstrate the ability to both deepen and broaden their knowledge by making themselves become acquainted with a related area not addressed during the lectures.

Required Knowledge

To be admitted you must have 60 ECTS-credits in Computing Science or 2 years of completed studies, in both cases including the courses Introduction to Discrete Mathematics (5MA008), Single variable Analysis I (5MA009), Data Structures and Algorithms (5DV108), Fundamentals of Computer Science (5DV037), and finally either Basic Calculus (5MA016) or Calculus in One Variable 2 (5MA011) or equivalent.
Proficiency in English equivalent to Swedish upper secondary course English A (IELTS (Academic) with a minimum overall score of 5.5 and no individual score below 5.0. TOEFL PBT (Paper-based Test) with a minimum total score of 530 and a minimum TWE score of 4. TOEFL iBT (Internet-based Test) with a minimum total score of 72 and a minimum score of 17 on the Writing Section).
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

Part 1: Instruction consists of lectures including scheduled times for questions and feedback between teachers and students. In addition to scheduled activities, individual work with the material is also required.

Part 2: Instruction consists of self-studies in which students work with literature or materials and information made available via the Internet. Students also have access to tutors.

Examination modes

Both parts of the course are examined through mandatory assignments. In Part 1, the grades given are Fail (U) or Pass (G). In Part 2 and on the course as a whole, the grades given are Fail (U), Pass (3), Pass with Credit (4) or Pass with Distinction (5). In order to pass the course completely, all mandatory parts must be passed. The final grade of the course is a combining assessment of the results that is made only after all mandatory parts have been passed. A student who has passed an examination may not be re-examined.

For all students who do not pass the regular examination there is another examination opportunity. A student who has taken two tests for a course or segment of a course without passing has the right to have another examiner assigned, 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.

TRANSFER OF CREDITS
In an degree, this course cannot be included, in whole or in part, simultaneously with another course of similar content. If in doubt, consult a student counselor at the Department of Computing Science or the program director of your program.

Note that this course cannot be fully accounted for in a degree together with one of the courses The Analysis of Algorithms (5DV022), Computational Complexity (5DV018) and Formal Languages (5DV023)

Transfer of credits is considered individually (see the University Code of Rules and regulations for transfer of credits). An application for transfer of credits is made on a special form and should be submitted to the Faculty of Science and Technology, Umeå University.