A Prospective Randomized Approximation Algorithm for the MISR problem : Prof. Sandeep Sen, CSE, IIT DelhiBTech Thesis
This is an ongoing research project, we are trying to coming up with an algorithm for the Maximum Set of Axis Parallel Rectangles. This problem, which is a specific case of the independent set problem, has interested researchers due to applications in digital cartography, allocation of network resources and data mining among others. This problem is NP-hard, hence efforts have been directed towards obtaining approximation algorithms. The best algorithm provides an O(log log n) approximation for n rectangles, we aim to improve this and hopefully obtain a PTAS. Our starting point is the natural LP-relaxation of MISR where each rectangle is associated with a variable which can take values between 0 and 1. The approach involves carrying out a specialized random walk starting from the relaxed solution to reach an integral solution with high probability.
Feedback Capturing Device : Prof. M Balakrishnan, CSE, IIT Delhi Mini Project in continuation of a Course Project
This project was done by a team of six. Our aim was to create a efficient, scalable opinion-gathering mechanism; an easy-to-use communication channel between the provider of a service and it's consumer.
The Problem: Most existing mechanisms for gathering feedback focus on collecting detailed information from the consumer, they require a significant investment of time and effort and thus lead to scarce participation.
Our idea was to provide a solution at the other end of this spectrum i.e. situations where a simple consumer opinion has to be gauged but large participation is crucial (eg. airport authorities gauging the level of satisfaction among the hundred thousand people going through daily).
The Solution: Several portable polling devices installed across a facility, all of which are centrally managed by a server. An administrator can create polls in advance, polling takes place on the machines and finally the compiled results are made available online. The devices' portability enables us to tap a consumer's sentiment at the opportune moment (e.g. just after crossing the check-in counter at the airport). Salient features of the device include a touchscreen, RFID authentication (optional), Wifi and a low cost.
We succeeded in converting this idea into a functioning prototype, we also executed several field tests around campus. Here's the poster we presented at IIT Delhi's annual research showcase, I2Tech Open House.
Modeling Portfolio Market Impact : Dr. Nicholas Westray, Deutsche BankInternship Project
When one wishes to trade, one put in orders at the exchange which look like this: "I wish to buy 100 stocks of Microsoft". As it happens, on an average, the price you end up paying for your order is worse (greater) than the price of the stock at the instant you put your order. This can be due to a couple of reasons
- you divulge your intent to buy by posting the order and as a response, the other market participants make the price move against you (higher)
- your order consumes orders on the sell side, hence driving the price up
This difference in the price is called the Market Impact of the order. (Symmetrical arguments hold for a sell order)
The Bloomberg model is a standard model to predict the market impact of single stock trades. In this project, we investigated the trading of portfolios and were able to establish that there exists a systematic difference in market impact when trading well-hedged portfolios as compared to single stocks. i.e. if I put in orders for two stocks, say Microsoft and Apple, which are correlated, then the market impact I suffer on my Microsoft order not only depends on its own characteristics but also on my order for Apple. This led us to formulate better models for predicting the market impact of portfolio trades which, unlike the Bloomberg model, take into account the portfolio's characteristics and stock correlations.
Limit Order Book Reconstruction : Sidharth Chaturvedi, Deutsche BankInternship Project I devised and implemented an efficient data structure to construct the limit order book from an exchange's raw message level data. In particular, I did this for NASDAQ's ITCH feed. Using the simulator, I gathered insights regarding volumes present at all levels in the book and it's relation to stock characteristics like spread, volatility, liquidity etc. Having access to the message level data, I was also able to assess the amount and nature of Hidden Liquidity (non-displayed orders whose presence is detected only after they get executed) in NASDAQ.
Both these projects were done during a very enjoyable summer at Deutsche Bank's CIB Centre, Mumbai. I presented my work to an audience of Directors and Vertical Managers; I obtained some very interesting results using the limit order book simulator.
A New Quiz Format based on Hamiltonian CyclesIndependent Project The traditional setting for a quiz involves teams seated around a circle and questions are asked in the order imposed by the seating arrangement. At any point of time, if the team facing the current question (the team that is "live") answers correctly, the next question goes to the team to its immediate left, which now becomes live. In case the live team passes or answers incorrectly, the same question "bounces" to its left neighbour and so on around the loop. This format, when played with a great number of teams (upwards of ten, as is commonly done in quizzes here at IIT Delhi) engenders two problems:
- There is a large element of luck involved. A team wishes that the question it knows does eventually come to it (or the question it doesn't does not!).
- The teams aren't actively involved at all times. With the path of the questions predetermined, at any time only the live team and a couple of teams to it's left are concerned with the current question.
I imagined a format which would reduce the element of luck and keep the teams on their toes. The plan is to make the live team decide which team the next question goes to or the current question "bounces" to (depending on whether the live team answers the current question correctly or incorrectly respectively). This rule gives rise to various strategies:
- The live team will want to direct the next question to a team which, it feels, does not know the answer. It may also choose to direct it to a team which is way below itself in the points tally if it seems that team knows the answer.
- The non-live teams which know the answer will try to lure the live team to direct it to them (by pretending to not know the answer, for example). The non-live teams which do not know the answer would try for the opposite outcome.
This scheme, though quite natural, has never been adopted in quizzes because it leads to absurd outcomes (for e.g. two teams directing questions only between themselves). The ingenuity of my idea was how I avoided such outcomes. I enforced that the path traced by "live"ness should be composed of consecutive hamiltonian paths over the fully connected graph of teams. This ensures that each team will be live after atmost 2n chances (n being the number of teams).
Concomitant with enforcing this restriction, was a need to track the precise progress of the quiz and display it to the teams at all times. To do this, I created an application in Python (using pygame for the GUI) to be used by the quizmaster. It has the provision to "undo" indefinitely (this turned out to be a great foresight) and can also keep score. Here are a couple of screenshots (The four corners serve as the legend, teams are represented around the circle in the middle):
The quiz is being played between ten teams each led by some distinguished gentlemen (and a lady).
Each team has a unique letter (used to shift "live"ness to it), name and score.
Live : The team which has to answer the current question.
Seen : These teams have seen the current question and hence can't be live in the next turn.
Hamiltonian'd : These teams have already had a chance in the current hamiltonian path and hence can't be live in the next turn.
Predicting App character from its icon on the Apple App Store: Prof. Parag Singla & Prof. Prem Kalra, CSE, IIT DelhiCourse Project
The Apple iOS App store boasts of over 400 million accounts and over 650,000 downloadable apps. Apart from being a very rich source of data, it's unique in the way it displays apps to prospective customers. On entering the app store, a buyer is greeted by an endless grid of app icons with the corresponding titles written below. A buyer's decision to explore the app further is founded solely on the basis of a 120x120 image and a title. In a setting such as this, the app icon occupies a position of paramount importance and serves to attract the right kind of audience towards the app.
This paradigm of showcasing apps necessitates that the app icon carry important information about the nature of the app and its intended audience. Our plan is to use the app's textual description as a reliable indicator of the app's nature and try to correlate it with the image features in the app's icon.
Below are two clusters of apps we extablished using unsupervised learning techniques, we used both image features (app icon) and textual features (app description). Along with some sample app icons, the words most likely to appear and least likely to appear corresponding to each cluster are also represented. These results were quite encouraging to say the least.
Image Stitching using a Multi Resolution Spline: Prof. Prem Kalra, CSE, IIT DelhiCourse Project Two input images are stitched along their vertical/horizontal axis to create a blended image. The technique employs Laplacian image pyramids and results in a much smoother blend than a simple gradient. Below two images are blended in four possible ways.
Image Registration using Fourier Transform: Prof. Prem Kalra, CSE, IIT DelhiCourse Project Image registration is the process of transforming different sets of images into one coordinate system. My implementation accepts two images different from each other by a rigid transformation (translation and rotation) and outputs their correct overlay.
Assignments on PintOS : Prof. Sorav Bansal, CSE, IIT DelhiCourse Project Done as a team of two, we implemented thread scheduling, system calls (fork, exit, wait, etc), virtual memory management (using page tables, swap disks & memory maps), the ability to run user programs & file system control. Coding was done in C, and SVN was used for version control.
Assignments on PIOS : Prof. Sorav Bansal, CSE, IIT DelhiCourse Project Added the functionality of catching traps caused by the kernel's code, implemented protected control transfer to run application mode in a less priviledged mode and a dynamic memory allocator.
Indigenous Systems of Medicines (ISM) in the Indian context : Prof. Naveen Thayyil, HSS, IIT DelhiIndependent Project India has for centuries boasted of numerous ISMs, collectively called AYUSH (Ayurveda, Yoga, Unani, Siddha, Homeopathy), with each of them commanding popular support in terms of usage, cultural consonance and number of practitioners. The Govt. of India's policy to base state-sponsored health care on the modern, scientific biomedicine for over a century has put both firmly on a collision course. There is a need for laws and infrastructure that give the population access to the best of both worlds. Under the guidance of Prof. Thayyil, I am researching various aspects of this ongoing debate with the aim of shaping public policy.