texts: Construction of a counter automaton for the complement of the palindromes

texts:
How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = \{0,1\}$?

The definition I am using for 1-NCAs consists of:

$S$, the set of states,
$\Sigma$, the alphabet ($\Sigma = \{0,1\}$ in our case),
$s_{0} \in S$, the initial state,
$F \subseteq S \times \{\text{zero},\text{nonzero}\}$, the set of accepting states, and
$\delta : S\times\{\text{zero},\text{nonzero}\}\times A \rightarrow S \times \{-1,0,1\}$, the transition function.

Given a word $w = x_1x_2\ldots x_ny_1y_2\ldots y_n$, I know that if $x_i$ is not equal to $y_{n-i+1}$, the palindrome requirement fails. I have a feeling that the counter has something to do with that distance in between those letters but formalizing this is what I am stuck at.

Since a 1-NCA is the same thing as a NPDA (nondeterministic pushdown automaton) with only one symbol in the stack alphabet, I would accept answers using such PDAs also. This is especially since I find very few texts discussing counter automata.


texts:
Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them?

Is this problem NP-Hard?

For example, given the $4$ unique numbers smaller than $2^3$

011
100
101
110
 ^^

The numbers are still unique if we remove the leftmost bit from each number. So for $k = 2$, the answer is yes: we keep bits {0, 1} (the rightmost bit is here defined as the bit with index 0).

I want to solve the above problem as a precomputation step for integers less than 20 bits, so for my application an exponential algorithms could be allowed. Then it would be great to minimize $k$ and then break ties in such a way that the number of gaps between the indices that are kept is minimized. For example, {0, 1, 2, 5, 7} has two gaps: between 2 and 5 and between 5 and 7. This precomputation should lead to a great hash function for a set of integers. In my application the sets of integers don't change later.


texts:
It is already possible to let a computer drive the human brain to some limit like for example in the medical world, but will it be possible to let the human brain control a computer system by directly connecting the human brain to it in order to cause the computer to behave in a (some) non-linear way.
It should be a reverse order of the current Real Mode -> Protected Mode order (i.e. Protected Mode -> Real Mode), for several reasons.

and how can the PC boot directly from the human brain?
..and follow the instructions from the core instead of the processor?
what would be an estimate of the research costs?

Btw. The tag is not correct, this question has nothing to do with Machine Learning, but it's the only tag that was the least miserable for this question.


texts: Unable to understand control flow in KMP algorithm

texts:
I am facing problem in understanding the KMP algorithm as given in the book  "Introduction to Algorithm" by Cormen et. al. (Chapter 32):

With respect to the above algorithm, I have following question:

In both the algorithms, where exactly (which line number?) while loops, if and for loop ends? It is difficult to visualize the functioning of the algorithm without knowing the 'end' for each loop and conditional statements.
On line number 6 in KMP-MATCHER() and COMPUTE-PREFIX-FUNCTION(), what is the need of checking q>0 and k>0, when we know q and k will always be 0 or positive. Or do the authors want to test q!=0, k!=0?
If q=0 and i=1 in KMP-MATCHER(), from 6 to 10 which line will be executed (If I get answer to 1- above then I can find this)


texts: Why Deterministic PDA accepts $\epsilon$ input but DFA not

texts:
I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final state.

In DFAs we don't consider $\epsilon$ transitions, while in PDAs we do include them. Why?


texts: How to guarantee the minimum path removed from priority queue is the shortest path after all infinite vertices relaxed

texts:
I readed the proof of Dijkstra's algorithm in "CLRS"，and the code in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Figure 24.7 in CLRS proofs the correctness of Dijkstra's algorithm.

The proof said that we should add the minimum path vertex in set V - S,
But the code add the minimum path vertex in priority queue to SPT.

My question is how to guarantee the vertices that not be relaxed currently (which distTo is POSITIVE_INFINITY) will never shorter than the removed  minimum vertex after the following loop.

In another word, should we consider the vertices that not be relaxed currently when we remove the minimum path vertex from set V - S?

Forgive my English, please.


texts: Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}

texts:
I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option.

NPDA are not very intuitive to me. The only solution I found online is:

I don‘t really understand how it works and also I‘m not allowed to use final states. The only way an input is accepted is by emptying the Stack (how we do it at my university).

Thanks in advance!


texts: Is what the all-zeroes instruction does considered in machine instruction design?

texts:
I remember using a simulated machine with with a minimal instruction set in university. In particular I remember that the instruction that consisted of all zeroes loaded was a LOAD instruction. So, if you made a mistake and began executing empty memory then it would simply keep executing until it ran out of address space.

x86 appears to perform an ADD on empty memory, so similar behaviour to the example above.

All zeros in 6502 on the other hand, corresponds to the BRK instruction which activates a software interrupt so executing empty memory quickly puts the machine in a known state.

My understanding is that 6502 was designed to be written by humans, whereas (at least modern) x86 is designed for compilers to output. Historically, when a machine instruction set is designed, how much attention has been paid to the specific representation each instruction has, given that it can have real effects? I've focused on what the all-zeroes instruction does because I expect that would be the most common instruction to be accidentally executed, but I'd be interested in considerations relating to other instruction representations as well.


texts: Can we minimise regular expressions using known DFA minimisation algorithms?

texts:
Of course, converting NFA to DFA is not a problem. But what about the other direction?

My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.


texts: Syntax and formal grammar of a formal language

texts:
For  a formal language, I wonder what differences and relations are between its syntax and its formal grammar.

A formal grammar
is a set of formation rules
that describe how to generate the strings that belong to the formal language.

Wikipedia says that syntax

  is "the study of the principles and processes by which sentences are
  constructed in particular languages."

  the term syntax is also used to refer directly to the rules and
  principles that govern the sentence structure of any individual
  language.

So I wonder if for a formal language, its syntax and its formal grammar the the same concept? Thanks!


texts: What does the complexity class $\mathsf{XP}$ stand for?

texts:
$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page as "Fixed-parameter Tractable for Each Parameter", but I fail to see how adding "for each parameter" to the description causes such a significant change to the definition compared to $\mathsf{FPT}$, which contains problems solvable in $O(f(k)\cdot n^{O(1)})$ time.

The complexity zoo page mentions the book it was defined in, Parameterized Complexity, but I don't have access to it right now.


texts: Checking large number of configurations with multiple constraints

texts:
I have a very large number of constraints such as:

$ A1 \land B1 \land C1 \land D1 \land E1 \land F1$
$ A2 \land B2 \land C2 \land D2 \land E2 \land F2$
$ A3 \land B3 \land C3 \land D3 \land E3 \land F3$
$ A4 \land B4 \land C4 \land D4 \land E4 \land F4$

Here a constraint is a condition. For example, A1 is (response time < 10). All the condition needs to be satisfied such that the configuration is feasible. For instance, the configuration 1 needs to have A1, B1, C1, D1, E1 and F1 =1. How can I quickly check which configurations are valid? At moment I'm using a CSP (choco-solver) and iterate over each configuration and check the conditions. Is there a better (faster) way to do this rather than just checking the configuration one by one?


texts: Worst-case time algorithm?...which one is faster?

texts:
Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why?

Is A more faster than B, for all $n>n_0$ if $g(h)=Ω(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=O(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=Θ(f(n)\log n)$?


texts: Is matrix "adjoint-squaring" faster than general matrix multiplication?

texts:
The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are related to each other in some known way, it's sometimes possible to get a speedup. For example, computing $U \cdot V$ is quite easy if you're promised that $V = U^{-1}$.

I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication.

Can the special case $U \cdot U^\dagger$ be computed asymptotically more quickly than the general case $U \cdot V$?


texts: Is Bounded Waiting satisfied for this 2 process Solution?

texts:
This is my new post linked with my previous post.

Is bounded waiting satisfied in the 2 Process Solution?

The answer in that post was very useful and cleared many concepts, but I just want to apply that answer for this example, that how BW works here .

Especially, I want to know this definition works for this example.

  Define $k$-bounded waiting for a given mutual exclusion algorithm to
  mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.

Here, the Question comes

  What can be said bout the Bounded Waiting of this 2 process solution"

<------- P1 ------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

<-------- P2 -------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}


texts: Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

texts:
The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$

How can I prove by induction that this is $\Omega(n^2)$?

I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$


texts: Which gates are “pre computation” universal?

texts:
In the following, by “functions” I will mean 2 input 1 output Boolean logic functions (for conciseness).

A function is called “universal” if by using it (sometimes multiple times, chained together), you can construct all 16 functions.

However this isn’t the whole picture. In some esoteric circuit computing models, you keep track of all input/output variables and their negations. This allows you to have circuit universality once you get an AND and an OR gate. How? Consider if I have a large circuit composed of many NAND gates.

Given an individual NAND gate

c = a NAND b

we have

c = !a OR !b
!c = a AND b

Using these substitutions throughout the circuit, we can compute the original function we were computing with NAND gates, using only OR and AND gates. (With O(num inputs) pre computation time)

However, for example, linear computing only give us XOR/NOT, and there doesn’t seem to be an easy way to do some pre computation in the same manner.

To give a formal definition: call the function g a “NOT pre-computation universal function” if it can construct all functions, given the inputs and their negations, and outputting the output and its negation.

Which functions are “NOT pre-computation universal”? Is there a name for this idea and it’s generalizations (such as when you provide all pairwise applications of some function f) in the literature?

To generalize this, we can say a function f is “g pre-computation universal” given some function g if by being given the two inputs a,b and g(a,b), all 2 input 2 output functions can be produced (with a third output of g(first output, second output) to allow the substitution like above)


texts: Complexity of the algorithm to find occurences of a given number in a given array

texts:
I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm:

// A is the input array.
// |A| is the size of the input array.
i = 1
j = 1
m = 0
c = 0
while i < |A| {
    if A[i] == A[j]
        c = c + 1
    j = j + 1

    if j > |A|
        if c > m
            m = c
        c = 0
        i = i + 1
        j = i
}
return m


texts: Algorithm for finding largest subset with equal number of even and odd elements

texts:
A sequence of positive integers $a_1, ..., a_n$ is given. Compute the
  length of the largest continuous subsequence such that the number of
  even integers is equal to the number of odd integers in the subsequence.

I have thought that we could take all those integers mod 2 and store those in an array, then take two pointers $i=0,j=n-1$ and somehow sweep the table until #(even) = #(odd) is found in the subsequence inside, so that $j-i+1$ would be the optimal length. But I don't know how exactly to choose which of the two pointers to increase/decrease each time, so that I get an $O(n)$ algorithm.

Is my algorithm on the track, or can't it be used here? What algorithm do I need to apply and how can I think of its idea? (It would be preferable if this problem could be solved without using special data structures, such as AVL, segment, suffix trees, etc.)


texts:
Assumptions
Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" recurrence relations):
$$T(n) = \;?$$
For example:
$$T(n) = aT\left(\frac{n}{b}\right) + h(n)$$
We could have this recurrence where the input is an array of length $n$ and $a$ and $b$ are determined by particular functions of the array values (e.g. max value, min value, median value, etc.)
This is "unpredictable" in the sense that we do not know precisely how the tree will be structured for any given $n$.
Let's say that in the worst case the following holds:
$$T(n) = \Theta(f(n))$$
Let $L(T(n))$ be the function mapping to the total work (number of basic operations) done at the leaf level (base cases) of the recurrence relation $T(n)$. Now let's say in the worst case of $L$ (not $T$), the following holds:
$$L(T(n)) = \Theta(g(n))$$
Question
Does the following hold:
$$L(T(n)) = \Theta(g(n)) \implies T(n) = \Theta(f(n))$$
That is to say, if the work at the leaf level is worst case, does this imply that work of the total recurrence tree is worst case?

This has particular value if you don't necessarily know how the recurrence is broken up or divided throughout the tree. Perhaps you could bound the worst case work done at the leaf level and reverse engineer the tree to show the worst case overall. Alternatively, though not as useful, you may be able to prove the following:
$$T(n) = \Theta(f(n)) \implies L(T(n)) = \Theta(g(n))$$

Here is an example recurrence:
$$T(n, m) \leq \begin{cases}
n^2 & m = 1\\
m^2 & n = 1\\
O(\min(n,m)) + \displaystyle \max_{i \in \{1 \ldots \min(n,m)\}} \left\{ T(n - i, i) + T(i, m - i)\right\} & \mathrm{otherwise}
\end{cases}$$
In this case, determining the splits is rather difficult. However, analyzing the worst case on the leaf nodes is rather simple. When we think about the recursion tree, the work at the leaves will be maximized when $n$ and $m$ are as large as possible. Namely, $T(1, m - 1) + T(n - 1, 1) = (m-1)^2 + (n-1)^2$. Now, if we know this will be the worst case overall, e.g. $$L(T(n,m)) = \Theta(n^2 + m^2) \implies T(n,m) = \Theta(f(n,m))$$
We can deduce the splits in recursion that made it this way:
$$\begin{align*}
T(n,m) &= T(n-1, 1) + T(1, m-1) + O(m + n)\\
& = \Theta(n^2 + m^2)
\end{align*}$$


texts: Find cut vertex in tree with constraint on the size of largest component

texts:
I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:

remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
take back the original graph and remove the cut vertex. Check the size of the largest connected component

This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...


texts:
Consider the following definition of 3-friends:

person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or  person 1 is friends with a friend of a friend of person 2.

In graph-theoretical terms, person 1 is a 3-friend with another person 2 if there is a path of length 1, 2 or 3 from vertex 1 to vertex 2.

Is there an efficient algorithm to find all the paths between say person 1 and all its 3-friends? (I.e. all the paths of length 3, all the paths of length 2, all the paths of length 1).

Or the only option is an exhaustive search?


texts: Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable

texts:
I want to prove that:
$\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable.

Here $w$ is a string and $B(n,w)$ is the set of all $n$-state machines that halt on input $w$ after exactly the maximum number of steps. I don't know how to prove this. I tried finding another language to apply the reduction method but also to no avail. Can anybody help me with this?


texts: Computer Networks Link layer error detection

texts: I am aware that Link-Link error detection and correction takes place as an optimization to the error detection taking place at the Transport Layer at the destination host's end. I was wondering if retransmission is possible in the link layer. Could someone please suggest a method that does not flout the end-to-end design principle?


texts: What machine learning training algorithm to use for this kind of string dataset?

texts:
I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent variable has more than 100 values in decision tree. I need help for choosing algorithm. Dataset is custom made and small. I am confused, since there are 100+ songs.

Dataset looks like this. Song is to be predicted. Every activity etc. comes from a predefined set of possibilities.

PS: It's not class assignment question. I made this database. I am also noob in ML.


texts:
I've been looking at various calculus with explicit substitutions for efficient implementation of normalisation of terms in the lambda calculus.

AFAICT there are basically two approaches: the λσ calculus of explicit substitutions, and the suspension calculus.  All others I found suffer from the fact that they cannot compose substitutions, so they sometimes require several traversals of the terms.

Between the two, the suspension calculus seems much more amenable to an efficient implementation, but the λσ calculus seems more elegant and I find it a lot easier to have an intuition for what it means.

So, how can I implement the λσ calculus, in a way that is competitive (in terms of efficiency) with the suspension calculus?


texts:
I am looking for an algorithm to solve the following problem:

INPUT: a set of $n$ points in the plane, $(x_1,y_1),...,(x_n,y_n)$.

OUTPUT: a set of $n-1$ axis-parallel interior-disjoint squares, such that the boundary of each square contains at least two points. (*)

Here is an example of input (left) and possible output (right) for $n=4$:

Efficiency is not a concern right now - the time complexity may be exponential in $n$ (since I will usually use this algorithm with small $n$'s).

My first thought was along the following lines:

For every pair of points, find a square that touches these two points.
In the resulting set of $n(n-1)/2$ squares, find a subset with $n-1$ squares that are interior-disjoint, or report that such a set does not exist.

The problem is that, for every two points, there may be infinitely many squares that touch them. For example, the points $(0,0)$ and $(10,7)$ are touched by any square with a side-length of 10 and lower-left corner in $0 \times [-3,0]$.

How would you approach this problem?

(*) NOTE: I don't know whether such a set of $n-1$ squares always exists. I want to play with points in order to gain some intuition about this question and maybe find a counter-example.


texts:
I'm gathering examples from everything that I've read about Dependent Type Theory mainly from Dependent types at Work paper.

This is my list so far of some dependent types (with abbreviations of mine):

[NVec]: $A^n$ vectors of length n with elements of type $A$
[NMMAtrix]: $A^{m\times n}$ matrices
[Fin]: Finite sets of size $n$
[SList]: Sorted lists
[NBTree]: Height-balanced trees of a certain height
[SBTree]: Sorted binary trees
[PAIR]: A pair of integers where the second is greater than the first

How can I justify that the types from my list are indeed dependent types.
I appreciate another example to add it to my list.


texts: Binomial trees in binomial heap with 27 elements

texts: How many binomial trees are in a binomial heap with 27 elements and how would you find this number?


texts:
I know that in the case of a 16 bit word, if we have x - 115 in decimal, the smallest x that would cause overflow would be (32767 + 115 + 1)= 32883 because it would represent a number that is larger than the largest positive integer we could represent in a 16 bit word.
However, I was wondering what would the largest value of x be? would it be (2^16)? which would cause 2 carries after the addition.  Or would the largest x be a number that would only result in 1 carry alone?


texts: Is there a correlation of zip compression ratio and density of information provided by a text?

texts:
I'll phrase my question using an intuitive and rather extreme example:

Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults?

I read somewhere that specifically the compression ratio for zip compression can be considered an indicator for the information (as interpreted by a human being) contained in a text. Can't find this article anymore though.

I am not sure how to attack this question. Of course no compression algorithm can grasp the meaning of verbal content. So what would a zip compression ratio reflect when applied to a text? Is it just symbol patterns - like word repetitions will lead to higher ratio - so basically it would just reflect the vocabulary?

Update:

Another way to put my question would be whether there is a correlation which goes beyond repetition of words / restricted vocabulary.

Tangentially related:

Relation of Word Order and Compression Ratio and Degree of Structure


texts: Non Deterministic PDA accepted language not clear

texts:
This is a PDA from the lecture slides I'm using:

They say it accepts all words that contain double a's. While it makes some sense it's not full proof.

What prevents the second a to be read in the left branch not the right? Or even a 3rd..4th a and so on? Is that the case of human Intervention like needed in PDA for oddpalindrome?

Also as far as I understand a PDA needs to read the whole input tape AND have an empty stack by the end which doesnt seem to be the case if the input is more than an a. What am I not understanding?


texts:
Given two languages $L_1$ and $L_2$, give a language $L'$ that both $L_1$ and $L_2$ reduce to.

I'm not quite how to do this. I know the solution is fairly simple. I know I can somehow represent $L'$ in terms of $L_1$ and $L_2$. Then I need to create a computable function that maps $L_1$ to $L'$ and either use the same function, or create a separate function that maps $L_2$ to $L'$.


texts: When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?

texts:
It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and "grandma" but can distinguish between "I'm going to see grandma" and "I'm reading a book on english grammar". (yes, I just tried it with my Android phone with vLingo app)

That is much improved (with Speaker Independent SR (i.e., no training)) over what I experienced with Dragon Dictate even using Speaker Dependent SR (with 30m of training).

So, I'm wondering whether my guess is right: When did the commercially available SR software start using grammar and sentence structure to "guess" the right speech?


texts:
I am confused on byte addressable/word addressable architecture.

I have studied MIPS implementation and I came to know that when the data is retrieved from main memory, it is shifted accordingly to convert it into a byte. But if this is the case, why do we need byte addressable? We can simply fetch a word shift it and operate on its 8 bits.

Or is it that the byte addressable architecture requires multiplexers to select a byte from a 32/64 word fetched from memory?

Please help me out.


texts:
I was thinking about the homework problem:

  Given $n$ vectors in 3D: $(\mathbf{v_1},\mathbf{v_2},\dots,
 \mathbf{v_n})$. Their coordinates are positive integers and less than $10^9$.
  We should split this set into $k$ groups in the way that each two
  vectors from one group are collinear and from different are not.

So, for example, the set $\big((2,2,2), (3,3,3), (4,5,4), (8,10,8)\big)$ should be split into 2 groups.

If we divide coordinates of each vector $\mathbf{v}$ by $\text{gcd}(x_{\mathbf{v}}, y_{\mathbf{v}}, z_{\mathbf{v}})$. then in each group vectors should be mutually equal and vice versa. So, the problem is to find the number of unique vectors in the set.

I need to develop an algorithm to calculate k efficiently.

1. I need an algorithm of $O(n)$ expected running time. I know that we could build this groups by sorting, but unfortunately I banned with sorting for this problem.

2. I suppose that we could build something with hashing and disjoint-set data structure.
The draft of the solution in this case is following:

Considering only x-coordinate we "hash" vectors into $m_x$ buckets by a hash-function taken from a universal set.
Each bucket we hash again considering y-coordinate. And again for z-coordinate.
For each received bucket we launch an $O(n^2)$ pairwise algorithm and form groups. There we willl need disjoint-set data structure to maintain formed groups.

This solution is simple but requires quite a lot memory. Are there any approaches to solve the problem?


texts: Bit complexity of $n$-th Fibonacci number using matrix multiplication

texts: I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations have complexity $O(1)$, but if we now consider their true complexity, for example $O(n)$ for addition, I don't know how to calculate its true complexity. Can anyone help?


texts: Formally describing a new domain specific programming language

texts:
I am about to implement a domain specific language for representation of social learning conventions. Part of the implementation is a formal description of a language - its 'calculus', symbols and logical expressions.

My approach would be to describe the language by describing its grammar but there are also concepts such as relations, dialogs, expectations that require more theoretic approach and the description of the logic.

I would like to ask for an example and a literature recommendation (papers, books) that would help me with this description. I feel relatively competent approaching this task so I am not asking for a total hand holding, but help from a theoretician in this area would be GREATLY appreciated.


texts: Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?

texts:
I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm:

But I couldn't understand what does $E(n)$ and $E(p)$ mean. I know that it has something to do with sets.


texts: Reference request: Introduction to reinforcement learning with hand calculation examples

texts:
For me, the most difficulty when it comes to learning about reinforcement learning is that there is not much to learn in the sense that without running some algorithm, it is very difficult to get a sense of how abstract RL framework is done in practice.

This is in contrast to a lot of the stuff you learn in related courses on optimization, game theory or even pure algorithm. In each of these courses, you have a large amount of examples where you can hand compute to obtain the solution (for algorithms, you can solve for shortest path etc by hand). It is also easy to compute the gradient, and calculate the value at each step using gradient descent algorithm for example in an optimization class, or compute the Nash equilibria in simple games. This allows one to better appreciate how the algorithms work.

Even for supervised machine learning, algorithms such as ANN, KNN, SVM etc. can be analyzed by hand, using step by step calculation.  However, this does not seem to be the case for reinforcement learning. Every article I have came across basically runs through the whole "state, action, reward" framework then goes on talking about MDP and Q, TD learning. Then applications that usually follows are not something that are easily programmed on a first try i.e. robotic acrobat, pole cart system etc.

Are there any introduction or tutorial to reinforcement learning where a problem is solved by hand? Meaning, you can actually compute the values at each step following a particular technique and perhaps obtain the optimal solution.

Even if not, are there any mathematical convergence analysis of reinforcement learning algorithms?


texts: What is the relationship between two definitions of Turing-computability of a partial function?

texts:
When one wants to know that whether a partial function $f \colon \Sigma^{*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{*}$ is Turing-computable, there are two methods that I think they are both useful.

We can define a total function $\bar{f}$ such that
$$ \bar{f}(x) = \left\{
\begin{aligned}
&f(x),&x \in \mathrm{dom}(f) \\
&\bot,&x \not\in \mathrm{dom}(f) \\
\end{aligned}
\right.$$
Thus, $f$ is Turing-computable if $\bar{f}$ is Turing-computable by a TM using $\bar{\Sigma} = \Sigma \cup \{ \bot \}$.
(Some answers use this definition. see [1] and [2])
Let $M$ be a TM, and We say $f$ is Turing-computable by $M$ if
$$M(x) = \left\{
\begin{aligned}
&f(x),&& x \in \mathrm{dom}(f) \\
&\bot,&&x \not\in \mathrm{dom}(f) \\
\end{aligned}
\right.$$
where $M(x) = \bot$ means that $M$ never halts on $x$. (This definition is introduced in my books.)

These two definitions are not equivalent, since $M$ can computes some functions whose domain is Turing-recognizable instead of Turing-decidable in sense of definition 2.

I want know that is the definition 2 more powerful? In another word, if $f$ is Turing-computable in sense of definition 1, can we prove that it is also Turing-computable in sense of definition 2?


texts:
What is the difference between a single processing unit of CPU and single processing unit of GPU?
Most places I've come along on the internet cover the high level differences between the two. I want to know what instructions can each perform and how fast are they and how are these processing units integrated in the compete architecture?
It seems like a question with a long answer. So lots of links are fine.

In the CPU, the FPU runs real number operations. How fast are the same operations being done in each GPU core? If fast then why is it fast?
I know my question is very generic but my goal is to have such questions answered.


texts: Trust in online platforms dealing with virtual goods

texts:
I am implementing an online platform, where third-parties sell virtual goods to clients on a subscription basis. Let's take for example ebooks as a virtual good in this case.
How can the third-parties trust my platform? How can they know that I don't cheat with the number of subscriptions I report back to them? Do any solutions exist for this or some papers? I can't possibly be the first with this kind of problem. The problem is I even don't know what to search for.


texts:
I am wondering at a high level the mathematics of the Polyhedral Model.

  The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of operations -- too large to be explicitly enumerated -- thereby requiring a compact representation. The polyhedral method treats each loop iteration within nested loops as lattice points inside mathematical objects called polyhedra, performs affine transformations or more general non-affine transformations such as tiling on the polytopes, and then converts the transformed polytopes into equivalent, but optimized (depending on targeted optimization goal), loop nests through polyhedra scanning.

I would like to understand the basic mathematical components of this but am having difficulty with the notation.

Specifically wondering what is going on in Figure 1 below. That is, where the polyhedra, lattice points, and affine transformations are, and how to represent/define them with mathematical notation. For instance, I haven't seen anything yet saying "a polyhedron from a loop is a tuple $p = (R, L, A)$ where $R$ is a set of loops, $L$ is a lattice and $A$ is a set of affine transformations, ...". Looking for the definitions of these 3 things and their relationship, as well as the relation between the loop variables and the what looks like is a matrix equation in the figure.

Figure (1) -^.

Figure (2) -^.


texts: How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5?

texts:
I'm trying to write a formal proof in automata theory to show a few properties of DFAs but I am having some trouble with this that I am trying to incorporate into my proof. I want to show how many languages $S$ there are such that $S\subseteq\{0,1\}^*$ and $\forall s\in S, |s|\leq 5$ where $s$ is a string.

I got that there are $2^1+2^2+...+2^5 = 62$ different strings such that $|s|\leq 5$ but that is where I am stuck. How many different languages can I create with $62$ strings? Would it simply be $62!$ ?


texts: Interpretation of Backtracking Algorithm Problem - weighted matching

texts:
I am attempting to resolve the following problem using Backtracking:

  Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ for the woman $j$ and $Q_{ij}$ is the preference of the woman $i$ for the man $j$.

  Depict an algorithm that follows the Backtracking technique to find the pairs of men and women whose sum of the products of the preferences are the highest possible.
  With help from the matrices
  $P = \begin{bmatrix}
1 & 3 & 2 & 0 \\
2 & 4 & 3 & 1 \\
0 & 3 & 1 & 2 \\
3 & 4 & 2 & 1 \\
\end{bmatrix}
$
  and
  $Q = \begin{bmatrix}
0 & 1 & 2 & 3 \\
4 & 3 & 2 & 1 \\
4 & 2 & 3 & 1 \\
3 & 1 & 4 & 2 \\
\end{bmatrix}
$
  and represent the exploration tree of the exploration of the search space of the solution. Indicate:

  How will you represent the solution and based on that, what are the restrictions of the problem and how will you calculate the value of the objective function.
  In the process of ramification, what will represent the levels and how will you generate the children of each node.

  Analyze the time complexity of the algorithm.

I have the basic ideas of how backtracking works but I am having trouble interpreting the problem. What does it mean by ... the sum of the products of the preferences ...?


texts: Show that the language L = { | M1 is a Turing machine that accepts 0} is Turing recognizable

texts:
Show that the language L = {< M1 > | M1 is a Turing machine that accepts 0} is Turing recognizable. I was told by my professor to go about this proof by giving an informal description of a Turing Machine 'V' that would accept 'M1' if and only if 'M1' was a Turing Machine that accepts 0.

Below I have the informal description I gave for the Turing Machine 'V'. I wanted to know if my description accurately depicts the Turing Machine 'V' and therefore proves that the language  'L' is Turing recognizable. Any feedback would be appreciated.

“V On input M1 where M1 is a Turing Machine

i = 1, stop = false;

While (stop==false){

Simulate i steps of M1 on 0

If the simulation enters an accepting state, stop = true. else i=i+1

}

accept.”


texts: Are there algorithms to exactly minimize NFAs which are sometimes efficient?

texts:
I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time algorithm.

What I mean by this is an algorithm which may run in exponential time in the worst cases, but which uses some sort of heuristic to speed up the process, albiet not enough to make it exponential.

I'm only using this to try to get a better idea of what the minimal NFAs of certain languages look like. I'm not using it in any production code, so it doesn't need to be blazingly fast.

For example, the Antichains algorithm for NFAs does equivalence testing which is usually fast but sometimes has exponential explosion. I'm looking for something similar, but for minimization.

Note that I'm NOT looking for things like equivalences, etc. which run efficiently but don't produce a minimal NFA.

Bonus points to anyone who find one with an implementation, and quadruple bonus points if it's in Prolog or Python.
If the tool I'm looking for doesn't exist, I'd be happy if anyone gave any old implementation of NFA minimization.


texts: Is the halting problem decidable by an "infinite Turing machine"?

texts:
It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.

However, I'm wondering, if we want to decide for the set of Turing machines $T$, whether a turing machine $t$ halts, and we somehow have access to "infinite Turing machines" $I$, which have the property $P$: "They can calculate an infinite amount of steps in finite time", would it then be possible to grab a $i$ from $I$ that decides the halting problem for all $t\in T$?

The proof of the undecidability of the halting problem no longer applies here, because it would require one of the $t\in T$ to contain $i$, but then we might possibly have that $t\in I$ (since $t$ now simulates $i$, which is in $I$).

So my question is, can we prove that in this case, the halting problem is decidable? If not, are there other constructions of $I$ than the one I came up with that would make it possible?

(is there a name for what I've called "infinite turing machines"?)


texts: How to retrieve reset bit in constant time in a bit array

texts:
In a game application there is a session id assigned to each player every time they start a new session.
Session id's are always unique and there can be billion users of this game. Whenever a user logs-in, get() function is called which basically assigns a bit to the user by setting a bit from a bitarray and when user logs out, set() function is called which resets that bit.

So,it may happen that at some point the bit array looks like below:
101010101000011111

For uint_32 bitarray[100000], 100000 integers needs to be searched for finding out reset bit in worst case if linear search is used. Is it possible to make this search constant time?

For a 32/64 integer and not using bit array this would be pretty much constant using bit operation (x&-x) but for a bit array getting constant time it would be not that easy.

Is there any data structure which I can use for this purpose? I think we can use skip list for this but need some information as to the right approach to insert and delete element from this skip list?


texts: Basic question about backjumping in SAT solvers

texts:
I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić.

My question is about how backjumping is defined. In an example [1], there is a conflict clause C equal to

[-1,-2,-3]

that has already been explained and learned. The decision trail is

|6, 1, 2, |7, |3, 4, 5,

where true decisions are marked with | and the others are propagated literals.

Then the algorithm performs a backjump to the level of literal 2, the most recently asserted literal that makes the conflict clause a unit clause.
This modifies the decision trail to

|6, 1, 2

and immediately propagates -3 since [-1,-2,-3] is unit now, obtaining

|6, 1, 2, -3

What I would like to understand is: why not define backjumping so that the choice of 7, and all the (potential) work performed after it, were preserved? In this example, choosing 7 didn't do much, but it could have done a lot of propagation that we would not want to waste. There could also be other choices between 7 and -3 that we would benefit from preserving. It seems to me that the algorithm would be perfectly correct if it has backjumped to a decision trail

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them)

and then propagated -3 and got

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them), -3.

More generally, I am proposing that backjumping be defined not to go back to the most recent literal in C making it a unit clause (that is, 2), but to the most recent literal in the trail immediately before the last literal (-3) in C. That would be whatever is immediately before -3 in the trail, before the backjump, including 7, its propagations, and whatever other non-conflicting choices that happen to have been made.

Am I correct that this would be a better alternative that preserves work, or am I missing something?

[1] Fig. 6, trace of Example 7 if you are curious, but there is no need to go look as I think all the relevant information is here.


texts: Total number of red black tree arrangements

texts:
Consider a list of n integers.

And assume we take each integer from this list sequentially and add it to a red-black tree.

Then for the n! permutations of the list how many red-black tree arrangements are there in total?

N.B: Some permutations result in the same arrangement.


texts:
This is not from online contest
Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.

Four functions
You are given four functions
$$
\begin{align}
A(x)&=\text{Number of }i\text{ where }1\leq i\leq x\text{ and }\gcd(i,x)=1\\
B(x)&=\sum_{d|x}A(d)\\
C(x)&=\text{Sum of exponents of each prime in the prime factorization of }B(x)\\
D(x)&=\sum_{i=1}^{x}C(x)
\end{align}
$$
Input:

First line: $T$ [number of test cases]
Each test case consists of an integer $N$

Output format
For each test case, print a single integer denoting the value of $D(N)$ in a new line.
Input constraints
$$\begin{align}1\leq T\leq 10^6\\1\leq N\leq 10^6\end{align}$$

Here's my observation:

About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.

I guess this problem is a math one. We somehow need to come up with an efficient formula to resolve all 4 functions.

I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute gcd and prime factor.

I've thought about this one for two days I can't find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.

Since this is a math problem, some talented and gifted genius out there might be interested. :D
Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.


texts: Represent a real number without loss of precision

texts:
Current floating point (ANSI C float, double) allow to represent an approximation of a real number.
Is there any way to represent real numbers without errors?
Here's an idea I had, which is anything but perfect.
For example, 1/3 is 0.33333333...(base 10) or o.01010101...(base 2), but also 0.1(base 3)
Is it a good idea to implement this "structure":

base, mantissa, exponent

so 1/3 could be 3^-1

{[11] = base 3, [1.0] mantissa, [-1] exponent}

Any other ideas?


texts: How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?

texts:
I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half size blocks, how would someone know (on a particular computer using a particular language and complier) what the ideal blocksize would be to get the best actual runtime speed using mergesort to put them all back together?  For example, what if someone had 1024 sorted blocks of size 1024, but it could that be beaten by some other combination?  Is there anyway to predict this or someone has to just code them and try them all and pick the best?  Perhaps for simplicity they would want to use some simple bubblesort on the 1024 size blocks, then merge them all together at the end using mergesort. Of course the mergesort portion would only work on 2 sorted blocks at a time, merging them into 1 larger sorted block.

Also, what about the time complexity analysis on something like this?  Would all divide and conquer variations of this be of the same time complexity?  The 2 extremes would be 2 sorted blocks (of size 524,288) or 1,048,576 "sorted" blocks of size 1, handed over to a merge process at that point.


texts: Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?


texts: What is the computational class of a pushdown automaton with real values?

texts:
Say there is a push-down automata, in this example I'll use a deadfish-like set:
+: increase x by 1
0: set x to 0
ln: set x to ln(x) <-- real valued result
With x being an infinite precision real-valued variable, does this allow said machine to have more power than if it was operating on integers? Or am I misunderstanding something?


texts: Maximum degree of concurrency in task dependency graphs

texts:
I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find out the maximum degree of concurrency in a given task graph.

In my case, I'm talking of a relatively small graph, around 100 nodes, but nodes, representing tasks, are long running tasks. So the occuracy, more then complexity of such an algorithm would matter.

Assuming I came up of such a degree, the second problem, is how should I distrubute tasks? I've read about topological sort, and transforming the result in a list of sets, with each set being run in parallel. But again, I suspect if this is the best approach.


texts: How to generate a connected random network topology for a specific number of nodes?

texts:
I'm trying to generate a random but realistic network topology so I can test the performance of some routing algorithms. I came across Waxman's model described in Routing of Multipoint Connections, which seems pretty simple:

Distribute $N$ nodes randomly across a plane (uniform in x and y).
For each pair of nodes, generate an edge between them with the probability $ P = \beta \exp \frac{-d}{L\alpha}$, where $d$ is the euclidean distance between the nodes, $L$ is the maximum distance between two nodes, and $\alpha$ and $\beta$ are parameters in the range $(0, 1]$.

I've implemented my current understanding of Waxman's algorithm as a simple web-based demo, which visualizes a generated topology from chosen parameters $\alpha$, $\beta$, and $N$.

However, I want to be able to generate a connected network topology for
a specific number of nodes. Since Waxman's algorithm generates edges probabilistically, I usually end up with disconnected nodes. How do I connect the rest of the nodes to the topology in a way consistent with Waxman's algorithm, i.e. simulates a real network topology?

There are plenty of ways to "finish" the topology by connecting the disconnected nodes, but I don't know which one is the most compatible with the already-generated edges. Waxman's paper doesn't seem to mention how disconnected nodes are treated.


texts: Minimum number of exchanges needed to get all negative values left of all positive ones

texts: Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?


texts: Tree Optimization, Combinatorics, algorithm

texts:
My Partners and me, we are trying to optimize frequency process...

I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java help us a lot.

What we want to simplify our problem as much as possible in a JTree.

As you can see, each node or leaf has a numResampleOperations involved per node/leaf.

L -> Increment or multiplication
M -> Decrement or division

How do we calculate the values?

Target = Source*L/M
numResampleOperations = filterSize * Source * Integer.max(L, M);

We want to obtain only one value per frequency indicated in one String, removing not needed branch of Tree. 210, 200, 180, 160 and 150 like is shown in the image.

For this example we used only 5 ordered Target frequencies (only integers value are allowed), but can grow until 50 frequency values.

The Tree must preserve at least one per included Target frequency of 150Hz, at least one of 160Hz, .., 210Hz.

The highest priority is to have the minimum sum involved of numResampleOperations

How do we remove not needed branches (those whose sum is very high), nodes or leafs, with the guarantee of having at least one (frequency required on String), but the sum of all numResampleOperations is minimum?

What do you suggest to us?

We starting with https://stackoverflow.com/questions/56095738/generate-list-with-combination-of-subset-of-list-java
But due to the dimensions the solution is not viable.


texts: With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?


texts: The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

texts:
I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they mention that?

I ask this before I've recently found a paper where such a type system is presented and an algorithm based on the search of a fixed-point allows type inference for the type system. The trick is that you can fix a number $k$ of iterations for the search to maintain decidability of such a type system. If you cannot find a fixed point you can use the usual ML rules to try to type the program disallowing polymorphic recursion.

The authors proved that, given a well-typed expression $s$ there exist $k \in \mathbb{N}$ such that you can type the expression with the correct type limiting the number of iterations to $k$.

Now, I think this implies semidecidability of type inference with polymorphic recursion in such a case. If we allow $k = +\infty$ what would happen is that the algorithm would always terminate for well-typed expression, but could not terminate for non-well typed expressions.

Am I correct in this conclusion or is there some hidden issue I didn't understand?


texts: Doron ZEILBERGER's P = NP computer proof

texts:
In 2009 Doron has published a paper stating "Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm for the NP-complete subset sum problem.". I've been looking for other people's opinions on this but I haven't found anything significant. Has this problem been officially settled? is this a correct solution? I am not able to assess the paper because of my limited knowledge. What do you guys think ?

Paper : http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf


texts: Loop invariant for adding 2 arrays storing binary value of integer

texts:
Question:

Given 2 arrays of size $n$, $A = \langle a_1,a_2,\dots,a_n \rangle$ and $B = \langle b_1,b_2,\dots,b_n\rangle$, where $A$ and $B$ store the binary value of an integer. Find $A + B$ and stores the result in array $C$ of size $[n+1]$, $C = \langle c_1,c_2,\dots,c_{n+1}\rangle$.

Pseudocode:

ADD-BINARY(A,B)
C = new integer[A.length + 1]
carry = 0

for i = A.length to i = 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2

C[1] = carry

return c

After writing the pseudo-code, I'm trying to find the loop invariant. One of the statement I can think of is

At the start of each iteration in the for loop, C[A.length...i] consists of the sum of binary A[A.length...i] and B[A.length...i].

But I check the initialization stage and found out that it is invalid because at the beginning of the for loop C[A.length] does not have the sum yet(it just got initialized). So I'm puzzled whether I'm approaching it the right way.


texts: How words can instruct hardware to do an operations . I understand that these are converted to 0s and 1s . But still I can't intuitively understand How it works .  A detailed explanation would be appreciated .


texts: Cover marked squares with rectangles with optimal tradeoff

texts:
I'm trying to solve this problem where I have to cover all the squares in a N x N grid with rectangles with a tradeoff between cost and computation. These are the constraints:

Fields are rectangular, but may be of any width or height
Rectangles may cover any cell whether marked or not
Must be rectangular
Must be axis-aligned with the grid (i.e., not diagonal)
Rectangles cannot overlap
Each rectangle costs 10 + 5 per unit of area covered

Some possible solutions are given below:

I would ideally want to create a random array and test out the code for this. Grid can be any size with any number of marked squares. Optimal solution would be a balanced solution between lowest cost and lowest computational cost.


texts: Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

texts:
My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\langle M_x\rangle$, while $M_x$ performs some simulation of $M$ on $x$.

(The answer eluded me for some time, so I started writing a question here. After I found the surprisingly simple answer, I decided to post it (Q&A-style) anyway.)


texts:
According to Galvin and Silberschatz, 5 queues are maintained in multilevel queue scheduling, each for:

System Process
Interactive Process
Interactive Editing Process
Batch process
Student Process

where System process has highest priority and Student process has lowest priority.

What is meant by Student Process?

Also, I only have a vague idea about the rest except system process. If possible, elucidate them.


texts: I have seen a way how to convert a decimal number to BCD (packed & unpacked) using 8,4,2,1 weighing forms but how to do it using 4,2,2,1 and 7,4,2,1 ? Any method please.Suggestions


texts: Using transitive closure to determine acyclic property on directed graph

texts:
Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not?

I'm trying to achieve this but getting stuck on the reflexive property of the transitive closure!


texts: Issue with Campaign problem to find distinct valid campaigns

texts:
Question:

An email campaign has a sequence of email messages
where each email message belongs to one of two categories:
transactional (and/or) marketing.
Given the campaign size n and the gap length k, find the total number
of distinct valid campaigns.

My Approach:
My initial thoughts were around generating all the valid permutations for each scenario and then counting it. However, I am not sure if that's the way to go!
I would appreciate any insights.


texts: Give the Regular-Expression (NFA) with specific Separation Patterns

texts:
Question:
Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.
Attempt:
Followed the way we construct the set of strings such that $a$ occurs the odd number of times, I got the following solution:
$$b^*a(bb(bb)^* abb(bb)^*a)^*$$
But then I found the pattern $abbaa$ is not acceptable, as $a$ can appear multiple times consecutively. Is there any systematic way to solve the above problem?


texts: Does P not NP imply NP COMPLETE disjoint from RP?

texts:
According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference?
Furthermore, am I correct that if this indeed the case, then $NP-COMPLETE \cap RP = \emptyset$ since we can use $NP$ completeness to solve all other $NP$ problems?


texts: Proving undecidability of HALT_tm by reduction

texts:
Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ is decidable, and built a decider for $A_{TM}$, and since $A_{TM}$ is already proved by digonalization method to be undecidable, thus the contradiction occurs and $HALT_{TM}$ is undecidable. The Turing Machine is simple and straightforward and I'm not going to talk about its details.

What makes me confused is this sentence

  We prove the undecidability of $HALT_{TM}$ by a reduction from $A_{TM}$ to $HALT_{TM}$

and I would like to know in which part of the proof reduction actually occurs?

From what we know of the concept of reduction, reducing $A$ to $B$ means: we have two problems $A$ and $B$ and we know how to solve $B$ but we stuck in $A$, then if we reduce $A$ to $B$, it means solving an instance of $B$ will cause solving an instance of $A$.

let's get back to the proof, Sipser says

  We prove the undecidability of $HALT_{TM}$ by a reduction from $A_{TM}$ to $HALT_{TM}$

thus $A = A_{TM}$ and $B = HALT_{TM}$. We don't know how to solve $HALT_{TM}$ and actually this is the problem in hand, furthermore the strategy of the proof is based on contradiction, something that is completely irrelevant to the concept of reduction. Then why Sipser uses the term reduction in this proof?


texts: Is there a heuristic or function to determine if two arrays of integers are alike or similar

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

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


texts: Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

texts:
I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are allowed).

What am I missing? According to my (buggy) analysis of the reported estimator's variance, the variance equal to 0 (see below).
How should I analyze the use in an $\ell_0$-sampler? (Currently, my analysis ignore it)

Algorithm:

Init: Define $k := O(\frac {n^3} {\epsilon^2 t})$. Pick $k$ random subsets $S_1, \ldots, S_k \subset V$ each of size 3 (with repetitions).
Update: For each random subset of size 3, denoted $S_i$, maintain a counter $x_{S_i}$, which represent the number of internal edges in $S_i$, i.e. a number in $\{0, 1, 2, 3\}$.
Output: Use an $\ell_o$-sampler over the vector $x = (x_{S_1}, \ldots, x_{S_k})$ to pick an index $j \in [k]$ (i.e. $j$ is chosen uniformly at random from $\{i \in [k] : x_{S_i} > 0\}$). Compute $z := \mathbb{1}[x_{S_j} = 3], N = \|x\|_0$. Report $\tilde{T} = N \cdot z$.

Analysis, where $T$ is the number of triangles:
$$
\begin{split}
E[\tilde T] &= E[N \cdot z] \\
&= N \cdot E[z] \\
&= \|x\|_0 \cdot E \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \\
&= \|x\|_0 \cdot \Pr \left[ x_{S_j} = 3 \right] \\
&= \|x\|_0 \cdot \frac T {\|x\|_0} \\
&= T
\end{split}
$$
Which seems to be ok. But for the variance:
$$
\begin{split}
Var[\tilde T] &= Var[N \cdot z] \\
&= N^2 \cdot Var[z] \\
\end{split}
$$
Then
$$
\begin{split}
Var[z] &= Var \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \\
&= E \left[ \left( \mathbb{1} \left[ x_{S_j} = 3 \right] \right)^2 \right] - \left( E \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right]  \right)^2 \\
&= E \left[ \mathbb{1} \left[ x_{S_j} = 3 \right], \mathbb{1} \left[ x_{S_i} = 3 \right] \right] - \left( \frac {T} {\|x\|_0} \right)^2 \\
&= \Pr \left[x_{S_j} = 3 , x_{S_i} = 3 \right] - \left( \frac {T} {\|x\|_0} \right)^2 \\
&= \left( \Pr \left[x_{S_j} = 3 \right] \right)^2 - \left( \frac {T} {\|x\|_0} \right)^2 \\
&= \left( \frac {T} {\|x\|_0} \right)^2 - \left( \frac {T} {\|x\|_0} \right)^2 \\
&= 0
\end{split}
$$


texts: P=NP when number of inputs that give 1 is bounded by polynomial

texts: Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, for every $n$, $|\{ x \in \{0, 1 \}^n : f(x) = 1\}| \leq p(n)$ for some polynomial $p$. Then, I want to show that the existence of this problem implies $\mathsf{P} = \mathsf{NP}$. Is it somehow related to LEXSAT?


texts: PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?

texts:
In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:

  Requiring solutions to all type equations may seem suspicious, because
  we know by Cantor’s Theorem that an isomorphism such as $X \cong (X \rightarrow \mathbf{2})$
  is set-theoretically impossible. This negative result tells us not that our requirement
  is untenable, but rather that types are not sets.

I understand why solving such an isomorphism is set-theoretically impossible, and therefore why being able to solve it means that "types are not sets". However, I cannot think of any possible type $X$ that would actually solve this isomorphism.

Can anyone give an example of such a type (and ideally, some advice for more generally solving such type isomorphisms)?


texts: Confused between turing-completeness and universal approximation - are they related?

texts:
I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem".

The context here is deep neural nets: So, consider two types of networks: a recurrent neural net, (RNN), and a feedforward net, say a pure convolutional neural net (CNN).

I understand that the RNN is turing complete. I also know that a CNN is a universal approximator, but is NOT turing complete.

What I am trying to understand is the link between universal approximation, and turing-completeness: Is there a link? Why is a CNN a universal approximator but NOT turing complete? Does a machine being turing-complete automatically make it a universal approximator? Trying to uncouple the two concepts.

Thanks!


texts: How can neural networks learn to create new things (sentences for example)?

texts:
I have already taken a college course at my uni on machine learning where we implemented all the basic ML programs: linear regression, logistic regression, basic neural network with logistic regression (not perceptron, but we learned the theory of perceptron as a history lesson), k-means, and naive Bayes classifier. The class also had a high focus on the theory behind these algorithms so i know a lot of the relates maths.

But all of our projects were based on simple numbers. What I mean by that is all of the projects had features which were simple numbers such as miles per gallon, year, horsepower, weight, frequency, etc.  We never made anything that could understand more abstract things like text, or color, etc.

I recently stumbled upon this article about a recurrent neural network that makes up its own Magic: The Gathering cards and my interest in ML was piqued again. I want to learn to implement something which can learn about things besides basic numbers, I want to make something that can learn to put sentences together like the one in this article. Hell it even makes up its own words (fuseback) that don't exist in Magic and added rules text to them (like for Tromple).

What resources are there to learn how to make a system which can learn these more abstract ideas like words and colors? I don't understand how the neural network can come up with it's own words. All the machine learning stuff i did only classified test data into existing sets (or predicted a number on a feature), but it never created a new feature.


texts: How to implement a prolog interpreter in a purely functional language?

texts: Is there a clear reference, with pseudo-code, on how to go about implementing a Prolog interpreter in a purely functional language? That which I have found so far seems to deal only with imperative languages, is merely a demonstration of Prolog implemented in itself, or offers no concrete algorithm to use for interpretation. I would be very appreciative of an answer.


texts: Proving the correctness of an algorithm, which computes the connectivity of a directed graph

texts:
Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not strongly connected.

Why does the following algorithm compute the connectivity of a graph correctly?

\begin{equation}
\begin{split}
&\text{Connectivity}(\text{graph }G=(V,E)) \\
&\;\;\;\;01\text{:}\;\;k=\infty \\
&\;\;\;\;02\text{:}\;\;\text{for }i=1,\ldots,|V| \\
&\;\;\;\;03\text{:}\;\;\{\\
&\;\;\;\;04\text{:}\;\;\;\;\;\;\text{for each }v\in V\\
&\;\;\;\;05\text{:}\;\;\;\;\;\;\{\\
&\;\;\;\;06\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v_i,v\text{-seperator }U_{v_i,v}\\
&\;\;\;\;07\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v_i,v}\right|\right\}\\
&\;\;\;\;08\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\
&\;\;\;\;09\text{:}\;\;\\
&\;\;\;\;10\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v,v_i\text{-seperator }U_{v,v_i}\\
&\;\;\;\;11\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v,v_i}\right|\right\}\\
&\;\;\;\;12\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\
&\;\;\;\;13\text{:}\;\;\;\;\;\;\}\\
&\;\;\;\;14\text{:}\;\;\}
\end{split}
\end{equation}

More precisely, why can we return $k$ in line 08 (resp. 12) without concerning the other $u,v$-seperators?


texts:
I have tried to solve the following question:

  van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$.

In CLRS (Introduction to Algorithms), they make use of the master method case 2. They let $m = \log_2u$ so we have $T(2^m) = T(2^{m/2}) +O(1)$. Then they substitute $T(2^m) = S(m)$ and the recurrence looks as follows:

$$S(m) = S(m/2) + O(1).$$

The above confuses me, because I don't see how $S(m/2)$ is the same as $T(2^{m/2})$. Taking half of $m$ is not the same as taking half of the exponent $m$.


texts: How to prove the correctness of the MinDistance algorithm?

texts:
My question is about how to prove the correctness of this algorithm, I know it is not a good algorithm, it is not efficient and can be improved. How could I prove it still returns the desired value? What are the loop invariant and variant? How to insert assertions between lines?

The algorithm goes like following,

Algorithm MinDistance (A [0…n-1])

//Input: Array A [0...n-1] of numbers

//Output: Minimum distance between two of its elements

dmin←∞

for i←0 to n-1 do

    for j←0 to n-1 do

        if i≠j and |A[i]-A[j]|<dmin

        dmin←|A[i]-A[j]|

return dmin


texts: What does > mean in this TAOCP solution?

texts:
For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.

  Problem:
  Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.

  At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?

  In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i < N$, in random order, where the $x_i$ are distinct, how can the sequence $x_1 x_2 \ldots x_N$ be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other.

  Solution by Norman Hardy, c. 1967: Make another copy of the input file; sort one copy on the first components and the other on the second. Passing over these files in sequence now allows us to create a new file containing all pairs $(x_i, x_{i+2})$ for $1 \le i \le N-2$ and to identify $(n-1,x_{n-1})$. The pairs $(n-1, x_{n-1})$ and $(n,x_n)$ should be written on still another file.

  The process continues inductively. Assume that file F contains all pairs $(x_i,x_{i+t})$ for $1 \le i \le n - t$, in random order, and that file $G$ contains all pairs $(i,x_i)$ for $n-t < i \le n$ in order of the second components. Let $H$ be a copy of file $F$, and sort $H$ by first components, $F$ by second. Now go through $F$, $G$, and $H$, creating two new files $F'$ and $G'$, as follows. If the current records of files $F$, $G$, $H$ are, respectively $(x,x')$, $(y,y')$, $(z,z')$, then:

  If $x' = z$, output $(x,z')$ to $F'$ and advance files $F$ and $H$.
  If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.
  If $x' > y'$, advance file $G$.
  If $x' > z$, advance file $H$.

  When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.

So here is my question:

  If $x' > y'$, advance file $G$.
  If $x' > z$, advance file $H$.

What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is it referring to string size?


texts: Why is $\emptyset L = L\emptyset = \emptyset$ correct?

texts:
I am taking a course on Automaton where I faced the algebraic laws of regular expressions.
First two were ok:

$\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language gives the language $L$ itself.

$\epsilon L = L\epsilon = L$: Concatenation of empty string with strings belonging to certain language $L$ gives back the set of string of language $L$

But the third one is confusing me:

$\emptyset L = L\emptyset = \emptyset$

I felt it should be  $\emptyset L = L\emptyset = L$, since concatenation of strings of language L with string of empty language which is essentially no strings at all (which essentially means nothing to concatenate), should give back the language $L$ itself. Where I am thinking wrong?


texts:
I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of the weak and strong one way function. I known it's very broad notion, therefore I will be as specific as possible in my questions.

Strong one way function. $\forall$ nonuniform PPT $A$, $\exists \epsilon s.t. \forall n \in N, Pr_{x\in\{0,1\}^n}[A(1^n, f(x)) \in f^{-1}(f(x))] \leq \epsilon(n)$

  Q:$1^n$ as the first parameter of the PPT $A$ represent the length of the initial input, the usage of it is justified as "this ensures that the output of A doesn't shrink the size if its too must as in the f(x)=|x| example". Unfortunately I didn't get the previous explanation (may be because the lost the sign, which takes an additional bit). In my opinion putting in A the size of $x$ might help $A$ get the right output $x$.

  Q: in the lecture it mentioned that $f(x)=|x|$ is hard, "because it will take $2^c$ time to write a valid inverse of something such that $f(x)=c$". It happens because we cannot find $x$ with probability with negligible more than 0.5,  but it's due to another problem not a computational but rather information theory problem, by running the function we lost the information about the sign of the input $x$, if it's a correct reasoning, why actually it would take $2^c$ time?  In addition for  me it looks like the great discover to find the strong one way function, however do have more assumption of hard function like $f(x)=|x|$?

Definition of weak one way function.$\exists$ $q(x)$, $\forall$ nonunoform PPT A, $\forall$ n $\in$ N,
$Pr_{x \in \{0,1\}^n}[A(1^n,f(x)) \in f^{-1}(f(x))] \leq 1-\frac{1}{q(n)}$

  Q: in the lecture there was an assumption that the multiplication is weak one function, how we can actually show that the multiplication is weak one way function, and do we have more assumptions of examples of weak one way functions?

I am very sorry for being naive, even though I will appreciate any help.


texts: Can we write algorithms without conditional statements?

texts:
Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.

Consider the factorial problem, we would typically define the algorithm as

Solution 1.

int fact(int n)
{
if n == 0 then
 return 1;
else
 return n*fact(n-1);
}

An alternative would be to define the function fact as

Solution 2.

int fact(int n)
{
 if n == 0 then return 1;
 elseif n == 1 then return 1;
 elseif n == 2 then return 2;
 elseif n == 3 then return 6;
 ....
 all cases define as above
}

Also, another solution would be to have functions like:

Solution 3.

int fact0()
{
return 1;
}

int fact1()
{
return 1*fact0;
}

int fact2()
{
return 2*fact1;
}

int fact3()
{
return 3*fact2;
}

Then we would have an array of function pointers p which we would have to index according to the factorial we want to determine, such that p[0] points to fact0, p[1] points to fact1, and so forth.

I know that this might sound dumb, but it actually works! What makes solution 1. a valid argument to show that conditionals are required to compute the factorial?

Some additional thoughts on my part:

Is solution 1 the only true "algorithm"? Because the other 2 solutions to not seem to "compute" anything
Are conditionals required only because we don't know the results (or execution steps) of functions beforehand?


texts: Bisimulations: Proof that the following LTS are not bisimilar

texts:
I have the two LTS (labeled transition system) as seen in the following picture:

And the book is telling me that between those two LTS, their $1$ and $1'$ are non-bisimilar.

So I tried to get a bisimilation starting from the pair $\{\{1,1'\}\}$ by continuously extending it whenever I found a conflict, ending up with:
$$\{   \{1,1'\} ,\{2,2'\},\{3,3'\},\{2,4'\},\{4,3'\},\{3,5'\},\{4,5'\}               \}$$

Finally, to check whether it truly was a bisimilation, I checked for each pair each node, and asserted that all possible pairs of derivatives were part of the set.

I am arriving that they are a bisimilation - is the crux in the $a$'s and $b$'s? (They didn't really explain what it means)


texts: Number of possible heaps on $\{1,...,2^h-1\}$

texts:
Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree is ordered if the key at every node is smaller than the keys at its children.
An ordered binary tree of height $h$ is called a heap if the tree induced by all levels except the last is a complete binary tree and all leaves are "as much to the left as possible".

So what I've come up with is this expression:
$$C_h=\displaystyle\prod_{n=1}^{h} (2^{i-1})!$$
The intuition behind it is that with every  increment by $1$ of $h$ the tree gains $2$ times more leaves than before and the possibilities of ordering these leaves can be determined via the factorial operation. Does that make sense?


texts: Is < binary relation a strict partial order on IEEE doubles?

texts:
To me it looks that it is:

irreflexivity: NaN < NaN == false
transitivity: if a < b and b < c then a < c (the antecedent is never true for NaNs)
asymmetry: if a < b then not b < a (again, the antecedent is never true for NaNs)

However, it cannot be extended to non-strict partial ordering <= because there's no (reflexive) equality for doubles (NaN != NaN).


texts:
I am reading William Stallings operating system book which gives this pseudo-Code for disabling interrupt to achieve Mutual Exclusion

while (true) {
 /* disable interrupts */;
 /* critical section */;
 /* enable interrupts */;
 /* remainder */;
}

But I don't get why there is a While loop in the code which is true
this means that this part of the code repeats forever but why?


texts: Iterative and/or tail-recursive implementations of merge sort?

texts:
I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented in an iterative style?

In general how can a recursive algorithm converted into an iterative and tail-recursive algorithm? What are the possible pros and cons of this conversion?


texts: How does the Fetch-Decode-Execute-Reset (FDER) cycle work?

texts:
How is this different to the Fetch-decode-execute (FDE) cycle?
I have an understanding of the FDE cycle and how the CPU works, although I came across a FDER cycle, when reading about the CPU scheduling and the the methodology regarding process swapping using process control blocks.
There was limited information on the actual workings of the FDER cycle - which I will appreciate if you can help me with?
I presume it sort of resets the registers, although I am not sure?
Thank you for your help.
Reference: A/AS Level Computer Science for OCR (p43) - used for self-study.


texts: Give an example of a connected graph where α(G) =100 and β(G) = 200

texts: So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.


texts: Randomized Meldable Heap - Expected Height

texts:
Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert.

The question is, what is an expected height of that tree with $n$ nodes?

Theorem 1 of Gambin and Malinkowski, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF) gives the answer to this question with proof. However, I do not understand why we can write:
$$\mathbb{E} [ h_Q] = \frac{1}{2} ((1 + \mathbb{E}[h_{Q_L}]) + (1 + \mathbb{E}[h_{Q_R}]))\,.$$

For me the height of the tree is

$$h_Q = 1 + \max\, \{ h_{Q_L}, h_{Q_R}\}\,,$$

which I can expand to:

$$\mathbb{E} [ h_Q] = 1 + \mathbb{E}[\max \,\{ h_{Q_L}, h_{Q_R}\}] = 1 + \sum k  \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k]\,.$$

The probability that the maximum of a height of two subtrees is equal to $k$ can be rewritten using the law of total probability:

\begin{align*}
\hspace{2em}&\hspace{-2em}
\mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k] \\
&= \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L}\leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em} + \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \\
&= \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}]\,.
\end{align*}

So at the end I get:

\begin{align*}\mathbb{E} [ h_Q] &=  1 + \sum k \{ \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \}\,.
\end{align*}

This is where I am stuck. I can see that $\mathbb{P}[h_{Q_L} > h_{Q_R}]$ is more or less equal $\frac{1}{2}$ (However we need at most $\leq \frac{1}{2}$). But except that nothing leading to the formula from the beginning.

The heights of the subtrees do not seem to be independent to me.

Thanks for help.


texts: Is the set of strings with equal number of 010’s and 101’s regular?

texts:
Consider the language $$L = \{ w\in \{ 0, 1\}^*: \#_{010}(w) = \#_{101}(w) \}$$
Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?


texts:
Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$.
I can't figure out why this is true.
Since $f$ is computable there is a Turing machine that computes it, denote it by $M_f$.
Since $A \in RE$, we get another machine that accepts $A$, and obviously $f(A)$ is reducible from $A$, but given only that an input $f(x)$ for $f(A)$, is accepted iff $x\in A$, and $f$ is not necessarily injection so idk if you can get $x$.
Another idea I had was:
Given that $A\in RE $, there is a counter machine for it, and since $f$ is computable then there is a Turing machine that prints $f(x)$ for a given $x \in A$, so what we could do is count each word in $A$ one by one, and for each one simulate $f$ on that word and that would result in a counter machine for $f$, i.e. $f$ is recursively enumerable, so we get $f\in RE$.
Any idea if this is true? if not, how can this be proved?
Thanks in advance.


texts: Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges?

texts: I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first negating the weight of all the edges?


texts: Consistency and completeness imply soundness?

texts:
I understand that soundness implies consistency. Also, I understand that consistency alone does not imply soundness. But shouldn't consistency + completeness imply soundness? Scott Aaronson in his blog-post hints otherwise. What am I exactly missing?

Update: By completeness I assume that all sentences true under all interpretations are deducible. By soundness I assume that all deduced sentences are true under all interpretations. Finally, by consistency I assume that no sentence $P$ and its negation $\neg P$ can be deduced.


texts:
I am trying to prove that the next problem is NPC:
$$
A = \{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE}  \}
$$
I am trying to find polynomial mapping reduction from SAT but I can't find a way to force exactly 10 variables to get TRUE assignment.
My idea was to create new formula, with 10 clauses, each clause is the intersection of a new variable $x_i$ with the old formula, but I don't see how my idea helpful.
I would appreciate help.


texts:
When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do the extra rotation beginning at the leaf or save the extra rotation and do it at the root. Does it matter?

For example, in the attached image I insert a 4 into a BST, and "splay it"
it to the root. On the top of the figure, I first locate the zig-zig pair
at the leaf node and perform the zig-zag splay from the bottom leaving a final right rotation at the root. At the bottom of the figure, I first do the odd rotation starting from the leaf, and the then do a zig-zig splay to the root.

Which is correct? Or  will both lead to the usual splay-tree performance?


texts: How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?

texts:
Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-dimensional matching):

  Exact-3D-Matching: Given a set $S$ and a collection of three-element subsets of $S$, called triples, is there a sub-collection of disjoint triples that exactly cover $S$?

The 3-Partition problem is defined as (It is also from Lecture 29: NP-Hard Problems. You can also refer to 3-partition problem.):

  Given a set $S$ of $3n$ integers, can it be partitioned into $n$ disjoint three-element subsets, such that every subsets has exactly the same sum?

It is known that the 3-Partition problem can be proved to be NP-complete by reducing the NP-complete Exact-3D-Matching problem to it. And the NP-completeness of the Exact-3D-Matching problem is proved by reducing the 3SAT problem to it (both are given in the book Computers and Intractability: A Guide to the Theory of NP-Completeness).

Problem:
My problem is:

  How to prove the NP-completeness of the Exact-3D-Matching problem by reducing the 3-Partition problem to it?

I have found neither papers nor lecture notes on it.


texts: Does crossover take the parents or the offsprings? How to select parents with linear ranking?

texts:
I am building genetic algorithm for feature selection. But there are vague things to me.

For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?
I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?
Assume if the answer on number (1) is taking 80 parents. After I get parent's candidates, what will happen to the unused parents if those candidates are more than our requirement? And what will happen if those candidates are less than our requirement?
If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

Thanks before.


texts: Confusion about the definition of "Exponential Average"

texts:
I was having doubt regarding the concept of "exponential averaging". Till now I have come across the concept twice and they seem to be quite similar (except that they have minor but sharp differences, which sort of confuses me). Once in Operating System and another in Computer Networks.

The above picture is from Galvin OS text, which associates $\alpha$ (smoothening factor with the actual value , here actual CPU burst time).

The above picture is from Forouzan Computer Network text where the $\alpha$ is associated with the estimated value (of RTT).

The above picture is from Kurose and Ross Computer Networks text and it associates $\alpha$ with the actual value (of RTT) [ which is similar to what done in Galvin]

Is there any standard definition of this concept? It kind of seems confusing to me.


texts: For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication

texts:
I've recently stumbled upon a problem that I struggle realy hard with ever since.
There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary representation of $A*B$ are set (how many 1s are there in the binary representation). Now, for small numbers, that's trivial. You just multiply them, and then using bit-shifts compare each bit with a 1, incrementing a 1-counter every time bit & 1 is true. However, for very large numbers, hardly any programming language will allow the user to perform such multiplication. So how to achieve thet without any high-level languages and fancy libraries?
I think the proper start here is to create arrays for both numbers, to store them as separate digits. That can be done in a number of ways, from using sprintf and then transcribing the char array to int array using intarr[i] = chararr[i] - '0', or by a simple loop which divides the number modulo 10 and then divides it by 10. Either way, we're left with two arrays of the respective numbers' digits, and we can multiply them by each other quite easily. Now, we're left with and int array of the multiplication result's digits. Where do we go from here? How to get a binary representation of a very large number stored like that? How to count the 1s in its binary representation? Is there any trick for that?


texts: Do two strongly connected nodes constitute a cycle in directed graph?

texts:
I'm seeing seemingly contradictory information about this around. On the one hand, it seems that for undirected graphs, you need at least 3 nodes to make a cycle.
On the other other, I've also seen people differentiate between trivial and non-trivial cycles.

Let's say in your directed graph you have two nodes A and B with an edge  from A to B and an edge from B to A. Do you have a cycle (A, B)? And does it always count as a cycle, or would some people consider it a cycle and others not?

Also, let's say you traverse that directed graph and hit A before you hit B. Is the edge (B, A) a back edge?


texts:
This question is about max heap and array

  Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at the beginning/head of the heap $h$ is assumed to be new array $C$.
  The array $C$ is a heap  (or)  not?

My answer: is heap because it's bigger than any other element in array

  With $n$ data items already stored in heap $h$, a new array $D$ is created by adding a value $u$ to the heap $h$ that is smaller than any of the $n$ items already stored in heap. If $u$ is added to last element in heap $h$, is array $D$ heap or not?

My answer: it is heap because the smallest one has to be in the leaf

But what is the relation with array? Is there rule to insert node in heap?
I know that to insert node to array in heap we insert data as last element of heap and then put it in the root and heapify it.


texts: $L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

texts:
Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side.

I need to Show that $L$ is regular.

I'd relly like some help, I tried to think of any way to prove it but I didn't reach to any smart conclusion. what is it about the only side right moves and the regularity?


texts: Mapping a free variable of type A to a cartesian closed category

texts:
In From Lambda Calculus to Cartesian Closed Categories, the author explains the interpretation of lambda calculus in cartesian closed category and at one point he explains how a term representing a free variable of type A is mapped to the cartesian closed category as follow:

 [Γ x:A :- x:A] = π2 : ([Γ ] × [A]) → [A]

 (A term which is a free
 variable of type A is an arrow from the product of Γ and the type object A to A;
 That is, an unknown value of type A is some arrow whose start point will be
 inferred by the continued interpretation of gamma, and which ends at A.
 So this is going to be an arrow from either unit or a parameter type to A -
 which is a statement that this expression evaluates to a value of type A.)

I appreciate if someone can elaborate further on what the author means, perhaps with an example, since I am a newbie to category theory.


texts:
The TCP(Transmission Control Protocol) delayed duplicate problem is discussed in Tannenbaum's "Computer Networks." The discussion references Tomlinson (1975) improved by Sunshine and Dayal (1978). Basically, from what I could make out it uses a ToD (Time of the day) clock to uniquely number packets and ensure that, if packet lifetime is $T$ secs, then no new packets have the same sequence number within $T$ secs. To elucidate the above fact a graph between sequence numbers and time is drawn which shows the linear relation and marks a Forbidden region, entering which produces duplicate packets.

So here are my questions:

How exactly does entering the forbidden region produces the delayed duplicates?
If I wanted to quantify the discussion with the following parameters:

a) ToD clock size - 32 bits(keeps running even when the host is down)

b) clock increases once per milliseconds

c) maximum packet lifetime - 64 s

How would I find the minimum and maximum permissible sequence number generation rate?


texts: Automatic softcore configuration based on intermediate representation (IR) compiler output

texts:
When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target specific assembly code.

When we have a fixed processor architecture, often optimizations are made to make the machine run a bit faster, or consume less memory. It is always a trade off when designing the ISA, is this computation general enough to dedicate a separate instruction for it, so that later on when compiling software, these optimizations can be made.

With soft cores, however, we could make a whole new processor every time we have a new piece of code.  Often we see soft cores being designed for a specific purpose, while still keeping them general purpose enough so that they can be reused, or still work well when the software is changed.

It seems possible to, instead of first making designing the processor and then compiling the code for the target, making the processor based on your code. Profiling and debugging could be done on a general purpose machine running the intermediate representation code. Based on those results, an effective instruction set can be generated. With that instruction set, a soft core can be generated.

Designing an instruction set and building a good soft core and making a proper tool chain for target compilation steps is a lot of work, but it seems possible to automate this process. I could not find anything on this topic however.

Is this just too complex to do, and are we just better of having a few settings for your soft core with a bunch of optional extensions? Like you often see with soft cores like the Microblaze or NIOS II.

Or is this already a thing and can I just not find it? I do know of coarse grain reconfigurable architectures, but these are more for parallel computations and aim to replace FPGAs for some purposes.

Also, is this stack exchange the right place for these quite multidisciplinary questions?


texts: Why does the operating system switch an active process to different cores?

texts:
When running a single-threaded application that is 'always busy', on a multi-core computer, modern operating systems will typically switch the process from one core to another from time to time. Even when the other cores are always idle.

Typically you can see 1 of 4 cores on a quad core processor at 100% load while the other cores are 0-1%. Once in a while, the active process will 'jump' to another core, now leaving the original core idle and utilizing 100% of another core.

Why does this happen?

Is it because the process was context-switched (even though other cores were idling)? Or is it because of thermal or power-related reasons? Something else?