COURSE SYLLABUS

Algorithms 7.5 Credits

Algoritmer
Second cycle, D7009E
Version
Course syllabus valid: Spring 2017 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.

Syllabus established
by the Department of Computer Science and Electrical Engineering 28 Feb 2007

Last revised
by Jonny Johansson, HUL SRT 15 Jun 2016

Education level
Second cycle
Grade scale
G U 3 4 5
Subject
Computer Science
Subject group (SCB)
Computer Technology

Entry requirements

The student should have knowledge about basic algorithms and data structures, and discrete mathematics, equivalent to the courses D0012E and M0009M.


More information about English language requirements


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 ofalgorithms and data structures
  • demonstrate the ability to construct, analyze and critically evaluate various algorithmic solutionswith respect to correctness, efficiency, and reliability
  • demonstrate the ability to identify, formulate, and mangeproblems 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 theability 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

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

Written exam.

Remarks

The credits for this course cannot be combined with the credits forSMD 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

Items/credits
NumberTypeCreditsGrade
0001Written exam7.5G U 3 4 5

Study guidance
Study guidance for the course is to be found in our learning platform Canvas before the course starts. Students applying for single subject courses get more information in the Welcome letter. You will find the learning platform via My LTU.