Computational Science & Engineering (CSE) Algorithms

Course Description and Topical Outline

Learning Objectives:

Students will develop knowledge and skills
concerning:

the design and analysis of real-world algorithms employed in computational science and engineering applications, and
performance optimization of applications using the best practices of algorithm engineering.

Goals:

The course balances the use of theory and practice in algorithm design by presenting the student with case studies from application domains. After an introduction to computational science and engineering applications, algorithm theory, and realistic models of computation, the course consists of three modules. The first focuses on basic techniques used in algorithm design. The second focuses on combinatorial algorithms. The third focuses on attaining high-performance implementations. Each module develops the theoretic framework and complements the study with examples from real-world problems using implementations on modern computing systems.

Topics: (45 Hours)

Computational Science & Engineering Introduction (3 weeks)
- Overview of Computational Science and Engineering Applications; characteristics and requirements
- Computability and Complexity
- Ideal and Realistic Models of Computation
- Design of Parallel Algorithm
- Performance Analysis
- Multi-scale, multi-discipline applications

Basic Techniques (4 weeks)
- Recursion
- Divide and Conquer
- Dynamic Programming
- Searching, Sorting, Merging

Combinatorial Algorithms (4 weeks)
- Graph algorithms for trees and networks
- Graph partitioning
- String algorithms
- Pattern matching
- Geometric algorithms

Algorithm Engineering (4 week)
- Cache-friendly algorithms
- Parallel and distributed algorithms and applications
- Problem solving frameworks
- Tools for Performance analysis
- Experimental methods and validation

Suggested Texts:

Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Algorithm Design (Hardcover) by Jon Kleinberg, Éva Tardos
Parallel Scientific Computing in C++ and MPI : A Seamless Approach to Parallel Algorithms and their Implementation by George Em Karniadakis, Robert M. Kirby II
An Introduction to Parallel Computing: Design and Analysis of Algorithms, Second Edition by Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta