Find the minimum number of rows needed

Assignment Help Basic Computer Science

Reference no: EM131361821

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: EM131361821

Questions Cloud

Describe role of organization play in reducing misuse drug : Debates surrounding definitions of gangs and identification of gang members will continue indefinitely. Using your textbook and outside resources propose (3) reasons why gangs are so difficult to define and classify. Next, hypothesize three (3) wa..

Summarize background and what makes unique : Summarize your background and what makes you unique (your competitive advantage/differentiation) in a one-paragraph elevator pitch. Identify three to four companies for whom you want to work (your target market and how you can fulfill its needs/wa..

Healthcare services to the mature healthcare consumer : The CEO of your firm has just announced that the organization is considering two diverse strategies to increase business: marketing healthcare services to the mature healthcare consumer, or marketing healthcare services to international consumers.

Calculate the standard deviations for each stock : Consider the stocks, AAPL and MSFT. Using Yahoo Finance (or similar), calculate the standard deviations for each stock, along with the correlation between the two. What would be the volatility of a portfolio with 50% in AAPL and 50% in MSFT? How abou..

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.

Discuss about the post given below : socw 6000:The term competence connotes a level of preparedness for addressing issues and maintaining a high standard of practice with clients. Competent social workers have completed adequate preparations for licensure, and they are appropriately ..

Net working capital that will be recovered at end of project : A company is considering an investment in a new project which would require $55,000 worth of (unrecoverable) capital expenditures and an increase of $45,000 in net working capital that will be recovered at the end of the project. Each year, starting ..

What do you believe was the ethnicity of ancient egyptians : Study the figural images and canons of Egyptian art closely in this chapter and consider the geographic location of Egypt. What do you believe was the ethnicity of the Ancient Egyptians? Why

What role do poverty and broken homes play : What role do poverty and broken homes play in a student's pursuit of an education? Are schools rendered, impotent in terms of teaching some students because of these social problems?

User Account

All Pages