
Course unit
COMPUTABILITY AND ALGORITHMS
SCN1037673, A.A. 2015/16
Information concerning the students who enrolled in A.Y. 2015/16
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Core courses 
INF/01 
Computer Science 
10.0 
Course unit organization
Period 
Second semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Practice 
2.0 
16 
34.0 
No turn 
Lecture 
8.0 
64 
136.0 
No turn 
Examination board
Examination board not defined
Prerequisites:

The course requires some familiarity with basic mathematical concepts such as relations, functions, sets, cardinality, partial orders, principles of induction.
There are no propaedeutical courses. 
Target skills and knowledge:

The aim of the course is to guide the student into some classic themes in the theory of computability and to complete and deepen the algorithmic knowledge acquired at undergraduate level. For the first part, starting from a mathematical analyisis of the intuitive concept of an effective procedure, the class of effectively computable functions is formally introduced, and a theory of undecidability and recursion is developed. For the second part, some algorithmic techniques are presented, for the elaboration of fundamental structures such as graphs, strings and geometric objects. Also multithreaded and randomized algorithms are discussed. More generally, the course is intended to improve the formalization, reasoning and problem solving skills of the student. 
Examination methods:

The exam consists of a written test, mainly focused on exercises concerning the theory of computability, and in an oral discussion focussed on algorithmic themes. 
Assessment criteria:

The written test contains exercises designed to test the student's ability to use concepts and proof techniques, learnt during the course, for the solution of new problems. The oral test verifies the acquired knowledge and the depth of understanding of the topics discussed during the lessons, by requiring the presentation of known concepts and proofs. 
Course unit contents:

The course is divided into two parts, the first focused on computability theory, and the second devoted to algorithmic themes.
As regards the theory of computability, the following topics will be developed:
 Algorithms and the concept of effective procedure. Register machines (URM). Partial recursive functions. Equivalences between computational models. Universality of computational models. Church's thesis.
 Enumeration of computable functions. Existence of noncomputable functions: diagonalization techniques. The parameter theorem. Universal programs.
 Decidable, undecidable and semidecidable problems. Undecidability of the halting problem. Reduction techniques. Other undecidable problems.
 Recursive and recursively enumerable sets. Rice and RiceShapiro theorems.
 Functionals. Recursive definitions. Partial orderings, monotone functions and fixed points. Recursive functional. MyhillSheperdson's theorem. First recursion theorem. Second recursion theorem.
The deepening of algorithmic techniques will focus on:
 Graph algorithms. Breadthfirst and depthfirst visit. Topological sort. Strongly connected components.
 String algorithms. Comparison based algorithms (Knuth, Morris and Pratt, Boyer, Moore and Yao, Corasich). Semi numerical algorithms (ShiftAnd and Fingerprint Rabin Karp). Suffix trees and Ukonnen algorithm for their construction in linear time.
 Multithreaded Algorithms.
 Computational Geometry. Representation of geometric objects and fundamental algorithms. Nonintersection test between segments. Convex hull: Graham algorithm and Jarvis algorithm. Finding the poligonal region that contains a given point.
 Randomized algorithms. Rendering algorithm. Routing algorithm. 
Planned learning activities and teaching methods:

The course consists of lectures and exercises. 
Additional notes about suggested reading:

Web page for computability theory: http://www.math.unipd.it/~baldan/Computabilita
Material for the algorithm part:
http://www.math.unipd.it/~colussi/CompAlgoritmi_201415 
Textbooks (and optional supplementary readings) 

Nigel Cutland, Computability. An Introduction to Recursive Function Theory. : Cambridge University Press, 1980. Testo per la parte di computabilità.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati (3a edizione). : McGrawHill Italia, 2010.


