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.

- 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.

- 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 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.

- 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)
**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.

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.
- 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 413-447, 2006
- 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, 1994

- 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.

- 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/

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.

- 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
**Chintan**

(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 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.

- 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.