Srikrishnan Divakaran

Associate Professor

**PhD (Rutgers University)**

**+91.79.61911175**

**Research Interests:** Design And Analysis Of Algorithms For Problems With Applications In Bioinformatics/Computational Biology, Combinatorial Optimization and Data Sciences.

Profile

Dr. Srikrishnan Divakaran is a Theoretical Computer Scientist with over 25 years of experience in education and research, as well as over 5 years of industry experience in computing and finance with leading international companies. In 2002, Dr. Divakaran received his PhD from Rutgers University in New Brunswick, New Jersey. He then worked as an Assistant Professor in the Computer Science department at Hofstra University on Long Island, NY, from 2002 to 2008, and as an Associate Professor at DAIICT from 2009 to 2016, before becoming an Associate Professor at Ahmedabad University's School of Engineering and Applied Sciences.

Dr. Divakaran has taught a variety of courses in Computer Science and related disciplines such as *Applied Mathematics, Computational Biology/Bioinformatics and Data Sciences. *Dr. Divakaran’s research focuses on the *design and analysis of algorithms for problems with applications in Computational Biology/Bioinformatics, Combinatorial Optimization and Data Science*. Dr. Divakaran’s current research focus is mostly on the design and analysis of algorithms and heuristics for problems with applications in Data Science. Dr. Divakaran has also played a key role in designing (i) the Bioinformatics specialization as a part of Hofstra’s Master’s degree in Computer Science, (ii) the B.Tech (ICT) program with a specialization in Computational Sciences at DAIICT, and (iii) the B.S. Computer Science (Honors) program at Ahmedabad University. He has also (i) guided many undergraduate students in gaining a better understanding of research through summer internships and summer research projects; and (ii) mentored many groups of students for ACM programming competitions.

Research

Static List Update Problem: Given an ordered list ρ (an ordering among the items in L) and a request sequence σ, we need to determine how to reorganize L while serving σ so as to minimize the total servicing (access and list reorganization) cost.

This is a very hard problem that has been widely studied by theoretical computer scientists since 1980’s and has widespread applications in distributed systems in the context of designing paging and resource allocation algorithms.

__Bin Packing____:__ In this problem, my research was on the design of fast heuristics and approximation schemes for classical bin packing and its variants. The classical bin packing problem can be defined as follows:

*Given an infinite supply of bins with capacity C and a list L = (a _{1}, a_{2}, …, a_{n}) of items, where for i in [1..n] 0 <= s_{i }<= C denotes the size of item a_{i}, we need to pack the items into a minimum number of bins under the constraint that the sum of the sizes of the items in each bin is no greater than C. *

This problem has a wide variety of applications including cutting stock applications, packing problems in supply chain management, and resource allocation problems in distributed systems.

* Our Results*: As part of my PhD research, I began working on a project on scheduling with set-ups with Prof. Michael Saks. For the weighted completion time and maximum lateness criterion, we were able to get new approximation algorithms for the offline problem of scheduling a succession of jobs on a single machine with sequence independent set-up times. For this problem, our methods were the first known polynomial time constant approximation algorithms. With the goal of lowering the maximum flow time, we proposed an O(1)-competitive online algorithm for a problem with sequence independent set-ups and arbitrary job release times for the online problem. We also show how to prove that the associated offline problem is NP-complete.

For the static list update problem, I was able to characterize the list reorganizations in an optimal offline solution in terms of an initial list permutation followed by a sequence of m element transfers, where an element transfer is a type of list reorganization in which only the requested item can be moved. Then I used this characterization to create an offline method that is an O(l^{2}(l − 1)!m) time optimal offline algorithm.

For the bin packing problem, I devised a fast scalable heuristic that divides the given problem into similar sub-problems of constant size and solves these constant size sub-problems by evaluating just a fixed number of bin configurations with bounded unused space. My empirical investigation demonstrates the scalability of our heuristic as well as its tighter empirical analysis for difficult cases due to a better lower constraint on the required wastage in an optimal solution. I also published a n^{O(k2}) time approach for solving the 1-dimensional cutting stock problem, which is a constrained counterpart of the bin packing problem.

Publication

S. Divakaran. Explainable Algorithms for Image Registration with Applications in Medical Imaging, Explainable AI in Healthcare (xAI 2022) (under review), CRC Press, 2022.

S. Divakaran, Data Science: Principles and Concepts in Modeling Decision Trees, Data Science in Agriculture and Natural Resource Management, 55-74, Studies in Big Data, Springer, 2022.

S. Divakaran and M. Saks, An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times, Algorithmica 60(2): 301-315, 2011.

S. Divakaran, Approximation algorithms for constrained generalized tree alignment problem, Discrete Applied Mathematics 157(7): 1407-1422, 2009.

S. Divakaran and M. Saks, Approximation Algorithms for problems in Scheduling with set-ups, Discrete Applied Mathematics, Volume 156(5), 719-729, 2008.

S. Divakaran, Approximation Algorithms for problems in Scheduling with Set-ups, Graduate Dissertations, Rutgers, The State University of New Jersey, 2001, ISBN: 0-493-47085-9.

S. Divakaran and M. Saks, An Online Scheduling Problem with Job Set-ups, Center for Discrete Mathematics & Theoretical Computer Science, 2000-34.

__Conference and Workshop Articles__

Srishti Sharma, Srikrishnan Divakaran, Tolga Kaya and Mehul Raval. A Hybrid Approach for Interpretable Game Performance Prediction in Basketball, International Joint Conference on Neural Networks (IJCNN 2022), Padua, Italy, July 18-23, 2022.

M. Shah, M. Raval and S. Divakaran. A Deep Learning Perspective to Atmospheric Correction of Satellite Images, IEEEiGARSS 2022, Kuala Lumpur, Malaysia, July 17-22, 2022.

M. Shah, M. Raval and S. Divakaran. Deep Learning Based Emulator for 6S Atmospheric Correction Model, IEEE InGARSS 2021 (Virtual Symposium), December 6-10, 2021.

S. Divakaran. Introduction to Spatial and Temporal Data Analysis with R, Workshop on Data Science and Natural Resource Management (DSANRM2021), December 15, 2021.

S. Divakaran. Statistics of Sequence Analysis Using BLAST, Workshop on Application of Biostatistics in Biotechnology and Pharmaceutical Sciences, L.M. College of Pharmacy, October 21-23, 2021.

S. Divakaran, Data Clustering with Applications in Computational Biology, Big Data: Algorithms, Frameworks and Machine Learning Techniques for Problems in Evolving Networks and Computer Vision, Big Data Analytics 2019, December 17-20, 2019.

S. Divakaran, Algorithms for Exact String Matching, Learning in Data Science: Models, Algorithms and Tools, Summer School, July 17-22, 2017.

S.Divakaran, Fast Algorithms for Exact String Matching. Winter School of Combinatorics, Charles University, (Filed as CoRR abs/1509.09228), 2016.

S. Divakaran, An Approximation Algorithm for a Multi-dimensional Resource Allocation Problem, Proceedings of the 13^{th} International Conference on Combinatorial Optimization, CO2004, Lancaster, UK, pp 15, March 28-31, 2004.

S. Divakaran, A framework for Request Scheduling in Web Servers, Special Focus on Next Generation Networks Technologies and Applications, DIMACS, Piscataway, New Jersey, December, 2002.

S. Divakaran and M. Saks, Online Scheduling with release time and set-ups, Proceedings of the 12^{th} International Conference on Combinatorial Optimization, CO2002, CNAM Paris, pp 43, April 8-10, 2002.

S. Divakaran and M. Saks, Approximation Algorithms for Offline Scheduling with set-ups, Proceedings of the 12^{th} International Conference on Combinatorial Optimization, CO2002, CNAM Paris, pp 44, April 8-10, 2002.

M. Rangarajan, S. Divakaran, T. Nguyen and L. Iftode, Multi-threaded HLRC DSM, 1^{st} Workshop on Software Distributed Shared Memory, Rhodes, Greece, June 25, 1999.

S. Divakaran, A Fast Scalable Heuristic for Bin Packing. CoRR abs/1904.12467, DOI: 10.13140/RG.2.2.12887.52643 (2019)

S. Divakaran, Fast Approximation Schemes for Bin Packing. CoRR abs/1902.03422, DOI: 10.13140/RG.2.2.28815.64165 (2019)

S.Divakaran, A Fast Heuristic for Exact String Matching. CoRR abs/1512.03512 (2015)

S.Divakaran, Fast Algorithms for Exact String Matching. CoRR abs/1509.09228 (2015)

S. Divakaran, An Optimal Offline Algorithm for List Update. CoRR abs/1404.7638 (2014)

S. Divakaran, A Fast Template Based Heuristic For Global Multiple Sequence Alignment. CoRR abs/1302.6030 (2013)

S. Divakaran, Approximation Algorithms for Constrained Generalized Tree Alignment Problem, DIMACS Technical Report 2007-21.

S. Divakaran, Approximation Algorithms for a Multi-dimensional Resource Allocation Problem, DIMACS Technical Report 2006-24.

S. Divakaran and M. Saks, Online Scheduling with release time and set-ups, DIMACS Technical Report 2001-50.

S. Divakaran and M. Saks, Approximation Algorithms for Offline Scheduling with set-ups, DIMACS Technical Report 2001-49.

Teaching

**Teaching Statement of Srikrishnan Divakaran**

My goals in teaching are to help students develop the ability to solve problems, equip them with a good conceptual understanding along with practical problem solving skills. I address these goals by focusing on the following:

__Motivation__: I introduce a concept by motivating its usefulness by describing the key idea, its application context, and its strengths in comparison with other approaches.

__First Principles__: I have observed that many concepts in computing are simple at their core and can be extended in simple ways to yield powerful but simple ways for solving problems. So, I believe in explaining key concepts by first explaining the relevant first principles and then highlight some of the subtleties and challenges in putting them together. This helps in developing their intuition without getting bogged down by the technicalities.

__Illustration of Concepts__: I illustrate a concept by employing problems that range from direct applications to problems that involve subtle twists. I illustrate the use of techniques by first solving some simple instances of a problem. Then, I illustrate the power of a technique by comparing it with other alternate ways of solving problems. This helps the student to the computational complexity and challenges/limitations of the various ideas/techniques in different contexts

__Critical Thinking__: I believe that developing critical thinking is an essential part of learning. I believe that students should be taught to think through ideas and understand what the strengths and limitations of new ideas are, and how these ideas can be applied and extended? I attempt to provide this experience through carefully designed tutorials/ group projects that complement their lectures. In these tutorials, I assign some extensions of simple instances to small groups and initiate the discussion by giving hints, suggestions and raising questions. The objective of the group activities is to help them collaborate with one another and also critique each other’s ideas. This experience, although slow and frustrating has helped many of my students develop deeper intuition and greater rigor in writing their proofs.

**List of Courses Taught in the past 10 years**

__Theory__: Discrete Mathematics, Probability and Statistics, Advanced Statistics, Design and Analysis of Algorithms, Data Structures and Algorithms, Advanced Data Structures and Algorithms, Approximation Algorithms, Online Computation, and Combinatorial Optimization.

__Bioinformatics/Computational Biology__: Algorithms for Computational Biology, Statistical Methods for Bioinformatics.

__Data Science__: Foundations of Data Science, Elements of Statistical Learning.

__Others__: Operating Systems, Distributed Systems