Find the minimum number of rows needed

Assignment Help Basic Computer Science

Reference no: EM131366369

Your job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form "i hates j". If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.

(a) Give an algorithm that orders the line, (or says that it is not possible) in O(m + n) time.

(b) Suppose instead you want to arrange the children in rows such that if i hates j, then i must be in a lower numbered row than j. Give an efficient algorithm to find the minimum number of rows needed, if it is possible.

Reference no: EM131366369

Questions Cloud

Describe the founding of european nations first colonies : Explain current beliefs about how the first peoples settled North America, and discuss the ways in which they became differentiated from one another over time.Describe the founding of European nations' first colonies in the New World. Give 2-3 exam..

Mode of inheritance for this disease-trait : Research the mode of inheritance for this disease/trait? Why? If you are not able to find a specific mode of inheritance, provide a hypothesis for the mode of inheritance. Explain your thinking here very thoroughly; this should take up about half ..

Internalization important for respiration in animals : Why is internalization important for respiration in animals? And what does it mean?

Respiratory and gastrointestinal systems : Topic: Systemic Pathophysiology of the Respiratory and Gastrointestinal Systems Objective: Discuss a disease, condition or syndrome affecting the cardiovascular system and current research, events, or interesting facts about the disease/condition/..

Find the minimum number of rows needed : Suppose instead you want to arrange the children in rows such that if i hates j, then i must be in a lower numbered row than j. Give an efficient algorithm to find the minimum number of rows needed, if it is possible.

What should we make of edward carrs observations : What is history? What should we make of Edward Carr's observations? How do we take into account how History, as a discipline, has changed in the 19th and 20th centuries? Now that we have had a sampling of David Christian's introduction to "Big His..

Draw a map of the supply chain for leapfrog : Draw a map of the supply chain for LeapFrog, including the retailers, Capable Toys, and suppliers of key materials (i.e., Tyvek). Which supply chain partners are upstream of LeapFrog? Which are downstream? Which partners are first-tier suppliers? ..

What are the effects of childhood obesity : What are the effects of childhood obesity? Research intensively on the effects of obesity, to the individual and society and possible solutions. Font 12, apa,atleast three references.

Creation science and intelligent design creationism : Write an essay on the differences and similarities of creation science and intelligent design creationism, and how do they stand up as actual science?

User Account

All Pages