Marcus Ritt

Esta página é apenas de leitura. Pode ver a fonte, mas não alterá-la. Informe-se com o administrador deste Wiki se achar que isto não está correcto.
====== 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 ====

<html>
<!-- BEGIN BIBLIOGRAPHY Bibliografia -->
<!--
    DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND!  IT IS MAINTAINED AUTOMATICALLY!
    YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED!
-->
<!-- Generated by: /home/ritt/arch/share/bib2xhtml/bib2xhtml.pl -s unsortlist Bibliografia.bib Bibliografia.html -->
<ul class="bib2xhtml">

<!-- Authors: Jon Kleinberg and Eva Tardos -->
<li><a name="Kleinberg.Tardos/2005"></a>Jon
  Kleinberg and &#xc9;va Tardos.
<cite>Algorithm design</cite>.
Addison-Wesley, 2005.</li>

<!-- Authors: Udi Manber -->
<li><a name="Manber/1989"></a>Udi Manber.
<cite>Introduction to Algorithms: A Creative Approach</cite>.
Addison-Wesley, 1989.</li>

<!-- Authors: Jeff Erickson -->
<li><a name="Erickson/2019"></a>Jeff Erickson.
<a href="https://jeffe.cs.illinois.edu/teaching/algorithms"><cite>Algorithms</cite></a>.
2019.</li>

<!-- Authors: Thomas H Cormen and Charles E Leiserson and Ronald L Rivest and
  Clifford Stein -->
<li><a name="Cormen.etal/2001"></a>Thomas&nbsp;H. Cormen,
  Charles&nbsp;E. Leiserson, Ronald&nbsp;L. Rivest, and
  Clifford Stein.
<a href="http://mitpress.mit.edu/9780262046305/introduction-to-algorithms"><cite>Introduction
  to Algorithms.</cite></a>
The MIT Press, 4th edition, 2022.</li>

<!-- Authors: Christos H Papadimitriou and Kenneth Steiglitz -->
<li><a
  name="Papadimitriou.Steiglitz/1982"></a>Christos&nbsp;H.
  Papadimitriou and Kenneth Steiglitz.
<cite>Combinatorial optimization: Algorithms and complexity</cite>.
Prentice-Hall, dover edition, 1982.</li>

<!-- Authors: S Dasgupta and C Papadimitriou and U Vazirani -->
<li><a name="Dasgupta.etal/2009"></a>S.&nbsp;Dasgupta,
  C.&nbsp;Papadimitriou, and U.&nbsp;Vazirani.
<cite>Algoritmos</cite>.
McGraw-Hill, 2009.</li>

<!-- Authors: Juraj Hromkovivc -->
<li><a name="Hromkovic/2001"></a>Juraj
  Hromkovi&#x10d;.
<cite>Algorithmics for hard problems</cite>.
Springer, 2001.
INF 65.012.122 H873a.</li>

<!-- Authors: Bernhard H Korte and Jens Vygen -->
<li><a name="Korte/2018"></a>Bernhard&nbsp;H. Korte and
  Jens Vygen.
<a href="http://www.or.uni-bonn.de/~vygen/co.html"><cite>Combinatorial
  Optimization &#x2013; Theory and Algorithms</cite></a>.
Springer, 6th edition, 2018.
INF 65.012.122 K85c.</li>

</ul>

</html>

<html>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
