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
- 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
- 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
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.
- 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
Both topics require mathematical maturity and a liking for hard, rigorous
- 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.
- 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
- 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.
- gn1 Rough Sets
- gn2 Data Clustering
- gn3 Inductive Logic Programming
- 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.
- 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
- nls1 Time series analysis
- nls2 Data visualization
(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)
(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.
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
All the seminars can potentially be extended into projects. But this
is not compulsory, and will have to be determined later based on
- 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
- 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.
- M. H. Baaj and H. S. Mahmassani, ``Hybrid route generation heuristic
algorithm for the design of transit networks,'' Transportation Research
Part C, vol. 3(1), pp. 31-50, 1995.
- S. B. Pattnaik, S. Mohan, and V. M. Tom, ``Urban bus transit route network
design using genetic algorithm.,'' Journal of Transportation Engineering,
ASCE, vol. 124(4), pp. 368-375, 1998.
- M. O. Imam, ``Optimal design of public bus service with demand
equilibrium,'' vol. 124, pp. 431-436, 1998.
- S. Chien, Z. Yang, and E. Hou, ``Genetic algorithm approach for transit
route planning and design.,'' Journal of Transportation Engineering, ASCE,
vol. 127(3), pp. 200-207, May/June 2001.
- rkj1 Applying concept analysis for design improvement
- rkj2 Multi-paradigm programming in Mozart Programming system
- rkj3 Agent-oriented programming
- 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 :
- Effective Pattern Matching of Source Code Using Abstract Syntax
Patterns, Software Practice & Experience, Vol 36, No 4, pages
- Lightweight Source Code Extraction, ACM Transactions on Software
Engineering & Methodology, Vol 5, No 3, pages 262-292, 1996
- A Framework for Source Code Search using Program Patterns, IEEE
Transactions on Software Engineering, Vol 20, No 6, pages 463-475,
- 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
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.
- 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.
This seminar will focus on techniques used by the Moby/PLC tool
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/
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
- 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
- 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
- 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
- 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.
- sundar1 Topics in Graph Colouring
- sundar2 Algorithms for Network Flows
- sundar3 Applied Extremal Combinatorics
(Warning: Need mathematical maturity for this.)
- 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
- supratik2 Symbolic simulation and constraint solving for microprocessor
- 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.
- 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.
- 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.