Selecting optimal order of questions to minimize total time - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:15:10Z https://cs.stackexchange.com/feeds/question/70521 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/70521 2 Selecting optimal order of questions to minimize total time skankhunt42 https://cs.stackexchange.com/users/54167 2017-02-19T18:22:58Z 2017-02-20T23:58:32Z <p>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$.</p> <p>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.</p> <p>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?</p> <p>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.</p> <p><strong>Example</strong><br> 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.<br> 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.</p> <p>$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!</p> https://cs.stackexchange.com/questions/70521/-/70557#70557 1 Answer by xavierm02 for Selecting optimal order of questions to minimize total time xavierm02 https://cs.stackexchange.com/users/2353 2017-02-20T13:20:08Z 2017-02-20T13:20:08Z <p>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.</p> <p>Let's say you place $Q_0$ as the $k^{th}$ question. Then the total time waited by students is:</p> <ul> <li><p>$L(n,m)=n(m+1)+m^2$ if $Q_0$ is last</p></li> <li><p>$nk + m(m+1)$ if $Q_0$ is $k^{th}$</p></li> </ul> <p>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)$.</p> <p>Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n&gt;1$ and $m&gt;0$, we'll have $L(n,m)&gt;F(n,m)$. So placing it first is better.</p> <p>But your greedy algorithm would put it last if we take $m&gt;n$.</p>