PhD (Rutgers University)
Research Interests: Design And Analysis Of Algorithms For Problems With Applications In Bioinformatics/Computational Biology, Combinatorial Optimization and Data Sciences.
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.
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 = (a1, a2, …, an) of items, where for i in [1..n] 0 <= si <= C denotes the size of item ai, 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(l2(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 nO(k2) time approach for solving the 1-dimensional cutting stock problem, which is a constrained counterpart of the bin packing problem.
S. Divakaran, A Fast Scalable Heuristic for Bin Packing. CoRR abs/1904.12467, DOI: 10.13140/RG.2.2.12887.52643 (2019)
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