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