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.

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.

Download Presentation Slides (July 12)

Download Presentation Slides (July 13)

Download Presentation Slides (July 12)

Download Presentation Slides (July 13)

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(c^{n}) where c is a constant?

In this talk, we will discuss a few techniques for designing efficient Exact exponential algorithms.

Download Presentation Slides

In this talk, we will discuss a few techniques for designing efficient Exact exponential algorithms.

Download Presentation Slides

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.

Download Presentation Slides

Download Presentation Slides

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.

Download Presentation Slides

Download Presentation Slides

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.

Download Presentation Slides

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.

Download Presentation Slides

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.