Find optimal shelf placement and analyze time complexity

Assignment Help Basic Computer Science

Reference no: EM131361548

Consider the problem of storing n books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book bi, where 1 ≤ i ≤ n, that has a thickness ti and height hi. The length of each bookshelf at this library is L. Suppose all the books have the same height h (i.e. , h = hi = hj for all i, j) and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that bi does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

Reference no: EM131361548

Questions Cloud

Give an algorithm that takes the array bad : Each path would consist of only rightward and downward moves. Give an algorithm that takes the array BAD and returns the number of safe paths of length X + Y - 2. For full credit, your algorithm must run in O(XY ).

Level of income and job satisfaction : A study has results that seem fine, but there is no clear association to social change. What is missing? A correlation test was conducted to determine whether a relationship exists between level of income and job satisfaction.

Summarize the results of your multicultural self-assessment : Review Chapter 7 in the course text, Orientation to the Counseling Profession: Advocacy, Ethics, and Essential Professional Foundations, and select two different stages of human development that resonate with you the most. Think about how an under..

Review the case study of working with families : Then Submit a description 1-2 of a social or economic justice issue that is evident in the case. Suggest two strategies the social worker might employ to address the issue.

Find optimal shelf placement and analyze time complexity : Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

Student satisfaction levels in a quantitative reasoning : An independent samples t test was used to determine whether student satisfaction levels in a quantitative reasoning course differed between the traditional classroom and on-line environments. The samples consisted of students in four face-to-face ..

Discuss the concept of ecological services : From the list, identify two services you believe are the most important and cite at least 3 reasons why and also, choose two services that you think are most likely to decline due to human influence and cite at least 3 examples of the result of dec..

Prepare a summary of the cpp reporting requirements : To avoid a recurrence, the Payroll Manager, Mary Arnstein, has asked you to prepare a summary of the CPP reporting requirements on T4 information slips.

Are there any debates surrounding the issue : Are there any debates surrounding the issue? Also, provide a brief history of how the issue began. For this assessment, you will examine a contemporary social issue using your sociological lens. You will begin by selecting your own contemporary so..

User Account

All Pages