Course 2017-2018 a.y.

Classes: 25 (II sem.)

Instructors:
Class 25: RICCARDO ZECCHINA

Quantitative data analysis of complex systems in economics and social sciences require a multidisciplinary methodological training. Computer science, especially its algorithmic aspects, constitutes one of the fundamental building blocks of such preparation.
The aim of the course is to provide students with the essential mathematical tools that are the basis of the theory of algorithms, along with a general introduction to the different classes of algorithms and data structures, and to the theory of computational complexity.
As part of the course, students are introduced to programming, starting from the basics and leading up to the implementation of data structures and algorithms discussed in the theoretical part of the course. The programming language used is Python, especially suited for a general understanding of programming techniques.

• Introduction to the notion of algorithms in Computing.
• Analyzing algorithms, growth functions and asymptotic notation.
• Recurrences and generating functions. Case study: Divide-and-Conquer algorithms.
• Probabilistic Analysis and Randomized Algorithms. Case study: Quicksort.
• Elementary Data Structures and Hash tables.
• 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.
• Introduction to programming. Python language.
• Implementation of data structures and algorithms.

• 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.
• C. Moore, S. Mertens, The Nature of Computation, Oxford (optional).
• Handouts.