Recursive definition of a language $ L $ over $ \{a,b\} $ How would I start the recursive definition of the following language:

L over {a, b} such that L consists of strings in which each
occurrence of b is immediately preceded and followed by an a

The 'and' part is causing me problems with this problem and I don't see a clean way to gurantee the occurence being preceeded and followed recursively.
The recursive definition structure is as follows:
Basis: The base we have to start with for the recursion
Recursive step: How we generat ethe language from the basis
Closure: Trivial to state
My thought process on this:
We can have lambda, because no b's or no a's doesn't apply to the condition.
My attempt so far:

Basis: $ \lambda \in L $
Recursive Step: If $ w\in L $ then $ aw, wa, babw, waba \in L $.

What i don't see is how th break the recursive step to account for being able to place b's anywhere in $ w\in L$ such that the condition is satisfied.

There is no problem to obtain $b$'s anywhere in the string: basically you can just "read" the string from left to right, and add the $aba$ to the end. That leaves one with only two recursive steps: if $w\in L$, then $wa\in L$ and $waba\in L$.

A bigger problem is that you now do not generate strings like $ababababa$!

This can be handled by having rules like: if the string ends with a $a$ we can add $ba$ to the end.


Dimension of 1x1 convolution output I am having a hard time understanding maths behind a 1x1 convolution and how is it actually performed.

Assuming that I have a 6x6x32 input to my 1x1xK convolution layer similar to the one presented in this video and shown below. I understand that I would take a 1x1x32 slice from the input ( blue in the image below), but what operation would I actually perform?

Do I just take one value, let's say at [1,1,1] of yellow and multiply each value in the input slice with this value, or do I multiply each value from the slice with the corresponding value in the 1x1x32 part.

Also what is meant by #filters? Doesn't it need to match 32 in a given example?

Have a look at this:
https://medium.com/machine-learning-bites/deeplearning-series-convolutional-neural-networks-a9c2f2ee1524

It's like this:
third dimension of input and filter must match!
So if you only have one of those yellow filters your output will be 6x6x1. But if you have let's say 42 filters then you'll perform 42 filter operations and your output will be 6x6x42.

Hope this helps ;)


An example of a non-regular grammar for a regular language? I understand that a regular language can be specified by either regular or non-regular grammars.  What is an example of a non-regular grammar for a regular language?

Regular Language L = {aab}

Non-regular grammar

S -> aAb

A -> a


What is the regular expression of this language? $\Sigma = \{0, 1\}$

$L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$  $ \#_1(x) = 3 \}$

What is the regular expression of this language?

At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $ or$ $ $ $r = (0+1)^*1(0+1)^*1(0+1)^*1$

And what is it's corresponding NFA/DFA?

I've been puzzled by this language and if it's regular for a while now.

Check RE and FA for finite automata construction.

It has to be regular since we can create Regular Expression for it.


reduce k-colorable to 3-colorable graph problem given a graph G = (V, E) of n vertices, decide whether G is k-colorable. if I were to have an oracle that solves for 3 color, how do I use it to solve the k color graph problem?

It is known that K-Colorability reduces to 3-Colorability in polynomial time as obviously both problems are NP-complete, and NP-complete problems are polynomial-time reducible to each other. However, in order to $k$-color a graph using a 3-coloring oracle, you need a specific reduction from $k$-colorability to $3$-colorability which is constructive in the sense that given a 3 coloring of the output graph, then you have a way to extract from it a $k$-coloring of the input graph (and not only prove that there exists a $k$-coloring). Such a reduction, was shown by László Lovász  here. Specifically, it was shown that Colorability reduces to 3-Colorability in polynomial time which is sufficient to solve your problem using the same reduction. Here is a very good explanation by Vašek Chvátal's for Lovász's reduction. The reduction has the following format:  given an instance to the Colorability problem which is a pair $\langle k, G \rangle $, where $k$ is a positive integer and $G$ is an undirected graph, the reduction outputs in polynomial time, a graph $G'$ such that $G'$ has a 3-coloring iff $G$ has a k-coloring. The proof in the link is actually constructive, in particular, it details how a k-coloring of $G$  can be easily extracted from a 3-coloring of $G'$ (When I say easily, I mean in polynomial time). So to solve your problem: given a graph $G$, you can consider the pair $x = \langle k, G\rangle$ ($k$ is constant in your problem) and feed $x$ as an input to the reduction to get $G'$ in polynomial time. Now using your oracle, you can 3-color $G'$, and then use the 3-coloring of $G'$ to extract a $k$-coloring of $G$.


What is running time of an algorithm? What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm? If so, how ?

What do we mean by running time of algorithms?

Depends on who is talking. It can mean everything from actual time in seconds to execution count of some asymptotically dominant instruction.
Things get muddied further by widespread overuse of Landau notation.

Also, one typically distinguishes at least worst, average and best case.

  when we say running time of bubble sort is $O(n^2)$, what are we implying?

Here we use that the actual running time is in $\Theta$ of the execution count of an asymptotically dominant operation. We can rigorously show that Bubblesort takes $\Theta(n^2)$ comparisons (in fact, we can get the exact number for worst-, best- and average case), that all other operations happen only $O(n^2)$ often, and thus the real running-time has to be in $\Theta(n^2)$ as well.

That assumes that our machine model (usually RAM) and the real machine differ only by constant factors (unknown to us). If you analyzed formally on the TM model, you could not carry over Landau bounds as easily. In general, converting between (reasonable) models can add a polynomial factor.

  Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm?

No, not at all. Assuming that by "asymptotic complexity" you mean a Landau bound on the runtime function $T$,

you only know the behaviour of T for $n \geq n_0$ for some $n_0$ that may be larger than anything you ever see in inputs;
you only know the behaviour up to a constant factor $c$;
you only know the type/degree of the leading terms but lower terms can be significant (i.e. the absolute error of your bound can tend to infinity, even if you have a tight estimate of the constant factor of the leading term).

Even if you knew $n_0$, lower-order terms and all constant factors,

these bounds are usually not tight and
the analysis gives you the execution of some operations, not actual time.

The only way to use formal analysis for predicting actual running times is

analysing the execution counts for all statements,
analysing up up to small error terms, and
know how many (nano)seconds each statement takes.

Sometimes we can do 1. and 2. but 3. is very, very tough for real machines -- which is why everybody in TCS analyses on clean machine models.


Shortest path between all pairs with colored nodes I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly.  The question is:

Let's say we have a directed graph with no cycles, it has N vertices and M edges.
Exactly 2018 vertices are colored green, and the others are black.
We know that in each shortest
path, each vertex is colored green,
perhaps without the first and the last node.

We can find the shortest path of all two pairs of nodes in:  O(___) and not less

What I tried:
If we run the Floyd Warshall algorithm on the 2018 green vertices we get the shortest path between all pairs of greens. (This is O(1) because of the green vertices amount is constant).

Now for each (u,v) in VxV:

If both u and v are green we already have the shortest path from Floyd Warshall.
If one is green and the other black, we add the edge's weight that connects the source/destination to the green group and add the Floyd Warshall result.
If both u and v, are black, we add the lightest weight of each which connects to the green group.

I think my solution is kind of messy, and I do not know if it's 100% correct.

The solution is: We can find the shortest path of all two pairs of nodes in:  O(n^2) and not less.

Your answer and reasoning are correct, but the last steps in your algorithm are wrong.

First, discard all edges with no green vertex.  Then:

To find the shortest path between a green and black node, you have to consider all of the black node's green-adjacent edges, and add the shortest path to/from the green.  There are at most 2018 of these, so it's still constant time.

To find the shortest path between two black nodes, you have to consider all combinations of their green-adjacent edges, and add the distance between the greens.  There are at most 20182 of these combinations, so it's still constant time.

So you can certainly do this in O(n2) time, and you can't do any better, because that's also the size of the output.

It may be simpler just to show how you can optimize Floyd-Warshall to take O(n2) time when all edges are known to be green-adjacent.


Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding? I use the same notation as I used in this previous question, About showing algorithmic gap instance for the Goemans-Williamson SDP The same definition continue.

Given a $f : \{0,1\}^n \rightarrow \mathbb{R}$ one defines a quantity called $\overline{sos}_d(f)$ which is the smallest $c \in \mathbb{R}$ such that one can find functions on the Boolean hypercube $g_1,g_2,..,g_t : \{0,1\}^n \rightarrow \mathbb{R}$ for some $t$ with $deg(g_i) \leq d/2$ such that on the Boolean hypercube we have the equality, $c -f = \sum_{i=1}^{t} g_i ^2$

So one would say that $\overline{sos}_d(f)$ is the minimum $c$ such that the inequality $c-f \geq 0$ has a ``degree-d SOS certificate" on the Boolean hypercube.

Now one claims that the GW algorithm for Max-Cut is "based on the upperbound $\overline{sos}_2(f)$" and this in equation means that for the objective function of Max-Cut $f_{Max-Cut(G)} = \sum_{(i,j) \in E(G) } (x_i -x_j)^2$ we have,

$max(f_{Max-Cut(G)}) \geq \alpha_{GW} \overline{sos}_2(f_{Max-Cut(G)})$

Is the above some immediate consequence of the GW analysis?  Can someone kindly help recast that as this inequality if this is indeed true?
Or if this inequality requires a separate proof then can someone kindly reference that? I haven't been able to find that..
Do we know anything about say showing something like,

$max(f_{Max-Cut(G)}) \geq (\alpha_{GW} + \text{something positive}) \overline{sos}_{\text{something greater than} 2 }(f_{Max-Cut(G)})$ ?

The quadratic sum-of-squares relaxation of Max-Cut should indeed work out to be equivalent to the SDP that Goemans and Williamson solve. I encourage you to work this out yourself. This means that the Goemans-Williamson analysis indeed shows the inequality you mention.

You ask whether degree-2 SoS is a rewriting of the Goemans-Williamson rounding. It isn't. Rounding is a completely separate issue. Degree-2 SoS is a rewriting of the SDP that Goemans and Williamson solve. Rounding is how we bound the integrality gap.

Assuming the Unique Games Conjecture, $\alpha_{GW}$ is the optimal approximation ratio achievable in polynomial time. Since optimizing degree $d$ sum-of-squares can be done in time $O(n^{O(d)})$, this implies (assuming UGC) that every constant degree $d$ has the same integrality gap $\alpha_{GW}$ in the worst case.


Problem easy for humans and hard for general purpose machine learning, not needing external context? There are many problems that people can solve more easily than a machine learning algorithm.  Often this is attributed to the extra context we have access to.

Image segmentation is an example of a problem that people are good at, but algorithms are not good at, probably because people have lots of external contextual knowledge they bring to bear on the problem.  To date, the best techniques use a human in the loop, such as this technique called click carving from HCOMP 2016.

Are there problems that people can solve more easily than most or all machine learning algorithms, where people do not need to depend on access to external context?

Here is another example that is easy for people but hard for a particular algorithm implementation called XGBoost.  A human can easily fill in the missing shapes with 100% accuracy, but XGBoost cannot score above 50% accuracy, and its accuracy drops as it gets more training data.  Neural networks also seem to have difficulty with this problem.

Note that the person does not need external knowledge about the problem that the algorithm does not have, in order to perform better.  All the person needs to see is the configuration of shapes, and they can guess from that what the missing shapes are.  The only information the human needs is that the simplest description of the data is most likely the best description, and that the training data is randomly sampled.  Both items of information are used in designing XGBoost, and most ML algorithms for that matter.

Are there other concrete examples like this?  Historically, the XOR problem showed that single node perceptrons were inadequate, leading to today's neural network.  Besides that, I do not know of any other historical examples.

This answer is an ongoing catalogue of instances I find.

"A Deep Belief Net Learning Problem" explains why shallow networks cannot learn XOR problems, stating that deep networks can.  However, empirically deep networks are not good at learning XOR problems, suggesting the XOR problem is one that is easy for humans but hard for neural networks.


Can lists be defined in a special way so that they contain things of different type? In https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf it is written that

A type $\tau$ list is the type of lists with elements of type $\tau$

Why must a list contain elements of the same type? Why can't it contain elements of different types?
Is there a way of defining a list polymorphically in the typed lambda calculus, so that it takes elements of any type?
Can we then use the List monad on lists, defined polymorphically?

The short answer is that $\tau\ \text{list}$ is defined as a type constructor, along with rules for formation and elimination, and so we could similarly define a type constructor that allowed terms of different types to form a single "variably-typed list". However, lists cannot take different types in the definition given, simply because they are defined with respect to a single type. In either case, adding lists, or variably-typed lists, involves extending the simply-typed $\lambda$-calculus, as lists of any kind do not exist in the usual presentation.
If we have a slightly richer type system than the simply-typed $\lambda$-calculus, we can encode variably-typed lists using standard $\tau\ \text{list}$s.

If we have a form of subtyping, we can store terms of different types, as long as they share a supertype. However, when we project elements out of the list, we can no longer tell specifically what type they were to begin with (this may be familiar from object-oriented programming), so this is a little limited.
If we have dependent sum types (also called $\Sigma$-types) and a universe type $\mathcal U$ (i.e. a "type of types"), we can form the type $(\Sigma_{A : \mathcal U} A)\ \text{list}$, whose elements are pairs consisting of a type $A$ and a term of that type.

Finally, I'll just note that polymorphism doesn't help us if we want heterogeneous lists: it just allows us to manipulate homogeneous lists for different $\tau$ more effectively. Polymorphic types have to be uniform in some sense, which is why we need dependency here instead.

To answer a follow-up question: if we have two variably-sorted lists using the dependent type approach, we can concatenate and flatten lists just as with ordinary lists.

The $\mathrm{List}$ monad has an operation $\mathrm{join}$ (in the language of Haskell), so given a list of variably-typed lists, $$l = [[(A, a), (B, b)], [(C, c), (D, d)]] : (\Sigma_{X : \mathcal U} X)\ \text{list list}$$ we can perform $\mathrm{join}$ to get a new list: $$\mathrm{join}(l) = [(A, a), (B, b), (C, c), (D, d)] : (\Sigma_{X : \mathcal U} X)\ \text{list}$$
Similarly, $\tau\ \text{list}$ can be equipped with a concatenation operation $+\!+$, so given the two lists in the previous example, we can concatenate them for a similar result:
$$[(A, a), (B, b)]\ {+\!+}\ [(C, c), (D, d)] = [(A, a), (B, b), (C, c), (D, d)] : (\Sigma_{X : \mathcal U} X)\ \text{list}$$


Are non-ordered (Slabbed) Neural Networks in wide modern use and what does Fiesler (1994) mean by Clamping Function and Ontogenic function? In Fiesler (1994) Neural Network Classification and Formalization, he talks a lot about a more general version of neural networks, one that is not ordered into layers, but rather the network is called slabbed and the "layers" are instead called clusters. Unlike for feed-forward networks, slabbed networks may be cyclical and terminate when a stable state has been reached, rather than when propagation has reached output neurons.
Much of this paper is outdated (terminology in particular). Is this an outdated concept or are these types of networks being used and/or researched?
Also from this paper, he mentions "clamping functions", but I am not sure what he means. Here is an excerpt where he talks about clamping functions:
"clamping functions, which determine if and when certain neurons will be
insusceptible to incoming information, that is, they retain their present
activation value independent of external stimuli"
I have seen a few more recent uses of "clamping" in literature, but they tend to be referring to something different. What exactly is he talking about here and is there a modern name for this?
Similarly, he refers to ontogenic functions and ontogenic networks, which I believe we call dynamic networks, but what is the ontogenic function? I understand it dictates how the network changes, but mathematically what are the inputs and outputs? What triggers the change to start and/or stop?
I am very interested in this formal definition of neural network as a mathematical object (this tuple with topology, interconnection structure, transition functions and intial state), does anyone know of a source that gives a similarly rigorous definition of a neural network, but with more modern terminology and ideology (I imagine some developments in theory may have allowed for networks to be more general)?

I have not heard of recent work on this kind of thing, but there's a huge amount of literature and I know only a tiny slice of it.
Today much of the work on neural networks is concerned with feedforward neural networks, which don't have a cyclical structure.  The most common form is
$$z(x) = L_n(\cdots (a(L_1(x))))$$
where $f:\mathbb{R}^n \to \mathbb{N}^k$, each $L_i$ is a linear function, and each $a$ represents an activation function: i.e., $a(x_1,\dots,x_d) = (a(x_1),\dots,a(x_d))$ and $a$ is a simple nonlinear function called the activation function.  The ReLU $a(x)=\max(0,x)$ is a common choice of activation function.  There is some cleverness in the structure of the linear layers.  Finally, the output of the neural network is $f(x)=\text{softmax}(z(x))$ where
$$\text{softmax}(z_1,\dots,x_k) = ({e^{z_1} \over e^{z_1} + \dots + e^{z_k}}, \dots, {e^{k_1} \over e^{z_1} + \dots + e^{z_k}}).$$
This is not the only architecture, but it is probably the most commonly seen, and as you can see, it has a relatively clean formalization.


Min path cover problem in Cormen et.al. question about notation In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here:

A path cover of a directed graph $G = (V, E)$ is a set $P$ of vertex-disjoint paths such that every vertex in $V$ is included in exactly one path in $P$. Paths may start and end anywhere, and they may be of any length, including $0$. A minimum path cover of $G$ is a path cover containing the fewest possible paths.
a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph $G =(V, E)$ (Hint: Assuming that $V = {1, 2, ... , n}$, construct the graph $G' = (V',E')$, where:
$$V' = \{x_0,x_1,\dots x_n\} \cup \{y_0, y_1, \dots y_n\} $$
$$E'=\{(x_0,x_i):i \in V\} \cup \{(y_i,y_0) : i \in V\} \cup \{(x_i,y_i):(i,j) \in E\}$$
and run a maximum-flow algorithm.)

What are the $x_i$ and $y_i$ here? Am I missing something obvious?

The graph $G'$ has $2n+2$ vertices. We give them the names $x_0,\ldots,x_n,y_0,\ldots,y_n$ to make it easy to refer to them. So $x_i,y_i$ are just names of vertices. They have no value, and do not refer to anything. In that regard, they are akin to indeterminates.
What might be confusing you is the existence of a different graph $G$, which has $n$ vertices. The vertices $x_i,y_i$ are just vertices – they are not variables referring to vertices of $G$. The "value" of $x_i$ is just $x_i$.


The meaning of discount factor on reinforcement learning After reading of the google deepmind achievements on Atari's games, I am trying to understand the q-learning and q-networks, but I am little bit confused. The confusion arise in the concept of the discount factor.
Brief summary of what I understand.
A deep convolutional neural network is used to estimate the value of the optimal expected value of an action. The network has to minimize the loss function
$$
L_i=\mathbb{E}_{s,a,r}\left[(\mathbb{E}_{s'}\left[y|s,a\right]-Q(s,a;\theta_i))^2\right]
$$
where $\mathbb{E}_{s'}\left[y|s,a\right]$ is
$$
\mathbb{E}\left[r+\gamma max_{a'} Q(s',a';\theta^-_i)\right|s,a]
$$
Where $Q$ is a cumulative score value and $r$ is the score value for the action choose. $s,a$ and $s',a'$ are respectively the state and the action choose at the time $t$ and the state and the action at the time $t'$. The $\theta^-_i$ are the weights of the network at the previous iteration. The $\gamma$ is a discount factor that take into account the temporal difference of the score values. The $i$ subscript is the temporal step.
The problem here is to understand why $\gamma$ does not depends on $\theta$.

From the mathematical point of view $\gamma$ is the discount factor and represents the likelihood to reach the state $s'$ from the state $s$.

I guess that the network actually learn  to rescale the $Q$ according to the true value of $\gamma$, so why not letting $\gamma=1$?

The discount factor does not represent the likelihood to reach the state $s′ $from the state $s$. That would be $p(s'|s,a)$, which is not used in Q-Learning, since it is model-free (only model-based reinforcement learning methods use those transition probabilities).
The discount factor $γ$ is a hyperparameter tuned by the user which represents how much future events lose their value according to how far away in time they are. In the referred formula, you are saying that the value $y$ for your current state $s$ is the instantaneous reward for this state plus what you expect to receive in the future starting from $s$. But that future term must be discounted, because future rewards may not (if $γ < 1$) have the same value as receiving a reward right now (just like we prefer to receive \$100 now instead of \$100 tomorrow). It is up to you to chose how much you want to depreciate your future rewards (it is problem-dependent). A discount factor of 0 would mean that you only care about immediate rewards. The higher your discount factor, the farther your rewards will propagate through time.

I suggest that you read the Sutton & Barto book before trying Deep-Q in order to learn pure Reinforcement Learning outside the context of neural networks, which may be confusing you.


Smallest convex set containing given point Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is there an (efficient) algorithm that finds $n+1$-subset of $M$ with smallest convex hull that contains $x$ (or, $k$-subset for some $k < n + 1$ if such exists)? "Smallest" is defined according to the volume in $R^n$ (or $R^{k-1}$). "Efficient" would imply something much better than the brute force strategy that examines all $n+1$-subsets of $M$.

Here is an idea to find a "smallish" simplex containing your given point $x$. It does not find a smallest simplex (except by luck).

Construct the convex hull $H$ of your set of $M$ points.
For each $p$ of your set $M$, shoot a ray from $p$
through $x$ until it hits a facet $F$ of $H$. Then $F \cup p$ is a simplex containing $x$. Repeat for all $p \in M$ and retain the smallest volume simplex.

It is easy to create examples where this is terrible, as it is biased toward a simplex
containing a facet of the hull. One can imagine various heuristics to improve, for
example, discarding from $M$ the vertices of $H$ and repeating.


Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].

Why Isn't this construction considered a counterexample to P = NP? And if it is not, can it be strengthened into one? It seems tome that we have constructed a languge recognizable in NP time but not in P time.
In the proof there is the sentence "If P_i^B(i) accepts 0^n, then place no string into B at this stage." How can this possibly happen?

I figured that, since B is intially empty, the oracle B(i) ALWAYS rejects. So the only reason why P_i would accept is some reason OTHER than a  question to B(i). Please correct me if I am wrong.

The proof in question is verbatim reproduced here. The original paper is here.

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know.

As you can see there, the complete statement of Baker, Gill, Solovay is:

  There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$

The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "divide" by B so to say. Constructing a oracle language $L^A$ out of a "normal" language $L$ is not that easy. The languages $P^B$ and $NP^B$ behave completely different than $P$ and $NP$. To show you an example for this: Even if $P=NP$ is true, the statement $P^B \neq NP^B$ is still valid. This shows how different $P,NP$ and $P^B, NP^B$ behave.

  It seems to me that we have constructed a language recognizable in NP time but not in P time.

Be careful here. It is shown that unary language $U_B$ can be recognized by a $NP^B$-TM, not by a $NP$-TM. Again, this is because Oracle-Languages/TMs behave completely different than their "normal" counterparts. If you want to recognize $U_B$ in $NP$ without the oracle, you have to do a lot more work as you could guess a word $w$ of length $i$ in poly. time, but you cannot decide $w \in B$ that easy, as we have no clue by BGS if $B \in NP$ or not.

  And if it is not, can it be strengthened into one?

Maybe yes, maybe not. As this would solve $P=NP?$, which is unknown, it is unknown if you could strengthen it or not.

  In the proof there is the sentence "If $P_i^{B(i)}$ accepts $0^n$, then place no string into B at this stage." How can this possibly happen?

As you just simulate all TMs in $P_i^{B(i)}$ and don't change them, you cannot change whether the TM accepts or not. For example, the TM that accepts all words is in $P$, so it also is in $P^B$, so it will be simulated at some point. Then, your case will happen. Of course, this TM will not call the oracle once.

Edit 3:

Now I want to convince you that your Algorithm does not run in $NP$-time. I can't convince you by now that really $B \not \in NP$, but I think I can convince you now at least that this algorithm does not gives us $B \in NP$.

Let's try to formulate your algorithm as an $NP$-TM that decides $w \in B$ (using original BGS, Theorem 3 now):

Guess $i$ s.t. $M_i^B(1^{|w|})$ is the poly-TM where $n:=|w|$ is choosen. See that $M_i$ has access to oracle $B$. Guessing $i$ is possible because $i\leq n$ as each stage needs a unique $n$. However, can we verify that $i$ is right? To do so, we might have to really build $B$ from stage $i=0$, which would take to long.

2. Simulate $M_i(1^{|w|})$ for $2^n/10$ time. I'm not sure whether we can do this. We don't know if $M_i$ is a poly-time TM, so we can't really guess a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$  so it could really run for $2^n/10$ time as we enumerate all TM's so e.g. also the $EXP$-hard ones. Can you find a fix for this? If so, I will re-edit this answer to describe the next steps. Using original BGS now:
Simulate $M_i^B(1^{|w|})$ for $p(|w|)$ time. We can guess the polynomial $p$ in $NP$-time. However, can we verify that $p$ is the right polynomial? We cannot assume that it's right and I can't find an easy way to do this. But here comes the problem: Can we really simulate $M_i^B(1^{|w|})$ in poly. time? I want to convince you that this is not the case.

2.1. If $M_i^B(1^{|w|})$ writes $x_B$ on the oracle tape and asks $x_B \in B?$, what can we do in $NP$ without the oracle? We can only start another simulation, guess another $i'$ s.t. stage $i'$ takes $n':=|x_B|$ and simulate $M_{i'}^B(1^{|x_B|})$.

However, how many such new simulations do we have to do in the worst case? $M_i^B(1^{|w|})$ with running time $p(|w|)$ could ask the oracle $p(|w|)$ questions of length $p(|w|)$. Let's look at some arbitrary question at step $j$ now. Let the asked question in step $j$ be $x_B \in B?$. Now, we have to guess $i'$ s.t. $n':=|x_B|$ and simulate $M_{i'}^B(1^{|x_B|})$. Let $p'(|x_B|)$ be the running time of $M_{i'}^B(1^{|x_B|})$. Now, in the worst case, $M_{i'}^B(1^{|x_B|})$ asks the oracle $B$ in every of the $p'(|x_B|) = p'(p(|w|))$ steps again a question of length $p'(|x_B|) = p'(p(|w|))$. And this can go on and on.

In the end, we have build a tree with the vertex degree being $O(p''(|w|))$ for some polynomial $p''$. The depth of this tree can be pretty huge, because $i$ could equal $i'$. Let's assume just for simplicity that in each step $j$ we asked each stage $k \in \{1,\cdots,n\}$ exactly one question. Then we have depth $n$ for each path from the root to some leaf in the tree. Therefore, to answer the initial question $w \in B?$, we have to look at each of the $O(p''(|w|))^n$ verticies. Clearly, this can only be done in exponentioal time and not in polynomial time, because we have a exponention number of vertecies w.r.t $|w|$. Therefore, the algorithm does not run in $NP$-time.


How many comparisons do we need to find min and max of n numbers? Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers.

Recurrence for the above problem is

$$T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2$$
$$\approx 1.5 \times n - 2$$

hence

$$T(100)=1.5 \times 100 - 2 = 148$$

But by solving like as I've mentioned below, I'm coming up with the ans 162

We can divide list of 100 numbers in two list (50,50). Now upon combining the result of these two list 2 more comparisons will be required. Now recursively we break the lists like below, which will make a binary tree

$$100 \implies (50,50)$$
$$50 \implies (25,25)$$
$$25 \implies (12,13)$$
$$12 \implies (6,6), 13 \implies (6,7)$$
$$6 \implies (3,3), 7 \implies(3,4)$$
$$3 \implies (2,1), 4 \implies (2,2)$$

By combining the results upwards in the tree with 2 comparisons on merging each two lists I'm coming up with ans 162. What am I over counting.

You're dividing badly. If you look at your execution tree, you'll notice that most of the leaves on the last level are 3's. This means you'll need 3 comparisons here. For the same cost you could also compare 4 elements. Your efficiency here is 75%.

Your partial trees have to be full to be the most efficient. So you'll need to divide into trees with numbers of elements that are powers of two.

In your case dividing into a left oriented tree it's

T(100) = T(64) + T(36) +2
       = T(64) + T(32) + T(4) + 4
       = 94 + 46 + 4 + 4
       = 148


Batch sizing for convolution neural networks -- powers of 2 or powers of primes? The conventional wisdom for convolution neural networks (CNNs) is to make the batch size a power of 2 because of hardware utilization/optimizations done in the convolution layers.

A similar logic applies to the Fast Fourier Transform (FFT). However, the FFT is actually best used when it is a size of a power of primes (e.g. $2^M3^N5^P$ where $M,N,P$ are positive integers.)  I was wondering if this also applies to CNNs.

No.  It doesn't apply to CNNs.  CNNs are doing the same operation on each item in the batch; it's much simpler than what's happening in a FFT (which involves interaction between the elements of the array; you can't compute a FFT by just separately doing something to each element of the array in parallel).


A question from Computer Organization on Peak Clock Frequency Given below are 3 different pipelined processors:

$P_1:\ 4\ stages\ with\ delays\ \ \ \ 0.6_{ms}\ \ 0.8_{ms}\ \ 0.6_{ms}\ \ 1.1_{ms}\\
P_2:\ 4\ stages\ with\ delays\ \ \ \ 2.0_{ms}\ \ 1.8_{ms}\ \ 2.0_{ms}\ \ 1.0_{ms}\\
P_3:\ 5\ stages\ with\ delays\ \ \ \ 1.0_{ms}\ \ 0.8_{ms}\ \ 1.0_{ms}\ \ 1.5_{ms}\ \ 1.5_{ms}$

One has to find the Peak Clock Frequencies of each $\mathbf{P_i}$. Pipeline buffer register latency is Zero.

I don't know how to solve this, but I've come up with an intuitive formula for calculating peak frequency of clock for processor $P_i$ as $$\mathcal{C_{p.f}}=\frac{1}{max(d_i)}$$ where $d_i$ is individual stage delay for processor $P_i$. For example for $P_2$ it's $\frac{1}{2}KHz = 0.5 KHz$.

Now I don't know whether it's the correct way to calculate peak frequency.
If it's not, can anyone tell me what is it?

P.S: I also don't know whether this is the right place to ask this question.
But I didn't have any idea about where to post it otherwise.

The peak possible frequency is, no doubt, equal to the inverse of maximum time supported by each stage. The stage consuming maximum time is the limiting condition and your anwer is correct.


Scheduling problem on bipartite graph Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled.

If $u_i$ and $u_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?

So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.

If we can generate a Bipartite Graph, the edges ${ v_i, ...v_j}$  going across are all non-conflicting matches. Those edges for this matching ( $M_1$) can be held on that day. Next, we remove ${ v_i, ...v_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.

Not sure if this is what you asked for.


Limitations of Stack Inspection This is a follow up to the How does Stack Inspection work? that explores the notion in more detail

Stack inspection is a mechanism for ensuring security in the context of the JVM and CLR virtual machines when externally downloaded code modules of different levels of trust may be running together. That system libraries need some way of distinguishing between calls originating in untrusted code and calls originating from the trusted application itself. This is done by associating with code the principal corresponding to its origin. Then access permissions are recorded on the stack and whenever a call to a sensitive, system method is made, the stack is traversed to see whether the appropriate permissions for the principal making the call are present on the stack.

  What are the limitations of stack inspection? What mechanisms have been proposed to replace it? Have any significant changes been made to the model since it was introduced in the late 90s?

Stack inspection is necessary because programs on the JVM and CLR have default access to dangerous operations, so something must be done to prevent disasters. For example an untrusted program can reference an I/O library and call it:

using IO;
...
IO.DeleteFile("/home/foo/bla");

So on each dangerous operation made, we need to check whether it is allowed. With stack inspection it is generally complicated to understand who gets access to what. It also makes optimizations such as inlining and tail calls difficult.

A superior mechanism is to not give each program automatic access to dangerous operations in the first place. In this model there is no way to import an IO library. The only way to get access to an IO library is if somebody else gave it to you. This is called capability security. An introduction can be found here.

Instead, we would write the previous program like this:

Main(IOLibrary IO){
  IO.DeleteFile("/home/foo/bla");
}

The IO library is a parameter to the entry point of the program, and this is called a capability (because it gives use some capability, in this case to do IO). To be able to run this program, we must have access to an IO capability ourselves, and run the program by calling Main(ourIOlibrary). If we are running an untrusted program, we simply do not pass our IO library to it, since it might use that library to delete our files. In some cases we want to give an untrusted program limited access to the filesystem. In that case we create a wrapper around our own IO library that only allows access to a certain directory, and pass that one to the untrusted program instead of the full IO library

So if we need an IO capability to invoke a program that needs an IO capability, that also means that whatever invoked our program needed to have access to an IO capability to be able to give it to us. So where did its IO capability come from? Well, eventually there is a point where the human operating the computer invoked a program. This human has access to all the system capabilities, so he was able to pass the IO capability on. If this human does not trust the program he is running, then he simply will not pass his IO capability to it.

You can probably easily imagine other kinds of capabilities: internet access, access to draw stuff on your screen, etc. For example a secure browser plugin system might give a graphics capability to an untrusted plugin that only allows it to paint graphics in a predefined rectangle on the page.


Finding a minimal containing rectangle from a given set of rectangles The problem is as follows:

Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations:

Check, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns true iff there is a rectangle $c\in S$ so that $r_x \leq c_x$ and $r_y \leq c_y$.
Get, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns the minimal member of $S$ (that is, a member with a minimal area - $c_x c_y$) that contains $r$ (i.e., $r_x \leq c_x$ and $r_y \leq c_y$).
Insert, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and adds it to $S$.
Remove, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and removes it from $S$.

The four procedures have to be efficient, measuring efficiency by $m$ and $n$, where $m$ is the number of different widths in $S$ and $n$ is the number of different heights in $S$.

Space efficiency has to be no worse than $O(mn)$ (that is, linear to the number of elements in $S$).

Check, insert, and remove can be accomplished by a data structure for dynamically maintaining 2D maxima (this 2011 paper by Brodal and Tsakalidis presents a history of the problem including their new algorithm). I have no idea how to do get.


Which word to pump in pumping lemma? Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in dependence of the number $n$? The problem is that I got an $m$ and an $n$ in the exponent and they cannot be equal. Can I choose $0^{n+1}1^n$ for the word?

You can use any word in the language that lets you complete a proof. The pumping lemma says that, if a language $L$ is regular/context-free, then every long-enough string in the language can be partitioned in a way that generates an infinite set of strings that are also in $L$. So, if you can find any string in $L$ where the partition generates strings outside $L$, you're done.

Finding the right string to start with requires some thought and creativity; I'm not aware of any general method for doing it. I've not written anything out but I think that, if you start with $0^{n+1}1^n$, the proof won't work. However, you should try doing the proof with that string. Assuming that you don't make any mistakes, there are two possible outcomes:

you win by successfully proving that the language isn't regular;
you find that the proof doesn't work, and if the reason is the one I'm expecting, it should guide you straight to a better string to try to pump.


algorithms and the sequencing of numbers given a value The numbers in the table below are the result of executing an algorithm that has one parameter $n$, a non-negative integer, and produces sequences of integers as outputs. For values of $n$ from 0 to 5, the algorithm produces the following sequences of numbers as outputs:

$n = 0$: 0, 2.
$n = 1$: 3, 5, 7, 9.
$n = 2$: 6, 8, 10, 12, 14, 16.
$n = 3$: 9, 11, 13, 15, 17, 19, 21, 23.
$n = 4$: 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
$n = 5$: 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37.
$n = 6$: ?

I just started a course and I don't understand. I get the pattern differences and I understand all the patterns that are formed such as each outputs first number is a multiple of three and then the lists rise by two for each output given. When I put this down off of what I was given as a reference in the class it tells us to create an algorithm for this, but we have not been given but a few ways to do this so I tried:

$n^2-2\cdot0$ which would be $36-0=36$.
$n^2-2\cdot1$ which would be $36-2=34$.
$n^2-2\cdot2$ which would be $36-4=32$.
$n^2-2\cdot3$ which would be $36-6=30$.
$n^2-2\cdot4$ which would be $36-8=28$.
$n^2-2\cdot5$ which would be $36-10=26$.

So my outputs come out as 36, 34, 32, 30, 28, 26.
Is this correct? If not, where am I going wrong?

I don't see an algorithm in your answer. Also, I doubt that if you convert your sequence of steps into an algorithm, then it will produce the correct answer for $n=0,\ldots,5$.
From the given examples, you can see that the first number in the sequence is always $3n$, and from then on the numbers increase by $2$ each time (as you mention; but then in your "algorithm" they decrease by $2$ each time), and in total there are $2(n+1)$ of them (you can see this since the length of the sequence increases by $2$ each time).
How do we convert this into an algorithm? An algorithm is a recipe that prints the sequence for every value of $n$, not for the particular value $n=6$. Also, it should reproduce the given sequences for $n = 0,\ldots,5$.
Your question makes me doubt that the lecturer has explained the concept of "algorithm", so instead, try to write a function in your favorite programming languages that given $n$, prints the sequence corresponding to $n$. Code is just a formal way of presenting an algorithm.


Transitive Amstrong Rules I have R={A,B,C,D,E} with functional dependencies ABCD → E and AC → ABCD,with Axiom of transitivity rule is AC → E a transitive dependency? Thanks before and sorry for this simple question

From the definition of transitive dependency -

A functional dependency is said to be transitive if it is indirectly formed by two functional dependencies. For e.g.

X -> Z is a transitive dependency if the following three functional dependencies hold true:

X->Y
Y does not ->X
Y->Z

Given, ABCD->E and AC->ABCD, or simply AC->BD

So, ABCD -> E can be written as AC -> E, as AC->BD.

So, the transitive rule is not required to prove AC -> E

Also, if we take X= AC, Y=ABCD, then X->Y (given) but X is subset of Y

So, Y->X (failing the second rule for transitivity)


Is computation expression the same as monad? I'm still learning functional programming (with f#) and I recently started reading about computation expressions. I still don't fully understand the concept and one thing that keeps me unsure when reading all the articles regarding monads (most of them are written basing on Haskell) is the relation between computation expressions and monads.

Having written all that, here's my question (two questions actually):

Is every F# computation expression a monad? Can every monad be expressed with F# computation expression?

I've read this post of Tomas Petricek and if I understand it well, it states that computation expressions are more than monads, but I'm not sure if I interpret this correctly.

First of all, computation expressions are a language feature, while monads are mathematical abstractions, so from this point of view, they are completely different things.

But that would not be a very useful answer :-). Computation expressions are a language feature that gives you a syntax which can be used for programming with computations (or data types) that have the monadic structure, but they can be also used with other structures. You can read my F# computation expression zoo paper for more details, but computation expressions can be used with:

Monads, but also additive monads (what Haskellers call MonadPlus or MonadOr)
Composed computations (what Haskellers call monad transformers)
Computations that are monadic, but support other F# constructs like exception handling
Monoids (and a couple of variations without monadic bind)
Applicative functors (though this is only implemented in a research extension)

So, computation expressions are certainly closely linked to monads, but they are not linked to them that closely. This is in contrast e.g. with Haskell's do notation, which is much more closely linked to monads (although even that can be used with computations that are not strictly mathematically monads).


For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient? I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) should be sufficient for all AVL tree operations, so essentially we don't need to keep heights of the node for every node. Can anyone prove to me why that would be the case?

The core argument is that the balance can never change by more than one when inserting or deleting a single key; of course, since heights can only change by at most one.

That way, knowing the old balance (which is in $\{-1,0,1\}$) and if (and how) subtree heights changed is enough to know the new balance (which is in $\{-2,1,0,1,2\}$).
If the balance is $-2$ or $2$ we rotate, of course, and restore balance (in that node).

In order to prove this, simply write out all possible cases of old balances and changes due to insertion or deletion.


PDA that accepts if there is an "a" in the second half of the string How could I build a PDA on $Σ = \{a,b\}$ that accepts if there is an "a" in the second half of the string?

Formally the language is the following: $L = \{xy \mid x ∈ Σ^*, y ∈ Σ^*aΣ^* \land |x| ≥ |y|\}$.

The PDA has three phases. In the first phase, it adds $A$ to the stack per character. It switches to the second phase nondeterministically. In the second phase, it removes $A$ per character. It switches to the third phase nondeterministically, during which it empties the stack. The PDA accepts if it encountered an $a$ during the second phase.


A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program.

But Simply-typed lambda calculus has to stop - so the question is, can anyone show some "useful" program in Turing-complete language (e.g. untyped lambda calculus) that does not go into infinite loop but cannot be written in (simply-)typed lambda calculus?

from comment section:

"Yes I know all of these and I know that they are more expressive and those - but halting problem would only have meaning if there is an algorithm (program) that typed ones cannot express - otherwise, we can write all programs into typed one and see whether it is well-formed, right? Then we automatically know whether a program halts or not. This is what I am asking."

The distinction isn't just about being able to write non-terminating programs. There are significant differences even between normalizing lambda calculi. For example, consider System F. It's normalizing, so all its programs are terminating (so it's not Turing complete), but it has much more expressive power than the simply-typed lambda calculus (it can express any function that can be proved total in second-order Peano arithmetic).

Perhaps the simplest example is Church numerals. In System F Church numerals can be expressed as terms of type $\forall\alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Each natural number $n$ is then represented as
$$\Lambda\alpha.\lambda f:(\alpha\to\alpha).\;\lambda x:\alpha.\; f^n x$$ where $f^n x \equiv \underbrace{f(f(...f}_{n\mbox{-times}} (x)...))$. In the untyped lambda calculus it would be just $\lambda fx.f^n x$.

However, we cannot represent Church numerals and operations on them in the simply typed lambda calculus, because it lacks the necessary polymorphism.

Church numerals can be viewed as one of the simplest recursive data structures. In Haskell we could represent them as

data Nat = Z | S Nat

foldNat :: Nat -> (r -> r) -> (r -> r)
foldNat Z     f z  = z
foldNat (S n) f z  = f (foldNat n f z)

(Observe that foldNat actually converts our representation into the System-F representation.)

System F and the untyped lambda calculus allow us to represent any (inductive) recursive data structures such as list, trees etc. in the similar way as we represented Church Numerals (see System F Structures). This is not possible in the simply typed lambda calculus - it can express only non-recursive data structures with bounded size.

A good source of information is Proofs and Types by Jean-Yves Girard, Yves Lafont and Paul Taylor.


Approximating a discrete distribution I have a discrete distribution of reference. For the example let's say:

P(X=1)=0.2
P(X=2)=0.7
P(X=3)=0.1

Now I am given n numbers, and I want to group (sum) those numbers into 3 bins and approximate as close as possible the above distribution in the sense of minimizing the sum of squared error. So let's say I have those numbers: 10, 25, 25 50 (total sum =100). So I want to group them into 3 bins, and ideally the sum of each bin would be 20, 70, 10 and that would perfectly match the distribution. Unfortunately that's not possible and the best here would be 25, 75 (50+25), 10. The error here is (25-20)²+(75-70)²+(10-10)²=50

What is the algorithm solving the general problem?

The case where $\Pr(X=1)=\Pr(X=2)=\tfrac12$ is the subset sum problem, which is NP-complete so you won't find an efficient algorithm in general. Dynamic programming is probably the way to go.


What is prefix monotonicity? I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly.

For now I have "a stream transformer is prefix monotonic if its output for a given input record r is dependent only on the input stream up to and including r, and independent from whether r is the last record in the stream". But this was gathered by word-of-mouth and I am not sure it is the proper approach.

I would welcome suggestions for:

proper formal background and definitions;
useful analogies to explain the concept to a newcomer (the audience of the paper needs to understand prefix monotonicity but may not be knowledgeable with TCS).

This publication provides a definition of prefix monotonicity: link

Definition:

"Prefix monotonicity reflects a basic property of communicating systems: assume we have
observed a finite sequence of output messages for a corresponding finite sequence of input
messages. Then if we observe additional input (thus the old input sequence is a prefix of the extended one) we may just observe additional output (thus the old output sequence is a prefix of the extended one). Prefix monotonicity provides a notion of causality between input and output. It reflects the stepwise consumption of input and production of output and guarantees the existence of least fixed points, which is mandatory for giving meaning to communication feedback loops."


Test two LTL expression trees for equivalence Is there an algorithm on how to check if two LTL expressions (represented as binary trees) are semantically equivalent? Since there are many smaller equivalences such as
$a\Rightarrow b \equiv \neg a \vee b$ or  $F(a) \equiv true U a$ as well as commutativity, distributivity, etc. that need to be considered.
My initial idea was to create the truth table for both expressions and compare them. But then the temporal operators would not be taken into account. Creating and comparing the automaton for each expression sounds like it would be rather inefficient.
Is there a better way to do this?

Unfortunately, the approach of constructing automata for each formula and testing their equivalence is pretty much the best you can do.
The problem of checking whether an LTL formula is valid, that is, whether it is satisfied in every computation, is PSPACE complete (this is an easy exercise, given that LTL satisfiability is PSPACE complete).
Thus, checking whether two LTL formulas are equivalent is also at least PSPACE hard, since you can reduce from the former by testing equivalence with the formula "true".
In order to show membership in PSPACE, you can take the standard approach of checking equivalence of the corresponding automata "on the fly", without actually constructing them  explicitly.


Does this "reference" problem have a name? I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course).
The situation is as follows:
I receive distinct items (A...E in the below sketch) one after the other. Each item has a relation which can generally be termed "descendance" or "family" and is in itself anonymous - the only requirement is that an item can only belong to one family and that it must somehow be possible to distinguish the families. Items keep coming in and are referenced to their own family (like A and B in step 1), but sometimes an item can change the situation for other items already received: see the second step of the sketch: a connection in C points back to A and B and revokes their original descendances and points them to the family of C. Such connections are transitive, which can be seen in step 3: the connection between E and C also converts the descendance of A and B to the new family of E.

The task I need to solve is to keep the descendance relation correct for all items. It may look trivial but the solution that I am looking for should be O(n), n == number of items.
Is there a name (and most likely a different description) of the problem in
literature?

This is disjoint-set data structure.

Here is the summary at Wikipedia. I put the statement about time-complexity in bold font to emphasize its efficiency.

  In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

There are many tutorials for this data structures on the web, such as the one at TopCoder and the one at GeeksforGeeks.


Calculating disk seek times I have  a system where disk requests come to a disk drive for cylinders in the order 10, 22, 20, 2, 40, and 38 at a time when the disk drive is reading from cylinder 20.  The seek time is 6ms per cylinder.  I have to find total seek time if the disk scheduling algorithm is First-Come-First-Serve (FCFS).

To find the answer I used a formula:

total seek time=0.254*sqrt(d)(for each cylinder and sum them)

But that gave the incorrect result.
What formula(s) should I be using to handle questions like this?

@tonny,
     I am also found this example from a book, I think the number 6 is missed after the number 40 in the example. The correct order is 10, 22, 20, 2, 40, 6 and 38.
So if it starts from cylinder 20,
You can write it as, -> (20), 10, 22, 2, 40, 6, 38
                     -> (20-10)+(10-22)+(22-2)+(2-40)+(40-6)+(6-38)
                     ->  10+12+20+38+34+32
                     -> 146.
So seek time is = 146*6
                  876 ms.


Big-O notation for lower bound instead of Big-Omega In the Wikipedia's Binary search tree, one can read

Traversal requires $O(n)$ time, since it must visit every node.

Since it is question of a lower bound, shouldn't we write

Traversal requires $\Omega$(n) time, since it must visit every node.

Is the $O(n)$ statement here even correct?

If you consider the problem Tree traversal, then the correct answer is indeed:

Traversal requires $\Omega$(n) time, since it must visit every node.

We are here talking about requirement and lower bound, as in "what is necessary".
If you want to talk about common algorithms for tree traversal, then it is true that they also have a complexity $O(n)$, which means that it is an upper bound in "what we can do".
However, since your question, the wikipedia page was modified and the current sentence does not really make any sense (basically "Tree traversal is $O(n)$. Since it is also $O(n)$, it is optimal.").


Connecting The Informal and Formal Definitions of Decidable With Each Other From pg. 64 of Lambda Calculus and Combinators, the author formally and informally defines the notion of "decidability":

1 Formal Definition

  Definition 5.4 A pair of sets $\mathcal{A}$, $\mathcal{B}$ of natural numbers is called recursively separable iff there is a
  recursive total function $\phi$ whose only output-values are $0$ and
  $1$, such that

  $$ n \in \mathcal{A} \implies \phi(n) = 0, $$ $$ n \in \mathcal{B} \implies \phi(n) = 1 $$

  A pair of sets of terms is called recursively separable iff the
  corresponding sets of Godel numbers are recursively separable. A set
  $\mathcal{A}$ (of numbers or terms) is called recursive or
  decidable iff $\mathcal{A}$ and its complement are recursively separable.

2 Informal Definition

Shortly thereafter, the author states

  Informally speaking, a pair $\mathcal{A}$, $\mathcal{B}$ is
  recursively separable iff $\mathcal{A} \cap \mathcal{B}$ is empty and
  there is an algorithm which decides whether a number or term is in
  $\mathcal{A}$ or in $\mathcal{B}$.

3 How to Connect These Definitions

Why is the existence of a recursive total function $\phi$ satisfying the properties of (1) logically equivalent to the notion that "there is an algorithm which decides whether a number or term is in the disjoint $\mathcal{A}$ or $\mathcal{B}$"?

The author himself wrote informally speaking, the second is not a definition in the same sense of the first.

Intuitively, since a recursive function is defined by either $\mu$-recursion or composition of simpler functions, the existence of a total recursive function provides an effective method to compute the answer.

The informal part of the above reasoning is that we didn't really define what we mean by "effective method".

The usual formalization involves the definition of a computational model, which provides a rigorous framework for the notion of algorithm. Once you have done that, you can prove the equivalence in a mathematical sense.


Expressing complexity class P using first-order logic with LFP Can anyone show how to express complexity class P using first-order logic with LFP? (descriptive complexity)

In Neil Immerman's Descriptive Complexity the proof that P = FO + LFP uses alternating graphs: an alternating graph is a directed graph $G= \{ V, E, A, s, t\}$ where $A$ is the set of nodes marked as universal ($V \setminus A$ are existential). The accessibility relation is defined in this way:

$P_a^G(x,x)$
if $x \in V \setminus A$  $\land P_a^G(z,y)$ holds for some edge $(x,z)$ then $P_a^G(x,y)$
if $x \in A$ $\land \; outdeg(x)>0 \land P_a^G(z,y)$ holds for all edges $(x,z)$ then $P_a^G(x,y)$

The reachability problem $REACH_a$ is defined as $\{G | P_a^G(s,t)\}$ and is complete for P via first-order reductions.

Using LFP one can give a FO + LFP definition of $REACH_a$ (i.e. $REACH_a \subseteq FO+LFP$):

$$\varphi_{as}(P,x,y)\equiv  x = y \lor [\exists z(E(x,z)\land P(z,y)) \land (A(x)\rightarrow \forall z(E(x,z)\rightarrow P(z,y)))]$$

and $REACH_a = (LFP_{P_{xy}\varphi_{ap}})(s,t)$

We have $P \subseteq REACH_a \subseteq FO+LFP$, the inverse $FO+LFP \subseteq P$ follows from the fact that a FO query can be evaluated in $L$ and at most $n^k$ evaluations of $\varphi(R,x_1,...,x_k)$ are needed for $(LFP_{R \varphi})$ ($R$ is a k-ary relation).

For further details you can see the proof on Immerman's book.


Size of the universe for van Emde Boas Trees In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size  $u$  is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde Boas trees. Why choose $u$ to be of this specific form ?

This assumption makes the analysis easier. If the universe $\mathcal{U}$ is of size $2^{2^k}$ then every element in $\mathcal{U}$ can be represented by $2^k$ bits. Roughly speaking, when executing one of the vEB-tree operations you halve the "relevant bits" in every level of the recursion. So when you start with $2^k$ bits, then the recursion depth is $k$.

If your universe has a size not of the form $2^{2^k}$, then you have to use floor/ceiling in the analysis.


Is there a way to calculate the number of all the languages over an alphabet? Let $\Sigma = \{ a,b,c \}$ be an alphabet.

How should I calculate the number of Languages over $\Sigma$?

It's uncountable infinite.

There are the languages $\{ a^0 \}$,  $\{ a^1 \}$,  $\{ a^2 \}$,  $\{ a^3 \}$ etc., which is already countable infinite.

But the powerset of the integers is uncountable infinite. So for every set S of integers, take the language $\{ a^k: k \in S \}$ and you have an uncountable infinite set.

(The number of languages that can be defined by any algorithm is only countable infinite, so most of these uncountable many languages cannot be described in any way).


Optimizing the problem I have a recurrence relation:

$$f(a,b) = \begin{cases}
  1 & (a,b) = (0, 0)\\
  1 & (a,b) = (a, 0)\\
  0 & (a,b) = (0, b)\\
  2a & (a,b) = (a,1)\\
  f(a-1,b) + f(a-2, b-1) + f(a-1,b-1) & \mathrm{otherwise}
\end{cases}$$

Where the constraints: $1 \leq a \leq 10^9$ and $1 \leq b \leq 1000$. I tried using recursion to find out the values but the time complexity was very high. I also tried using a dp table but that has a high time complexity as well. Also, since a can be upto $10^9$, it isn't possible to create such a large table as the space complexity will be too high and I'll get a runtime error. I want to optimize this code so that its time complexity gets reduced. Can anyone help me to achieve this? I mean which data structure to use or what algorithm should I implement to achieve this?

you can go to Dynamic programming. To achieve benefits do this you need overlapping recursion.

Easiest way yo program it, using a Map library as Memoization. Store any value calculated. Check any value from the map before calculation. This will eliminate the recalculations.

The simple case is always the Fibonacci Sequence, in which given $n$ find the $F(n) = F(n-1) + F(n-2)$.

You could see the overlappings easily. Make an array to store $F_i$ once found to prevent refound, Top-Down.

Buttom up; Start from the lowest of the recursion to reach the target.

For your case you need a table of size $10^9 \times 1000$ to fill. If the size is big, you may reuse some rows.


Definition of integers needs explaining Zero and one are defined by the successor function.

$$
\begin{align*}
&0 ≡ λsz.z \\
&1 ≡ λsz.s(z)
\end{align*}
$$

But why? $λsz.z$ is irreducible to a value. If I call this function on some value, I get back $z$, which is merely a variable in itself. If I call the function on two values, I get back the second value, which is not necessarily zero.

And yet we're just assigning the function the value $0$? Why? Why not assign zero to say $λs.(λz.xyt)$. This seems arbitrary.

This is from the arithmetic section of:
http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf

The natural numbers don't exist natively in the world of lambda calculus, and so if we want to use them, we have to define them somehow. You are describing the Church numerals, one possible definition which supports arithmetic. Church defines $n$ to be the function $(s,z) \mapsto s^{(n)}(z)$ that maps a pair $(s,z)$ into an $n$-fold application of $s$ to $z$. In particular, when $n = 0$ we get $(s,z) \mapsto z$.

Why this definition and not any other one? No reason. It is just a common definition, but you can use any other definition you like, or even come up with a new one. This particular definition supports arithmetic – you can define addition, multiplication and so on. See Wikipedia for the details.


Use DFA minimization on LR(1) states I have recently started reading more about context-free parsing techniques, in particular LR parsing.

As I have read, LR state transition graph (or table(s)) used for finding handles in sentential form is created by first constructing NFA from grammar rules (with included position in the rule - dot and possibly lookahead terminal) and then by converting the NFA to DFA with powerset/subset algorithm to remove non-determinism.

LR(1) state transition graph is usually an order of magnitude larger than LR(0)/SLR(1)/LALR(1).

Is it worthy or even practically possible to use DFA minimization (either Hopcroft or Moore or Brzozowski) on LR(1) state transition graph to get a minimal LR(1) graph?
I haven't found any literature mentioning this.

Also, is there an algorithm to convert NFA directly to minimal DFA? Perhaps by constructing NFA state subsets in some particular order?

The following paper uses DFA minimisation for a minimal LR(1) parser: https://www.researchgate.net/publication/258746690_An_LR_parser_with_less_states


Does my simple, static hash table have O(1) worst case lookup? Will the following simple hash table construction algorithm be able to construct a
static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the problems, and is there a simple solution?
Construction
Let's assume we have a static set of $n$ keys.
We also have a fully random universal hash function $h_i(x)$ (let's say we use SHA-2 with $i$ as the IV).
Now we try to partition the set of keys into $m$ buckets, where $m = \lceil n/100 \rceil$.
First we try with $i$ 0. If one bucket has more than 1000 entries
(this is possible, but extremely unlikely, much less likely than to get a SHA-2 hash collision), start from scratch, that is re-build the hash table but use a different hash function, that is $h_1(x)$. Do this in a loop until we find an index $i$ that works.
Now the largest bucket has less than 1000 entries.
Each bucket is stored as a list, sorted by hash value.
The index $i$ is also stored.
Evaluation
For the static hash table constructed above, with the stored index $i$, calculate $h_i(x)$. Calculate the bucket, and in this bucket, do a binary search. I believe (hope) that this is an O(1) operation, because there are at most 1000 entries in this bucket.
Closely related: (When) is hash table lookup O(1)?. But I have a static set, and I have a fully random universal hash function. I know about FKS hashing, but I can't use it in my case, because it would require too much memory, and I would like to have a simpler algorithm. I understand my algorithm is terribly inefficient, but I'm mostly interested in a guaranteed $O(1)$ worst case access time.

Yes, your access time is $\mathcal{O}(1)$. Your construction time is a bit more complicated. Let $P(k)$ be the propability, that a set structure containing $k$ elements has a bucket with more than 1000 entries. If there is an overflow after the initial construction in $\mathcal{O}(k)$, everything is rearranged with costs of $\mathcal{O}(k)$. But this might clash again. Thus you get expected costs of $\mathcal{O}(k) + \sum \limits^\infty_{j=1}P(k)^j\mathcal{O}(k)=\mathcal{O}\left(\frac{k}{1-P(k)}\right)$.


Reconstructing Graphs from Degree Distribution Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph can be constructed and any one example if multiple graphs can be constructed.

If the degree distribution is given as a list of degree, then you can do the following, given $n$ nodes with degrees $d_1, ... ,d_n$:

Create a complete graph $K_n$ on $n$-vertices. For each vertex $v_i$ in $K_n$, split it into $d_i$ copies. Split here means, create a number of copies with edges to every vertex $v_i$ has an edge to, but no edges to other copies of $v_i$. If $d_i = 0$ then simply remove the vertex. In the new graph, call these vertices $v_{ij}$ for $1 \leq j \leq d_i$.

Once you are done, you have a very dense graph on $N = d_1 + ... + d_n$ vertices; call this graph $H$. Pick your favorite algorithm for maximum matching (since the graph is so dense, you should probably use one of the fast matrix-multiplication based algorithms) and run it on $H$. This will return a matching $M$. If the matching is not perfect (i.e. if it does not cover every vertexes) then your degree distribution was impossible; so return no.

If you have a perfect matching $M$, then remove all edges not in $M$ from $H$, and then for every $1 \leq i \leq n$ merge the $d_i$ many vertices $v_{i1}, ... , v_{id_i}$ into one vertex $u_i$. Merging two vertices means combining them into one, such that the resulting vertex has edges to every vertex at least one of the original had an edge to. Call the resulting graph $G$; it has the desired degree distribution.

The resulting runtime is $O(N^\omega)$ where $\omega$ is the constant for the fastest matrix-multiplication algorithm (which at the time of writing is about $2.373$). In terms of number of vertices in the resulting graph, in the worst case of degree distribution being dense, we have $O(n^{2\omega})$.


Evolutionary algorithm in stochastic environment Consider the following model problem:

I want to use an evolutionary algorithm to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not when. Once a particle is placed, it is part of the dynamics, which is stochastic, i.e. whether certain particles interact is modeled by a random variable. A mutation of the evolutionary algorithm corresponds to slightly changing the time when the particle is introduced in the system.

I have now two choices:

1) I let the stochastic dynamics evolve while the evolutionary algorithm is optimizing, i.e. after every mutation I draw a new interaction environment from the distribution. That means, the algorithm is evaluating every situation with a different environment (drawn from one fixed distribution).

2) I draw an interaction pattern for every particle apriori to have one fixed environment (we assume they can be drawn independently). Then I let the algorithm optimize my problem in that deterministic environment. I do that for several environments and take some statistic over the solution.

Does someone have experience with those two approaches and can tell me their advantages and disadvantages from a practical point of view?

I'd go with option 1.

A dynamic training environment is a good way to produce a robust solution (after all natural evolution, which is the inspiration for EA, is always dynamic).

Moreover "take some statistics over the solutions" can be a very hard problem (you shouldn't take for granted that there is a meaningful way to combine / extract information from multiple solutions).

Indeed there are some important aspects to consider:

population diversity have to be carefully monitored. Often EAs are designed for a static optimization problem and the quick loss of diversity can be a problem in a dynamic environment;
it seems that you have a system in which environmental change occurs rapidly. Try to slow down the environment: do not draw a new interaction environment after every mutation but wait for a sequence of mutations (in Genetic Programming this is the approach taken in Dynamic Training Subset Selection{1}). I'm not sure this will work, but it's worth a try;
supply the EA with an explicit memory (sometimes called Valhalla) so that the EA can recall useful information from past generations (e.g {5}).

This is small compendium of interesting papers.

Looking for further resources, consider that there are many kinds of dynamic environments: e.g. noisy fitness functions, environments with optimum changing over time... they are somewhat different problems but share many interesting techniques.

Also it seems to me that you're describing a so called co-adaptive environment (each individual's evolution drives other individuals evolution and individuals change their fitness landscape evermore). You may find interesting techniques in papers about co-evolution.

Dynamic Training Subset Selection for Supervised Learning in Genetic Programming by Chris Gathercole, Peter Ross (1994).
Genetic Algorithm for Adaptation to Dynamic Environments - A survey by Naoki Mori, Hajime Kita (2000).
Evolutionary Dynamic Optimization - A survey of the state of the art by Juergen Branke, Trung Thanh Nguyen, Shengxiang Yang (2012).
An evolutionary approach for time dependant optimization by Philippe Collard, Cathy Escazut, Alessio Gaspar (1997).
"Memory enhanced evolutionary algorithms for changing optimization problems" by Juergen Branke (1999).
Evolutionary Algorithms and Dynamic Optimization Problems by Karsten Weicker (2003).


How to show ExactOneSAT is NP-Complete? $\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$

I am trying to reduce 3SAT to this problem but can't find a way. I tried taking a small example $\phi=(x_1 \vee x_2) \wedge (\overline{x_1} \vee x_2 ) $. In this example the formula can only be satisfied only when both $x_1,x_2$ are True. How do I reduce such a case of 3SAT to ExactOneSAT ?
This is an exercise from Sanjeev Arora and Barak Boaz : A modern approach to complexity, but not a homework exercise.

We can reduce 3SAT to ExactOneSAT (3SAT $\leq_P$ ExactOneSAT) as follows. Replace each clause $C_m$ by $(z_{m,1} \lor z_{m,2} \lor z_{m,3})$ and ensure that if $C_m$ is, say, $(v_i \lor \overline{v_j} \lor v_k)$ then  $(\neg v_i \Rightarrow \neg z_{m,1})$, $(\neg \overline{v_j} \Rightarrow \neg z_{m,2})$ and $(\neg v_k \Rightarrow \neg z_{m,3})$. Thus, for example, if $v_i$ is true then $z_{m,1}$ can be true or false, but if $v_i$ is false then $z_{m,1}$ must be false.

Thus replace  $(X_{m}^1 \lor X_{m}^2 \lor X_{m}^3)$  in clause $C_m$ by
$$(z_{m,1} \lor z_{m,2} \lor z_{m,3}) \land (\neg X_{m}^1 \lor y_{m,1} \lor z_{m,1}) \land ( \neg X_{m}^2 \lor y_{m,2} \lor z_{m,2}) \land ( \neg X_{m}^3 \lor  y_{m,3} \lor z_{m,3})$$
where $X^1_m, X^2_m, X^3_m$ are the three literals in the clause $C_m$. Note that $X$'s are literals in the clauses and can have negations, whereas $y$'s and $z$'s are variables.

If $\phi'$ is the modified boolean CNF, then this will give us $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT. This along with the fact that above transformation is polynomial-time gives us a proof of NP-completeness.

Let us see how $\phi \in 3SAT \Rightarrow \phi' \in$ ExactOneSAT.

Assume we have a satisfying assignment for $\phi$.

For example, say $X_m^1$ is true and $X_m^2$  and $X_m^3$ are  false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = False, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say $X_m^1$ and $X_m^2$ are true and $X_m^3$ is false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say all $X_m^1$, $X_m^2$ and $X_m^3$ are true. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = True, $z_{m,3}$ = False

So we can see that we can find a satisfying assignment for $\phi'$ where only one literal is true in every clause.

Let us now see how $\phi' \in$ ExactOneSAT $\Rightarrow \phi \in $ 3SAT

Assume we have a satisfying assignment for $\phi'$ where exactly one literal is true in every clause.

Let us say $z_{m,1}$ is true and $z_{m,2}$ and $z_{m,3}$ are false. Then definitely $X_m^1$ in the second clause should be true, implying that same assignment satisfies $C_m$.

Thus we have $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT.

We have actually prove ExactOne3SAT is NP-complete by this because every clause has 3 literals.


Relation between Type Assignment system (TA) and Hindley-Milner system Recently I started my studies in type theory/type systems and Lambda Calculus.

I have already read about Simple Typed Lambda Calculus in Church and Curry style. The last one is also known as Type Assignment system (TA).

I'm thinking about the relations between TA and Hindley-Milner (HM), the system in languages like ML and Haskell.

The book Lambda-Calculus and Combinators: An Introduction (Hindley) says that TA
is polymorphic (pag. 119). Is that the same sense of polymorphism in systems like HM and System-F?

TA is said to have the strong normalisation property, so is not turing complete. Languages that use HM system are turing complete, Haskell for example. So must be the case that HM system allows terms like the infinity loop $\Omega$ to receive a type. Is that correct or I'm missing something?

Any way, I would like to know the relation between TA and HM.

System F and its subsystem HM have a type former for universal quantification:

$$
   \tau \quad::=\quad \forall x.\tau \ |\ ...
$$

which the system in Hindley/Seldin doesn't have. That is the key difference.

Now System F doesn't have decidable type-inference, and HM is a way of combining type-inference with reasonably expressive parametric polymorphism. HM achieves this by allowing only outermost universal quantification, i.e. all types are of the form

$$
   \forall x_1 \forall x_2 ... \forall x_n.\tau
$$

where $\tau$ is quantifier free (and $n \geq 0$). HM gives a rule system that ensures that only programs that can be typed in this way are admissible. This is achieved by "let-polymorphism". The system in Hindley/Seldin doesn't do any of that. Later, in Chapter 13, Hindley/Seldin introduce pure type systems (PTS), of which System F is a special case.  I'm not sure if HM can be expressed as a PTS.

The question of strong normalisation is orthogonal. System F and HM are strongly normalising, but that can easily be remedied by introducing fix-point combinators or similar. The paper  Principal type-schemes for functional programs  by L. Damas and R. Milner even states this:
"For example, recursion is omitted since it can be introduced by simply adding
    the polymorphic fixed-point operator ..." The introduction of fixpoints, making the system Turing complete, poses no issues from the point of view of type inference.


A variant of job assignment (scheduling) problem with variable time span The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take anything from 5 mins to 10 mins. The list of jobs and their duration interval is given to the scheduler and the aim is to minimize the time all jobs would be finished.
In interval scheduling, the job start and end time is given and the length is fixed. Here, the job can start and end anytime (should be done in whole though) but its duration (length) is not exactly known.

I searched the literature for this problem but couldn't find it. Is there any keywords I can use or any reference for this problem? Is it well-defined?

I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf.  I hope it helps.

I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times.  An algorithm for exponentially distributed times might be very different than an algorithm for a uniform distribution.

I think you will also need to trade off expected completion time vs. variance.  With known completion times a decent approximation algorithm is Coffman's list scheduling algorithm: sort the jobs by length (longest to shortest) and then schedule greedily (next job starts as soon as a machine is free.)  With uniform completion times you might try sorting by best-case completion times, expected completion times or worst-case completion times, and you would be getting different answers.


Exit a deadlock cycle Suppose i have the following resource allocation graph with a deadlock cycle, i see why it is a deadlock cycle, what i don't get is how to recover from this cycle

i'm thinking about aborting a process, any process here will lead to non-deadlock situation, but doesn't that cause the other process to not execute and hence the program won't execute as we're expecting it to be, i think this is a correct answer, but is there another way to do such that all processes will eventually run ?

You don’t exit a deadlock cycle. Once you are in a deadlock situation, you lost. You do your best to avoid deadlocks.

With server software, you may be able to have a process that watches other processes and kills them if they are stuck due to a deadlock. Doing this correctly and make your software continue to run correctly is extremely difficult. It’s so difficult that i wouldn’t even try. In addition it is an absolute pain to test (and you don’t want software that isn’t tested). For normal software running in anything from workstation to mobile phone, it’s just not done. Remember that you have two tasks that are trying to do something and one or both of them have to be killed, that is hard to recover from.

What you do in practice: 1. Instead of locking a mutex you check if it is lockable which avoids deadlocks. 2. You add code that detects situations where a deadlock is possible. And if you find a possible deadlock you fix your code. 3. Write sensible code in the first place.


How to perform AND on binary "recursive repeating sequences"? Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related to how many times this sequence is repeated, or can contain a bit either 0 or 1. Following image describes it visually:

On this image repetition is denoted by lower index number nearby ending bracket. The bits need to be expanded are denoted by regular size font.
Each sequence can produce binary sequence (sequence of bits), when we expand it.
The questions are:

Can we create a algorithm, that performs AND on two recursive repeating sequences, without expanding both of them? (The algorithm should produce third recursive repeating sequence, such when we expand it, it is AND on both expanded input sequences).
If the answer for first question is true, how such algorithm will look (for example in pseudo code) ?

Note: In practice, the numbers responsible for repetition may be very large, so expansion of whole sequence is not practical in terms of computation - but if algorithm will need to do it partially, it may be accepted.

Let $A,B$ be the two recursive repeating sequences, where $|A| = |B|$. If $|A| = |B| = 1$ then there is nothing to do. Otherwise, either $A$ is of the form $A_1A_2$ or of the form $(A')_k$, where $k > 1$. In the second case, we can write $A = A' (A')_{k-1}$, which is also of the form $A_1A_2$. Thus it suffices to explain how to compute $A_1 A_2 \land B$ (here $\land$ means AND). We will show that we can find two recursive repeating sequences $B_1B_2$ such that $B=B_1B_2$ and $|A_1|=|B_1|$, $|A_2|=|B_2|$. We can then compute $A \land B = (A_1 \land B_1) (A_2 \land B_2)$.
Given a recursive repeating sequence $B$ and a number $\ell$, we have to break $B$ into $B_1B_2$, where $|B_1| = \ell$. We consider two cases:

$B = C_1 C_2 \dots C_r$. We can find $t$ such that $|C_1 C_2 \dots C_t| \leq \ell < |C_1 C_2 \dots C_t| + |C_{t+1}|$. If $|C_1 C_2 \dots C_t| = \ell$ then we can take $B_1 = C_1 C_2 \dots C_t$ and $B_2 = C_{t+1} \dots C_r$. Otherwise, we break $C_{t+1}$ into two parts $D_1D_2$, where $|D_1| = \ell - |C_1 C_2 \dots C_t|$, and take $B_1 = C_1 C_2 \dots C_t D_1$ and $B_2 = D_2 C_{t+2} \dots C_r$.

$B = (C)_r$. We treat this as an explicit description of the preceding case, where $C_1 = \cdots = C_r = C$. We use division with remainder to find $t$ efficiently. In the easy case we take $B_1 = (C)_t$ and $B_2 = (C)_{r-t}$, and in the complicated case we take $B_1 = (C)_t D_1$ and $B_2 = D_2 (C)_{r-t-1}$.


How can I identify that a restricted variant of Boolean SAT remains hard or not? While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I though of it) and searched, but could not find anything useful.

Consider this variant:

  Suppose $f$ is a boolean function in $n$ boolean variables, but with this extra property, that $f$ is increasing. I have thought of $n$ boolean variables, $X_1, \ldots, x_n$ as representation of subsets of a set with $n$ elements, and if some  subset like $X$ satisfies $f$, then all $Y$ s.t. $X \subseteq Y$ satisfy $f$, too. What I want is finding the collection of all minimal $X$ where $f$ satisfies each of them, but not any $Z$ where $Z \subsetneq X$?

Is this problem still hard?

If I consider the $x_1, \ldots, x_n$ as a number, then increasing property of $f$ helps solving it in polynomial time, just a binary search suffices! So, I made it a little bit harder.

Any help, even offers of search terms is appreciated.

Your problem cannot be solved in polynomial time, for a boring reason: the size of the output might be exponential in the time of the input.  Therefore, there is no hope for a polynomial-time algorithm.

For instance, consider the boolean function $f:\{0,1\}^n \to \{0,1\}$ that outputs $1$ if its input vector has at least $n/2$ ones (i.e., its Hamming weight is at least $n/2$), and $0$ otherwise.  This function can be represented by a polynomial-size monotone formula.  However, there are exponentially many minimal $x$ such that $f(x)=1$.  In particular, each $x$ of Hamming weight $n/2$ is such a minimal input, and there are ${n \choose n/2}  \approx 2^n/\sqrt{n}$ such inputs.

So, there's no hope.

As Andrej Bauer points out, a related problem (testing whether there exists an input of Hamming weight at most $k$ that causes the boolean function to output $1$) is also NP-complete; see Prove NP-completeness of deciding satisfiability of monotone boolean formula.


Finding the height of a d-ary heap I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:

The parent of a node $i$ is given by: $\left\lfloor\frac{i+1}{d}\right\rfloor$

The $d$ children of a parent at node $i$ are given by: $di-d+1, di-d+2,\ldots di+1$

The height of a heap (which is slightly different than the height of a binary search tree) is a longest path from the root to a leaf. A longest path will always be from the last node in the heap to the root, but how do I calculate this longest path?

My first Idea is to setup a recurrence relation for the height of the tree:

\begin{equation}
h(1) = 0\\
h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1
\end{equation}

This seems overly-complicated and I feel like the answer is much more simple. Is there a better way to find the height of a $d-$ary heap?

A path from the last node to the leaf would always be a longest path. This is because the last node is always at the lowest level in the heap. Now, assume the root is at level $0$. Then the number of nodes at a completely filled level $i$ would be $d^i$.

Let level $k$ be the last completely filled level in the heap. So the number of nodes upto (and including) level $k$ is: $$\sum\limits_{i = 0}^{k}d^i = \frac{d^{k+1} - 1}{d - 1}$$

Now, the last node - the $n^{th}$ node - can either be the last node at level $k$, or it can be in an incomplete level $k+1$. Taking care of these two cases, it can be seen that:
$$\frac{d^{k+1} - 1}{d - 1} \le n < \frac{d^{k+2} - 1}{d - 1}$$
$$\Rightarrow k\le \log_d(n(d-1) + 1) - 1 < k+1$$

Now, equality is only if the last node is the last leaf of level $k$, which also has distance $k$ from the root. If not, that is if there is a level $k+1$, then the $\log$ term would not be an integer, and applying the ceiling operator would give the right height of $k+1$. Thus, if the last element of the array is at position $n$, the height of the heap is:
$$h = \lceil \log_d(nd - n + 1) \rceil - 1$$
You can change the base of the logarithm using the change of base formula. Note that this is the same method that Yuval gives in his answer.


From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm? I am reading one of Guido van Rossum's essays on optimization in Python.

We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward algorithm.

def f3(list):
    string = ""
    for character in map(chr, list):
        string = string + character
    return string

Guido claims that the following algorithm avoids the quadratic behavior in the string concatenation.

def f5(list):
    string = ""
    for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
        s = ""
        for character in map(chr, list[i:i+16]):
            s = s + character
        string = string + s
    return string

How does this actually help and what is the significance of the value 16 in f5?

f5 does not actually turn out to be faster, but I want the intuition that went into trying this strategy of optimization.

Note: we can assume that we are working with a list of length exactly 256.

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:

  Read the list in chunks of $k$, convert them to strings, and sum the chunks.

Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. Adding the chunks takes time $\Theta(k+2k+\cdots+n) = \Theta(k(1+2+\cdots+n/k)) = \Theta(k(n/k)^2) = \Theta(n^2/k)$. In total, we get a complexity of $\Theta(n(k+n/k))$. The optimal choice of $k$ is $\sqrt{n}$, and this gives a complexity of $\Theta(n^{3/2})$. In contrast, the trivial algorithm has $k = 1$ and so complexity $\Theta(n^2)$.

More generally, you can consider $d$ levels of recursion. Let $f_d(n)$ denote the optimal complexity of such a scheme, measuring just the merging steps. Clearly $f_1(n) \approx n^2/2$. Given an algorithm with $d$ levels, we can construct a $d+1$-level algorithm which cuts the input into chunks of length $k$, runs the $d$-level algorithm on each of them, and concatenates the result. This takes time roughly $(n/k)f_d(k) + n^2/2k$. For example,
$$
\begin{align*}
2f_2(n) &\approx \max_k nk + n^2/k \approx 2n^{3/2} & (k=\sqrt{n}), \\
2f_3(n) &\approx \max_k 2nk^{1/2} + n^2/k \approx 3n^{4/3} & (k=n^{2/3}), \\
2f_4(n) &\approx \max_k 3nk^{1/3} + n^2/k \approx 4n^{5/4} & (k=n^{3/4}).
\end{align*}
$$
We get that $2f_d(n) \approx dn^{(d+1)/d}$. Calculus shows that the best choice of $d$ is $d = \log n$, in which case we obtain $2f_{\log n}(n) = \Theta(n\log n)$. However, this scheme is not necessarily achievable.

If we choose a branching factor of 2 then we get an algorithm whose running time is $\Theta(n\log n)$ which resembles merge sort. In fact, the sorting lower bound gives a lower bound of $\Omega(n\log n)$ on any such merging procedure.

We can also prove the lower bound directly. For a sequence $\sigma_1,\ldots,\sigma_m$ of chunk lengths summing to $n$, define its potential by
$$
\Phi(\vec\sigma) = nH(X_{\vec\sigma}), \text{ where } \Pr[X_{\vec\sigma} = i] = \frac{\sigma_i}{n}.
$$
Here $H$ is the entropy function.

The potential function starts at $\Phi(1,\ldots,1) = n\log n$ and ends up at $\Phi(n) = 0$. Suppose that $\vec\tau$ is obtained from $\vec\sigma$ by merging $\sigma_i$ and $\sigma_j$ to a new chunk $\tau_k$. We can sample $X_{\vec\sigma}$ by first sampling $X_{\vec\tau}$, and if the result is $k$, sample according to the marginal distributions $\frac{\sigma_i}{\sigma_i+\sigma_j},\frac{\sigma_j}{\sigma_i+\sigma_j}$. Calculation shows that
$$
\begin{align*}
\Phi(\vec\sigma) = nH(\vec\sigma) &= nH(\vec\tau) + n\Pr[X_{\vec\tau}=k] h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + (\sigma_i+\sigma_j) h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + O(\sigma_i+\sigma_j).
\end{align*}
$$
Here $h$ is the binary entropy function.

This shows that the potential difference is a lower bound on the running time. Since the overall potential difference is $n\log n$, we obtain a lower bound of $\Omega(n\log n)$. Furthermore, the calculation shows that it's best to always merge chunks of identical size.


Pumping Lemma for Regular Language seems to Fail Let $L = \{ab^ncd \mid n \geq 0\}$.  If we take $p = 5$ and $w = abbcd$ and write
$w_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w_2 = abbccd$ which is not in $L$.  We conclude that $L$ is not regular but it obviously is!

What am I doing wrong?

The pumping lemma says that there exists a decomposition of $w$ to $xyz$ such that $y$ can be pumped.

It doesn't say that for all decompositions of $w$ to $xyz$, $y$ can be pumped.

In your example, a possible decomposition is:

$x=a$

$y=bb$

$z=cd$


Can three regular languages be concatenated? I can't seem to find anything about this and I wonder if I'm asking a silly question.

  If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated?

If yes, would you concatenate the first two and concatenate the result to the third one or would you concatenate it as $\{ace, ade, acf, adf, bce, \ldots\}$?
And what if one of the languages only contained the empty word $ε$?

Concatenation is associative:
$$
(L_1L_2)L_3 = L_1(L_2L_3) = \{w_1w_2w_3 : w_1 \in L_1, w_2 \in L_2, w_3 \in L_3\}.
$$
We denote the common value by $L_1L_2L_3$.

A class of languages closed under concatenation of two languages is also closed under concatenation of three or more languages, as a simple induction shows.

The "zero" element for concatenation is the empty language $\emptyset$, which satisfies $L\emptyset = \emptyset L = \emptyset$. The "one" element for concatenation is the language consisting of only the empty word $\{\epsilon\}$, which satisfies $L\{\epsilon\} = \{\epsilon\}L = L$.