MTech Seminar Topics Fall 2006

Check the list of offered topics below, with completed assignments as they come in. Per CSE bylaws, faculty members whose names do not appear below are also offering seminars but with unknown titles, up to a maximum of the ceiling of the department average.

There will be no coordinated session where faculty members will describe their seminar topics to prospective students. Instead, prospective students should team up and approach faculty members for time/s when they can do this, to save many-to-many multicasts.

Here is the tentative timeline and procedure for topic assignment.

11:59pm Wednesday 2006-08-16
Up to this time faculty members can report to me voluntary mutual pairings. Each faculty member will be limited to two students.
10:00am Friday 2006-08-18
Within this time, I will need a preference list from each faculty member for students hitherto unassigned. Assuming there is at least one unassigned student, if a faculty member does not send me a list or sends me an empty list, that means the faculty member will accept any student assigned to him or her in the next round.
11:59pm Friday 2006-08-25
Within this time, in consultation with faculty members, I will complete all pairings that are included in someone's preference list. At most two more students will be included per faculty in this stage.
11:59pm Tuesday 2006-08-29
In this last phase, within this time, I will be making final assignments without any guarantee of interest match between faculty and student. The primary goal here is load balance.

I am considering 1st Nov as the earliest date when advisors, if they can organize examiners, are free to schedule the viva on their own. This will give two full months to work on the seminar. For those students who don't go through this channel, we will have the usual 2-day schedule very close to final exams and project submissions. Hopefully, enough students will finish early so that those 2 days will not be as jam-packed as they are to date.

Prof. Diwan

aad1 Graph Minors
06305031 Namrata Tholiya The study of graph minors (a generalization of subgraphs) is a deep topic in graph theory with many challenging problems. The aim of this seminar is to get acquainted with some of the results in this area.
aad2 Even cycles in Directed Graphs
The problem of finding a polynomial-time algorithm to decide whether a directed graph contains a cycle of even length was unsolved for many years. The aim of this seminar is to study results that give sufficient conditions for a directed graphs to contain an even cycle. This problem has connections to many other problems.

Both topics require mathematical maturity and a liking for hard, rigorous arguments.

Prof. Sanyal

as1 Garbage Collection
as2 Incremental Garbage Collection
Apart from descriptions of garbage collection algorithms, the study will focus on their performance in realistic settings.
as3 Study of a theorem prover
The specific theorem prover will be decided later.

Prof. Dhamdhere

dmd1: Region based compilation techniques
A region is a part of a program that is considered as a unit for program optimization. Region-based compilation/optimization techniques permit generation of code that executes very efficiently. Regions may be identified based on profiling data to fully exploit this possibility.
dmd2: Optimization in the presence of exceptions
Exceptions and their handling lead to a large number of control paths in a program's flow graph. This feature inhibits optimization of programs due to considerations of safety of an optimization. This seminar is devoted to a study of techniques used to perform optimization in a program where exceptions could occur during its execution.

Prof. GN

gn1 Rough Sets
gn2 Data Clustering
gn3 Inductive Logic Programming

Prof. Krishna

krishnas1 Modeling and Analysis of Real-Time Systems Using Hybrid Automata
This would involve understanding how real time systems are modelled using hybrid automata, and decidability issues pertaining to them.
krishnas2 The Automata-Logic Connection in Timed Systems
Lakshmi Manasa G This involves understanding the classical notion of Alur and Dill's timed automata as well as variants, and logical characterizations of the same.

Prof. Krithi

krithi1 Real-time support for safety-critical applications
krithi2 Convergence of streaming, sensors, peer-to-peer, and the Internet
krithi3 Data-based support for resource constrained environments

Prof. Sarda

nls1 Time series analysis
nls2 Data visualization

Prof. Pushpak

(Students are advised to definitely discuss with me before opting for any topic)

pb1 Machine Translation: Knowledge Based and Statistical
IIT Bombay has been a major center for Machine Translation for over a decade now (UNL Project, Indian Langauge Technology development project etc.). The emphasis has been on semantic analysis and the subsequent high quality output generation. This seminar will study these contributions and also the current statistical approaches in the area. Machine translation among Indian Languages and from-to English will be kept in focus.
pb2 Mining of Biological Texts (with Prof. Pramod Wangikar, ChE)
Biotext and bio-ontologies (hierarchical knowldege bases) are very active research areas these days, working on sophisticated algorithms for information extraction. This seminar will be devoted to the study of these topics.
pb3 Structuring, Augmentation and Enhancement in multiple language wordnets
IIT Bombay is a major center for development of word-knowledge networks called wordnets (Hindi, Marathi) which are essential for langauge processing applications. In this seminar the focus will be on studying the algorithms, storages structures and NLP methods creating wordnets and associated ontologies, and for linking wordnets of many languages.
pb4 Shallow parsing of languages (Indian and English)
miteshk (With Prof. Om Damani, SIT) Operations like Part of Speech Tagging, Chunking, Named Entity Detection are considered vital for building language processing systems. This is the focus of this seminar (for multiple languages).
pb5 Cross Lingual and Meaning Based Search
sandeepl Multilingual search engines are slowing arriving in the scenario with both shallow and deep processing approaches. In IITB, we have been pursuing this problem for last few years. The world wide effort on this is also quite intense. The seminar will study these issues.

Prof. Ranade

I will be offering the following 3 seminar topics. If you are interested, please check out some of the pointers, then drop me an e-mail describing why you are interested, what expertise you think the seminar will involve, and how you have it. Mention the courses you are taking.

All the seminars can potentially be extended into projects. But this is not compulsory, and will have to be determined later based on mutual inclination.

ranade1 RECOGNITION OF MOUSE DRAWN SKETCHES
Given a sketch drawn using the mouse, can you recognize the object drawn? The "object" could be a part of a machine, a mathematical formula, a circuit, a figure drawn by a student while solving a problem and so on. The goal would be to survey this area. Some starting points are here.
ranade2 CLUSTERING AND GRAPH PARTITIONING
Clustering and graph partitioning are important problems in Computer Science. The goal of this seminar would be to study these, a starting (or ending) point is: Dhillon, Inderjit S., Yuqiang Guan, and Brian Kulis. "A Unified View of Graph Partitioning and Weighted Kernel k-means." Please look up the net for additional literature.
ranade3 TRANSIT ROUTE NETWORK DESIGN
(Co-guide: Prof. Tom Mathew, Dept of Civil Engg. IITB) Transit route network design (TRND) problem for urban bus operation involves the determination of a set of bus routes and the associated frequencies such that the given demand can be met as inexpensively as possible. The objective of the seminar would be to study the formulations and algorithms for the above problem, and related problems from Operations Research.

Prof. RKJ

rkj1 Applying concept analysis for design improvement
rkj2 Multi-paradigm programming in Mozart Programming system
rkj3 Agent-oriented programming

Prof. Biswas

sb1 Pipeline features of Pentium
This seminar deals with the study of the pipeline features of Pentium IV. The survey involves understanding the pipeline characteristics in detail and its implication in instruction selection part of the compiler. The expectation is that given an assembly program, the study would provide the reasons for the schedule generated by the compiler using the pipeline. Reading Material : Pentium Architecture Manual, Automata for pipeline hazard recognizer (Research paper), experimenting with schedules produced by a compiler using GCC.
sb2 Compilation issues in Object Oriented Programming Languages
This seminar would involve studying the schemes employed in the compilation for the object oriented features such as compile-time and run-time polymorphisms. The target language could be C++ and Java. Reading Material : Papers on compilation of polymorphic features of C++/Java.
sb3 Program Understanding using Pattern Matching
This seminar involves survey of the various methods suggested for understanding source code using pattern matching. Reading Material :

Prof. Sharat

sharat1 Video: Retrieval, Summarization
sharat2 Augmented Reality: Image Based Relighting
sharat3 GPU: Techniques for GPGPU
sharat4 Motion Capture Reuse
sharat5 Projector Camera Systems
sharat6 Biomedical Informatics

I plan to have only 2 out of the six topics above. Main idea in listing more topics is to give some sort of feeling on what I am doing with my other students.

More information on this will appear here

MTP allocation is expected to happen next semester only. However, it is too late if you don't take my seminar+course this sem+course next sem. Department does not object if students decide early -- therefore I strongly recommend that you take my seminar and my class if you are going to work with me.

Prof. Sivakumar

siva1 Hidden Markov Models for Speech Recognition
A hidden Markov model (HMM) is a statistical model where the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden parameters from the observable parameters. The extracted model parameters can then be used to perform further analysis, for example for pattern recognition applications. (from http://en.wikipedia.org/wiki/Hidden_Markov_model) This seminar will study recent work in using HMMs for Speech Recognition. Requires some aptitude for mathematics/theory.
siva2 Formal Design and Verification of Programmable Logic Controllers (PLCs)
Many safety-critical real time systems can be modelled using PLCs. (http://dce.felk.cvut.cz/susta/publications/thesis.htm) This seminar will focus on techniques used by the Moby/PLC tool (http://csd.informatik.uni-oldenburg.de/~moby/PLC/) to model, design and verify PLC-automata.
siva3 Termination Orderings
Proving termination of programs and proofs are very important in many domains. From purely syntactic approaches using "simplification orderings" to more context and semantics aware "dependency pair" various methods are being developed. This project will explore how to extend these ideas to show termination of inductive proofs. One starting point is http://rewriting.loria.fr/

Prof. Soumen

These topics are merely representative of some papers I am reading nowadays. I will offer probably 2 and at most 3 topics. Your final topic will depend on your aptitude and initial discussions and may not be exactly what you selected.

soumen1 Optimization techniques for text mining
Quasi-Newton optimizers are used in many text mining and learning applications. We wish to study approaches based on iterative scaling and approximate Hessians. We wish to inspect the effect of Lasso, Gaussian, Laplacian and exponential priors on model parameters, and look at a few papers that integrate model fitting with feature selection.
soumen2 Searching and ranking uncertain data
There is much recent interest in databases that are uncertain in at least two senses: tuple uncertainty where each row in a table has an associated probability of "happening" and attribute uncertainty where a cell has a distribution instead of a value. We wish to look at query classes and their execution semantics and optimizations, with a focus on answering text+structure queries.
soumen3 Link spam and remedies
Link farms are a major impediment to effective static ranking of Web pages based on hyperlinks. Recent papers list a number of ways to detect automatically when a dense link community on the Web graph appears to be artificially created to mislead link-based ranking algorithms. Here we will study such proposals.
soumen4 TREC and INEX evaluation methodology
TREC organizes an annual competition where search engines are evaluated on a number of performance measures. Precision at top-k ranks, average precision over top-k ranks, mean reciprocal rank, normalized discounted cumulative gain (NDCG) are some of the measures used. TREC uses a comprehensive judgment and evaluation mechanism. We will study these procedures, measures and their properties. We will also look at extensions for XML+text search under the INEX initiative.
soumen5 Predicting query difficulty
A few recent papers say something like "in cases where the original response ranking was poor, the improvement from our idea was the most pronounced". This is useful only if a search engine can estimate its success at ranking for a given query. We will study a few papers that propose approaches to estimate the difficulty of a query and how well/poorly a ranking system performs in response to a query.

Prof. Sudarshan

sudarsha1 Adaptive query processing/optimization
06305001 Vinay Sudhir Deshpande Traditionally, query optimizers generate a fixed plan for a query, based on estimates of various parameters. Plans do not change even if these parameters are found to be incorrectly estimated during execution. Adaptive query processing/optimization attempts to adapt the query plan based on run-time information.
sudarsha2: Database security/authorization
Review recent work in this area, including approaches to fine-graiend authorization, and detection of database tampering
sudarsha3: Keyword querying on structured and semi-structured data
Review work on querying on relational and XML data, as well as querying on general graph data models.

Prof. Sundar

sundar1 Topics in Graph Colouring
sundar2 Algorithms for Network Flows
sundar3 Applied Extremal Combinatorics
Chintan

(Warning: Need mathematical maturity for this.)

Prof. Supratik

supratik1 Polytope abstractions for numerical domains
This study will cover different polytope abstractions used for representing numerical domains when analyzing programs manipulating integers and reals. We intend to survey a range of techniques with varying tradeoffs between complexity and precision of representation. A liking for mathematics and discrete maths, in particular, is preferred.
supratik2 Symbolic simulation and constraint solving for microprocessor verification
This study will cover different techniques used to perform symbolic simulation of complex microprocessors. The study will look into exact and approximate techniques used in such simulation, and also constraint solving techniques that are used in conjunction with symbolic simulation to verify properties of microprocessor systems. A liking for architecture and interest in discrete maths would be preferred.
supratik3 Symbolic model checking techniques for large state spaces
This study will cover techniques to symbolically search large state spaces -- abstractions and approximations used in such endeavours, and the variety of techniques that have been used in different contexts to tame the state explosion problem. A liking for algorithms, and discrete maths is preferred.

Prof. Uday

uday1 Register allocation for SSA intermediate representation
Graph colouring based register allocation is a fairly well known approach to register allocation. This approach is based on an interference graph in which adjacent nodes represent variables which are live simultaneously (i.e. those which cannot share a register). The use of SSA (Static Single Assignment) form of intermediate representation brings out some interesting properties related to the chromatic number of the interference graph. This seminar studies some recent findings related to the above.
uday2 A survey of some non-separable data flow frameworks
Data flow analysis is the process of discovering useful information about program entities (eg. variables or expressions etc.). Non-separable data flow problems relate data flow information of one program entity to another. As a continued research in non-separable data flow framework, this seminar studies some frameworks like slicing, points-To analyses, signs analysis etc.
uday3 The LLVM compiler infrastructure
The Low Level Virtual Machine (LLVM) is an interesting approach to compiler infrastructure which facilitates many optimization in different phases of compilation (eg. post-link optimizations). This seminar studies this infrastructure.

Prof. Varsha

varsha1 Self-tuning software servers
Servers (such as web servers) need to be configured and tuned for best performance on the given platform and workload. Research is now ongoing to build mechanisms that require no manual tuning from an administrator. The server should "self-tune". In this seminar you will read latest papers in this topic.
varsha2 Performance Isolation in Virtual machines
06329017 Rahul Chandrakumar Gundecha Virtualization is increasingly being used to share resources of a machine in a transparent manner. But how does one give performance gurantees in this scenario? In this seminar you will read latest papers answering this question
varsha3 QoS support in Wireless Mesh Networks
Mesh networks (multi-hop wireless access networks) are being built to increase the reach of wireless networks. In this seminar, you will read latest papers in this topic.