Time interval correction for step detection algorithm I am currently going over this paper, and in fact have already tried to implement it:
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4634483/ [1]
Paper looks at the amplitude of the step and the time between the swings. ALthough I seem to understand the general idea, I am slightly confused about one of the formulas, which describes time between steps, namely:
"To extract only one valley from a gathered group of valley candidates in a very short time range, every valley candidate is validated by checking the time distance to the recent valley using the following threshold.
$Th_v = \mu_v - (\sigma_v/\beta)$
where $\mu_v$ and $\sigma_v$ represent the average and the standard deviation of the time interval between adjacent valleys in the magnitude of acceleration, respectively. These averages and the standard deviations are calculated for recent M peaks or valleys."*
Except time threshold obviously magnitude is also taken into consideration.
So I have produced magnitudes that I obtain from my sensor:

where red dots correspond to initially discovered valleys and purple to points that should re-evaluate last valley.
So what I currently have is something like this:
1) I obtain valley at point 20. I obtain valley at Point 49. This should mean that the average distance between two valleys is 29 readings, and therefore I set my $\mu_v = 29 and \sigma = 0$, which yields me a value of $Th_v=29$ ( my $\beta = 1/3$). I also store the difference (29).
2) Then I get to point 51, which should update the $Th_v$ value. So now I calculate the mean, which I think means $(29 + (51-49))/2 = 15.5$
And calculate standard deviation, which equals $19.09$. So then when I actually plug these values in the formula above I get $Th_v = -41.909$, which should not be possible as I believe this value should be always positive to indicate the time between two valleys.
Am I dong something incorrect or do you have any idea what's wrong with my or paper's approach?
References:
[1]: Lee H, Choi S, Lee M. Step Detection Robust against the Dynamics of Smartphones. Wang X, ed. Sensors (Basel, Switzerland). 2015;15(10):27230-27250. doi:10.3390/s151027230.

I managed to solve the problem of the algorithm by using a different approach. Algorithm is not clear on what is happening with the initial values or how to reliably capture a set of peak/valley candidates and how to deal with them.

Therefore, we decided to use only magnitude part of the paper, which radically simplifies the whole algorithm, and in fact works great ( assuming you are getting reasonable sensor readings).


Probability of randomly designated subsets cover the universe Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.

Is there a polynomial time algorithm that computes:

$$\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right]$$

Or is there any equivalent famous problem?

There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$.
I will show that such an exact solution would provide a polynomial time algorithm for set-cover.

Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-cover. Let $m = |S|$.

Let
$$
 \Gamma = \left\{ K \in \mathscr{P}(S) : U =\bigcup_{X \in K} X \right\}
$$

For each $h \in \mathbb{N}$ let:

$$
 \nu_h = |\{K \in \Gamma : |K|=h\}|
$$

Observe that our instance of set-cover is satisfiable if and only if $\nu_k \neq 0$.

Now, let $T$ be a set, constructed as in the problem statement. $T$ covers $U$ if and only if $T \in \Gamma$. Therefore:

$$
\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right] = \mathbb{Pr}[T \in \Gamma] = \sum_{X\in\Gamma}p^{|X|}(1-p)^{m-|X|} = \sum_{h=0}^m \nu_h p^h(1-p)^{m-h}
$$

The rightmost expression is a polynomial over the ring $\mathbb{Q}[p]$, which means that its coefficients can be found by computing its value at $m-1$ points and applying an algorithm such as the finite differences method.


A and B are Turing recognizable, is A - B Turing recognizable? If A and B are Turing recognizable, is A - B Turing recognizable?

I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability.   For example, if A is context free and B is a regular language A - B would result in a language that is sill Turing recognizable.

However, does this become a question about emptiness?  Two Turing recognizable languages equal to each other leave an empty set.  Is the empty set Turing recognizable?  I would still say yes.

Not sure if I'm thinking about this correctly...

Suppose that $L$ is a Turing-recognizable language and $L^C$ is its complement. Let's assume, for the purposes proof by contradiction, that $L^C$ is also Turing-recognizable. This means that a recognizer exists for each of these two languages: we will call them $M_L$ and $M_{L^C}$. How might we use these two recognizers to do something absurd?

For starters, we can construct a decider for the language $L$. Given any string $w$, we can use it as input for both $M_L$ and $M_{L^C}$. $M_L$ will halt and accept if $w$ is in $L$ (and halt and reject or loop forever if not). Conversely, $M_{L^C}$ will halt and accept if $w$ is in $L^C$ (and halt and reject or loop forever otherwise). In any case, our constructed machine will halt with a decision about $w$, and so we've proven the existence of a decider for $L$.

By assuming that any Turing-recognizable language $L$ is closed under complement, we can show that $L$ is also Turing-decidable, which implies that $R=RE$. So we must conclude that Turing-recognizable languages are not closed under complement!

If they're not closed under complement, is it possible for them to be closed under set difference? (Hint: the set of Turing-recognizable languages is closed under intersection. Can you rewrite $A-B$ in terms of complement and intersection?)

(Solution: $A-B$ can be written $A \cap B^C$; loosely speaking, both describe the set of elements which belong to $A$ but not to $B$. Since set difference can be expressed using intersection and complement operators, and since Turing-recognizable languages are not closed under complement, we conclude that Turing-recognizable languages are not closed under set difference.)


How is the implementation of pipes in a OS I understand that a pipe is a form of IPC where a process creates a link to communicate with some other process (a child maybe), taking each one a end of the pipe. File descriptors are created for read and write and they can use it in half-duplex or full-duplex. My question is if the implementation of this schema is something like shared memory or message passing.

Like message passing.  The kernel allocates a private buffer for storing the data that has been sent and is waiting to be delivered to the recipient.

For more details, see:

http://www.slideshare.net/divyekapoor/linux-kernel-implementation-of-pipes-and-fifos
http://linux.omnipotent.net/article.php?article_id=12504&page=-1

In the future, please do more research before asking.  We expect you to do some serious research before asking.  The links above showed up in the first few responses to my first Google search, which is a hint that you should have done more research on your own.


How to determine valid handle for given bottom up parser? I came across following question:

  Consider the grammar:

  $E → E + n\text{ | }E × n\text{ | }n$

  For a sentence n + n × n, the handles in the right-sentential form of the reduction are
  (A) $n, E + n$ and $E + n × n$
  (B) $n, E + n$ and $E + E × n$
  (C) $n, n + n$ and $n + n × n$
  (D) $n, E + n$ and $E × n$

Solution given was:

n+n×n
E+n×n  //reduce n to E
E×n    //reduce E+n to E
E      //reduce E×n to E

  Hence option D

Then I came across following problem:

  Consider the following grammar:
  $A\rightarrow A(B)|B$
  $B\rightarrow B*C | id $
  $C\rightarrow (id)$
  Which of the following can be the correct handle in bottom up parsing for the given grammar?
  (A) (id)
  (B) id*C
  (C) id
  (D) none

The given solution was (A)(id)

Doubts

After thinking about the definition of the handle and two problems, I concluded following:

If problem asks which are valid handles for given string and grammar, then we have to actually try parsing that string with given grammar and determine which handles are reduced during parsing.
But, if no string is given, and just the grammar is given, then following are valid handles:
(a) right hand side of each production
(b) those sentential forms which can be derived from start symbol by doing rightmost derivation are valid handles. For example, $B*(id)$ is a valid handle as we can derive it by doing rightmost derivation as follows: $S\rightarrow B\rightarrow B*C\rightarrow B*(id)$

As explained in 2nd bullet point of point 1 above, answer of 2nd problem is wrong and both of $A$ and $C$ options are correct: both $(id)$ and $id$ are valid handles.

Am I correct with both conclusions above?

A handle is a production whose right-hand side can be reduced at a specific moment during a parse. (Or, as it is usually presented, it is the production which has been expanded at a specific point in a derivation for a sentence.) Although a handle is almost always defined as a production, it's common to talk about them as though they were just the right-hand side. That's clearly not correct because you cannot reduce a handle without knowing what it will reduce to, but in many contexts (including multiple-choice exams) it's possible to get away with this informality.

So I'd disagree that $B∗(id)$ is a handle, because it is not the right-hand side of any production. That doesn't really alter your question about whether $id$ is a handle.

A production (or its right-hand side) could be a handle for a grammar if there exists a derivation which involves that production. That is not necessarily the case for every production in a grammar, since grammars can include unreachable and useless productions. However, the grammar you present does not include any such productions. There exist derivations which use each of the productions, including $B\to id$ and $C\to (id)$. On that basis, I agree that both (A) and (C) are correct answers.


Analyzing the time complexity of nested loops So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.

What is the time complexity of this code?

for  i = 1 to n
   for  j = 1 to n*n
      for  k = 1 to j
         Task

where the time complexity of Task is Θ(1)

The most inner loop, for k = 1 to j is Θ(j). Then the middle loop, for j = 1 to n^2 I thought, should produce Θ(n^2) as it loops from j = 1 to n^2 but I've been told it's Θ(n^4). I honestly do not understand how it could be Θ(n^4) when it's iterating from 1 to n^2. Can someone explain how this works in simple terms?

Translating for-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:

$\qquad\displaystyle\begin{align*}
\#\mathrm{Task} \quad&= &&\sum_{i=1}^n \sum_{j=1}^{n^2} \sum_{k=1}^j 1 \\
                     &= && \sum_{i=1}^n \sum_{j=1}^{n^2} j \\
                     &= && \sum_{i=1}^n \frac{n^2(n^2 + 1)}{2} \\
                     &= && \frac{n^3(n^2 + 1)}{2}.
\end{align*}$

We use the closed form of the triangular numbers (which you find on any formulary if you have not memorized it). Finally, obtain a $\Theta$-class using standard tools.


Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$? Until just now I thought that I have fully understood Rice's theorem but this example irritates me:

$L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$
where $H_{all}$ denotes the totality problem. Correct me if I'm wrong but in my opinion this is not the same as $L' = \{ \langle M \rangle \mid M \mbox{ is a Turing machine that halts on every input} \mbox{ } \}$. Here, I could apply Rice's theorem and conclude that L' is not decidable but in the other case, L* is actually empty so the theorem is not helpful.

Well, Rice's theorem doesn't apply but we don't need it—$L^*$ is empty and therefore decidable.

To figure this out, we just need to be meticulous about what these languages are.

$L^*$ is the set of all Turing machines that recognize the totality problem. It is the set of all Turing machines that can take in a Turing machine $\langle N\rangle$ and accept just if $N$ halts on all inputs.
$L^\prime$ is the set of all Turing machines that halt on all inputs.
They're different languages: $L^*$ is the set of all machines whose language is $L^\prime$.

The totality (all-halt) problem is unrecognizable: there is no Turing machine that takes in a TM $\langle N\rangle$ and accepts just if $N$ halts on all inputs. (Consider a reduction to the halting problem.) Therefore, $L^*$ is empty and $L^\prime$ is unrecognizable.

$L^*$ is empty, therefore decideable (when given a machine $\langle N\rangle$ and asked if it recognizes the totality problem, always say no.) $L^\prime$ is unrecognizable, which is stronger than merely undecidable.

But, if we didn't already know that $L^\prime$ was unrecognizable, we could use Rice's theorem to show that $L^\prime$ is undecidable. There's a string in $L^\prime$, for example the Turing machine that ignores its input and always accepts. There's a string not in $L^\prime$, for example the Turing machine that ignores its input and loops forever.

Also, a side note: Rice's theorem says that non-trivial language properties of TMs are undecideable. As you point out, there are two trivial languages which the theorem doesn't cover: the empty language $\varnothing$ and the language of all strings $\Sigma^*$. Note that we don't need Rice's theorem for these languages to determine decidability— we already know they're decideable. In fact, they're regular: there's a DFA that accepts all strings, and a DFA that accepts no strings.


Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher I have a field in my data store which must take exactly 180 bits of information. Some users will choose to make this data encrypted, some won't, so some of those 180 bit fields will be ciphertext some will be plaintext. A boolean will indicate which one the user is using. The important thing here is that I need this field to be exactly 180 bits long.

However, a 128-bit cipher will mean I have to put in 256 bits in as plaintext, which is fine, just use a buffer string, but this means that the output is 256 bits when what is stored must be exactly 180 bits. And I can't simply cut off the ciphertext or that would mess up the decryption.

If you have a unique, unchanging identifier for each entry in your data store, you can use counter mode.

A nice thing about counter mode turns a block cipher into a stream cipher. No matter what the block size is, CTR mode encrypts an $n$-bit plaintext into an $n$-bit ciphertext.

In order to achieve that, CTR requires a unique counter value per block. Note: not just a unique counter value per message, but a unique counter value per block. The counter size is the same as the block size. In your case, you have messages that fit on two blocks, thus each message requires two counter values. If you have a unique identifier $k$ for each message, you can use $k$ and $k+1$ as the counter values for the two blocks (the second of which is partial) of the message.

Thus you need a 127-bit unique identifier for each message (128-bit block, minus one bit to distinguish the two blocks inside each message). The only security requirement for these 127 bits is that they are never reused for a given key. The initial counter value to encrypt a message is often chosen randomly, but this is not a requirement, just a convenience to ensure uniqueness. Of course, to decrypt the data, you need to be able to recover the unique identifier associated with each entry.

If your entries have some kind of unique identifier, which is often the case in databases, then you're set. Just remember that if you move data around or normalize it in a way that changes the identifiers, you will need to decrypt and reencrypt the data.

Some crypto libraries may present CTR mode through a function that randomly generates the initial counter value and prepends it to the message (so you'd input a 160-bit plaintext and get back a 288-bit ciphertext). Use a library that lets you specify the initial counter value (almost all implementations will increment the counter by 1 for each successive block, so pick initial counter values that are even, but you'll need to be aware of the endianness used by your library).

Keep in mind that encryption only gives you confidentiality, not integrity. In other words, someone who obtains the ciphertexts but not the key will not be able to find any information about the data; but if someone can inject fake ciphertexts or modify existing ciphertexts, the tampering cannot be detected. It is intrinsically impossible to detect tampering by cryptographic means in your scenario since there is no room for any redundancy.


How to identify periodic pattern recognition I'm dealing with a time series that consists of one year's data of the result of some measurement. The time index is in second and the result of the measurement is a non-negative integer.

Interestly, after some tweaks & transformation & plot of the original data, I found that in some days the data shows a periodic pattern within that each day.

For an instance, I found that on one day throughout the whole day a specific measurement (integer) is recorded every 1 minute. The pattern is obvious because the integers are almost the same and spaced in nearly 1 minute interval while others are kind of random.

Whilst it is relatively easy to spot the pattern I found it hard to precisely state it. The main issues here are that

The "specific" integers are slightly varying, say the majority of the integers are 1700, but occasionally I can find 1800, 1600, or 1701, etc;
The "specific" integers are different across days and sometimes even different within one day.
The interval is not necessarily 1 minute and furthermore, it is not the same even within a single day. Say, in the morning the pattern is spaced in 58 second interval whilst in the afternoon, it is in 61 second interval;
The interval is not very precise either. Say, in the first 2 hours patterns are spaced in 60 second interval but then a 61-second interval occurrs and then after that going back to the 60-second interval again;

Because the data is huge and so I want to see if I can programmatically identify the patterns (if it exists for a day) and also retrieve those "specific" integers in the pattern.

Anyone suggest an approach? Or any guidance?

Thanks.

One way to detect a pattern is to write a filter that scans the entire sequence and returns true/false at each point.  True means that the pattern was recognized, false means that it was not found.  Count the number of "true" values and divide by the entire length to see the fraction of times that the pattern was found.

For example, one filter would require three parameters: f, the expected frequency (60 seconds); w, the allowed width (2 seconds means 58-62 seconds); and d, the allowable difference between values.

In Python code:

f = 60    # frequency, every 60 points
w = 2     # width, (point - f) +/- w
d = 10    # delta, allowable difference

points = [... list of data points ...]
n = len(points)

found = 0     # start counting the number of matches
# main loop: start at point f+w so we can look back that far
for p1 in range(f+w, n+1):
    # compare point p1 with point p0, looking back (f +/- w)
    for p0 in range(p1-f-w, p1-f+w+1):
        if abs(points[p1] - points[p0]) < d:
            found += 1    # filter found a match
            break         # exit innermost loop
print 100.0 * found / (n - f - w)    # show the percentage of matches

You can play around with the parameters, and maybe use d as a percentage instead of an absolute value.

For more complex pattern recognition, you will need to write more complex filters.  This is a start.


Divide and Conquer to find a power I understand the concept behind Divide and Conquer, making one problem into sub problems and then merging the solutions together. However, from looking at a past paper a question has occured where it asks how 2^11 can be found using Divide and Conquer, I'm just confused how finding a power can be divided into sub problems =/

pow(2, 11) = 2 * pow(2, 5) * pow(2, 5)

pow(2, 5) = 2 * pow(2, 2) * pow(2,2)

pow(2, 2) = pow(2, 1) * pow(2, 1)

pow(2, 1) = 2

would this be correct?

The algorithm relies on two facts:

If $n$ is even, $n=2k$, we have $a^n = a^{2k}=a^ka^k = a^{n/2}a^{n/2} = (a^{n/2})^2$
If $n$ is odd, $n=2k+1$, we have $a^n=a^{2k+1}=a^1a^{2k}=a(a^ka^k)=a(a^{(n-1)/2})^2$

In other words, we have
$$
a^n=\begin{cases}
(a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is even}\\
a(a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is odd}
\end{cases}
$$
You've computed $pow(a, n)$ by changing it to a problem involving an instance of the half-sized problem $pow(a, n/2)$ along with a squaring and possibly a multiplication by $a$.


Term rewriting; Compute critical pairs I have tried to solve the following exercise but I got stuck while trying to find all the critical pairs.

I have the following questions:

How do I know which critical pair produced a new rule?
How do I know I found all the critical pairs?

  Let $\Sigma= \left \{ \circ, i, e \right \}$ where $\circ$ is binary, $i$ is unary, and $e$ is a constant.
  $$
E=\left \{  \begin{gather}
( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\
x \circ e \approx x \\
x \circ i(x) \approx e
\end{gather} \right\}
$$

My work so far:

  $x\circ e >_{\textsf{lpo}} x$   (LPO 1)   $x$ is a variable
  $x\circ i(x)>_{\textsf{lpo}} e$   (LPO 2b)   there are no terms in the right hand side
  $(x\circ y)\circ z\approx x\circ(y\circ z)$
  $s=\circ(\underset{\large s_1}{\circ(x,y)},\underset{\large s_2}{\strut z})\qquad t=\circ (\underset{\large t_1}{x\strut}, \underset{\large t_2}{\circ(y,z)})$     (LPO 2c)

  check that $s>t_j$, $j=\overline{1,m}$
  $s>_{\textsf{lpo}}t_1$     (LPO 1)
  to prove that $s>_{\textsf{lpo}}t_2$ (LPO 2c) we prove that
  $$s>_{\textsf{lpo}} y \;\;\text{(LPO 1)};\qquad s>_{\textsf{lpo}}z \;\;\text{(LPO 1)};\qquad \circ(x,y)>y\;\;\text{(LPO 1)}$$
  find $i$ such that $s_i>_{\textsf{lpo}}t_i$     $i=1$
  $$\circ(x,y)>_{\textsf{lpo}}x\;\;\text{(LPO 1)}$$

  $(x\circ y)\circ z>_{\textsf{lpo}} x\circ (y\circ z)$
  a. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $x_1\circ e\;\rightarrow\; x_1$
  $x\circ y \mathrel{\,=?\,} x_1\circ e$
  $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;e\}$
  $$\require{AMScd}
\require{cancel}
\begin{CD}
(x_1\circ e)\circ z @>>> \cancel{x_1}\circ z\\
@VVV @VVV\\
\cancel{x_1}\circ(e\circ z) @>>> e\circ z\approx z
\end{CD}\qquad\text{left identity?}$$
  b. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $e\circ x_1\;\rightarrow\; x_1$
  $x\circ y \mathrel{\,=?\,} e\circ x_1$
  $\theta\{x \;\leftarrow \;e;\; y\;\leftarrow \;x_1\}$
  $$\begin{CD}
(e\circ x_1)\circ z @>>> x_1\circ z\\
@VVV @VVV\\
e\circ(x_1\circ z) @>>> ?
\end{CD}$$
  c. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $x_1\circ i(x_1)\;\rightarrow\; e$
  $x\circ y \mathrel{\,=?\,} x_1\circ i(x_1)$
  $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;i(x_1)\}$
  $$\begin{CD}
(x_1\circ i(x_1))\circ z @>>> e\circ z\\
@VVV @VVV\\
x_1\circ(i(x_1)\circ z) @>>> ?
\end{CD}$$

As a support document I have "Term Rewriting and All That" by Franz Baader and Tobias Nipkow.

(original image here)

EDIT1

After searching for the critical pairs I have the following set of rules(assuming 2.a is corect):

$$
E=\left \{  \begin{gather}
( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\
x \circ e \approx x \\
x \circ i(x) \approx e \\
x \circ (i(x) \circ y) \approx y \\
x \circ ( y \circ i(x \circ y) ) \approx e \\
e \circ x \approx x  \\
e \circ (x \circ y) \approx x \circ y
\end{gather} \right\}
$$

Before adressing the actual questions, one remark on your work so far: the left cancellation in 2.a. is not correct in general, the critical pair would just be $x\circ(e\circ z) \approx x\circ z$. Consequently, you don't get the critical pair 2.b. The problem with this cancellation is that the equation you get does in general not follow from the axioms you started from; for example, if you are working in the language of rings, you might at some point derive the critical pair $0*x \approx 0*y$, but it would be incorrect to deduce $x\approx y$ (which would mean that you only have a trivial model). No sound rewriting procedure, including Huet's, should allow this reduction.

On the other hand, you are missing the critical pairs you get by unifying (variable-renamed versions of) $x\circ e$ or $x\circ i(x)$ with all of $(x\circ y)\circ z$ (i.e. using the second $\circ$). The resulting critical pairs are

$x\circ(y\circ e)\leftarrow (x\circ y)\circ e\to x\circ y$, which after reduction becomes the trivial equation $x\circ y\approx x\circ y$, and
$x\circ(y\circ i(x\circ y))\leftarrow(x\circ y)\circ i(x\circ y)\to e$, which cannot be reduced further and gives the rule $x\circ(y\circ i(x\circ y))\to e$ (assuming that $\circ\triangleright e$ in the precedence $\triangleright$ used to define the LPO, just as you did when orienting $x\circ i(x)\approx e$).

For the basic completion procedure:

Whenever you create a critical pair, you reduce both sides as far as possible using the current set of rules. If the resulting normal forms are not equal, you create a new rule. For example, your 2.c. gives a new rule $x\circ(i(x)\circ z)\to e\circ z$. On the other hand, unifying $(x\circ y)\circ z$ with $x_1\circ y_1$ gives the critical pair $(x\circ y)\circ(z\circ z_1)\leftarrow((x\circ y)\circ z)\circ z_1\to(x\circ(y\circ z))\circ z_1$, which can be reduced to the trivial $x\circ(y\circ(z\circ z_1))\approx x\circ(y\circ(z\circ z_1))$ and discarded.
Whenever you create a new rule $l\to r$, you must consider all critical pairs between it and the existing rules $l_1\to r_1,\dots,l_n\to r_n$, checking for unifiability of $l$ with each non-variable subterm of $l_i$ and vice versa. Also remember to check for self-overlaps, i.e. unifiability of $l$ with its own subterms, as we did above for associativity. You only stop when all critical pairs of the existing rules have been examined and either produced new rules, or been discarded.

This procedure can be improved quite a bit. In particular, you can use new rules to simplify old ones (and possibly discarding them if they become trivial, meaning they are subsumed by the new rule), and a good heuristic for picking the next critical pair to examine can drastically cut down on the amount of rules.


Undecidability of TMs recognizing a decidable language The language $L = \{ \text{M} \mid \text{M  is a TM and the set of words w such that M halts on w is decidable} \}$ is given.

I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it should be similar to prove to the Rice Theorem, using a reduction. However, this hint isn't very helpful to me.

Given a machine $A$, construct a machine $M$ which on input $x$, acts as follows: run $A$ on the empty input, and if it ever halts, run the Turing machine encoded by $x$ on the empty input.

If $A$ halts on the empty input then the language $M$ recognizes is the halting language, while if $A$ doesn't halt on the empty input then the language $M$ recognizes is the empty language.


Reconstruct directed graph from list of ancestors for each node I have a problem that I encountered that boils down to the following:

Considered this directed graph I found on Google:

I have the following information available to me

Node: Ancestors

1 : 3
2 : 1 3 5 7
3 : Null
4 : 3 5
5 : 3
6 : 1 2 3 4 5 7
7 : 1 3
8 : 1 2 3 4 5 6 7

How can I re-construct the original graph in a reasonably efficient manner? I basically have large sets of data that I would like to have visualized as branches and merges(similar to a code repository, but not quite).

Note: While I believe my data shouldn't be disjoint, I'm somewhat certain my data is incomplete and will produce disjoint graphs, or at the very least have many separate "roots". There is no ordering to the data, everything must be considered random, the lists can also be thought of as sets.

Such a list can yield more than one graph. Consider 4: 1 2 3, 3: 2 1, 2: 1. One graph is $1\to 2, 2\to3, 3\to4$. A second graph is $1\to 2, 2\to3, 3\to4 , 2\to4$.


Random access memory and data What kind of data is stored in the RAM when it  is fresh out of manufacture?
Apart from certain basic instructions (if yes, what are they), are there numbers stored as well or are most of the memory cells just empty?

RAM is cleared after each power cycle.
The power-up value of cells depends on the technology.

Static RAM content is usually random (there is no preference between 0 and 1, but the same chip may present similar patterns after each power-up).
Dynamic RAM has the value corresponding to empty capacitors in the RAM array, which usually corresponds to ones, but there is no guarantee.
Dynamic RAM can retain data for several seconds when unpowered (very dependant on temperature) : One cannot assume a known state at power-up and recent DRAM (DDR3, DDR4...) need complex initialization sequences where the RAM controller stores and checks some values like FFFF/0000/AAAA/5555, ...)


Testing graph property on enumerated graphs I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not sufficient for my use.

So I had two questions:

Which would be the most user friendly and RAM efficient program/library to work with graphs, if I already have the graph with me.
What would be an easy and efficient way to generate graphs satisfying certian conditions. I tried to search about Nauty over net but it is difficult to find a tutorial.

If you need to generate graphs, you can look at nauty: this is useful if you want to check whether a claim holds for all $n$-vertex graphs up to some small $n$. If you fancy planar graphs, you can have a look at plantri. I would not be surprised if you don't find tutorials, since this type of software is usually intended for professional researchers (but generally speaking, you should have little trouble in compiling and running if you are familiar with the typical Unix-like software).

To answer question 2, you can find online (via the nauty homepage, for instance) collections of small graphs with certain properties. House of Graphs is also pretty nice, but not exhaustive. If the properties you care about are exotic enough, you will have to come up with your own generator and/or just discard the graphs that don't satisfy your property from some collection of all small graphs.

To answer question 1, again, if you need efficiency, it will hard to beat something like nauty and its many utility programs. These are quite well-optimized and thoroughly used pieces of software. If you insist on more user friendliness at the expense of efficiency, I can recommend Mathematica. More generally, it is often the case you will have to write your own programs to strike the right balance between usability and efficiency.

There are also automated systems for suggesting conjectures, particularly in graph theory. One system I have successfully used is GraPHedron [1], but note that the system is currently unavailable. There are similar systems out there, and you should find pointers from [1] and the later papers that cite it.

[1] Mélot, Hadrien. "Facet defining inequalities among graph invariants: the system GraPHedron." Discrete Applied Mathematics 156.10 (2008): 1875-1891.


Visit all vertices on directed graph We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. You can revisit vertices, but can't "use" edges twice or more time. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.

The first question you need to ask yourself, is when does it happen that there is no such vertex. For undirected graphs the answer is easy: such a vertex exists if and only if the graph is connected. DFS/BFS allow us to decompose the graph into connected components, and in particular we can find out whether there is more than one.

For directed graphs, it could happen that the underlying undirected graph is connected, yet the directed graph itself has no vertex from which you can reach all others. An example is a path with two edges directed toward the center. The corresponding refinement of the concept of connected components is strongly connected components, in which each vertex is reachable from any other. We can contract each strongly connected component to a single vertex, and then what we are left with is a DAG (directed acyclic graph; can you see why?). The question you should be asking yourself now is:

  Given a DAG, when is there a vertex from which all other vertices are reachable?

Once you answer this question, all you need is an algorithm for finding strongly connected components. There are several DFS-based algorithms for that available on the web.

(Note: while this may not be the simplest solution, that is, there might be "shortcuts", the concept of strongly connected components is inherently useful and good to be aware of.)


Subset sum-like problem over boolean vectors I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): Pseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

Let us say that $x \leq y$ if $x_i \leq y_i$ for all $i$. Suppose that your starting vectors are $x_1,\ldots,x_n$ and your target is $y$. If $x_i \not\leq y$ then $x_i$ cannot belong to any solution, so you can throw away all these vectors. The remaining vectors OR together to a vector $x \leq y$. If $x \neq y$ then there is no solution. Otherwise, take all remaining vectors – this is clearly the maximal solution.


Removing common background in image processing phase for classification I'm trying to build a machine learning classifier that can detect which object is in an image. I have a labled training set of images and am currently in the image processing phase. Each of these images has one of the objects. However, almost all images have these objects embedded in a very common background color amongst all images.

These are not the images i'm training on but they give the general idea:

The background red is more or less uninformative of what object is in the picture. In order to reduce the dimensionality of my problem, I'd really like to apply an algorithm that somehow extracts the object from the common background. My idea after that was then to resize the resulting images all to some common dimension. Then i was going to try to do some deep learning. Does anyone know any algorithms in computer processing that can do this?

Try using clustering on the histogram of pixel color values.  I would suggest using $K$-means using $K=2$ as a starting point, but you could use any clustering algorithm.

You might want to convert to HSV color space, build a histogram of the hues, and apply clustering on those values.  You could also try other color space models, like CIELAB, but HSV is probably good enough for your purposes.  Working in HSV space tends to yield techniques that are more robust to variation in lighting/illumination.

In your examples, the majority class (the cluster containing the majority of pixel values) is the background.  You could use heuristics, such as that the cluster that contains the majority of pixels along the boundary of the image is more likely to be the background.

The watershed algorithm or other methods of image segmentation could be an alternative approach that might work well.

If your images are as clean as shown in the example, almost anything should work well.


Solving largely monotone SAT formulas I just wonder if solving largely monotone SAT formulas (meaning most clauses do not contain negated literals, but some do) is in any way easier than general SAT formulas? In other words, are there heuristics specially designed for solving such formulas that are not applicable to more general SAT problems? I tried but didn't find any research in this particular direction.
Of course, what is considered "most" is up to interpretation, but let's say >95% of the causes are monotone.

The theory probably depends on the details. In practice, if you're only interested in solving an instance, here are a some thoughts:

Most literals should be eliminated in presolve of today's solvers. They eliminate all positive-only (or negative-only) literals.
Next, your setup implies that most literals should be set to $true$. Many solvers allow you to specify which assignment should be tried first ("initial phase"). By setting this to $true$, you should get fast solves.
The potentially exponential blowup from resolution might be avoided, if there are very few negated literals. Thus, BVE and DP-based solvers could be quite effective on such formulas.
Local search solvers (WalkSAT & Co) should also do very well.

Have you tried feeding your problem to Kissat or CaDiCaL?


Find point with smallest average distance to a set of given points Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest):

  Given $n$ points $P_i=(x_i,y_i)$ in the 2-dimensional plane, find the point $Q=(x,y)$ that minimizes the average distance from $P_i$ to $Q$.

In other words, we want to find $Q$ that minimizes the objective function $f(Q) = \sum_i d(P_i,Q)$.  Here $d(\cdot,\cdot)$ represents the usual Euclidean (L2) distance.  I'm told that in the coding contest this was phrased in terms of finding the best location to put a washroom somewhere in an office building, so that the average distance to all employees is minimized.

Is there an elementary solution to this problem?  In other words, a polynomial-time algorithm that does not require knowledge of advanced methods (say, beyond what undergraduate computer science majors could be expected to understand).

If we were on the 1D real line rather than the 2D plane, this problem would be easy.  In one dimension, the solution is exactly the median of $x_1,\dots,x_n$.  However, this does not seem to generalize to the 2-dimensional plane.  It's tempting to take $x$ to be the median of $x_1,\dots,x_n$ and $y$ to be the median of $y_1,\dots,y_n$, but this does not provide the optimal solution: a counterexample is to look at three points at three of the corners of a square.  (The component-wise median is at a corner, but the optimal location is somewhere inside the square.)

It looks like this problem is a special case of the two-dimensional Euclidean $p$-median problem, for $p=1$.  Apparently the two-dimensional Euclidean $p$-median problem is NP-hard when $p$ is part of the input (Megiddo and Supowit, SIAM J Computing 13(1) Feb 1984) -- but here we have the special case where $p=1$, so the NP-hardness result doesn't apply to this special case.  I haven't been able to use this search phrase to help find an algorithm.

If the distance metric was the Manhattan (L1) distance, there would be a number of clean solutions.  The component-wise median would be optimal, since the Manhattan metric is linearly separable in the $x$-coordinates and $y$-coordinates.  For similar reasons, we could solve it using linear programming.  However, here we have the Euclidean distance, which is not linearly separable, so those methods do not seem to apply.

See also Find the point with minimum max distance to any point in a set, which looks at a related but different problem, the smallest-circle problem, where the objective function is $g(Q) = \max_i d(P_i,Q)$.  However, the techniques used for that problem don't seem to apply here.

Right now the approach I can see is a heuristic algorithm: use standard black-box optimization methods such as hill-climbing or gradient ascent to find the point $Q$.  However, there is no guarantee that this finds the exact optimum.

If there's a solution that does not require understanding advanced computational geometry algorithms (e.g., Voronoi diagrams, Delaunay triangulation, etc.), even better!

This point is known as the geometric median, also known as the 1-median.

Apparently, there is no simple algorithm for computing the geometric median.  Instead, one must use some kind of numerical approximation.  Wikipedia mentions Weiszfeld's algorithm, which appears to be a kind of iterative descent algorithm, and cites other more sophisticated algorithms.

This is a special case of the Weber problem, a facility location problem.  Standard solvers for facilitation location problems be able to compute the geometric median for you, by framing this as an instance of the Weber problem.


Existential Theory of the Reals in NP? It is known that the existential theory of the reals is decidable in PSPACE (via John Canny), but as far as I can tell no one has demonstrated that it is in NP. This confuses me because it seems like a short certificate for a given formula would be an example of values for the variables included in the formula that demonstrates a valid assignment. Why is this argument invalid?

No, unfortunately that doesn't work.  The certificate needs to be a sequence of bits that is verifiable in polynomial time -- and thus the length of the certificate has to be at most a polynomial in the length of the input instance.  If your certificate is the value of some variables, and those values are real numbers, you might not be able to write down their binary representation in any reasonable amount of space (indeed, their binary representation might be infinite-length).

For instance, consider the sentence $\exists x . x^2 = 2$.  This sentence is valid, as $x= \sqrt{2}$ is an example that makes $x^2=2$ true.  However, when you try to write out $\sqrt{2}$ in binary, you get an infinite sequence, so it's not clear what the short certificate would be.  (Certificates need to be of finite length, certainly.)  In general, representing real numbers in binary is messy business; no matter what representation you choose, there will always be some real numbers you can't represent finitely.


Choosing heuristic for A* algorithm where cost is less than absolute distance Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one.

For example, say movement is allowed in the cardinal directions. Should all edge costs be at least one, then I would consider diagonal distance. However, if costs can be less than one, this could lead to an instance where diagonal distance will be an overestimate and thus is not an admissible heuristic.

My thought on the matter is perhaps to find the smallest possible cost and figure out a constant to divide diagonal distance by to guarantee it will never overestimate?

Would appreciate some guidance or some resources to look further into this.

The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path.

The more complicated option is to look at the graph and estimate the chance that you will end up going through the low cost area. This requires some precalculation of the low cost areas and their influence on paths.

For example a low cost highway, any heuristic that is close to it will need to get a bonus to account for taking the highway. But heuristics that are not going to take the highway can use the larger estimation.


Understanding DIQKD protocol, a few questions I'm refering to this paper here "Fully Device-Independent Quantum Key Distribution" (Umesh Vazirani and Thomas Vidick) and unfortunately there are many things I don't understand.

1) Page 3: by the word round, what do the authors actually mean? Is it right to say it's basically how many times Alice and Bob use their own devices?

2) Page 3, Testing section: this equality aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ I was told it describes the requirement of the CHSH game. Alice input can be anything belonging to the set {0,1,2} while Bob's input can only be an element of the following set{0,1}. Their output can be 0 or 1, respectively.
The paper says "They compute the fraction of inputs in B that satisfy the CHSH condition aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ..". My understanding is: if ⊕ is exclusive OR and ∧ is logical AND then the following makes sense:  aᵢ=1 bᵢ=0    1 ⊕ 0 = 1 ∧ 1 Is that correct? If I'm right what does the following expression mean? "If this fraction is smaller than cos2 π=8 − η they abort the protocol"

Cross-posted on quantumcomputing.SE

All of these are defined in page 2 of that paper.

1) A round is a single interaction with the device: Alice gives it an input, Bob gives is  an input, and the device outputs a bit to Alice and a bit to Bob.

2) While Alice's input is from the set $\{0,1,2\}$, the output she gets from the device, $a_i$, is a single bit. Then, the equation $a_i \oplus b_i = x_i \wedge y_i$ is on bits (the case of $x_i=2$ is treated separately). This equation is indeed the CHSH condition. If the bits where classical, the expected CHSH term is bounded by $2$, while if the system is quantum, values of up to $2\sqrt2$ are possible. By measuring the amount of times the equation holds you can estimate the value of the expected CHSH term, and if it is large enough, this implies the generation of "true" randomness.

There is a longer and more detailed version of that paper in
https://arxiv.org/abs/1210.1810


if $\delta(q, a) = q$ for all symbols $a$, show that $\delta^* (q, w) = q$ is true for all strings $w$ Let $A$ be a DFA and $q$ a particular state of $A$, such that
  $\delta(q, a) = q$ for all input symbols $a$. Show by induction on the
  length of input that for all strings $w$, $\delta^* (q, w) = q$.

I'm completely new to the subject. But this is what I have done. Can someone please tell me if this is the correct solution?

For the basis of the induction $|w|=1$, $\delta (q,a)=a$ is already correct by definition.

Let $n = |w|$, the number of symbols in the string $w$. Let $\delta^*(q,w)=q$ be true for some $n \gt 1$ (hypothesis of induction). Now I should prove it for $n+1$ using the hypothesis of induction. Let $z=wa$.

$$
\delta^*(q,z) = \delta^*(q,wa)
$$

It follows that:
$$
\delta^*(q,wa) = \delta^*(\delta^*(q,w),a)
$$

From the hypothesis, I know that $\delta^*(q,w)=q$, so if I substitute this in the above equation:

$$
\delta^*(q,a)
$$

and this is equal to $q$ according to the base case. So, I conclude that $\delta^*(q,w)=q$ is true for every $n$.

Is the above so-called "solution" correct?

By popular request, here is what the proof could look like:

  By induction over the length of $w$.  Assume $\delta(q,a)=q$ for all
  $a$. Take any $w$. There are two cases:

  If $|w|=0$ then $w=\epsilon$ (the empty word). Now the definition of $\delta^*$ has "$\delta^*(q,\epsilon)=q$" without any assumption
  on $\delta$ or $q$. We thus have $\delta^*(q,w)=q$ in this first case.
  If $|w|>0$ then $w$ is some $w'a$ and $|w'|<|w|$. Now $\delta^*(q,w)=\delta^*(q,w'a)=\delta(\delta^*(q,w'),a)$ by definition
  of $\delta^*$. Since $|w'|<|w|$ we have $\delta^*(q,w')=q$ by
  induction hypothesis. Finally $\delta^*(q,w)=\delta(q,a)$, which is
  $q$ by the assumption. We have proved the required conclusion in this
  second case too.

  All cases have been covered. The proof is complete.

  Note that the two cases can be considered in any order we like. And
  that we do not use that $|w'|=|w|-1$, just that $|w'|<|w|$.

As you can see, the above proof uses the same arguments as in your solution, and at the same places. It is slightly more rigorous on the quantifications ("take any $w$" is a "$\forall w$" and "$w$ is some $w'a$" is a "$\exists w'\exists a:w=w'a$") and their nesting ($w'$ and $a$ depend on $w$).

It is the kind of proof I'd love to get from a bright student beginning automata theory. But it is too pedantic and pedestrian for experts who, in their own papers, will usually just state the conclusion as obvious from the assumption. They may even not state the conclusion at all and use it anyway.


Clarifiaction on the NP-hardness of k-SUM-variants I am currently looking into the $k$-Sum Problem and some of its variants. However i stumbled onto an inconsistency, that i can not seem to fix.

If we begin with $3$-Sum, the 'textbook'-definition goes something along the way of

  Let a set $S$ of $n$ integers be given. Are there $a,b,c\in S$ such that $a+b+c=0$.

From this definition however it is not immediatly clear, whether $a,b$ and $c$ have to be distinct. Compare this to this paper. In the Introduction they state

  The $k$-SUM problem is the parameterized version of the well known NP-complete problem SUBSET-SUM,and it asks if in a set of $n$ integers, there is a subset of size $k$ whose integers sum to $0$.

This seems to imply, that duplicates are not allowed, as sets usually dont permit duplicates. However in Section 2.2 of the same paper they reduce $k$-SUM to $k$-Table-SUM and link to Section 3.1 of this paper, where the reduction only works in the case, where duplicates are allowed.

Are these two variants equivalent? If so, are there possibly any sources on this? And furthermore, is $k$-Table-SUM NP-hard? Intuition and "closeness" to the $k$-SUM would suggest this, but i haven't found a proof for this apart from the linked sources with the noted inconsistencies.

Thanks!

Edit:

I finally found two sources that can answer this properly. The first contains a reduction from 'Perfect Code' to $k$-SUM without duplicates, however the k-SUM instance is constructed in a way, that allowing duplicates wouldn't find any other solution here (specifically at 22.5.3). In case anyone is not familiar with perfect code, at 22.2.1 the authors reduce Indepenent Set to Perfect Code.

The second source actually links to the first. They reduce $3$-SAT to $k$-SUM in Theorem 5.1. Note that the proof specifically states, that they seperate the instance into d blocks, and then make sure that $k$-SUM only finds one entry per block. This is exactly the same as $k$-Table-SUM and also easily reduced to $k$-SUM with duplicates, similar to the accepted answer.

Yes in case of 3-sum problem they are equivalent. Let $P$ be the version where the three numbers have to be distinct and $P'$ the version where you can use the same number multiple times. The reduction $P'$ to $P$ is by solving the cases with overlapping in preprocessing (since both overlapping cases can be done in almost linear time).

The other direction is a bit more complicated. We will reduce $P$ to another variant $P''$ and from $P''$ to $P$. We start by defining $P''$: given three sets of integers $A,B,C$. Can we pick a number from each to sum to zero.

$P''$ to $P'$ is quite easy. Let $M$ be the largest number in all sets. Let $U := 3M + 1$ build the set $$S := \{a+U:a\in A\} \cup \{b + 2U: b\in B\} \cup \{c-3U:c\in C\}$$ as input to $P''$. Try to prove why the reduction is correct as an exercise.

Now the last reduction from $P$ to $P''$ is a bit more complicated. It is actually randomized. Fix a correct tripple in $S$. A random partition of $S := A\dot\cup B \dot \cup C$, we will have the numbers in the triple assigned to distinct sets with probability at least $2/3 \cdot 1/3 = 2/9$. By repeating a constant factor of $\log n$ you get a running time of $O(n\log n)$ reduction with high probability.


What is this problem? Largest set of contiguous x values for which the same y value can be held I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it.  The best I've come up with is:

  Given a set of rectangles on a plane find the set(s) which allow the same y value for some largest contiguous set of x values.  All rectangles are axis aligned, the same width, and do not overlap.

I find this much easier to visualize so below is an example problem instance and solution.

Edit:

We have a linear solution that has a constant factor on the order $y_{max} - y_{min}$ which can be pretty big.  Here is an idea of the algorithm I've been trying to work out since originally posting this.

Rectangles are already sorted by $x$ position.
Maintain an ordered list $I$ of the intervals currently allowing a contiguous line.
Maintain two variables $(i_{min}, i_{max})$ which are the min and max
$y$ value of the current intersection (in the example solution $(5, 5.25)$).
Iterate from $x_0$ to $x_{max}$
At each $x$ position test if any of the current rectangle(s) intersect $(i_{min}, i_{max})$.

1) If yes, add the rectangle to $I$ and update $(i_{min}, i_{max})$.
2) If no, find the longest suffix of $I$ s.t. it allows overlap with current rectangle.
3) If no suffix exists or the current $x$ position has no rectangles skip to the next $x$ position with rectangles and reinitialize $I$, and $(i_{min}, i_{max})$.

In #2 and #3 save the current $I$ if it allows the widest contiguous line so far.

Here is a slightly different algorithm. Start by sorting the list according to the $y$ value. Iterating through all different $y$ values, maintain a list of all rectangles which intersect the given $y$ value, as well as the $x$-intervals that they span. When you lose an interval, you need to split a range. When you add an interval, you need to find which intervals, if any, it is adjacent to, and then enlarge the interval and possible merge two intervals. Some kind of search tree containing all endpoints of the current intervals can be useful for locating the intervals adjacent to a new segment (if they exist). Maintaining the intervals (shortening, splitting, enlarging, joining) should be possible with a Union-Split-Find data structure.

If you use the correct data structures, this algorithm should run in time $O(n\log n)$, where $n$ is the number of intervals. (That's an informed guess.)


Showing that graph of spanning trees are connected Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$.

We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in $ST_2$ (and vice versa).

How do we show that $H$ is connected?

Use induction on the number of edges and vertices in $G$.  Fix some edge $e$ of $G$.  If $S$ and $T$ are two different spanning trees that do not use $e$, apply the induction hypothesis on the graph $G\setminus e$.  If both use $e$, apply the inductive hypothesis to the contracted graph $G/e$.  If only one does, w.l.o.g., $S$, replace $T$ by $T'$, obtained by adding $e$ to $T$ and removing any edge in the (unique) cycle in $T+e$.  Either $T'$ is $S$, or we are back in a previous case.


Prove Halting on all Inputs is not in RE simulation I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine that the halting problem receives as input) on w(the word received as input) for n steps.

Can somebody explain to me who is n and why do we need to simulate M for n steps? Why not only once?

For proving that halting on all inputs problem is not in RE, the complement of halting problem is used. Supposed we take M(w) as the turing machine used for halting problem, I get the next simulation:

M'= simulate M(w) for n steps;
        if M(w) halts, make it loop
        else, stop.

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

N stands for the length of the word. I don't understand the simulation for a number of steps. Why is that?

What is the Halting on all inputs problem?

It is the problem about the language $TOTAL=\{⟨M⟩\mid M \text{ is a TM and }M\text{ halts on all inputs} \}$.

What are all inputs? Let us fix $\Sigma$, the set of input symbols for Turing machines. The set of all inputs is $\Sigma^*$, the Kleene star of $\Sigma$. Let $E$ be a Turing machine that computes a one-one correspondence $cor$ from $\Sigma^*$ to nonnegative numbers.

In order to specify the behavior of a Turing machine $M$ whose language/encoding is in $TOTOAL$, we will just specify its behavior when the input is a nonnegative integer $n$ with the understanding that we are actually specify its behavior on the input that corresponds to $n$ under $E$.

What is the complement of the halting Halting problem?

It is the problem about the language $\overline{HALT}= \{⟨M, w⟩\mid M \text{ is a TM and }M\text{ does not halt on input } w\}$.

Given a word $⟨M, w⟩$ where $M$ is a Turing machine and $w$ is a input word, how can we construct a new Turing machine related to the way how $TOTAL$ is specified?

  $M'$ = simulate $M(w)$ for $n$ steps; if $M(w)$ halts, make it loop else, stop.

The above quotation of a construction is too brief to be understood correctly easily. Here is a more detailed construction that should be easier to understand.

  $M' = $ "On input $x$, use $E$ to compute $cor(x)$. Simulate $M$ with input $w$ as long as possible but for no more than $cor(x)$ steps. If the simulation halts, continue to loop forever; otherwise, halt."

Now you should be able to check that
$$⟨M, w⟩\in\overline{HALT} \Longleftrightarrow M'\in TOTAL.$$

The too-brief version equates $x$ with $cor(x)=n$, which could be very confusing for beginners although acceptable for users experienced in the theory of computability.

  I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

The "N" in "N STEPS" is/represents/encodes the input to $M'$. It is a variable independent of $M'$.


What actually is the concept of transparency? Why not call it Abstraction? I searched this over Google few times but ended up with articles on transparency rather than an answer.
With relation to distributed database study(or distributed OS), what is the concept of transparency?
I mean in replication, fragmentation and everywhere I guess the idea is to implement these concepts but not to bother user about them. Correct me if I'm wrong but I think the idea is "User shouldn't know?". Then HOW is this transparency? Isn't it abstraction? Hiding the implementation details?

I agree with you.  The distinction is pretty weak.

I think the rationale is that transparent is supposed to mean "invisible", or "you don't even know it's there."  Abstraction means that you don't see the implementation of something, but you know that it's there.

Example: Consider Linux.  There's one command,  cp <srcfile> <destfile> for copying files on the mounted file system.  There's a completely different command, usually scp <user>@<machine-name>:<srcfile> <destfile> for copying a file from a remote filesystem that is mounted on a remote machine.  scp is an abstraction in that it hides all the implementation details about contacting the remote machine using the ip protocol, the encryption of the channel, and the mechanics of accessing the disks on the local and remote sides of the transfer.  But in no way is the distinction between a local file and a remote file transparent.  You have to use a different command depending on where the file is.

Worse, you can't edit the remote file in-place.  With a local file you just open the file in your text editor.  With a remote file you have to scp it to your local file system, edit the copy, and then scp the modified file back to the original location.


Will random function ever hit a hard coded decimal number? I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages.
But I am curious, will random function ever hits a hard coded decimal number?
I know mathematically it is impossible, but how about in computer science?
Such as the following javascript code, will it ever hit the number and stop?
// this can be any number
const rnd = 0.123456;

while (true) {
    if(rnd === Math.random()) {
        console.log('hit');
        break;
    }
}

Also I ran that code for 2 hours and it didn't stop

If decimal points are store in 64 bit, does that mean the chance to hit any decimal point is 1/2^64?
If it can hit, is 0.000123456 harder to hit than 0.01?

Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 <= rnd < 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0.123456 will never be hit.
But even if 0.123456 would be hit eventually, that random number generator would produce 2^53 possible values. On average it needs to produce 2^52 values before a match. That isn't going to happen within two hours. Assuming 10ns per number, 10ns * 2^52 is about 45 million seconds, or 521 days.


Definition P-Completeness I've got this problem:

  Write down a definition of P-completeness analogous to the definition of
  NP-completeness, i.e., using polynomial-time reductions.
  Which problems are P-complete in this sense, and why?
  Thus, what is the problem, i.e., what must be changed if the goal is to come
  up with a more interesting notion of P-completeness?

I have an idea about the first part, but I don't have any idea about the second and third part. The first part is like the NP-Complete, and small change for P-Complete, which is wrong I know, but I want it that way!

You should really work this out yourself, but here are a few hints.

Define P-completeness just as you say, by taking the definition of NP-completeness and changing NP to P. Then ask yourself which problems are P-complete. For a problem to be P-complete it must be in P. What about the other condition? Can you come up with a problem in P which you'd conjecture shouldn't be P-complete under your definition?

Once you've answered part 2, you will be able to answer part 3, so don't despair if you have no idea what they want in part 3 right now.


What is the point of selection step in a genetic algorithm? I'm reading about genetic algorithms, and I'm not sure I understand the point of selection step.Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

From what I understood till now we select a number of chromosomes (I still don't know how many should we select) and let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ? I'm not sure I got it right.Someone can clarify this for me ?

Thank you !

I think the confusion can be isolated in this sentence: "From what I understood till now we [...] [choose] $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration?"

Selection plays the role of the hand of death. Unselected organisms correspond to those that died without reproducing. Far from being left "untouched for the next iteration", unselected organisms are discarded. Now, to maintain the population size, we need to create new organisms to replace the discarded ones. This is done by applying mutation and cross-over to the chromosomes of the selected organisms. The next generation will contain a mix of the selected organisms that are left untouched, and mutants of those selected organisms. Biologically, the idea is that the next generation is the organisms that survived and their children. As an optimization technique, the idea is to cull out bad solutions and consider only variations of the "best" current solutions.


Implementation of datatypes in Haskell? In Haskell, are datatypes converted to the "Church encoding" i.e. folding the data type.  For example, given

data N = Z | S N

in Haskell, it can be converted to its church encoding by

foldN Z z s = z
foldN (S n) z s = s (foldN z s n)

Where if we do foldN m, we get the church encoding:

\z s . s (  .... s n ... )

In Proofs and Types, Girard shows how this works for any inductive datatype.  There are two questions I have: (1) is this actually how Haskell treats datatypes and (2) what is the equivalent construction for coinductive datatypes.

To answer the question: No implementation of Haskell to my knowledge has ever represented datatypes as church encodings.

I believe that church-style encodings (or variants such as Scott encodings) work equally well for coinductive types.


For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$? My question related to relativized world. I would like to know about how to show that class is different from another class in the oracle world and whether this applied to our real world.
For example, let us have the following assumption: suppose for all oracles A we have $P^A \neq PSPACE^A$, then Does it imply that $P = PSPACE$?

If $A = \emptyset$, or more generally, if $A \in \mathsf{P}$, then $\mathsf{P}^A = \mathsf{P}$ and $\mathsf{PSPACE}^A = \mathsf{PSPACE}$, and so $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ is the same as $\mathsf{P} \neq \mathsf{PSPACE}$.
It is also interesting to ask whether $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ for a random oracle implies $\mathsf{P} \neq \mathsf{PSPACE}$. This was disproved (with $\mathsf{P}$ replaced by $\mathsf{IP}$) by Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi in their paper The random oracle hypothesis is false.


Is finding if a graph has k isolated nodes a NP-Complete problem? I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem:

  Prove that the following problem is NP-Complete. Given a set of T
  transactions: $T = \{t_1,t_2,\dots,t_m\}$ where each transaction $t_i$ is a
  pair of banks $(b_{i1},b_{i2})$.  Find if, given an integer value k, there
  is a group of k banks that doesn't perform any of the given T transactions.

I was thinking to proceed this way:

Input complete graph with all the Banks: $G=(B,E)$
Subtract to E the T set, I obtain a new graph, $G'=(B,E\setminus T)$
Find if there's an existing k-clique in $G'$

Is there any more effective way to solve this problem?

No, determining whether a graph has $k$ isolated vertices is not1 NP-complete. Just count the number of isolated vertices and compare against $k$. This can be done deterministically in linear time (linear in the size of the graph's description; possibly quadratic in the number of vertices).

1 Unless P=NP and, even then, it might not be NP-complete.


Efficient serialization/deserialization of huffman tree I have implemented huffman encoding in the form

struct node
{
    node * left;
    node * right;
    double freq; // the frequency
    string letter;
    string binary_code; // the variable length code
};

that works fine, eg:

Data: electric eels
Compressed: -σ» //doesnt render in this text editor sorry
Decompressed: electric eelss
Ratio: 38%

But I have no idea how to efficiently encode the tree itself (needed for the decompression) to send over socket, and then decode it.

Can someone help me with some c code/pseudocode style explanation?

Any help appreciated.

The usual approach is to build Canonical Huffman code from the frequencies and use it to encode the data.

Canonical Huffman code can be encoded in a pretty compact way, as was described in the ZIP APPNOTE.TXT file, look for words Shannon-Fano and Huffman.

You can find C code in any deflate/inflate implementation or Huff0.


How to use Type application Rule to get a desired type In type application Rule :

$$\dfrac{ \Gamma \vdash t_1  : T_{11} \to T_{12} \qquad \Gamma \vdash t_2 : T_{11}}
        { \Gamma \vdash t_1 \ t_2  : T_{12} }
        \textsf{ (T-App)}$$

if we deriving the term from bottom up, how to get $T_{11}$ from ? How you'll know what is $T_{11}$?  Its not clear to me.

You can look at this rule in two ways:

As a checking rule, it says that, to verify that $t_1 t_2$ has type $T_{12}$, we check that there exists some $T_{11}$ such that $t_1 : T_{11} \to T_{12}$, and we check that $t_2 : T_{11}$. If these checks hold, then the typing of the application must hold.

As an inference rule, it says that to infer the type of $t_1 t_2$,
we infer the type of $t_1$ and verify that it has the form $T_{11} \to T_{12}$ for some types $T_{11}, T_{12}$, infer the type for $t_2$ and check that it is equal to $T_{11}$. If these checks hold, then we return $T_{12}$ as the type of the application.

So for knowing what $T_{11}$ is, it depends on what you're doing. If you're doing checking, then usually it is a type that has already been given to you. If you're doing inference, then you infer the type of the function, and inspect that type to verify that it's an arrow type, and can be broken into its parts. $T_{11}$ is one of these parts you break it into.

There's nothing saying you need to get $T_{11}$ only from the function's type. You could alternately infer it from the type of the argument, and then verify that it matched the function type.


What is softmax in reinforcement learning? There are multiple very complicated articles about softmax online. I just want to know a few things about it:

Why do we need softmax? What is the "problem"? What does it do?
How does it do it?

I find it very hard to get through all the math when I don't really get what it is all about. The problem is that all the things I read online is very complicated written and no one seems to just get to the point.
I hope you can help.

Ok, I have read a very good explanation to what softmax is.
A dog is programmed to walk through a maze. One start point has very few walls. The way it is programmed with the epsilon greedy algorithm, the dog will sooner or later start to walk mostly to the right or mostly to the left. That is a problem because it at some point might just walk in a circle the entire time. To get that out one could make it choose left or right randomly from time to time - but that is not really a good approach for obvious reasons.
So instead you use something called softmax. Softmax just smoothens the decision process: like taking out the walking-left or walking-right.


How to understand the solution to Task Scheduler problem on LeetCode? LeetCode Task Scheduler problem is the following:

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There are at least 2 units of time between any two same tasks.

Example 2:
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

This is a solution I found:
    def leastInterval(self, tasks: List[str], l: int) -> int:
      freq = [0]*26
      maxOccurrence = 0

      for task in tasks:
        freq[ord(task) - ord('A')] +=1

      freq.sort(reverse=True)

      idleBlocks = freq[0] - 1
      idlesState = idleBlocks * n

      for i in range(1, 26):
        idlesState -= min(freq[i], idleBlocks)

      return len(tasks) + max(0, idlesState)

Basically, it works like this:
Given the tasks  ["A","A","A","A","A","A","B","C","D","E","F","G"]

Sort the tasks by frequency descendingly

{ A: 6, B: 1, C: 1, D: 1, E: 1, F: 1, G: 1 }

We first place the most frequent character. All the spots between the same characters are first idle.

A _ _ A _ _ A _ _ A _ _ A _ _ A

We try to fill the remaining characters in the idleSpots using the sorted task array. (most frequent filled first)

A B C A D E A F G A _ _ A _ _ A

If the idleSpots < 0, we return the total number of tasks, else we return the total number of tasks + idleSpots.

I'm having issues proving this statement:
If the idleSpots < 0, we return the total number of tasks.
In other words, if we manage to fill all the idle spots between the most frequent character, why are we sure to complete all the tasks without complimentary idle tasks?
How come we can't we end up with a case like this
A X X A X X A B _ _ B _ _?
Where X represents a character such that the idle spots between all the As are filled.
Can you give me some hints?

When idleSpot (or, as in the code, idleState) is zero or negative, it means we have enough tasks other than A to fill the required minimum cooldown periods between A tasks.
Well, suppose BB are the overflowing tasks. Instead of appending them to the end of scheduling queue, we can just insert them, one right after each A.  So instead of
$\quad$A X X A X X A B _ _ B _ _
we will have
$\quad$A B X X A B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Bs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.
If we have addition overflowing tasks, such as CC, then we can do the same thing, inserting them one right after each A. So we would have
$\quad$A C B X X A C B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Cs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.
And so on.


Additional clarification about Simultaneous Multithreading I was looking for comments about SMT and got several responses. The last one looks strange:

  Simultaneous multithreading, which can only be implemented on a multicore system, executes the different threads on different cores, or on different processing units on the same core ("superscalarity").

Why can SMT be implemented only on a multicore system? Hyperthreading is normally used to improve performances by filling the most possible the functional units? Not? So, it seems to me that we could have only one core with hyperthreading..

What have I not understood ? Is the term 'processing unit' referred to as 'functional unit'?

The confusion seems to be different terminology used in different sub-communities of computer science.  To most computer scientists, simultaneous multithreading, is thought of as any situation in which two threads seem, to the operating system, to be physically executing in parallel.  When computer architects (including the well-known textbooks by Hennessy and Patterson) use the term they are referring specifically to the technique described in the paper: Tullsen, Dean M; Eggers, Susan J; Levy, Henry M: Simultaneous Multithreading: Maximizing On-chip Parallelism, Int'l Symp Comp Arch, (ISCA-22):392-403, 1995.

That is, computer architects are specifically referring to providing two or more hardware thread contexts on the same super-scalar core, and not to simultaneously executing threads on different cores.

Hyperthreading is typically used, by computer architects, as a synonym for the same thing: providing two or more hardware thread contexts on the same physical super-scalar core.  As pointed out by @PaulA.Clayton the term "Hyper-Threading" was invented by Intel as a marketing term, but Intel has sometimes used it to refer to hardware simultaneous multithreding, and sometimes to refer to coarse-grained hardware multithreading on the Itanium 2, but then does not use Hyper-Threading to describe the fine-grained hardware multithreading on the Xeon Phi.


Does the memory get unallocated when program exits? I have been trying to manipulate pointers just for the sake of studying. I have had some problems with some programs I wrote where I had memory leak. Does this memory stay allocated even when the program returns? If yes how to deallocate it?If no why, isn't all saved in heap so only the one who has that heap pointer can deallocate? Or does the operating system pull some magic tricks?

When you run your program its memory allocations take the form of page allocation requests to the operating system.  When your program terminates, the operating system notices and returns all the allocated pages to the list of free pages, which can then be used by other processes.  It does not matter if your program leaks memory (other than potentially using more memory as a result), because ultimately the operating system will reclaim everything.


Are disjoint edges the same as matchings? I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings.
To support this, I am also watching Coursera's Approximation algorithms course by EIT digital.
This video mentions using disjoint edges and would like to confirm that the 2 are actually the same and I am not missing and subtle details.

Two disjoint edges $(a,b)$ and $(c,d)$ are edges that do not share any endpoint, i.e., $\{a,b\} \cap \{c,d\} = \emptyset$. A matching is a set of pairwise disjoint edges.


Quotient in LOOP program I want to construct a LOOP-computable program for the integer division (quotient):

x = a DIV b

The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)

I don't know how to do this without a while.

Look for the unique integer $x$ such that $b x \le a$ and $b(x+1) > a$. With this approach, you don't need a WHILE statement.


Size of neighborhood in local search for symmetric TSP I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things.
The given example said:

  Suppose we have an instance of the symmetric TSP with n nodes and the neighborhood $N^k$.
  Here $N^k$ is the $k$-change-neighborhood (delete $k$ edges and afterwards insert $k$ other edges).

We define $\gamma_{n, k}$ to be the number of possibilities to delete $k$ non-adjacent edges in a given tour.

If I understand this correctly, it should be as follows:
$\gamma_{n, 0} = 1$, $\gamma_{n,1} = n$, $\gamma_{n, 2} = n(n - 3)$, and so on.

  Is there a formula for $\gamma_{n,k}$?

Let $\delta_{n,k}$ be the number of ways to select $k$ nonadjacent edges on a path of length $n$. We can compute $\delta_{n,k}$ using a simple recurrence:

$\delta_{n,0} = 1$.
$\delta_{0,k} = 0$ for $k > 0$.
$\delta_{n,k} = \delta_{n-1,k} + \delta_{n-2,k-1}$, where the first term corresponds to the case in which the first edge is chosen, and the other to the case in which the first edge is not chosen.

We can solve this recurrence and obtain $\delta_{n,k} = \binom{n-k+1}{k}$. Indeed, this satisfies the two base cases, and the inductive case is just Pascal's identity $\binom{n-k+1}{k} = \binom{n-k}{k} + \binom{n-k}{k-1}$.

To compute $\gamma_{n,k}$, choose a first edge arbitrarily. If it is chosen, we are left with a choice of $k-1$ edges in a path of length $n-3$, and otherwise we are left with a choice of $k$ edges in a path of length $n-1$. In other words,
$$
\gamma_{n,k} = \delta_{n-1,k} + \delta_{n-3,k-1} = \binom{n-k}{k} + \binom{n-k-1}{k-1}.
$$
This gives
$$
\begin{align*}
\gamma_{n,0} &= 1, \\
\gamma_{n,1} &= \binom{n-1}{1} + \binom{n-2}{0} = (n-1) + 1 = n, \\
\gamma_{n,2} &= \binom{n-2}{2} + \binom{n-3}{1} = \frac{(n-2)(n-3)}{2} + (n-3) = \frac{n(n-3)}{2},
\end{align*}
$$
and so on. Note that there is a difference in normalization: you count the edges with order, and I count them without order. This explains the factor of 2 in $\gamma_{n,2}$. In general, to take the order into account you need to multiply $\gamma_{n,k}$ by $k!$.


Can we add dependent type into an existing imperative programming language? As we know, dependent type allows programmers to write bugless programs.
But as I know there's only very few languages support dependent type, like Haskell with extensions, Idris, Agda, F*, etc.

Since these are all functional languages, is there any possibility to add dependent type into an imperative language?

I've googled and found some papers like http://www.ats-lang.org/MYDATA/Xanadu-lics00.pdf or https://www.cs.bu.edu/~hwxi/academic/papers/XanaduAbs.ps, but they create their own languages.

So, it's possible, but there are certainly some barriers:

What kinds of expressions are allowed in types? What does it mean for a type to have a side-effect? Can typrchecking my program perform IO?
Just because dependent types are in the system doesn't mean they provide a type safe language. It may be possible to produce proofs of False if the underlying type system is not consistent.
Many imperative languages don't have type systems complex enough to make dependent types useful. For example, Go has no higher kinded types, so if you can't index types by types, indexing types by values probably won't work.
Depending on the language, some additional type annotations might be necessary to make type checking decidable.
It may be hard to interpret dependent types in the context of side effects. What does a value of type $x=y$ even mean if $x,y$ can change their values at runtime? Does this mean a term can be well typed at one point, and dynamically become ill typed? Or can you only use dependent types for immutable values?

I'm sure that imperative dependent types are possible. In particular, I'd keep my eyes on Rust for adding these in a limited way.

But doing dependent types in a pure functional language is just so much easier.


sequence of problems that take $\Theta(n^k)$ for increasing $k$? Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly?

Suppose for example that we would know that finding a k-clique takes $\Theta(n^k)$, then this sequence could be {1-clique, 2-clique, 3-clique, ...}. However, perhaps there are more efficient algorithms for k-clique, so this answer is incorrect.

EDIT:

By the Time Hierarchy Theorem (which includes "P does not collapse to DTIME($n^k$) for any fixed $k$"), such a sequence should exist.
After some discussions in the comments, common NP problems are not good candidates. If it takes only $O(n)$ time to check a certificate (or $O(n^c)$, where $c$ is a constant independent of $k$), it would imply that $P\neq NP$

You leave the computational model open. I will assume that the question refers to random access machines (RAMs), as that is customary when one asks for the actual exponent in polynomial time.

Let $P_k$ be the set of (encodings of) RAMs $M$, such that $M$ halts in at most $|M|^k$ steps using at most the initial $|M|^k$ memory cells. A universal RAM can solve $P_k$ in $O(n^k)$.

On the other hand, $P_k$ is the universal problem for $DTIME(n^k)$ (in the RAM model and under linear time reductions). As a special case of the RAM version of the time hierachy theorem, a simple diagonalization shows that all algorithms for $P_k$ have running time $\Omega(n^k)$. Thus the complexity of $P_k$ is $\Theta(n^k)$ as asked.

The tightness heavily relies on the computational model. The Turing machine version of the time hierarchy theorem has a $\log n$ gap. Let $P'_k$ be the set of (encodings of) Turing machines $M$, such that $M$ halts in at most $\frac{|M|^k}{\log n}$ steps. Then $P'_k$ can be solved in $n^k$ time by a universal Turing machine and all algorithms have running time $\Omega(\frac{n^k}{\log n})$. I suspect this is the best one can do.

[EDIT]

In a comment, you ask for more conventional problems, like graph problems or logic.

First, let me point out how $k$-Clique (as suggested in the answer) does not seem like a good candidate. If we could prove that $k$-Clique requires time $\Omega(n^k)$ (or $\Omega(n^{f(k)})$ for some unbounded $f$), we have implied that Clique is not in P. And thus that P is different from NP. That is not likely to be easy. The same holds for slices of any other problem that we know to be in NP, or in some other classes like PSPACE that are unknown to be different from P.

Every problem can be rephrased as a graph problem, by encoding the input as a graph. I don't know if you would call a graph version of $P_k$ conventional. I wouldn't call it natural.

As for logic, I can provide an example. It is not boolean logic however, and there is a gap between the lower and upper bound. The example is based on the Immerman-Vardi theorem. Let $\mathcal L$ be first-order logic extended by least-fixed-point operators. Let ${\mathcal L}^k$ denote the fragment where only $k$ first-order variables are allowed. It is permitted to re-use variables, so the restriction is that each subformula has at most $k$ free variables. The Problem $M_k$ is the model-checking problem for ${\mathcal L}^k$, that is on input of a formula $\varphi\in{\mathcal L}^k$ and a structure $\mathfrak A$ of matching vocabulary, the task is to decide whether $\mathfrak A\models\varphi$, that is whether $\varphi$ is true in $\mathfrak A$.

$M_k$ can be solved in time $O(n^{2k+1})$. On the other hand, for some constant $c$, $M_{3k+c}$ is hard for $DTIME(n^k)$ (where we also require an $n^k$ bound on the contents of memory cells). I believe $c=2$ suffices. From diagonalization we obtain that $M_{3k+c}$ requires time $\Omega(n^k)$,
so $M_k$ requires time $\Omega(n^{\frac{k-c}3})$. The bound is not tight in the sense of $\Theta(n^{k'})$ for some $k'$, but at least we have $n^{\Theta(k)}$.


Studies of file access patterns in embedded systems I am considering what elements an operating system for Network On Chip systems might have and the issue of file systems looms large. NoCs have an embedded heritage, and their domain of use (at least initially) is likely to be similar tasks to embedded systems.

But I cannot find any studies of embedded system file access patterns - there are a number of published studies on scientific and super computing file access patterns I have been able to read but nothing on embedded systems.

Can anyone point me to some good papers on this?

There is a good paper titled "The Case for Efﬁcient File Access Pattern Modeling" by Thomas M. Kroeger and Darrell D. E. Long. It reviews two classic model for file access pattern "The ﬁrst model is based on a graph, that keeps frequency counts for all ﬁles accessed within a window following an access to each ﬁle. The second model was adapted from the text compression technique ﬁnite multi-order context modeling (FMOC), to track ﬁle access patterns. It uses a tree to keep frequency counts of access patterns, tracking a ﬁnite number of multiple-order patterns."

I think these techniques could be applied for different small scale file systems such as hard disk, flash memory, etc on pc or embeded systems.

This paper "Analysis of Disk Access Patterns on File Systems for Content Addressable Storage" written by Kuniyasu Suzaki, Kengo Iijima, Toshiki Yagi, and Cyrille Artho is also very useful, while the OS of many embedded systems are Linux-based.


Why we use context-free grammar for parsing? Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?

Because regular expressions are too weak and context-sensitive languages are too difficult to parse. More specifically, regular expressions can't specify that the brackets in your program match up; determining whether a string matches a context-sensitive language is PSPACE-complete (so probably takes exponential time).


Dubins TSP crossing trajectory theorem In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the Euclidean TSP (ETSP for short) however is that the visiting entity is curvature constrained by some $r$, meaning the vehicle can, at any moment in time, either go straight, or move on the edge of some circle of radius $r'\geq r$.

Consider the following theorem, by Le Ny et al. (Theorem 2 in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.982&rep=rep1&type=pdf) which we will call Theorem 1 in this post :

  A trajectory based on an ETSP optimal visit order, is not necessarily an optimal trajectory for the DTSP.

(I changed the wording of their theorem to suit this post)

Suppose the next theorem, Theorem 2 :

  There exists instances for which the optimal DTSP visit order creates a crossing ETSP trajectory.

My question is : Does Theorem 2 imply Theorem 1 ?
The idea is as follows. Since some instances have the optimal DTSP visit order creating a crossing ETSP trajectory $T$, this ETSP trajectory $T$ is not optimal (due to the triangle inequality). This in turn implies that some optimal ETSP trajectory $T*$ on these instances (or their corresponding optimal ETSP visit order) cannot be adapted and optimized to obtain the optimal DTSP trajectory. If it could, then $T = T*$, which is a contradiction, since $T$ admits a crossing trajectory.

No, theorem 2 does not imply theorem 1 unless you also prove for that instance that every optimal DTSP visit order creates a crossing ETSP trajectory.  There might be another optimal DTSP $|T'| = |T|$ visit order that does not result in a crossing ETSP so that we have $T* = T'$.


Path of exact cost k in DAG struggling with this question from an exam:

input:

  DAG G=(V,E). each edge  $e_i$ has weight $w_i\in \text{{0,1,2,3}} $

  Two vertices : s,t

  Number: k

output:

  A path from s to t with total cost k (if exists)

When you get a question about a DAG, the first thing to do is a topological sort.

Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.


What are the options of head movement for a Turing machine? I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is correct?

You are right to be confused! The problem is that different authors disagree on the definition of a Turing machine. There is actually no one "right" answer. Some authors define that the machine moves L / R; but others define that it moves L / S / R, as you have pointed out.
This is not the only thing that different definitions of a Turing machine disagree on. For example, some authors say that a Turing machine has a "halt" state, and some say that it has an "accept" and a "reject" state. Additionally, some authors say that a Turing machine's tape is "doubly infinite", meaning that it extends to infinity in both directions. But other authors say that a Turing machine's tape is "singly infinite", meaning that it only extends to infinity in one direction, and in the other direction it stops.
So what should you do about this? Well...

If you are a student or learning from a book: take a look at your textbook to see which definition they use. That definition is the "correct" one for the purposes of working through specific exercises.

If you are trying to understand the "bigger picture": then realize that it actually doesn't matter which definition you use! It turns out that all the different definitions are equivalent. So, which definition is picked is more a matter of convention, kind of like how we choose to say that $1$ is not a prime number, even though historically many mathematicians said that it was.

If you a researcher: Just pick whichever one is convenient to you or makes sense to you, and stick to it, and make sure you are consistent within your own paper or writing material to always use the same definition.

Which one is correct?

To reiterate: neither is correct; they are just different conventions. It doesn't really matter which you pick, because it turns out they are all equivalent.


Automaton-based model checking on finite traces I want to check whether a formula in finite LTL is valid on a finite, linear trace.

For infite traces I would create a Kripke structure of the trace and a Büchi automaton for the negated formula, and check if the intersection is empty.
Would this also work with a finite trace and formula in FLTL? I already tried adding another atomic proposition "alive" to the Kripke structure and automaton (like here https://spot.lrde.epita.fr/tut12.html). But how could I do it without this additional atomic proposition?

The nice thing about finite traces is that they end at some point. LTLf is now a logic in which you can only look into the future, and not in the past.

This means that you label every character in the word by which subformulas of your LTLf formula hold for a word starting from that character. You start with the last character and just apply the semantics of LTLf there. Then you do the same for the second-last character, where you can use the fact that for the last character, you already know which LTL subformulas hold.

And then you continue in this way until you hit the first letter. Once you are done with that, you know for all subformulas if they hold there. You just have to look at the whole formula as subformula and are done.


What are some of the best circuit separations that we know of and that we suspect? We know that $\mathsf{non-uniformAC^0\subsetneq PSPACE}$, $\mathsf{non-uniformACC^0\subsetneq NEXP}$. We know that $\mathsf{uniformACC^0=PH}$ is a possibility.

What are some of circuit separations that we know of?

What are some circuit separations that seem farthest apart but cannot be separated? By this question I mean that even though $\mathsf{uniformTC^0\subsetneq PH}$ is a possibility, an answer with  $\mathsf{uniformACC^0\subsetneq PH}$ suffices since $\mathsf{uniformACC^0\subsetneq uniformTC^0}$ is hypothesized.

For all uniform classes $\operatorname{UF}$, for essentially any non-uniform class $\operatorname{NU}$, one will

have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \:$, $\:$ since $\operatorname{NU}$ should be uncountable and $\operatorname{UF}$ is countable.

("Proof:" $\;\;\;$ By any reasonable definition of being uniform, for a language to be in $\operatorname{UF}$

there must be something in a particular at-most-countable set of things such that the

thing determines the language, so there are at most countably many languages in $\operatorname{UF}$.

On the other hand, for each subset $S$ of $\:\{\hspace{-0.03 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.04 in}\}\:$,$\:$ the definition of $\operatorname{NU}$ should

mean that [the language consisting of exactly the strings whose length is in $S\hspace{.02 in}$] is in $\operatorname{NU}$.

In that case, since those languages are all different, $\operatorname{UF}$ will be uncountable.

"Therefore," one will have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \;$.)

In particular, $\;\;\; \mathsf{non-uniformAC^0} \: \not\subseteq \: \operatorname{PSPACE} \;\;\;$ and

$\mathsf{non-uniformACC^0} \: \not\subseteq \: \operatorname{NEXP} \;\;\;$, $\;\;\;$ so both claims in your initial sentence are false.

It is far more interesting to ask which uniform classes

are subsets of which non-uniform classes.

$\operatorname{REG}$ $\: \not\subseteq \: \mathsf{non-uniformAC^0} \;\;\;$, $\;\;\;$ since $\;\;\;$ parity $\: \not\in \: \mathsf{non-uniformAC^0}$ $\:\:\:\:$.

$\operatorname{NEXP} \: \not\subseteq \: \mathsf{non-uniformACC^0} \;\;\;$; $\;\;\;$ which your question on cstheory was asking about.

$\operatorname{MA_{exp}}$ $\cap \hspace{.03 in}\operatorname{co-MA_{exp}}$ $\: \not\subseteq \:$ $\operatorname{P/poly}$ $\;\;\;$, $\;\;\;$ by page 16 of this paper.

$\operatorname{AM_{exp}}$ $\: \not\subseteq \:$ $\operatorname{(NP\cap coNP)/poly}$ $\;\;\;$, $\;\;\;$ by this paper. $\;\;\;\;\;$ (The right-hand-side of

the last non-containment is likely smaller than the class one would think it means.)

This paper shows that $\operatorname{MA_{exp}}$ can't be decided by circuits with "half-exponential" size.