MC558 - Design and Analysis of Algorithms II
MC558 - Projeto e Análise de Algoritmos II
MC558 - Proyecto y Análisis de Algoritmos II
This is an undergraduate course in Computer Science that aims to present the main concepts and algorithms in graphs, introduce classes of computational complexity (P, NP, NP-complete), and proofs of NP-completeness, as well as discuss basic notions of linear programming. It is expected that, by the end of the semester, the student will be able to solve computational problems by designing algorithms on graphs, proving their correctness, and analyzing their complexity. Additionally, the student should be capable of demonstrating the membership of problems in the NP-complete class and proposing linear programming models for some problems.
Offering: Second semester of 2024, from 05/08/2024 to 27/11/2024 Oferecimento: Oferta:
Schedule: Monday and Wednesday, from 2:00PM. to 4:00PM. Horário: Horario:
Location: PB14 Local: Localización:
PDD: Download here
Timeline: Cronograma: Cronograma: Download here
Student tutoring: Monday from 5:00PM. to 7:00PM. at room 6 / IC1, Thursday from 6:00PM. to 8:00PM. at lab 305 / IC3 Monitorias: Monitorías:
Bibliography
Bibliografia
Bibliografía
Main reference
Referência principal
Referencia principal
Complementary references
Referências complementares
Referencias complementares
Reduction examples
Exemplos de reduções
Ejemplos de reducciones
Lectures
Aulas
Clases
The slides will be added after each lecture. These can be used as a guide to review the lessons. To study and practice, you should read the main bibliography and solve the suggested exercises.
Acknowledgment: The slides are based on the material prepared by other professores. The list of professors that kindly provided the material is given below (in alphabetical order): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa, and Orlando Lee. The slides that will be shared has been adapted and modified by me, with possible introduction of errors, which I request to be reported to me.
Exercises lists
Listas de exercícios
Listas de ejercicios
The files will be added during the course.
Grades
Notas
Notas
Evaluation method
Método de avaliação
Método de evaluación
Two tests: P1 and P2. Three lists: L1, L2, and L3. One project: Pj. The final grade will be given by M=0.3P1+0.4P2+0.05L1+0.05L2+0.05L3+0.15Pj. Students with M in [2.5,5) may take a final test (E); for those students the new final grade will be M=min{5,0.5M+0.5E}. Students with M greater than or equal to 5 will be approved.
Dates: P1 - 09/10/2024. P2 - 25/11/2024. E - 13/12/2024.
The submission of exercise lists before the resolution and active participation in solving exercises during class may be considered to improve the grade.
Exercises solved in exams or submitted in the lists must be done individually. Any detection of fraud will result in a final grade of zero.
Files
Arquivos
Archivos
Attendance and grade files will be uploaded here.