texts: Reccurrence for the game of pile of stones

texts:
I am trying to solve this question from Project Euler for past few days: Divisor game.
The problem is as follows:

  Two players are playing a game. There are $k$ piles of stones. When it is his turn a player has to choose a pile and replace it by two piles of stones under the following two conditions:
  1.Both new piles must have a number of stones more than $1$ and less than the number of stones of the original pile.
  2.The number of stones of each of the new piles must be a divisor of the number of stones of the original pile.
  The first player unable to make a valid move loses.
  Let $f(n,k)$ be the number of winning positions/configurations for the first player, assuming perfect/optimal  play, when the game is played with $k$ piles each having between $2$ and $n$ stones (inclusively). Then find $f(10^7,10^{12}).$

What I tried

The first thought upon seeing the number of piles to be $10^{12}$, is that somehow matrix exponentiation is involved, with a linear recurrence being obtained on the number of piles $k$ for some fixed $n$.
The second thing which can be observed is that if I have $k-1$ piles of stones with each pile having stones between $2$ and $n$. And this  configuration is denoted by $S_{k-1}$, then if I have two numbers $a=q_1^{r_1}q_2^{r_2}...p_x^{r_x}$ and $b=s_1^{t_1}s_2^{t_2}...s_y^{t_y}$ ( where I have written the prime factorization of $a$ and $b$ ) such that $r_1+r_2..+r_x=t_1+t_2..+t_y$ then either both the configurations $S_{k-1}a$ and $S_{k-1}b$ are loosing configurations or both are winning configurations ( where $S_{k-1}a$ means I have added a pile with $a$ stones to the configuration $S_{k-1}$ ).
Based on the the above two points I tried the following approach. Let $L_{k-1}$ and $W_{k-1}$ be the number of loosing and winning configurations respectively, where each configuration has $k$ piles, with each pile having between $2$ and $n$ stones ( inclusive ). Also let $P$ and $C$ represent a prime and a composite number respectively, between $2$ and $n$ ( inclusive ).
Then it is easy to note the following:
$L_{k-1}P$ is a losing configuration with $k$ piles, last pile having $P$ stones.
$W_{k-1}P$ is a winning configuration with $k$ piles, last pile having $P$ stones.
$L_{k-1}C$ is a winning configuration . The reason is: as $C$ is a composite number it has a prime divisor $p$. The first player chooses the last pile ( $k$th pile ) having $C$ stones and replaces it with two piles each having $p$ stones. Now its the second players chance and he is left with configuration $L_{k-1}$ which is loosing configuration ( the second player can't choose the two newly form piles as they cannot be broken down further as they have prime number of stones ).
The problem comes here as $W_{k-1}C$ can be a winning or a loosing configuration. For example let $k=2$ and $n=10$ then it can be seen that a single pile having $4$ stones is a winning configuration. And also it is easy to see that $\{4,4\}$ is a loosing configuration whereas $\{4,8\}$ is a winning configuration ( where $\{4,8\}$ means two piles, first having $4$ stones and second having $8$ stones). So I am unable to move forward in this case.

I still suspect it is a matrix exponentiation question. But I guess it cannot be done just keeping variables $W_{k-1}$ and $L_{k-1}$. How do I proceed ?

PS: As this problem is from project Euler I would appreciate only hints.


texts:
I am currently working on a computer vision problem that involve 8 convergent cameras.
I am trying to recreate a 2D image (I actually don't care of the shape of the image) that is the representation of my scene seen from the 8 convergent cameras (like an above view ?).

I am currently working with Real-time Stereo-Image Stitching using GPU-based Belief Propagation by Adam, Jung, Roth and Brunnett,
which has been made for divergent aligned cameras. I am actually working on translating the formulas for not aligned cameras, but I have no clue on how it is going to work with convergent cameras.

I did some researches but didn't find anything on how to do exactly what I want, even if it seems possible.

If you have any path I could explore or any clue, I would love to have them!

I found Computer Vision: Algorithms and Applications by Richard Szeliski and it actually gives some clues.


texts: Grammar in formal languages versus programming language theory

texts:
Grammars seem to be used for different purposes.  In formal languages, they are used to describe sequences of symbols.  In programming language theory, they are used to describe objects in a term algebra (possibly enriched with some implicit, extra structure such as variable scoping rules).  My question is, are these two kinds of grammars the same notation reused for unrelated purposes, or are they describing the same things?  If they are unrelated, then do we have nomenclature to distinguish them?

For instance, the grammar

e ::= 1 | e e

could be describing a set of strings that includes "1", "1 1", and "1 1 1", or it could be describing a set of terms that includes "1", "1 1", "(1 1) 1", and "1 (1 1)".


texts:
According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things:

Store data
Manipulate data

But is this all? I mean, without I/O, can a computer be considered useful?


texts: Is the empty string ε in regular languages implicitly between any two characters in a string?

texts:
I'm wondering if this visualization makes sense with the definition of the empty string ε. I suppose it does because it doesn't seem to contradict its definition (ε is a string with no characters).

If that's the case, in finite state machines with empty transitions, is it always possible to assume ε is "before" the character a that should be read next, and take the empty transition instead?

If the next state also has an empty transition to another state, can I assume ε is "before" a again, even though the automata had just "consumed" ε in the last operation? In other words, can I assume there is an indefinite number of empty strings between any two characters in a string in a regular language?


texts: Prove if a property of a Turing Machine is decidable or not, how can I do it?

texts:
I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not.

For example, if a have this:

(1.1) "M always halts within 100 steps"

or this

(1.2) "M recognizes all words with an ‘a’ in them"

what do I do to prove if it's decidable or not? I know I should use reduction or diagonalization, halting problem and so on, but I don't know how to apply them.

Thanks for the help.


texts:
I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question:

  Recursive language with non-recursive subsets. Does one exist?

I'm sure it is a very simple and easy answer but I can't figure it out. Don't give me the answer just point me in the right direction and I'm sure I'll figure it out.


texts:
I got confused while solving the following problem (questions 1–3).

Question

  A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 children.

  How would you represent a d-ary heap in an array?
  What is the height of a d-ary heap of n elements in terms of n and d?
  Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INCREASE-KEY(A, i, k), which flags an error if k < A[i] = k and then updates the d-ary matrix heap structure appropriately. Analyze its running time in terms of d and n.

My Solution

Give an array $A[a_1 .. a_n]$

$\qquad \begin{align}
 \text{root} &: a_1\\
 \text{level 1} &: a_{2} \dots a_{2+d-1}\\
 \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\
 &\vdots\\
 \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1}
 \end{align}$

→ My notation seems a bit sophisticated. Is there any other simpler one?
Let h denotes the height of the d-ary heap.

Suppose that the heap is a complete d-ary tree
$$
 1+d+d^2+..+d^h=n\\
 \dfrac{d^{h+1}-1}{d-1}=n\\
 h=log_d[n{d-1}+1] - 1
 $$
This is my implementation:

EXTRACT-MAX(A)
1  if A.heapsize < 1
2      error "heap underflow"
3  max = A[1]
4  A[1] = A[A.heapsize]
5  A.heap-size = A.heap-size - 1
6  MAX-HEAPIFY(A, 1)
7  return max

MAX-HEAPIFY(A, i)
1  assign depthk-children to AUX[1..d]
2  for k=1 to d
3      compare A[i] with AUX[k]
4      if A[i] <= AUX[k]
5          exchange A[i] with AUX[k]
6          k = largest
7  assign AUX[1..d] back to A[depthk-children]
8  if largest != i
9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )

The running time of MAX-HEAPIFY:

$$T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$$
where $c_i$ denotes the cost of i-th line above.
EXTRACT-MAX:
$$
       T_E = (c_1+..+c_7) + T_M \leq C*d*h\\
       = C*d*(log_d[n(d-1)+1] - 1)\\
       = O(dlog_d[n(d-1)])
       $$

→ Is this an efficient solution? Or there is something wrong within my solution?


texts: Question about proving that Rado's function is non-computable

texts:
I am currently following the proof, found here, that Rado's function
$$
\Sigma (n) = \max \{ \text{# of 1's that may be written to a tape by an n-state turing machine} \}
$$
is non-computable. Within this proof, they say that there exists a Turing machine $M_F$, which we say has $n$-states, that writes $F(x)$ 1's to the tape.

However, they then go on to imply that there exists a Turing machine with $n$ states which writes $F(F(x))$ 1's to the tape! Surely, since $F(x) > x$ this should require more than $n$ states - since more states $\iff$ more 1's?

EDIT: For added clarity, I will now explain why I have interpreted this to mean that both $F(x)$ and $F(F(x))$ have $n$ states.

This proof first defines a Turning machine $M_F$ which has $n$ states and writes $F(x)$ 1's to the tape before halting. It then goes on to describe a (trivial) $x$-state Turing machine $M$ which "on input $\Lambda$" writes $x$ 1's to the machine's tape.

The proof then goes on to claim that
$$
\Sigma (x + 2n) \geq x + F(x) + F(F(x))
$$
which means that there exists a $x + 2n$ state Turing machine which prints $x + F(x) + F(F(x))$ 1's to the machines tape.

I am assuming that these $x + F(x) + F(F(x))$ 1's are written as follows:

The $x$ state Turing machine $M$ prints $x$ 1's to the tape.
Next, $F(x)$ 1's are written to the tape by the $n$ state Turing machine $M_F$
So far, we have written $x + F(x)$ 1's and $x+n$ states have been used to do so. Comparing this to the fact that $x + F(x) + F(F(x))$ 1's may be written using $x + 2n$ states, they are implying that there must exist a Turing machine which writes $F(F(x))$ 1's using $n$ states

I am probably interpreting this incorrectly, but I don't know why?


texts: How to represent sums of piecewise quadratic functions for efficient optimisation?

texts:
I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has a continuous compactly supported piecewise linear distribution of possible time allocations; the total contention at any time is then a certain sum of pairwise products of these individual piecewise linear distributions (this is the JointHeight criticality estimate, see [1]). As a consequence I am interested in the following:

Question: How can one represent sums of continuous compactly supported piecewise quadratic functions, in a way which affords efficient implementations of:

adding/removing/modifying a summand,
finding the maximum.

As D.W. points out, if a summand that is added/removed/modified spans the whole domain of support of the sum, then it seems inevitable to need to traverse the whole thing. However, when that domain is rather smaller, I'd hope to be able to efficiently update the whole sum without incurring an $\textrm{O}(\#\textrm{Tasks})$ cost; I should only need to update the control points that overlap the domain of the modified task.

After making each search decision, constraint solving takes place, resulting in the modification of the availabilities of certain tasks. My goal is to be able to efficiently update the above representation with these modifications, so that one can efficiently recompute the new time which is under maximum contention after these updates.

Now, a sum of continuous compactly supported piecewise quadratic functions is itself continuous, compactly supported and piecewise quadratic. Once one has an explicit piecewise quadratic expression, it is straightforward to compute the maximum. However I haven't figured out an implementation which would allow me to efficiently recompute the control points when adding/removing/modifying a summand.

A point of comparison is the PiecewiseExpand function from Mathematica. PiecewiseExpand can take a sum of piecewise functions and return an explicit piecewise expression, with the minimal number of control points. So I'd be interested in knowing how such a function is implemented.

[1] Beyond Contention: Extending Texture-Based Scheduling Heuristics (1997, AAAI'97/IAAI'97).
J. Christopher Beck, Andrew J. Davenport, Edward M. Sitarski, Mark S. Fox


texts: AdaBoost - why using such alpha function?

texts:
I'm reading the paper where AdaBoost was invented (link), and I couldn't understand why they have chosen the formula α_t = 1/2 * ln((1-ε_t) / ε_t).
snippet:
AdaBoost algorithm from the paper
What is the motivation behind that specific formula?
Why not using something that feels more natural like ε_t?


texts: Algorithm for the following graph transformation

texts:
Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$:

For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$
For every $(z,i)\in V'$ and $zu\in A'$ we add the vertex $(u,i+w_{zu})$ and the arc $(z,i)\to(u,i+w_{zu})$
In each path of $D'$ the only vertex of $V$ that can be repeated is $v$ (and the path most end there)

For example if we have the graph $D=(V,A)$ with:

$$V = \{u,v,x,y,z,a\}$$
$$A = \{vz,zu,uv,vy,yx,xv,xu,xa\}$$

the new graph will be given by

$(v,0)\to(z,w_1)\to(u,w_2)\to(v,w_3)$
$(v,0)\to(y,w_4)\to(x,w_5)\to(v,w_6)$
$(x,w_5)\to(u,w_7)\to(v,w_8)$
$(x,w_5)\to(a,w_9)$

where the $w$'s are the respective sums of the weights.

At first I tried to attack this problem using a DFS type of approach, but given that the nodes can be repeated under certain conditions I got stuck and with no clues on how can this graph be constructed (algorithmically). Any ideas?


texts:
I went through the rules of Moore and Mealy Machine or FA. I read that both could have one initial state and no final state.

If Moore Machine has one initial state then there is a problem for converting those Mealy Machines into Moore Machines in which inputs coming towards the initial state give different outputs. In this case we will get a Moore Machine which will have many initial states.

For example: if we convert the following Mealy Machine then we will get a Moore Machine with two initial states!

Is there any way to convert such Mealy Machines into single initial state Moore Machines?


texts:
Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants.

$T(n) = a$, if $n = 2$

$T(n) = 2T(n/2) + cn$ if $n > 2$
Use induction to prove that $T(n) = \Theta(n \log n)$

Any idea on how to solve this?


texts: Help with reviewing locking logic for sync system

texts:
I'm implementing a sync algorithm where multiple apps sync files with a data source. Syncing is already working and has been for several years so there's no issue with this.
Now I want to implement a way to lock the data source, to tell clients that they shouldn't write to it anymore. This will be used to upgrade the data source - i.e. upgrade its structure, move folders around, etc. which needs to be done when nothing else is syncing.
So I came up with the following algorithm, inspired by [SQLite 3 locking mechanism][1], but changed to take into account that it's network based.
There are three types of locks, and a client request a lock by POSTing a file to the data source. The locks are:

SYNCING: The client is syncing - any other client can still read or write to the data source. There can be multiple SYNCING locks.
PENDING: The client wants to acquire an exclusive lock on the data source - any other clients can still read or write to the data source, but no new SYNCING lock can be posted. There can be multiple PENDING locks.
EXCLUSIVE: The client has locked the data source - no other client can read or write to it. There can be only one EXCLUSIVE lock.

And it would work like so:

When a client starts syncing with the data source, they acquire a SYNCING lock. When a client finishes syncing, they release the SYNCING lock they've created
When a client needs to lock the data source, it first posts a PENDING lock. When a PENDING lock is present, no new SYNCING or PENDING locks can be posted. Clients that are syncing however can complete the process. The client who has acquired a PENDING lock will poll the data source and wait for all SYNCING lock to be released. When they are all gone, the client checks for all the PENDING locks - if there are others, the client checks the timestamps of these other locks and if his lock is not the oldest one, it deletes it and exit. Locking failed, and it will need to try again later.
If the PENDING lock is the oldest, then the client posts an EXCLUSIVE lock. At this point, no other client can post any other lock.

I'm wondering if I overlook something with this system, like I'm wondering if there could be some race conditions in some cases?
For now, I'm not dealing with clients that post a lock then crash, there will be some logic to clean up. At this point, I just want to make sure that this system will only allow one client to acquire an EXCLUSIVE lock. Any ideas?


texts: How can i compare lossy image compression techniques?

texts: I need to find which lossy image compression technique is the best. I chose to test JPEG, WebP and BPG. Which criteria can I choose for comparison apart from quality and speed of compression and how can I measure each criteria using tools like PSNR?


texts: Hash function which is invariant under small changes

texts:
I am looking for a hash function which is invariant under small changes.

E.g., if I have two strings MyString and MySttring which slightly differ, their hash values should only differ slightly as well.

Actually, this is the opposite of the normal concept of a hash functions (Avalanche effect) where even slight changes in the input lead to big changes in the output.

Does any one know of such a concept or a hash function?
(It should not be the identity function ;))

Background:
I want to store personal data (name, surname, date of birth). Due to data privacy laws, it is not allow to store the data in clear text. So, I need to hash it.
There might be typing errors or OCR errors when storing the data. So, two hash values of the same person might differ. But they should only differ a little, so I know that the input data must have been very similar.


texts: Complexity of using Extract-Max to extract n/2 elements from a max-heap with n distinct elements

texts:
I've been given the following question and I've been finding it hard to give a good answer:

Prove or disprove: given a max-heap with n distinct elements, using Extract-Max to extract n/2 of the elements takes Ω(nlogn) time.

Because the heap contains distinct elements, I'm lead to believe the claim is true: I've tried to create heaps with distinct elements such that Extract-Max would take O(1) for n/2 extractions, but just couldn't do it. So, in order to prove the claim, I've tried to prove another claim that could help - that in a heap with distinct elements, Extract-Max would take Ω(logn) except for maybe the first few times, but couldn't prove it either.

Does anyone have a nice way to prove/disprove this?


texts: How to handle negative edge weights in distance vector routing protocol with a digraph?

texts: In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors).  How would a source node identify a destination node it could reach at an infinitely low cost by traversing a negative cycle over and over again?


texts: If lower bound of a problem is exponential then is it NP?

texts:
Assuming that we have a problem $p$ and we showed that the lower bound for solving  $p$ is $\mathcal{\Omega}(2^n)$.

can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?


texts: Approximation ratio of greedy algorithm for makespan

texts:
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

The approximation factor of the modified greedy [scheduling] algorithm is 4/3.

And gives the example:

Note that 4/3 is essentially tight. Consider an instance with m machines, n=2m+1 jobs, 2m jobs of length m+1,m+2,⋅⋅⋅,2m−1 and one job of length m.

now how can number of integers in the range m+1,m+2,....,2*m-1,be 2*m ?


texts: Computing the line equations of two crossing tangents in a point set separated by a vertical line?

texts: I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations for both l1 and l2, as listed in the picture. My understanding is that this is a linear programming problem. The algorithm I'm looking for would run in O(n+m) time. I have only been able to find examples of O(n log n) time, and I'm not quite sure where else to look for O(n+m) time specifically.


texts: Choosing error rates for probabilistic algorithms

texts:
Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ iterations. This is a fine situation to be in, because $2^{-k}$ can be made as close to $1$ as you like without having to make $k$ very big at all. At this point, the theoretician sits back contentedly, his or her job done.

In practical terms, though, are there any guidelines as to which value of $k$ should one choose? Obviously, there's no universal answer, since the answer in any particular situation will be a trade-off depending on the importance of avoiding errors and the cost of doing more iterations.

For example, choosing $k=10$ gives an error rate of about one in a thousand, which seems rather high for most purposes; choosing $k=60$ means the expected number of errors would still be less than one even if you'd run the algorithm once a second since the big bang.


texts: Constrained (linear) NFA-epsilon to DFA conversion

texts:
Goal: convert NFA -> DFA
Overall goal: see if the intersection of 2 of these NFAs is empty.
This will be done by converting to DFAs then DFA intersection.

input NFA: multigraph between states (each edge has 1 alphabet symbol xor epsilon)

The NFA happens to look like a linear list of states:
${S_1, S_2, ..., S_n}$
where edges only exist from $S_{i}$ to $S_{i+1}$

$S_1$ is the start state
$S_n$ is the only accepting state

Known NFA -> DFA algorithm: SC (subset construction) (exponential in worse case).

Given the constraints on the NFA, is SC provably polynomial?
Given the constraints on the NFA, is there a more efficient conversion algorithm?

Here we're measuring efficiency as runtime: a function of $n$, the number of NFA states.


texts: How Can We Classify Summit Supercomputer in Terms Of Topology

texts: Summit supercomputer has Processor: IBM POWER9 22C 3.07GHz Interconnect: Dual-rail Mellanox EDR Infiniband. So how can we classify in terms of topology? How can I find resources about this subject?


texts:
I had two questions on my automated test which I don't understand the answer for.

$\log(n!) = \log(n\cdot (n-1)\cdot  \cdots \cdot 2\cdot   1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(n))$. But is it also in $\Omega(n \log(n))$? I don't think so, but my automated interview test thought so!

$\log(n)+\log(n^2) = \log(n)+2\log(n) = 3\log(n)$. So, it is in $O(\log(n))$, $\Omega(\log(n))$ and $\Theta(\log(n))$. But for some reason my automated interview test thought otherwise.

Is my understanding correct or is the automated test correct?


texts:
I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?

Inputs: two numbers $(a,b) \in \mathbb{N}$
Output: $a^b$


texts: Find set of non-overlapping rectangles in a 2D grid

texts:
I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid.  Each rectangle is a subset of the cells.  (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.)

I want to find a subset $S$ of rectangles, so that $S \subseteq R$, so that no two rectangles in $S$ overlap, and so that $S$ is as large as possible.  (Alternatively, you can think of this as finding a maximum independent set in a graph where we have one vertex per rectangle, and an edge between two rectangles if they overlap.)

Can this problem be solved in polynomial time?  Is it NP-hard?

I can see how to solve the one-dimensional analog (maximum set of non-overlapping intervals) in polynomial time using dynamic programming, but that algorithm doesn't seem to extend to this case.  Wikipedia calls this the maximum disjoint set problem and says that when the set of shapes is arbitrary, the problem is NP-hard, but it doesn't discuss the specific case of axis-aligned rectangles with integer coordinates.  That makes me suspect this problem might be NP-hard, but I haven't found a reference or proof of that.


texts: Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"?

texts:
$O(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ [Source A], [Source B]
Say $t_{n} \in O(n)$
By formal definition $t_{n} \leq k \cdot n$  [Source C]

But how can this be? Say $t_{n}$ is actually $n^{2}$, then $t_{n} \leq k \cdot n$ is just false. Would it not be more logical to have $t_{n} \geq k \cdot n$ as a formal definition acompanying $O(n)$?


texts:
As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning algorithm at least make sure that every kid gets a gift once in a while while Santa also serves as many kids as possible each year?

Consider a complete graph with real, positive weights and a constant $k$. We want to solve a variant of the Travelling Sales Person problem:

  Is there a circular route of length at most $k$ that serves more than $m$ nodes?

The optimisation version would be:

  Maximise the number of nodes that can be served with a circular route of length at most $k$.

This is motivated by real-world limitations on routes: Santa has one night to deliver as many gifts as possible, a sales person has eight hours for one day's route, and so on.

The first, but not final question is: how hard is this problem? Let's assume we can start at any node, but that should not make too much of a difference.

Now, in order to model fairness, let's assume there are $N$ nodes and we can visit at most $M$ with every tour. Ideally, we would want that every node is visited $t\cdot\frac{M}{N}$ times across $t$ efficient tours. Since there may be bottleneck nodes that have to be visited more often in order to ensure routes visit many nodes, some will inevitably have to be visited less often. That also excludes the trivial approximation of removing once visited nodes until all have been visited.

So, here is the final question. Let $T$ be the number of tours needed until all nodes have been visited by efficient $k$-tours. How can we algorithmically determine the minimal value of $T$ (and all the necessary routes)? How complex is this problem?

I guess this is really a multi-criterial problem: each tour should visit as many nodes as possible while we want to keep tours as disjoint as possible.


texts: Predicting energy consumption of households

texts:
I have the dataset which you can find here, containing many different characteristics of different houses, including their types of heating, or the number of adults and children living in the house. In total there are about 500 records. I want to use an algorithm, that can be trained using the dataset above, in order to be able to predict the electricity consumption of a house that is not in the set.

I have tried every possible machine learning algorithm (using weka) (linear regression, SVM etc) . However I had about 350 mean absolute error, which is not good. I tried to make my data to take values from 0 to 1, or to delete some characteristics. I did not managed to find some good results.

I also tried to use R tool, and I did not have good results either...

I would be very grateful, if someone could give me some advice, or if you could examine a little the dataset and run some algorithms on it. What type of preprocessing should I use, and what type of algorithm?

I have posted a similar question last month, but I did not get any useful answers.


texts: Channel capacity of DMC with each transmission having different distribution

texts:
I got this doubt while reading about AVC in Csiszar Korner's book.

Corollary 12.3 The $\epsilon$-capacity of the AVC {$W : X \to Y$}
average probability of error equals, for every $0 < \epsilon < 1$, the
corresponding $\epsilon$-capacity of the AVC {$\mathcal{\bar W} $}. It does not exceed
the minimum of $C(W)$ as $W$ ranges over $\bar W $ where $C( W)$ is the
capacity of the DMC {$W$}.

Here, $\mathcal{\bar W}$ is the closure of all channels given by varying state sequence $\vec s$. I am wondering how $C(W)$ can be the capacity of the AVC as we need to analyze it for blocks on code length $n$. What the author has written makes sense for the capacity 'expression'. The capacity of AVC need not be that expression. It would make sense to me if the following can be proven true.
Given a class of DMC $\mathcal{W}$ which consists of DMCs $W$. All these $W$ are the normal DMC and their capacity is given by
$$\max_{P_X} I(X;Y)$$
Suppose that for each symbol transmission, one of the DMC $W \in \mathcal{W}$ is chosen by someone (possibly adversarially), then what can we claim about the new channel capacity? Intuitively, it feels like the worst case scenario would be when all the transmissions take place with the worst channel in $\mathcal{W}$ (in terms of capacity). In such case, capacity would be the normal capacity of the worst DMC in $\mathcal{W}$, ie,
$$ \max_{P_X} \min_{W \in \mathcal{W}} I(X;Y) $$
However, I am not sure if this is true and I do not know how to show that this is indeed the worst case scenario. Can someone please shed some light on this?


texts: Is this protocol suitable for transaction services?

texts:
The paper Eventually-Serializable Data Services (PODC'96) presented an eventually-serializable data service.

In the abstract, it says：

  … and generalizes their algorithm (in the related work Lazy replication) by allowing general operations …

In section 1.1 (Background of our Work), it says:

  … Also, their algorithm (in the related work Lazy replication) requires that all operations be either read-only queries or write-only updates …

My questions is as follows:

  Is the protocol in this paper suitable for transactions (as a kind of general operations) services?

Specifically:

In section 3, the authors give an abstract algorithm for implementing eventually-serializable data service. The algorithm is based on lazy replication, in which the operations received by each replica are gossiped in the background. The key property is that the operations requested in a partial order will be eventually total ordered through the gossip protocol. I want to extend this eventually-serializable notion to support transactions. Does this algorithm itself support transactions already? And what are the challenges to support transactions instead of ordinary operations?


texts: Algorithm for implementing the modulus "%" operator?

texts:
How can an efficient modulus operator be implemented?

Here's a naive way of defining A % B:

  given $(a,b) \in \mathbb{Z}$ (represented as int)

  while $a > b$ : $(a,b) \mapsto (a-b,b)$

  return $a$

This could be very slow. E.g. $(a,b) = (10^7, 13)$.  I could be subtracting 13's for a long time.

One more possibility is that % is defined in terms of another infix operator / as well as the int function (here in C and verbatim in Python):

  a % b = a - (b * int(a/b))

This is probably not how Python implements it's modulus operator (as it makes a call to C or Fortran).   The % operator is need to reduce fractions or compute GCD's.

Here are some examples of truncation and division from Wikipedia:


texts: External Sorting - Calculate passes with different number of disks

texts:
Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort)
a)  If we have 1 disk find minimum available to sort file in 2 passes
b)  If we have 2 disks how many passes we need to sort the file completely
I have started to read about external sorting and i am confused about how to answer this questions. I don't know how to think about to solve it.
I read the solution of this exercise 1 which is in the textbook that i read https://www2.cs.duke.edu/courses/spring03/cps216/lectures/rec-03-quiz.pdf
and i am confused about the connection of terms in 2 exercises. So i need some help to solve the questions that are solved in the link-file but with my data.


texts:
I am reading about Base & Bounds memory protection mechanism, and I noticed the use of the term 'relocation' in the context of address space, but failed to understand the meaning associated with it.

Below are some examples:

U.C Berkeley L02/CS162:

  relocating loader

Wisconsin S15/CS537

  Each process appears to have a completely private memory of size equal
  to the bounds register plus 1. Processes are protected from each
  other. No address relocation is necessary when a process is loaded.

Furthermore, I searched for the term and found only the definition on Wikipedia that wasn't very clear to me.

Does anyone have any idea?


texts: Polynomial hierarchy: inclusion between spaces

texts:
Using the definition for the polynomial hierarchy:

$$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$
$$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$

I have been asked to to show that:

$$ P^{\Pi_k^P } \subseteq \Pi_{k+1}^P $$

I don't really have many ideas on how to go for it:

by definition $ P^{\Pi_k^P } $ is the set of languages accepted by a $PTIME$ deterministic TM with an oracle answering queries in $\Pi_k^P$, while $\Pi_{k+1}^P$ is the set of languages accepted by a universal alternating TM, with an oracle answering queries in $\Sigma_k^P$.
If I could use a universal ATM $M_A$ to simulate a DTM (and I would say I can't) then I should be able to recognize a language $L \in P^{\Pi_k^P}$ by noticing that $L$ is accepted by a DTM $M$ that uses the oracle $O$ (that answers about $\Pi_k^P$), thus taking a universal ATM $M_A$ to simulate $M$ and another universal ATM $M_O$ (accepting queries in $\Pi_{k+1}^P$) to simulate the oracle (since $\Pi_k^P \subseteq \Pi_{k+1}^P $).

But I really think this reasoning cannot be done, as actually I'm not using the oracle…how should I approach the problem?


texts: Example of pseudo-peripheral vertex which is not peripheral vertex

texts:
I need to find an example of a pseudo-peripheral vertex which is not a peripheral vertex. I came up with this example, where diameter is 4 and pseudo-peripheral vertices labeled aqua. Am i right here?

$$\mbox{dia} = 4$$
$$e(9) = e(4) < \mbox{dia}, e(8) = e(4) < \mbox{dia}$$

Could you provide other examples? Maybe some interesting theorem on how to build such?


texts: Is protein folding really NP-hard and how to show that?

texts:
This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a lattice (similar to self-avoiding walk):

Simplification significantly reduces the computational effort in handling the model, although even in this simplified scenario the protein folding problem is NP-complete.

However, this simplification takes a continuous problem which has some local convexity characteristics in real life into an integer programming problem, because protein folding resembles the problem of finding the global minimum on some continuous energy "cost function", also known as the energy landscape as illustrated by Ken Dill et al., 2012:

As stated by others, translating a problem defined over continuous domain into problems over the integers or a binary lattice may introduce higher complexity cost. You may think about it as taking a linear problem and solve it using 3SAT solver, any problem in $P$ is presumably reducible to 3SAT. I assume that there is a convex nature to the energy landscape, and this piecewise convexity is beneficial for the search for the minimal energy state.
How to reduce hydrophobic-polar protein folding to TSP/3SAT/CNF?
The work by Bahi et al. really confused me. I expected it to be something relatively simple to reduce 3SAT or TSP to the problem of protein lattice, because intuitively it seems that finding Hamiltonian path could be stated as finding a protein conformation on a lattice.

Bahi, Jacques M., et al. Computational investigations of folded
self-avoiding walks related to protein folding. Computational biology
and chemistry 47 (2013): 246-256.
Bahi, Jacques M., et al.  Chaos of protein folding. In IJCNN 2011,
Int. Joint Conf. on Neural Networks, pages 1948–1954, San Jose,
California, United States, July 2011.
Bahi, Jacques M., et al. Protein folding in the 2D
hydrophobic-hydrophilic (HP) square lattice model is chaotic.
Cognitive Computation, 4(1):98–114, 2012.
Bahi, Jacques M., et al. Is protein folding problem really a
NP-complete one ? First investigations. arXiv:1306.1372, October 2012.
Submitted to Journal of Bioinformatics and Computational Biology
(Elsevier).
Bahi, Jacques M., et al.  Unfoldable self-avoiding walks are infinite.
Consequences for the protein structure prediction problem. arXiv.org,
2013.
Bahi, Jacques M., et al. Protein structure prediction software
generate two different sets of conformations. Or the study of unfolded
self-avoiding walks. arXiv:1306.1439, 2013.


texts: Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

texts:
For example:
This looks like a context free grammar:
 →
 →  |
 →  |
 →  | c

but it can be reduced to this regular language:
 →  |
 →  |
 →  | c

I want to know if it is possible or not and why


texts: How can an A* algorithm visit all nodes?

texts: Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?


texts: Checking Feasibility of Linear Program in Polynomial Time

texts:
Given a linear system of the form:

$$\begin{array}{c}
x_r = a \quad x_j = b \\
c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\
x_1+x_2 + x_3 + \ldots + x_n = k\\
0 \le a,b,x_1,x_2,x_3...x_n \le 1\\
k \ge 0
\end{array}$$

How quickly can the feasibility of the system be checked? To clarify: $x_r,x_j$ are members of $x_1,x_2...x_n$. Would it be $O(n^{3.5})$ since I believe that is the general complexity for running a linear program or would it be less? Can one use gaussian elimination to quickly reduce the first 4 equations in $O(n^3)$ and after that systematically move through the equations starting from the terms with largest coefficient and moving to terms with smallest coefficient assigning values that bring the equations as close to satisfactory as possible?

Additional info:

I am assuming that the number of variables scales linearly. $n \ne N$ (I think that was clear though).


texts: Time complexity of $T(n) = nT(n-1) + n^2$

texts:
This time complexity comes from $N$-queen problem. There are many threads talking about the time complexity to be $O(n!)$ but I cannot figure out how we get it. Here is the progress I have so far:

$$
\begin{align}
T(n) & = n T(n-1) + n^2\\
& = n(n-1)T(n-2) + n(n-1)^2 + n^2\\
& \vdots\\
& = n! + n! + n(n-1) \dots 2^2 + n(n-1) \dots 4*3^2 + \dots + n(n-1)^2 + n^2
\end{align}
$$

RHS and LHS divided by $n!$

$$
    \frac{T(n)}{n!} = 2 + \frac{2}{1!} + \frac{3}{2!} + \dots + \frac{n-2}{(n-3)!} + \frac{n-1}{(n-2)!} + \frac{n}{(n-1)!}
$$

From comments in GeeksForGeeks the RHS converges to a constant. Can anyone please explain why the RHS converges to a constant?


texts: Question about the undecidability of $A_{TM}$

texts:
You probably know this one (or at least a version of it).
Let $P$ be a program code, and $w$ be an input string.
Define $A_{TM}=\left\{(P,w)| P(w)=1\right\}$.
Meaning: $A_{TM}$ is the set of all ordered pairs $(P,w)$ s.t. $P$ accepts $w$.
$A_{TM}$ is undecidable.

I just read the proof for it, that made me wonder about something.
The brief of the proof (by contradiction) looks something like this:
Suppose there exist $D_{A_{TM}}$ - a computer program that answers 'yes' if $(P,w)\in A_{TM}$, and 'no' if $(P,w)\notin A_{TM}$.
Let us consider the following program:

$Q(w):$
1. run $D_{A_{TM}}$ on $(w,w)$
2. if $D_{A_{TM}}$ returned 'yes', then return 'no'.
if $D_{A_{TM}}$ returned 'no', return 'yes'.

Now running $Q(w);$ with the input $Q$, contradicts the existence of such $D_{A_{TM}}$

This is a brief, since I assume most of you already know this problem (and its proof).

Now what makes me wonder is this: when I looked at $A_{TM}$, and needed to determine if it's decidable or not, the first thing that came to my mind when I tried to imagine a machine that accepts $A_{TM}$, is how can machine like that handle inputs $(P,w)$ s.t. $P$ doesn't halt on $w$?  How can it 'predicts', beforehand, that $P(w)$ goes to an infinite loop, without actually running $P$ on $w$?
That intuition, as it turns out, wasn't wrong.
The thing is: How come the proof, as clever as it is, has nothing to do with that fact?
You'd expect it to lean - and even in the slightest way - on that leverage, but instead, the proof looks like something that was taken from the realm of paradoxes.

Basically, what I'm asking is: why does this proof work?


texts:
I have to count the number of one's in last $m$ bits in a stream of bits and $m \leq n,$ where $n$ is the window size and it should take polylogarithmic space in $n$. I could only store last $n$ bits and then count the number of one's in those $n$ bits but it takes $O(n)$ space. How to achieve it in $O(\log^k n)$, $k>0$.
Any hint would be appreciated.


texts: How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

texts:
The theorem states that

$$
H(P)\leq\mathrm{MinACL}(P)<H(P)+1
$$

where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word length of any Huffman coding and $H$ means the entropy of the probability distribution $P$.

Now, the problem is how to show that for any $\epsilon>0$, there is a probability distribution $P$ s.t. $\mathrm{MinACL}(P) - H(P)\geq1-\epsilon$?

(I was given a hint that I can start with a source s.t. $H(P)=\mathrm{MinACL}(P)$ and try to change the probabilities in order to skew the code.}


texts: Time to construct a GNBA for LTL formula

texts:
I have a problem with the proof for constructing a GNBA (generalized nondeterministic Büchi automaton) for a LTL formula:

Theorem: For any  LTL formula $\varphi$ there exists a GNBA $G_{\varphi}$ over alphabet $2^{AP}$ such that:

$\operatorname{Word}(\varphi)=L_{\omega}(G_{\varphi})$.
$G_{\varphi}$ can be costructed in time and space $2^{O(|\varphi|)}$, where $|\varphi|$ is the size of $\varphi$.
The number of accepting states of $G_{\varphi}$ is bounded above by $O(|\varphi|)$.

My problem lies in the proof of (2), that is, in the proof it says that the number of states in $G_{\varphi}$ is bounded by  $2^{|\operatorname{subf}(\varphi)|}$ but since $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ (where $\operatorname{subf}(\varphi)$ is the set of all subformulae) the number of states is bounded by  $2^{O(|\varphi|)}$.

But why does $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ hold?


texts: Why do we try to maximize Lagrangian in SVMs?

texts:
I was learning about support vector machines from MIT OpenCourseWare. I figured it out. I understand why we try to minimize $\frac{1}{2} w^2$. I just did not get why we try to maximize Lagrange expression like said at 35:56 in the YouTube video.

Margin (width) of the support vector is $2/\|w\|$. We want to maximize width it means that we also want to minimize $\|w\|$ from the equation $2/\|w\|$. It is true that we also want to minimize $\frac{1}{2}\|w\|^2$. Now we use Lagrange expression here, $$L = \frac{1}{2}\|w\|^2 + \sum_i α_i(y_i(w \bullet x+b)-1).$$ To find the minimum of $\frac{1}{2}\|w\|^2$, we apply gradient; $∇L = 0$. From the $∇L = 0$ equation, we get $Σ_iα_iy_i = 0$ and $w = Σ_iαi_iy_ix_i$. Then by using $Σ_iα_iy_i = 0$ and $w = Σ_iα_iy_ix_i$ equations and putting this in the Lagrange expression we end up with $$L(w,b,α) = \sum_iα_i-\frac{1}{2}\sum_{i,j}y_iy_jα_iα_j(x_i\bullet x_j).$$

I really understand up to here, but the professor said that we want to maximize $L$ here, why?
I really don't understand. Why are we trying to maximize the Lagrange expression? I thought we were trying to minimize it.


texts:
Language:

$ L = a^{n+m}b^{n}c^{m} $

As per a recent test I gave, this language is not context free.

However, I think it is.

Corresponding Grammar:

$ X \rightarrow aXY \space |\space \epsilon $

$ Y \rightarrow b \space | \space c $

Pushdown Automata:

Keeping pushing all $a$ to the stack, until a $b$ is scanned. Keeping popping  $a$ from stack for each character scanned, until end of input.

If, after the end of input the stack is empty accept the string. Else, go to non-accepting state.

Please let me know if I'm thinking along the right lines or if I've missed something..


texts:
Like Linked-list for Array, is there a recursive counter-part for Matrix?

Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?


texts: Can we do better than $O(n\log n)$ building a balanced binary tree?

texts:
I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?

Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. If these properties hold then it seems to me that it must be possible to build a balanced binary tree in better than $O(n\log n)$ time.

I don't believe this so I'm wondering where the flaw is in my thinking.

The data-structure is the conc-tree list. In it's standard form it looks like a normal binary tree and comes with a concat operation that ensures the invariant that the left and right subtrees of any node never differ in height by more than one. As expected concat has complexity $O(\log n)$.

But there's a builder variant of the conc-tree list called the Append list. This variant allows for temporary height differences in subtrees of more than one. Amortized $O(1)$ time appends are claimed for this variant.

So it seems appending $n$ elements must have a complexity of $O(n)$.

However it's a characteristic of this variant that whenever $n$ is a power of two one ends up with a complete balanced binary tree (containing all elements inserted so far). So while temporary imbalances are allowed the tree becomes balanced every power of 2 insertions.

In this variant a new class of nodes, called Append nodes, are introduced and it's these nodes whose subtrees are allowed differ in height by more than one. However every $2^k$ insertions all such temporary nodes are eliminated.

The Wikipedia page page describes the algorithm fairly succinctly (see the description of the basic data-structure and the append method in particular).

So when $n$ is a power of two our cost for inserting elements is $O(n)$ and we've built a balanced binary tree. Or so it seems.

In a separate question I effectively asked "if I can state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, is this enough to allow me to state the complexity for all values of $n$?"

I can see from Yuval Filmus's answer that the answer is no, but that "in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold."

So it seems to me that in this case if inserting $n$ elements has complexity $O(n)$ and every $2^k$ elements I have a balanced binary tree then the cost of building balanced binary trees with this conc-tree variant approach must be $O(n)$.

So what's wrong here? To be honest I can't see the amortized $O(1)$ append time claimed for this variant. I can see that often insertions do have cost $O(1)$ but that when one looks at what's happening with the temporary Append nodes the overall insertion cost looks to me to be amortized $O(\log n)$.

If this is the case then building our balanced binary tree has an unsurprising $O(n\log n)$ cost.

Sorry for such a long question and sorry for not going into detail about the algorithm in question - instead leaving you to look around on Wikipedia.


texts: Finding the value of y for given equation?

texts:
Given the equation :
x & y = x, where x, y are positive integers.

Note: Here '&' stands for Bitwise operator AND between two numbers.

I am provided with the value of x. Can I find possible values of y satisfying the given equation ?

Thanks for help!


texts:
One approach for querying knowledge graph is to use nearest neighbor (NN) data structures. Read the paper On Integrating Knowledge Graph Embedding into SPARQL Query Processing for more details. Roughly speaking, the authors redesign the loss function used for knowledge graph embedding methods to generate vector representations that improve the NN search performance. For example:

Nonetheless, the following fact is know:

  It is known that using the same embedding space to represent both entities and relations is less competitive compared to considering two separate spaces. (source: LogicENN: A Neural Based Knowledge Graphs Embedding Model with Logical Rules).

My question is: Since there are embedding which represent entities and relations in different spaces, how can I use NN methods to ask a Knowledge Graph?


texts: How can Computer Science theories and inquiries be resolved?

texts:
It's probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I've been reading through this list), but how would we go about proving any of those things? Have there been any proofs to any computer science theories, or answers to any substantial computer science questions (such as the ones in that list)? Are they like mathematical proofs (such as Grigori Perelman's resolution to the Poincaré conjecture)? I know that the P versus NP problem seems out of my league, being a junior in high school, but it's a problem that intrigues me, and I would really like to see how others (if any) have answered other, related questions, because I would like to look into a resolution to the problem.

This isn't a duplicate of this question primarily because physics isn't computer science, and secondarily because, unless I'm mistaken, computer science theories are not proven the same way that theories related to physical sciences are proven. They're more like mathematical proofs in that they're logical (right?).


texts: What is the earliest use of "trees" in computer science?

texts: I have a little history question, namely, as the title says, I am looking for early uses of trees  (as a data structure, search tree, whatever) in computer science.


texts: Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

texts:
A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, describing the problem with inequalities alone can suffice, as $a\le b$ and $a\ge b$ is equivalent to just $a=b$. For this reason, a lot of literature just focuses on the inequalities.

However, I only have quadratic equality constraints, without any inequalities. In fact, it's enough constraints, that I believe in my case the space of points satisfying the constraints is discrete (like $2^{n/2}$ separate points or something). So it becomes very little of an "optimization" problem, and much more of a "search space" problem. I would like to figure out a way to transform this system into a form amenable to discrete search, but I can't find any directives on how to accomplish that. All the heuristics/approximations I could find for QCQP definitely seem to treat more of the "not very constrained" case, where you're moving around continuously in the allowed region -- that picture doesn't apply here, though.

I realize that searching all $2^{n/2}$ points is intractable in general, of course. But I hope that whatever form it would come in would then be amenable to its own heuristic searches, like a binary quadratic program is.


texts: How could i create a multi-threading system in a kernel?

texts: Im trying to figure out if there's an assembler instructions or a bios intruction to get multi-threading in a kernel. In the case that doesn't exist that, how could i set muti-threading in a kernel?


texts: Regular expression that have the same number of 0 and 1

texts:
I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I cant figure out how to solve it.

Could I get a hint on how to construct a regular expression that describe the following language given the alphabet $\Sigma = \{0, 1\}$:

$A = \{w \in \Sigma^ * : |w|_0 = |w|_1 \cup \Sigma^*\{00,11\}\Sigma^*\}$

Some examples that I think might be right:

00011 belongs to the language

0does not belong to the language

1does not belong to the language

0011 belongs to the language

01010101 belongs to the language

$\lambda$ belongs to the language because $w_0=0$ and $w_1=0$

One solution that I found so far is that the regular expression $\alpha$ would be:

$\alpha = ((0 \cup 1) \Sigma^*)^*$

However, to be honest, I really does not have sure if this one is correct.

Could please someone clarify this one?

Thanks !


texts: The order of which time complexity is higher, 3 ^ log(n) or n ^ 3?

texts:
Which one has a higher order time complexity:

$n ^ 3$
$3 ^ {\log n}$

I know that an exponential time order is higher than polynomials. However, it uses a logarithmic power which is low for a large n, while n^3 or more could remain still high, not?


texts:
What am I doing?

I have been digging more and more and googling more than often finding very small amount of results

I am trying to make a RAM testing program that can do memory testing with the ability to detect most RAM problems, I am making this app because I want to add networking functionality to it so all of the clones of this app connect to one PC on a specific IP and send results to it and then the results are visually displayed

What do I want?

I am looking for an algorithm so it can detect most problems at an affordable time.

What I have tried?

I have found this Power Point file, it contains a good amount of information, I have read about RAM problems and such, I have also read some other PDFs, providing similar informations

I have read about Checkerboard as well as Zero-One tests, I have also read about March tests and their types, the document covers only a finite list of how these tests detect errors

I haven't done any benchmarks or even started the program yet, but, I have tried to read Memtest86+ source, but, my basic knowledge in C/C++ made me unable to extract/read/understand the algorithm, but in the description they say that they write on the memory in a specific pattern, so it detects a great amount of errors

Can somebody point me out an algorithm or something so I can use it to test RAMs?

Please note that the RAMs I am testing are affected with heat (some chips might be re-soldiered)


texts: Are there any stochastic models of non determinism in the rate of program execution?

texts:
We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems.  Java & jet engines don't mix, and consequently a lot of study has gone into researching and developing real time operating systems.

Is there any research as to exactly why a traditional operating system and high level garbage collecting language can't be used?  I'm interested in any stochastic modelling that might have been done, rather than lots of words. So as a simple example, is there a mathematical model for the execution rate of say a simple FOR /NEXT loop on something like *nix + Java?  Ideally this should refer to contemporary micro processors with all their associated speculative execution, interrupt handling and other modern optimisations like memory reclamation and parallel processing.

I would also extend this reference request to any models that might try to equate the mensuration of the execution rate of such a FOR /NEXT loop, with the Observer Effect as found in quantum mechanics.


texts:
I was reading universal Hashing from Introduction to Algorithms by Cormen et al., and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables:

  Corollary 11.4

  Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(n)$ to handle any sequence of $n$ Insert, Search, and Delete operations containing $O(m)$ Insert operations.

  Proof Since the number of insertions is $O(m)$, we have $n = O(m)$ and so $\alpha = O(1)$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of  $n$ operations is $O(n)$. Since each operation takes $\Omega(1)$ time, the $\Theta(n)$ bound follows. $\quad\blacksquare$

How is the author able to say that $n = O(m)$, in the first line of the proof?
Also, what does $n=O(m)$ mean? Because $n$ is a variable and $m$ is a constant, therefore the statement seems wrong.
Also, if $n=O(m)$ is true, then obviously $n=\Omega(m)$ is true, thus yielding $n=\Theta(m)$.


texts: How are observational equivalence, contextual equivalence, and extensional equality related?

texts:
First, some context: I'm reading this blog post by Andrej Bauer.

So, I stumbled in these terms: "observational equivalence" and "contextual equivalence".

I know almost nothing about operational semantics ... I know it gives meaning for terms by it's reduction to normal form, if I'm not wrong.

Extensional equality says that two functions are equal if they always give the same result for the same input, for some definition of same result.

From what Wikipedia says about observational equivalence I can't see how is not the same thing as extensional equality .

So my question is: how these things (all three things) are related and what distinguish them?

My question maybe be simple to answer. But if not because I should know more operational semantics to be able to understand the answer, them I would be glad to be informed about some literature about this subject.


texts: Algorithm to return largest subset of non-intersecting intervals

texts:
I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.

i.e. Given a set of intervals $I =  \{I_1, I_2, \ldots, I_n\}$ of the real line, we need to output a set of intervals $O = \{O_1, O_2, \ldots, O_k\}$ such that

$O$ is a subset of $I$.
For any $i \neq j$, $O_i$ and $O_j$ are non-intersecting.
$k$ is the maximum possible.

Example: if the intervals are $[1,100], [2,3], [4,5], [6,7], [3,20]$ we should return $\{[2,3], [4,5], [6,7]\}$.


texts: Similarity-based binary representation of graph

texts:
I have given an undirected graph of which I want to associate every vertex with a (random) binary vector. I can chose the dimensionality of the vector but it has to be identical for every vertex. The main constraint is that the closer two vertices are in the graph, the lower the Hamming distance between the two associated binary vectors should be. The exact Hamming distance between two specific vertices may vary, as long as the average Hamming distance growths with the distance within the graph.

Do you have any pointers or ideas to a systematic solution to this problem? I was thinking about a breadth-first construction process, but was not sure whether this gives me the best solution for nodes which are reached over multiple paths.

I appreciate any advice!


texts: A basic question about recursive computation

texts:
I was going through the following paper: http://www-formal.stanford.edu/jmc/recursive.pdf

In the last part of the second section (at the end of page 7) he speaks about the inadequacy of lambda notion for naming functions described recursively.

The right hand side of the following expression
$$\text{sqrt} = \lambda((a,x,\epsilon),(|x^2 -a|<\epsilon \to x,T \to\text{sqrt}(a,\frac{1}{2}(x+\frac{a}{x}),\epsilon)))$$ cannot serve as an expression of function because there would be nothing to indicate that the reference to $\text{sqrt}$ within the expression stood for the expression as a whole.
I did not get what it meant. Why should there be a further indication that the expression stood for whole? Please explain this point.


texts: Given a set of numbers, get the maximum 10 number average below a certain threshold

texts:
As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the numbers used in that average are also returned).

Right now, I'm testing all 10 number combinations, recording them and their average in a list and getting the maximum average from that list.

As you know, though, when the set becomes too big (usually around 30 numbers), the time period the program takes to execute gets much larger, often way too large to be usable.

What would be an algorithm that cuts down on execution time, while achieving the same (or approximate) result?

EDIT: numbers are floats between 0 and 1.


texts: Is there an impossibility to mechanically distinguish between sets and classes?

texts:
Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either a set or else a proper class, in cases where we do not wish to distinguish.

If a set is defined by its membership function, then we can see that there exist membership functions that will not define a set but a proper class.

If we try to define the collection of set membership functions, we would need to exclude proper class membership functions.

This means that this collection needs a membership function that can determine if other membership functions are set membership functions or else proper class membership functions.

We can turn computable functions into programs that accept input and return output.

Is it valid to say that because of Turing's Halting problem, since it is impossible to design a program that will even determine if these other programs will even halt, it will be impossible for any program to distinguish between set membership functions versus class membership functions?

In that case, is it correct to say that it will never be possible to mechanically distinguish between set membership functions and proper class membership functions?

In other words, is it permissible to liberally use/abuse Turing's halting problem to decide that kind of questions? So, is this a proper use or merely an abuse of Turing's work on the halting problem?


texts:
What are some of the known properties of half-integral linear programs?
That is, linear programs for which the solution vector always takes its values in the set $\{0, \frac{1}{2}, 1\}^n$.

I'm asking this in relation to half-integral linear programs that are relaxations of integer programs (are they "faster" in terms of complexity class, to solve?).


texts:
I have the following code in Python:

def is_unique(string):
    if len(string) <= 1:
        return True

    if len(string) > 128:
        return False

    char_set = defaultdict(lambda: False)

    for char in string:
        if not char_set[char]:
            char_set[char] = True
        else:
            return False

    return True

It's basically checking if a string is unique or not. I think that my algorithm is O(1):

No matter what it's the length of the string, I will only iterate over at most 128 times in the worst case. All the operations (len, dict lookup etc) are of constant time as well.

I guess my generic question here is if you can proof that your algorithm will always iterate for a constant number of times, can you claim that this is O(1)?


texts:
I am solving some example exercises in preparation of a Computational Theory examination.

In Exercise 2, I am tasked with building an NFA and DFA of the regular expression: $(b|bba)^*a$

My question is: Can I simplify $b|bba$ inside the parentheses to $bba$? Are they indeed equivalent or will I be breaking some generality?

I am asking this since it is going to be easier for me to construct the automata after the simplification.


texts: Is this problem a variant of TSP problem? if not, what is it called?

texts:
A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are under construction and will be available soon.
We get an array C of length N, where the value of C[i] describes the petrol station at location i in the following way:

If C[i] = -1 there is no station.
If C[i] = 0 there is a station at    location i
If C[i] = x there is a station at location i which will be
available at in x days.

Assume that flying from point a to point b takes no time. But if jet runs out of petrol on a point x of array, it should wait x days to refill and then continue its way. If x=-1, jet is stuck.
The task is to find the minimal number of days the jet can get from point 0 to N+1, refilling on the way when necessary.

Is it a TSP variant with an extra condition? I am new to these.

P.S.The task is the same as "compute the maximum value of minimum values for each range of length R".

UPD. I looked at all types of dynamic programming questions, it is not close to them. I was given this problem in the university, as one in the miscellaneous set of problems.


texts: How are data types related to information theory?

texts:
I was just reading from wikipedia the following about information:

  From the stance of information theory, information is taken as a
  sequence of symbols from an alphabet, say an input alphabet χ, and an
  output alphabet ϒ. Information processing consists of an input-output
  function that maps any input sequence from χ into an output sequence
  from ϒ. The mapping may be probabilistic or determinate. It may have
  memory or be memoryless.

I'm just guessing here, but is the input alphabet the two states of a bit (0 and 1) and the output alphabet governed by the datatypes of the executing program when those bits are accessed?


texts: Are NP proofs limited to polynomial length?

texts:
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.

The proofs for an NP decision problem are verified in polynomial time.

Does this imply the proofs are at most polynomial length?

"Well you have to read the whole input. If the input is longer than polynomial, then the time is greater than polynomial."

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Therefore, perhaps some NP problem has candidate proofs that are longer than polynomial length but checked in polynomial time.


texts:
This is the homework question:

  $ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $

This is my answer:

  $$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | (bca)^* | (ba)^* | (bc)^*)^* | ((cab)^* | (cba)^* | (ca)^* | (cb)^*)^* | ((\epsilon +a) | (\epsilon + b) | (\epsilon+c)) \}
 $$

Is there a way to simplify this expression?


texts: How to compare algorithms having the same complexity

texts: I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same complexity. How do i compare such algorithms


texts: Combinatorics approach to staircase problem

texts:
There are $n$ stairs and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs every time. What is the total number of ways they can reach the top?

There are many ways to do this by using code. But when I first read this problem was to use a combinatorics approach. This problems seems very similar to a "stars and bars" problem. The stars would be the number of stairs and the bars would be the number of steps that be taken.

Given this is the case, my solution is simply: ${(n)+(2-1)}\choose{1}$.

Is the concept of stars and bars the simplest approach to solving this problem or is there a simpler combinatorics concept at play here and if so, how do I recognize such things? By simple, I mean can I solve this problem by simpler computation than combinatorics (even if it requires some sort of brute force method)?


texts: What are practical applications of AI Planning?

texts:
note: any tips toward making this more constructive will be highly appreciated.

I've dealt with ai-related problems, from searching algorithms, to computer vision, to machine learning. However none of which required planning, just algorithms following algorithms.

I'm not sure how effective will it be to implement AI Planning in practical problems, so I'm curious to know if there's a significant effect in doing so. Like at what point does the programmer/designer realize we need to apply AI Planning to solve this.


texts: What are some data mining algoritms used in finance?

texts:
I want to test the applicability of homomorphic encryption in the financial domain, as suggested in Can homomorphic encryption be practical ?.

Now, I want to know what algorithms are used for financial cloud solutions, and if these methods can be improved by adding confidentiality of data. Namely, somebody wants both the cloud power for computation/storage and at the same time wants to feel his/her data are protected.

What are these algorithms used for financial cloud services and data mining that I should study ?


texts: Why does many to one reduction imply Turing reducibility?

texts:
So, $ A\leqslant_mB $ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $ f(A) \subseteq B$ and $ f(\overline{A}) \subseteq \overline{B} $.

$ A\leqslant_TB $ (Turing reducibility) means that language $A$ can be Turing-reduced to language $B$ if there exists an oracle machine $O^B$ which decides $A$.

I sort of get them both individually, but I don't get why $ \leqslant_m $ implies $ \leqslant_T $.


texts: Minimum number of transactions to redistribute unequal shares

texts:
I thought of a problem which must certainly be known:
n persons get an uneven share of m oranges, m being a multiple of n. All the persons having more than m/n oranges are to give their excess share to the less fortunate. What is the minimum number of transactions needed to reach a perfectly even distribution, each transaction being represented by a tuple i, j, k where i represents a source person, j represents a destination person, and k the number of oranges being transferred.

I think this problem can be represented as a DAG with the shortest path representing the solution. However, I am trying to find out if this is a classic problem.


texts:
I try to get a better understanding about Failure Detectors in the field of Distributed Computing.

Let consider the algorithm for reaching consensus with Perfect Failure Detector, it's named as Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch on the page 679. In addition, it can be found in the following presentation Asynchronous Network Computing with Process Failures. Slide 16.

The basic idea of the algorithm is each process $P_i$ attempts to stabilize two pieces of data: a vector val, indexed by $\{1,2,...,n\}$, with values in $V \cup \{null\}$.$val(j) = v \in V$, it means that $P_i$ knows that $P_j$’s initial value is $v$. A set stopped of process indices. If $j \in stopped$, it means that $P_i$ knows that $P_j$ has stopped.

The question is as one of the step of the algorithm every process that receive a message ignores it from the processors it has already placed in stopped.

I don't understand why we need this, even we don't ignore the message from stopped process it won't broke anything. This case may occur when  $P_j$ sends a message to $P_i$ and crashes, FailureDetector see the crash and informs the process $P_i$ that $P_j$ is stopped after that $P_j$'s message reaches $P_i$, but this message contains a correct data, and it doesn't change the state of $P_j$ in stopped set, because only INSERT (insert new values that previously was null) and COMPARE are allowed operations on the set.

If you see the real reason for ignoring messages from the crashed process please share it with us.

Addendum: Unfortunately I didn't find any use of the aforementioned fact (ignoring message from crashed node) in the algorithm (Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch).

In addition, in main papers Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors forasynchronous systems and Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest
failure detector for solving consensus slightly different algorithm can be found without ignoring messages from crashed nodes.


texts: Rows and columns in quantum-gate matrices read the same - why?

texts:
I have noticed that for all the matrices representing quantum gates, if we read rows left-to-right and top to bottom, the read the same as columns top to bottom left to right.

Example:

\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1&  0
\end{pmatrix}
(CNOT gate), if we read the values in from the first row, we see 1 0 0 0. Similarly if we read left-most column top to bottom. Second row reads 0 1 0 0, just like 2nd left column etc.

I believe this is a property of all matrices representing quantum gates, but cannot explain why exactly this is the case (and if it is, in fact, guaranteed for every quantum gate?)


texts: Does mutual exclusion hold in this case?

texts:
I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds:
Consider two processes:

$s_1$ and $s_2$ are two variables, set equal initially.
P1:

while $s_1 = s_2$: wait.

/execute critical section/

$s_1$ is set such that it is not equal to $s_2$

P2:

while $s_1 = s_2$: wait.

/execute critical section/

$s_1$ is set such that it is not equal to $s_2$

My friend argues that mutual exclusion holds. His explanation:

Mutual Exclusion holds if the following implication holds:
If a process is in its critical section, then other processes should not be allowed in their critical sections.

Consider this implication as $P \to Q$. He argues that since the premise $P$ is wrong (because none of P1 and P2 are in their critical sections), the implication is true and hence mutual exclusion holds.
Whereas my thinking is that when none of the processes get to enter their critical section, talking about mutual exclusion is pointless and hence the property doesn't hold.
Is the implication way of thinking the correct approach? I feel that it's not, but I have not been able to prove my intuition.


texts: Turing Machines: decidability and bounds checking

texts:
I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w.

I'm assuming I construct a TM which shifts the input on the tape on cell to the left, write the cell at the right-hand end with a new symbol (like "!") that's not in the alphabet for input w.
Then add a transition for the head to move left on e cell on reading the extra symbol?

Thoughts?


texts: Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case

texts:
This is a question from Introduction to Algorithms by CLRS (Exercise 9-1-1).

The approach I thought of is

compare the first two numbers, assign the lower number min and the bigger one to next_min
loop through numbers 3 - n,
if the number is lower than min, set min to that number.
else if the number if lower than next_min set next_min to that number

If this is the optimal solution how can I prove the number of comparisons is n + lg n - 2.


texts: The meaning of modulo in “formula modulo a background theory”

texts: I have been reading some papers where I keep reading stuff like “first-order formula modulo a background theory”. Does anyone know what modulo means in this case ? Is it something like “with respect to”?


texts: What is the 2's complement answer of 16.5?

texts: According to this post it is saying Two's complement is only for integers, but in Wolframalpha is is saying the Two's complement of 16.5 is 0010000.1, how?


texts: Multiple sequence Progressive alignment example using five sequences

texts:
I tried to find sources that explain multiple sequence alignment with an example using progressive alignment, but I couldn't find one.

I actually know till creating a guide tree, after creating a guide tree we use guide tree to arrange sequences. This is the critical part. Can some please help me in explaining how to align sequences that are already aligned with a new sequence.

For Example there are 5 sequences S1, S2, S3,S4 and S5. After aligning S1 and S3, suppose the aligned sequence is A1. Now the problem is I don't know how to align A1 with S2 or S4 or S5.

Please help me by explaining that with an example. Your help is much appreciated.

Thanks, Ravi


texts: Please explain linear programming as seen for this load balancing problem

texts:
I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful.

I wonder if someone can explain the basic lingo used in the formulation of the linear program. The goal of the program is of course to introduce the maximum amount of load capable on the lightest loaded machine.

Let

$p_i$ be load of processor $i$
$L$ be our load to be distributed
$x_i$ be the fraction of load $L$ distributed to processor $i$
$\gamma$ be the minimum of final load after distribution of $L$

Then solve:

$$max_{x,\gamma} \gamma$$

subject to $\gamma \underline 1 \leq p + xL$, $\underline 1'x = 1, x \geq 0$, $\underline 1$ is the one vector

Some confusions:

How do you physically characterize the load of a processor, is it
equivalent to CPU utilization? i.e. what can I do to find out what
the load of my processor is currently having
How is the fraction of load $L$ to be distributed determined?
If $\gamma$ is the minimum final load after L, then why do we
maximize it? wouldn't that be equivalent to maximize the left over
work to be done?


texts:
Consider the problem
$\frac{n}{3}$-CLIQUE:
determining whether a graph contains a clique with at least $n/3$ vertices.

I want to prove it is NP-complete using a polynomial transformation from CLIQUE.

How can I approach this problem?


texts: Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

texts:
The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(

Problem:

We implement a merge sort algorithm to sort $n$ items. The algorithm will divide the set into 2 roughly equal-size halves, and merge the 2 halves after each half set is recursively sorted. Because the item comparison is complicated, the merge process takes $\theta(m\sqrt{m})$ steps for input size $m$. What is the time complexity for this algorithm?

(a) $\theta{(n\log{n})}$
(b) $\theta{(n)}$
(c) $\theta{(n^2)}$
(d) $\theta{(n\sqrt{n})}$
(e) $\theta{(n\sqrt{n}\log{n})}$

What I tried:

I know the merge sort normally can be written $S(n) = 2S(\frac{n}{2}) + n, S(1) = 1$, where the recursive function $S$ is the step cost of the merge sort for the size $n$.
But the problem specifies the step costs to merge is $\theta(n\sqrt{n})$, I have to rewrite it as $S(n) = 2S(\frac{n}{2}) + \theta(n\sqrt{n}) = 2S(\frac{n}{2}) + n\sqrt{n}$.
I have no idea how to transform it into the general solution...

Please help me, I will learn a lot from this problem! Thanks :)


texts: What's this type of semantic analysis called in NLP?

texts:
I'm speculating that this is very much known in NLP, but as I've not studied NLP, I don't know what concepts are related to this:

Basically I have entities that are connected by some strings. I want to do semantic analysis using this kind of constructs. I.e. by checking whether a given sentence has entities (the yellow ellipses) connected with the right strings.

Notice that this is also basically describable as a a deterministic context-free language. But I'd like to understand the semantical aspect of this, rather than mere parsing (string matching).


texts: Does NFA to DFA conversion give the minimal DFA as result?

texts: When converting NFA to DFA, do I always get the minimal DFA or not?


texts: Create cfg and npda/pda for Language {ww}

texts:
I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language):

L(M)={ww:w∈{a,b}∗,|w| is even}.

i had already solved the reverse of the language (like this):

L′={wwR:w∈{a,b}∗},

Please check this snapshot to know what i am asking to do ! (L') : http://i921.photobucket.com/albums/ad53/Johann_1990/IMG_20150117_132616.jpg

but is there is a way to solve this L(M)={ww:w∈{a,b}∗,|w| is even}?

For example, abaaba∈L with w=aba.

Note that I'm not asking to prove by conduction or anything else.


texts: Is type inference done by an interpreter static or dynamic?

texts:
Type inference can be done by a compiler, and in such cases, type inference is static.

Type inference can also be done by an interpreter. An interpreter does the jobs of both compilation and execution. So is type inference done by an interpreter static or dynamic?

This question is an example that motivated my question Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language? at a more general level.


texts: How to find optimal token set for compression?

texts:
By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like in LZ).

(Please feel free to correct me on this term, if I use it incorrectly.)

I'm thinking: what if we first find optimal set of tokens, and only then compress our data as a stream of these tokens? Will it improve compression of text or of xml or of some other kind of data? LZ sort of does this, but it is limited to letters. I'm asking about truly general approach when a token can have any bit-length. For example, it can be interesting to do it for compression of x86 executable files. Or in other cases, when sub-byte (and sup-byte) bit-strings behave as individual tokens.

How to find this set of tokens optimally? In a way that maximize average entropy of a stream of such tokens under 0-order Markov model?

Are there existing algorithms for it? Are there any algorithms related to the problem?

How to find approximation of this set? What is complexity of optimal and approximation solution?

And what if we want to maximize entropy for higher order Markov model? How harder the problem will be in this case?


texts:
I got this question on my final exam: Is the following language context-free?

$$ L = \{w\bar w^R \mid  w\in \{0,1\}^*   \}$$

Notation:
The string $\bar w$  is obtained from $w$ by replacing all 0s with 1's and all 1's with 0's.  The string $\bar w^R$ is $\bar w$ in reverse order.

  I've thought about it being a context-free language, but I notice that
  when you pump the string in the middle, the string will still be in the
  language. (using pumping lemma)

I think it's context free.
This is the context free grammar:

$$
S \to 0S1 \mid  1S0 \mid \varepsilon $$
(It's basically a palindrome, but both sides are exact opposites.)


texts:
I have a small question regarding the ECLOSURE of a certain state in an ε-NFA.

If we have a transition that has both a and ε transitions, is the ECLOSURE affected?

Also is there any rule that in ECLOSURE we should include the states that are accessible only from transitions containing ε?


texts: Restrictions to counter machines capturing LBA

texts:
As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows:

Values: natural numbers only, but of unlimited precision.

• Variables:

– Input variables X1, X2, X3, . . .

– An output variable Y

-Local variables Z1, Z2, Z3, . . .

• Instructions:

1 ) $V ← V + 1$ Increase by 1 the value of the variable V .

2 ) $V ← V − 1$ If the value of V is 0, leave it unchanged; otherwise decrease by 1 the value of V.

3 ) $ IF \;V \neq 0\; GOTO \;L$ , If the value of V is nonzero, perform the instruction with label L next; otherwise proceed to the next instruction in the list.

• Labels: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, . . .

• Exit label: E.

• All variables and labels are in the global scope .

for example the following program computes f(x) such that if x = 0 , f(x) = 1 otherwise f(x) = x
\begin{align}
[A] \quad &X ← X − 1 \\
    &Y ← Y + 1 \\
    &IF\; X \neq 0\; GOTO \;A \\
\end{align}
this language can use infinite number of variables.

  What restrictions should be added to this language so its power will be the same as Linear Bounded Automata? One of them is clear about the variables but I will appreciate if anybody helps me about any others, if they exist. I have searched a lot but I couldn't find any source that describes both topics. I would appreciate any relevant pointers.


texts: Is there a way to map a multi-variable structure onto a single range?

texts:
I want to categorise variants of a structure made up of some number of variable components by mapping it to a unique range. Assume that the individual components all fall within the same base range.
I'm using color as an example for this question as its intuitive to think about but I don't want the question to be specific to that, its just a framework for understanding the problem.
Simple case:
Imagine I have a structure, called C made up of two values (r, b) (red and blue) and I want to categorise variants of C into distinct bands, things like "very red", "quite blue", "slightly blue", "quite red" etc.
In this case I could just map the values by starting at 0 and then adding anything in the r channel and subtracting anything in the b channel, then I would get a final value in a 1 dimensional range somewhere between -1 and 1 (assuming the values for r and b are clamped. Then I could use this output value to categorise it into a band: maybe anything below -0.8 is "very blue" and a value between 0.4 and 0.5 is "somewhat red".
Examples:
(0.1, 0.3) -> -0.2
(1.0, 0.0) -> 1.0
(0.2, 0.9) -> -0.7
Not so simple:
However, if I introduce a third value, so C is made up of (r, b, g), I can't see how I can easily map this to a range which I can make assertions about, like "bluey green" or "reddish blue". Trying to create a solution in code for this (naively) just ends with a complicated set of conditional statements.
One solution I thought might work would be to convert the 3D version of C into a point on a triangle expressed as a weighting of its vertices (where each vertex corresponds to one of C's components), and then convert that point in 2D coordinate space into a categorisation based on where it falls in a sub-shape - which is just a delimited area - on the triangle. So I could say, if the point falls inside this sub-shape on the triangle its "bluey green", if the point falls inside this other sub-shape, then its "reddish blue" etc. However, this does seems like a fairly intricate solution and I'm not sure if I am heading down the wrong path.
Also, I can't see how this would then generalise to putting more and more variables into C.
I don't a have strong intuition for what field of mathematics or computer science I should be looking into to solve a problem like this or how exactly mapping like this work.
If anyone knows how to solve this or what sort of things I should be looking at to solve it, I would really appreciate some advice! Thanks.


texts: Warm starting LP solver at non-basic feasible solution

texts:
I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming solvers, like GLPK.

After having solved a discrete approximation at resolution $h_0$, I can produce a reasonably good feasible solution $x_h$ for any discrete approximation of the problem at a higher resolution $h$. BUT, that reasonably good feasible solution $x_h$ is in general not a corner(i.e. basic) solution.

Given that solvers like GLPK can do a warm start only at a basic solution, how can I come up with a basic feasible solution near $x_h$ to warm start the solver with? Are there any open source, or at least free, solvers that can be warm started with feasible non-basic solutions?


texts: Real-world scenario for a theoretical problem on trees

texts:
Suppose one has a tree with each node weighted with a tuple (say, some fixed $2$ dimensions, for now) of integers. Now we query the tree with two vertices $x$ and $y$ and a range $[a,b]\times [c,d]$, and the query should return the number of nodes in the (unique) path from $x$ to $y$ such that their tuples fall within this rectangle $[a,b]\times [c,d]$. What would be a possible real-world scenario that would result in such a model?

For the 1d-case, one could use, say, Homory-Hu tree of minimum cuts to motivate such a problem. I am not sure how to motivate this theoretical question with a real-life problem, that is the question.

Suppose the path $x\sim y$ has vertices $u_1,u_2,\ldots,u_m$ with attached tuples (respectively) $(-1,2),(3,4),\ldots,(13,-17).$ Then if we query with $x,y$ and a rectangle $[-2,2]\times[2,3]$, then the first node, $u_1$ (among possibly others) would be counted,
since its tuple $(-1,2) \in [-2,2]\times [2,3].$


texts: How to prove a greedy algorithm that uses the longest increasing subsequence?

texts:
Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy algorithms.

The problem says: I need to sort an array of $n$ numbers, but the only operation I am able to do is to move an element from position $i$ to $j$, and if $i<j$ then every elements in the interval $[i+1, j]$ (inclusive) are moved one position backwards. On the other hand if $i>j$ then every element in the interval $[j, i-1]$ increase their position by one. That operation has a cost of $i+j$ for doing it. So I need to sort the array using the lowest cost possible using a series of only that kind of operations.

Assume that I need to sort the array in decreasing order.

After a lot of thinking, I came up with the idea of finding the (first) longest increasing subsequence from right to left. If I have that sequence, we are to assume that those elements in that sequence are already sorted. So, I wouldn't need to use them (i.e selecting them (from $i$) to move them (to $j$)), cause they are already sorted. That way, the cost of moving them would never be calculated into the final cost of making every operations. And also I will be doing fewer operations and then guaranteeing that the ones I am doing has the lowest cost.

The cost will be easily calculated because the subsequence was created using a sort of Tuple element, with the value and the actual position in the array, so I'll use the value of the position to calculate cost.

After having that subsequence in hand, I am to insert the remaining elements in that sequence (the first longest increasing subsequence from right to left). After that I insert the remaining elements in a Queue to easily Dequeue them in the order of their position (from lowest to highest). That way, we guarantee that the cost of moving them will be minimum. After inserting we update the position of the elements in the sequence (in the Tuple) in the Queue and in the sequence (say I am using a List of Tuple for the sequence).

That algorithm is working, and have thrown a correct answer for several cases I tested against a brute force algorithm version.

Now I need to proove it works, but I have no clue how. It can easily be seen I am using a greedy aproach to insert the elements, but I how does it guarantee what I am looking for!

Hope anyone can point me into the right direction of that proof!
Thanks in advance

EDIT: I have done some progress here, and I am in a point where I have proven that the optimum must have selected a decreasing subsequence to avoid those items of being moved, but I need to prove that this is the maximum decreasing subsequence. In order to do that I am trying to prove that the cost of moving $X$ elements is less than the cost of moving $Y$ elements with $X<Y$. I haven't been able to prove it, but I can't come up with an example that prove me wrong.

Do you think this happens? How could I prove it?

Thanks

EDIT: This is the problem itself SPOJ Problem RSORTING - RANKLIST SORTING
I have a solution but I need to prove its correctness


texts: Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

texts:
In the CLRS, time complexity of Prim's algorithm is $O(|V|lg|V|+|E|lg|V|)=O(|E|lg|V|)$.

But, for my understanding, Prim's algorithm iterates $|E|$ times for DECREASE-KEY operation which takes $O(lg|V|)$ times and it leads to $O(|E|lg|V|)$.

So, it iterates $|V|$ times then, I think $O(|E||V|lg|V|)$ is right because whole time complexity is like below.

Initialization of key and predecessor + making a binary heap = $O(|V|)$
EXTRACT-MIN operation = $O(|V|lg|V|)$
DECREASE-KEY operation is iterated for $|V|$ times = $O(|E||V|lg|V|)$

Consequently, $O(|V|+|V|lg|V|+|E||V|lg|V|)=O(|E||V|lg|V|)$.
Why is it $O(|E|lg|V|)$?

From 2 answers, first while loop iterates $|V|$ times and $DECREASE-KEY$ operation iterates $|E|$ times and time complexity of that operation is $O(lg|V|)$ because min heap has to be reconstructed.

From this, I got a $O(|V||E|lg|V|)$ because for loop is in while loop. What your answers are saying is that I don't know $DECREASE-KEY$ operation iterates $|E|$ times, but I know that.


texts: What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?

texts:
Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the evaluator must ensure that the beta-reduction step uses capture-avoiding substitution, i.e., that the variables it substitutes into a term are not free variables of that term.
Combinatory logic can be seen as a subset of lambda calculus that only allows closed terms. Despite this, it is still Turing-complete, and can thus be used to compute everything that lambda calculus can. As such, what are the benefits of allowing free variables and open terms, and the disadvantages of disallowing them? On a related note, why does lambda calculus seem to be a more popular topic of study than combinatory logic despite the apparent shortcoming mentioned? Is the former somehow more relevant and useful to a larger variety of topics than the latter?


texts: Deciding whether set of running times is infinite

texts:
I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$.

\begin{align}
\mathrm{Count}(M)= \{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly $k$ steps}\}.
\end{align}

I need to check whether the language $L$ is in RE, and whether it is in R.
$$L= \{ \langle M \rangle \mid \text{$\mathrm{Count}(M)$ is an infinite set}\}.$$

My idea for a solution starts with:
even though $L$ is an infinite language, it contains $\mathrm{Count}(M_i)$ that halts eventually. Each $M$ in $L$ must halt, and $\mathrm{Count}(M)$ is infinite.

So, in order to prove that $L$ is in RE, can I simply say every $M$ in $L$ halts eventually?