Randomized Algorithms

Credits
6
Types
  • MIRI: Specialization compulsory (Advanced Computing)
  • MEI: Elective
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Web
http://www.cs.upc.edu/~conrado/docencia/ra-miri.html
Mail
conrado@cs.upc.edu
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.

Teachers

Person in charge

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0.32
Autonomous learning
9.325

Competences

Technical Competences of each Specialization

Advanced computing

  • 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

    Generic

  • 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.

    • Transversal Competences

    Reasoning

  • 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.

    • Basic

  • 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.

    • Objectives

    1. Become acquainted with the main techniques and problems of randomization
      Related competences: CG1, CEE3.1, CEE3.2, CTR6,
    2. 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.
      Related competences: CG3, CB6, CTR6, CG5,

    Contents

    1. Introduction
      Motivating examples; random algorithms; probabilistic analysis; Monte Carlo algorithms, Las Vegas algorithms.
    2. 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.
    3. Sorting and searching
      Randomized quick sort; randomized quick select; randomized selection by sampling.
    4. Data structures
      Hashing; universal hashing, cuckoo hashing, Bloom filters.
    5. Algebraic techniques
      Fingerprinting; database consistency; pattern matching; primality testing.
    6. Optimization, approximation, sampling and counting

    Activities

    Activity Evaluation act


    Development of the topics in the syllabus (I)

    Development of syllabus topics and practice exercices.
    Objectives: 1 2
    Contents:
    Theory
    10h
    Problems
    10h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    25h

    Mid-term exam


    Objectives: 1 2
    Week: 7
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Theory and exercises of the syllabus (II)



    Theory
    10h
    Problems
    10h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    25h

    Lab assignment

    Design, implementation and documentation of a practical work on one of the topics developed in the subject

    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    20h

    Oral presentations (I)

    Oral presentation of an academic paper or some specific topic related to the course

    Week: 14 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Oral presentations (II)



    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final exam


    Objectives: 1 2
    Week: 16
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    There will be two kinds of classes: theoretical sessions and practical sessions. On average, two hours per week is dedicated to theory and two hours per 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 will propose exercises in advance. Students are required to submit the exercises and then discuss the various solutions/alternatives in class.

    Evaluation methodology

    Grade = 0.7 E + 0.3 OP

    P = Mid-term exam (graded between 0 and 10)
    F = Final exam (graded between 0 and 10)
    E = max(0.4 P + 0.6 F, F)
    OP = Oral presentation of a specific article or topic related to the course, together with a written summary and the audiovisual material of the presentation (rated between 0 and 10); the articles and / or topics will be chosen by the student from among the proposals made by the teacher

    Bibliography

    Basic

    Complementary

    Previous capacities

    - Basic knowledge of algorithms and data structures: sorting algorithms, graph algorithms, binary search trees, hash tables, analysis of algorithm, notions of complexity, algorithmic schemes, ...

    Knowledge of at least one programming language, preferably C++ or Python.