2
$\begingroup$

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be the set of questions that a student has a doubt it. Assume that $\forall 1 \leq j \leq n: Q_j \neq \phi$ and $\bigcup_{1\leq j\leq n}Q_j = Q$.

Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the time spent by $s_j$ in the tutorial session. We want to find out an optimal permutation $\sigma$ in which questions are discussed $(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $\Sigma_{1\leq j \leq n}t_j$ is minimized.

Intuitively it seems that we can greedily discuss the question that the most number of students (in the current iteration) have a doubt in. Is the greedy algorithm correct?

Sidenote: By the way, I thought of this question after an actual tutorial session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!

$\endgroup$
  • $\begingroup$ I think that greedy algorithm should focus on students. You don't want to pick questions, you want to pick a student whose questions you will answer first. Something like "Define the cost of a student as the sum over his questions of $1/k_i$ where $k_i$ is the number of students asking question $i$. At each step, answer the most popular question (I'm not sure that's useful but it can't hurt) of the student of minimal cost. Note that unless all this student's questions have been answered, he will remain of minimal cost.". $\endgroup$ – xavierm02 Feb 20 '17 at 13:59
  • $\begingroup$ I edited your question to match the answer (to ask whether a greedy algorithm is correct). Can I encourage you to post a separate question asking whether an efficient polynomial-time algorithm exists for this problem? That will provide a place where people can answer that question, and will ensure it isn't treated as already-answered. Thanks! (Implicitly your original question seemed to be asking two different questions: (a) is this greedy algorithm correct? and (b) does an efficient algorithm exist. The site usually works better when there's one question per post.) $\endgroup$ – D.W. Feb 20 '17 at 23:59
  • $\begingroup$ Finally, for future reference: to check whether a greedy algorithm is correct, I suggest you first try the resources in cs.stackexchange.com/q/59964/755 to see if you can prove it yourself, before asking. Often some random testing suffices to get a pretty good idea of whether your greedy strategy is correct or not. $\endgroup$ – D.W. Feb 21 '17 at 0:01
  • $\begingroup$ @D.W. I didn't mean to ask if the greedy algorithm was correct or not, it was more of a side-note, that's why I explicitly stated to find an efficient algo (polytime) as my question, so can I edit it back and remove the greedy part if you don't want two questions in one? PS: Thanks for the reference question. $\endgroup$ – skankhunt42 Feb 21 '17 at 7:11
  • $\begingroup$ @skankhunt42, sure, you can roll back my edit, or change it as you suggest, or otherwise. I'd just like to see you get your question answered. As it stands, there is an answer, so this question is treated by the system as 'answered' -- I was thinking that the alternative I suggested might get more attention for your question, but feel free to revert/change as you like, based on whatever seems best to you. $\endgroup$ – D.W. Feb 21 '17 at 7:14
1
$\begingroup$

Counterexample: Students are $x_1\dots x_n$ and $y_1\dots y_m$ and questions are $Q_0, \dots Q_m$. Students $x_i$ only want $Q_0$ to be answered while the $y_i$ students want question $Q_1,\dots, Q_m$ to be answered.

Let's say you place $Q_0$ as the $k^{th}$ question. Then the total time waited by students is:

  • $L(n,m)=n(m+1)+m^2$ if $Q_0$ is last

  • $nk + m(m+1)$ if $Q_0$ is $k^{th}$

Clearly, if you want to not put $Q_0$ last, then you might as well put it first so that the cost is $F(n,m)=n + m(m+1)$.

Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n>1$ and $m>0$, we'll have $L(n,m)>F(n,m)$. So placing it first is better.

But your greedy algorithm would put it last if we take $m>n$.

$\endgroup$
  • $\begingroup$ Great! I hope it's not NP-hard like all the interesting CS problems. $\endgroup$ – skankhunt42 Feb 20 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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