Course Title:
Optimization and Complexity
Course Description:
Offers theory and methods of maximizing and minimizing solutions to various types of problems. Studies combinatorial problems including mixed integer programming problems (MIP); pure integer programming problems (IP); Boolean programming problems; and linear programming problems (LP). Topics include convex subsets and polyhedral subsets of n-space; relationship between an LP problem and its dual LP problem, and the duality theorem; simplex algorithm, and Kuhn-Tucker conditions for optimality for nonlinear functions; and network problems, such as minimum cost and maximum flow-minimum cut. Also may cover complexity of algorithms; problem classes P (problems with polynomial-time algorithms) and NP (problems with nondeterministic polynomial-time algorithms); Turing machines; and NP-completeness of traveling salesman problem and other well-known problems.
Fall Offering:
Lab/Coreq 1:
Spring Offering:
Lab/Coreq 2:
Summer Offering:
Lab/Coreq Remarks:
Summer 1 Offering:
Prerequisite 1:
Summer 2 Offering:
Prerequisite 2:
Cross-Listed Course 1:
Prerequisite 3:
Cross-Listed Course 2:
Prerequisite 4:
Cross-Listed Course 3:
Prerequisite 5:
Cross-Listed Course 4:
Prerequisite Remarks:
Cross-Listed Course 5:
Repeatable:
N
