Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class mates but they all seemed to be confused. One gave me a sample answer of code doing it, whereas another one thought he wants some sort of graph with nodes/edges to represent the answer.


1)
A group of $n$ teenagers $T_1,\dots,T_n$ are to sit in a single row of $n$
chairs watching a particularly 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.


a) Propose a solution to this problem using the Backtracking
approach. Specify clearly the search space and any
pruning conditions used. Show how your algorithm would
work for 3 teenagers, $T_1,T_2,T_3$, assuming that the only
quarrelling teenagers are $T_2$ and $T_3$.
Note: stop the search after finding a solution. [12 marks]


b) Propose a solution to this problem using the Greedy
approach. Estimate the complexity of the resulting
algorithm. [8 marks]

I've spent days going through my notes and reading up on greedy/backtracking but I still don't see how it fits with the question. Whenever I look up Backtracking/greedy approach questions the questions are nothing like how college asks them which makes me very confused...

We've covered dynamic programming, backtracking, greedy algorithms knapsack problem, first fit, next fit minimal spanning trees, Kruskal's algorithm, Prim's algorithm, divide and conquer $N$ queens problem for backtracking.

Overview of the problem

If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
information. Much is said in wikipedia about the Hamiltonian path
problem, which is a NP complete problem. I will only try to discuss
some apects, with my limited competence on the topic, taking into
account the way your question is stated.

Backtracking is just a way of implementing a non-deterministic
algorithm. It is usually simpler to describe the non-deterministic
algorithm, and just say that it is implemented by backtracking, and
possibly explain separately what that is (as I do below)

The non-deterministic algorithm

In the case of the Hamiltoniam path problem (which you can translate
back into your teenagers problem), the non-deterministic algorithm is
as follow:

-
Choose a starting node for the path, and mark it used.

-
While there are unmarked nodes do:

Choose a new unmarked node connected to the last node added to the path,
add it at the end of the path, and mark it used.

At the end of the loop you have a Hamiltonian path. The choose
statement is non deterministic, as you have to take one of many
possibilities, many (or all) of which may not succeed.

Backtracking interpretation

Failure may in general occur in different ways. Here you have failure
when none of the unmarked nodes is connected to the last node added to
the path (i.e. none of the remaining teenagers is compatible with the
last one chosen).

The backtracking implementation consist in keeping track, at each
occurrence of a choose statement, of all the possible choices that
have not yet been tried. If you fail, you go back to the previous
choose, undoing what was done (i.e. node addition to the path and
node marking), discard the choice made and make a new choice from
those that have not yet been tried at that choose statement.

One way of implementing this is to associate a list of remaining
alternative choices to each node of the constructed path. Another
possibility is to rely on the exception mechanism of the programming
language.

Pruning

I am not sure what is (or should be) considered pruning in this case.

Checking that a node chosen is connected to the previously chosen one
is a very trivial form of pruning. No pruning at all would be
exploring the complete set of remaining nodes at each choose
statement, to discover soon after that some fail because the node is
not connected to the end of the path.

Greedy algorithm

The greedy algorithm as described by Yuval Filmus' answer is just the
non-deterministic algorithm, except for the fact that you do not
backtrack. You just fail. I do not know whether there is more to be
said.

He is much more expert than I am on these issues. However, my own
feeling is that the very concept of greedy algorithm makes less or little
sense in this case. The reason is that I understand greedy algorithms
as a way of finding good solutions to quantitative optimization
problems, which may not be optimal in some cases.

A greedy algorithm also has to make choices, and does so on the basis
of local optimizations that may not be optimal globally. But it is
expected to succeed anyway and does not have to backtrack: the price
of greediness is that the "cost" (however defined) of the result obtained
by the algorithm may be higher than the cost of the optimal solution.

I do not think that is really very meaningful in an all or nothing
situation, were you are supposed to succeed or to fail, without any
measure of intermediate situations, like placing the largest possible
number of teenagers, or placing them all with the smallest number of
conflictual sittings. These examples may be seen as optimization
variants of the problem where greediness makes sense.

However, we can use heuristics that could possibly increase the
chances of success. In the case of our optimization variants, they
could e seen as greedy techniques that improve the chances of having
near otpimal solution (Though I did not prove anything). But the
greedy algorithm remains basically the non-deterministic description.
The heuritic comes as a way to choose that improves chances of
success, or of approaching the least cost.

One such heuristic, is to always choose one of the unmarked nodes that
has the least number of edges connecting to other unmarked nodes. The
purpose is to keep in your bag nodes that will be easier to connect to
the path, while removing those that are getting hard to use. And if one
of these node is disconnected from all others, or has only one
connection but cannot be added to the path immediately, you know you
have failed and can start backtracking earlier.

We could say that we try to optimize the cost of the search reather
than the cost of the solution obta

StackExchange Computer Science Q#35806, answer score: 7