MO417 - Complexity of Algorithms I

MO417 - Complexidade de Algoritmos I

MO417 - Complejidad de Algoritmos I

"Computer science is no more about computers than astronomy is about telescopes, biology is about microscopes or chemistry is about beakers and test tubes. Science is not about tools. It is about how we use them, and what we find out when we do." "Ciência da computação tem tanto a ver com o computador como a astronomia com o telescópio, a biologia com o microscópio, ou a química com os tubos de ensaio. A Ciência não estuda ferramentas, mas o que fazemos e o que descobrimos com elas." "La ciencia de la computación no trata más sobre computadoras que la astronomía sobre telescopios, la biología sobre microscopios o la química sobre tubos de ensayo. La ciencia no se trata de herramientas. Se trata de cómo las usamos y de lo que descubrimos cuando lo hacemos."
Attributed toAtribuída aAtribuída a Edsger W. Dijkstra

This is a graduate course in Computer Science that aims to present strategies for the design and analysis of algorithms, as well as to study the main concepts and algorithms in graphs. Additionally, it introduces classes of computational complexity (P, NP, NP-complete) and proofs of NP-completeness. It is expected that, by the end of the semester, the student will be able to solve computational problems by designing algorithms, proving their correctness, and analyzing their complexity. Furthermore, the student should be capable of demonstrating the membership of problems in the NP-complete class.

Esta é uma disciplina de pós-graduação em Ciência da Computação que tem como objetivo apresentar estratégias de projeto e análise de algoritmos, além de estudar os principais conceitos e algoritmos em grafos. Também se propõe a introduzir classes de complexidade computacional (P, NP, NP-completo) e provas de NP-completude. Espera-se que, ao final do semestre, o aluno seja capaz de resolver problemas computacionais projetando algoritmos, provando sua corretude e analisando sua complexidade. Além disso, espera-se que o aluno seja capaz de demonstrar a pertinência de problemas à classe NP-completo.

Esta es una asignatura de posgrado en Ciencia de la Computación que tiene como objetivo presentar estrategias de análisis y diseño de algoritmos, así como estudiar los principales conceptos y algoritmos en grafos. Además, se introducen clases de complejidad computacional (P, NP, NP-completo) y demostraciones de NP-completitud. Se espera que, al final del semestre, el estudiante pueda resolver problemas computacionales diseñando algoritmos, demostrando su corrección y analizando su complejidad; además de ser capaz de demostrar la pertenencia de problemas a la clase NP-completo.


Offering: 1st semester of 2024Oferecimento: 1ro semestre de 2024Oferta: 1er semestre de 2024
Schedule: Tuesday and Thursday, from 4:00PM. to 6:00PM.Horário: Terça-feira e Quinta-feira, das 16:00 às 18:00Horario: Martes y Jueves, de las 4:00PM. a las 6:00PM.
Location: Local: Localización: CC51

Bibliography

Bibliografia

Bibliografía

Main references

Referências principais

Referencias principales


T. Cormen, C. Leiserson, R. Rivest, C. Stein. "Introduction to Algorithms". MIT Press (MA); 3rd ed. (2009).
U. Manber. "Introduction to Algorithms: A Creative Approach". Addison-Wesley. (1989).

Complementary references

Referências complementares

Referencias complementares


C. Papadimitriou, K. Steiglitz. "Combinatorial Optimization: Algorithms and Complexity". Dover Publications. (1998).
M. Sipser. "Introduction to the Theory of Computation". Cengage Learning; 3rd ed. (2012).

J. Kleinberg, E. Tardos. "Algorithm Design". Pearson; 1st ed. (2005).
M. Garey e D. Johnson. "Computers and Intractability: a Guide to the Theory of NP- Completeness". Freeman. (1979).

A. Aho, J. Hopcroft, J. Ullman. "The Design and Analysis of Computer Algorithms". Addison-Wesley. (1974).

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

Topics Tópicos Asuntos
slides (Portuguese only) slides (somente em Português) slides (solo en Portugués)
Lecture 00 - Course presentation Aula 00 - Apresentação da disciplina Aula 00 - Presentación del curso
Lecture 01 - Mathematical proofs Aula 01 - Demonstrações matemáticas Aula 01 - Demostraciones matemáticas
Lecture 02 - Asymptotic notation Aula 02 - Notação assintótica Aula 02 - Notación asintótica
Lecture 03 - Asymptotic notation and exercises Aula 03 - Notação assintótica e exercícios Aula 03 - Notación asintótica y ejercicios
Lecture 04 - Analysis and correctness of algorithms Aula 04 - Análise e correção de algoritmos Aula 04 - Análisis y correción de algoritmos
Lecture 05 - Analysis of recursive algorithms Aula 05 - Análise de algoritmos recursivos Aula 05 - Análisis de algoritmos recursivos
Lecture 06 - Analysis of recursive algorithms Aula 06 - Análise de algoritmos recursivos Aula 06 - Análisis de algoritmos recursivos
Lecture 07 - Correctness and design of recursive algorithms Aula 07 - Correção e projeto de algoritmos recursivos Aula 07 - Corrección y diseño de algoritmos recursivos
Lecture 08 - Recursive algorithms design. Divide and conquer Aula 08 - Projeto de algoritmos recursivos. Divisão e conquista Aula 08 - Diseño de algoritmos recursivos. División y conquista
Lecture 09 - Sorting and priority queue Aula 09 - Ordenação e fila de prioridade Aula 09 - Ordenamiento y fila de prioridad
Lecture 10 - Introduction to randomized algorithms and sorting by partitioning Aula 10 - Introdução a algoritmos aleatorizados e ordenação por particionamento Aula 10 - Introducción a algorimos aleatorios y ordenamiento por particionamiento
Lecture 11 - Sorting lower bound. Sorting in linear time Aula 11 - Cota inferior para ordenação. Ordenação linear Aula 11 - Límite inferior para ordenamiento. Ordenamiento lineal
Lecture 12 - Algorithms for order statistics Aula 12 - Algoritmos para estatísticas de ordem Aula 12 - Algoritmos para estadísticas de orden
Lecture 13 - Dynamic programming Aula 13 - Programação dinâmica Aula 13 - Programación dinámica
Lecture 14 - Dynamic programming Aula 14 - Programação dinâmica Aula 14 - Programación dinámica
Lecture 15 - Greedy algorithms Aula 15 - Algoritmos gulosos Aula 15 - Algoritmos golosos
Lecture 16 - Graph concepts Aula 16 - Conceitos sobre grafos Aula 16 - Conceptos sobre grafos
Lecture 17 - Graph concepts Aula 17 - Conceitos sobre grafos Aula 17 - Conceptos sobre grafos
Lecture 18 - Graph search Aula 18 - Buscas em grafos Aula 18 - Búsquedas en grafos
Lecture 19 - Graph search. Topological ordering Aula 19 - Buscas em grafos. Ordenação topológica Aula 19 - Búsquedas en grafos. Orden topológica
Lecture 20 - Connectivity. Minimum spanning tree Aula 20 - Conexidade. Árvores geradoras mínimas Aula 20 - Conexidad. Árbol genenador mínimo
Lecture 21 - Minimum spanning tree algorithms Aula 21 - Algoritmos para árvore geradora mínima Aula 21 - Algoritmos para árbol genenador mínimo
Lecture 22 - Minimum paths Aula 22 - Caminhos mínimos Aula 22 - Caminos mínimos
Lecture 23 - Minimum paths Aula 23 - Caminhos mínimos Aula 23 - Caminos mínimos
Lecture 24 - Reductions Aula 24 - Reduções Aula 24 - Reducciones
Lecture 25 - NP-complexity Aula 25 - NP-complexidade Aula 25 - NP-complejidad
Lecture 26 - NP-completeness Aula 26 - NP-completude Aula 26 - NP-completud

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 e 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 e 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.

files (Portuguese only) arquivos (somente em Português) archivos (solo en Portugués)
List 01 - Algorithm desing (do not submit) Lista 01 - Projeto de algoritmos (não entregar) Lista 01 - Diseño de algoritmos (no entregar)
List 02 - Algorithm desing (must submit) Lista 02 - Projeto de algoritmos (deve entregar) Lista 02 - Diseño de algoritmos (debe entregar)
List 03 - Graphs, reductions and NP-complexity (do not submit) Lista 03 - Grafos, reduções e NP-complexidade (não entregar) Lista 03 - Grafos, reducciones y NP-complejidad (no entregar)
List 04 - Graphs, reductions and NP-complexity (must submit) Lista 04 - Grafos, reduções e NP-complexidade (deve entregar) Lista 04 - Grafos, reducciones y NP-complejidad (debe entregar)


Grades

Notas

Notas

Evaluation method

Método de avaliação

Método de evaluación


Two tests: P1, and P2. Two exercises lists: E1 and E2. The average grade will be given by M=0.2P1+0.5P2+0.1E1+0.2E2. The final grades will be: A if M in [8.5,10], B if M in [7,8.5), C if M in [5,7), and D if M in [0,5).

Duas provas: P1 e P2. Duas entregas: E1 e E2. A média será dada por M=0.2P1+0.5P2+0.1E1+0.2E2. O conceito final será: A se M está em [8.5,10], B se M está em [7,8.5), C se M está em [5,7) e D se M está em [0,5).

Dos pruebas: P1 y P2. Dos entregas: E1 y E2. La media será dada por M=0.2P1+0.5P2+0.1E1+0.2E2. La nota final será: A si M está en [8.5,10], B si M está en [7,8.5), C si M está en [5,7), y D si M está en [0,5).

Dates: P1 - 30/04/2024. P2 - 27/06/2024.

Datas: P1 -30/04/2024. P2 - 27/06/2024.

Fechas: P1 - 30/04/2024. P2 - 27/06/2024.

Any detection of fraud will result in a grade of D.

Qualquer detecção de fraude implicará em finalizar com conceito D.

Cualquier detección de fraude implicará terminar con nota D.

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í.