Course Identification

Randomized Algorithms
20134151

Lecturers and Teaching Assistants

Prof. Robert Krauthgamer, Prof. Moni Naor
Gilad Tsur

Course Schedule and Location

2013
First Semester
Sunday, 14:00 - 17:00, Ziskind, Rm 1
04/11/2012

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Elective; 3.00 points
Life Sciences (Systems Biology Track): Computer Sciences & Mathematics; 3.00 points
Mathematics and Computer Science (Systems Biology / Bioinformatics): Computer Sciences & Mathematics; 3.00 points

Comments

N/A

Prerequisites

Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level.

Restrictions

No

Language of Instruction

English

Registration by

01/01/2013

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

50%
50%

Evaluation Type

Examination

Scheduled date 1

17/02/2013
FGS, Rm B
1000-1330
N/A

Scheduled date 2

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

2

Syllabus

Algorithms that are randomized, i.e. use coin tosses during their execution, are central in many computational scenarios, and have become a key tool in Theoretical Computer Science and in application areas. The course will cover the development and use of such probabilistic techniques, including some of the following topics: Concentration results; Simulating randomness, in particular limited independence; Load balancing; Routing algorithms; Randomized rounding; Sampling and sublinear algorithms; Algorithms in the data stream model; Communication protocols and the sketching model.

Learning Outcomes

Upon successful completion of this course students should be able to:

[1] Analyze probabilistic events and randomized processes.

[2] Design algorithms that use randomness, and analyze their performance.

[3] Make use of basic tools such as first and second moment, concentration bounds, balls and bins, birthday paradox.

[4] Describe and apply algorithmic paradigms that rely on randomness like hashing, sampling, sketching, and streaming.

Reading List

N/A

Website