Brief description: 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.
Brief description: The aim of the lectures is to give a brief introduction to the field of Parameterised Algorithms and Complexity. This is relatively young area (around 30 years old) was introduced primarily as a means to tackle NP-hard problems. The key idea is to identify the different "parameters" of a problem instance and to study the complexity of the problem as a function of this parameter. Thus the problems that admit algorithms that run in time polynomial in the input size while exponential only in the parameter are said to be Fixed Parameter Tractable (FPT). We will discuss some basic algorithmic design techniques for FPT algorithms with examples. The sessions will also involve a brief introduction to the concept of intractability and lower bounds in Parameterised Complexity.
Brief description: We give a very brief introduction to cryptography covering basic primitives in symmetric-key and public-key settings such as encryption, signature and message/entity authentication schemes etc., and the corresponding adversarial models used for security analysis. We will briefly understand the notion of reductionist proof of security. Finally, we will look into an advanced cryptographic primitive called Homomorphic Encryption scheme.
Brief description: Lectures in this area will give an overview of formal methods and focus on two specific techniques: program analysis and theorem proving using set theory and first order logic (B-method). We will look at a few program analysis techniques like abstract interpretation and symbolic testing in detail. We will also introduce B-method which uses set theory for modelling and first order predicate calculus for writing and proving axioms and theorems. All these techniques will be illustrated using applications from embedded software and IoT.
Brief description: Algorithmic computing that is based on foundations of Turing-completeness,
models computation as a closed-world from the input "problem" state to
a desired output "solution" state. Closed-world computations perform atomic and
isolated transitions between the start and the finish of the computation. Any Turing-complete
computation does not respond to the environment in the middle of a
computation, and any two active Turing machines do not interfere with one another.
The expressiveness of the class of Turing-complete functions can be shown to be
equivalent to First-order Predicate Logic.
For most practical applications however, involving interactive problem-solving, the
transition from the problem state to the intended goal (solution) state cannot be
modelled as a closed-world transition. An interactive or open-world workflow, may need
to cater to several intermediate inputs from the environment, as well as interference
from other processes, as part of computing its transition to the intended goal state. This
is called the open-world computing problem. Several approaches have been explored
for representing and computing in open worlds in mathematical terms. In this tutorial,
we will look into disparate models addressing open-world computing -- including, modal
and non-monotonic logics, deontic logics, non well-founded sets, and agent-based
computing. We will also address paradigmatic changes between closed-world and openworld
computing. Open-world computing shifts the emphasis from algorithms to
strategies, as the building block for computation.
Brief description: Not Available
Brief description:The theory of NP-completeness and the widely held belief that P != NP imply that NP-complete problems can not be solved in time polynomial in the input size. However, the naive algorithms for some of them take $n!$ time, some take $k^n$ time for a large $k$ and some of them can be solved in $c^n$ for some $c < 1.5$. We will look at a variety of such problems, and a few algorithmic techniques towards the goal of obtaining better exponential time algorithms for them.
Brief description: Not Available
Brief description: Abstract interpretation is a technique for static analysis of programs. The objective of any static analysis technique is to identify whether a property of interest holds across all executions of a program without running the program at all. Abstract interpretation has certain unique advantages: (1) It is a framework, in that it can be customized by a user to analyze any property of interest. (2) It is safe, in that it declares a property as holding only if it provably holds in all possible runs of the program. (3) Implementations of it are provided by many tools, for various prevalent programming languages. (4) It is efficient in practice, even on very large programs. In this tutorial we will explore abstract interpretation by going over some examples involving it, by taking a look at the mathematical theory underlying it, and by looking at its usage in practical settings.
Brief description: The talk will cover how enterprises can use the power of cloud and data to build an end-to-end analytic solution covering big data, machine learning, IOT. It will cover an example of using Azure data components to build a practical solution.