Explore BrainMass

Explore BrainMass

    Seating arrangement to increase social contact

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    College Students go out for a party. To increase social contact, they would love to sit at tables so that no two students from the same programme are at the same table. Show how to find such a seating arrangement or prove that no such seating plan is possible.

    The input is the p programmes, for each i the number ai indicates the students from programme i, and the seating capacities of the q tables with table j seating bj people. Give the time complexity of your algorithm with a brief justification.

    © BrainMass Inc. brainmass.com October 10, 2019, 12:29 am ad1c9bdddf

    Solution Preview

    To grasp this solution easily, try to mentally picture the situation when going through the explanations.
    You may like to refer to http://en.wikipedia.org/wiki/Sorting_algorithm for a comparison of sorting algorithms.

    procedure SeatingArrangement

    Input: Array Students[1..p], Tables[1..q]

    // Students[i] gives number of students in program i.
    // Tables[i] gives available seating capacity of table i. This array gets modified in this solution.
    // p indicates number of programs.
    // q indicates number of tables.
    // Considering that a worst case NlogN sorting algorithm is chosen wherever sorting is required.

    Sort ...

    Solution Summary

    Solution is presented in pseudo-code form along with plain description. Count of comparisons or complexity is marked for various steps in the given implementation. Solution analyzes the given implementation for worst case complexity (in terms of number of comparisons) in achieving a successful seating arrangement.