====== CMP 625: Algorithms (2024/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:** 60 h (in 30 lectures of 2h)\\ **Credits:** 4\\ **Summary:** Algorithms: Analysis of algorithms. Main techniques for designing algorithms.\\ **Time and room:** Tue/Thu 10.30, 109/43413.\\ **Consultation hours:** By appointment.\\ **Details:** On the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp625|homepage of the course at PPGC]].\\ ===== News ===== * Oct 4, 2024: second list of exercises and solution to the first list available * First lecture: Sep 24, 2024. ===== 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]]. * Homepage of CMP612 in [[:cmp612:2023-2|2023/2]]. * {{:cmp155:notas-11959.pdf|Lecture notes}} (in Portuguese, updated June 2022). ==== Lectures ==== ^ No. ^ Date ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ | 1 | 24/09 | Administrativa. Introduction. | 1 | {{ue01.pdf|E1}} | {{us01.pdf|S1}} | 1 | | 2 | 26/09 | Introduction and representative problems. | 2 | | | 1 | | 3 | 01/10 | Introduction and representative problems. | 2 | | | 1 | | 4 | 03/10 | Exercises: Introduction. | | | | | | 5 | 08/10 | Basics of analysis 1. | 2 | {{ue02.pdf|E2}} | {{us02.pdf|S2}} | 2 | | 6 | 10/10 | Basics of analysis 2. | 2 | | | 2 | | 7 | 15/10 | Basics of analysis 3. | 2 | | | 2 | | 8 | 17/10 | Exercises: Basics. | | | | | | 9 | 22/10 | Graph algorithms 1. | 4.2 | {{ue03.pdf|E3}} | {{us03.pdf|S3}} | 3 | | 10 | 24/10 | Graph algorithms 2. | 4.2 | | | 3 | | 11 | 29/10 | Graph algorithms 3. | 4.2 | | | 3 | | 12 | 31/10 | Exercises: Graphs. | | | | | | 13 | 05/11 | [[:cmp612:greedy1|Greedy algorithms 1.]] | 4 | {{ue04.pdf|E4}} | {{us04.pdf|S4}} | 4 | | 14 | 07/11 | [[:cmp601:greedy2|Greedy algorithms 2.]] | 4 | | | 4 | | 15 | 12/11 | Greedy algorithms 3. | 4 | | | 4 | | 16 | 14/11 | Exercises: Greedy algorithms. | | | | | | 17 | 19/11 | Divide-and-conquer algorithms 1. | 5 | {{ue05.pdf|E5}} | {{us05.pdf|S5}} | 5 | | 18 | 21/11 | Divide-and-conquer algorithms 2. | 5 | | | 5 | | 19 | 26/11 | Divide-and-conquer algorithms 3. | 5 | | | 5 | | 20 | 28/11 | Exercises: Divide-and-conquer algorithms. | | | | | | 21 | 03/12 | Dynamic programming 1. | 6 | {{ue06.pdf|E6}} | {{us06.pdf|S6}} | 6 | | 22 | 05/12 | Dynamic programming 2. | 6 | | | 6 | | 23 | 10/12 | Dynamic programming 3. | 6 | | | 6 | | 24 | 12/12 | Dynamic programming 4. | 6 | | | 6 | | 25 | 17/12 | Exercises: Dynamic programming. | | | | | | 26 | 19/12 | **Exam**. | | | | | | 23/12-04/01 || //Summer break// ||||| | 27 | 07/01 | Review of the exam and exercises. | | | | | | 28 | 09-13/01 | **Retake Exams**. | | | | | | 29 | 14/01 | Additional topics and exercises in design techniques | 4,5,6 | | | | | 30 | 16/01 | Additional topics and exercises in design techniques | 4,5,6 | | | | | | 18/01 | Official end of the lecture period. | 4,5,6 | | | | | | 20/01 | **Qualification exam**. | | | | | ==== Evaluation ==== See the [[https://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp625|homepage of the course at PPGC]]. Specifically in this source we have * An exam (see the agenda above), which contributes 60% to the final grade * Six exercise lists, which contribute 30% to the final grade * The presentation of two solved exercises in class, which contributes 10% to the final grade ==== 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