2
$\begingroup$

What is the time complexity of the following problem?

Definitions

A FIFO is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

FIFO code (or a schedule of commands) is a sequence of commands to execute.

Problem Description

We are given $n$ items of data $T_1,\dots,T_n$, and $n$ triplets $(T_1,t^{in}_1,t^{out}_1),\dots,(T_n,t^{in}_n,t^{out}_n)$. $t^{in}_i$ and $t^{out}_i$ identify the time when $T_i$ is PUSHed and POPed respectively. We're guaranteed that $t^{in}_i<t^{out}_i$ for every $i$ and $t^{in}_i,t^{out}_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T_i$ at time $t^{in}_i$ and pop it at time $t^{out}_i$, by adding NOP and PNP commands between the PUSH and POP commands given. No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

Example

Input: $(T_1,2,4)$, $(T_2,1,5)$

Solution:

  1. PUSH $T_2$
  2. PUSH $T_1$
  3. PNP
  4. POP // T_1
  5. POP // T_2
$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 4 '16 at 15:30
  • $\begingroup$ Are you still looking for a solution to this? Are we allowed to add extra PUSH($T_i$) statements that aren't at time $t_i^{in}$? For instance, suppose the input is $(T_1,1,6)$, $(T_2,2,9)$, $(T_3,3,8)$, $(T_4,5,10)$. Do you want the output to be "Not possible", or do you want it to be "PUSH T1, PUSH T2, PUSH T3, PUSH T2, PUSH T4, POP, POP, POP, POP, POP"? (the extra PUSH and POP that have been inserted are in bold) $\endgroup$ – D.W. Jun 5 '16 at 6:07
  • $\begingroup$ @D.W. Thanks for your answer. Adding PUSH T2, as in your example, means this data is available again (in a later time) at the input of the FIFO, making it a schedule of different code, so no, it is not allowed. Adding a PUSH of the head of the FIFO, effectively duplicating it, into the back of the FIFO, could be allowed (and will add solutions to some scenarios) but I think is would be better to first try and solve this without allowing this duplication. $\endgroup$ – Daugmented Aug 21 '16 at 12:15
  • $\begingroup$ Can I assume that the numbers $T_1,\dots,T_n$ are all distinct? (i.e., there is no $i \ne j$ such that $T_i=T_j$) $\endgroup$ – D.W. Aug 22 '16 at 5:55
  • $\begingroup$ Yes, I suspect that this "simple" scenario shouls already prove hard. $\endgroup$ – Daugmented Aug 22 '16 at 6:31
1
$\begingroup$

Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}_i$/$t^{out}_i$ by $K_i$.

In the above example in the question there are three intervals:

|PUSH($T_2$) | PUSH($T_1$)|---------------|POP($T_1$) |POP($T_2$)|

|---------------|---------------|---------------|---------------|---------------|

  1. $K_1=0$.
  2. $K_2=1$.
  3. $K_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d_i$.

In the above example:

  1. $d_0=0$.
  2. $d_1=1$.
  3. $d_2=2$.
  4. $d_3=1$.

Denote by $x_i\in \mathbb{N}\cup\{0\}$ the number of PNP assigned in interval $K_i$, then $x_i\leq K_i$.

In the above example:

  1. $x_1\leq 0$.
  2. $x_2\leq 1$.
  3. $x_3\leq 0$.

Per data unit $T_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}_i$ by adding $d_i+x_{i+1}$ modulo the depth, $d_{i+1}$ of the FIFO per interval. In the above example:

  1. For $T_1$: $(1+x_2)\bmod 2=0$.
  2. For $T_2$: $((( (0+x_1)\bmod 1+x_2 ) \bmod 2)+x_3) \bmod 1 =0$.

And the solution is $x_1=0, x_2=1, x_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

In the worst case,

The element at the tail of the queue need to be popped i.e.,

Given n units of data and n triplets

If n = 4 (number of element in the queue and number of triplets are four)

Input: (T1, 1, 14), (T2, 2, 13), (T3, 3, 11), (T4, 4 ,8)

At time 4 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T1  │ T2 │ T3 │  T4  ║
╚══════╧══════╧════╧════╧══════╝

At time 5, T4 should be popped and to do that all the element left to T4 should be PNP (here, three PNP).

PNP (POP the head of queue and PUSH it to the back)

That is, (n-1) elements of the queue should be PNP to pop nth element from the queue.

At time 7 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T4  │ T1 │ T2 │  T3  ║
╚══════╧══════╧════╧════╧══════╝

At time 8 the state of the queue (pop T4):

╔═════════════════════════════╗
║            QUEUE            ║
╠══════╤═══╤══════╤════╤══════╣
║      │   │ Head │    │ Tail ║
╟──────┼───┼──────┼────┼──────╢
║ DATA │ - │  T1  │ T2 │  T3  ║
╚══════╧═══╧══════╧════╧══════╝

As we go on, we can see for popping one element at the tail requires to PNP all the element right of it.

Gives,

╔══════════════════════╤════════════════════════╗
║ Element to be popped │ Number of NPN required ║
╠══════════════════════╪════════════════════════╣
║          n           │          n-1           ║
╟──────────────────────┼────────────────────────╢
║         n-1          │          n-2           ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          2           │           1            ║
╟──────────────────────┼────────────────────────╢
║          1           │           0            ║
╚══════════════════════╧════════════════════════╝

Thus, in worst case we have a total

= n-1 + n-2 + n-3 + ... + 2 + 1

= [ n ( n + 1 ) ] / 2 - n

= n2 + n

= O( n2 )

Answer :

Worst case time complexity of the problem = O( n2 )

Best case time complexity of the problem = O( 1 ) // when an element is requested to pop, it is found at the head of the queue.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Hi Alwyn, the question was about the complexity to generate the code. I think your answer regards the running time of the code (that was generated). $\endgroup$ – Daugmented Jun 4 '16 at 8:29
  • $\begingroup$ I provide the triplets with the operations, the problem is to find code satisfying these triplets as constraints. I would be happy actually just with an algorithm that declares if a solution exists or not. $\endgroup$ – Daugmented Jun 4 '16 at 8:35
  • $\begingroup$ This doesn't answer the question, yet. This tries to prove that the output (the code) will need to be $\Omega(n^2)$ long, for some inputs. That'd imply that any algorithm will have worst-running time at least $\Omega(n^2)$ [unless it uses some special concise way of representing the output]. However, this doesn't really answer the question, because it doesn't show us an algorithm that always works to compute that code. Remember, the question asks for the time complexity of generating the code. We don't know whether that can be done in $O(n^2)$ or whether it might take longer. $\endgroup$ – D.W. Jun 5 '16 at 6:14
  • $\begingroup$ On further analysis -- this is not even a valid proof of a $\Omega(n^2)$ lower bound. There are other ways to pop the items in the reverse order they were pushing, using a total of $O(n)$ queue operations. So this answer seems like a non-sequitor: it doesn't seem to address the question that was asked. $\endgroup$ – D.W. Jun 6 '16 at 2:39

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.