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:30pm Venue: SR2, Education Resource Centre, University Town Map//goo.gl/maps/2Zy3M Free 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

Melvin is a programmer at Hoiio and the maintainer of Magarena, an open source card game with a challenging AI opponent. Melvin received his B.Comp (Hons) and Ph.D. degrees from NUS School of Computing.
comments powered by Disqus