Neeraj Sharma

Currently working as Senior computer scientist with 10+ years of experience in C/C++. Good understanding of D.S. Algorithms and enjoy working in a team environment.

• Brief announcement: efficient cache oblivious algorithms for randomized divide and-conquer on the multi core model.
• Publication date. Jun 25, 2012
• SPAA '12: Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures
• Description : In this paper we present a cache-oblivious framework for randomized divide and conquer algorithms on the multi core model with private cache. We first derive an O(n/p log n + log n log log n) expected parallel depth algorithm for sorting n numbers with expected O(n/B logM n) cache misses where p,M and B respectively denote the number of processors, the size of an individual cache memory and the block size respectively. Although similar results have been obtained recently for sorting, we feel that our approach is simpler and general and we apply it to obtain an algorithm for 3D convex hulls with similar bounds.
• We also present a simple randomized processor allocation technique without the explicit knowledge of the number of processors that is likely to find additional applications in resource oblivious environments.