Proving intuitionistic tautologies in Agda I am to use Agda to prove some intuitionistic tautologies. One of them is the so called Weak Peirce's Law
$$
((((A \rightarrow B) \rightarrow A) \rightarrow A) \rightarrow B) \rightarrow B
$$
I understand that there is an "equivalence" between intuitionistic tautologies and programs and their types, that is if I manage to write a function of this type, it works like a proof of this tautology.
The type of the function is wp : {A B : Set} ((((A -> B) -> A) -> A) -> B) -> B.
My question is - how do I even approach this thing? I managed to prove some other laws of intuitionistic logic, but with this one I'm kind of stuck. I imagine that somehow I'd like to get the first A -> B function and apply A to it, but how can I do that if all I get is the whole function f of type ((((A -> B) -> A) -> A) -> B)? Should I use $\lambda$'s for this?
Additional question: What does this Law even mean? There are so many implications that I can't even parse it...

For examples like this, they can often by easily written interactively just looking for the only thing possible to do at each stage. So for instance, you start with:
wp e = ?

and the only option is to apply e, at which point Agda will tell you you need to provide $((A → B) → A) → A$, so you introduce a lambda:
wp e = e (λ k -> ?)

Now you need to give an A, which is the result type of k, so you apply k and abstract again:
wp e = e (λ k -> k (λ x -> ?))

Now you need to give a B. The only thing that results in a B is e, so you apply it again. However, now your situation is different, because x is in scope. And presumably you don't want to follow the same pattern as you did before, so you can write:
wp e = e λ k → k (λ x → e (λ _ -> x))

In this case, the process is constrained enough that the auto-solver comes up with this solution.
As for what the type means, Peirce's law is similar to double-negation elimination with the $⊥$ replaced with $B$: $$((A → B) → B) → A$$ Peirce's law follows from the above type, because you can massage an $(A → B) → A$ into an $(A → B) → B$ by duplicating the function argument.
So, your overall type can be read as similar to:
$$¬¬(¬¬A → A)$$
Which fits the theme of double-negated classical (propositional) theorems being intuitionistic theorems.


All paths of less than a given length in a directed graph between couple of nodes Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, due to the possibles cycles.

This question is slightly different, or at least I think.

INPUT:  Be G a directed graph. G can have cycles and also selfconnected nodes. Let A(G) be the adjacency matrix of G (with a 1 in Gi,j if there's a link going from i to j and a 0 otherwise). Define T and B two subset of nodes of G, possibly with void intersection.

OUTCOME: A list of all paths of length at most k going from one node in T to one node in B. Paths can contain multiple time the same edges, as long as they go from the source node to the target node in strictly less than k+1 steps.

QUESTION: I would like to know which algorithm perform best in this task. I'm trying to develop a possible answer based on the fact that the n-th power of the adjacency matrix, if computed symbolically (with a different variable for each entry instead of a 1), keep traks of all this paths (and it reduces to the counting of paths if computed numerically with 1 in the entries). But I really don't know if this is the fastest way of doing the task (probably not).

CAVEAT: I'm not asking for the counting problem, nor for the shortest paths, the length of a path is defined as the number of edges used (counting the repetition). I'm using R, but if you prefer think about it in any other language! I'm really sorry if the question was already posed and solved. Thank you for the kind help!

additional info: I tried a matrix power series approach (A^3 gives all the 3 long path, ...) and dfs / bfs. I think the latter two are far from optimality as they don' take into account that I'm working on sets of sources and targets, and hence do a lot of redundant work...

If I am not missing something about your question, you can apply the standard trick for reducing the question about multiple sources and destinations to the case of single source and single destination:

  Add two new nodes $s$ and $t$,
  Connect $s$ to all sources,
  Connect all destinations to $t$.

After this reduction we are in the standard question setting
with two extra vertices $s$ and $t$ and
we want to find walks from $s$ to $t$ of length at most $k+2$.


In information theory, why is the entropy measured in units of bits? In information theory, we have the quantity "information".

Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{1}{2},\frac{1}{4},\frac{1}{4}\}}$. Then, information, $h$, is measured as $h(x) = -\log_{2}P(x)$.

So now we can say: $$h(a) = -\log_2 \bigg(\frac{1}{2}\bigg) = 1 \text{ bit}$$ $$h(b) = -\log_2 \bigg(\frac{1}{4}\bigg) = 2 \text{ bits}$$.

My question is, why does that computation result in a quantity measured in bits?

Explanations I've seen all say something along the lines of: "this quantity is measured in units of bits because of the log base 2" with no further explanation as to why. So why does taking the log (base 2) of a probability result in a quantity measured in units of bits?

Is it somehow related to the idea that if a system can be in $N$ states, then we can encode those $N$ states using $log_2 N$ bits? E.g. if a system can be in 4 states, we can encode those 4 states in binary with $log_2 4 = 2 \text{ bits}$: $00, 01, 10, 11$.

The entropy of a random variable $X$ can be described in terms of prefix-free binary encodings. Let $T(X)$ be the minimal average codeword length of a binary prefix code for $X$, and let $X^{\otimes n}$ be the random variable corresponding to $n$ independent samples of $X$. Then
$$ \lim_{n\to\infty} \frac{T(X^{\otimes n})}{n}. $$

Shannon's source coding theorem allows a similar description. An encoding scheme for a variable $X$ over an alphabet $\Sigma$ is a pair of mappings $E\colon \Sigma^n \to \{0,1\}^{\ell(n)}$ and $D\colon \{0,1\}^{\ell(n)} \to \Sigma^n$. The entropy is the infimum of $H$ such that there are encoding schemes with $\ell(n) = Hn$ such that as $n\to\infty$,
$$ \Pr_{x \sim X^{\otimes n}}[D(E(x))=x] \to 1. $$
In words, there is an encoding at rate $H$ if we can encoded $n$-tuples of samples of $\Sigma$ using $Hn$ bits in such a way that most of the time, we can decode the original sample from its encoding.

Both of these characterizations show that when encoding a large number of samples of $X$, each sample of $X$ takes $H(X)$ bits to encode.

Another characterization is the asymptotic equipartition (AEP) theorem, which states that $X^{\otimes n}$ consists, up to some small error, of roughly $2^{nH(x)}$ points whose probability is roughly $2^{-nH(x)}$.


Working out the connectives (And, Or, Not) in a Truth Table that has the outputs I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g

P | Q | Output
1 | 1 | 1
1 | 0 | 0
0 | 0 | 0
0 | 1 | 0

I need to find the logical operators and connectives (and, or, not, implies etc.) that is equivalent to the output.
Please guide me through the steps or teach me how to work out how to do this. Thanks.

Generally speaking, there is no unique boolean function $f(p, q)$ that produces your output. For your example, the function $f(p, q) = p$ would be a valid solution, as well as $f(p, q) = (p \vee q) \wedge (p \vee \neg q)$, and $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$.
You can find an equisatisfiable function to the one that produced the given output, and there are a number of approaches to do so.

A simple approach would be the enumeration of variable constellations that produce $\top$, and disjunct them. For your example that would mean first finding the constellations that produce $\top$:

$p \wedge \neg q$
$p \wedge q$

and finally producing $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$

This way you produce a function in disjunctive normal form (DNF). A similar approach works for CNF, but in both cases you end up with a fairly large function.

More complex approaches are Karnaugh Maps and the Quine McCluskey algorithm. They can produce much more concise, even minimal equisatisfiable functions.

As far as I know, most approaches focus on CNF (and sometimes DNF), i.e. use only conjunctions, disjunctions and negations, and don't nest operators any further.


Why selection sort is a stable sort algorithm? One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm.
Why selection sort is unstable and can we make a sort algorithm stable by changing its swap condition?

Just run an example. I will use colors to distinguish multiple elements with the same value and a $\mid$ to separate the unsorted part from the sorted part.
With the input
$\mid\color{blue}{2},3,\color{red}{2},1$
the first step will swap $\color{blue}{2}$ with $1$.
$1,\mid3,\color{red}{2},\color{blue}{2}$
The order of the $2$s changed. It continues
$1,\color{red}{2},\mid3,\color{blue}{2}$
$1,\color{red}{2},\color{blue}{2},\mid3$
So, the $2$s ended in a different order as they started.
To avoid this you can insert the smallest element of the unsorted part at the beginning of the unsorted part, instead of swapping it.
So, the first step would be
$1,\mid\color{blue}{2},3,\color{red}{2}$
The next step leaves it as it is.
$1,\color{blue}{2},\mid3,\color{red}{2}$
It continues with
$1,\color{blue}{2},\color{red}{2},\mid3$
To prove that this happens in general, observe that if an element with multiplicity is about to be moved, it must be the first element (from left to right) of that value appearing in the unsorted part. So, when it gets moved to the beginning of the unsorted part it continues appearing before all the elements of the same value appearing in the unsorted part and after all the elements of the same value that could already be in the sorted part.


How hard is factoring a complex number? Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as Integer factoring. Prime complex number has one as its only factor.

Does this problem reduce to integer factoring? Is it NP-hard?

If $C = \prod_i C_i$ is a prime factorization of $C$ then $N(C) = \prod_i N(C_i)$, where $N(\alpha + \beta i) = \alpha^2 + \beta^2$. Furthermore, $\pi$ is prime if either (i) $N(\pi) = 2$, (ii) $N(\pi) = 4a+1$ is prime, (iii) $N(\pi) = (4a+3)^2$ is the square of a prime. So factoring $C$ reduces to factoring $N(C)$.


generating recursive descent parser I have a grammar,

$L \to A \langle A \rangle^*$

$A \to () \mid (L)$

but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\rangle^*$ then I can create parser like

proc E begin
  T;
  while symbol='*' do
    T
  od

However in my case don't have any symbol. So how can I check symbol for while process? Or my grammar is incorrect?

You do have a symbol, "$($". A bit more generally though (if I understand the notation you're using), if you're processing an $L$ and you see anything, it must come from an $A$, if it's not an error, so you can recurse to processing an $A$.


Asymptotic complexity of $-\log(c^{1/n} - 1)$ What is the asymptotic complexity of
$$f(n) = -\log(c^{1/n} - 1)$$
for some constant $c > 1$? I conjectured $O(\log n)$ and checking WolframAlpha does give $$\lim_{n\to\infty}\frac{f(n)}{\log(n)} = 1,$$ but I haven't found a proof yet.

For $c \gt 1$ we have $c^{1/n} - 1 \sim \frac{1}{n}\ln c$, which gives
$$\lim\limits_{n\to\infty}\frac{\log(c^{1/n} - 1)}{-\log(n)} = \lim\limits_{n\to\infty}\frac{\log\ln c - \log(n)}{-\log(n)}=1$$
For proof brought approximation we can consider limit
$$\lim\limits_{x \to 0}\frac{e^x-1}{x} = \lim\limits_{x \to 0}e^x=1$$
based on   L'Hôpital, Taylor expansion etc. De facto it's derivative of exponent in point $0$.


Finding right quotient of $a^*b^*/b^*.$ I argue that right quotient of  $a^*b^*/b^*$ is $a^*$,is that true?any help or argument  to accept or reject my argument will be appreciated:)

$a^*b^* / b^* = \{ w \ | \ \exists \ x, \ x \in b^* \land wx \in a^*b^*\} = a^*b^*$. This is because $wx \in a^*b^* \text{ AND } x \in b^*$ means $w$ is of the form $a^ib^j$ for some $i,j \in \mathbb{N} \cup \{0\}$. Finish it off now.


Bounded Quantification: Full F<: intuition I'm currently looking into Chapter 26 of Types and Programming Languages and am a bit confused by the "intuition" for Full F<: (p. 395):

  A type T = ∀X<:T1.T2 describes a collection of functions from types to values, each mapping subtypes of T1 to instances of T2. If T1 is a subtype of S1, then the domain of T is smaller than that of S = ∀X<:S1.S2, so S is a stronger constraint and describes a smaller collection of polymorphic values.

Why is S a stronger constraint due to the fact that T's domain is smaller than S's?

Consider these assertions:

all the cats in my house are grey
all the cats in my town are grey

The second assertion implies the first, since any cat in my house is also in my town, so by the assertion it must be grey. In other words, "cats in my town" is a superset of "cats in my house", so the second assertion is stronger (it applies to more cats).

In the same way, the type S = ∀X<:S1.T2 is stronger than T = ∀X<:T1.T2 since S1 is a supertype of T1. A program of type S must work in all cases (types X) where a program of type T would work, and possibly even more cases.


If $A \leq B$, $B \leq \overline{A}$, and $B$ is r.e., is $A$ recursive? We know that $A ≤ B$, $B ≤ \overline{A}$ and $B$ is recursively enumerable. Is $A$ recursive or not?
I tried negating whats given, but didn't achieve much. I know that from the very first inequality that $A$ is also recursively enumerable. I assumed whether $B$ is also recursive or not to maybe get to a contradiction of some sort, but I always ended up with "sometimes recursive, sometimes not".

Notice that $A \leq B \leq \overline{A}$. Since $B$ is r.e., $A$ is r.e., hence $\overline{A}$ is co-r.e. Since $A \leq \overline{A}$, $A$ is also co-r.e. Hence $A$ is recursive.


Set cover problem with constant size subset Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?

The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the  3-dimensional matching problem.


2-SAT Problem with additional constraints on variable? Given a 2-SAT problem that is satisfiable. The solution to the problem can be found in polynomial time.

Adding an additional constraint:

The maximum number of positive literals that can have the boolean Value 1 is N. (i.e. a=positive literal, ~a=negative literal)

Is the problem still solvable in Polynomial time?

My assumption is it should be but I am unclear now to modify the original solution? Or are we looking at something similar to the Vertex Cover Problem?

That is NP-hard by reduction from vertex cover, even when there are no negative literals.

If you meant to count by occurrences rather than just bounding the number of

distinct variables which are true, then use this paper's result and this paper's result.


Lowest complexity - Number closest to 0 I'm currently trying to improve my algorithm skills and I was trying a simple algorithm :
Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his opposite, we want to return the positive one.
My current complexity on this algorithm is O(n). Is it possible to get a lower one ?
My current solution looks at all the values. I was thinking about a binary search, but we're not looking for a specific number, and the list of integers is not sorted.
Thanks for the help !

If you want an algorithm that is always correct you can not do better, precisely because you have to look at all the values at least once (except if you find a $0$ somewhere, then you can immediately return that).
Otherwise, suppose your run your algorithm $A$ some input $I=[a_1,a_2,\ldots,a_n]$, and it returns a value $v\neq 0$ without looking at all numbers in $I$. Say it didn't look at $a_k$. Then we could just as well set $a_k=0$ and $A$ wouldn't know about it (because it didn't look at $a_k$). Thus $A$ will be wrong on this (modified) input.
That is of course assuming that setting $a_k = 0$ doesn't contradict some assumption you have about the data (for example it being sorted).


Lexicographic permutation list Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?

Thanks.

You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller.

Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order.

Start by sorting the input sequence, $A$, of $n$ objects
Find the largest index $k$ such that $A[k] < A[k+1]$.  If no such $k$ is found, terminate. The sequence $A$ contains the last lexicographic permutation.
Find the largest index $l$ such that $A[k] < A[l]$
Swap $A[k]$ and $A[l]$
Reverse the sub-sequence starting from $A[k+1]$ to the final element, $A[n-1]$

Note that this algorithm generates the next lexicographic permutation of $A$ in-place. To generate all permutations, you can repeat this until no more permutations are found.


Travelling with the most efficient path A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.

The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.

For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.

You need to find the most efficient way to reach the destination.

What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.

Do you have any idea how to do it? Or any hints?

Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?

Some more thoughts:

Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
$1000$ and $50$ might be deliberately picked to avoid complex computation.
Is there a greedy solution? I cannot think of any just yet.
I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.

And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.

The basic idea is to make $n$ trips, returning to the start and refueling on all but the last trip. On each trip but the last, you'll leave some fuel at a new dump. You want to know how far you can go on the last trip. To make calculations easy, we'll say that a full tank contains 1 (unit) of fuel and that amount will take you a distance of 1 (other unit) of distance.

Example 1 ($n = 1$ trip). Trivial: drive until you run out of fuel. Distance covered $D(1)=1$.

Example 2 ($n=2$). On the first trip, travel $x$ distance, so you'll have $1-x$ fuel remaining. Leave just enough fuel at dump 1 to allow you to return to the start. Leaving $1-2x$ at dump 1 will do the trick. On the second trip, starting with a full tank, go to the first dump (using $x$ of your fuel), top off your tank (taking $x$ from the dump, leaving $1-3x$) and drive until you run out of fuel. To maximize the distance we'll need the dump to be empty so $1-3x=0$, so $x=1/3$. The total distance you'll cover will be $D(2)=1+1/3$.

The general case. With $n$ trips, you'll hit dump 1 $2n-1$ times, dump 2 $2n-3$ times, dump 3 $2n-5$ times, and so on. To empty the dumps on the last trip, we'll place dump 1 at a distance $1/(2n-1)$, dump 2 at a further distance $1/(2n-3)$, and so on. Then the last trip will cover
$$
D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}
$$
If we define the $m$-th harmonic number,
$$
H_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m}
$$
then it's well known that $H_m\approx\ln m$ and we can write our distance
$$\begin{align}
D(n) &= 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}\\
 & = \left(1 + \frac{1}{2}+\frac{1}{3}+ \dotsm + \frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+ \dotsm + \frac{1}{2n-2}\right)\\
 &=H_{2n-1}-\frac{1}{2}H_{n-1}
\end{align}$$
This will take an amount of trips (and fuel) that are exponential in the desired distance. For example, to go a distance of $2$, it will take $n=8$ trips and to go a distance of $5$ will take $3093$ trips.

This (and a variant) is known as the jeep problem and is covered in more detail here.


Why can you push multiple symbols on a PDA stack at once? I'm really new to learning about PDA's and stuff, i understand that on a edge between 2 nodes you'll have something like this a,b->c. This means:

if a is in the beginning of your string and b is on top of your stack you can

remove a from your string (the one you run through the PDA),
remove b from your stack
place c on your stack

and take the edge...

My book also tells me that you can place more then one symbols on your stack. For instance a,b->cd.

I think this is because you can also have this edge  ε, ε -> c wich just puts c on the top of the stack,

so a,b->cd between Node 1 and 2 can by replaced by Node1 - a,b->c - New node -  ε, ε->d -> Node2.
Can someone please confirm if this is correct?

the pda is defined as (Q,E,T,d,s,F) with

Q an finite collection of states
E a finite inputalfabet
T a finite stackalfabet
d a transitionfunction Q x E (including ε) x T (including ε) -> V collection of(Q x T (including ε))
s the startstate
F a collection of eindstates (subcollection of Q)

You always have to take out a symbol. So if we could only write a single symbol, we could never really build up stack content.

Writing more than two symbols is just syntactic sugar; we could easily simulate it with PDAs restricted to writing zero, one, or two symbols.


Advantage of byte addressable memory over word addressable memory What is the reason that almost all computers (besides some DSPs) use byte addressable memory? With byte addressable memory and a 32 bit address you can have 4GB while with word addressable memory you can have 4GB * wordsize. Are single bytes used that much that you can't use routines that filter out single bytes from a word because there is an advantage of having more memory?

For 32-bit addresses and 32-bit words, the benefit of being able to address a larger memory is relatively minor, adding only two generations of Moore's Law to the lifetime of the architecture. Compared to a transition from 16-bit addresses to 32-bit addresses (sixteen generations), this is a relatively minor extension.

For the CDC 6600, having 18-bit addresses and 60-bit words and targeting technical computing, the use of word addressing made more sense. Technical computing emphasizes performance over price (so wasting some memory was less important than fast memory access) and has less use for finer-grained accesses.

Many 16-bit DSPs use word addressing. This more significantly increases addressing range than for a 32-bit processor and the benefit of finer-grained access is much smaller for the targeted workloads.

For business and general purpose computing, system cost is a more significant consideration and data element size is more variable. The cost of memory provides an incentive to use smaller data elements. Not supporting direct access to such elements not only increases instruction count (which somewhat directly relates to performance) but code size (which increases memory pressure).

Having a single flat address space simplifies software development. If sub-word addressing requires special handling, this has an effect similar to segmentation where some accesses have to be treated differently than others. Even if such is handled by the compiler, such makes performance less transparent (as well as making compiler development more complex, reducing the resources spent on other features).

Word addressing also requires the use of atomic read-modify-write operation to support simple sub-word stores. (The atomicity requirement may only be with respect to interrupts, but this does add complexity.) A further complication occurs for memory-mapped I/O, where read-modify-write cannot be used since accesses can have side effects. While this issue can be managed by having regions that translate word addresses to specific sub-word granularities, such is an awkward solution. This was how the Alpha 21064 handled byte I/O addresses without byte loads or stores (also 2-byte I/O accesses). (Some 32-bit microcontrollers use bit-banding regions, where an address region uses bit-granular addressing.)

A large part of the reason that byte-addressing (with 8-bit bytes) is popular is, in fact, historical. Not only did IBM's S/360 have a strong influence on the de facto standardization on byte addressing and 8-bit bytes, but the IBM's choice of Intel's 8088 further solidified this trend. With early microprocessors, 8-bit processors would naturally use 8-bit word addressing, maximizing the use of existing software (often written in assembly language) would increase the incentive for using byte-addressed memory. (Note: Reasonable alternatives to the 8086/8088 also used byte-addressing, though IBM's requiring a cheaper and more compatible 8-bit interface may also have been a significant factor. I am not suggesting that word-addressing was only avoided because of the choice of Intel's 8088 for the IBM PC.)

As noted, compatibility with existing I/O interfaces can be particularly problematic.

As Richard L. Sites notes in "Alpha AXP Architecture" (PDF) perhaps more significant benefits of word addressing are avoiding extra shifting of the load result and supporting moderate overhead ECC in a fast writeback cache. Traditional SECDED ECC would require 7 extra bits over 32-bit granules (22% overhead) versus 4 extra bits over 8-bit granules (50% overhead). (Sites' argument about library writers being lazy and using simplistic byte-based string operations is less convincing; forcing extra effort may encourage a moderate addition of effort for higher performance code but it may simply annoy programmers.)

A similar issue applies to unaligned memory accesses. Architecturally disallowing unaligned accesses can simplify hardware but makes some not uncommon operations significantly more complex. Even with MIPS-like load/store unaligned, software must special case unaligned accesses since such instructions increase dynamic instruction count and should not be used if the accesses are known to be aligned. Support for unaligned memory accesses can be particularly beneficial for short vector operations where the individual elements might be properly aligned (e.g., 16-bit elements aligned at 16-bit granularity) but the start of the vector might not be aligned. (This is effectively the same problem as string handling.)

It might be worth noting that software-based pointer compression has some popularity. On a 64-bit architecture, software can choose to use simple 32-bit pointers or even exploit structure alignment to store larger pointers in 32-bit memory locations. (A similar software technique uses bits that can be ignored based on known alignment to store metadata. SPARC even architecturally defined such use by supporting tagged arithmetic operations. Storing metadata in the more significant bits of a pointer is also a common technique. ARM's AArch64 allows the most significant 8 bits to be used for metadata without requiring extra masking, and Azul Systems' Vega processor used the most significant 16 bits for metadata.) In pointer-intensive programs, the reduction in cache misses may justify the additional left shift when loading a pointer. Obviously, this technique has limited use since it requires knowing that the data set will fit within the smaller region and that the objects will be aligned. These factors are easier to enforce at the application or even virtual machine software level than at the architectural/hardware level, especially for a merchant processor (a processor sold to various system vendors).

(Using segments identified by the least significant two bits might be better than word addressing. Like word addressing, such would extend the reach of 32-bit pointers by exploiting structure alignment but it would allow further reach by changing segment addresses. This would require special instructions to distinguish dynamic segment specification (which masks out two bits) and static segment specification (which allows byte granular addresses). HP PA-RISC used a similar segmentation system, but used the most significant two bits to identify the segment — allowing simple byte-granular addressing in dynamically specified segments within a GiWord region but making the 64-bit transition messier than if the least significant bits were used. This choice may hint at how important byte granular addressing is for general purpose computing.)


Prove that L = { wu; wu in {a,b}* and |w| = |u| } is not regular Prove that $L = \{wu, wu \in \{a,b\}^* \ \land  |w| = |u| \}$ is not regular.

I'm trying to approach this problem with the pumping lemma.

So I know I have to pick a string s, which can be split into xyz components in terms of the pumping length, p.

But I cannot seem to find an s.

For example using $ s = a^p b^p$ or $s = a^p a b^p b $, since $|xy| \le p  \land |y| > 0$, then y must contain some a's. So we can try to pump $x y^i z$ to see the new string is still in L.

The issue is that if y contains an even number of a's it can always be pumped because the resulting string will have even length so w can be the first half and u be the second half.

As Rick Decker said $L$ is a regular language. For example:
$$L= \mathscr{L}(\,(aa | ab | ba | bb)^*\,)$$

If your teacher asked you to prove that $L$ is not regular in an exam then he is a big troll. Otherwise remember that the pumping lemma is only usefull to prove that a language is not regular and if you fail to find the contradiction in the lemma then that doesn't prove anything. $L$ can be regular or irregular at that point.

In this answer I covered some common mistakes when students use the pumping lemma: Common Mistakes


Turing machine and coming up with an idea I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am given to solve? I mean: checking if a word is a palindrome, for example, consists of 11 states in the book I'm learning from. For my current state of knowledge, just sitting over an empty sheet of paper and coming up with all these states seems next to impossible, to say the least. When I try to do something like this, I get stuck immediately since I don't know what should I do to make these states work somehow "together". I don't have such problems when programming in some prog languages but here, I just can't figure out how I should approach something consisting of some n-teen states. Could you please point me some direction to learn about it?

Just to expand the comments above, you should try to find a high level algorithm, and then refine its steps in smaller pieces.

For example, if you want to recognize palindrome words, a high level agorithm can be:

1. check if the leftmost symbol is equal to the rightmost symbol
2. if they are not equal reject, otherwise delete them
3. if there are other symbols then goto 1, otherwise accept

That can be refined in the following way:

1.1 move the head on the leftmost symbol
1.2 "store" its value
1.3 if it is the only symbol left then accept (w has an odd length)
1.4 otherwise move the head to the rightmost symbol
2.1 compare it to the "stored" one
2.2 if they are not equal halt and reject, otherwise
2.3 delete the rightmost symbol
2.4 move the head to the leftmost symbol
3.1 delete it
3.2 if the tape is empty halt and accept, otherwise
3.3 goto 1.1

The steps are "implemented" using the internal states of the Turing machine.
While designing the Turing machine you can name the states with labels instead of "q0, q1, q2" to make the design process easier.

If you have a single tape Turing machine, the step [1.2 "store" its value] means that you must use the internal states to "remember" the symbol read while the head moves to the rightmost one.

Suppose you have two input symbols $a,b$ and $-$ is the blank symbol, then you can use a set of states La,L'a,CMPa and Lb,L'b,CMPb to represent (store) the leftmost symbol read; so steps 1.1, 1.2, 1.3, 1.4, 2.1, can be implemented in this way:

     |  a      |   b     |   -
START| a,R,La  | b,R,Lb  | -,R,START << move right until you find a symbol
La   | a,R,L'a | b,R,L'a | ACCEPT    << step 1.3
Lb   | a,R,L'b | b,R,L'b | ACCEPT    << step 1.3
L'a  | a,R,L'a | b,R,L'a | -,L,CMPa  << step 1.4
L'b  | a,R,L'b | b,R,L'b | -,L,CMPb  << step 1.4
CMPa | -,L,MVL | REJECT  |           << compare to a
CMPb | REJECT  | -,L,MVL |           << compare to b
MVL  | .......                       << move left

As you can see after reading the leftmost symbol the states are doubled:

Lx we are on the first symbol after the leftmost one (which is symbol x)
L'x we are moving rightward from the leftmost symbol x
CMPx we are comparing the rightmost symbol with the leftmost symbol x


Why is this pushdown automaton for some palindromes right? $B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$

Solution:

For example: $111$ should be accepted

steps are

$q_1 \to q_2$ stack: [$\$$]

$q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$ only having a single $1$ left)

$q_2 \to q_3$ stack: $[\$, 1, 1]$ (no change except we lost our final $1$)

$q_3 \to$ (no strings left to use)

I'm confused understanding this

PDAs are nondeterministic. Although you have found a valid computation which does not lead to an accept state, a PDA is said to accept its input if there is some valid computation which does lead to an accept state.

In this case (input $111$), an accepting computation is:

$q_1 \to q_2$, stack: $[\$]$
$q_2 \to q_2$, stack: $[\$, 1]$
$q_2 \to q_3$, stack: $[\$, 1]$
$q_3 \to q_3$, stack: $[\$]$
$q_3 \to q_4$, stack: $[]$


What's the name of this DFS variation Classical DFS:
A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic.
A DFS is usually used to find an ordering of the tasks that satisfies all of the precedence constraints, classical DFS algorithm can do it by building the sequence step by step.
An extension:
Consider now the following variation. Each node $j$ is weighted by a value $w_j$. When we are currently at node $j$, this weight will determine the next node to visit (the one with the higher weight).

Moreover, imagine that each time a node is added to the list, we recompute the weight for the unvisited nodes using a given function (we don't care about the nodes that has already been added to the sequence).  Thus at step $t$, the $w_j(t)$  of node $j$ can be different from its weight at step $t+1$.

Questions: Is there a name of this problem ? How to solve it efficiently? (e.g If a node has several successors, one needs to determine the successor with highest weight, so which data structure to use?)
N.B The image is only used for an illustration purpose. The graph is not assumed to be a binary tree.
Edit: the graph is assumed to be connected

This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e.g. a heap, in this case a max heap).
Consider the following algorithm. $G=(V,E)$ is a graph with vertex set $V$ and edge set $E$, $w(j,t)$ is the weight function taking a vertex $j \in V$ and a timestep $t$, and $S \subseteq V$ is the list of start vertices (one in each connected component of $G$). $G$ is not necessarily connected.
BestFirstTraversal(G=(V,E), w(j,t), S)
    visited = []
    t = 0

    # from [0, t):   heap is the order in which the vertices are visited
    # from [t, end]: heap is a max heap
    heap = S  # from t to the end is max heap

    # loop until all vertices have been visited
    while len(visited) != |V| do
        u = heap[t]  # get the max element

        # do something with u

        append u to visited
        append neighbors of u (not in visited) to heap
        t = t+1

        heapify(heap[t:])  # based on w at step t
    end while
end

Let $n = |V|$ be the number of vertices.
Run Time: BestFirstTraversal runs in $O(n^2)$.
Notice $S$ is a list of vertices, one for each connected component of $G$. This is necessary because there must be a starting point for each connected component. If we started from a single node in a graph with more than one connected component, we would never be able to visit the other connected components. Thus the loop will visit each node in $G$ from one of the starting vertices.
Thus the while loop runs $n$ times. Appending neighbors and heapify takes up to $O(n)$ work. Hence, $n * (2 * O(n)) = O(n^2)$.
Note, heap will contain the order of the vertices visited at the end BestFirstTraversal.
Hope that helps!


Why is it that O(N + P) where P < N/2 reduces to O(N)? My book says that

  If $P < N/2$ then we know that N is the dominant term so we an drop the $O(P )$."

If it was $O(N + P)$ where $P > N/2$ what would it reduce to?

In the Big-O notation, constant factors are irrelevant.

Then if $N>P$, $O(N+P)$ reduces to $O(N)$, by swapping $N$ and $P$ we have that if $P>N$, $O(N+P)$ reduces to $O(P)$.


Are permutations of context-free languages context-free? Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ context-free?

I found two papers dealing with similar, but not identical, questions:

Generating all permutations by context-free grammars in Chomsky normal form by Asveld (2003) deals with finite languages.
Permutations are not context-free: An application of the interchange lemma by Main (1982) deals with "permutation languages", i.e. sets of strings of the form $w x p(x) z$, where $p(x)$ is a any permutation of $x$. Also, the result is limited to alphabets with 16 symbols.

Start with simple context-free (or even regular) languages, and see what happens. For instance determine $p(L)$ for $L = (ab)^*$ and $L=(abc)^*$.


Substitution-based Operational Semantics of algebraic datatypes Assume, I want to define the operational semantics for some subset of ML.

e ::= \\x. e | e e | c | match e with p+ | A e*
v ::= ... | \\x. e | ... | A v*
p ::= A p* -> e | x

Where e is the expression language, v are the values or normal forms, p are the patterns and A are the constructors for my algebraic datatypes.

Also assume I want to define the semantics based on substitution, not on environments. Finally, the language should be typable, e.g. every constructor will only be allowed to be applied to the same number of arguments.

So I assume, I have to introduce a "construct" operation and a "data declaration" and then substitute every constructor with an appropriate datatype declaration. But how does one define this "construct" operation? And how does the data declaration look like in an untyped calculus?

I found the solution to my answer: ADTs can be represented by a combination of sum-types and tuples enter link description here. In that representation, every construction takes exactly one argument (possibly the unit value).

Two special tagging forms, inl and inr for "inject left" and "inject right" are introduced. These forms allow the encoding of arbitrary tags. So every constructor is a one-argument function that applies the corresponding tag.

Hence, any data structure definition is operationally defined by the constructing operations:

data A | B | C

=>

let A = \\x. inl x in
let B = \\x. inr (inl x) in
let C = \\x. inr (inr x) in

The corresponding pattern can be substituted similarly.


Kolmogorov complexity of a sequence of n bits with k ones Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length;
Of these sequences, print the ith sequence."

Apparently the length of this program is $\log(n) + \log(\binom{n}{k}) + c$ where $c$ is a constant. Where $i$ can be represented in $\log(n)$ bits and
k in $\log(\binom{n}{k})$ bits. Why does the length of the program not take into account that we will be generating all of these sequences in lexicographic order, does the length of the sequences and the number of sequences not depend on $n$. Don't you have to hold those in an array? Does that not take space?

Thank you.

In Kolmogorov complexity, our measure of complexity is program length. We don't care about the resource consumption of the program (unless we're interested in resource-bounded Kolmogorov complexity). Given $n$ and $k$, a program can generate all $n$-bit strings of weight $k$, so there is no need to store the list itself as part of the program.

The formula you quote and the explanation you give seem mistaken. In order to use the program you mention to generate a specific vector, we need to give it as input $n,k,i$. It takes $K(n) \le \log n + O(\log\log n)$ bits to encode $n$ itself. Given $n$, we can encode $k$ in $\lceil \log n \rceil$ bits, and $i$ in $\lceil \log \binom{n}{k} \rceil$ bits. Overall, we obtain that the Kolmogorov complexity is at most
$$ 2\log n + \log \binom{n}{k} + O(\log\log n). $$


Counting the nodes of a unidirectional graph Suppose that we have the above graph. The graph is directed and is unidirectional; that is, we can only traverse it from top to bottom.

We want to update the count of the nodes such that the count of any given node indicates the sum of the count of the node itself and the previous nodes, avoiding any duplicate nodes.

Example

For $ id:5 $ the count will be the sum of counts of $id:1,2,3,4$.
So, the count will be calculated as
$Count(id:5) = \sum Count(ancestors) + selfCount$.

So, the $Count(id:5) = 5$ in this case.

Implementation that has been thought of

One such implementation could be traversal from top to bottom, and updating the count levelwise (breadth-first search).

We could then add the count of previous nodes, and subtract the count of the LCA(Least Common Ancestor) node.

Example

So, if we have to find the count of node $id:5$, we would get the following count:

$ Count(id:5) = Count(id:5) + Count(id:2) + Count(id:3) + Count(id:4) - 2*Count(id:1) = 1 + 2 + 2 +2 - 2*1 = 5$

Here is the final graph that we are getting.

Another example:

$ Count(id:7) = Count(id:7) + Count(id:5) + Count(id:6) - Count(id:4) = 5 + 3 - 2 +1 = 7 $

Problem

How do we remember the counts of ancestor nodes, when we are analyzing the counts of the current nodes?

It could be possible that the ancestor might not be immediately present, it could be far away at previous levels also.

Is there any algorithm that could solve the problem? I would really appreciate the help.

You can build a graph $G'=(V,E')$ that comprises the same set of vertices $V$ from the input graph $G=(V,E)$ and whose set of edges $E'$ includes an edge $(v,u)$ for every edge $(u,v) \in E$. That is, $G'$ is the same graph as $G$, but with the edges reversed; therefore, $G'$ is also topologically sorted (in the same way as $G$, but in the opposite direction). You are looking for the number of successors (+1) of every vertex in $G'$. This can be found using depth-first search, starting a new traversal from every vertex and counting the nodes that you find. The running time of this algorithm is $O(mn)$, where $n$ is the number of vertices of the graph and $m$ is the number of edges. D.W.'s answer provides some useful links with approaches with slightly better running times.


(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees? Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible diﬀerence between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or big-Theta.

I drew six trees and drew the max number of nodes I could on one tree and the min number of nodes on the other subtree while keeping it an AVL tree.
Here  is table with the information for number of minimum nodes in left subtree, max number of nodes in right subtree and difference between the number of nodes between the two trees:

But I simply cannot figure out a pattern for the maximum possible difference between the number of nodes in the two subtrees. My current guess is that the max possible difference between the two number of nodes is 2h-1 - (h-2).

Here is a picture  of the diagrams I drew to come up with the numbers in the table above:

I drew as little nodes as possible on the left subtree and drew as many nodes as I could on the right subtree.

I assume that we start labeling heights from $0$.

Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-tree to $h-2$ (doing so, the bottommost node of this sub-tree would be at height $h-1$ of the main tree) and we fix the height of right-side sub-tree to $h-1$. Now, we should answer following questions:

What is the minimum number of nodes in an AVL tree of height $h-2$?
What is the maximum number of nodes in an AVL tree of height $h-1$?

Answer to question 1: By recursions and assuming that $n(h)$ is the minimum number of nodes of an AVL tree of height $h$ we can easily get:
$$
\begin{array}{rl}
n(h) &=& n(h-1)+n(h-2)+1\\
n(1)&=&2\\
n(0)&=&1
\end{array}
$$

Answer to question 2: In this case, we're dealing with a perfect tree (which is an AVL tree too) and we must find the number of nodes in a perfect tree of height $h-1$.

So, the answer to your question would be:
$$
2^h - 1 - n(h-2)
$$

As an example, if $h=2$, this formula returns $2$, which is not the value you have got, and I think that's because you start labeling heights from $1$.


What does it mean if a generic structure is type-erased? This documentation states that the generic structure AnyIterator is a type-erased iterator of Element.

It means that at runtime you will not be able to see what object comes out of
the collection, as that information is removed from the lower-level code that is generated by the compiler.

In your specific instance, it would mean that at runtime an object of type AnyIterator<Element> will not be able to tell you what is the exact type of Element, unless ofcourse, you (implicitly/explicitly) cast it.


More the number of for loops greater the problems solved This is more a formal language theory question.

Imagine a setting where you are given a very basic programming language where variable assignments etc are taken care of without any of the iteration capabilities. The only iteration capability of this primitive language is having a for loop. I'm not sure if there is already such a language defined in literature, if yes, I'd be happy to know its name. Let an instance of this language be called a program. And I think we can understand that a program is usually written to solve a problem or a set or problems that can be solved by the same program with very minor modification to the program for each specific problem.

Now my question is. Let $P_i$ be the set of problems that can be solved by programs in the given primitive programming language that uses at most $i$ many for loops.

We understand $P_i \subseteq P_{i+1}$.

But can we write down a proof of $P_1 \subset P_2$? that is prove a separation !

I know this is "too wordy" may be someone can help formalise this question. And if someone can point out to relevant literature that already exists on this problem, it'd be a great help.

Its like the complexity resource being targeted here is the "for loop".

Let us consider the LOOP programming language. For a program $f$, denote by $f_{\max}(n)$ the maximal value of a variable at the end of the program, given that initially, all variables are at most $n$. If $f$ has only one loop then $f_{\max}(n) = O(n)$. In contrast, using two nested loops you can compute the product function, and the resulting program $g$ satisfies $g_{\max} = \Theta(n^2)$. This separates $P_1$ and $P_2$.

More generally, $f_{\max}$ can be bounded in terms of the maximum nesting depth of loops in $f$. If the maximum nesting depth is $d$, then the growing rate of $f_{\max}$ is comparable to the $d$th level of the Ackermann hierarchy. This allows us to separate $P_i$ and $P_{i+1}$ for every $i$.


Rice Theorem - What is non-trivial property? Every nontrivial property of the recursively enumerable languages is undecidable.

What exactly is nontrivial property?

A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property.

To see why, note that such a property can be decided by a very simple Turing machine, which accepts/rejects every Turing machine representation.


Finding an exactly weighted st-path in a digraph I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.

The question is: given 2 nodes $v_1$ and $v_2$, is there a path from $v_1$ to $v_2$ with a weight $w$.

I would like to know if there are any known complexity results for this problem, or even anything related to this but with a specific weight, and not just shortest path, longest path etc.

This problem is NP-complete.

The "$\in$ NP"-part is trivial.

For the NP-hard part we reduce directed hamiltonian path:

  Given a directed graph $G=(V,E)$ and two vertices $v_1,v_2\in V$, is there a path from $v_1$ to $v_2$, that visits each vertex exactly once?

For the reduction we keep $G$, $v_1$, and $v_2$ and number the nodes from $1$ to $n$, so that $v_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.

It is easy to compute, that a hamiltonian path will have the correct weight.

For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.

Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0<i<n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.

The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.


Bayesian Nets & Markov Blanket As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem.

In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to find minimum number of variable that Xi independent from other variables. at least, how many variable we need?

i think, we use Markov Blanket for this problem. any solution for this problem?

Regards.

In a Bayesian network, a variable is independent from all the variables given its Markov blanket (except of course the variables in the Markov blanket).

However, the Markov blanket is not the minimal set that renders two variables independent.

Also note that a variable may be independent of some variables in the Markov blanket, given another set of variables (think about the case of a spouse in the network).

By the way, I think that this problem has been solved already (if you refer to the problem of identifying the minimal set that renders two variables independent).

Edit: Check this out: http://www.cs.iastate.edu/~jtian/r254_min_separator.pdf
They show how to find a minimal d-separating set in a given Bayesian network.


Graph with exactly 2 Minimum Spanning Trees Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs).
  Given this condition stipulated, prove that any cycle formed by all
  the edges in both the MSTs (i.e., the union of the edges in of the 2
  MSTs) that at minimum, 2 of the edges in the set which is the union of
  the edges have equal weight. Also show that either this edge is the
  largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can't be distinct, otherwise there wouldn't be multiple MSTs. Also the graph $G$ must contain cycles, otherwise, it wouldn't have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $MST_1$ there is some edge, $e$ that is not in $MST_2$ and there is also some edge $f$ that is not in $MST_1$. Using the cut property if $e$ was not placed in $MST_2$ and $f$ was not placed in $MST_1$ then then we have that the weight of $f$, and $e$, $w(f) = w(e)$.

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that's actually true. Then from there I felt that there had to be some node, $z$ such that $z$ had 2 edges with the same weights, and when we combine the edges from $MST_1$ and $MST_2$ we end up with both the edges from $z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle... Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $G$, in order for it to have exactly 2 MSTs? Or is there some property I'm missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.

Lemma: Let $C$ be a cycle of $G$ that contains an unique edge $e$ of maximum weight. Edge $e$ does not belong to any MST of $G$.

Proof:
Suppose that a MST $T^* = (V, E^*)$ of $G$ contains $e = (u,v)$.
Root $T^*$ in $u$ and let $f$ be any edge of $C \setminus E^*$ that has exactly one endpoint in the subtree of $T^*$ rooted in $v$ (this edge always exists since $C \setminus \{ e \}$ is a path from $v$ to $u$ that avoids $e$). The edge $f$ closes a fundamental cycle containing $e$ and is such that $w(f) < (e)$.
Then $(V, (E^* \setminus \{e\}) \cup \{ f \}$) is a spanning tree of $G$ that weighs less than $T^*$. This is a contradiction. $\square$

Let $T_1 = (V, E_1)$ and $T_2 = (V, E_2)$ be two distinct MSTs of $G$.
Let $C$ be a cycle in $(V, E_1 \cup E_2$).
Let $M = \arg\max_{e \in C} w(e)$.

If $|M|>1$ we are done. Suppose then that $M = \{ e \}$.
By the above lemma, $e$ is the unique heaviest edge of $C$ and hence it cannot belong to any MST of $G$. This is a contradiction since $e$ must belong to at least one of $E_1$ and $E_2$.


Construct SLR Parse table problems Consider the augmented grammar G is:

S` -> S
S -> a
S -> (T)
T -> T,S
T -> S

I have tried to construct parse table. But, when I read '(' nonterminal Symbol (item 3), there is no action table elements either 'shift' or 'reduce'.

I3:
S -> (.T)
T -> .T,S
T -> .S

so I can't construe '(a,(a,a))' in this Parse table.
then is it ambiguous grammar? or I wrong the answer?

I3 productions are:
S->(.T)
T->.T,S
T->.S
here you need to add closure of S
S->.a
S->.(T)


$\text{DSPACE}(O(1))=\text{REG}$ Proof? I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and know that the idea is to encode the finite possibilities of memory as finite states, and also have read https://cs.stackexchange.com/a/57938/112750 . However, I still have a question that I'm unable to answer. A finite automaton needs to read the characters one by one and never look back, but a TM, though restricted to use only $O(1)$ memory, may choose to go back and forth on its input tape. How can I eliminate this kind of looking back problem and construct an automaton that is equivalent to this TM?

Suppose you have a Turing machine with an $n$ sized tape with $k$ symbols and $s$ states. This system, as a whole, then has $s\cdot k^n \cdot n$ possible states it can be in ($s$ states, $k^n$ tape contents, $n$ tape head positions).

By definition $k$ and $s$ must be $O(1)$. If $n$ also is however, then the entire expression $s \cdot k^n \cdot n$ is a constant, and we can construct a finite state machine with that many states that has exactly the same behavior as the Turing machine.


Is this NP-hard: min-weight n-clique in a complete n-partite graph I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total.  My problem is to find a minimum weight $n$-clique in the graph.  I would like to know whether the problem can be solved in polynomial time.

More details of the terms:

Complete $n$-partite graph: a graph in which vertices are adjacent if and only if they belong to different partitions (wikipedia).  There are $n$ partitions in the graph.  (In my case, each partition contains exactly $n$ vertices.)

Minimum weight clique:  Every edge in the graph has a weight.  The weight of a clique is the sum of the weights of all edges in the clique.  The goal is to find a clique with the minimum weight.

Note that the size of the required clique is $n$, which is the largest clique size in a complete $n$-partite graph, and it is always attainable.

I have searched for hours and there seems no research tackling the exact problem.  Any suggestions?

The decision version of your problem (whether there is a clique of weight at most something) is NP-hard, by reduction from 3-SAT. Let $\varphi$ be a 3CNF formula with $m \geq 7$ clauses. We create an $m$-partite graph. Each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause, and $m-7$ dummy vertices. All edges touching a dummy vertex have weight $1$. Edges connecting two conflicting assignments also have weight $1$. Edges connecting two non-conflicting assignments have weight $0$. The graph has a clique of weight $0$ iff $\varphi$ has a satisfying assignment.

We can also get a hardness of approximation result this way. Given a 3CNF formula $\varphi$ with $m \geq 7$ clauses, we create an $(m+1)$-partite graph. There is a part corresponding to each clause, which has $8$ vertices corresponding to all assignments to the clause, and $m-7$ dummy vertices. In addition, there is a part with $m+1$ special vertices. All edges touching a dummy vertex have weight $m^2$. Edges connecting two conflicting assignments also have weight $m^2$. Edges connecting two non-conflicting assignments have weight $0$. Edges connecting satisfying assignments (for clauses) and special vertices have weight $0$. Edges connecting non-satisfying assignments and special vertices have weight $1$. The minimal clique in this graph has weight equal to the minimal number of unsatisfied clauses in any assignment to $\varphi$. Therefore for every $\epsilon > 0$ it is NP-hard to decide, for $(m+1)$-partite graphs, whether the minimal clique has value $0$ or at least $(1/8-\epsilon)m$. In fact, by modifying $\epsilon$ slightly we get the same result for $m$-partite graphs.


Number of nodes at given depth in binary tree Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction of $1/2^n$?

The running time of a specific input is linear if the corresponding leaf node is within a linear distance from the root. Considering a binary tree, the maximum number of nodes within a linear distance from the root is $2^{kn+1}-1$.

How $2^{kn+1}-1$ was reached? just I need an intuitive idea not a proof. this is my notes not an homework or exercises. $k$ and $n$ not defined on it context.

Intuitively, the maximum number of leaves at distance at most $d$ from the root is obtained when all of these leaves are at distance exactly $d$ from the root. Since there are at most $2^d$ nodes at distance exactly $d$ from the root, this suggests that the maximum number of leaves at distance at most $d$ from the root is $2^d$.
We can easily prove this bound formally using Kraft's inequality, which states that
$$ \sum_{\ell} 2^{-d(\ell)} \leq 1, $$
where $\ell$ goes over all leaves, and $d(\ell)$ is the distance of $\ell$ from the root. Kraft's inequality implies that
$$ 1 \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d(\ell)} \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d},$$
from which it immediately follows that there are at most $2^d$ leaves at distance at most $d$ from the root.

The text you quote is less sophisticated. It is bounding the number of leaves at distance at most $d$ from the root by the number of nodes at distance at most $d$ from the root. Since there are at most $2^e$ nodes at distance exactly $e$ from the root, it follows that the number of nodes at distance at most $d$ from the root is bounded by
$$ \sum_{e=0}^d 2^e = 2^{d+1} - 1. $$


Partition into paths in a Directed Acyclic Graphs I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.

When $b_i=1$ for all the vertices, the problem can be solved in polynomial time. But I am searching for the complexity of the problem  when $b_i>1$ for at least one vertex $v_i$, do you know about any results that may help me?

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in A$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.


Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (Pg 102-103). It would be great if someone can provide a clarification on this.

The No-regret (sub-linear) algorithm is given in Algorithm 17 (Pg 102), and proof for no regret is shown in lemma 6.1 . I will make the description as self-contained as possible, but a more detailed presentation can be found in pgs 102-103 in the book mentioned above.

Let $\mathcal{K}=\left[1, n \right]$ denote the set of experts(arms). Let $i_t \in \mathcal{K}$, denote the expert chosen by the algorithm in the $t^{th}$ round. Let $l_t(i_t)$, denote he loss function provided by the adversary in the $t^{th}$ round. Since we are dealing with the bandit setting, we do not know $l_t(i)$ for all $i \in \mathcal{K}\backslash i_t$. Further, the loss functions ($l_t$) are assumed to be bounded between 0 and 1. The way the algorithm works is, at each round we flip a coin, with bias $\delta$. If the outcome of the coin is heads, the algorithm chooses one of the actions i.e. $i_t$, and constructs a estimate of $l_t$ as follows:
\begin{equation}
\hat{l}_t =
\begin{cases}
\frac{n}{\delta} l_t(i_t), \text{ if } i = i_t\\
0, \text{ otherwise}
\end{cases}
\end{equation}

If however, the outcome of the coin toss was tails, then it simply sets $\hat{l}_t = 0$.

It can be easily shown that by using the above scheme we have $E\left[ \hat{l}_t(i)\right] = l_t(i), \, \forall i \in \mathcal{K}$.

The regret as shown in the book is as follows.
\begin{eqnarray}
\label{Eq:1}
E[regret_T] &=& E\left[\sum_{t=1}^{T} l_t(i_t) - \sum_{t=1}^{T}l_t(i^*)\right] \\
\label{Eq:2}
& \leq& E\left[\sum_{t \not \in S_T} \hat{l}_t(i_t) - \sum_{t \not \in S_T} \hat{l}_t(i^*)  + \sum_{t \in S_T} 1 \right]
\end{eqnarray}

where $S_T \subseteq [1, T]$ denotes the round in which the coin toss was heads, and $i^* = \underset{i \in \mathcal{K}}{\text{arg min}} \sum_{t=1}^{T} l_t(i)$ . I am having a hard time showing why $E[regret_T] \leq E\left[\sum_{t \not \in S_T} \hat{l}(i_t) - \sum_{t \not \in S_t} \hat{l}_t(i^*)  + \sum_{t \in S_T} 1 \right] $. The comment in the book is that $i^*$ is independent of $\hat{l}_t$, hence validity of inequality. I did not understand what that was supposed to mean.

My Attempt:

For my attempt, I will be using the some of the notation used in the proof of that book.
We know that $\underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \leq \sum_{t=1}^T \hat{l}_t (i), \, \forall i \in [1,n]$. Applying $E$ (expectation) on both sides we get,
\begin{eqnarray}
E\left[ \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \right] &\leq & E \left[\sum_{t=1}^T \hat{l}_t (i) \right], \, \forall i \in [1,n] \\
\implies E\left[ \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \right] &\leq & \underset{i \in [1, \dotsc, n]}{\text{min}} E \left[\sum_{t=1}^T \hat{l}_t (i) \right] \\
&=& \sum_{t=1}^T l_t (i^*)
\end{eqnarray}
, in the book it is easily shown that $E\left[\hat{l}(i)\right] = l(i)$.
In view of the above inequality, we can show

\begin{eqnarray}
E[regret_T] &=& E\left[\sum_{t=1}^{T} l(i_t) - \sum_{t=1}^{T}l_t(i^*)\right] \\
& \leq& E\left[ \sum_{t=1}^{T} \hat{l}(i_t) - \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i)   \right]
\end{eqnarray}

Clearly, I am making some mistakes in the attempt above. I will be grateful if someone can point me to those and help clarify the reasoning in the book. I say my attempt is incorrect because, in the way I have shown, I completely disregarded the set $S_T$. Without this set, the book shows the regret to be $\mathcal{O}(\sqrt{T})$, whereas with the $S_T$ set the regret is shown to be $\mathcal{O}(T^{\frac{3}{4}})$

I don't think you wrote anything incorrect, it's just that you didn't finish your proof yet. How are you going to go from there to an actual bound on the regret? You're going to have to use the regret guarantee of the gradient descent algorithm. But we didn't run Gradient Descent on all of the time steps. We only ran it on the time steps not in $S_T$. So we get a regret bound for the steps not in $S_T$ from gradient descent, which is $O\left(\frac{n}{\delta}\sqrt{T}\right)$. And we have to use a separate bound for the time steps in $S_T$. The proof uses the easiest one: at each such step, at worst, the algorithm has loss $1$ while $i^*$ has loss zero, so the contribution to regret from that step is at most $1$, for a total of $|S_T|$, which in expectation is $\delta T$.

As a sidenote, I am not sure that independence of $i^*$ and $\hat{\ell}_t$ is really being used, maybe it is just linearity of expectation (?).


Correctness of the greedy algorithm I am trying to solve the following problem:
Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.

For instance, if the given matrix is:

There can be 2 blocks which can be extracted out of this.

My Solution:
I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.

The algorithm is as follows:

1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columns
in this row from left to right.

2) If a zero is encountered at a position (i,j), I check if this is a possible
contender to be the top-left corner of a 2x2 block consisting of all zeros -
which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.

3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and a
counter is incremented.

4) Steps 2 through 3 are repeated for all rows from the top to bottom.

5) I restore the original matrix in the problem, and start again from the top-right corner
of the matrix (0, N) - N being the number of columns in the matrix, and iterate along
all the columns in this row, from right to left.

6) If a zero is encountered at a position (i,j), I check if this is a possible contender
to be the top-right corner of a 2x2 block consisting of all zeros - which would be the
case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.

7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and a
different counter is incremented.

8) Steps 6 through 7 are repeated for all rows from the top to bottom.

9) Likewise, the matrix is traversed two more times from bottom-left and bottom-right
corners, checking for a '0', which can be a possible bottom-right or bottom-left corner
for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on
the original matrix given in the problem - i.e. changes made in top-left traversal are
discarded while traversing the matrix from top-right and so on.

10) The 4 traversals of the matrix give us 4 different counters, and the maximum of
these 4 values is returned as the result.

So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.

Thanks!

If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.

But there is an 8 blocks solution (on the right).

The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.

Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.


Finding infinitely many Myhill–Nerode equivalence classes I need to prove the following languages are not regular and I'm having a
tough time identifying the equivalence class that can have an infinite
index.
How would I go about doing these? I know how to prove it after finding
the equivalence class but any tips on how to identify the one that has
the infinite index?
I know I should find the equivalence class where there are distinct
extensions for each string belonging to $L$, but could anyone help me
out on these 2:

$0^m  1^n$ where $m$ is even or $m$ is greater than $n$

$0^m  1^n$ where $\text{gcd}(m,n)=1$.

Let's consider your second example (the first example is easier). We will be interested in
$$
F(m) = \{ n : 0^m 1^n \in L \} = \{ n : \gcd(m,n) = 1 \}.
$$
If $F(m_1) \neq F(m_2)$, then $m_1$ and $m_2$ belong to two different equivalence classes.
From $F(m)$ you can recover the set of primes dividing $m$: $p \in F(m)$ iff $p \not\mid m$. In particular, this shows that if $p_1 \neq p_2$ are two different primes, then $F(p_1) \neq F(p_2)$. Since there are infinitely many primes, we conclude that there are infinitely many different equivalence classes.
The first example can be analyzed in a similar way (considering only odd $m$).


Are chaotic systems computable in polynomial time Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed.

Say, for instance, as input we have a start configuration of the chaotic Rule 30 cellular automata and a time-step $t$, and as output, we require the configuration at time-step $t$.

What can be said about the computational complexity of such a computation?

Wolfram's rule 30 is a one dimensional cellular automaton.
If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such  CA is linear in $t$.


Moving an edge in a weighted tree to maximize longest path length Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.

Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:

The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.

One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.

My question is the following: could we do better than brute-forcing all possibilities?

Hints:

When you remove an edge from the graph, you split it into two trees.

Given a tree, can you find the longest path in that tree?  (It's not hard.)

Given two trees, can you find which edge to add to make the longest path in the resulting graph as long as possible?  (Hint: first find the longest path in each of the two trees.  Then..)

This is your exercise, so I'll let you take it from here.  That should give you plenty to work with.


create new data from trained ANN I use a very simple neural network to make classification between classes. Once my ANN is trained I'm able to present new and unknown data, and get a good classification.

Is there a simple way to reverse the process and create an artificial data, knowing at which class it should belong ?

What would be the method name ?

Thanks a lot !

Of course you can create artificial data.  Simply pick the inputs to the neural network randomly; that's an artificial instance.  You can run it through the neural network and tell what class the neural network will assign to it.  That doesn't mean you know what class it should be given, or what is the correct class; there's no way to get that (you can't get something from nothing).


FA for |w| divisible by 3 or number of zeros divisible by 2 Working on a question were I should construct a deterministic finite automaton for the language

$L=\{w\in \{0,1\}^* \mid |w| \mod 2 =0 \lor |w|_0 \mod 3 =0 \}$

The DFA for the two sublanguages is clear, and also howto construct a nondeterministic automaton from these. However my DFA look horrible complicated. Is there a better one than this:

Only six states are required. Indeed, you can accept the language of all words of even length using two states, and the language of all words whose number of 0s is a multiple of three using three states. Using the product construction, you obtain a DFA for your language using only six states.

We can easily show that six states are required using Myhill–Nerode theory, by considering the following six words:
$$
\epsilon,0,00,1,10,100
$$
Details left to reader.


Complexity analysis using big - O, Omega and Theta notation I was reading a research paper and there I read the following:

$t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\left(n^{\alpha}\right)$ for some $\alpha \in(0,1)$.

It also says $t=O\left(d^{2} \log n\right)$ outperforms $t=O\left(d^{2} \log _{d}^{2} n\right)$ in the regime where $d=O(\operatorname{poly}(\log n))$

I am not sure how to verify these statements? I understand the basics of all the complexity notations, but how can we mathematically prove this?

When $d = \Theta(n^\alpha)$, we have $\log_d n = \Theta(1)$, and so there is no difference between $d^2\log_d^2 n$ and $d^2\log_d n$ (or rather, the two differ only by a constant factor).

When $d$ is polylogarithmic in $n$, $\log_d n = \log n / \log d = \Theta(\log n/\log \log n)$, and so $\log^2_d n = \Theta((\log n / \log\log n)^2)$ is asymptotically larger than $\log n$.

For what values of $d$ are $\log^2_d n$ and $\log n$ asymptotically the same? We need $\log^2n/\log^2d = \Theta(\log n)$, and so $\log d = \Theta(\sqrt{\log n})$, i.e., $d = 2^{\Theta(\sqrt{\log n})}$. This is more than polylogarithmic but less than polynomial in $n$.


Reducing from Hamiltonian Cycle problem to the Graph Wheel problem EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this post, the answer is a proper solution.

Is there a way to "polynomialy" reduce the problem of finding graph wheel $W_{n}$ to the problem of detecting Hamiltonian Cycle
(or vice versa) ? The ultimate goal is to show that finding $W_n$ is NP-complete problem. So far I can show that the problem is in NP. To show that I claim that given an input of graph it is possible in polynomial time to check every vertex and to make sure that it has three edges(except the hub): one goes to the hub, one goes to the next vertex and one to the previous vertex. By checking every vertex in this fashion one can make sure the "ticket" indeed represents $W_{n}$.

As far as converting from the Hamiltonian Cycle problem to the problem of fining $W_n$ goes I have encountered that $W_n$ has many Hamiltonian cycles inside it.It is easy to see if one imagines a wheel with  a hub and bunch of spokes. Every triangle created by the spokes forms a Hamiltonian cycle as well as any other "closed loop" formed inside a given $W_{n}$.

The intriguing part is the fact that only one vertex is in "the way" and that vertex is the hub. Is the hub of the wheel main culprit in figuring out the conversion ?

We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$. $G$ has a Hamiltonian cycle if and only if $G'$ has a $W_{n+1}$. It is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W_{n+1}$ wheel (just set $v$ as a center). On the other hand, if $G'$ has a $W_{n+1}$ then there are two possibility:

$v$ is the center of $W_{n+1} \rightarrow G $ has a Hamiltonian cycle.
Another vertex $u$ is the center of $W_{n+1}$ in $G'$. So both $deg(u) = deg(v) = n$. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.

P.S1: By $W_n$ I mean the wheel with $n$ vertex.

P.S2: In this proof we say if we fix $k=n+1$ (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case $k$ is as input parameter.


Comparison Procedure in Robinson's Unification Algorithm I'm studying the Principal Type (PT) Algorithm in Basic Simple Type Theory by J. Roger Hindley.
One step to find the PT of a term is the Unification of types. The Robinson's Unification Algorithm uses a comparison procedure like as follow:

Comparison Procedure

Given a pair $(u, v)$ of types, write $u$ and $v$ as symbol-strings, say

$u \equiv s_1 ... s_m$ and $v \equiv t_1 ... t_n$ $(m, n >1)$

where each o f $s_1,... , s_m$, $t_1, ... , t_n$ is an occurrence of a parenthesis, arrow or
variable.

If $u \equiv v$, state that $u \equiv v$ and stop.

If $u \not \equiv v$,  choose the least $p < \min(m, n)$ such that $s_p \not \equiv t_p$;
 it is not hard
to show that one of $s_p$, $t_p$, must be a variable and the other must be a left
parenthesis or a different variable. Further, $s_p$ can be shown to be the leftmost
symbol of a unique subtype $u^*$ of $u$. (If $s_p$ is a variable, $u^* \equiv s_p$.) Similarly
$t_p$ is the leftmost symbol of a unique subtype $v^*$ of $v$. Choose one of $u^*, v^*$ that is a variable and call it $a$. (If both are variables, choose the one
that is first in the sequence given in Definition 2A1.) Then call the remaining
member of $(u^*, v^*)$ $\alpha$; the pair $(a, \alpha)$ is called the disagreement pair for
$(u, v)$.

My issue is with the Note bellow:

3D5.1 Note To prove that $p$ exists in the case that $u \not \equiv v$ in the comparison
procedure we must show that it is not possible to have

$t_1 ... t_n \equiv s_1....s_m t_{m + 1} ... t_n$

with $n > m$. This is left as a (rather dull) exercise for the reader.

I disagree with this note. I can image, say, $u \equiv a \rightarrow b$ and $v \equiv a  \rightarrow b  \rightarrow c$, where no $p$ is possible.

Maybe I'm missing something!
How $p$ is always possible?

As asked, the definition of types is given as follow:

2A1 Definition (Types) An infinite sequence of type-variables is assumed to be given,
distinct from the term-variables. Types are linguistic expressions defined thus:

i.   each type-variable is a type (called an atom);

ii. if $\delta$ and $\rho$ are types then $(\delta \rightarrow \rho)$ is a type (called composite type).

2A1.1 Notation  Type-variables are denoted by "a", "b", "c", "d", "e", "f", "g", with
or without number-subscripts, and distinct letters denote distinct variables unless
otherwise stated.

Arbitrary types are denoted by lower-case Greek letters except $\lambda$.

Parentheses will often (but not always) be omitted from types, and the reader
should restore omitted ones in such a way that, for example,

$\rho \rightarrow \sigma \rightarrow \tau \equiv (\rho \rightarrow (\sigma \rightarrow \tau))$

This restoration rule is called association to the right.

It looks like the answer is that, to be syntactically valid, composite types must be fully parenthesized.

In particular, $a \to b \to c$ is not a syntactically valid type (per definition 2A1).  2A1.1 introduces "syntactic shorthand": when they write something like $a \to b \to c$, it should be understand that they actually mean $(a \to (b \to c))$.

The Note appears to be valid when we restrict to syntactically valid types.  Thus, your example is not actually a counterexample.


How to iterate the Hardy-Ramanujan integers quickly The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:
$$
\begin{array}{lll}
  1 & = & 1\\
  2^1 & = & 2\\
  2^2 & = & 4\\
  2^1 \times 3^1 & = & 6\\
  2^3 & = & 8\\
  2^2 \times 3^1 & = & 12\\
  2^4 & = & 16\\
  2^3 \times 3^1 & = & 24\\
  2^1 \times 3^1 \times 5^1 & = & 30\\
  2^5 & = & 32\\
  2^2 \times 3^2 & = & 36\\
  2^4 \times 3^1 & = & 48\\
  2^2 \times 3^1 \times 5^1 & = & 60\\
  \vdots
\end{array}
$$
As you can see, the exponents don't really follow much of an order that I can see. I thought perhaps the exponents increased in some way, but we have $288 = 2^5 \times 3^2$ shortly followed by $480 = 2^5 \times 3^1 \times 5^1$.
Is there a method to iterate these integers quickly?
I can only see a simple way of listing all of them below some upper bound $u$. I find the maximum exponent for $2$ by $\lfloor \log_2(u) \rfloor$, find the maximum # of primes, and iterate all decreasing sequences of exponents $\leq \lfloor \log_2(u) \rfloor$.

I'm very happy that the site linked me to How can I generate first n elements of the sequence 3^i * 5^j * 7^k?. It was a critical stepping stone, which enabled me to solve my own question after lots of thinking.

First I want to elaborate on that answer a bit, as it took me a while to understand and code it.
We want to iterate $3^i 5^j 7^k$.
The next element must be one of $3 x, 5 y, 7 z$, where $x, y, z$ is a previous number in the sequence. This is because $x < 3 x, y < 5 y, z < 7 z$, and $3 x, 5 y, 7 z$ satisfy the constraints.
For $x$, we start with the first element in the sequence. We increment it's position whenever $3 x$ is the smallest out of $3 x, 5 y, 7 z$. To see why, we've already included $3 x$ in the sequence, for all $x$s in the sequence so far. So the only possible $3 x$ that can be inserted in the sequence, is if $x$ is the new element we just inserted.
Similarly for $y$ and $z$.
The following code iterates this sequence:
def main():
    x = 1
    y = 1
    z = 1
    S = []
    x_iter = iter(S)
    y_iter = iter(S)
    z_iter = iter(S)
    for _ in range(20):
        m = min(3 * x, 5 * y, 7 * z)
        S.append(m)
        if m == 3 * x:
            x = next(x_iter)
        if m == 5 * y:
            y = next(y_iter)
        if m == 7 * z:
            z = next(z_iter)
    print(S)

The Hardy-Ramanujan Integers can be defined as the integers $2^{e_1} 3^{e_2} 5^{e_3} \cdots$, s.t. $e_1 \geqslant e_2 \geqslant e_3 \geqslant \cdots \geqslant 0$.
It seems that these two problems are related, and indeed they are the same, if we re-write the Hardy-Ramanujan Integers by removing the decreasing exponents constraint, as $2^{e_1'} (2^{e_2'} 3^{e_2'}) (2^{e_3'} 3^{e_3'} 5^{e_3'}) \cdots$.
Now the only issue is that compared to the previous problem, our list of bases is infinite. But note that a new prime $p$ can only be included in the sequence, if it's smallest form, $2^1 3^1 \cdots p^1$, is less than the next sequence element, produced with primes $< p$. So we only need to introduce a new prime when this occurs.
Before this occurs, The exponent of $p$ is 0. Any prime $> p$ will give a sequence element bigger than $2^1 3^1 \cdots p^1$, so does not yet need to be considered.
This gives the following code:
import math

from sympy import nextprime

def main():
    S = [1]
    primes = [2]
    next_prime = nextprime(primes[0])
    # The smallest Hardy-Ramanujan integer that includes `next_prime`
    next_prime_product = primes[0] * next_prime
    candidates = [1]
    candidate_S_indexes = [0]
    for _ in range(20):
        m_options = [
            math.prod(primes[:i + 1]) * candidate
            for i, candidate in enumerate(candidates)
        ]
        m = min(m_options)
        if next_prime_product < m:
            # Add a new prime & candidate
            m = next_prime_product
            primes.append(next_prime)
            next_prime = nextprime(next_prime)
            next_prime_product *= next_prime
            candidates.append(m)
            candidate_S_indexes.append(len(S))
        S.append(m)
        for i, m_option in enumerate(m_options):
            if m_option == m:
                candidates[i] = S[candidate_S_indexes[i] + 1]
                candidate_S_indexes[i] += 1
    print(S)

P.S. I saw some answer in Haskell in German before at:

A good algorithm for A094348?
A025487Haskell - seqcomp

but could not understand the German at all, nor the Google-translated version, nor the Haskell code. But I'm quite satisfied with my algorithm here. It feels pretty optimal.


Using persistence on a constant database I'm quite new to understanding persistent data structures, so bear with me.

Consider some database with data of the form $(\text{id}, d_1, d_2)$. The last two could e.g. mean production data and sales date, respectively.  The database is constant, i.e. we will not be adding or removing data points.

Let $n$ be the number of items in the database. I want to be able to do the following query:

  Query$(a,b,s)$: Return the number of objects that have $a\leq d_1 \leq b$  and $d_2 \leq s$.

I want to be able to perform the query in $\mathcal O(\log n)$ time, with the best possible space and preprocessing time complexities. My question is how could one construct a persistent data structure that solves this problem?

I think that I need to use timestamps that relate to the $d_1$ and/or $d_2$ in some way. However, I'm not quite sure how.

Yes, you can do this in $O(\log n)$ time.  Use a sweep-line algorithm together with a persistent tree data structure.

Imagine the point $(d_1,d_2)$ as being on a grid, with $d_1$ as the value of the $x$-coordinate and $d_2$ as the value of the $y$-coordinate.  Your sweep line is a horizontal line, namely, at time $t$, the sweep line is the line $d_2=t$.

You will build a data structure that stores all the points $(d_1,d_t)$ such that $d_2 \le t$.  You can use a balanced binary search tree, keyed on the value of $d_1$.  This data structure will let you answer the query Query$(a,b,t)$ in $O(\log n)$ time.

Now you're going to gradually increase the value of $t$ (sweeping the line upward), and adjusting the data structure as you go.  You'll save a copy of the data structure for each value of $t$ that occurs in the $d_2$-database.

This sounds like it requires $O(n^2)$ space.  However, there's a clever trick.  Use a persistent data structure to store the trees.  As you move the sweep line upward, you insert more items into the tree.  A persistent data structure will let you pick any time $t$ and do a lookup into the state of the tree at time $t$.  This lets you answer Query$(a,b,t)$ in time $O(\lg n)$.


Prove that $|P(X)| = 2^{|X|}$ Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.

Basis
    $$ |X| = 0 $$
    $$|P(X)| = 2^{|X|} = 2^0 = 1$$
    True. Any set with zero elements takes the form $\{\}$, and thus its power set will be $\{\{\}\}$. One element.

Inductive Step

We must show:
    $$|P(X+1)| = 2^{|X+1|}$$
    Thus:
    $$|P(X+1)| = 2^{|X+1|} = 2*2^{|X|} = 2*|P(X)|$$
    This is true because, if $X$ as a set grows by one, the power set, for every member in its set now has a new binary choice: include the new element or not. Thus the power set doubles.


Definition of $D^P$? What is the definition of the complexity class $D^P$?

In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too.

Is it the same as: "A language L is in the class $DP$ if and only if there are two languages $L_1\in NP$ and $L_2\in coNP$ such that $L = L_1\cap L_2$" (Def. 17.1 from Papadimitriou - Computational Complexity (1994))?

Note: In the stated definition it says $DP$ not $D^P$. But I was wondering if it is the same.

The class $\mathsf{D^p}$ was originally introduced in the context of studying the facets of the traveling salesman polytope. It contains all languages that can be considered as the intersection of a language in $\sf NP$ and one in $\sf co\text{-}NP$. Formally, $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$. It first appeared in [1].

[1] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Journal of Computer and System Sciences 28.2 (1984): 244-259.


Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for any functions $T(n),U(n)$, such that $U(n)$ is time-constructible and

$$n \leq T(n) = o\left(\frac{U(n)}{\log T(n)}\right).$$

This proof is based on the existence of the Universal Turing machine simulating any Turing machine with time complexity $T(n)$ in time $T(n) \log T(n)$.

I understand (and believe) the proof that every $k$-tape Turing machine can be simulated by a two-tape Turing machine with a logarithmic overhead. However, I understand this construction only if the simulated Turing machine is fixed, not in the case of the Universal TM simulation.

I see one "problem" in the reasoning given in the cited paper (and also in several standard books on computational complexity) related to the construction of the Universal machine. This "problem" is that in the Universal machine simulation, one computational step of a simulated machine is supposed to be executed in constant time by the Universal machine. In other words, the length of the description of the simulated machine is supposed to be constant.

But is this OK? Since in the proof of the Time Hierarchy Theorem, the input given to the simulated Turing machine is exactly this description, and thus, the description is somehow dependent of $n$. I am aware of that the description can be lengthened by a sequence of leading bits, but this does not seem to solve this problem.

That is, I cannot figure out why the computation step of a simulated machine can be supposed to be executed in a constant time by the Universal machine. The paper of Hennie and Stearns does not pay much attention to this, it merely states that this time is something that is implicitly assumed to be a constant. Similarly in the textbooks I have read on the topic.

I simply cannot figure out why the time complexity of the simulation is $T(n)\log T(n)$, and not $n T(n) \log T(n)$.

I am almost sure that I am missing something. However, I am trying to understand this for a relatively long time and somehow I cannot figure this out.

I'm referring here to the proof of the hierarchy theorem as I am familiar with it, in which I don't see the problem you mention.

We define the language
$L=\{(M,w): M $ does not accept $(M,w)$ within $\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\}$ (where $t$ is the time function we are working on).

We show that $L$ is decidable in $O(t(n))$ using the universal machine, and in the universal machine each step is indeed dependent on the size of the machine, which is why we have $|M|^3$ in the denominator (the 3 is just some upper bound on the computations needed to simulate a step).

For completeness of the answer: when we try to reach a contradiction, then we assume that there exists a machine $T$ that decides $L$. After this assumption, the encoding of $T$ is fixed, and then a simulation of a single step really does take constant time, and we can reach a contradiction by taking a long enough $w$ to increase the length of the input without changing $T$.


What is the output of below algorithms on a disconnected Graph? If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run Dijkstra's algorithm on it then it will return shortest path in the connected component only , but we maintain a predecessor array in all the algorithms which has information about the parent from which the node learnt the path so it will values for all the vertices , so even if we have a disconnected Graph then still other vertices will also be printed .

So output is Graph right for all the algorithms whether the graph is undirected or directed ?

No.  The output of Dikstra's algorithm is a set of distances to each node.  It's not a graph or a tree.  This is true no matter whether the input graph is connected or disconnected.  The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source).  The standard algorithm doesn't print anything, so if you are printing something, you're probably adding something extra to the standard algorithm, and we can't analyze that without seeing what your variation of the algorithm is.