ECE665: Algorithms

Instructor: Ramgopal Mettu

Time: TuTh 2:30-3:45, Place: LGRT 111

Description

This course will survey the design and analysis of algorithms. We will study several basic algorithmic paradigms (e.g. divide-and-conquer, dynamic programming, the greedy approach and randomization), their application to core problems in graph theory and optimization, as well as analysis of time and space complexity. Our focus will be on understanding these paradigms and studying the algorithmic problems that can be solved using that particular paradigm. For each of these problems, we will rigorously analyze the correctness and time complexity of the developed algorithms. The goals of this course are to i) survey a variety of problem areas where one or more algorithmic paradigms can yield solutions that are optimal (or near optimal) with respect to time and/or a given optimization criterion, and ii) to provide experience in applying techniques from one or more of these algorithmic paradigms to devise efficient algorithms. A rough chronological outline of the course topics is as follows:

Asymptotic Notation and Computational Models
Greedy Strategies
Divide and Conquer Strategies
Dynamic Programming
Network Flows and Linear Programming
Local Search Algorithms
Computational Tractability and Complexity
Approximation Algorithms
Randomized Algorithms