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.
Esta é uma disciplina de graduação em Ciência da Computação que objetiva apresentar os principais conceitos e algoritmos em grafos, introduzir classes de complexidade computacional (P, NP, NP-completo) e provas de NP-completude, assim como discutir noções básicas de programação linear. Se espera que, no final do semestre, o aluno consiga resolver problemas computacionais projetando algoritmos em grafos, provando que são corretos e analisando sua complexidade; ademais de ser capaz de provar pertença de problemas à classe NP-completo e propor modelos de programação linear para alguns problemas.
Esta es una asignatura de pregrado en Ciencia de la Computación que tiene como objetivo presentar los conceptos y algoritmos principales en grafos, introducir clases de complejidad computacional (P, NP, NP-completo) y demostraciones de NP-completitud, así como discutir nociones básicas de programación lineal. Se espera que, al final del semestre, el estudiante pueda resolver problemas computacionales diseñando algoritmos en grafos, demostrando su corrección y analizando su complejidad; además de ser capaz de demostrar la pertenencia de problemas a la clase NP-completo y proponer modelos de programación lineal para algunos problemas.
Offering: Second semester of 2024, from 05/08/2024 to 27/11/2024 Oferecimento: Segundo semestre de 2024, do 05/08/2024 ao 27/11/2024 Oferta: Segundo semestre de 2024, del 05/08/2024 al 27/11/2024
Schedule: Monday and Wednesday, from 2:00PM. to 4:00PM. Horário: Segunda-feira e quarta-feira, das 14:00 às 16:00 Horario: Lunes y miércoles, de las 2:00PM. a las 4:00PM.
Location: PB14 Local: PB14 Localización: PB14
Timeline: Cronograma: Cronograma: Download here Baixe aqui Baje aquí
Student tutoring: Tuesday from 12:00PM. to 2:00PM. at room 351 / IC3, Thursday from 6:00PM. to 8:00PM. at lab 305 / IC3 Monitorias: Terça-feira das 12h às 14h na sala 351 / IC3, quinta-feira das 18h às 20h no lab 305 / IC3 Monitorías: Martes de las 12:00PM. a las 2:00PM. en la sala 351 / IC3, jueves de las 6:00PM. a las 8:00PM. en el lab 305 / IC3
Bibliography
Bibliografia
Bibliografía
Main reference
Referência principal
Referencia principal
Complementary references
Referências complementares
Referencias complementares
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.
Os slides serão disponilizados após cada aula. Estes podem ser usados como guia para revisar as aulas. Para estudar e praticar, devem ler a bibliografia principal e resolver os exercícios sugeridos.
Los slides serán disponibilizados después de cada clase. Estos pueden ser utilizados como guía para revisar las lecciones. Para estudiar y practicar, deben leer la bibliografía principal y resolver los ejercicios sugeridos
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.
Agradecimentos: Os slides foram baseados em material didático preparado por outros professores. A lista dos professores que gentilmente cederam o material é dada a seguir (em ordem alfabética): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa e Orlando Lee. O material que será disponibilizado foi adaptado e modificado por mim, com possível introdução de erros, que solicito sejam reportados a mim.
Agradecimientos: Los slides se basearon en material didáctico preparado por otros profesores. La lista de los profesores que amablemente proporcionaron el material es la siguiente (en orden alfabética): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa y Orlando Lee. El material que se proporcionará fue adaptado y modificado por mí, con posible introducción de errores, que solicito sean reportados a mí.
Exercises lists
Listas de exercícios
Listas de ejercicios
The files will be added during the course.
Os arquivos serão adicionados durante o curso.
Los archivos serán adicionados durante el curso.
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.
Duas provas: P1 e P2. Três listas: L1, L2 e L3. Um projeto: Pj. A média final será M=0.3P1+0.4P2+0.05L1+0.05L2+0.05L3+0.15Pj. Alunos com M no intervalo [2.5,5) poderão fazer o exame (E) e, para eles, a nova média final será M=min{5,0.5M+0.5E}. Alunos com M maior ou igual que 5 estarão aprovados.
Dos pruebas: P1 y P2. Tres listas: L1, L2 y L3. Un projecto: Pj. La media final será M=0.3P1+0.4P2+0.05L1+0.05L2+0.05L3+0.15Pj. Alumnos con M en el intervalo [2.5,5) podrán realizar el exámen (E) y, para ellos, la nueva media final será M=min{5,0.5M+0.5E}. Alumnos con M mayor o igual que 5 estarán aprobados.
Dates: P1 - 02/10/2024. P2 - 27/11/2024. E - 04/12/2024.
Datas: P1 - 02/10/2024. P2 - 27/11/2024. E - 04/12/2024.
Fechas: P1 - 02/10/2024. P2 - 27/11/2024. E - 04/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.
A entrega de listas de exercícios antes da resolução e a participação da resolução de exercícios em aula, poderão ser coniseradas para melhorar a nota.
La entrega de listas de ejercicios antes da resolución y la participación de la resolución de ejercicios en clase, podrán ser coniserados para mejorar la nota.
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.
Exercícios resolvidos nas provas ou entregues nas listas, devem ser feitos individualmente. Qualquer detecção de fraude implicará em zerar a nota final.
Los ejercicios resueltos en las pruebas o entregados en las listas deben realizarse de forma individual. Cualquier detección de fraude implicará la anulación de la nota final.
Files
Arquivos
Archivos
Attendance and grade files will be uploaded here.
Arquivos com as notas e a frequência serão disponibilizados aqui.
Archivos con las notas y la asiduez serán disponibilizados aquí.