Panel Discussion on
Under-graduate and graduate curricula in theoretical computer science

FSTTCS, December 17, 2010, 1600 to 1730 hrs.
Ramanujan Auditorium

Dijkstra once said that to call this field "Computer Science" was like referring to surgery as "knife science". In CS education, the pressure to tailor curricula to the rapidly altering landscape of computer technology is natural, but it also calls for the role of theory in the distillation of knowledge acquired through conceptualization and analysis. TCS curricula attempt to identify core structures: for instance, the logarithmic / exponential relationship in trees that underlies many arguments in computer science, from short certificates for NP-complete problems to stack trace of expression evaluation in programming languages. With new topics like information security, game theory, computational biology and web mining crowding the curriculum, there is a need to delineate the role of theory in the CS curricula.

Such an examination gives rise to a number of questions: Should the increasingly web-centric nature of computer use have any impact on the field and its education? (Is there a "web science"!?) Does the growing concern about multi-core architectures and concurrency imply that concurrency should be brought early into the CS curriculum (as the ACM 2008 CS education report seems to suggest)? Is security theory to be treated as an area of specialization or a core concern? Do we have a consensus on the knowledge areas and learning outcomes? How do we visualize the computer science graduate in the years to come, say within a decade?

IARCS, the Indian Association for Research in Computing Science, seeks to discuss and take a stand on these curricular issues, for which the panel discussion at FSTTCS 2010 is intended as an initiator and curtain raiser.


Friday, 17 December, 2010
16:00-16:05 Opening remarks, R. Ramanujam (IMSc, Chennai)
16:05-16:20 Somenath Biswas (IIT Kanpur)
Theory curriculum over three decades
16:20-16:35 Mike Fellows (Univ of Newcastle, Australia)
Theoretical computer science: its mission and attitude
16:35-16:45 Open Discussion
1645-1700 Madhavan Mukund (CMI, Chennai)
Teaching theory to practitioners and practice to theoreticians
17:00-17:20 Open Discussion
17:20-17:30 Wrap-up, R. Ramanujam (IMSc, Chennai)


Somenath Biswas (IIT, Kanpur)
Theory curriculum over three decades

CS curriculum over the last three decades (1980 - 2010), especially in its core component, has developed more through evolution than through revolutions. If we include the earlier decade too, the 70's, then that saw a revolutionary development: the notion of NP-completeness, and more generally, what we should mean by an efficient algorithm. This idea almost immediately made its entry even to the beginning texts on algorithms and theory of computation.

At the same time, it is rather strange that even now there is no consensus on two very basic aspects of CS education: (a) what should be the programming language for the first computing course-- more generally, how should we introduce programming, and (b) what is the mathematics that is required to be taught to every CS student.

On some other core courses:
Theory of Computation: Little change-- with emphasis having gently shifted from languages to machines. How many of our current students know what are AFLs? At the higher end, in the elective offerings, recursion theory has yielded to computational complexity. Overall, the emphasis has moved from decidability to feasibility.
Principles of Programming Languages: New kid in the block is object orientedness. However, more fundamentally, it is not clear even now what should be the relative emphasis on principles of declarative vs. applicative vs. functional vs. logic programming.
Algorithms: Two most dramatic entries are: randomized algorithms and linear programming, and in a related way, the notion of approximation algorithms. (Earlier, one learnt LP in an OR course, rarely in a CS course). This now means that we must make every of our students comfortable with linear algebra and discrete probability. And that brings us back to the question of what we should teach in the discrete mathematics course.

Mike Fellows (Univ of Newcastle, Australia)
Theoretical computer science: its mission and attitude

In many places, theoretical computer science has been for many years in retreat in the role that it plays in the curriculum. Theory courses once considered a standard part of an undergraduate education in CS, are at many universities no longer required. I would like to ask whether this might be in part because theory was presented in a way that is excessively dry and detached from applications. I think that theory needs to compete for attention, and convey a spirit of being aimed at (and essential in) solving useful problems, that its mission is to create and use effective tools, and that it is "open" and changing. I would also like to ask if the retreat of theory in the curriculum might be part of a larger picture that includes the retreat of funding for research in theoretical computer science that has perhaps had allied causes. At an even larger level, mathematical sciences seem to be in retreat at all levels of curriculum, starting in the elementary schools, where similar questions could be asked.

Madhavan Mukund (CMI, Chennai)
Teaching theory to practitioners and practice to theoreticians

Is an understanding of theoretical computer science relevant to the needs of the (Indian) industry? Can students of computer science gain a better understanding of theoretical issues through exposure to application areas? Our experience is that the answer to both questions is yes, especially if one takes a broader view of theoretical computer science to mean "foundational aspects of computing", extending from the more standard topics of algorithms and automata theory to areas such as databases and machine learning. We illustrate our point with some examples drawn from our interactions with trainees in the software industry as well as students ranging from high school to masters level.