Algorithmics, Computability and Complexity (ALCC)

Upon finishing this subject, students should have an understanding of the basic elements of Theory of Computation, including Automata and Formal Language Theory, Computability Theory, Complexity Theory and Algorithmics. Students gain the understanding and the experience needed to be able to classify problems. Problems are classified according to the existence or absence of algorithms for solving them, and, in the case of the latter, based on the possibility of finding an efficient alfgorithmic solution.

Knowledges

1. Understand some abstract models of classic calculation and their scope and limitations.
2. Know how to classify problems by classes of complexity as defined by various calculation models. In particular, understanding what negative results mean (irregularity, intractability, undecidability).
3. Understand the concept of problem reduction, and its use in demonstrating whether or not a problem is tractable.
4. Learn how to analyze an algorithm"s cost and a problem"s computational complexity. Understand the qualitative difference between polynomic time and exponential time.
5. Learn the computational problems for which no polynomic algorithms are currently available.
6. Learn some of the algorithmic techniques for tackling difficult problems; in particular, complete NP problems.
7. Understanding the use of logical-mathematical notation to represent computational problems and calculation models.

Abilities

Competences

1. Critical, logical-mathematical reasoning.
2. Ability to understand and build logical-mathematical constructions.
3. Ability to solve problems through the application of scientific and engineering methods.
4. Ability to apply mathematical knowledge and logic in solving problems.
5. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.
6. Ability to act independently: Know how to work on one"s own with just the bare minimum of knowledge and guidance.
7. Ability to effectively convey one"s ideas in writing.
8. Intellectual curiosity and openness.

The first half of each two-hour class covers theory and the second half is spent doing exercises. Moreover, there will be a continued evaluation which will consist of three exams (for parts I-III) undertaken during class time.

The subject has a continued evaluation system and a final exam. The continued evaluation consists of 3 tests made during the semester, while the final exam contains 4 parts.
If the grades of the tests are p1, p2, p3, and the grades of the problems of the final exam are f1, f2, f3, f4, then the global grade of the subject is

max(p1,f1) + max(p2,f2) + max(p3,f3) + f4

The four values of the previous summation respectively correspond to the four parts in which the subject is divided. Parts I-III contribute with 3 points each, while part IV contributes with 1 point.

The tests will take place at usual classroom hours, shortly after finishing the topics they include. They will be announced at Racó at the beginning of the course.

• Michael Sipser Introduction to the theory of computation, Thomson Course Technology, 2006.
• G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.
• Maria Serna ... [et al.] Els Límits de la computació : indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.

• Efim Kinber, Carl Smith Theory of computing : a gentle introduction, Prentice-Hall, 2001.
• Christos H. Papadimitriou Computational complexity, Addison-Wesley, 1994.
• Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
• Ian Parberry Problems on algorithms, Prentice Hall, 1995.
• Rafel Cases, Lluís Màrquez Llenguatges, gramàtiques i autòmats : curs bàsic, Edicions UPC, 2003.

Programming knowledge and data structures.
Familiarity with logico-mathematical reasoning.