Direction Optimizing Breadth-First Search: To optimize breadth first search on large graphs, we implemented a hybrid approach which uses conventional top-down approach with the novel bottom-up approach. Initially during the top-down phase, nodes in the active frontier(queue) searches for a non-visited child while during the new bottom-up approach, the non-visited children look for a parent in active frontier. This hybrid approach reduces the number of edges to be examined and thus provides the required speedup. Technology Used: C++ and OpenMP
Fault Tolerance in wireless adhoc network: In this Project, we started with finding out the cut-nodes in the given graph, which are also single point of failure because they are the only nodes to connect two disjoint parts of the graphs. Now to make the system fault tolerant, we used the concept of bi-connectivity in which we found some neighboring nodes which can be moved (removable nodes) and by moving these removable nodes to the cut-nodes and making them replica of the cut-nodes (having same connections/edges as cut-nodes). Thus, the system becomes bi-connected means there is no single point of failure thus have more fault tolerance. Technology Used: C++
Travelling Salesman Problem - Branch and Bound(TSP): Implemented different versions of TSP – branch and bound algorithm. General travelling salesman problem is NP-complete so there is no polynomial time algorithm available for TSP. As the number of cities increases in the problem, the execution time shoot up exponentially so we wanted to control the execution time using branch and bound concept. For each node, we calculate the least cost that will be acquired expanding it and if it is greater than the minimal cost found so far, then we will prune that branch. Three different version of this approach were implemented, sequential version, parallel version with pthread library and at last distributed version with openMPI. Technology used: C++, pthread and OpenMPI
Kakurasu: Japanese puzzle solver: Implemented the solver for Japanese puzzle Kakurasu. First step of solver, where we implemented arc consistency to reduce the domains of each variable by removing all the non-essential domain values. In second phase, we implemented Search-tree minimization(STM) heuristic for variable ordering and as the last step we used backtracking search algorithm with Arc consistency. In an another approach the same problem was solved using the simulated annealing approach and Hastings-Metropolis algorithm. Technology Used: C++