THE DEFINITION OF

THE PROBLEMS

AND

THEIR INFORMAL DESCRIPTION

**01CHAPTER
ONE****-SUCHI THE ****BABY**** ****BEAR**** ****GETS**** ****READY**** ****FOR**** ****SCHOOL**

*THE 0/1 KNAPSACK PROBLEM*

*GOOGLE SEARCH WORDS: THE 0/1 KNAPSACK PROBLEM*

**CONSTRAINTS**

**1. Suchi Bear has to choose clothes to
wear to school.**

**2. There are over 40, perhaps a 100 or 1000 pairs to choose
from. They have been collected over the years.**

**3. There are combinations of clothes she can choose.**

**4. Every night Mama Bear and Aunty Bear keep on arranging her
wardrobe.**

**5. They throw away a lot of clothes every day.**

**6. Papa Bear, Grandma Bear and Uncle Bears keep on adding
dresses for her every day.**

**7. Baby Bear has to maximize the best impression she will create
in her clothes.**

**8. Early in the morning she has to choose her clothes.**

**9. Nobody is there to help her.**

**10. While she is choosing her clothes no new clothes come or old
clothes thrown out.**

**11. The number of clothes she can wear at a time
are limited.**

**12. For over 40 clothes it will take years for Baby Bear to choose the best combination of clothes.**

**13. Baby zebra is gifted and can guess the answer easily.**

**14. She has only got to go through the list of clothes once.**

**15. Then one only has to verify the answer.**

**16. Baby zebra is gifted with nondeterminism.**

**02CHAPTER TWO-SRIDHAR BEAR AND THE VERY SCARY STORY**

*THE EUCLIDEAN TRAVELING SALESMAN PROBLEM*

*GOOGLE SEARCH WORDS:THE EUCLIDEAN TRAVELING SALESMAN PROBLEM*

*CONSTRAINTS*

*1.
**The monster will visit all the baby animals in the forest.*

*2.
**There are over 40, perhaps 100 or 1000
families with baby animals.*

*3.
**The monster wants to frighten the baby
animals.*

*4.
**The monster has a map of the forest.*

*5.
**It is raining cats and dogs.*

*6.
**Many roads become unusable, the monster cannot
use them.*

*7.
**King Lion keeps adding new roads every day.*

*8.
**The monster must frighten all the children.*

*9.
**Can the monster visit all the children in the first place? Yes
or No. This is the Hamiltonian cycle problem.*

*10.**For 1000 baby animals
it will take eons of time for the monster to find out the answer.*

*11.
**The monster must find the shortest cycle to all the
children. The smallest shortcut in the Traveling Salesman Problem.*

*12.
**It will take the monster eons of time to find
the shortest route.*

*13.
**Baby Zebra can guess the answers and we only
have to verify the answer.*

*14.
**Baby Zebra is gifted with nondeterminism.*

*15.
**Baby Zebra has only glance through the map
once, with only one glance
at each available road.*

**03CHAPTER THREE-THE EDUCATION OF BABY BEAR**

*THE SUM OF SUBSETS PROBLEM*

*GOOGLE SEARCH WORDS:THE SUM OF SUBSETS PROBLEM*

**CONSTRAINTS**

**1.
****There is list of integers of monies tucked away.**

**2.
****There are over 40, perhaps 100 or 1000 such places.**

**3.
****We have a target sum to raise.**

**4.
****It will take eons of time to find an answer for the exact
target to be met.**

**5.
****The question is can the exact target be met.**

**6.
****We want the exact target not approximate.**

**7.
****Baby zebra can guess the answer and we can verify it.**

**8.
****She is gifted and has got to glance through the list of
items, their weights and profits once only.**

**9.
****She has the power of nondeteminism.**

**04CHAPTER FOUR-THE BEAR FAMILY GOES VISITING**

*THE HAMILTONIAN CYCLE PROBLEM*

*THE TRAVELING SALESMAN PROBLEM*

*GOOGLE SEARCH :THE HAMILTONIAN CYCLE
PROBLEM*

*THE TRAVELING SALESMAN PROBLEM*

**CONSTRAINTS**

**1.
****There are over 40, perhaps 100 or 1000 relatives.**

**2.
****It is raining, there are riots.**

**3.
****Train and bus services are disrupted.**

**4.
****Roads are disrupted at places.**

**5.
****New emergency roads have come up.**

**6.
****The relatives must all be visited in any order.**

**7.
****There are some constraints.**

**8.
****No relative should be visited twice.**

**9.
****You must start at home and reach back home.**

**10.****The question is can we come back home?**

**11.****We must visit spending
the least amount of money.**

**12.****Can we come back home?
Yes or No. This is the Hamiltonian cycle problem.**

**13.****It will**** take eons of time to answer for 100 or 1000 realatives.**

**14.****We want the least cost
tour.**

**15.****This will take eons of
time to answer for 100 or 1000 relatives.**

**16.****Baby zebra is gifted.
She glances through the list of relatives. She glances through the list of
available trains and buses only once. **

**17.****She can guess the
answer, in almost the time she takes to glance through the list. We verify her guess.**

**18.****She has the power of nondeterminism.**

**05CHAPTER FIVE-MAMA BEAR VISITS THE BABY BISON**

*THE 0/1 KNAPSACK PROBLEM*

*GOOGLE
SEARCH** WORDS:THE 0/1 KNAPSACK PROBLEM*

**CONSTRAINTS**

**1.
****Mama Bear must pack up 40 or more things.**

**2.
****Typically she must pack up 100 or 1000 gifts.**

**3.
****She cannot take the fraction of a gift.**

**4.
****She can either take it or leave it ---for any gift.**

**5.
****If she can take a gift to Baby Bison there is a profit.**

**6.
****The weight of her suitcase increases per gift.**

**7.
****The airlines have a weight restriction,**

**8.
****Mama Bear must not exceed the weight restriction.**

**9.
****It is
too expensive to exceed the weight restriction.**

**10.****Mama Bear must choose
the best gifts, with maximum profit, within the weight restriction.**

**11.****For
a typical 100 or 1000 items**** it will take her eons of time to decide.**

**12.****Baby Zebra**** is gifted. She
glances through the
list of gifts, their weights and profits.**

**13.****She can guess the best
combination almost immediately.**

**14.****Mama Bear has only to
verify the answer.**

**15.****We say Baby Zebra is nondeterministic.**

**06CHAPTER SIX-THE SOCIAL CIRCL E OF EMILY THE SIBERIAN CRANE**

*THE SET COVER PROBLEM*

*GOOGLE SEARCH WORDS: THE SET COVER PROBLEM *

**CONSTRAITS**

**1.
****Emily the Siberian Crane has hundreds of friends, in over
40 places.**

**2.
****Perhaps she has friends in 100 or 1000 different places.**

**3.
****She wants to keep contact with all of them.**

**4.
****She wants to keep the list of contacts small.**

**5.
****She identifes key persons,
extroverts with large circles **

**6.
****She keeps track of some of these key persons.**

**7.
****Through them she can have a connection to all her friends in all
the places.**

**8.
****How does she choose these key persons?**

**9.
****All her friends and acquaintances must be covered.**

**10.****She wants thesmalles list of
these key persons.**

**11.****For 100 or 1000
friends the time taken is
eons.**

**12.****Baby zebra**** is very
clever.**

**13.****She is born gifted.**

**14.****She can guess the list of key persons by glancing through the list
of persons and their circles. She does not take much time for the guess. About
as much time as it
took her to glance through the list.**

**15.****Emily the Siberian
Crane has only got to verify the choice.**

**16.****The Baby Zebra is
gifted with nondeterminism.**

**07CHAPTER SEVEN-UNCLE BEAR AND THE INDIAN RAILWAYS**

*THE FEEDBACK EDGE SET PROBLEM*

*THE FEEDBACK NODE SET PROBLEM*

*GOOGLE SEARCH WORDS:THE FEEDBACK EDGE SET PROBLEM*

*THE FEEDBACK NODE SET PROBLEM*

**CONSTRAINTS**

**1.
****The Indian railways have thousands of trains and stations.**

**2.
****We want to participate in all tours.**

**3.
****A tour starts with a station and ends with a station.**

**4.
****From every tour we must cover a train.**

**5.
****It is raining as it is monsoon season.**

**6.
****There are riots and bandhs.**

**7.
****Some trains are not running.**

**8.
****Some special trains have been introduced.**

**9.
****Uncle Bear wants to take all the tours, or rather a train
in each tour.**

**10.****For 100 or 1000 tours
the choice of trains he should take will
take eons of time.**

**11.****Baby Zebra is very
clever and gifted.**

**12.****She can guess the
trains simply by going through the list of trains and the stations enroute.**

**13.****One has to only verify
the answer.**

**14.****She is
nondeterministic.**

**08CHAPTER EIGHT-BABY BEAR DOES TOO MUCH SHOPPING**

*THE BIN PACKING PROBLEM*

*GOOGLE SEARCH WORDS:THE BIN PACKING PROBLEM*

**CONSTRAINTS**

**1.
****Baby Bear buys up over 40 items, typically 100 or 1000
items at the Mall.**

**2.
****The Mall has carry bags of fixed size.**

**3.
****How many carry bags does she require?**

**4.
****It will take eons of time to compute, if she needs more than 2 bags.**

**5.
****Baby Zebra is very clever. She is gifted.**

**6.
****She goes through the list of items Baby Bear has purchased.**

**7.
****In about the same time as it took her to go through the
list, she guesses the correct number of shopping bags.**

**8.
****Only
her**** guess has to be
verified.**

**9.
****Baby
Zebra**** is nondeterministic.**

**09CHAPTER NINE-GRANDPA BEAR AND THE OLD AGE BILL**

*THE SATISFIABLITY PROBLEM*

*GOOGLE SEARCH WORDS:THE SATISFIABLITY PROBLEM*

**CONSTRAINTS**

**1.
****There are over 40, typically 100 or 1000 politicians.**

**2.
****They are in many, more than 3 political parties.**

**3.
****A politician may be in more than one party.**

**4.
****Every politician has an opponent who votes in the opposite way.**

**5.
****Some politicians may be absconding.**

**6.
****Grandpa Bear wants an old age bill passed.**

**7.
****It is enough if one politician from each party supports it.**

**8.
****Is there a collection of politicians whose support will ensure that the
bill will be passed?**

**9.
****It will
take eons of time to
calculate the answer for 100 or 1000 politicians.**

**10.****Baby Zebra is very
clever.**

**11.****She can guess the answer
by simply going through the
list of politicians, and
the list of members in each poltical party.**

**12.****She can do it in as much time as it takes her
to glance through the list.**

**13.****She is very clever and
gifted.**

**14.****She is nondeterministic.**

**15.****We only have to verify
her result.**

**10CHAPTER TEN-PAPA BEAR AND THE ****INVISIBLE**** ****COLLEGE**

*THE CLIQUE PROBLEM*

*GOOGLE SEARCH WORDS: THE CLIQUE PROBLEM*

**CONSTRAINTS**

**1.
****There are 40, typically 100 or 1000 researchers in some
area.**

**2.
****They are in different countries, over 3 countries.**

**3.
****Each researcher has an opponent he does not get along with.**

**4.
****Some researcher may be in more
than one country.**

**5.
****Researchers in the same country do not know each
other. They do not get along.**

**6.
****A researcher knows all the researchers in all countries
but his own.**

**7.
****Is there a collection of researchers, one from each country, who get along with all the others in
the collection?**

**8.
****For 100 or 1000 researchers this problem will take eons of
time to compute.**

**9.
****Baby Zebra is gifted, nondeterministic and clever.**

**10.****She can guess the
collection by going
through the list of reseacheres and
their affiliations.**

**11.****We only have to verify
the answer.**

**11CHAPTER ELEVEN-SANIKA BEAR PLAYS HOLI**

*THE GRAPH COLORING PROBLEM*

*GOOGLE SEARCH WORDS:THE GRAPH COLORING PROBLEM*

**CONSTRAINTS**

**1.
****Uma**** Bear plays Holi with her friends.**

**2.
****There are 40, typically 100 or 1000 friends involved.**

**3.
****All are playing Holi.**

**4.
****Uma**** wants to color all
her friends.**

**5.
****Among her friends if two of them are on cross terms with
each other then Uma should color them differently.**

**6.
****How many colors should Uma use?**

**7.
****We want the minimum number of different colors she
should use.**

**8.
****It will take eons of time to find out for 100 or 1000
friends. Every year the list of friends drastically changes.**

**9.
****Baby Zebra is very clever.**

**10.****She is
nondeterministic.**

**11.****She can guess the minimum
number of colors required.**

**12.****She merely goes to the list of friends and the persons a friend is on
cross terms with.**

**13.****In about the same time as it
takes her to glance through the list she
guesses the answer.**

**14.****Uma**** has only got to verify the answer.**

**12CHAPTER TWELVE- UMA BEAR AND NAUGHTY MICKEY**

**THE EXACT COVER PROBLEM**

**THE HAMILTONIAN CYCLE PROBLEM**

**GOOGLE SEARCH WORDS:THE EXACT COVER PROBLEM**

**THE HAMILTONIAN CYCLE PROBLEM**

**CONSTRAINTS**

**1.
****Uma**** Bear and Mickey go to
photocopy a book.**

**2.
****The pages are not numbered.**

**3.
****The drop the photocopies.**

**4.
****The whole pile of 40, typically 100 or 1000 pages is all
mixed up.**

**5.
****They have to put it back in order.**

**6.
****They know for a pair of pages what comes after what.**

**7.
****They have to put the whole bunch back.**

**8.
****It will take them eons of time.**

**9.
****Baby Zebra is very clever.**

**10.****She can guess the
order of the Xerox
copies. This she does merely by going throung the list of copies.**

**11.****Uma**** and Mickey only have to verify the result.**

**13CHAPTER THIRTEEN-THE MONSTERS FORM A CLUB**

**THE CONCEPT OF NP-COMPLETENESS**

**GOOGLE SEARCH:NP-COMPLETENESS**

**14CHAPTER FOURTEEN-THE CREATION OF A MONSTER**

*GOOGLE SEARCH WORDS:COOKS THEOREM*