Efficient Computational Algorithms 2021

Image

USI/FAU Course on Efficient Computational Algorithms (3 ECTS)

Prof. E. Wit (USI),  Prof. O. Schenk (USI),  Prof. H. Koestler (FAU),  Dr. A. Ditter (FAU)

 

Course Objectives

This course provides an introduction to computational algorithms. It covers the common computing algorithms, algorithmic paradigms, and data structures used to solve these problems and applications in computing. The course emphasizes the relationship between algorithms and programming, and introduces performance measures and analysis techniques for these problems. The course primarily targets students from the Master double degree programme from FAU Erlangen on Computational Engineering and USI on Computational Science.

Course Description

This course provides a comprehensive overview of the concepts of algorithm analysis and computing development. We will review ten computing algorithms with the greatest influence on the development and practice of computing and engineering in the 20th century. Following is our list (in chronological order): Metropolis Algorithm for Monte Carlo, Simplex Method for Linear Programming, Krylov Subspace Iteration Methods, The Decompositional Approach to Matrix Computations, QR Algorithm for Computing Eigenvalues, Quicksort, Algorithm for Sorting, Fast Fourier Transform, Integer Relation Detection, and Fast Multipole Methods.

Examination Information

The students should select one of out 10 possible computational algorithms, and summarize it in the class (30 to 45 min, and if applicable, including a Python, or Julia software framework). 100% of the grade is determined by a mandatory graded project presentation and report on Friday January 29, 2021 from 9:30am to 1:00pm (at the latest). Please sign up on the Doodle pool for a project until December 13 (midnight, at the latest). The seminar projects will be assign to a first come, first serve basis.

We will use the USI course manegement system iCorsi iCorsi for all additional information and course anncounements. Please enroll on iCorsi as well.

Interesting Articles Relevant to the Course

from IEEE Computing in Science & Engineering - Volume 2, Issue 1, Jan.-Feb. 2000

Sullivan, F.
From the Editors: The joy of algorithms
Page 2
Dongarra, J.; Sullivan, F.
Guest Editors Introduction to the top 10 algorithms
Pages 22-23
Bailey, D.H.
Integer relation detection
Pages 24-28
Nash, J.C.
The (Dantzig) simplex method for linear programming
Pages 29-31
van der Vorst, H.A.
Krylov subspace iteration
Pages 32-37
Parlett, B.N.
The QR algorithm
Pages 38-42
JaJa, J.
A perspective on Quicksort
Pages 43-49
Stewart, G.W.
The decompositional approach to matrix computation
Pages 50-59
Rockmore, D.N.
The FFT: an algorithm the whole family can use
Pages 60-64
Beichl, I.; Sullivan, F.
The Metropolis Algorithm
Pages 65-69
Padua, D.
The Fortran I compiler
Pages 70-75
Board, J.; Schulten, L.
The fast multipole algorithm
Pages 76-79