COURSE SYLLABUS

Algorithms 7.5 credits

Algoritmer
Second cycle, D7009E
Version
Course syllabus valid: Spring 2022 Sp 3 - Present
The version indicates the term and period for which this course syllabus is valid. The most recent version of the course syllabus is shown first.

 Education level Second cycle Grade scale G U 3 4 5 Subject Computer Science Subject group (SCB) Computer Technology Main field of study Computer Science and Engineering

Entry requirements

The student should have knowledge about basic algorithms and data structures, and discrete mathematics, equivalent to the courses D0012E Algorithms and Data Structures and M0009M Discrete Mathematics. Good knowledge in English equivalent to English 6. .

Selection

The selection is based on 20-285 credits

Course Aim

To develop knowledge and skills in constructing and analyzing algorithms and data structures, to study advanced algorithmic solutions for the problems on sets, graphs, arithmetic, network and geometry, and to investigate the computational complexity of different problems.

After the course the student should be able to

• demonstrate knowledge of the disciplinary foundation and of proven experience in the design and analysis of algorithms and data structures
• demonstrate the ability to construct, analyze and critically evaluate various algorithmic solutions with respect to correctness, efficiency, and reliability
• demonstrate the ability to identify, formulate, and mange problems of high complexity by develop computer program that use computer resources efficiently
• show knowledge of mathematical tools for analyzing algorithms
• demonstrate the ability to plan and use appropriate methods to undertake advanced tasks within predetermined parameters
• demonstrate the ability to model , predict and evaluate the events even with limited information

Contents

Algorithm analysis: Correctness and efficiency, amortized and competitive analysis
Construction principles: Dynamic programming, approximation, augmenting data structures, randomized, dynamic, parallel, and on-line algorithms.
Computational complexity: Efficiency measures, upper and lower bounds, problem reduction technique, complexity classes including P, NP, and NP-complete problems.

Realization
Each course occasion´s language and form is stated and appear on the course page on Luleå University of Technology's website.

Lectures. During the course there could be homework assignments that render bonus points on the written exam that follows directly after the course has been given.

Examination
If there is a decision on special educational support, in accordance with the Guideline Student's rights and obligations at Luleå University of Technology, an adapted or alternative form of examination can be provided.

Written exam.

Remarks

The credits for this course cannot be combined with the credits for SMD 073, SMD087, SMD141, och SMD160.

Examiner
Jingsen Chen

Literature. Valid from Autumn 2012 Sp 1 (May change until 10 weeks before course start)
Th. H Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein: Introduction to Algorithms (Third Edition) ISBN 0-262-03384-4, 978-0-262-03384-8, MIT Press, 2009.
Scientific articles (determined at every occasion that the course is given).

Course offered by
Department of Computer Science, Electrical and Space Engineering

Modules