The goal of this course is to present the power and the variety of randomized algorithms and to deep into the probabilistic analysis of algorithms.
A randomized algorithm is an algorithm that makes random choices as part of its logic. Probabilistic analysis of algorithms estimates the computational complexity of algorithms or problem assuming some probabilistic distribution of the set of all possible inputs.
The course has two main themes. The first theme presents basic tools and techniques from probability theory and probabilistic analysis that are recurrent in algorithmic applications. The second theme deals with specific areas of application. Tools and techniques will be interleaved with applications that illustrate them in concrete settings.
Person in charge
Maria Jose Serna Iglesias (
Technical Competences of each Specialization
CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes.
CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.
Generic Technical Competences
CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.
CG5 - Capability to apply innovative solutions and make progress in the knowledge to exploit the new paradigms of computing, particularly in distributed environments.
CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.
CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
Become acquainted with the main techniques and problems of randomization
Examine conditions under which randomized algorithms can be used. Perform an analysis and extract the fundamental properties, from different domains, to assess the suitability and applicability of randomized methods.
Motivating examples; random algorithms; probabilistic analysis; Monte Carlo algorithms, Las Vegas algorithms.
Probabilistic tools and techniques
Events and probabilities; random variables and expectations; moments and deviations; tail inequalities; balls and bins and random graphs; Markov chains and random walks.
Sorting and searching
Randomized quick sort; randomized quick select; randomized selection by sampling.
Hashing; universal hashing, cuckoo hashing, bloom filters.
There will be two kinds of classes: theoretical sessions and practical sessions. On average, two hours a week is dedicated to theory and one hour a week to exercises. The teacher will allocate the hours in accordance with the subject matter.
The theory classes take the form of lectures in which the teacher sets out new concepts or techniques and examples illustrating them.
The practical classes are used to carry out exercises in which students take an active part. Teachers set the exercises in advance. Students are required to submit the exercises and then discuss the various solutions/alternatives in class.
C1 , C2, C3 = Graded in-class assignments. Each one is graded from 0 to 10.
LW = Lab assignment (graded from 0 to 10) in which each participant is required to present a program that implements a randomized algorithm to solve a problem taken from a research paper or a section of a book (previously assigned by the lecturer). The presentation consists of:
3-5 minutes background on the topic of the paper, a motivation.
1 minute overview of the key ideas of the algorithmic solution.
10 minutes presentation with most important details.
5 minutes demo of a program that implements the ideas introduced in the paper.
FT = Final test graded from (0 to 10) including all the contents of RA.
Probability and computing: randomization and probabilistic techniques in algorithms and data analysis -
Mitzenmacher, M.; Upfal, E,
Cambridge University Press, 2017. ISBN: 9781107154889 http://cataleg.upc.edu/record=b1494392~S1*cat
There are no modifications to the contents of the teaching guide.
No hi ha modificacions respecte als continguts de la guia docent.
No hay modificaciones respecto a los contenidos de la guía docente.
There are no modifications to the methodology given in the teaching guide. The on-line classes will be complemented with voluntary activities that encourage participation in these classes and the assimilation of the topics of the course.
No hi ha modificacions respecte a la metodologia de la guia docent. Les classes de teoria no presencial es complementaran amb activitats voluntàries que fomentin la participació en aquestes classes i l'assimilació dels continguts de l'assignatura.
No hay modificaciones respecto a la metodología de la guía docente. Las clases no presenciales se complementarán con actividades voluntarias que fomenten la participación en estas clases y la asimilación de los contenidos de la asignatura.
There are no modifications to the evaluation method.
No hi ha modificacions al mètode d'avaluació.
No hay modificaciones al método de evaluación.
In case of cancellation of the face-to-face teaching, the classes will continue on-line, in the same schedule, and they will be reinforced with communication tools that allow to maintain contact between students and between students and teachers in an agile way.
The exams will be held in person, with delivery through the Racó and/or Atenea
En cas de cancel·lació de tota activitat lectiva presencial les classes es continuaran de forma no presencial en el mateix horari i és reforçaran amb eines de comunicació que permetin mantenir el contacte entre els estudiants i entre estudiants i professors de forma àgil.
Els exàmens i controls es realitzaran de forma no presencial, amb entrega a través del Racó i/o d'Atenea.
En caso de cancelación de toda actividad lectiva presencial las clases continuarán de forma no presencial en el mismo horario y se reforzarán con herramientas de comunicación que permitan mantener el contacto entre los estudiantes y entre estudiantes y profesores de forma ágil.
Los exámenes se realizarán de forma no presencial, con entrega a través del Racó y/o de Atenea.
Where we are
B6 Building Campus Nord
C/Jordi Girona Salgado,1-3
08034 BARCELONA Spain
Tel: (+34) 93 401 70 00