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 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 ====

<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/bin/bib2xhtml -s unsortlist Bibliografia.bib Bibliografia.html -->
<ul class="bib2xhtml">

<!-- Authors: Sanjeev Arora and Boaz Barak -->
<li><a name="Arora.Barak/2009">Sanjeev</a> Arora and Boaz Barak.
<cite>Computational Complexity: A Modern Approach</cite>.
Cambridge University Press, 2009.</li>

<!-- Authors: Thomas H Cormen and Charles E Leiserson and Ronald L Rivest and
  Clifford Stein -->
<li><a name="Cormen.etal/2001">Thomas</a>&nbsp;H. Cormen, Charles&nbsp;E.
  Leiserson, Ronald&nbsp;L. Rivest, and Clifford Stein.
<a href="http://projects.csail.mit.edu/clrs"><cite>Introduction to
  Algorithms.</cite></a>
The MIT Press, 2nd edition, 2001.</li>

<!-- Authors: Michael R Garey and David S Johnson -->
<li><a name="Garey.Johnson/1979">Michael</a>&nbsp;R. Garey and David&nbsp;S.
  Johnson.
<a href="http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness"><cite>Computers and intractability: A guide to
  the theory of NP-completeness</cite></a>.
Freeman, 1979.</li>

<!-- Authors: E Horowitz and S Sahni -->
<li><a name="Horowitz.Sahni/1984">E</a>.&nbsp;Horowitz and S.&nbsp;Sahni.
<cite>Fundamentals of Computer Algorithms</cite>.
Computer Science Press, 1984.</li>

<!-- Authors: Laira Vieira Toscani and Paula A S Veloso -->
<li><a name="Toscani.Veloso/2005">Laira</a>&nbsp;Vieira Toscani and
  Paula A.&nbsp;S. Veloso.
<a href="http://www.inf.ufrgs.br/~laira/"><cite>Complexidade de
  Algoritmos</cite></a>.
Editora Sagra Luzzatto, 2a edition, 2005.</li>

<!-- Authors: G Ausiello and P Crescenzi and G Gambosi and V Kann and A
  Marchetti Spaccamela and M Protasi -->
<li><a name="Ausiello.etal/1999">G</a>.&nbsp;Ausiello, P.&nbsp;Crescenzi,
  G.&nbsp;Gambosi, V.&nbsp;Kann, A.&nbsp;Marchetti-Spaccamela, and M.&nbsp;Protasi.
<a href="http://www.nada.kth.se/~viggo/approxbook"><cite>Complexity and
  approximation &ndash; Combinatorial Optimization Problems and their
  Approximability Properties</cite></a>.
Springer-Verlag, 1999.</li>

<!-- Authors: Bernhard H Korte and Jens Vygen -->
<li><a name="Korte/2005">Bernhard</a>&nbsp;H. Korte and Jens Vygen.
<a href="http://www.or.uni-bonn.de/~vygen/co.html"><cite>Combinatorial
  optimization theory and algorithms</cite></a>.
Springer, 4th edition, 2008.
INF 65.012.122 K85c.</li>

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

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

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

</ul>

<!-- END BIBLIOGRAPHY Bibliografia -->

</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
