Course Identification

Title:

Seminar on Algorithms and Geometry

Code:

20144182

Lecturers and Teaching Assistants

Lecturers:

Prof. Robert Krauthgamer

TA's:

N/A

Course Schedule and Location

Year:

2014

Semester:

Second Semester

When / Where:

Wednesday, 16:15 - 18:00, Ziskind, Rm 1

First Lecture:

12/03/2014

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Elective; 2.00 points

Comments

N/A

Prerequisites

Basic knowledge of algorithms, at an undergraduate level, is required, and familiarity with Euclidean geometry, probability theory, and linear algebra may be necessary.

Restrictions

Participants:

No

Language of Instruction

English

Registration by

Registration By:15/04/2014

Attendance and participation

Obligatory

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

Attendance

50%

Assignments:

50%

Evaluation Type

Scheduled date 1

Date / due date

N/A

Location

N/A

Time

-

Remarks

N/A

Estimated Weekly Independent Workload (in hours)

2

Syllabus

This seminar will cover recent algorithmic topics that involve geometric concepts and techniques, including algorithms for nearest neighbor search, dimensionality reduction, traveling salesman problem, metric embeddings, metric decompositions, and their applications to combinatorial algorithms such as approximation algorithms for graph partitioning.

Learning Outcomes

Upon successful completion of this course students should be able to:
[1] Define and use basic concepts involving metrics spaces
[2] Identify and solve basic problems in metric problems
[3] Recognize standard tools in metric embeddings and apply them to optimization problems

Reading List

N/A

Website

N/A