====== CMP 601: Algorithms and Theory of Computation (2015/1) ======

//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:** Leila Ribeiro, 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:** Seg/Qua 13.30, room 102.\\
**Consultation hours:** Seg 13.30, sala 201\\
**Details:** Ver a [[http://ppgc.inf.ufrgs.br/index.php?option=com_content&view=category&layout=blog&id=81&Itemid=73|homepage of the course at PPGC]].

===== News =====

  * Introduction: Mar 2, 2015.
  * First exam: Mar 4, 2015. The exam will take 2.5 hours.
  * Second exam: Jul 6, 2015. The exam will take 2.5 hours.

===== Results =====

  * [[2015-1a-Notas|Resultados]] do primeiro exame de qualificação.
  * [[2015-1b-Notas|Resultados]] do segundo exame de qualificação.
  * [[2015-1c-Notas|Resultados]] da disciplina.


===== 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]]
  * {{:cmp155:notas-4227.pdf|Lecture notes}} (in Portuguese, updated 16/5/2012).


==== Lectures ====
==== Aulas ====

^ No.  ^ Data   ^ Tópicos                                              ^ Notas pág. ^  Exercícios  ^  Soluções 	 ^ Leitura ^
|     |       | ** Introduction & pre-semester exam **                         |           |   |   |                       |
|   1 | 02/03 | Administrativa, Introduction.                                  |           |   |   |                       |
|     | 04/03 | Pre-semester exam.                                             |           |   |   |                       |
|     | 09/03 | //Evaluation of exam//                                         |           |   |   |                       |
|     | 11/03 | //Evaluation of exam//                                         |           |   |   |                       |
|     |       | ** Theory of computation **                                    |           |   |   |                       |
|   2 | 16/08 | Proof techniques and structural induction                      |           |   |   |                       |
|   3 | 18/08 | The Turing machine: motivation, importance                     |           |   |   |                       |
|   4 | 23/03 | Universal TMs, multi-tape TMs                                  |           |   |   |                       |
|   5 | 25/03 | Primitive recursive functions                                  |           |   |   |                       |
|   6 | 30/03 | Primitive recursive functions, exercises                       |           |   |   |                       |
|   7 | 01/04 | Partial recursive functions                                    |           |   |   |                       |
|   8 | 06/04 | Equivalence of TMs and partial recursive functions             |           |   |   |                       |
|   9 | 08/04 | Equivalence of TMs and partial recursive functions             |           |   |   |                       |
|  10 | 13/04 | The halting problem, reductions, Rice's theorem                |           |   |   |                       |
|  11 | 15/04 | O-notation, introduction to complexity theory, nondeterminism  |           |   |   |                       |
|  12 | 20/04 | The Church-Turing thesis (a distância)                         |           |   |   |                       |
|  13 | 22/04 | Languages and problems, classes P and NP, NP-completeness      |           |   |   |                       |
|  14 | 27/04 | The Cook-Levin theorem                                         |           |   |   |                       |
|  15 | 29/04 | More NP-complete problems                                      |           |   |   |                       |
|     |       | ** Algorithms **                                               |           |   |   |                       |
|  16 | 04/05 | Introduction and representative problems                       |           |   |   |                       |
|  17 | 06/05 | Basics of algorithm analysis                                   |           |   |   |                       |
|  18 | 11/05 | Basics of algorithm analysis                                   |           |   |   |                       |
|  19 | 13/05 | Graph algorithms                                               |           |   |   |                       |
|  20 | 18/05 | Graph algorithms                                               |           |   |   |                       |
|  21 | 20/05 | Graph algorithms                                               |           |  {{q0120151.pdf|E1}}  |  {{sq0120151.pdf|S1}}  |                       |
|  22 | 25/05 | Greedy algorithms                                              |           |   |   |                       |
|  23 | 27/05 | Greedy algorithms                                              |           |   |   |                       |
|  24 | 01/06 | Greedy algorithms                                              |           |   |   |                       |
|  25 | 03/06 | Divide-and-conquer                                             |           |   |   |                       | **Prazo lista 1** |
|     | 08/06 | //Sem aula//                                                   |           |   |   |                       |
|     | 10/06 | //Sem aula//                                                   |           |   |   |                       |
|     | 15/06 | //Sem aula//                                                   |           |  {{q0220151.pdf|E2}}  |  {{sq0220151.pdf|S2}}  |   |
|  26 | 17/06 | Divide-and-conquer                                             |           |   |   |                       |
|  27 | 22/06 | Divide-and-conquer                                             |           |   |   |                       |
|  28 | 24/06 | Dynamic programming                                            |           |  {{q0320151.pdf|E3}}  |  {{sq0320151.pdf|S3}}  |   | **Prazo lista 2** |
|  29 | 29/06 | Dynamic programming                                            |           |   |   |                       |
|  30 | 01/07 | Dynamic programming                                            |           |   |   |                       | **Prazo lista 3** |
|     | 06/07 | Prova de recuperação.                                          |           |   |   |                       |
|     |       |                                                                |           |   |   |                       |
|     | 11/07 | Término oficial das aulas.                                     |           |   |   |                       |

==== Evaluation ====

See the [[http://ppgc.inf.ufrgs.br/index.php?option=com_content&view=category&layout=blog&id=171&disc=106|homepage of the course at PPGC]].

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