Insegnamento a.a. 2019-2020

Theoretical topics:

• Introduction to the notion of algorithms in Computing (Turing Machines, Church Thesis).
• Analyzing algorithms, growth functions and asymptotic notation (introduce elementary data structures).
• Recurrences and generating functions. Case study: Divide-and-Conquer algorithms.
• Probabilistic Analysis and Randomized Algorithms. Case study: Quicksort.
• Elementary Data Structures.
• Algorithms for Matrix Operations (inversions, eigensystems, page rank).
• Introduction to graph theory and Elementary Graph Algorithms (Minimum Spanning Trees, Single-Source Shortest Paths, Dijkstra's algorithm and Karger's randomized algorithm for the Minimum Cut problem).
• Introduction to computational complexity and NP-completeness.

Programming topics:

1. First part: introduction to programming; introduction to Python; elementary data structures and control flow constructs; basic algorithms; basic programming techniques.
2. Second part: more advanced data structures; introduction to object-oriented programming - classes and methods; pseudo-random numbers.

• State the basic axioms of the theory of computation and explain the theory of computational complexity.
• Analyze elementary algorithms and recurrences.
• Illustrate the role of different data structures for efficient computations.
• Master the basic notions of graph theory and related algorithms.

• Read/write Python codes and use the Anaconda  development environment.
• Develop basic codes for algorithmic problem solving.

• Face-to-face lectures
• Exercises (exercises, database, software etc.)

Exercises consist in programming assignments to be done in class under the supervision of the Instructor and Teaching Assistants.

• The exam consists of a theory part and a programming part, separated in two distinct phases.
  • The theory part consist in exercises and questions to be answered on paper, and is used to asses the "knowledge and understanding" learning   objectives. This contributes to 50% of the final grade.
  • The programming part consists in programming exercises to be performed at the PC in the computer room. It is used to asses the "applying knowledge and understanding" learning   objectives. This contributes to the remaining 50% of the final grade.
• The exam is not open-book: any material outside of what is provided by the instructors is forbidden.
• In order to pass the exam, students must achieve a passing grade in both parts individually.

Adopted textbooks:

• T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, et al., Introduction to Algorithms, MIT, 3rd edition.
• A.B. DOWNEY, Think Python, O’Reilly Media, 2dn edition (http://greenteapress.com/wp/think-python-2e/).
• C. MOORE, S. MERTENS, The Nature of Computation, Oxford (optional).

Handouts of each lecture and sample codes are provided.