Department of Mathematics FAS Harvard University One Oxford Street Cambridge MA 02138 USA Tel: (617) 495-2171 Fax: (617) 495-5132

Math table October 30, 2018

Shyam Narayanan, Harvard Undergraduate, will give a talk titled:
Divide and Conquer and 1-Center Clustering
Abstract: Divide and Conquer is a common technique in theoretical computer science and has many cool applications! I'll begin by talking briefly about algorithms and the divide and conquer technique, and will explain how this technique can be used for the well-known Merge Sort algorithm. I'll finally explain the 1-Center Clustering with Outliers problem and show how one can get a linear-time algorithm for it using divide and conquer techniques.
Prerequisites: Familiarity with the idea of an algorithm and big-O notation.