Friday, May 29, 2009

A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm

Dancing Links is a powerful algorithm that solves Exact Cover problems. These problems can lead to interesting algorithmic exercises such as the Pentominos problem, polyiamonds, tetrasticks, the N queens, traveling knight, and other chessboard derivatives. However, Exact Cover problems aren’t just theoretical mathematical puzzles though. They describe many real life problems: problems such as making hotel room assignments given a group that has a many specific room requests, and organizing simple flight schedules for airports. Dancing Links is a backtracking, depth-first algorithm that can find all possible solutions of the problem.

Monday, May 4, 2009

Technology News from all around the world

Doing a PhD in Computer Science

Pankaj Jalote
Professor, CSE Department, IIT Kanpur

PhD is the highest degree offered anywhere in the world (barring the highly uncommon DSc). Its focus, unlike regular degrees, is not learning existing knowledge but creating new knowledge. No wonder, PhD is desired by anyone wishing to `make a mark' - the brightest seek it as it allows challenges that no other degree does; the innovative desire it as it allows the possibility to innovate and create new knowledge and technologies; the ambitious seek it as it is the top of the academic ladder; and the persistent seek it as this is the one degree where persistence and self discipline are brought to full use.

Despite the romance of doing a PhD, there seems to be some `fear' frequently in the youth about pursuing a PhD - prospective students are sometimes scared because they think it is ``too difficult and they will not be able to do it'', or because ``it takes too much time'', or perhaps just because ``PhD means that you have to be a teacher and I don't want to be a teacher''. All of these reasons/fears are actually false. This note discusses some of these issues in an attempt to clarify the situation for prospective candidates.

What is Involved in a PhD?

First let us clearly understand what is involved in doing a PhD. PhD is, as everyone knows, about doing research. And research is about formulating problems or questions whose answers the research or practitioner community wants to know, and whose answers are not known. Doing research is to provide some answer to these questions. So, the key aspects of doing a PhD are (a) formulating a question or a problem that is of interest and that can be solved, and (b) providing a useful/interesting solution to the stated problem. The results obtained are presented in national/international conferences, and/or submitted to scientific journals.

The problems that are addressed by a PhD scholar can range from very difficult open problems to evolutionary technology issues. In Computer Science, the problem area can range from highly theoretical/mathematical to modeling and experimentation or building new technologies. For example, there are a lot of open problems regarding the complexity of solving some problems algorithmically (for example, checking whether a number is a prime - a problem for which an efficient solution was proposed only recently by Prof. Agarwal of CSE/IITK). These problems typically involve complex theoretical and mathematical development. Similarly, there are many problems that require understanding the behavior of various systems. Approaching such problems frequently uses modeling and experimentation. Then there are problems of the type where something innovative and useful is done using computers and software. Working on such problems typically involves building systems and prototypes. In other words, a scholar doing a PhD in Computer Science has a wide range of areas to choose from, depending on his inclination, ability, and interests.

Generally, PhD programs world over proceed as follows: do some course work, pass some qualifying exam, and then write a thesis that has to be defended (sometimes, at the early stages of the thesis a `proposal' may have to be submitted.) In a place like CSE/IIT Kanpur, generally, a student who joins the PhD program after completing his/her B.Tech/BE will spend about 1 year doing the courses, about 1 to 2 years for formulating the problem, which also requires an in-depth study of the chosen area, and about 2 years or more for developing the solutions and writing the thesis. Once the thesis is written, it is examined by some experts and a thesis defense is scheduled. This process takes about 6 months, but the candidate can start his post PhD job once the thesis is submitted. Hence, doing a PhD takes about as much time as doing a BE, or the amount of time a doctor spends doing his residency and MD.

Doing a PhD is indeed hard. However, the difficulty is not because extreme intelligence is necessary. Brilliance, of course, helps - brilliant people can attack hard problems and produce solid results and leave a permanent mark on the field. However, students with good academic background and some amount of creativity can also do a PhD, and do quite well. Completing a PhD primarily requires a drive, motivation, and hard work. Hard and motivated work determines not only the quality of the final work, but also the amount of time needed to complete the PhD. In general, a PhD can be completed in 4 to 5 years - 4 years for the motivated and 5 for the not-so-motivated.

What are the Options after PhD?

Clearly, one of the main job opportunities after PhD is a faculty position in some University, College, or an Institute. This option, world over, is one of the most preferred options for people with PhD. One of the reasons for this is that in today's world, the best quality people require freedom in their work and have a strong desire to ``make a mark''. Both of these are well supported by research activities a faculty undertakes as part of his job - he has the freedom to select the problems he works on, and through his research he creates new knowledge which is published under his authorship. This is a very strong motivating factor and very good people across the world sacrifice other benefits for academic freedom and possibilities to create and innovate.

In faculty positions it should be mentioned that for Computer Science, as there is a shortage of qualified faculty in most good institutions, there are always openings in places like IITs/NITs/RECs/Central Universities, etc. In addition, now some private universities as well as institutions set up by overseas universities coming up which also are looking for qualified faculty (and these places are paying much more than Govt. scales - up to 3 times more!)

However, teaching is by no means the only option for a PhD. India today is fast becoming a center for global R&D. Due to the quality of its manpower, and the lower cost, many organizations have started setting up R&D centers in India. And these centers are looking for PhDs (and not finding them, as there are not enough getting produced!) Some example of these are IBM India Research Center in New Delhi, GE Research in Bangalore, Mentor Graphics in Hyderabad, Cadence, etc.

Besides these research centers, most of the big Indian IT companies have started high end technology development and consulting, and R&D centers or cells, in which they need PhDs. Almost all the IT majors - TCS, Infosys, Wipro, etc. employ a large number of PhDs (upward of about 50 each) and are always looking for more people to enhance their R&D activities. This activity will increase in these companies as these companies become larger. A few years back, we had done an informal survey on salaries with these companies and we were told that most of them will offer at least twice as much starting salary for a PhD as for a BE. Starting salaries for many of these positions are of the order of Rs 50,000 PM or more.

Besides these opportunities in India, people with PhDs are global citizens and move around quite a bit. Immediately after PhD, there are opportunities for post-doctoral work in US and Europe. While working as a researcher/faculty, there are opportunities for visiting faculty appointments or visiting researchers in US, Europe, Singapore, etc., where a faculty member from India can spend a year or two in overseas universities or research labs. Many faculty members from India avail of this from time to time.