Insegnamento a.a. 2020-2021

Introduction: Basic Notions and Theoretical Background

• Introduction, Turing Machines
• Stacks and Queues
• Array Resizing, Analysis of Algorithms, Asymptotic Notation, Exercises

Programming Paradigms and Data Structures

• Elementary Sorts
• Divide and Conquer, Mergesort
• Binary Heaps, Binary sort, Binary Queues
• Quicksort
• Binary Search Trees, Red-Black Trees
• Master Theorem, Exercises
• Hash Tables
• Shortest Path Algorithms
• Dynamic Programming
• Optimization Algorithms (Gradient Descent, SGD, Momentum, possibly expectation maximization)

Randomized Algorithms and Algorithms on Graphs

• Introduction to the Gibbs measure and its applications to study complex systems
• Computational complexity of estimating the Gibbs measure
• Markov Chain Monte Carlo: Basic definitions in discrete time
• Random walks in 2D and 3D
• Detailed balance and importance sampling
• Convergence
• Metropolis and heat-bath algorithms
• Applications to estimate the Gibbs measure in critical regimes
• Estimation of observables
• Elements of graph theory

• Understand the basic notions of algorithmic complexity, various design paradigms and data structures
• Develop an intuition about which problems are amenable to which kind of programming paradigm and relate this to common computational tasks like sorting and optimization
• Analyze the structure of advanced algorithmic schemes
• Illustrate the role of randomness in optimization.

• Design algorithms using paradigms like divide and conquer and predict their scaling in terms of memory and computational resources
• Describe algorithms (possibliy developed by the students themselves) in pseudocode
• Read literature on algorithm design
• Develop algorithms for large scale difficult optimization problerms

• Face-to-face lectures

Lectures.

The exam consists of a presentation and questions. The presentation can be either about a specific topic related to the course content, or about a project that the students complete before the exam. Several possible topics and projects will be proposed and students can also suggest also their own ideas. The questions will be about the presentation and related topics that were covered in class.

The exam will test the students' ability to explain algorithms using the concepts learned in class and connect these concepts to specific problem instances. It will further test if the student can describe the scaling properties of the presented algorithms in terms of the mathematical notions of complexity learned in class. Depending on the topic of the presentation, the abilities of the students in the design of algorithms will be assessed and the understanding of related topics from the course will be tested.

• T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, et al., Introduction to Algorithms, MIT, 3rd edition.
• R. SEDGEWICK., and K. WAYNE.  Algorithms. Addison-wesley professional, 4th Edition.
• C. MOORE, S. MERTENS, The Nature of Computation, Oxford.
• R. MOTWANI, P. RAGHAVAN, Randomized algorithms, Cambridge University Press New York, NY, USA
• Lecture notes by the instructors.