1. HiG
  2. Studiehåndbok
  3. Studiehåndbøker
  4. 2008-2009
  5. Emner
  6. Avdeling for informatikk og medieteknikk
  7. IMT4781 Design and analysis of Algorithms

Design and analysis of Algorithms
2008-2009 - IMT4781 - 5sp

Forventet læringsutbytte

This course provides an opportunity to study programming and scripting in the context of imaging. The course aims at providing knowledge on algorithm complexity, algorithm design and classical data structures.

On completion of this course the participant will be able to:

  • Demonstrate an understanding of programming concepts
  • Demonstrate an appreciation of the software design process
  • Devise, develop and implement algorithms for image processing
  • Demonstrate the use of a programming language to solve a computing problem in digital imaging.
  • Analyse the complexity of the code he/she writes
  • Use well known techniques for obtaining a certain complexity when possible
  • Choose the appropriate data structures

Emnets temaer

  1. Methodologies: divide and conquer, dynamic programming, and greedy strategies. Applications: sorting (asymptotics, merge sort as recursive algorithm), ordering and searching (recurrencies, quicksort, order statistics, heaps, amortized analysis, counting sort, hashing, binary search trees, red/black trees), graph algorithms, geometric algorithms, mathematical (number theory, algebra and linear algebra) algorithms, and string matching algorithms.
  2. Algorithm analysis: - worst case, average case, and amortized, with an emphasis on the close connection between the time complexity of an algorithm and the underlying data structures (Greedy algorithms, Huffman encoding, minimum spanning trees, dynamic programming, Bellman-Ford algorithm). We study NP-Completeness and methods of coping with intractability.
  3. Techniques such as approximation and probabilistic algorithms are studied for handling the NP-Complete problems.

Pedagogiske metoder

Forelesninger
Lab.øvelser
Oppgaveløsning

Vurderingsformer

Skriftlig eksamen, 3 timer
Øvinger

Vurderingsformer

Exam (75%), Practical work (25%)

Karakterskala

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

Sensorordning

One internal and one external examiner

Utsatt eksamen (tidl. kontinuasjon)

None

Tillatte hjelpemidler (gjelder kun skriftlig eksamen)

None

Læremidler

  • T. Cormen, C. Leiserson, and R. Rivest: Introduction to Algorithms, MIT Press, 1990
  • Levitin: The design and analysis of algorithm, Addison Wesley, 2007
  • P. Fränti, Introduction to Combinatoric Optimization Techniques, Lecture Notes, 2004

Supplerende opplysninger

CIMET