CS 5120 : Design and Analysis of Algorithms

CS 5120: Design and Analysis of Algorithms

Semester Hours:   3.0
Contact Hours:   3
Coordinator:   Tianyi Song
Text:   Introduction to Algorithms
Author(s):   Cormen, Leiserson, Rivest, and Stein
Year:   2009

SPECIFIC COURSE INFORMATION

Catalog Description

Algorithms for solving problems that occur frequently in computer applications. Basic principles and techniques for designing and analyzing algorithms. Introduction to computational complexity, divide-and-conquer, dynamic programming, greedy approach, and graph algorithms. Prerequisites: Full Admission to MS in CS program or consent of department.

Course type: REQUIRED

SPECIFIC COURSE GOALS

• I can determine the complexity of an algorithm.
• I can explain and implement different types of algorithms (e.g., Divide-and-Conquer, Dynamic Programming, Greedy Algorithms).
• I can explain and implement different graph algorithms.
• I understand the classes of algorithms (P, NP, and NP-complete) and the role of polynomial-reduction in establishing NP-completeness.
• I understand the implications of algorithm design in real-world applications.
• I can analyze relevant research and communicate my findings.

LIST OF TOPICS COVERED

• Introduction (1 week)
• Algorithmic Complexity (1 week)
• Divide-and-Conquer Strategy (2 weeks)
• Binary Search Tress (1 week)
• Dynamic Programming (3 weeks)
• Greedy Algorithms (1 week)
• Graph Algorithms (3 weeks)
• NP-Complete Problems (3 weeks)