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. At various junctures throughout the course, students will be given assignments to do during their personal study periods. The time scale for submissions will typically cover a few days.

The subject has a continued evaluation system and a final exam. The continued evaluation consists of k tests (3 <= k <= 10) made during the semester, while the final exam contains k problems, each of which has the same weight than the corresponding test. If the grades of the tests are c_1, ..., c_k and the grades of the problems of the final exam are f_1, ..., f_k, then the global grade of the subject is

max(c_1,f_1) + ... + max(c_k,f_k).

Each test of the continued evaluation (and the corresponding problem of the final exam) evaluates one or two topics, and its weight is the sum of the weights of the topics it contains. The weights of each topic can vary between 0.5 and 1.5, and their exact values will be announced at the Racó at the beginning of the course.

The tests will be made at the classroom during the exercises hour, will take place shortly after finishing the topic (or topics) they include, and will be announced at Racó at least one day before.

• Sipser, M. Introduction to the Theory of Computation, PWS, 1997.
• Brassard, G. i Bratley, P. Fundamentos de Algoritmia, Prentice Hall, 1997.
• Serna, M, Àlvarez, C., Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Cormen, T.H., Leiserson C.E., Rivest, R.L. i Stein, C. Introduction to Algorithms, second edition, MIT i McGraw-Hill, 2001.

• Kinber, E. i Smith, C. Theory of Computing. A Gentle Introduction., Prentice Hall, 2001.
• Papadimitriou, C. Computational Complexity, Addison Wesley, 1994.
• Garey, M. i Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1978.
• Parberry I., Gasarch W. Problems on Algorithms (2nd edition), http://hercule.csci.unt.edu/ian/books/free/, 2002.
• Cases, R. i Màrquez, L. Llenguatges, gramàtiques i autòmats, Edicions UPC, 2000.

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