Analysis and Design of Algorithms (CSEN 703)
Offered By:
Media Engineering and Technology Faculty
Description
It is an advanced undergraduate course in the art and science of algorithm analysis and design. Students are introduced to algorithm complexity analysis. Although space and work complexity are touched upon, the main concentration is on time complexity. Methods for carrying out asymptotic analysis and for solving recurrence equations are covered in detail. Students are acquainted to major methodical algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, etc. Parallel models of computation (PRAM, Mesh, Tree, Hypercube) are introduced, and fundamental parallel algorithms are discussed and analyzed for each model (parallel prefix, broadcasting, rotation, etc.) Throughout the course, examples of classical and state-of-the-art algorithms are provided for illustration. Example algorithms are selected from fields such as graph theory, DNA alignment, computer arithmetic, and data compression.