Design and Analysis of Algorithms
20092010

IMT4781
 5 ECTS
On the basis of
IMT2021 Algorithmic Methods or equivalent
Expected learning outcomes
Specification of the concept of algorithm and analysis of its computational complexity. Design principles of algorithms and their application to computing problems. Topics include theory of NPcompleteness, analysis techniques, and the main design principles such as divideandconquer, dynamic programming, branchandbound. Heap data structure and advanced binary search trees are also studied. Approximation, randomized and optimization techniques are considered for finding suboptimal solutions to NPcomplete problems. These include local search, genetic algorithms and swarm intelligence.
On completion of this course the students will be able to:
 Design algorithms for difficult problems
 Analyze and understand their complexity
 Implement the algorithms in practice
Topic(s)
• Complexity theory
• Data structures and graph theory
• Greedy algorithms
• Divide and conquer
• Dynamic programming
• NP completeness
• Approximation algorithms
• Metaheuristics
Teaching Methods
Lectures
Laboratory work
Net Support Learning
Exercises
Meeting(s)/Seminar(s)
Form(s) of Assessment
Written exam, 3 hours
Exercises
Form(s) of Assessment (additional text)
Exam (75%), Practical work (25%) based on 1 exercise
Grading Scale
Alphabetical Scale, A(best) – F (fail)
External/internal examiner
One internal and one external examiner
Resit examination
Ordinary resit for the written exam
Examination support
None
Teaching Materials
Reference book:
 Jon Kleinberg and Eva Tardos: Algorithm Design , Pearson International Edition, 2006.
Additional textbooks and lecture materials:
 T. Cormen, C. Leiserson and R. Rivest: Introduction to Algorithms , MIT Press, 2nd edition 2001
 Levitin, A. V.: The design and analysis of algorithm , Addison Wesley, 2007
 E. Horowitz, S. Sahni and S. Rajasekaran: Computer Algorithms , W. H. Freeman Press, 1997.
Additional information
CIMET.
Practical Laboratory Sessions : The student should be allowed to use the programming language he/she prefers (provided the language can handle usual data structures). Examples can be C++, C, Java, etc.