CCO - 00.2.01 - Design and Analysis of Algorithms

Amount of credits: 8
Total hours of theoretical classes: 60
Total hours of exercise classes, seminars or directed studies: 60

Objective

To enable the students to apply advanced algorithmic strategies to their projects
To empower students to analyze the correctness and performance of nontrivial algorithms
To allow students to consolidate algorithm design paradigms through various examples and demonstrations
To familiarize students with notions of computational complexity theory
To encourage students to evaluate which design techniques, algorithms, and data structures best suit each situation, problem, or application

Asymptotic notation: O, Omega, and Theta
Algorithm design paradigms: principles, algorithms, and applications of divide-and-conquer, greedy algorithms, and dynamic programming
Graphs: traversals, shortest paths, flow, and contraction
NP-completeness: completeness, definition, and interpretation (P vs NP problem)
Approaches to deal with NP-Complete and NP-Hard problems

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009. (T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009.).
R. Sedgewick, K. Wayne. Algorithms, 4th. ed., Addison-Wesley, 2011. (R. Sedgewick, K. Wayne. Algorithms, 4th. ed., Addison-Wesley, 2011.).
Nivio Ziviani. Projeto de algoritmos: com implementações em Java e C++. 2. ed. São Paulo: Cengage Learning, 2011. (Nivio Ziviani. Projeto de algoritmos: com implementações em Java e C++. 2. ed. São Paulo: Cengage Learning, 2011.).