====== CMP 612: Algorithms (2023/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 ===== **Professor:** Marcus Ritt\\ **Total hours:** 30 h (in 15 lectures of 2h)\\ **Credits:** 2\\ **Summary:** Algorithms: Analysis of algorithms. Main techniques for designing algorithms.\\ **Time and room:** Tue/Thu 8.30, 113/43425.\\ **Consultation hours:** By appointment.\\ **Details:** On the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601|homepage of the course at PPGC]].\\ ===== News ===== * First lecture: Tue, Oct 10. ===== 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:2022-1|2022/1]], [[:cmp601:2020-2|2020/2]], [[: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-11959.pdf|Lecture notes}} (in Portuguese, updated Junho 2022). ==== Lectures ==== ^ No. ^ Date ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ | | | ** Algorithms ** | | | | | | 1a | 10/10 | Administrativa. Introduction. | 1 | | | 1.1 | | | 12/10 | Nossa Senhora Aparecida | | | | | | 2 | 17/10 | Basics of analysis and representative problems. | | | | 1.2 | | 3 | 19/10 | Basics of analysis and representative problems. | 2 | {{e0120232.pdf|E1}} | {{se0120232.pdf|S1}} | 2 | | | 20/10 | Exame de qualificação | | | | | | 4 | 24/10 | Graph algorithms 1. | | | | 3.[123],4.4 | | 5 | 26/10 | Graph algorithms 2. | | | | 3.[46] | | 6 | 31/10 | Graph algorithms 3. | | {{e0220232.pdf|E2}} | {{se0220232.pdf|S2}} | 3.5 | | | 02/11 | Finados | | | | | | 7 | 07/11 | [[:cmp612:greedy1|Greedy algorithms 1 (a distância).]] | 4 | | | 4.[12] | | | 09/11 | Semana academica | | | | | | 8 | 14/11 | Greedy algorithms 2. | 4 | | | 4.5, 4.9 | | 9 | 16/11 | Divide-and-conquer algorithms 1. | 5 | {{e0320232.pdf|E3}} | {{se0320232.pdf|S3}} | 5.[123] | | 10 | 21/11 | Divide-and-conquer algorithms 2. | 5 | | | 5.[45] | | 11 | 23/11 | Divide-and-conquer algorithms 3. | 5 | | | 5.6 | | 12 | 28/11 | Dynamic programming 1. | 6 | {{e0420232.pdf|E4}} | {{se0420232.pdf|S4}} | 6.[12] | | 13 | 30/11 | Dynamic programming 2. | 6 | | | 6.[45] | | 15 | 05/12 | Dynamic programming 3. | 6 | {{e0520232.pdf|E5}} | {{se0520232.pdf|S5}} | 6.[67] | | 1b | 07/12 | Revisão e exercícios. | | | | | | 15 | 12/12 | Prova (AUD-0) | | {{p.pdf|P}} | {{s.pdf|S}} | | | | A combinar | Prova de recuperação | | | | | | | 24/02 | Official end of lecture period 2023/2. | | | | | ==== Evaluation ==== See the [[https://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp612|homepage of the course at PPGC]]. Specifically in this source we have * An exam (see the agenda above), which contributes 80% of the final grade * Five exercise lists, which contribute 20% of the final grade * A retake exam, for those who participated in all activities, whose final grade is below 6. To pass, you need a grade of 6 in this exam. ==== Material ==== * Template ([[http://www.inf.ufrgs.br/~mrpritt/ca/answers.tex|LaTeX]],[[http://www.inf.ufrgs.br/~mrpritt/ca/answers.pdf|PDF]]) for exercise lists. ==== Bibliography ==== Locations of visitors to this page