##### Topics

The broad theme of the school is Algorithms. Algorithm Design is an important topic in the study of Computer Science and Information Technology. Every student of a degree program in any Computer Science related stream does a basic course in Algorithm Design and Analysis. The summer school expects to introduce advanced topics in Algorithm Design.

##### Approximation Algorithms (V N Muralidhara)
We give an introduction to Approximation Algorithms. The objective here is to design and analyse efficient algorithms that may not be optimum, but is very close to the optimum solution. The challenge is to design algorithms that give solutions which are close to the optimum, without knowing the optimum solution. We will discuss the approximation algorithms for vertex cover probelm, metric traveling sales man problem and the knapsack problem.

##### Exact Exponential Algorithms (Pradeesha Ashok)
Exact exponential algorithms deals with designing “good” exponential time algorithms for computational problems. It is believed that there exists some problems that cannot be solved in polynomial time. However, every combinatorial problem can be solved in exponential time using brute-force search. It is interesting to see if we can design an algorithm whose running time is better than those of the brute-force algorithm. For example, the Travelling Salesman Problem can be solved in time O(n!) time by using brute force. But can we design an algorithm that solves the Travelling Salesman Problem in O(cn) where c is a constant?
In this talk, we will discuss a few techniques for designing efficient Exact exponential algorithms.

Parameterised algorithms were introduced as a paradigm to cope with NP-hardness. Here the running time of the algorithm is measured not only as a function of the input size but also in terms of a parameter - a property of the input instance or solution. Moreover, the running time can be exponential in parameter but only polynomial in the input size. Thus a parameterised algorithm is efficient when the parameter is very small compared to the input size. In this talk, we will discuss known parameterised algorithms for some problems.

##### Introduction to Online Algorithms (Arindam Khan)
In online algorithms, we consider optimization problems where the input is received in an online manner (i.e., the input does not arrive as a single batch but as a sequence of input portions) and the output must be produced online (i.e., the algorithm must take immediate and irrevocable decisions in response to each incoming portion taking into account that the future input is not known at any point in time). Online algorithms are ubiquitous in computer science and optimization: from ad-allocation to taxy-dispatching, from network routing to machine learning. In this introductory session, we will study some basic problems, techniques, and models related to online algorithms.

##### Stable Marriage, Ties and Incomplete Lists. (Meghana Nasre)
Matching problems with preferences arise in real life in a variety of applications. In this talk we will introduce the stable matching problem and a natural variant of the problem where participants are allowed to express ties in preferences. With this flexibility, computing the largest stable matching turns out to be NP-Hard. We present a simple and elegant algorithm by Kirlay which gives a constant factor approximation to the problem of computing stable matchings in the presence of ties.
In the second part, we introduce a different notion of optimality namely popularity. A matching is popular if no majority of participants wants to deviate from it. We will present an algorithm to compute a popular matching in the stable marriage problem.

##### Introduction to Dynamic Algorithms (Manoj Gupta)
In a static algorithm, the input given to the algorithm does not change. However, in the dynamic algorithm, the input changes at each time step. For example, in a dynamic graph, at each update step, an edge may be added or removed from the graph. In such a dynamic graph, we want to maintain a property of the graph, say connectivity, matching, shortest path etc. We can always recompute these properties from scratch after each time step, but can we do better? Thus, the aim of the dynamic algorithm is to maintain a property of the graph after each time step. Also, the time taken to process an update should be much less than the time taken to compute the property from scratch. In this talk, I will introduce some simple algorithms for some basic dynamic problems like connectivity, matching, shortest paths etc.
##### Details
Date: 12th July - 16thJuly, 2021
##### News
• There is no registration fee but registration is mandatory.

• This is an online event, virtually hosted by IIIT Bangalore

• The schedule for the summer school is uploaded

• Registration for the summer school is closed