Design and analysis of Algorithms
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
- 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.
- 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.
- Techniques such as approximation and probabilistic algorithms are studied for handling the NP-Complete problems.
Skriftlig eksamen, 3 timer
Exam (75%), Practical work (25%)
Bokstavkarakterer, A (best) - F (ikke bestått)
One internal and one external examiner
Utsatt eksamen (tidl. kontinuasjon)
Tillatte hjelpemidler (gjelder kun skriftlig eksamen)
- 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