Maximise the value of the minimum weight intra edge I've been doing review problems for a midterm and I came across this one
problem that I haven't been able to solve. The problem essentially says
that given a complete graph $G=(V,E)$ partition the vertices into
two subsets $A$ and $B$ such that weight of the smallest intra edge
(i.e. an edge $e=(u,v)$ such that $u$ and $v$ belong to the same subset)
is maximized. The graph has $n$ vertices and $k$ weighted edges.
The edges with no weight can be assumed to have infinite weight. The
required runtime is $O((n+k) \log k)$.
I thought of this in two ways:

Arrange the edge weights in increasing order and for every edge
$(u,v)$, place $u$ and $v$ in different subsets.

Arrange the edge weights in decreasing order and for every edge
$(u,v)$, place $u$ and $v$ in the same subset until all the vertices
have been placed in some subset.

The second approach doesn't work because there could be a smaller edge
among two vertices in the same subset.
Could someone please help me with this?

Let $G=\left(V, E=\binom{V}{2}\right)$ be your input graph, let $n=|V|$, and call $w(u,v)$ the weight of edge $(u,v) \in E$. Let $x^* = \max_{A, B} \min_{ (u,v) \in A^2 \cup B^2} w(u,v)$ be the value of an optimal solution to your problem (here $A \cup B = V$ and $A \cap B = \emptyset$).
Suppose that you have a guess $x$ on the value of $x^*$ and let $D_x$ be the set of all edges of weight smaller than $x$. Consider the graph $G'=(V, D)$.
If $G'$ is bipartite, then the two sides of a bipartition will give you a partition of $V$ such that every intra-edge has weight at least $x$. This shows that $x \le x^*$.
If $G_x$ is not bipartite then, for every partition $A,B$ of $V$, you have $D_x \setminus (A \times B) \neq \emptyset$. Since the same must hold for every $x' \ge x$ (since $D_{x'} \supseteq D_x$) this shows that no partition of $G$ can have a measure of at least $x$. I.e., $x > x^*$.
You can then sort the set  $W=\{w(u,v) \mid (u,v) \in E\}$ of all edge weights and
binary search for the value of $x^* \in W$.
The binary search will require at most $O(\log n)$ iterations, and each iteration requires time $O(n^2)$ to check whether $G_x$ is bipartite.
The overall running time is then $O(n^2 \log n)$.

If the edges are already sorted by their weight, or if the edge weights are polynomially bounded (w.r.t. $n$) you can improve the above time complexity by a factor of almost $\Theta(\log n)$.
Indeed, if you have already conducted a bipartiteness test on $G_x$, and $G_x$ was bipartite, and then you are asked to determine whether $G_{x'}$, with $x' > x$, is bipartite there is no need to check all edges in $D_{x'}$. Indeed, you can get away with only checking the edges in $\Delta(x, x') = D_{x'} \setminus D_{x}$.
The idea is as follows: maintain a disjoint-set (union find) data structure $U$ on the vertices of $V$, such that if $u,v \in V$ belong to the same set in $U$, then they must also belong to the same side of the bipartition of the last tested graph $G_x$.
To be more precise: $U$ will contain one set $S$ for each isolated vertex of $G_x$ and two sets $S_1, S_2$ for each connected component $C$ of $G$ with at least $2$ vertices, where $S_1, S_2$ are the unique bipartition of $G$.
It is also convenient to store,  for each set $S_i$ in $U$, the name $\eta(S_i)$ of the set corresponding to the other side of the bipartition. Namely, $\eta(S_1) = S_2$ and $\eta(S_2)=S_1$.
If $S$ is a singleton set, then $\eta(S)$ is undefined.
Initially $x=0$ (assuming w.l.o.g. that all edge weights are non-negative) so $D_0 = \emptyset$ and $U$ contains $n$ singletons.
A bipartitness check on $G_{x'}$ can be done as follows: For each edge $(u,v) \in \Delta(x, x')$ query $U$ to find the sets $S_1,S_2$ such that $u \in S_1$ and $v \in S_2$. We distinguish some cases:

Case 1: $S_1 = S_2$. In this case $G_{x'}$ cannot be bipartite since we already know that $u$ and $v$ must be on the same side of the bipartition.

Case 2: $S_1 \neq S_2$, $\eta(S_1)$ is defined, and $\eta(S_1)=S_2$. In this case $(u,v)$ connects two vertices in different sides of the bipartition of an already existing connected component. Do nothing.

Case 3: $S_1 \neq S_2$ and $\eta(S_1)$ is either undefined or $\eta(S_1) \neq S_2$. In this case we just discovered an edge across different connected components. Perform a union operation between $\eta(S_1)$ and $S_2$ and let $S'$ be the resulting set (if $\eta(S_1)$ is undefined then $S' = S_2$).
Perform a union operation between $\eta(S_2)$ and $S_1$ and let $S''$ be the resulting set (if $\eta(S_2)$ is undefined then $S'' = S_1$).
Set $\eta(S') = S''$ and $\eta(S'')=S'$. See the figure for an example.

If all edges in $\Delta(x, x')$ are processed without ever encountering case 1, then $G_{x'}$ is bipartite.
The final algorithm checks whether $G_x$ is bipartite for $x \in W$ in order, until $G_x$ becomes not bipartite. Then it returns the predecessor $y$ of $x$ in $W$. The actual partition of $V$ can be found using standard techniques (the laziest one is to find a bipartition of $G_y$ from scratch).
All the sets $\Delta(x, x')$ can be found in time $O(n^2)$ once $E$ is sorted w.r.t. $w(\cdot)$ (if $E$ is not already sorted we can use radix sort and the fact that the weights are polynomially bounded).
Moreover, the number of find operations is $O(n^2)$ and the number of union operations is $O(n)$. Thus the overall required time $O(n^2 \alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.
Notice that $\Omega(n^2)$ is a trivial lower bound for your problem.


calculating overlap of modular ranges So, this might be a really simple problem but I can't seem to find a nice algorithm to solve it:

  Given two ranges, [a1, a2], [b1, b2]  (all real numbers) and a real number n, find the length of the overlapping segment between the two ranges over a modulo of n.

For example, consider a 24-hour clock and the range [20, 4] (night time); for a given range, calculate the number of hours within that range that are night hours:

[13, 21] ==> 1 #[20,21]

[0, 6] ==> 4 #[0, 4]

[11, 19] ==> 0

I tried to think of it in terms of predefined segments
[a1,b1], [b2, a2] and do some math with them but it didn't work.
Maybe I should sort them somehow?

I will appreciate any help or direction, thanks!

Here is how I understand your problem. We have a modulus $n$. A generalized interval $[\![a,b]\!]$ consists of $[a,b]$ if $a < b$, and of $[a,n) \cup [0,b]$ if $a > b$ (assume for simplicity that $a != b$). You want to know the size of the intersection of two generalized intervals $[\![a_1,b_1]\!],[\![a_2,b_2]\!]$.

One way to solve this is to decompose each generalized interval into a disjoint union of one or two intervals, and then compute the size of the pairwise intersections (which I will let you work out yourself), and sum them up.


Optimizing neural network on small training set I'm in the process of optimizing my neural network.  I'd like to optimize on a small training set (1000 rows) as opposed to my full training set (100K rows) for speed reasons.

Will the optimal hyper-parameters (i.e. my learning rate, dropout prob, regularization parameter, # of hidden units, etc...) for my small training set also be optimal for my large training set?  In other words, which parameters can I optimize on my small training set, and which must I try to optimize on my large?

Thanks--

This is a bad idea.  For many tasks, you'll likely get poor performance.  For many machine learning tasks, having a lot of data is essential to getting good results.

Instead, I recommend you set yourself up with software and hardware that can train your network on the full training set efficiently: buy a fast GPU, use software that can use the GPU for training, use stochastic gradient descent with mini-batches and other standard techniques.

You'll likely need to optimize all of your hyper-parameters on the full training set.  I don't think optimizing the hyper-parameters on a small training set is likely to work well.  If there's any past research on similar machine learning tasks, you might look at what network architecture and hyper-parameters they used as use that as a starting point for your exploration.


Calculate maximum ammount of Bus Bandwidth Don't know if this is the right community for this and this should be pretty basic but here goes.
I'm studying System Engineering and one of the homework problems is the following question.

  A 32-bit computer with a 200-MHZ Bus requires four cycles to read a
  32-bit word. How much bus bandwidth does the CPU consume in the worst
  case ?

I just can't get my head around this for some reason.
I thought that because it's a worst case scenario the CPU would just consume 4x (cycle) the entire Bus (200MHZ) which would be 800MB/s. I even reasoned this with reversing BIT > BYTE. Byte per Clock cycle. clock Cycle * Clock rate = bandwidth.
But appereantly i'm wrong with the correct answer seemingly being 400MB/s. I can't find (in the study material atleast) how to determine this.

Anyone out there that can help me out or at least set me on the right track ?
I could drop this question but i'm afraid this will haunt me in my nightmares.

Thanks so much.

Start from the definition.  Bandwidth is defined as data transferred per unit time.  For instance, it's the number of bytes transferred, per second.

So, work out how many bytes it would be possible to transfer across the bus, in one second.  Forget formulas: just try to reason it through.  How many 32-bit words could you transfer in one second?  How many bytes does that correspond to?


What's the point of 48 bit colour? I've read that the human eye can only really decipher around 10 million different colours, so what's the point in technology that uses 48-bit colour, which allows for $2.81\times 10^{14}$ colours. Is this not like giant, super inefficient overkill?

Some reasons for using more bits per color channel:

Tetrachromats. There are rare humans with four types of cone receptors in their retinas instead of the usual three.  These people can distinguish an order of magnitude more color shades than the rest of us.
Color gamut.  Your question assumes that the 16 million colors available in 8-bit per channel RGB exactly covers the colors that normal humans can see.  But if that were so then we would only need one RGB color space.  We have more..  More bits per channel allows a wider gamut of colors to be represented without posterization, because the increased bit depth means smaller gaps between the individual shades.
Image manipulation.  Every image manipulation, from switching color models for printing, to sharpening, to resizing, to tone curve adjustment, loses information.  The more information you start with the more you have at the end of post-processing.  The more information you start with the easier it is to avoid the introduction of visible artifacts like posterization.


Throughput increase/decrease by how much percent I am learning computer architecture and organization. I am stuck in the following question. Can someone please help me?

The stage delays in a 5-stage pipeline are 300, 200, 100, 400 and 350 picoseconds. The second and third stages are merged into a single stage with delay 350 picoseconds. The throughput increase/decrease by ………… (percent).

This is what I tried:
Throughput of 1st case T1: 1/max delay =1/200
Throughput of 2nd case T2: 1/max delay= 1/350
%age increase/decrease in throughput: (T2-T1)/T1 * 100
= (1/350 - 1/200)/(1/200)*100
= -42.8
So the throughput decreases by 42.8%.
But the correct answer is given to be 0. I don't understand why?

The max delay isn't 200 and 350. In both cases, there is also a stage with a delay of 400ps, the clock speed is limited by that stage as well. The clock speed cannot be faster than 1/400ps = 2.5GHz either way, otherwise the slowest stage would break.


Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible? I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have

$$
NSPACE(S(n)) \subseteq DSPACE(S(n)^2)
$$

Am wondering, what happens if $S(n)$ is fully time-constructible instead, could we have the stronger result $NSPACE(S(n)) \subseteq DSPACE(S(n))$ ? ...

For instance, for fully time-constructible $S(n))$, we have the result :

$$
NSPACE(S(n)) \subseteq \bigcup DTIME(c^{S(n)}) \text{ for } c \geq 1
$$

However, we also have:

$$
\bigcup DTIME(c^{S(n)}) \subseteq NTIME(S(n)) \subseteq DSPACE(S(n))
$$

where the first containment follows given that for a fully time constructible $S(n)$, we have that $c^{S(n)}$ can be 'simulated' by the non-determinisitc branches of an $NTIME$ machine..

Combining the two statements above, we have:

$$
NSPACE(S(n)) \subseteq DSPACE(S(n))
$$

for fully time-constructible $S(n))$... But is this result correct or am I missing something?

Space-constructibility is a red herring. The real problem in your argument is the step
$$
\mathsf{DTIME}(c^{S(n)}) \subseteq \mathsf{NTIME}(S(n)),
$$
which is not expected to hold in general. For example, the problem of deciding whether an input Turing machine halts in time $2^n$ can be solved in deterministic exponential time, but is conjectured not to be solvable in nondeterministic polynomial time.

Furthermore, while it's not clear whether Savitch's theorem is tight, it is expected that in general $\mathsf{DSPACE}(s(n)) \neq \mathsf{NSPACE}(s(n))$. For example, it is believed that $\mathsf{L} \neq \mathsf{NL}$.


How does an operating system create entropy for random seeds? On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random bytes.

They can be read as normal files:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Many other unix variants provide /dev/random and /dev/urandom as well, without the blocking/non-blocking distinction.

The Windows equivalent is the CryptGenRandom() function.

How does the operating system generate pseudo-randomness?

The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference.

Where does randomness come from?

Random number generators (RNG) come in two types:

Pseudo-random number generators (PRNG), also called deterministic random bit generators (DRBG) or combinations thereof, are deterministic algorithms which maintain a fixed-size variable internal state and compute their output from that state.
Hardware random number generator (HRNG), also called “true” random number generators, are based on physical phenomena. “True” is a bit of a misnomer, because there are no sources of information that are known to be truly random, only sources of information that are not known to be predictable.

Some applications, such as simulations of physical phenomena, can be content with random numbers that pass statistical tests. Other applications, such as the generation of cryptographic keys, require a stronger property: unpredictability. Unpredictability is a security property, not (only) a statistical property: it means that an adversary cannot guess the output of the random number generator. (More precisely, you can measure the quality of the RNG by measuring the probability for an adversary to guess each bit of RNG output. If the probability is measurably different from 1/2, the RNG is bad.)

There are physical phenomena that produce random data with good statistical properties — for example, radioactive decay, or some astronomical observations of background noise, or stock market fluctuations. Such physical measurements need conditioning (whitening), to turn biased probability distributions into a uniform probability distribution. A physical measurement that is known to everyone isn't good for cryptography: stock market fluctuations might be good for geohashing, but you can't use them to generate secret keys.

Cryptography requires secrecy: an adversary must not be able to find out the data that went into conditioning. There are cryptographically secure pseudo-random number generators (CSPRNG): PRNG algorithms whose output is suitable for use in cryptographic applications, in addition to having good statistical properties. One of the properties that make a CSPRNG cryptographically secure is that its output does not allow an adversary to reconstruct the internal state (knowing all the bits but one produced by a CSPRNG does not help to find the missing bit). I won't go into how to make a CSPRNG because that's the easy bit — you can follow recipes given by professional cryptographers (use a standard algorithm, such as Hash_DRBG, HMAC_DRBG or CTR_DRBG from NIST SP 800-90A) or the ANSI X9.31 PRNG. The CSPRNG requires two properties of its state in order to be secure:

The state must be kept secret from the start and at all times (though exposure of the state will not reveal past outputs).
The state must be linear: the RNG must never be started twice from the same state.

Architecture of a random number generator

In practice, almost all good random number generators combine a CSPRNG with one or more entropy sources. To put it succintly, entropy is a measure of the unpredictability of a source of data. Basing a random number generator purely on a hardware RNG is difficult:

The raw physical data is likely to need conditioning anyway, to turn probabilistic data into a uniform distribution.
The output from the source of randomness must be kept secret.
Entropy sources are often slow compared with the demand.

Thus the RNG in an operating system almost always works like this:

Accumulate sufficient entropy to build an unpredictable internal state.
Run a CSPRNG, using the accumulated entropy as the seed, i.e. as the initial value of the internal state.
Optionally, periodically mix additional entropy into the internal state. (This is not strictly necessary, since entropy is not “consumed” at any measurable rate. It helps against certain threats that leak the RNG state without compromising the whole system.)

A random number generation service is part of the job of an operating system, because entropy gathering requires access to hardware, and entropy sources constitute a shared resource: the operating system must assemble them and derive output from them that will suit applications. Pseudo-random conditioning of the entropy sources is required in the operating system; it might as well be cryptographically secure, because this isn't fundamentally harder (and it is required on operating systems where applications do not trust each other; on fully cooperative systems, each application would have to run its own CSPRNG internally if the operating system didn't provide one anyway).

Most systems with persistent storage will load an RNG seed from disk (I'll use “disk” as an abbreviation for any kind of persistent storage) when they boot, and overwrite the seed with some fresh pseudo-random data generated from that seed, or if available with random data generated from that seed plus another entropy source. This way, even if entropy is not available after a reboot, the entropy from a previous session is reused.

Some care must be taken about the saved state. Remember how I said the state must be linear? If you boot twice from the same disk state, you'll get the same RNG outputs. If this is a possibility in your environment, you need another source of entropy. Take care when restoring from backups, or when cloning a virtual machine. One technique for cloning is to mix the stored entropy with some environmental data that is predictable but unique (e.g. time and MAC address); beware that if the environmental data is predictable, anyone in possession of the stored VM state can reconstruct the seed of a forked VM instance.

Entropy sources

Finding (and correctly using) entropy sources is the most challenging part of random number generation in an operating system. The available entropy sources will necessarily be dependent on the hardware and on which environment the hardware runs in.

If you're lucky, your hardware provides a peripheral which can be used as an entropy source: a hardware random number generator, either dedicated or side-purposed. For example:

thermal noise
avalanche noise from an avalanche noise
various types of (combinations of) oscillators, such as ring oscillators
radioactive decay
various quantum phenomena that I couldn't explain
acoustic noise
camera noise

NIST SP800-90B provides design guidelines for hardware RNG. Evaluating a hardware RNG is difficult. Hardware RNG are typically delicate beasts, which need to be used with care: many types require some time after boot and some time between reads in order to destabilize, they are often sensitive to environmental conditions such as the temperature, etc.

Intel x86-64 processors based on the Ivy Bridge architecture provide the RdRand instruction which provides the output from a CSPRNG seeded by thermal noise. Most smartphone processors include a hardware entropy source, though Android doesn't always use it.

Systems that lack a strong entropy source have to make do with combining weak entropy sources and hoping (ensuring would be too strong a word) that they will suffice. Random mouse movements are popular for client machines, and you might have seen the security show by certain cryptography programs that ask you to move the mouse (even though on any 21st century PC operating system the OS will have accumulated entropy without the application needing to bother).

If you want to look at an example, you can look at Linux, though beware that it isn't perfect. In particular, /dev/random blocks too often (because it blocks until enough entropy is available, with an overly conservative notion of entropy), whereas /dev/urandom is almost always good except on first boot but gives no indication when it doesn't have enough entropy. Linux has drivers for many HRNG devices, and in accumulates entropy from various devices (including input devices) and disk timings.

If you have (confidential) persistent storage, you can use it to save entropy from one boot to the next, as indicated above. The first boot is a delicate time: the system may be in a fairly predictable state at that point, especially on mass-produced devices that essentially operate out of the factory in the same way. Some embedded devices that have persistent storage are provisioned with an initial seed in the factory (produced by a RNG running on a computer in the factory). In virtualized server environments, initial entropy can be provisioned when instantiating a virtual machine from the host or from an entropy server.

Badly-seeded devices are a widespread problem in practice — a study of public RSA keys found that many servers and devices had keys that were generated with a poor RNG, most likely a good PRNG that was insufficiently seeded. As an OS designer, you cannot solve this problem on your own: it is the job of the entity in control of the deployment chain to ensure that the RNG will be properly seeded at first boot. Your task as an OS designer is to provide a proper RNG, including an interface to provide that first seed, and to ensure proper error signaling if the RNG is used before it is properly seeded.


How is clock syncing implemented? I'm looking for an explanation or reference on the implementation of computer clock. To keep the question at the level of logical abstractions: say, we put together some combinational and sequential logic from basic gates. The role of the clock (an oscillator of some sort, but that's going into more detail than needed for my abstraction) is to synchronise the unorderly chorus of inputs and outputs passing through the gates. Exactly how does the clock synchronize the signals?

To render things more concrete... Take a two-way NAND gate. Say, I set the two inputs (U1) to high signal, and obtain (after some inherent delay) a stable low signal at the other end (U2). Now, to add basic sequential logic to this inverter, let's add a Data Flip-Flop (DFF). The effect is that we can be certain that the Q end of the DFF will broadcast the low signal "definitively" at the start of the next clock cycle. What happens within the cycle is not to be trusted. The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?

The metaphor in my mind is that the clock acts as a sluice. But the comparison is misleading, in that the signal entering and exiting the DFF is not truncated at any point. We could physically measure the signal within the tick-tock cycle of the clock at the Q end of the DFF. Another high-flown metaphor would be the warm-up motions of an orchestra before the rehearsal gradually transforming into an attuned performance, with the conductor setting the beat.

How is the proper signal (attuned to the clock's oscillations) distinguished from the noise propagating through gate circuitry at all times? I realize, there may be missing parts in my picture, so that question should be framed in constructive terms:
How can one implement this basic circuit to allow the logic to distinguish between signal and noise?

Edit: Judging by responses to this question, my original question must be poorly phrased. I understand the reasons behind the choice of frequency for the system clock to ensure the circuit is stable on the tick of the clock. The responses from @Ran G. and @slebetman emphasize the "contractual" side of things. My question is really about why the contract holds. In retrospect, what I was getting at is the trivial fact that measuring instruments (system clock) must be selected based on the degree of precision required -- in a typical case discussed here, for our human sluggish attention span.

To illustrate, here's a graph of the clock pulse against data-in and Qa output for a DFF.

Say, in the 2nd clock cycle, Captain Marvel sends a pulse on the data-in line and -- oblivious to the clock period -- expects to read it off immediately (mid-phase). With his lightning speed, there's no way he can make sense of the output of this circuit because the clock cycle is geological time to him. Billy Watson, on the other hand, can read it just fine. Neither Captain M. nor Billy W. is synchronized with the system clock. Not in the sense that the gate circuitry is. But for Billy's experience of time, the clock's time scale is sufficiently precise.

I feel there are multiple questions in your post. I will attempt to answer the first -
"...The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?
Shown below is a transistor level circuit of the D flip-flop shown in the picture in your post.
If you replace your D-ff schematic with the above picture, you can see how the signal propagates from the D input to the Q output.
Your second question is
How can one implement this basic circuit to allow the logic to distinguish between signal and noise?
Logic does not distinguish signal from noise. Noise is a signal. It is an (usually) unwanted signal, but a signal all the same. It is the job of the designer to ensure that noise from various sources does not pollute the actual signal so much that it results in an incorrect reading at the Q output.
Circuits have some amount of noise immunity. Chips and cell libraries are designed such that the noise does not cross the specified noise immunity of the circuit.


Minimum cost of "signal" cover in a tree with DP I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ with $n$ being a node and $i$ being the signal strenght. The cost for each node may vary, the only assumption one can make is that $f(n, i) \geq f(n, j)$ for $i > j$.

I need to find the minimum cost to cover the whole tree.

Example:

For $f(n, i) = (i + 1)^2$, the minimum cost would be 7:

Setting a signal with strenght 0 for every node covers the whole tree for the cost of 7. Setting a signal with strenght 1 for the nodes $b$ and $c$ covers the tree for the cost of 8 and setting a signal with strenght 2 for node $a$ results in a cost of 9.

Using Dynamic Programmming this task should be achieved in $O(n^2)$. This is an assignment so I'd be grateful for tips.

Let $T$ be your tree, and root it in an arbitrary vertex $r$.
Given a vertex $v$, let $T_v$ denote the subtree of $T$ rooted at $v$.
For simplicity, let $f(0, v) = 0$.
For $i \ge 0$, define $D[v,i]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance smaller than $i$ from $v$ are always considered as covered.  Intuitively this means that the signal "coming into $T_v$" is strong enough to cover all vertices of $ T_v$ at distance at most $i-1$ from $v$.
For $i \ge 0$, define $U[v,i]$ as the minimum cost needed to cover the subtree $T_v$ rooted at $v$ with the constraint that the selected signal strengths should also be a feasible solution for the tree obtained by appending a path of $i$ vertices to $v$. Intuitively this means that the signal "outgoing from $T_v$" is strong enough to cover all vertices of $T \setminus T_v$ at distance at most $i$ from $v$.
Notice that, by definition, $D[v,i] = U[v,i]$.
If $v$ is a leaf of $T$, then
$$
D[v, i] =
\begin{cases}
f(v, 0) & \mbox{if } i=0 \\
0 & \mbox{if } i>0 \\
\end{cases},
$$
and
$$
U[v, i] = f(v, i).
$$
If $v$ is not a leaf of $T$, then let $C_v$ be the set of children of $v$.
For $i=0, \dots, n-1$:
$$
U[v, i] = \min
\begin{cases}
U[v, i+1] & \mbox{only if $i \neq n-1$}\\
f(v,i) +  \sum_{u \in C_v} D[u, i]    \\
\min_{z \in C_v} \left\{ U[z, i+1] +  \sum_{u \in C_v \setminus {z}} D[u, i] \right\}  & \mbox{only if $i \neq n-1$}
\end{cases},
$$
and, for $i=1,\dots,n$:
$$
D[v, i] =
\min
\begin{cases}
D[v, i-1] \\
\sum_{u \in C_v} D[u, i-1]
\end{cases}
$$
You can then compute all values $U[v, i]$ and $D[v,i]$ where $v$s are considered in postoder w.r.t. $T$ and the order of subproblems for a fixed vertex $v$ is $U[v,n-1], \dots, U[v,1], U[v,0] = D[v,0], D[v,1], \dots, D[v,n]$.
As far as the computational complexity is concerned notice that there are $O(n^2)$ subproblems.
The overall time needed to evaluate the second argument of the minimum of $U[v,i]$ and $D[v,i]$ is $O(n^2)$ since, for each value of $i$, computing $\sum_{u \in C_v} D[u, i]$ takes time proportional to $|C_v|$ and $\sum_v |C_v| = O(n)$.
Suppose then that all the values $\sum_{u \in C_v} D[u, i]$ are known for free (since the time needed to compute them has already been accounted for).
The overall time needed to evaluate the third argument of the minimum of $U[v,i]$ is again $O(n^2)$ since, for each value of $i$, $\sum_{u \in C_v \setminus {z}} D[u, i]$ can be found in time $O(1)$ by difference, and the inner minimum ranges over $|C_v|$ elements. Once again  $\sum_v |C_v| = O(n)$.


Given an CFG determine if $\varepsilon \in L(G)$ Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?

The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (Assuming it's not in CNF)

Is my intuition right though?

You can transform the CFG to Greibach normal form, and then simply check whether the rule $S\rightarrow \varepsilon$ exists.

In fact, you are asking whether there is a parsing algorithm for CFG.


Algorithms to play randomized game I'm interested in building an AI algorithm to play a board game.  This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural.

However, the twist here is that the game is randomized.  There is a deck of cards that is shuffled randomly; each turn involves drawing the next card from the deck, then making a move.

What algorithms are appropriate for selecting a move, in a game with randomness?

I understand that one approach is to think of this as a three-player game: in addition to the two players, there is a third player (the dealer) who makes a random move.  For instance, if the two players are Minnie and Maxwell, we might alternate moves in the following order: Dealer (chooses a random card for Minnie), Minnie (selects a move), Dealer (chooses a random card for Maxwell), Maxwell (selects a move), and so on.  I think I've read that alpha-beta search can be adapted to this setting.  However, this doesn't sound too promising to me.  There are perhaps 52 possible outcomes of the moves by Dealer, so the tree will be very bushy (with a large branching factor), causing exponential blowup.  Also, this sort of modified alpha-beta search feels a bit inefficient to me.  Each move likely affects a player's score by only a little bit at a time, so we'd expect that the effects of the randomness to average out over many moves, and there is no need to explore all combinations of possible random outcomes.  To put it another way: the game is more about positional elements and random luck than about tactical/combinatorial elements.

Is there a better algorithm framework for randomized games, that takes into account the stochastic element?  (Bonus points if you can suggest something that takes advantage of the fact the strength of a position changes only slowly over many moves.)

From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves.

The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte Carlo algorithm. This way you will be able to explore deeper the game tree and still take into consideration the randomness.


Is this a proper LL(1) Grammar? Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) parsers - mostly from papers from different colleges. They tend to use the same examples and I've never been a fan of abstracting through notation, so I'm almost positive I have the syntax incorrect.

The input is very trivial:

header>rows>h-row>a|b

main>rows>m-row>qs|d
qs>qs-row>qa|qu

footer>rows>f-row>a|b

And this is the grammar definition:

S -> aBC
B -> op
C -> a

First:

S: [a]
B: [>, |, /]
C: [a]

Follow:

S: $
C: $
B: C | S

It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for.

The three sentences:

a < a
a | a
a / a

For precision: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead of using $op$, you write:

$$\begin{align}B& \to \mathbb{<}\\
B&\to\text{|}\\
B&\to\text{/}
\end{align}$$

Alternatively, you could define $op$ as the three possible operators, as above, and leave $B\to op$.

Also: $FOLLOW$ sets (like $FIRST$ sets) are sets of terminals. So $S$ and $C$ are not going to be found in any $FOLLOW$ set. $FOLLOW(B)$ is $\{a\}$.


How does a register remember value? So I am studying this great book, and Chapter $3.1$ is about registers.

Quoting from this book / chapter:

  A register is a storage device that can "store" or "remember" a value
  over time, implementing the classical storage behaviour $out(t) = out(t-1)$.

What is mean by:

  the classical storage behaviour $out(t) = out(t-1)$ ?

If $out(2) = out(1)$ and $out(1) = out(0)$ how are we ever going to store a value?

Registers can be thought of as collections of flip-flops. These have inputs which, when activated, change the stored value. When not activated, the stored value stays the same. Look at the truth tables in the Wikipedia article.


Understanding details of NP-Hard definition I am learning from this video: https://www.youtube.com/watch?v=eHZifpgyH_4
at 21:17 he talks about his definition of NP-Hard.

The definition is: X is NP-Hard if every problem y which belongs to NP reduces to X.

I watched that part of the video several times but don't understand it. In particular, here's one thing I don't get:

P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard? That would mean that y we just converted would have an NP-Hard solution but it is actually polynomial? Sorry if this is confusing. I hope I can word it better but it to me that definition only makes sense if they talk about NP problems that are not part of P

The definition of NP-hardness for a problem $X$ is that every problem in NP reduces to $X$. Informally speaking, "$L$ reduces to $X$" means that if you could solve $X$, you could use that to solve $L$.

So, if $X$ is NP-hard, you can reduce all problems in NP, including the ones in P, to $X$. There's no contradiction here: $X$ is a hard problem, so saying that you can reduce a problem in P to $X$ is just saying, "If I could solve this hard problem, I could use that to solve a pretty easy problem." Sure, there are easier ways of solving that easy problem (that's why we call it an easy problem!) but all you've done is to show that there's a hard way to solve it, too.

  P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard?

Maybe it's just inaccurate writing but you have the implication the wrong way around. If $X$ is NP-hard, then you can reduce a problem in P to $X$. The converse (if you can reduce a problem in P to $X$, then $X$ is NP-hard) is not true.


Is Monotone 3-SAT with exactly 3 distinct variables untractable? I have given the following SAT variation:

Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated. Example:

$F= (x_1\vee x_2 \vee x_4) \wedge (\neg x_2\vee \neg x_3 \vee \neg x_4) \wedge (x_3\vee x_4 \vee x_5)$

Is this variation of SAT tractable?

My findings so far:
I suspect the problem is NP-complete and therefore not tractable. Thus I would like to perform a poly-reduction from 3-SAT to the variation described above.
An arbitrary 3-SAT formula can be converted to monotone 3-SAT.
Take following example:
$C_1=(x_1\vee x_2 \vee \neg x_3)$ and define $z_3$ by $\neg x_3 \leftrightarrow z_3$ and  $x_3 \leftrightarrow \neg z_3$ which is equivalent to $(x_3\vee z_3)\wedge(\neg x_3 \vee \neg z_3)$.
From that we get the monotone form of $C_1$ by
$(x_1\vee x_2 \vee \neg x_3) \leftrightarrow (x_1\vee x_2 \vee  z_3)\wedge (x_3\vee z_3)\wedge(\neg x_3 \vee \neg z_3)$
By applying this transformation to all clauses I get a monotone 3-SAT formula which is equally satisfiable.
My reduction produces additional 2 clauses with 2 literals for each non-monotone clause, but how do I get only monotone clauses with exactly 3 distinct literals?

I will try to answer now my own question and would be glad about some feed back concerning the corectness.
Like in the question above discussed and pointed out by Kyle Jones we can reduce arbitrary 3-SAT formulas to monotone 3-SAT formulas.
For example a clause $C=(x_1\vee x_2 \vee \neg x_3)$ can be converted to $C'(x_1\vee x_2 \vee z_3)\wedge (z_3 \vee x_3) \wedge (\neg z_3 \vee \neg x_3)$. One can check if $C$ is satisfiable $C'$ is also satisfiable and if  $C$ is not satisfiable $C'$ is also not satisfiable.
The next step is to convert all the clauses with less than 3 literals to clauses with exactly 3 distinct literals.
Therefore take for example $C_1=(x_1 \vee x_2)$ and transform it to $C_1'=(x_1 \vee x_2 \vee y_1)\wedge (x_1 \vee x_2 \vee y_2) \wedge (x_1 \vee x_2 \vee y_3) \wedge (\neg y_1 \vee \neg y_2 \vee \neg y_3)$ then again if $C_1$ is satisfiable $C_1'$ is also satisfiable and if  $C_1$ is not satisfiable $C_1'$ is also not satisfiable.
The same can be done for the negative case i.e. $C_2=(\neg x_1 \vee \neg x_2)$ can be transformed to $C_2'=(\neg x_1 \vee \neg x_2 \vee \neg u_1)\wedge (\neg x_1 \vee \neg x_2 \vee \neg u_2) \wedge (\neg x_1 \vee \neg x_2 \vee \neg u_3) \wedge ( u_1 \vee u_2 \vee u_3)$
By applying the two transformations one can convert an arbitrary 3-SAT instance to a monotone 3-SAT instance with exactly 3 distinct literals. As can be seen easily above the transformations have polynomial complexity. Therefore since 3-SAT is NP-hard the reduction aswell must be NP-hard.


Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas I recently asked a similar question, however, I'd like to address it in a more mathematically precise setting.
In that paper, on page 5, it talks about a rigorous definition of what it means to $\epsilon$-refute random 3CNF formulas. For that, I will provide a screenshot of the exact part I want to address:

The problem of refuting random 3CNF concerns efficient algorithms that provide a proof that a random 3CNF is not satisfiable, or far from being satisfiable. This can be thought of as a game between an adversary and an algorithm. The adversary should produce a 3CNF formula. It can either produce a satisfiable formula, or produce a formula uniformly at random. The algorithm should identify whether the produced formula is random or satisfiable.
Formally, let $\Delta\colon \mathbb N \to \mathbb N$ and $0 \leq \epsilon < \frac14$. We say that an efficient algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if its inputs is $\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$, its output is either "typical" or "exceptional", and it satisfies:

Soundness: If $\operatorname{Val}(\phi) \ge 1-\epsilon$ then $$ \Pr_{\text{Rand. coins of $A$}}(A(\phi)=\text{"exceptional"}) \geq \frac34.$$

Completeness: For every $n$, $$ \Pr_{\substack{\text{Rand. coins of $A$}\\ \phi \sim \operatorname{Uni}(\mathrm{3CNF}_{n,n\Delta(n)})}}(A(\phi)=\text{"typical"}) \geq 1 - o(1). $$
By a standard repetition argument, the probability of $\frac34$ can be amplified to $1-2^{-n}$, while efficiency is preserved. Thus, given such an (amplified) algorithm, if $A(\phi)=\text{"typical"}$, then with confidence of $1-2^{-n}$ we know that $\operatorname{Val}(\phi) < 1-\epsilon$. Since for random $\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$, $A(\phi)=\text{"typical"}$ with probability $1-o(1)$, such an algorithm provides, for most 3CNF formulas, a proof that their value is less than $1-\epsilon$.

The exact part I want to address is the properties soundness and completeness of the algorithms.
First, what does it mean that the output is "typical" or "exceptional"? I don't think the authors define that precisely. I am guessing from context, if the algorithm returns exceptional then it found a boolean formula that is unsatisfiable? Though I am just guessing from the definition of the word refute.
From the definition of $\operatorname{Val}(\phi)$ (=the fraction of clauses that are satisfiable, so its 1 when the whole thing is satisfiable) I am assuming that if the algorithm is sound then if it returns an answer, then the answer must be correct (i.e. the formula must be unsatisfiable). However, from the definitions given, it seems that if the formula is nearly satisfiable, then it says with high probability (greater than 3/4) that its "exceptional" (whatever that means)?
For completeness, what that usually means for me is that, if there is a correct answer, then the algorithm will return it. In this case, if we give it a boolean formula, if it's unsatisfiable, then it will say so. Thats what completeness usually means for me. In this case, the conditions given in the paper for completeness are hard for me to understand.
I think maybe the main source of confusion might be what the word "exceptional" and "typical" mean. My intuition says that most boolean formulas are unsatisfiable, so in fact, "exceptional" should mean satisfiable and "typical" means unsatisfiable? Which is kind of opposite of what a refuting algorithm would do in my head.
Anyway, anyone have any ideas of how to resolve this in a mathematically precise way?

The words "exceptional" and "typical" have absolutely no formal meaning. Let's rephrase the definition using two other words, "Clinton" and "Bush".

We say that a (possibly randomized) algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if:

Given a 3CNF formula $\varphi$ with $n$ variables and $\Delta n$ clauses such that a $1-\epsilon$ fraction of the clauses (at least) is satisfiable, the probability that $A(\varphi)$ outputs "Clinton" is at least 75%.
With high probability, $A(\varphi)$ outputs "Bush" given a random 3CNF formula with $n$ variables and $\Delta n$ clauses.

What does the algorithm $A$ try to do? It tries to identify "Clinton" inputs, which are inputs that are at least $1-\epsilon$ satisfiable. At the same time, on a random input, which is with high probability not "Clinton", it should return "Bush". So it tries to separate the rare "Clinton" inputs from a random input.


Why not a $coNP$ hierarchy? In the polynomial hierarchy we have $\Sigma_2=NP^{NP}$ and $\Pi_2=co\Sigma_2$.

So we have $\Pi_2=co(NP^{NP})$.

Is it same as $(coNP)^{NP}$?

I just wonder why not a hierarchy with $coNP$.

By definition, for any oracle for a language $A$, $(coNP)^{A}=\{L \mid \overline{L} \in NP^{A}\}$. Using this definition and definition of co-class we have

$$L \in co(NP^{NP})\iff \overline{L}\in NP^{NP} \iff L \in (coNP)^{NP}$$

You can also use $coNP$ instead of $NP$ as oracle (as Yuval commented), since if we can decide $x \in L$ using an oracle for a language $A$ we can decide $x \in L$ using another oracle for $\overline{A}$ as well, because $x \in A \iff x \notin \overline{A}$.


Max sum cyclic path of fixed length in matrix Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves are up, down, left, right and each position can be visited multiple times but only contributes to your sum once.

Example: for K = 8

7 3 5 9
1 2 0 4
9 4 2 7
7 6 3 2

Optimal route (I think): 0 2 4 9 7 6 3 2 0

First off, of course K has to even (or the problem should state of length at most K). Secondly I was thinking of a solution along the lines of:

opt[i][j][t] = the maximum sum that can be obtained at position (i,j) at time t

The problem with this is that you can't be sure where you can come from. There is no way to (efficiently) know what values you can use to calculate opt[i][j][t]. I could keep the actual path for each position but that would be $O(nmk^2)$ memory, which is essentially $O(n^6)$ - which is extremely unfeasible. Even the solution itself which is $O(nmk) = O(n^4)$ is probably a little too slow. And, in fact, if I have to check each path that would make the complexity as bad as the memory necessary.

Does anyone have any ideas? I would appreciate hints to try to figure it out myself, not actual solutions. Thanks!

problem with this is that you can't be sure [which path] you can come from.

Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $t$ up to $K$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $O(t^2)$ memory to remember the cells we should avoid.

Naively one could access a dense matrix opt by dereferencing opt[i][j]. To access the $n$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if edit[(i, j, n)] exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $n$th variant as a list of (i, j, value) tuples.

Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $\frac{K}{2}$ and each new matrix gives rise to another $\frac{K}{2}$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.

Consider the Manhattan distance between current cell and origin. A decent heuristic for 1st stage search would be to make that distance strictly increasing on the outbound path, then strictly decreasing on the inbound path, which reduces the search space a little. Your idea about storing optimal values is a good one for further pruning the search space.

Please do keep us posted on your progress, especially on any pruning techniques that seem promising.


Are all language over $\Sigma= \{0\}$ decidable? I have problem in determine whether it is decidable or not, can somebody help me please

A language over $\{0\}$ is any subset of the set S of all strings consisting of a finite number of 0s. S is countable, the set of all subsets of S is uncountable.

Any decidable language must be decided by some algorithm. The set of algorithms, no matter how you describe it, is countable, not uncountable. Therefore some subsets of S (actually almost all) are not decidable.


TQBF as interactive game My teacher describes true quantified boolean formula (TQBF) as an interactive game between two players $\exists$ and $\forall$, and asks us to show a winning strategy for the existential player $\exists$. Can someone describe what this game is? I feel like this is background knowledge I am missing.

Hint:  Imagine the formula in some (prenex) normal form and consider the order of quantifiers: $\exists x_1 \forall x_2 \exists x_3 \exists x_4 \dots Q x_t \phi(\overline{x})$.  Let the player corresponding to the first quantifier choose its valuation (true or false) and then continue the game with that variable $x \mapsto v$ where $v$ is the value chosen for $x$, and with the first quantifier removed from the formula, i.e., in the example, if $\exists$ chooses true, let $x_1 \mapsto \mathtt{true}$ and continue the game on $\forall x_2 \exists x_3 \exists x_4 \dots Q x_t \phi(\overline{x'})$.

Let $\exists$ be the winner (as usual) if and only if the end result is a quantifier-free true formula.


Is there a heuristic or function to determine if two arrays of integers are alike or similar What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], b = [0, 2, 1, 3, 4], and c = [1, 4, 2, 0, 3].  Is there a function to determine that a is closer to b than c is?

So the function I am looking for I think should be similar to SHA, but without the avalanche effect. The examples I give is using arrays of integers, but obviously this should also work on any arbitrary stream of data.

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures:

First, I consider distances most commonly associated with strings:

Edit distance: Here, we count minimum the number of 'edit operations' required to transform string $A$ into string $B$. These edit operations are usually inserting, deleting or substituting a single character in your string or array. Usually, the different operations have different costs. The Levenshtein distance is a special case of the edit distance that is commonly used to compare words.
Hamming distance: This distance simply counts the number of indices between two sequences that differ, which is the same method you described in your comment. This can at times be a decent metric, but it often doesn't come close to an our intuitive notion of 'similarity'.

There are many more string metrics, but those above are the most commonly known.

Next, you could also consider metrics over time series: here the sequences are interpreted as measurements at increasing time-steps. Usually, we assume there is some distance measure over the individual elements of your sequences, this can be taken as simply $d(x,y) = \begin{cases} 0 & \text{if $x=y$}\\ 1 & \text{if $x\neq y$}\end{cases}$, if you don't have a more reasonable notion of distance between your characters.

Dynamic Time Warping (DTW): This distance finds a suitable 'alignment' between the pair of sequence that minimizes the sum of the distances between the alignment. An advantage of this method is that this measure is insensitive to 'time shifts': The sequences $A=\langle 1, 2,3,4,5 \rangle$ and $B=\langle 0 ,1, 2,3,4\rangle$ have maximum Hamming distance, but a low DTW distance, as DTW is allowed to match the element $A[1]$ to $B[2]$, $A[2]$ to $B[3]$ and so on. Computing the DTW between two sequences takes $O(n^2)$ time (if both sequences have length $n$), but there are many faster approximations and heuristic speed-ups.
Longest Common Subsequence (LCS): This isn't always used as a similarity measure, but the length of a LCS between two sequences $A$ and $B$ can be seen as inversely proportional to the distance between $A$ and $B$ (i.e. long common subsequences mean high similarity). A disadvantage of this measure is that it often ignores too much of the relevant structure of the sequences, but it sometimes works fine.

Other similarity measures for time series can be found here.


shortest path tree algorithm Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$.

I want to find an algorithm for the shortest path tree rooted in $s$ with time complexity of $O(V+E)$.

We may assume that all vertices are reachable from $s$.

I thought of running something like BFS traversal on $G$ and for each vertex $u$ I examine, for each neighbor $v$ of him, I'll check that $\delta(u)+w(u,v)=\delta(v)$ and if so, I'll add $(u,v)$ to the output SPT.

Is that sounds right? or has any pitfalls I haven't thought about?
If so, how would you prove that? by induction?

Use a proof by induction on the length of the paths.  In other words, prove first that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 1; then that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 2; and so on.


any one can prove following inequality? are for every $\alpha \in N $   ,      $   \frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?

That inequality is not defined for $\alpha = 0, 1, 2$. For $\alpha > 2$ you have:
$$
\frac{1}{\alpha-2}  - \frac{1}{\alpha-1} -  \frac{1}{\alpha} =
\frac{\alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2)}{\alpha(\alpha-1)(\alpha-2)}
$$
Clearly the denominator is always positive. Regarding the numerator:
$$
\alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2) =
\alpha(\alpha-1-\alpha+2) - (\alpha-1)(\alpha-2) =\\
\alpha - (\alpha-1)(\alpha-2) =
\alpha - \alpha^2 + 2\alpha  + \alpha  -2=
-\alpha^2 + 4\alpha - 2,
$$
which is negative as soon as $\alpha \ge 4$. In fact, your inequality is only true for $\alpha=3$.


Restricting possible permutations in Graph Isomorphism problem Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.

Call two such graphs $2n$ vertex labelled graphs $G$, $H$ whose adjacencies are $A$ and $B$ respectively $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ iff there is a permutation $P$ such that $A=PBP'$ on the condition that the permutation $P$ permutes only supervertices (only a subset $n!$ of permutations of $(2n)!$ allowed).  In particular, the permutation must map even-numbered vertices in $G$ to even-number vertices in $H$; and if vertex $2i$ in $G$ is mapped to vertex $2j$ in $H$ by the permutation, then vertex $2i-1$ in $G$ must be mapped to $2j-1$ in $H$.

Is $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ $\mathsf{GI}$-$\mathsf{complete}$?

It's GI-complete.  Here's a simple reduction.  Let $G_0,H_0$ be any two connected, undirected graphs on $n$ vertices.  Consider the vertices of $G_0$ as even-numbered vertices of $G$, and add $n$ odd-numbered vertices that aren't connected to anything. Construct $H$ from $H_0$ similarly.  Now $G$ is vertex-pair-isomorphic to $H$ if and only if $G_0$ is isomorphic to $H$, so solving vertex-pair-isomorphism is at least as hard as solving graph isomorphism.


Difference Between Small and Big-step Operational Semantics What's the fundamental difference(s) between small and big-step operational semantics?

I'm having a hard time grasping what it is and the motivation for having the two.

Small-step semantics defines a method to evaluate expressions one computation step at a time. Formally speaking, a small-step semantics for an expression language $E$ is a relation $\rightarrow : E \times E$ called the reduction relation. Small-step semantics describes what happens to an expression in detail. It's able to give a precise account of even non-terminating programs, with an infinite chain $e_0 \to e_1 \to e_2 \to \dots$. A terminating program is one such that $e_0 \to e_1 \to \dots \to v$ terminates with a value $v$ such that $\forall e' \in E, v \not\rightarrow e'$.

$\newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]}$

At the other end of the spectrum is denotational semantics. Denotational semantics assigns a “meaning” to each expression. It is a function from expressions to denotations: $\llbracket \cdot \rrbracket : E \to D$ ($D$ is called the domain). The space of denotations can be completely unrelated to the syntactic space, for example $E$ could be expressions that evaluated to a number and $D$ could be a set of numbers like $\mathbb{N}$ or $\mathbb{R}$.

Big-step semantics are kind of in the middle. A big-step semantics on an expression language $E$ and a set of values $V$ is a relation $\Downarrow : E \times V$. It relates an expression to its value (possibly multiple values if the language is non-deterministic). Often, a special value $\bot$ is used for non-terminating expressions.

So why do we have these three notions? All of these notions can model each other, but the model adds a degree of complexity.

Given a small-step semantics $\to$, you can define a corresponding big-step semantics that relates each expression to its value (or values, if the reduction is non-deterministic): $e \Downarrow v$ iff there exists a chain $e \to e_1 \to \dots \to v$ and $v$ cannot reduce any further. Note that in general you cannot reconstruct the small-step semantics from the big-step semantics. For example, all non-terminating expressions are indistinguishable under the big-step semantics.
Given a big-step semantics $\Downarrow : E \times V$, you can say that it's a small-step semantics on $E \cup V$. This is not particularly useful.
Given a small-step semantics $\to$, you can define a corresponding denotational semantics where the denotation of an expression is the set of reduction chains starting from it. This satisfies the formal definition, but it isn't particularly useful, because it adds a set theoretic overhead to objects which are easier to reason about by looking directly at the syntax.
Given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a small-step semantics by adding all possible denotations as values in the language. That requires creating values that are not part of the syntax that the programmer can write, which means that some interesting results have to state “for all programs that the programmer can write” rather than “for all programs”. This one is thus not very useful either.
Given a big-step semantics $\Downarrow$, you can define a corresponding denotational semantics where the domain is the set of sets of values: $\llbracket e \rrbracket = \{v \mid e \Downarrow v\}$. If the big-step semantics is deterministic (each expression reduces to a single value), you can define a simpler denotational semantics where the domain is the set of values.
Conversely, given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a big-step semantics $E \Downarrow \llbracket \cdot \rrbracket$. Again this one is a little pointless.

Operationally speaking, small-step semantics corresponds to looking at each operation performed by an interpreter for the language. Big-step semantics only looks at the resulting value. Denotational semantics looks at a mathematical interpretation which may or may not have anything to do with what happens on a computer.

Small-step semantics is the most obvious one. It clearly provides useful information about non-terminating programs. More generally, it provides detailed information about the behavior of the program.

Denotational semantics transforms syntactic constructs into arbitrary mathematical objects; it can express whatever the scientists wants (you can define the denotation of an expression to be all possible reduction chains from it), but at the cost of adding a level of complexity. It's used when we do want to abstract away some details such as exactly how the expression is evaluated.

Big-step semantics is in the middle: it abstracts away the details of the evaluation but retains the syntactic nature of the result. Usually the concept is used when there is an underlying small-step semantics, as a way to express concisely “$\exists (e_1, \dots, e_n), e \to e_1 \to \dots e_n \text{ and } \not\exists e', e_n \to e'$” as “$e \Downarrow e_n$”. In such constructions, while the concepts are very different (one allows us to talk about individual computation steps and about non-terminating programs, the other doesn't), the definitions will look very similar, because in this case the rules that define the big-step semantics are basically of the form “if $e_1 \to^* e_2$ and … and $e_n \to^* v$ and $v$ is a value then $e_1 \Downarrow v$”.


Is L={0,1}* without strings that start with 00 decidable? Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable?  I'm drawing a blank on this one.

so turns out its decidable because its the regular expression $L = 01(0|1)$*


Simulating Turing Machine with writing only on non-input fields on read-only Turing machine Can you show me how to simulate Turing Machine with writing only on non-input fields on read-only Turing machine ?

I tried to do it be using internal states, but it provides me to infinitely many states, what is not allowed.
Any ideas ?

Edit
I consider standard Turing machines - one leftly-infinite tape.
read-only Turing machine is for me Turing machine such that it can't write on tape.
non-input fields - I mean part of tape where input is given. For example,
abcd#####...., machine can't overwrite abcd but it can overwrite each #.  However, readonly can  only read this tape, so no changes.

Edit II
I am searching for solution in which we use functions and Myhill-Nerode theorem. Can anyone provide this kind of solution ?

By Single-tape Turing Machines with write-protected input recognize only Regular Languages, a Turing machine that writes only on non-input fields accepts a regular language.

Any regular language can be accepted by a read-only Turing machine: just form a DFA for the regular language, then use that as the finite-state control of the Turing machine and scan the input from left to right.

Chaining those two facts together gives a full proof of the statement.


Topological sorting and NP-hard proof I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness.

The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,x_n\}$, a partial order $<$, where $x_i <x_j$ means that $x_i$ must be in front of $x_j$, and a new item $x_k$ as well as related statements $x_k<x_i$ for some $i$'s and $x_j<x_k$ for some $j$'s to be added to the partial order, how to find the least replacement solution to insert $x_k$ into the original sequence $X$ without violating the resulting partial order?

It can be ensured that the partial order forms no cycle such as $x_i<\cdots<x_j<\cdots <x_i$.

I guess this optimality depends on how you define "the least replacement solution". I'm taking it to mean minimum insertions / deletions. If you prefer minimum number of swaps necessary, take a look at step 4.1 and 4.2 and you may be able to optimize it for such, though I don't show it here.

If it is ensured that no additional $x_k$ and its partial constraints will cause a cycle, then this becomes relatively easy. Consider a topological ordering $\{x_1, x_2, \ldots, x_i, \ldots, x_j, \ldots\}$ where $x_i$ and $x_j$ have no transitive relation. We now have five options for additional constraints to be added:

$x_k$ with no constraints: put $x_k$ anywhere in the ordering.
$x_k > x_i$: put $x_k$ anywhere after $x_i$ in the ordering.
$x_k < x_j$: put $x_k$ anywhere before $x_i$ in the ordering.
$x_i < x_k < x_j$: put $x_k$ anywhere in between $x_i$ and $x_j$ in the ordering.
$x_j < x_k < x_i$: this is the only case where we will need to rearrange existing nodes because $x_i$ and $x_j$ are out of order currently.

For case 5 we will first worry about the fact that we are transitively adding an edge $x_j < x_i$, then after re-ordering, this will resolve to case 4. Do the following:

Let $A_i$ be all elements reachable ("after") in the DFS starting at $x_i$ of the current partial ordering.
Let $B_j$ be all elements on any path from the root to $x_j$. This can be computed in linear time by doing a DFS on the reverse partial ordering, starting at $x_j$.
Note that if $x_j \in A_i$ then this violates our original assumption. If $x_i \in B_j$, this also violates our original assumption. So we know $x_j \not\in A_i$ and $x_i \not\in B_j$.
Greedily move all elements in $B_j$ before all elements in $A_i$. This can be done by doing one of the following which has minimum insertions:

Move all elements in $B_j$ that are after $x_i$ in the ordering, before $x_i$.
Move all elements in $A_i$ that are before $x_j$ in the ordering, after $x_j$.

You can show that the minimum of these two will be a lower bound for the number of insertions / moves necessary.

After you have separated $B_j$ into the first half of the order and $A_i$ into the second half, this case reduces to case 4 as described above. Overall this will take $O(n + m)$.


Can the sorting of a list be verified without comparing neighbors? A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $e_i$, I have a set of pairs of indices $(j,k)$ for which I know whether $e_j > e_k$, $e_j = e_k$, or $e_j < e_k$. There exists a pair $(l,l+1)$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases:
$$
1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\
1,2,\ldots,i-1,i+1,i,i+2,\ldots,n
$$


Time Complexity: Big-O What is the time complexity of this loop?

k=1
for(j=0;j<=n;j+=k)
    k++;

Is it $O(n)$ as we are increasing $j$ linearly?

Here are the values of $j$ at the end of each iteration:
$$
1,3,6,10,15,21,28,36,45,55,\ldots
$$
More generally, after $t$ iterations, $j = 1 + \cdots + t = \binom{t+1}{2} = \Theta(t^2)$. Therefore the loop halts after $\Theta(\sqrt{n})$ iterations.


Why is English not a regular language? Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., with states going to a looping non-final state whenever there are no possible words to be made beginning with the letters you have already gone through. Then make every state that ends on a word final.

The English language is regular if you consider it as a set of single words. However, English is more than a set of words in a dictionary. English grammar is the non-regular part. Given a paragraph, there is no DFA deciding whether it is a well-written paragraph in the English language. Of course, it can say whether each word is an English word or not, but it can not judge whole paragraphs.


What is the correct FSA representation of the following string sequence? Based on this article, i am trying to imagine how i would construct an FSA based index for the following string sequence:

ABCDEF
ABDDDF
ABDDEFGHI

These are the representations that i found:

There are problems with each:

The first introduces a new key in the automata that really isn't in the set (ABCDEFGHI)

The second one is the closest to my heart but it is more trie-like, so it can be inefficient at a large scale.

The third saves a lot of final states therefore saves some space. However, state 9 has multiple "F" transitions which i think is illegal.

So the big question is: Which one of the above is correct? If none of them, please share what is the correct!

Thank you

I think none of your finite automata accepts the third string ABDDEFGHI.The following is what I think a correct finite automaton for accepting all three strings

In case where your language has the third string ABDDDFGHI.The first is wrong since it accepts another string.The third also seems incorrect since there are multiple labels of same letter exiting from one node.Your second automaton is correct but you may want something like this


Probabilistic Substring Match I'm looking for an algorithm that will help me determine substring matches at scale.

I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage is cheap.

On detection side, I have both a very large pool (hundreds of TB) of strings to search for needles in, and also want to be able to stream detection as text comes in. So it's important that the detection be very fast (algorithmically). I can also pre-process this text as part of the detection, obviously.

I can store a copy of all needles, so a probabilistic algorithm would be fine (say, instead of the correct N strings, the algorithm returns some false positives -- I can always do a plain string search afterwards).

There is significant structure to the strings (they happen to be source code -- snippets on the needle side and files in the haystack).

Appreciate any thoughts on where to explore.

Rabin-Karp

Rabin-Karp string search would be a good candidate, because it can use a rolling hash function.

You pick a segment length $\ell$.  For each "needle", you hash its first $\ell$ characters, and store it in a hashtable keyed on the hash.

Then, as each character of text arrives, you compute the rolling hash of the last $\ell$ characters, look it up in the hash table, and possibly find one or more candidate needles that might match; then you test them directly.

This requires that the segment length be shorter than the shortest needle, but long enough to make hash collisions rare (i.e., so that the first $\ell$ characters of a needle mostly uniquely determines the needle).  If you have a wide range of needle lengths, I suppose you could pick two segment lengths $\ell_1,\ell_2$, have two hash tables, and store each needle in appropriate hashtable according to its length.

Aho-Corasick

The Aho-Corasick algorithm would also be a good candidate.  It solves exactly this problem, and doesn't require any assumptions on the lengths of the needles.

You might also look at Commentz-Walter.


Are these two sensible and related or unrelated ways of regarding a logic system as a programming language? When I am trying to understand logic programming languages e.g. Prolog, I am immediately confused by the following two ways of relating logic systems and programming languages or type systems.

In Types and Programming Languages by Pierce, Section 9.4
Curry–Howard correspondence on p109  has a table

Does it mean that a logic system is a programming language, where

types are propositions and
values of a type are proofs of the proposition?

On the other hand, a logic system is described in a formal language
that defines what a logic expression is. Can we view a logic system
(e.g. the first order predicate logic system) as a programming
language, where

it has two types: Boolean type and function type, and
Each logic expression without a variable has Boolean type, so can be evaluated to a truth value.  Each logic expression with any
variable has Boolean function type, so its application to truth
values for its variables can be evaluated to a truth value?

Are the above two views of a logic system as a programming language completely unrelated/orthogonal, or are they the same or can they be unified?

Thanks.

Does it mean that a logic system is a programming language, where types are propositions and values of a type are proofs of the proposition?

Not necessarily, being both (logic systems and programming language) formal languages, there certainly is a certain degree of isomorphism between the two concepts, this translates into the fact that we can encode a logical system through a programming language and develop algorithms to identify proofs of the theorems of our logical system.

If you are interested in the similarities between logical propositions and types, I strongly suggest you take a look at Homotopy type theory.


Is page size always equal to frame size? I'm learning about paging. My book says that the logical addresses generated by the CPU are in the form |p|d|(page number, page offset) and the physical addresses are in the form |f|d|(frame number, frame offset). It is also specifically mentioned that d i.e. the offset is copied directly to generate the physical address from the logical ones.

Now, commonsense says that if the offset is copied directly, the page size HAS to be equal to the frame size (otherwise, offsets wouldn't correspond). But unfortunately my book doesn't say anything about that.

So, is page size always equal to frame size?

A page is a region of virtual address space, and a page frame is a region of physical memory. A page which maps a region of physical memory must have the same size as that piece of physical memory, otherwise there's no point.

They also typically must be aligned correctly. If you try to map, say, a 2Mb page frame into virtual memory, both the virtual address and physical address must both be 2Mb aligned.

Many modern CPUs support more than one page size, and some can support different page sizes in the same address space. Current Intel x86-64, for example, supports 4kb, 2Mb and 1Gb page sizes. These numbers are not arbitrary; they represent the address space covered by different "levels" in the multilevel page table. Similarly, modern ARM supports 4kb, 64kb, and 1Mb pages, though ARM does not refer to the 1Mb pages as "pages" (they are "sections"). ARMv4 and ARMv5 supported splitting pages further into so-called "subpages"; these are no longer available in ARMv7.

Interestingly, there are a few other things that are often the same size as the page size. Obviously a TLB entry is the same size as a page or frame, since it's conceptually a cache for page table entries. However, L1 cache size is often determined by the page size, too.

Suppose the L1 cache is set-associative (a direct-mapped cache is really just a 1-way set associative cache, so you can think of this as a limiting case), then it's often convenient to make one "set" the size of a physical page. So suppose that the page size is 4kb, and the L1 cache is a 4-way set-associative cache, then the "best" size for the L1 cache is 16kb (which is four times 4kb). See if you can work out for yourself this might be the case.


Sum duplicates in array problem I get $n$ numbers, where every number is an integer between 1 and 1000. If within given numbers are duplicates, I sum all of them to one number. I repeat it until I have only distinct elements. As a result I return number of distinct elements at the end.
How do I do it in additional space complexity $O(1)$ and time complexity $O(n)$.
I know how to do it in space complexity $O(k)$ and time complexity $O(n+k\log k)$, where $k$ is number of distinct numbers.

Create an array $A$ of 1000 elements, indexed from $1$.
Store in $A[i]$ the number of input elements equal to $i$. This can be done in linear time by scanning the input elements once.
Create a list $L$ which will contain at most $1000$ elements (and can hence be implemented using a fixed-size array).
Each element of $L$ is a pair $(m_x, x)$ where $x$ is a number and $m_x > 0$ is the number of its occurrences. Initialize $L$ from $A[i]$ as follows: for each $i$ with $A[i]>0$ append to $L$ the pair $(A[i], i)$ (this can be done in constant time since $A$ contains only $1000$ elements).
From now on the algorithm is trivial, as it is just a simulation of the rules in your question.
Repat:

Search $L$ for the element $(m_x, x)$ with $m_x > 1$ that minimizes $x$.
If such an element does not exist, return the length of $L$.
Otherwise:

Delete $(m_x, x)$ from $L$.
If $L$ contains an element $(m_y, y)$ where $ y = x m_x$ increment $m_y$ by $1$; Otherwise add $(1, x m_x)$ to $L$.

An iteration can be carried out in constant time since all list operations take constant time as well ($L$ always has at most $1000$ elements).
Consider now the quantity $\eta$ defined as the number of elements in $L$ plus the number of elements in $L$ with multiplicity greater than $1$.
Initially $\eta$ is at most $2000$.
In all but the last iteration one of the following two things happens:

An element with $(m_x, x)$ with $m_x > 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and some $m_y$ is incremented (causing $\eta$ to increase by at most $1$).
An element with $(m_x, x)$ with $m_x > 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and a new element $(1, x m_x)$ is added to $L$ (causing $\eta$ to increase by $1$).

In any case, each but the last iteration decreases the value of $\eta$ by at least $1$. Since the final value of $\eta$ must be positive, it follows that the total number of iterations is at most $2000 - 1 + 1 = 2000 = O(1)$.
Finally, observe that above procedure only uses constant amount of memory and that any $O(n)$ time and $O(1)$ space algorithm is also a $O(n + k \log k)$ time and $O(k)$ space algorithm, thus also answering your second question.


Show that there are infinitely more problems than we will ever be able to compute I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot follow his reasoning, in practice what he says is this:
we can state a decision problem as string of $0$ and $1$ which in practice is the truth table of the function.
He goes on to say that a decision problem is an infinite string of bits while a program is a finite string of bits and up to here no problem. What I don't understand is the continuation of the proof from this point on: Decision problems are in $\mathbb{R}$ cause you can put a decimal point before the string representing the problem, thus obtaining the decimal part of a real

 for example if you have 0111011010101010101... it could become x.0111011010101010101...

A program is "just" an integer in $\mathbb{N}$ cause it is a finite string of bits. The point that I fail to understand is how it is possible that a decision problem is comparable to a real number instead of an integer ... I mean, if we use the argument of "put a dot in front of the number" could not the same reasoning also be applied to the number of possible algorithms that can ever be produced?

Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ordering of strings, any decision problem $P$ can be (uniquely) encoded as an infinite string of bits, where the $i$-th bit represents whether the $i$-th string is in $P$ or not, and any infinite string of bits (uniquely) encodes a decision problem (in the same fashion); hence, $\mathbb{R}$ and the set of decision problems are both uncountable sets.


Removing vertices from a labelled graph Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?

For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.

The problem is $NP$-complete by reduction from $3$-SAT. In the reduction, the goal will be to have at least one vertex of each labeled class left.

For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this gadget, which is not connected to anything else but allows us to conserve one vertex of the opposite color class.

For every clause with $3$ literals, we create a clique on $3$ vertices (corresponding to the $3$ literals), each with unique colors. We must delete all but one of the vertices from this gadget, and the vertex which is not deleted signifies which literal causes the clause to be satisfied. We create two further copies of this gadget, which are not connected to anything else but (similarly to the variable gadgets) allow us to conserve vertices of the unused color classes.

We now connect every vertex whose preservation denotes making a true (resp. false) assignment to a variable to the literals which are incompatible with that assignment.

For a clause with $2$ literals we do the same, except with $2$ (instead of $3$) cliques on $2$ (instead of $3$) vertices.


Prooving by Pigeonhole principle I've been given a question to solve:

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

For this, I used the dynamic programming approach which is not optimized and takes O(m * m * n) where n is the no. of distinct elements.

But, It's optimized time-complexity is O(m^2). Here, is the solution.

But, while going through the explanation, I encountered this written:

If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m.

I did not understand this part and want to know, how will it be proved rather than trying it by taking examples.

Also, why is the equality present with n < m and not with n > m ?

Let the $n$ distinct positive integers are represented by $c_1,\ldots,c_n$. Now form a series of sums as;

\begin{align}
S_1 =&\; c_1 \\
S_2 =&\; c_1 + c_2\\
    \vdots & \\
S_n =&\; c_1 + \ldots c_n
\end{align}

Now, use the pigeonhole principle on the $S_i$'s with $m$ holes and place them into the holes according to their result modulo $m$. We know that at least two $S_i$'s are sharing the same hole since $n>m$. Let call them $S_i$ and $S_j$.

$S_i \equiv S_j \bmod m \implies S_j -S_i \equiv 0 \bmod m \implies m| S_j-S_i$

By using the definition of $S_i$ and $S_j$ we can say that if $i<j$ then $m \;|\; a_{i+1} + \ldots + a_{j}$

if $n <= m$ we cannot prove it and even we can find counterexamples.


Generating uniform random connected graphs: doubt about Wilson's algorithm I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a random spanning tree using a loop-erased random walk (also called Wilson's algorithm); then add remaining $m-n+1$ edges between random pairs of vertices.

I implemented and investigated this algorithm and have several doubts.

First, what do they denote with random spanning tree in the first part? A random spanning tree of $K_n$? If so, there are $n^{n-2}$ of them, so we may directly restore the tree by its (random) Prüfer sequence. Why do we need the loop-erased random walk here? As far as I experimented it gives the same distribution as the Prüfer-based generation.

Second. If I'm right at the first part and each tree is equiprobable, then different graphs may have different probabilities. For example, if $n=4$ and $m=4$, we have two graphs (I skipped the labels as they are irrelevant here):

o--o    o---o
|  |    |\ /
o--o    o o

The first one can be produced from some spanning tree in 4 distinct ways, while the second one only in 3 ways. If all trees are equiprobable, this obviously introduces bias in graphs.

Where is my mistake? I don't understand Wilson's algo and the distribution on trees is not uniform, or I don't understand the latter part, or this algorithm is in fact incorrect?

Finally, if it is incorrect, how does one generate a random connected graph? The approach of generating a random graph and checking its connectivity fails if $m = \Theta(n)$.

P.S. When saying about randomness, I assume that I have an oracle which returns me a uniform random number in range $[0, n)$ for a reasonable $n$.

Here are two alternative algorithms. There are probably better ones.

Large $m$ When $m \gg \frac{1}{2} n\log n$, it is very likely that a $G(n,m)$ random graph will be connected. Generate $G(n,m)$ graphs until one of them is connected.

Small $m$ When $m$ is small, you can try the following algorithm, which however might be a bit slow (or perhaps very slow). Generate a random graph according to the stackoverflow procedure, calculate the number of $T$ spanning trees it has, and accept with probability $1/T$. You can check that this produces a uniform sample, though the expected running time is $n^{n-2}\binom{(n-1)(n-2)/2}{m-n+1}/G_{n,m}$, where $G_{n,m}$ is the number of connected graphs on $n$ vertices and $m$ edges.

You can speed up the algorithm by sacrificing the accuracy of the sample. Find a number $M$ such that "most" graphs generated by the stackoverflow algorithm have at least $M$ spanning trees, and accept with probability $\min(M/T,1)$. You can estimate $M$ by sampling.


Confusion in Banker's Algorithm: How resources are allocated? I have seen examples about Banker's Algorithm from this Wikipedia link, this book and many other places. In all these examples some processes are allocated resources less than their Max Need.

For example, consider the state of system as shown in below given image taken from Wikipedia link:

Here you can see that the process P1's Max Need is 3  3  2  2 and the total available resources are 6  5  7  6. But the system allocates 1  2  2  1 resources to P1. Although it could allocate all the requested resources to P1 and P1 would have completed.

So my questions are:

Why does the system allocate partial / incomplete resources even when it has the resources available
If the allocation of partial / incomplete resources is allowed, then why does the system / algorithm enforce that the number of requested / needed resources should be less than the available resources (at the time of request)?. The system could allocate some resources (available at the time of request) to process(es) and the remaining would have been assigned when released by other processes.

OR

The process has to tell the number of resource types (and their instances) in advance, but does not need to be assigned all resources at a time; rather it is assigned resources when actually needed?

Please correct me if I am wrong.

The maximum resources are an estimate by the process of what they might need, the currently allocated is what the process holds at the moment. The idea is that processes request more resources as they need them (and at those points you run the algorithm to see if it could lead to deadlock to grant the resources asked for, by seeing if there is a process that could finish and release all it holds if it goes on to ask for it's maximum announced request, releases what it holds, and so on). If a process releases resources, that clearly can't lead to a deadlock, thus no special handling (except for recording what is free now) is needed.

Think of you e.g. building a box out of wood, and the tools needed. You'll need a saw, a drill, a screwdriver, among other tools. You'd announce that, but you won't require all together, while you are busy with the saw somebody else could use the drill and screwdriver, so it doesn't make sense to ask for all at the start, or keep all until finished.


Space complexity for connectivity problem with given graph diameter Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph.
Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity.

I thought about using the $STCON$ problem for the whole nodes in the graph, but that will yield a space complexity of $O(n^2 \log^2n)$ (according to Savitch's theorem).

Then I thought about using a DFS traversal (it will be needed twice, actually), but I don't know how to prove it's space complexity.

The idea here is to use a reachability-based approach. Given $u, v \in V$ we ask ourselves whether $u$ reaches $v$ in $G$. By definition, there exists a path that connects $u$ and $v$ if and only if there exists a path of length at most $D$; there are at most $d^D$ such paths.

Loop over all pairs of nodes and all paths to answer the original question. The total space required by this procedure is $\left \lceil \log(n^2d^D) \right \rceil$ plus a constant amount.


Language Accepted by a Turing Machine with a Useless State? What language is accepted by a Turing machine which has a state that it does not enter on input I?

Specifically,

1.If the accept state is the state that it never enters then should L={empty}?

2.If the reject state is the state that it never enters then should L={everything}?

3.What if the TM has multiple accept/reject states?

4.What if the state that it never enters is neither the reject nor accept states? How does that affect L?

I have searched around and I have found a couple threads that helped prove that this problem is undecidable but is it Turing-recognizable? Co-Turing Recognizable? Both?

The definition of the language accepted by a Turing machine is valid for all Turing machines, whether they have useless states or not. Absolutely nothing changes. If there is a useless state, removing it wouldn't change the language accepted by the machine, as does adding another useless state.

Consider a similar question about C programs. What if I have a function which is never called? Does this affect the way the program executes? It doesn't.1 The same holds for Turing machines.

1Actually it might, since you might run out of memory a tiny bit faster.


Is a language with only a stack of fixed-size integers Turing-complete? I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.

There is only one data type in it (integer, since that's the only data type brainfuck supports). It supports functions and subroutines (to which you can pass integers by value, but not arrays, though you can access an array in the global scope from within a function/subroutine) but it does not support recursion (all function and subroutine calls are inlined). It supports statically allocated arrays (size known at compile time) and has just one unbounded stack. You can store as many items as you like in the stack, unlike with arrays, but you only have one stack for your entire program.

I have these limitations to achieve a balance between ease of use, and fast generated code.

However, I never studied any of this stuff and I actually started this project to learn about compilers (by making one), therefore my question is:

From the above description, is this language turing complete?

If your language supports an arbitrarily large array of integers (even of numbers in $\{0,1\}$), then you can simulate the tape of a TM. Then, clearly your language is Turing complete.

EDIT: based on your comment, you don't have an arbitrary array.

In this case, you can do the following:
If you can keep two counters (integers), and increase or decrease them, and check whether they are 0, then you can simulate a two counter machine (Minsky Machine), which is Turing complete (with a caveat).

If you also bound the maximal value that an integer can take, then I believe that your machine is no more powerful than a PDA.


How fast we can run 128-bit LCG generator? Let's consider some 128-bit LCG generator mod $2^{128}$, with some random 128-bit multiplier and increment. How fast we can run it using the same tricks like in AES:
https://crypto.stackexchange.com/questions/44927/how-long-does-a-good-aes-encryption-take
They use there some hardware instruction/hardware acceleration and it is absurdly fast. Can we do the same thing with LCG? If we run pure LCG in C it could be several dozen of GB/s. But can we do it faster in some easy way?

If you have a linear congruential random number generator X, then applying X say 8 times is another LCG whose constants are easy to find. If X calculated a series a0, A1.a2 etc. then you can calculate a0 to a7, and then apply Y to all 8 numbers in parallel, assuming this takes a lot less than eight times the effort.
I hope you know how to calculate the same LCG many times without divisions.


Refutation in first order logic Consider the following statement

  In FOL, we can reduce entailment checking to satisfiability checking:

  $S \models  S' \iff S  \land \neg S'$ is satisfiable (This proof
  strategy is called refutation).

Is the above statement true? If yes, then I got confusion because of the following steps

$ S \models  S' \iff S\implies S'$ is true

$S \models S' \iff \neg S \lor S'$ is satisfiable

$S \models S' \iff \neg( S \land \neg S') $ is satisfiable

$S \models S' \iff  S \land \neg S' $ is unsatisfiable

Which one is true?

This looks like a typo in your source, and your derivation looks correct. So the corrected statement should be:

  $S \models  S' \iff S \land \neg S'$ is unsatisfiable

or

  $S \models  S' \iff {\boldsymbol \neg} (S \land \neg S')$ is satisfiable


Substructural Prolog? Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer.com/chapter/10.1007/3-540-40030-3_8 Grammar Induction as Substructural Inductive Logic Programming - if substructural Prolog is possible then one can implement substructural inductive logic programming in it (e.g. http://ilasp.com/ for the answer set version of ILP over Prolog in the non-substructural setting) and apply, e.g. in grammar induction case.

How hard the usual (e.g. SWI) Prolog should be remade to be used as substructural Prolog?

Logic programming with substructural logics has been studied, starting in the second half of the 90's. I am not an expert, but I can probably provide enough references to get you going.

There is Dale Miller's Lolli, a programming language for linear logic programming.

Major research was carried out by Frank Pfenning and his coworkers and students. For example:

Frank Pfenning: lecture notes on Linear logic programming, part of a course on linear logic (the web site also has some software)
Iliano Cervesato, Frank Pfenning: A Linear Logical Framework
Jeff Polakow, Frank Pfenning: Properties of Terms in Continuation-Passing Style in an Ordered Logical Framework
Frank Pfenning, Robert J. Simmons: Substructural Operational Semantics as Ordered Logic Programming

I am pretty sure someone implemented logic programming for ordered linear logic, poke around the work done by Jeff Polakow and Frank Pfenning. I don't seem to be able to find it right now.