• Competitive Coding

• Developing a library for graph optimization algorithms

Mentors :

• Ameya Vikram Singh

• Prerak Contractor

• Anish Yogesh Kulkarni

Mentees :

• 9

Fast Algorithms for Searching Through Graphs Optimization is everywhere! From google maps, machine learning, airplane scheduling, network routing, to search and rescue, and even in war. Almost every problem in the world involves determining an optimal solution among all available options. The project will target a wide variety of such optimization problems, and implement a general purpose library with a huge toolbox of optimization algorithms. There will be a significant theory component, so that the problems can be modelled mathematically in terms of optimizing a cost function over some set, typically some graph (network). The mentees will build a robust, modular high-performance library for optimization using OO programming, in C++. We will look at Shortest Paths, Spanning Trees, Perfect Matching, Network Flow and advanced problems like the Travelling Salesman. We will employ heuristics like Greedy approach, Dynamic Programming, Linear Programming, etc. Some standard algorithms including Dijkstra, A* search, Floyd-Warshall (Paths), FFA, Edmonds-Karp and Dinic (Flows), Hungarian method and Blossom-Shrinking (Matching) will be implemented and contrasted. Depending on the timeline, we might also cover Randomized Algorithms and Approximation Algorithms for NP-Hard Problems (TSP). No former knowledge of any of these algorithms is expected, only enthusiasm to learn, understand and implement! Further, no advanced programming knowledge is required. Reference (theory): Combinatorial Optimization, Korte and Vygen (this is just a secondary reference, resources for studying specific algorithms will be shared along the project, but implementation will be from scratch)
There is no requirement for prior Deep Learning experience, however it would be helpful if you did. Some familiarity with python and image classification is expected but you can catch up quickly without that too if you are motivated enough. In your proposal, indicate your readiness to devote time to this project. If you have any previous coding (Python) or machine learning or deep learning skills, be sure to highlight that. Prequisites: No prereqs, except basic C++ programming, and enthusiasm of course! Knowing C++ OOP (Classes, Friends, Inheritance) will be good-to-have, though can be picked up easily.