Course Description:

This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. The course explores fundamental algorithm design techniques such as greedy, divide and conquer, dynamic programming, the network flow, reduction, and linear programming for efficient algorithm construction.

Learning Objectives:

• Understanding of the design and analysis of algorithms for a variety of problems
• Develop skills to reason about and prove properties of algorithms such as their correctness and running time.
• Use the concept of approximation andf randomness to find efficient algorithms for challenging problems.
• Use the theory of NP-completeness and other lower bounding techniques to argue for the difficulty of some problems.

Instructor:

• Victor Adamchik – adamchik@usc.edu

Teaching Assistants:

• Sandra Batista – sbatista@usc.edu
• Aida Rahmattalabi – rahmatta@usc.edu
• Zimo Li – zimoli@usc.edu
• Youwei Zhuo – youweizh@usc.edu

Lecture:

• Thursday, 5:00 – 7:20pm, SGM123