Design and Analysis of Algorithms
2009-2010 - IMT4781 - 5sp

Anbefalt forkunnskap

IMT2021 Algoritmiske metoder eller tilsvarende

Forventet læringsutbytte

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 NP-completeness, analysis techniques, and the main design principles such as divide-and-conquer, dynamic programming, branch-and-bound. Heap data structure and advanced binary search trees are also studied. Approximation, randomized and optimization techniques are considered for finding suboptimal solutions to NP-complete 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

Emnets temaer

• Complexity theory
• Data structures and graph theory
• Greedy algorithms
• Divide and conquer
• Dynamic programming
• NP completeness
• Approximation algorithms
• Meta-heuristics

Pedagogiske metoder

Forelesninger
Lab.øvelser
Nettstøttet læring
Oppgaveløsning
Samling(er)/seminar(er)

Vurderingsformer

Skriftlig eksamen, 3 timer
Øvinger

Vurderingsformer

Exam (75%), Practical work (25%) based on 1 exercise

Karakterskala

Bokstavkarakterer, A (best) - F (ikke bestått)

Sensorordning

One internal and one external examiner

Utsatt eksamen (tidl. kontinuasjon)

Ordinary re-sit for the written exam

Tillatte hjelpemidler (gjelder kun skriftlig eksamen)

None

Læremidler

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.

Supplerende opplysninger

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.