GET YOUR PEN DRIVE.

CONTACT DEPARTMENT OF CSE.

or third year CSE students.

(academic year 2010-2011)

M J COLLEGE OF ENGINEERING.

or third year CSE studentts.

(academic year 2010-2011)

MEDHA COLLEGE OF ENDINEERING.

KHAMMAN DISTRICT.

the ppts are free.

TO MAKE THEM FREE WE HAVE AVOIDED PUTTING THEM ON THE WEB.

IT IS ECONOMICALLY NOT EASY TO HOST THEM AND MAKE THEM FREE.

ACADEMIC INSTITUTIONS IN INDIA CANNOT ALLOW THIS FREE HOSTING.

THE PROOF OF THE PUDDING IS IN THE EATING .

"The brontosaurus moved deeper into the swamps when the mammals took over the forest, but one day it ran out of swamps."

BRINGING THE THEORY OF COMPUTATION TO PRIMARY & SECONDARY SCHOOL CHILDREN ....

click here: INTRACTABIITY FOR PRIMARY SCHOOLS

__draft__

USER FRIENDLY EXPOSITION
OF COMPUTER SCIENCE SUBJECTS FOR MASS EDUCATION

ABSTRACT

*The
rapid proliferation of computer science training and educational requirements
in India to
cater to the explosively growing outsourcing industry has led to many problems.
A major problem has been the proliferation of engineering colleges without the
requisite dedicated, competent and skilled faculty in core subjects. An experiment
conducted over the last decade in computer science instruction for mass formal
and informal education in a core subject is reviewed. Successful courseware and
material has been created over the last few years for not for profit mass distribution and instruction in the core
subject. This is for either
formal instruction or self study of the subject at undergraduate and beginning
graduate educational level in computer
science. The target is a variety of engineering, computer
applications colleges and computer training institutions of various degrees of quality in the interior
regions of India in remote towns and villages. It is expected that with the
growing global village, the rising and high costs of real estate and
infrastructure in the overburdened cities a major shift is of outsourcing is
evident to the interior regions of the Third World.*

The Y2K problem and the
dot com boom & bust led to the major revolutionary change in the
international software scene of the Indian IT professional being * *identified
with outsourcing at the lower levels and phases of the software development life cycle(SDLC).
This led to an
explosion in outsourcing to India over
the last decade. In a parallel line this also resulted in engineering colleges
mushrooming for formal education in computer science, information technology
and computer applications. The insatiable needs of the software outsourcing
industry for personnel has led to an acute shortage of trained and competent
faculty in the engineering and computer
applications colleges in core computer science subjects.

The rapid mushrooming of
engineering and computer applications colleges has led to a dichotomy in the mass production of
graduates oriented educational process over the last two decades in India. This
is best explained by an example drawn from the area of Modeling and Simulation.
In his visit to India
in the seventies Prof C A R Hoare of Oxford pointed out the unreality of the
simulation process. When the actual machine being simulated is actively and noisily doing the work
with utmost vigor the simulator is silent, maintaining a ghostlike silence. When the
machine is idle and silent the simulator grinds away furiously.
Thus many of the formal educational and training institutions and the associated plethora of statutory
bodies regulating the same are like the
simulator concentrating, in all forums with enormous fanfare, on the academic
requirements, formalities, paper work,
administration and all formalities with utmost vigor without the students and
teachers being really involved. At times the teachers and students may be
mostly or partially not be present at all. When the simulator is totally silent
like in the wee hours of the morning, evening and late hours of the day, holidays or off on
a seasonal/ yearly vacation, the actual process of acquiring information and
knowledge by the students takes place. Many coaching and training institutions
have sprung up all over for imparting the actual educational requirements of
teaching, coaching and all that goes into the basic requirements of actual
information and knowledge being imparted to the student community. This is like
the simulator closing its eyes, being disdainfully and totally silent while the
machine is grinding away. Our study is to cater more to the machine consisting
of the young generations and
not the simulator which primarily draws personnel from the older
generations. We have of course extensively and intensively used the material
presented here in the framework of the formal educational processes and
institutions.

The major skill
requirements of a software professional for outsourcing in the IT industry have been determined
almost 40 years ago. These requirements have been enunciated by Prof C A R Hoare of Oxford University in his visit to India in the
seventies. Software outsourcing requires that at the higher levels of the
software development life cycle(SDLC) the entire work
to be done in the outsourcing situation has to be thought out to the last
detail. Then the best possible persons with the highest IQ are to be employed,
and they should implement the details determined upon without the slightest
variation being allowed. It is this
strategy that was initially proven in the history of outsourcing with enormous
success. This was in the maintenance of tens to hundreds of millions of lines
of legacy software code. * *

Software Engineering specialists add to
the above requirements the personnel requirements of youth, competent
education, good communication skills, ability to work in a team, some skill in
programming, good command of English, a basic two years industrial experience
and the ability to work for low wages. The BRIC countries satisfy the need for
masses of personnel with these characteristics being available.

It appears that some industrial
and academic environments that did not understand the crucial need for a mass
of motivated, young, high
IQ personnel for carrying
out the software drudgery activities of
large legacy software, for low wages,
have failed to prevent outsourcing to the BRIC countries. It appears advanced economies underestimated the requirement of high IQ, high intrinsic skills and low wages. They decided it was not crucial for routine maintenance activity. It appears this wrong judgement caused outsourcing to the BRIC countries, but this is not clear.

In India the requirements of
the outsourcing industry are met only by a small percentage of the students
turned out by engineering colleges at present. A very large bulk of the
graduates is not easily finding a place in the IT outsourcing industry. This can be
attributed largely to the dichotomy of the educational process i.e. the actual knowledge acquired
when one goes through the educational process for a degree versus the formal
administrative and academic requirements to be satisfied to obtain the same. Another major reason is the fundamental requirement of high IQ or as high as the cut off point demanded by the software outsourcing industry.

Computer science has the doubtful distinction
of having some core areas having over developed and over studied in the sixties and
seventies of the last century. This has led to certain compilations which have
remained classic text books at the undergraduate level for the last 40 years.
Among these are the White Book for C, the Cinderella Book for Automata, the
Dragon Book for
Language Processors. The knowledge contained herein is more than sufficient. As far as the last two are concerned they not necessary for most jobs in the outsourcing industry. However it is essential to note that quite a few of these subjects have been ordained, by the powers that be, to be essential to the curriculum and the students all over have to clear the same. The masses of persons required for outsourcing is in millions and requires a mass of self-taught instructors.

In computer science
education a core subject we have selected for which there is an acute shortage
of faculty is the area of Design and Analysis of Algorithms, popularly called
DAA by the student community. For a major portion of the subject in the Indian
computer science and software area the classic text by Horowitz et al[1] has remained
the favorite with the boards of studies of various educational institutions. The
international scene may have accepted other renderings of the area. The subject
also has the difficulty of having an acute shortage of faculty who can impart
instruction in the same. Combined with data structures it is essential in
induction training programs in the training and outsourcing software industry.

The intake of the Indian
engineering colleges over the entire country runs into lakhs
of students. Assuming that the average teaching scope of one instructor is
about 100-200 students, tens of thousands of instructors are required per
subject. This is apart from the requirements of the computer training industry.
This requires that for some core subjects like DAA mass methodologies must be
in place for the mass creation of instructors. We suggest a scheme which we
have created after extensive experimentation over the last two decades, and
crystallized into working courseware over the last five years, at M J College
of Engineering.

The basic contents of a
DAA course can be defined to consist of about 30 basic algorithms. These
algorithms can be described employing either by a programming language like C,
C+ or JAVA or by informal algorithmic notations. We suggest a method used
historically in dBase in the childhood days of the personnel computer. This
was description by example called query by example. If a properly formulated
instance of an algorithm is simulated in detail then we have by generalization
the entire description of the algorithm. This reduces the core instruction in
DAA to a simulation of about 30 algorithms in step by step detail with a
properly chosen sample instance.

The instances of the 30
examples should be capable of wide reuse. It is seen that if examples are drawn
from widely available resources or the standard texts then there is a wide uniformity in their use
in the Indian environment. Algorithms not covered in the texts can be tackled
by using GATE problems which can be considered a free resource. GATE is a
competitive examination for entrance to IITs for postgraduate education and
some leading institutions in India. The previous question papers are in the
public domain and the problems on Algorithms there can also serve as a good,
standard, widely available and acceptable resource.

The selection of the
problems has also been influenced by the requirements of the SWITCH group of companies when
conducting induction training programs in data structures and programming in C,
C++ and JAVA. This is drawn from the requirements of a company in which one of
the authors has been actively involved in outsourcing during the period
1996-2003. The number of trainees experimented upon was about 1500.

The requirement of a mass
of instructors to be available in the engineering & computer applications colleges, and that too at short notice is a severe
limitation. To be taken into account is the rapid attrition of this mass of
instructors to the IT outsourcing industry. The major challenge is that the
instructors should be made acceptably competent in teaching and instructional
techniques in a small time frame and with the minimum effort on their part.

The first line of attack
is the exposition of the algorithms itself. In his directives for the
development of computer science education and the Indian software industry,
Prof C A R Hoare had pointed out that there was a major need to do away with
the unnecessary abstraction computer science has wound itself into. The basic
concepts of computer science were simple, made unnecessarily complex. He
suggested that common sense expositions are the way to proceed to tackle the
results of topics like concepts and algorithms.

Experimentation in common
sense expositions in the rendering of algorithms over the last two decades at
the public sector undertakings like
ECIL, various professional societies in Hyderabad like the IETE and
CSI, educational institutions under
Osmania University, JNTU, BITS, Kakateya University, Nagarjuna university etc., outsourcing industries like
Satyam computers, social charitable and
social expositions under the auspices of
the Lion’s club and other forums were attempted
by the authors. These common sense expositions were related to the
social and cultural requirements in an Indian setting. The audience is drawn
from feudal agrarian environments of towns, and villages without the necessary sophistication
of environments the industrial and information
revolutions bring. Over a period of time we have found that common sense
expositions and rendering of the problems in the algorithms were possible and
widely well accepted and received by the audiences.

Since the area of
algorithms is basically mathematical it is possible to have an interpretation
of an algorithm in a particular setting. Mathematical abstractions have an
ubiquitous component in that common sense interpretations of a mathematical concept
or problem can be found in any area of human thought and action. Thus
regardless of the environment being feudal or modern, whether it belongs to the
agrarian, industrial or information revolutions, whether it is urban or rural
we can find common sense interpretations to algorithms. However, commonsense
interpretations are culture dependent. Thus what may be a commonsense
interpretation in a culture or in a particular geographical region may not be
considered commonsense in another culture or in another geographical region.
Thus common sense interpretations have to be localized like the search results
in Google and other search engines.

It is a well known fact
that visual methods are superior to text. In the ancient Chinese saying: a
picture is worth a thousand words. Early expositions of Data Structures and
Algorithms in the initial formative days of programming and computer science
were highly mathematical. An example is the use of Iverson’s APL as a tool for DAA[4]. The classic work of Knuth[2]
culminated in popularizing visual methods for data structures. The fundamental
statement of almost all algorithms of practical interest using ADT’s is known[3]. To this set may be added a few to complete the collection[8].

Completeness and rigor are
claimed in the exposition of algorithms by some sources[8].
However these may not be requirements in the mass educational requirements for
the outsourcing software industry. Expositions where the formally stated
algorithms and associated data structures can be naturally visualized and easily
mapped to the C, C++ or JAVA programs seem more relevant to the outsourcing
industry[1]. It has been noticed that mediocre and above average students feel
the expositions with rigor and formality give the impression of the last word
in the algorithm or its formal treatment being said. Some expositions allows a continuous
development, modification and varied implementation of the algorithm to be
easily visualized[1]. This allows easy implementation in major popular
programming languages
with varied data structures. This is more suitable for preparing the
student for a professional career in the software outsourcing industry.

Algorithms are to be
studied along with the data structures used for the algorithm[1]. Even if ADT’s
are used, they can be visually represented in colorful, rich user friendly using tools easily
and widely available worldwide with MS-Office.

In our experimentation
over the last five years a method initially used was to have custom plastic pieces of various colors
for arrows and numbered colored round pieces for nodes to simulate algorithms
using the tree data structures. Square numbered plastic pieces of various
colors were used for the simulation of linked lists. This was necessitated as
there was at times no electrical connection in the remote geographical area
being considered. There was at times no access to paper or a blackboard. There
was no access to the PC as the charge on the same lasting for a reasonable amount of time was not
possible. Attempts to use these plastic
pieces for instructional purposes in the areas of data structures and
algorithms had the disadvantage that an error in the presentation with a
detailed simulation of the algorithm can have catastrophic pedagogical effects.
Also it was difficult to keep track of the instantaneous descriptions or
snapshots of the computation, and one could not backtrack to a previous
position.

The situation has changed
over the last few years with the advent of netbooks
with rapid growth of disk space in the ubiquitous personnel computer. (Note we have said personnel computer, rather than personal computer, as it is a shared resource in a class, a family or in a social circle, in most of India.) The use
of presentations using the easily available MS-Office was restricted to
megabytes of storage a decade ago. Large graphical images and content could not
be used. The high prohibitive price in India of writing on a CD-ROM a decade
ago, the low storage capacity of floppy drives, low disk capacities, small RAM
memories and compared to today the low processing speeds did not allow bulky, highly graphic
presentations to be used in the environment. The recent explosion in disk
capacities extending to terabytes allows gigabytes of storage to be easily
spared for a powerpoint presentation, presented in parts.
The ability of many peripheral devices to draw power from the USB port has been
a boon. The has been rapid rise in RAM capacity to gigabytes and the rapid
increase in the processing speeds and methods of processing in current easily
affordable first or second hand, personnel computers. This allows routine rich, colorful, user
friendly, high graphic content to be created by persons of ordinary skill and
talents, in a few hours or days. The availability and affordability of high capacity
pendrives, by all levels of society, allows easy transportation and distribution of
presentations requiring gigabytes of storage at very little cost or no cost at
all.

The technology
as available now allows multiple
snapshots of the entire computation. This is akin to the instantaneous
descriptions of the computation being recorded at each time unit by a slide, or a small ordered set of slides, in
the presentation. The use of such snapshots is very common in theoretical
computer science like the simulation of an automata like a Turing Machine[6]. In fact it is useful for the entire simulation,
in excruciating detail of a finite computation, or the sketch of some infinite
computations, possible on many
deterministic and nondeterministic computational devices.

Thus the
technology widely, easily and
cheaply available in India allows the medium of high graphics oriented powerpoint
presentations for all computer science
and software oriented subjects. We have found that in our presentations
on algorithms each algorithm, with suitable sample data as input, can be described in detail in about 500 to
1000 power point slides using upto half a of gigabyte of storage, in either one
presentation or a group of them. The exposition proceeds by noting that what an
instructor should do in the class, in a period of one or two hours, is a step
by step development of the algorithm by executing it for a suitably chosen
sample input. This is translated into a slow step by step sequence of annotated
power point slides in a method akin to the classic development of Walt Disney
movies like Snow White and the Seven Dwarfs. Each step is described in
excruciating detail by a new power point slide, thus requiring hundreds of
slides per algorithm. This allows the student or faculty to reuse the
presentations indefinitely for future recapitulation and revision. The normal
development time is 20 manhours of work for an hour
of presentation on the average. The basic requirement however is a mastery of
an excruciatingly detailed simulation process of an algorithm and its data
structures for a finely grained presentation to mirror the same.

Alternatives
to the same are seen on the internet for a long time. Simulations by JAVA applets of algorithms abound on
the internet. These perhaps give a visual representation. An algorithm has to
be simulated by hand for an average human being to understand it. There is no
escape from this requirement. The alternative we suggest is that it can be
watched as the presentation gives this simulation in detail as if by hand.
Historically this was done by pencil and paper and the use of the same was
advocated, as opposed to just doing it mentally[2].
Thus the JAVA simulations on the
internet by applets do not result in the knowledge of how the algorithm works
to be transmitted to the user. They do not also give the entire snapshots of
the computation in excruciating detail, tailor made for use by human teachers of different cultures.
It may be suggested that the presentations be automatically generated. The
software may be developed but what is required is different. One human being
should go through the excruciating process in great detail, with dynamically
varying commentary suited to the audience, for every instantaneous description
of the computation or slide of the powerpoint
presentation. This involves
stepping through the instantaneous descriptions and explain them
to another human being in detail without error.

To make the presentations
widely reusable and acceptable the data for the algorithms is drawn primarily
from previous GATE papers and secondarily from standard texts. This
allow the presentations to be used for notes as a supplement to the
standard syllabus contents of DAA, in most colleges and universities in India.

The presentations have
been used with a variety of audiences. They have been adapted to the curriculum
of the DAA syllabus of about half a dozen universities so far. They have been
experimented with instruction in GATE classes. The instruction of students in
rural engineering colleges has proved to be a challenge. Some colleges have
students who have ranks in excess of a lakh in EAMCET,
the common entrance test for engineering in Hyderabad. In experimenting with
the instruction of DAA in rural engineering colleges it was found that the low
ranks of the students were not problems of IQ. The low ranks in most cases has
been the effect of a sudden change to the medium of instruction changing from
Telugu or Urdu to English at the college level. By generalization the situation
is the same throughout India. The bulk of the population is educated in regional languages
at the school level. A transition to English as a medium of education occurs at
the college level.

In this connection a major motivation was the directive of the legendary Prof E W Dijkstra, both orally and in writing (through a EWD) to one of the authors. He held that the natural language used by a human being for elaboration in software and computer science did not matter. What was required was a mastery of the natural language. Thus the medium of instruction being in regional languages does not matter, in the long run. A temporary discomfort of about a year is felt by the student when a transition to English as the medium of education occurs at college level. In parts of India the regional language is employed by software engineers involved in outsourcing. The client outsourcing may be in Europe, America or Japan.

It was found that as the presentations are
basically pictorial in nature. They have a high requirement of mastery of mathematical concepts which can be stated in
common sense terms. They are basically natural language independent. They can
be adapted to expositions in any natural language. Thus the use of the presentations aids in the
understanding of other areas of computer science and software.

The rapid growth of the
global village is evident around us. The last decade and especially the last
five years have seen the global village effect reach remote villages and towns
in India. On the other hand the rapid rise in real estate, the collapsing
strain on the infrastructure of large cities is evident. The shift of the
outsourcing industry to the interior regions of India and the Third World is
being actively considered. In such a case the requirements of skilled and
competent software professionals in the interior becomes essential. We feel
that the use of the rapid growth of technology has to be used. This will allow
rapid growth of the software outsourcing industry for employment of the
graduates of the colleges. Our effort is a step in this direction to cater to
mass development of instructors in computer science. As a parallel line of
approach we tackle mass training and education in computer science subjects.

The aim is to distribute
the presentations on a no profit basis to a wide variety of students and
faculty and obtain feedback on their use for mass training and education. The
total storage capacity requirements of the presentations runs
into gigabytes. Wide distribution over the unreliable and not always available
Web in India is not possible. Also the bandwith
widely available economically on the Internet to the common person is limited. The
alternative is free distribution via the medium of pen drives. Either of the
authors can be contacted for a copy of the presentations. They can
easily be rearranged to cater to most of the curriculum requirements in the
subject for most educational and training institutions. Free modification, adaptation and expansion of
the presentations can be to the choice and taste of the student or faculty. We would
welcome a natural language translation of the presentations into the major
regional languages of India, and experimentation with expositions at the
primary and secondary school level. It may be noted that we have said even the
primary school level. The classic exposition is that all algorithms can be
reduced to about 30 easily stated problems[3].

The 30 problems considered by us have some
aspects where a simple common sense rendering can be easily explained to primary
school children. It may not be normally possible to explain the intricacies of
the algorithm and data structures in full detail to this level of audience. We
have found that graphic simulations of backtracking algorithms like the 4 queens problem, the Hamiltonian cycle problem and the graph
coloring problem are easily grasped by primary school children when presented
by the medium of our presentations. The problem statements of many of the algorithms can be introduced at this level with simple
commonsense renderings. For this purpose
algorithmic notation is not used. We follow the tradition used by innumerable
cultures for centuries in
the pre ALGOL-60 era and
explain the algorithms in natural languages with commons sense
explanations. The sacred constructs and concepts of ALGOL-60, PASCAL, JAVA, the
development of algorithms using pidgin
varieties of these and the associated venerable formal verification proofs are
left for a much later stage in the life
of the primary school children.

Our presentations span 30
problems which are basic to the DAA area and form the core of any curriculum in
DAA at the undergraduate level of a computer science or information technology
engineering baccalaureate course or a degree in computer applications in India.
The presentations have been prepared with an effort of about 1000 person hours
over a physical time duration of six months. They have
been experimented upon with audiences of various backgrounds, drawn from the
entire country, totaling about 3000 persons in various universities, colleges, coaching and training
centers in the southern states of India.

For detailed understanding
of the proof and time complexity of the algorithm common sense explanations can
be given. This requires that the culture independent formal mathematical
apparatus be dismantled. A particular suitable commonsense interpretation of
the problem be taken suited to the local cultural
environment. The construction then be recast in the
local setting. The
construction if properly chosen can be made to be very user
friendly, intuitive, and common sense based. Care should be taken no to offend
the cultural sensibilities of the local environment. Acceptable comparisons,
statements, and comments on ways of life in one environment may not be
acceptable at all when the environment, culture, geographical or economic situation of
the audience varies even slightly. What is common sense in one part of India
with one type of audience, may not be understood in
another part of India or same part of India with slight variations in the type
of audience.

A particular cultural
environment that seems to be universal is to use the world of nursery and
primary school children. Common sense examples from this world seem to have an universal appeal and are basically culture independent.
They are also universal and powerful and can cater to the interpretation of any
mathematical construct, concept or theorem. Thus they can be used for
commonsense renderings of algorithms. The world of Winnie the Pooh and Tigger seem to have universal appeal and will not result in
the instructor stepping on someone’s cultural toes.

For a soft copy of the
presentations, the logistics of obtaining the same and tailoring the same to
cater to a particular curriculum the authors may be contacted by e-mail. As
pointed out earlier in the existing Indian environment, the Web cannot be used
cost effectively for distribution, the presentations are too large for normal
CD’s, perhaps DVD’s would do but the cost of cutting them involves
administrative, economic and time overhead. Hence the ancient snail mail or its
variants, with high capacity pen drives, the social network and the public
transportation network have to be used.

APPENDIX

We now proceed to exhibit
that commonsense rendering of many concepts of computer science is possible. In
particular we take twelve computationally related problems and restate them in
a commonsense way.

In all areas of knowledge
in Arts, Sciences, Engineering and Technology a common modeling device is
combinatorial optimization. In the area of combinatorial optimization some 3000
hard problems have been isolated by Computer Scientists and mathematicians
which though deceptively easy are extremely hard to solve by the computer or by
hand. Among these problems are the NP-complete problems.

The
NP-complete problems are problems practically arising in computation in
industry, research and all activities of human endeavor. They have the
interesting property that all attempts to solve them over the centuries have
yielded problems of exponential time complexity. This restricts the input
problem size to about 40 elements. Practical models of problems have 100 to
1000 elements.

To
understand the concept of NP-complete problems let us consider the same from a user friendly
point of view. Let us consider the actions of the early Christians and Jesuits
in their pursuit of new converts to their religion. When they go round the
world to a new kingdom or tribe consisting of a million or couple of thousand persons, a
long, laborious and time consuming
method is to convert each one of the million or thousands of persons.
Alternatively a much simpler method may exist and this is what they
followed. What they did was to isolate a
kingpin person in the new kingdom or tribe. This could be the king, the chief himself or
a very influential noble. If that person could be converted then all the
million people of the kingdom or the entire tribe will fall in line and get converted. The king,
the chief or the
noble involved is called the “-complete” person. The same technique as per
Sociology is followed when one religion wants to swallow up another, or one
culture would like to swallow up another. Isolate a kingpin and convert him/her
then all fall in line. This is what happened as per Russian history in Russia.
The kinpin converted himself
to European culture and everybody fell in line and switched.

The
same problem is followed by a teacher in the class. If the class if unruly the
long way is to convince all the students in the class to behave. For
undergraduates this could be 200-300 students to be convinced. This is a long
and laborious. Alternatively, get hold of one kingpin student, the leader and
discipline him. Then all the students fall in line. This is what we mean when
we say -- “make an example of”.

The
method is followed by the police to control the goons in town, or break up an
agitation led by some politician as the eye of the cyclone. Isolate the kingpin
and discipline him. Everyone falls in line. This is the concept behind the
NP-complete problems.

The
existence of these kingpin problems was originally shown by Cook[9],
who showed the existence of the first NP-complete problem, called satisfiability. Karp[10] isolated
21 classic problems which were also shown to be kingpins or NP-complete
problems. For centuries these
problems had led countless
mathematicians, of all calibers, to lifetimes
of despair and found to be extremely hard to solve in a reasonable way in a
short span of time.

In
simple terms, we have two classes of problems: the goons and ordinary citizens.
We want to reform the goons and make them ordinary citizens. Cook[9] isolated the venerable kingpin goon, the satisfiability problem. If this goon can be reformed to an
ordinary citizen then all goons can be reformed. If the kingpin goon is incorrigible and
cannot be converted by any means to an ordinary citizen then the goons form a
distinct class and will contain many goons who cannot be reformed.

The
general process of showing that a problem is NP-complete can be described in a
user friendly way. Let us take the
kingdom of the goons. The basic requirement to be a kingpin goon is that one
must be a bonafide goon in the kingdom. This is like
some countries that allow anyone to become the President of the country but the
basic requirement is that one must be a bonafide citizen
of the country. The next step is that there is already a club of kingpin goons.
Cook started the initial membership with the satisfiability
problem. Karp further populated it by an aristocracy of 21 goons. This club has
exclusive membership. Membership is by invitation. An existing and known member
of the club, a bonafide kingpin goon, must go through
the procedures of converting a goon from the kingdom to a kingpin goon. He must
demonstrate that the goon chosen for elevation is a bonafide goon
in the first place, then that he is a peer of the kingpin goons, thus elevate him to the exclusive membership of the club. After Karp
large classes of goons were shown to be kingpins[1],
and the club effectively became a
democracy . Today thousands of goons in the kingdom are known to be wearing the
‘dunce cap’ of being kingpin problems. It was shown by Sahni[1] that there are no
approximations to the kingpin goons
being reformed to behave almost like ordinary citizens. Once a kingpin goon always a kingpin goon.

We
classify problems in two categories, decision problems and optimization
problems. Decision problems have a binary answer, yes or no. A solution exists
or does not exist. NP-complete problems are decision problems.

Optimization
problems are slightly different. Let us consider a user friendly example. We
would like to know what weight a weightlifter can lift. We call this an
optimization problem. We convert it to a decision problem by giving the
weightlifter two weights on small and one large. He easily lifts the small
weight. Then if he cannot lift the
heavier one then we try something midway. This partitions the weights between
the heavy and light weight into a lower and upper half. We proceed
to that half and repeat the process. At the end we end up with the weight he
can lift. Thus we convert an optimization problem to a decision problem. This
like the maximum height one can jump,
the maximum number of doughnuts a person can polish off in one sitting,
from how far away can one hear one’s teacher shout at a student, the minimum
bribe to be given to the government employee for a routine job etc. are all
examples of optimization problems. In principle they can all be converted to
decision problems like in the weightlifting example, though in practice it may
not work with a rapacious person in the bribe case.

From
the set of 3000 NP-complete problems augmented by a couple of thousand approximations
to the same, we select a basic set of six problems and an augmented set of
another six problems, making a dozen overall. We list the problems below with
both a user friendly rendering of the problem and a formal statement of the
problem.

The First problem is the
Boolean satisfiability problem. This can be related
to circuit design where if we have a combination of AND, OR and NOT gates will
we get an output signal. It can be related to a statement made up of clauses
which all have to be true. A clause in turn is a combination of variables which
can be true or false. The entire statement is made up of n variables. It is a
decision problem as we only have to decide if a combination can yield the value
true.

The Second problem is the
clique problem. In any social network there will be some special individuals
who form a clique. For example in the area of Information Science we have the
concept of the Invisible College or High Priests in some area of knowledge who
form a clique. In the area of Information Science we learn that all
organizations have their Invisible Colleges, which keep track of all
information in the organization. This can be modeled by a graph where the nodes
are the people with one node per person. Two nodes have an edge or are connected
if the two persons have a connection in the social network. We are to determine
if a clique of some give size k exists in the graph and hence in the social
network it models. This requires the determination of a subset of k nodes in
the graph where each node is connected to the remaining nodes. This is a
decision problem as we want to know if a clique of size k exists-yes or no.

The Third problem is the
vertex cover problem. In a social network we isolate a number n of persons. These persons
are key persons with a wide network in the social circle. The problem is to
determine is a subset k of these n persons cover the entire population in the
social circle. In formal terms we take a graph and have to determine if a
subset k of the n nodes of the graph covers all the edges of the graph. This is
a decision problem as we want to know is a vertex cover of size k exists—yes or
no.

The Fourth problem is the
Hamiltonian cycle problem. We are to start from home, visit the houses of n relatives one after
another and reach home. No relative should be visited twice. This problem is modeled as a graph problem
where we are to visit the n nodes of a graph, enter and leave each node exactly
once. This naturally occurring problem is extremely difficult to solve. Consider
the genome map assembly problem. We have millions of small pair lengths. Each
pair length can be modeled as a node of a graph. If a pair length comes after
another then put a directed
edge between the former
and latter. Finally, have an edge between the last pair and the first. If we
can find a Hamiltonian cycle in the graph we have found the correct assembly.
For another example consider the old Walt Disney cartoon movie, Snow White and
the Seven Dwarfs. This movie is made up of thousands of laboriously hand
painted slides, which vary slightly from each other. They are to be shown in
the proper sequence. Suppose they got mixed up and we are to rearrange these
thousands of slides in the proper order. Each slide can be modeled as a node of
a graph. If a slide follows another then put a edge
between the former
and latter. Finally, we have an edge between the final slide and the first one.
If a Hamiltonian cycle exists in the graph then we have found the proper order
of assembling the mixed up slides. This is a decision problem as we want to know
if a Hamiltonian cycle exists—yes or no.

The Fifth problem is the
Travelling Salesman Problem(TSP). This is a
generalization of the Hamiltonian cycle problem. If each bus stop in the city
is the node of a graph, and a bus from one bus stop to another exists then
introduce an edge between the nodes. The cost of travel between the stops is
the weight of the edge. We are to make a circuit or ‘chakkar’
in the graph of least cost, starting from an initial bus stop visiting all the
bus stops once and coming back to the first stop, with the total cost of travel
a minimum over all the possible cycles. This problem has been used in USA for
minimize the cost of travel
of a person who had to collect all the money from the pay phones
every day in a city or town. A milkman in the Third World will find it useful
if he has to deliver milk in a hundred
houses every day, or newspaper boy who
has to deliver the newspaper in over a couple of hundred houses every day with
the minimum recurring cost. Globalization and liberalization has burdened the
milkmen and newspaper boys in the Third World with gas guzzling vehicles for
transport. This requires them in due course to use the Travelling Salesman
Problem. As another example consider the problem of donkeys. For centuries the washereman used to use these beasts of burden extensively
in India. Lakhs of donkeys
were around. Globalisation and
liberalization have burdened the washerman with a gas
guzzling vehicle. The population of donkeys has reduced to a couple of
thousands. These poor things are now being eaten up by some humans who relish
their meat and will become extinct shortly. The washerman
on the other hand is now saddled with a personal computer and has to use the Traveling Salesman Problem to
control his fuel costs. This is an optimization problem as we want the circuit
of least cost. To convert to a decision problem we ask if a Hamiltonian cycle
of cost less than k exists---yes or no. We proceed as in the weight lifting
problem. Then we convert the problem to a decision problem.

The Sixth problem is the
Graph Coloring problem. If the map of the world/universe is to be colored and
two adjacent countries/worlds are to be colored differently, we are to determine if for N
countries/worlds a palette of k colors is sufficient. Another rendering of the
problem is the determination if k colors are sufficient for traffic lights, in a junction of N roads. The problem is formalized by a graph with
one node for each country. Two adjacent countries are modeled by an edge
between the nodes representing the countries. We are to color the nodes of the
graph with the palette of k colors with the constraint that two adjacent nodes
do not have the same color. This is a decision problem. We want to know if k
colors will do—yes or no.

The Seventh problem is the
Feedback Node
Set(FNS) problem. The Indian Railways have one of the largest railway networks in the world. Let us
count the railway stations and assign to them the number 1 to N. We are to
determine if for a given number k, we can select k railway stations with the
constraint that a person can make all the
tours in the Indian Railways,
originating from one of the k stations, taking connecting trains and
ending up finally at the starting station. The problem has applications in code generation in compilers. A compiler
translates a high level language program to the machine language of a computer.
The computer has
either locations in RAM or in registers. If data is stored in the
registers the computation is ten times faster than if the data is stored in the
RAM. Registers require extra
circuitry and are expensive. The problem is to minimize the number of registers
required to generate the code. This problem can be reduced to the feedback node
set problem. The problem is modeled by having a graph of N nodes. We are to
determine if for a given k, we can select k nodes such that all
cycles in the graph contain at least one
node from the k selected. This is a decision problem we want to know if
a FNS of size k exists—yes or no.

The
Eighth problem is the Feedback Edge Set(FES) problem. Consider again the Indian
railway network. Let there be |E| trains and N stations. We are to determine if
for a given k, we can select k trains such that they include all tours in the
Indian railways. This is modeled by a graph of |E| edges and N nodes, and we
are to determine for a given k, if we can select k edges such that all tours
include at least one edge. This is posed as a decision problem. We want to know
if a FES of size k exists---yes or no.

The Ninth problem is the
Set Cover problem. We have N goons, who
form themselves into gangs G1, G2,---,Gn, with the
possibility one goon being in more than one gang. We are to determine a subset
of gangs that contain all the goons. The problem is modeled by having a set S
and a family of subsets of S. We are to determine from the family of subsets, if some of them
cover the set S. This is a decision problem.

The Tenth problem is the
Exact Cover problem. We have N goons,
who form themselves into gangs G1 G2,---,Gn, with the
possibility of one goon being in more than one gang. We are to determine a
subset of gangs which are pairwise disjoint that
contain all the goons. A collection of gangs is said to be pairwise
disjoint if when we take any two gangs in the collection they do not have a
goon in common. The problem is modeled by having a set S and a family of
subsets of S. We are to determine
disjoint subsets from the family of subsets to cover the set S. The
problem is a decision problem. Does an exact cover exist? The answer is yes or
no. The next step is to compute all
the solutions.

The Eleventh problem is the Sum of Subsets problem. We
are to determine from a given set of integers a subset that sums up to a sum M
that is initially specified. This problem is akin to finding some money in hard
times that adds up to M. This is with
the bits and pieces of monies that have been tucked away over the years in
various places. This problem has been called the easiest hard problem and has
proved difficult to solve. Alternatively we want to pool up an amount M for a
splurge from various sources. What are the sources that will add up to the
amount? It can be efficiently solved by dynamic programming methods if the
numbers are small in size but if the numbers have as many digits as the
cardinality of the given set then the problem becomes difficult. Normal
requirements are for 100 or 1000 digits wheras we can
handle 40 digits easily. This is a decision problem. Does a subset exist? The
answer should be yes or no.

The Twelfth problem is the
0/1 Knapsack problem. We are to pack up our suitcase for a long international
air journey with some allowed N items. Each item has a profit if it is packed
and transported but associated with it is a weight. We have to stay within the
weight restriction of the airlines and maximize our profit. Let the n items
have the profits p1,p2,…pn and weights w1,w2,--wn and the weight restriction is M. We are to determine a
subset of the items 1..n, whose
cumulative weight is less than or equal to M and the profit is maximal. This is
an optimization problem. We convert it to a decision problem by asking whether
a solution exists greater than for a lower bound of Ml and less than an upper
bound of Mu. The answer is yes or no in each case. So it is a decision problem.
Just as in the weightlifting example we
proceed to obtain the solution, by considering a weight in between. Thus
we convert the optimization problem to a decision problem.

The process of demonstrating
that each one of the above problems is NP-complete lends itself to user
friendly, graphical restatements of the
constructions and proofs. For this we
have found that we may have to recast the constructions and proofs with common sense explanations. Also we have to
modify history a wee bit. We have to
redo how ancient problems were determined to be NP-complete in the first place.
Also it turns out that one specific problem, the exact cover problem, is some sort of a golden goose. Many NP-complete
problems can naturally, visually, pictorially and hence graphically be
expressed using the exact cover problem. This becomes easier if we augment the
elements of the sets in the exact cover problem. One way is to allow some of
the elements to be multisets. The other method is to
attach semantics and semantic routines to the elements. This is akin to the
strategy followed in syntax directed compilers[7]. Such an augmented exact
cover problem lends itself to nice graphical presentations of NP-complete problems.
In fact we can digress and note that computations using the automata &
grammars of the Chomsky hierarchy can naturally and neatly be expressed in this
augmented exact cover problem[6]. Thus the venerable satifiability
problem can perhaps be retired. The more visually colorful, active, and younger
exact cover problem and its variants can be used in user friendly presentations.
The augmented exact cover problem with semantic routines is akin to a special
case of constraint data bases.

References:

[1] Horowitz , E. and Sahni, S. K., Computer
Algorithms, Galgotia, 1993.

[2]
Knuth, D. E., The Art of Computer Progamming, Vol I, Addison-Wesely, 1971.

[3]Aho, V., Hopcroft, J. E., and Ullman, J.D., The Design and Analysis of Computer
Algorithms, Addison-Wesely,1979.

[4]
Iverson, K. E., A Programming Language, John-Wiley and sons, 1962.

[5]
Kernighan, B. and Ritchie, D., The C programming language, 1968, THE WHITE
BOOK.

[6]
Hopcroft, J. E., and Ullman,
J. D., An introduction to Automata, Languages and Computation, 1977, THE
CINDERELLA BOOK.

[7]
Aho, A.V., and Ullman,
J.D., Principles of Compiler Design, 1977, THE DRAGON BOOK.

[8]
Thomas H. *Cormen*,
Charles E. Leiserson, Ronald L. Rivest,
and Clifford Stein, Introduction to *Algorithms***.**

**[9]
**The
*Complexity* of *Theorem*-*Proving Procedures*.
Stephen A. *Cook*.
University of Toronto. 1971.

**[10]** *REDUCIBILITY AMONG COMBINATORIAL
PROBLEMS*. Richard M. *Karp*.
University of California at Berkeley.1972.

"The brontosaurus moved deeper into the swamps when the mammals took over the forest, but one day it ran out of swamps."

BRINGING THE THEORY OF COMPUTATION TO PRIMARY & SECONDARY SCHOOL CHILDREN ....

click here: INTRACTABIITY FOR PRIMARY SCHOOLS

THE PROOF OF THE PUDDING IS IN THE EATING .