CS 4120 : Design and Analysis of Algorithms

CS 4120: 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: MATH 2220 or MATH 3220 or equivalents and grade of C or better in CS 3350.

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.

COMPUTER SCIENCE STUDENT OUTCOMES ADDRESSED BY THIS COURSE

• CS 1 Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions
• CS 6 Apply computer science theory and software development fundamentals to produce computing-based solutions

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)