2
$\begingroup$

I'm revising for an Algorithms exam and looking at a sample question it says :

A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy movie. Some teenagers quarrel with each other all the time. The Problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.

Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm.

In lectures for greedy problems we've only covered Knapsack Problems so Next Fit/Best Fit for Bin Packing. I can't seem to understand how these methods have any relevance to coming up with a solution for the question.

Obviously I don't expect anyone to answer this, since I've not even made an attempt. But in honesty I don't know where to start. If you guys could give me some sort of hints or just general advice because I'm pretty stranded at the minute.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ What did you try? Where did you get stuck? Solving this exercise for you isn't going to help a whole lot: we'd prefer to help you understand the topic, so you can answer the next question on your own! $\endgroup$
    – David Richerby
    Commented Dec 29, 2014 at 18:08
  • $\begingroup$ This is all revision over my holidays so obviously I don't want someone to do the exercise for me. I've read all the topics we've covered so far for greedy Kruskals, Prims, Knapsack problems. I just don't seem to understand how any of them have any relevance to the question... @DavidRicherby $\endgroup$
    – user26234
    Commented Dec 29, 2014 at 18:17
  • $\begingroup$ Model the situation and abstract the problem. Does it look familiar? $\endgroup$
    – Raphael
    Commented Dec 31, 2014 at 12:45
  • $\begingroup$ see cs.stackexchange.com/questions/35806 It was posted later ... chance ... $\endgroup$
    – babou
    Commented Jan 1, 2015 at 14:04

1 Answer 1

Reset to default
0
$\begingroup$

I don't know if i understood your exercise. But pick a arrangement with n students in n positions is a permutation, so there are n! possible arrangements. So, it's look like a Hamiltonian path problem, where each student is a graph's vertex and there's an edge i,j if the student i can sit next to student j, with no quarrel. If you can find some Hamiltonian path, you have a arrangement. For greedy algorithm you can propose a heuristic that visit first the vertex with low degree (number of edges incident to the vertex), meaning that the most annoying student will be chosen to sit on the first place of the row.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 1) Not every problem that reduces to an NP-hard one is hard. (cf sorting) 2) The problem statement seems to require an exact algorithm. $\endgroup$
    – Raphael
    Commented Dec 31, 2014 at 12:46
  • $\begingroup$ @Raphael The very same question (up to textual presentation), asked a day later (!?), got two answers. -1) This does not just reduce to NP: it is the Hamiltonian path problem in thin disguise. -2) The problem statement does require an exact algorithm, that succeeds of fail. I would think that greediness does not make sense in such a case, since it implies an idea of "approximate" solution. But it is in the question(s). $\endgroup$
    – babou
    Commented Jan 1, 2015 at 18:33
  • $\begingroup$ @WhoeverDidIt Why the downvote on this question? $\endgroup$
    – babou
    Commented Jan 1, 2015 at 18:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.