Algorithms and Data Structures Ii
A.Y. 2018/2019
Learning objectives
Algorithm design and analysis is a fundamental part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications. We will focus on four main themes: computational complexity, string-matching algorithms, linear programming, and randomized algorithms.
Expected learning outcomes
Undefined
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Milan
Responsible
Lesson period
Second semester
Course syllabus
1. String matching
The Rabin-Karp algorithm
Algorithms based on automata
The Knuth-Morris-Pratt algorithm
Suffix trees
2. Computational complexity
Polynomial reducibility between decision problems
The P and NP classes
NP-completeness
3. Probabilistic algorithms
Montecarlo e Las Vegas algorithms
Karger algorithm for MinCut
The probabilistic complexity classes
The von Neumann extractor
The coupon collector problem
Reservoir sampling
Universal hashing
Approximate counting
Random projections
4. Linear programming
The standard form
Duality
The ellipsoid method
MaxFlow and MinCut
von Neumann Minimax theorem
The Rabin-Karp algorithm
Algorithms based on automata
The Knuth-Morris-Pratt algorithm
Suffix trees
2. Computational complexity
Polynomial reducibility between decision problems
The P and NP classes
NP-completeness
3. Probabilistic algorithms
Montecarlo e Las Vegas algorithms
Karger algorithm for MinCut
The probabilistic complexity classes
The von Neumann extractor
The coupon collector problem
Reservoir sampling
Universal hashing
Approximate counting
Random projections
4. Linear programming
The standard form
Duality
The ellipsoid method
MaxFlow and MinCut
von Neumann Minimax theorem
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cesa Bianchi Nicolo' Antonio
Professor(s)