====== CMP 601: Algorithms and Theory of Computation (2020/2) ====== //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 online via [[http://zoom.us|Zoom]].\\ **Consultation hours:** Any time per email or via Discord ([[https://discord.gg/P2U5ARwFzt|Invitation]]).\\ **Details:** On the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601|homepage of the course at PPGC]]. ===== News ===== * First lecture: Tue, Jan 27. ===== Results ===== ===== Additional material ===== * Homepage of CMP155 (Análise e Desenvolvimento de Algoritmos) in [[:cmp155:2011-1|2011/1]], [[:cmp155:2010-1|2010/1]], [[:cmp155:2008-1|2008/1]] and [[:cmp155:2007-1|2007/1]]. * Homepage of CMP601 in [[:cmp601:2020-1|2020/1]], [[:cmp601:2019-1|2019/2]], [[:cmp601:2018-1|2018/1]], [[:cmp601:2016-2|2016/2]], and [[:cmp601:2015-1|2015/1]]. * {{:cmp155:notas-10619.pdf|Lecture notes}} (in Portuguese, updated Sep 2019). ==== Lectures ==== ^ No. ^ Data ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ | | | ** Algorithms ** | | | | | | 1 | 26/01 | [[:cmp601:intro1|Administrativa. Introduction.]] | 1 | | | 1.1 | | 2 | 28/01 | [[:cmp601:intro2|Basics of analysis and representative problems.]] | | | | 1.2 | | | 02/02 | //Navegantes// | | | | | | 3 | 04/02 | [[:cmp601:intro3|Basics of analysis and representative problems.]] | 2 | | | 2 | | | 05/02 | First qualification exam | | {{exq20202aa.pdf|PA1}} | {{exq20202aas.pdf|SPA1}} | | | 4 | 09/02 | [[:cmp601:graphs1|Graph algorithms 1]]. | | | | 3.[123],4.4 | | 5 | 11/02 | [[:cmp601:graphs2|Graph algorithms 2]]. | | | | 3.[46] | | | 16/02 | //Carnaval// | | | | | | 6 | 18/02 | [[:cmp601:graphs3|Graph algorithms 3.]] | | {{q0120202.pdf|E1}} | {{sq0120202.pdf|S1}} | 3.5 | | 7 | 23/02 | [[:cmp601:greedy1|Greedy algorithms 1.]] | 4 | | | 4.[12] | | 8 | 25/02 | [[:cmp601:greedy2|Greedy algorithms 2.]] | 4 | | | 4.5 | | 9 | 02/03 | [[:cmp601:greedy3|Greedy algorithms 3.]] | 4 | | | 4.9 | | 10 | 04/03 | [[:cmp601:divconq1|Divide-and-conquer algorithms 1.]] | 5 | {{q0220202.pdf|E2}} | {{sq0220202.pdf|S2}} | 5.[123] | | 11 | 09/03 | [[:cmp601:divconq2|Divide-and-conquer algorithms 2.]] | 5 | | | 5.[45] | | 12 | 11/03 | [[:cmp601:divconq3|Divide-and-conquer algorithms 3.]] | 5 | | | 5.6 | | 13 | 16/03 | [[:cmp601:dynprog1|Dynamic programming 1.]] | 6 | | | 6.[12] | | 14 | 18/03 | [[:cmp601:dynprog2|Dynamic programming 2.]] | 6 | {{q0320202.pdf|E3}} | {{sq0320202.pdf|S3}} | 6.[45] | | 15 | 23/03 | [[:cmp601:dynprog3|Dynamic programming 3.]] | 6 | | | 6.[67] | | | | ** Theory of computation ** | | | | | | | 25/03 | //Sem aula// | | | | | | 16 | 30/03 | Theory 1: Introduction -- Noncomputability | | | | | | 17 | 01/04 | Theory 2: Introduction -- Intractability | | {{q0420202.pdf|E4}} | {{sq0420202.pdf|S4}} | | | 18 | 06/04 | Theory 3: Introduction -- NP-complete problems | | | | | | 19 | 08/04 | Theory 4: Turing Machines | | | | | | 20 | 13/04 | Theory 5: Undecidability | | | | | | 21 | 15/04 | Theory 6: Reducibility | | | | | | 22 | 20/04 | Theory 7: Time Complexity I | | | | | | 23 | 22/04 | Theory 8: Time Complexity II | | | | | | 24 | 27/04 | Theory 9: Time Complexity III | | | | | | 25 | 29/04 | Theory 10: Time Complexity IV | | | | | | 26 | 04/05 | Theory 11: Exercises | | | | | | 27 | 06/05 | Theory 12: Space Complexity I | | | | | | 28 | 11/05 | Theory 13: Intractability | | | | | | 29 | 13/05 | Theory 14: Exercises | | | | | | 30 | 18/05 | Theory 15: Exercises | | | | | | | 21/05 | Second qualification exam | | {{exq20202ba.pdf|PA2}} | {{exq20202bas.pdf|SPA2}} | | | | 29/05 | Official end of lecture period 2020/2. | | | | | ⌛: material from last semester, to be updated during the semester. ==== Evaluation ==== See the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601/|homepage of the course at PPGC]]. ==== Material ==== * [[http://www.inf.ufrgs.br/~mrpritt/ca/answers.tex|Template]] for exercise lists. ==== Bibliography ==== Locations of visitors to this page