CMPS 6610

Algorithms

Algorithms and Complexity

Instructor: Ramgopal Mettu

This course is a graduate introduction to the design and analysis of algorithms, and covers several basic algorithmic paradigms and their application to core computational problems in graph theory and optimization, as well as analysis of time and space complexity. The primary focus of the course will be on understanding the divide-and-conquer, greedy and dynamic programming paradigms for algorithm design as well as the problem areas to which they can be applied. We will also cover selected advanced techniques in algorithms and their use in a variety of now-classic results in the design and analysis of algorithms. Example application areas include graph theory, discrete optimization, numeric and scientific computing and machine learning. We will cover the following topics in this course:

• Asymptotic Analysis and Big-O Notation
• Divide-and-Conquer Algorithms
• Recurrences and The Master Method
• Greedy Algorithms
• Randomized Algorithms
• Graph Algorithms (Breadth-First Search, Depth-First Search, Connectivity and Shortest Paths)
• Dynamic Programming
• Linear Programming
• Parallel Algorithms
• Lower Bounds, Computational Complexity, and Approximation Algorithms

At the end of this course, students will have a technical understanding of a variety of algorithmic paradigms as well as their applications in practice.

Prerequisites

The equivalent of CMPS/MATH 2170 and/or CMPS 2200.

Meeting Time and Place

Lectures: MWF 12:00-1:50p, Stanley Thomas 302

Contact Information

Instructor:	Ramgopal Mettu
Telephone:	504.865.5804
Office:	Stanley Thomas 303E
Email:	rmettu@tulane.edu
Office Hours:	By appointment

Template design by Andreas Viklund