ACM India Eminent Speaker Programme Lecture – SSN College

start: Sep 24, 2014 10:00AM
End: Sep 24, 2014 11:30AM

Venue: Mini Auditorium, SSN College of Engineering, Kalavakkam 603 110

Description: SSN-ACM student chapter are pleased to announce a talk by Prof. Madhavan Mukund, Professor and Dean of Studies, Chennai Mathematical Institute under the ACM India Eminent Speaker Programme.

Those who are interested in attending the talk, please register through the following link.

Date : 24th September 2014
Time: 10 – 11:30 AM
Topic: Efficient Processing of Range Queries


Here are two typical range query problems:

A hotel has rooms numbered 1 to N. As time goes by, some guests check in and others check out. Rooms may be occupied by more than one person at a time. Periodically you have to report the number of people staying in the rooms between room i and room j.

A painter applies paint to a fence made up of N fence posts, numbered 1 to N. In each stroke, he paints a segment from post i to post j. These paint strokes may overlap. After several such strokes, how many coats of paint have been applied to a given fence post k?

If we have U update operations interspersed with Q queries, naive solutions to these problems will take time proportional to QN and UN, respectively. We describe two elegant data structures, due to Bentley (1977) and Fenwick (1994), that allow these problems to be solved in time (U+Q) log N. If U, Q and N are comparable in size, this means that we bring down the complexity of answering range queries from N2 to N log N.

Madhavan Mukund studied at IIT Bombay (BTech) and Aarhus University (Ph.D.). He has been a faculty member at Chennai Mathematical Institute since 1992, where he is presently Professor and Dean of Studies. His main research area is formal verification. He has active collaborations within and outside India and regularly serves on international conference programme committees.

He is President of the Indian Association for Research in Computing Science (IARCS) and Vice President of the ACM India Council. He enjoys teaching. He has been the National Coordinator of the Indian Computing Olympiad since 2002 and was Executive Director of the International Olympiad in Informatics from 2011 to 2014.