# Friday Hacks #69, April 4

## Posted on by vishnu

This friday, we have a talk by Melvin from Hoiio about optimal algorithms. See you there!

Date/Time: Friday, April 4th at 6:30pmVenue: SR2, Education Resource Centre, University TownMap: //goo.gl/maps/2Zy3MFree pizza is served before the talks.

### Talk: Quest for the optimal algorithm

**Talk Description:**

Algorithm development is often a messy process, much of which never makes it into the publication. This talk goes behind the scenes and traces the ongoing development of ever more efficient algorithms for the Gene Team Tree problem. We will end with an open data structure problem needed for a faster algorithm and a collaborative problem solving session.

Pre-talk preparation tips or instructions: Below is the open data structure problem that we will be discussing.

Input is a list, P, of n points on the number line in increasing order, [p_1, p_2, …, p_n].

The gap between two adjacent points p_i and p_i+1 is the distance between them, i.e. p_i+1 - p_i.

The max gap of P is max (p_i+1 - p_i) for i from 1 to n-1.

Design a data structure for P that supports a single operation delete(p), which deletes point p from P and return the max gap of P. Assume we have a direct reference to the point p so there is no need to search for it. a) perform n deletions in O(n lg n) time (solved) b) perform n deletions in O(n) time (open)

**Speaker Profile**

#### Supported by:

The HANGAR by NUS Enterprise — the campus hub for entrepreneurs.