Índice
-
- INF 5010: Otimização combinatória
- INF 5016: Algoritmos avançados
- INF 5023: Técnicas de busca heurística.
Ferramentas de Utilizador
Barra Lateral
cmp601:2020-1
Tabela de Conteúdos
CMP 601: Algorithms and Theory of Computation (2020/1)
Somebody once asked John Hopcroft about the problem of P and NP. He answered: “On Tuesdays, I try to prove that they are equal, on the rest of the week - that they are different.” I believe that he has reduced the time to try to show that they are equal to Sunday afternoons.
General information
Professors: Álvaro Freitas Moreira, Marcus Ritt
Total hours: 60 h (in 30 lectures of 2h)
Credits: 4
Summary: Theory of Computation: Models of computation. Limitation of formal systems. Complexity theory.
Algorithms: Analysis of algorithms. Main techniques for designing algorithms.
Time and room: Tue/Thu 10.30, 102, building 43425 (regular), on Zoom by inviation (online).
Consultation hours: Thu 13.30, room 216, building 43425 (regular), by individual appointement (online).
Details: On the homepage of the course at PPGC.
News
- Results for quizzes.
Results
Additional material
- Lecture notes (in Portuguese, updated Sep 2019).
Lectures
| No. | Data | Topics | Chap. in notes | Exercises | Solutions | Reading | ||
|---|---|---|---|---|---|---|---|---|
| Algorithms | ||||||||
| 1 | 05/03 | Administrativa. Introduction. | 1 | 1.1 | ||||
| 2 | 10/03 | Representative problems. | 1.2 | |||||
| 3 | 12/03 | Basics of algorithm analysis. | 2 | 2 | ||||
| 16/03-03/04 | No lectures (suspended) | |||||||
 Starting here: plan for online lectures | ||||||||
| 4 | 07/04 | Graph algorithms 1. | 3.[123],4.4 | |||||
| 5 | 09/04 | Graph algorithms 2. | 3.[46] | |||||
| 6 | 14/04 | Graph algorithms 3. | 3.5 | |||||
| 7 | 16/04 | Greedy algorithms 1. | 4 | E1 | S1 | 4.[12] | ||
| 21/04 | Tiradentes | |||||||
| 8 | 23/04 | Greedy algorithms 2. | 4 | 4.5 | ||||
| 9 | 28/04 | Greedy algorithms 3. | 4 | 4.9 | ||||
| 30/04 | No lecture. | |||||||
| 10 | 05/05 | Divide-and-conquer 1. | 5 | E2 | S2 | 5.[123] | List 1 due | |
| 11 | 07/05 | Divide-and-conquer 2. | 5 | 5.[45] | ||||
| 12 | 12/05 | Divide-and-conquer 3. | 5 | 5.6 | ||||
| 13 | 14/05 | Dynamic programming 1. | 6 | 6.[12] | ||||
| 14 | 19/05 | Dynamic programming 2. | 6 | 6.[45] | List 2 due | |||
| 15 | 21/05 | Dynamic programming 3. | 6 | E3 | S3 | 6.[67] | ||
| Theory of computation | ||||||||
| 26/05 | Q&A session algorithms 1 | |||||||
| 28/05 | Q&A session algorithms 2 | |||||||
| 16 | 02/06 | Theory 1: Introduction – Noncomputability | List 3 due | |||||
| 17 | 09/06 | Theory 2: Introduction – Intractability | ||||||
| 11/06 | Corpus Cristi | |||||||
| 18 | 16/06 | Theory 3: Introduction – NP-complete problems | E4 | S4 | ||||
| 19 | 18/06 | Theory 4: Turing Machines | List 4 due | |||||
| 20 | 23/06 | Theory 5: Undecidability | ||||||
| 21 | 25/06 | Theory 6: Reducibility | ||||||
| 30/06 | No lecture. | |||||||
| 02/07 | No lecture. | |||||||
| 22 | 07/07 | Theory 7: Time Complexity I | ||||||
| 23 | 09/07 | Theory 8: Time Complexity II | ||||||
| 24 | 14/07 | Theory 9: Time Complexity III | ||||||
| 25 | 16/07 | Theory 10: Time Complexity IV | ||||||
| 26 | 21/07 | Theory 11: Exercises | ||||||
| 27 | 23/07 | Theory 12: Space Complexity I | ||||||
| 28 | 28/07 | Theory 13: Intractability | ||||||
| 29 | 30/07 | Theory 14: Exercises | ||||||
| 30 | 04/08 | Theory 15: Exercises | ||||||
| 30 | 04/08 | Theory 15: Exercises | ||||||
| End of online lectures | ||||||||
| 28/08 | First qualification exam | PA1 | SPA1 | |||||
| 20/11 | Second qualification exam | PA2 | SPA2 | |||||
| 02/12 | Official end of lecture period 2020/1. | |||||||
| Current end of suspended lectures: Dec 31 |
||||||||
Evaluation
See the homepage of the course at PPGC.
Material
- Template for exercise lists.
Bibliography
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
- Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Freeman, 1979.
- E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1984.
- Laira Vieira Toscani and Paula A. S. Veloso. Complexidade de Algoritmos. Editora Sagra Luzzatto, 2a edition, 2005.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
- Bernhard H. Korte and Jens Vygen. Combinatorial optimization theory and algorithms. Springer, 4th edition, 2008. INF 65.012.122 K85c.
- Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
- Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
- S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.
cmp601/2020-1.txt · Esta página foi modificada pela última vez em: 2021/01/22 12:43 (Edição externa)
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
