MO417 - Complexity of Algorithms I - 2s2019

• Teacher: Rafael CS Schouery
  • rafael@ic.unicamp.br
  • Room 74 - Institute of Computing
• classrooms: Tuesdays and Thursdays at 16pm - Room 351 (IC3.5)
• Project Manager:
  • Fridays at 15pm, Room 28 (IC2) change!
  • Wednesdays at 13 pm, Room 28 (IC2) change!
• Notes and Frequency Worksheet
• Discipline Development Plan

Tests

• 6 test: Minimum path, Minimum Generating Tree, Reductions and NP-Completude - 28/11 - download
• 5 test: Graphs and Search - 14/11
• 4 test: Dynamic Programming and Greedy Algorithms - 31/10
• 3 test: Sorting, Quicksort, Linear Time Sorting and Order Statistics - 10/10
• 2 test: Correction of Algorithms and Design of Algorithms by Induction - 19/09
• 1 test: Complexity analysis of simple algorithms, asymptotic notation and recurrences - 29/08

Exercise Lists (for study)

• List 1
• List 2
• List 3
• List 4
• List 5
• List 6
• List 7
• List 8
• List 9
• List 10
• List 11
• List 12

Class Material

• 16 - NP-Completeness (handouts)
• 15 - Reduction (handouts)
• 14 - Minimum Path (handouts)
• 13 - Minimum Generating Tree (handouts)
• 12 - Graph Search (handouts)
• 11 - Graphs (handouts)
• 10 - Greedy Algorithms (handouts)
• 09 - Dynamic Programming (handouts)
• 08 - Order Statistics (handouts)
• 07 - Sorting in linear time (handouts)
• 06 - Quicksort (handouts)
• 05 - Ordering (handouts)
• 04 - Induction Algorithms Project (handouts)
• 03 - Correction of Algorithms (handouts)
• 02 - Complexity (handouts)
• 01 - Introduction (handouts)

Calendar

• Start: 01/08
• There will be no class on 06/08, 08/08 and 05/09, 07/11

Menus

• Computing models and tools / notation for analysis of algorithms.
• Mathematical induction and algorithm design.
• Greedy algorithms.
• Dynamic programming.
• Division and conquest.
• Algorithms for sorting and selection.
• Algorithms for basic graph problems.
• Reductions and NP-completeness.

REFERENCES

Recommended reading:

• Cormen, Leiserson, Rivest and Stein. Introduction to Algorithms, second edition, MIT Press, 2001.
  • It is possible to follow the course with the third edition as well
  • Avoid, if possible, the translated versions of the second edition

Official bibliography:

• Cormen, Leiserson and Rivest. Introduction to Algorithms, MIT Press, 1990.
• U. Manber. Introduction to Algorithms. Addison Wesley, 1989.
• Brassard and Bratley. Algorithms. Prentice Hall, 1996.
• Garey and Johnson. Computers and Intractability. Freeman, 1982.