Dec 02, 2022  
OHIO University Graduate Catalog 2020-21 
    
OHIO University Graduate Catalog 2020-21 [Archived Catalog]

Add to Portfolio (opens a new window)

CS 6040 - Advanced Algorithms


Advanced topics in the design and analysis of algorithms are explored. These topics include matching and network flow algorithms, randomized algorithms, and parallel algorithms, the theory of NP-completeness, NP-hard optimization problems, polynomial-time approximation algorithms, approximation schemes, approximability and non-approximability results.

Requisites: CS 5040 or 5060
Credit Hours: 3
Repeat/Retake Information: May not be retaken.
Lecture/Lab Hours: 3.0 lecture
Grades: Eligible Grades: A-F,WP,WF,WN,FN,AU,I
Learning Outcomes:
  • Students will be able to apply the theory of matchings to specific problems.
  • Students will be able to apply the theory of network flow to specific computational problems.
  • Students will gain an understanding of approximation complexity.
  • Students will gain an understanding of bipartite and general matchings and associate algorithms.
  • Students will gain an understanding of non-approximability results.
  • Students will gain an understanding of polynomial-time approximation algorithms and schemes.
  • Students will gain the ability to build approximation algorithms for NP-complete problems.
  • Students will understand how to develop and analyze parallel algorithms.
  • Students will understand how to develop and analyze randomized algorithms.



Add to Portfolio (opens a new window)