Randomized Algorithms

You are here

Credits
6
Types
Specialization compulsory (Advanced Computing)
Requirements
This subject has not requirements

Department
CS
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

  • Jordi Petit Silvestre ( )

Others

  • Josep Diaz Cort ( )

Weekly hours

Theory
2
Problems
1
Laboratory
0
Guided learning
0
Autonomous learning
0

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.

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, 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, skip-lists
  5. Graph algorithms
    Minimal cuts; shortest paths; minimum spanning trees.
  6. Algebraic techniques
    Fingerprinting; database consistency; pattern matching; primality testing.
  7. Optimization, approximation and counting

Activities

Development of the topics in the sylabous.

Theory
30
Problems
15
Laboratory
0
Guided learning
0
Autonomous learning
45

Exposition of topics by the students.

Theory
0
Problems
1
Laboratory
0
Guided learning
7.5
Autonomous learning
7.5

Teaching methodology

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.

Evaluation methodology

Grade = 40% FW + 30% FT + 30% SP

FW = Final Work (graded from 0 to 10) in which each participant is required to present a research paper or section of a book (previously assigned by the lecturer). The presentation consists of:
3-5 minutes backround on the topic of the paper, a motivation.
1 minute overview of the key ideas of the paper.
15 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.

SP = Summaries and participation (graded from 0 to 10) in which each participant is required to deliver a summary (1 page extent) of anothers presentation and to participate in class (with questions, comments and solving problems in the blackboard).

Bibliografy

Basic: