texts: Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$

texts:
I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\{x\in(a,b), \#_a(x) = 2\#_b(x)\}$, where $x$ is the input string and $\#_a(x),\#_b(x)$ the number that $a$ or $b$ appears in the $x$ string.

That means that the following sequences should all be accepted:

  aab
  aba
  bbaabaaaa
  baabaa
  abbaaa

My problem: I've found examples of PDAs being constructed for $a^nb^n$ and even $a^{2n}b^n$ which is pretty close to what I'm looking for, but these languages all have a predetermined sequence of the $a$s coming first, then the $b$s.

I've been trying for literally hours to build a PDA that circles between how many $a$s and $b$s it has, and how many it still needs, but every attempted solution has been wrong (situations where consequent same letters cause pops on empty stacks, halting the PDA).

Any information or methodical approaches on constructing a PDA out of a language like that? I'm at my wit's end.


texts: Difference between probabilistic and randomized algorithm

texts:
What I understated is this:

Probabilistic algorithm: an algorithm that produces result in determined time with a confidence value about the probability of the produced result being correct.

Randomized algorithm: an algorithm that uses some sort of randomization to reach the result, that too with absolute surety of reaching the correct result.

Is this correct? And what exactly is the difference between these two?


texts: How many possible ways to go right and up in an array

texts:
Let's say we have a 2D matrix, and we begin at $(0, 0)$.

We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$.

For example if $n = 5$ and $m = 4$, the following would all be valid:

UP UP UP UP RIGHT RIGHT RIGHT RIGHT UP

RIGHT UP RIGHT UP RIGHT UP RIGHT UP RIGHT UP UP

UP UP RIGHT RIGHT UP RIGHT UP UP RIGHT

How many possible different ways are there to travel up $n$ times and right $m$ times, if the ordering in which we travel right or up does not matter, as long as we start at $(0, 0)$ and finish at $(n, m)$


texts: Finding a language that is $NP^L$-complete

texts:
I'm trying to prove a theorem and as a lemma I would like to identify an $NP^L$-complete language. I was thinking something like a machine that can decide $SAT$ equipped with an oracle for $L$ can decide every language in $NP^L$, but I'm not sure how to formalize this. Here's my attempt at doing so

$$ SAT^L = \{\text{satisfiable boolean formulas with some clauses as }L(x_1, \dots, x_k)\}$$

The clauses that are of the form $L(x_1, \dots, x_k)$ are queries that are true if and only if $(x_1 \cdots x_k) \in L$.

I think $SAT^L$ is $NP^L$-complete, for any language $L$, but I don't know how to prove this. It's of course in $NP^L$ since we can take a witness
assignment and check it, and we can check the $L(\cdot)$ predicates with a query to our oracle to $L$. I'm not sure how to prove $NP$-hardness though.

I was thinking of just modifying Cook-Levin's construction so that I could add additional clauses to the formula of the form $L(x_1, \dots, x_k)$ when encoding the computation graph of an NTM $M^L$  but I'm not sure if this works in general, and is honestly more of a rough idea than anything else. This construction seems to be pretty sensitive to the "implementation" of the oracle queries, so I'm not sure how to make this rigorous.

Is there a more standard example of a $NP^L$-complete language?


texts: Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$

texts: Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a constant, it's really difficult to apply tree method and master theorem here. Any hint? My thought is that let $c = \sqrt{n}$ such that $c^2 = n$ so we have $T(c^2) \leq cT(c) + c^2$ but I does not look good.


texts: proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular

texts:
I am trying to prove this following theorem, can someone help please?

Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$.
If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is regular.


texts: When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

texts:
According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation."  However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (on page 610) as a language that is "translatable from left to right with bound $k$."

I am guessing that this new terminology was chosen to complement $LL(k)$ parsing's "left-to-right scan, leftmost derivation."  That said, I don't know when the terminology changed meaning.

Does anyone know where the newer acronym for $LR(k)$ comes from?


texts: Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?

texts:
From the analysis of Dijkstra there is a $O(mlogn)$ factor that assumes we do a decreasekey for every single edge of the given input graph.

However I find it hard to come up with an instance that can actually require this. All you have to do create the edges and then add the weights in a way that would induce a large number of decrease keys.

Is there any known way of doing that?


texts: Why does a graph traversal algorithm is initialised with visited[s]←true

texts:
I just had a course on algorithm, we just started to study graph traversal. the teacher wrote analgorithm but I think there is a mistake:
I'm a bit shy so I didn't asked her why so...

EXPLORE (s:sommet, D:dictionnary of the following vertexes or ahed of vertexes,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LISTE←LISTE-{i}

I'm not sure about this line:

visited[s]←_true_;

What does that mean? shouldn't it be false? At the begining, we haven't visited any vertexes yet?


texts: Semantics of Regex with boundary matchers

texts:
The regex /^(abc)$/ matches abc but why not abcdabc, abcdabc also begins with abc and ends with abc.

I am not sure about the semantics of this regex. Any explanation is welcome.


texts:
In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. For mean, I simply do the averaging by:
$\mu = \frac{\mu_1+\mu_2+.....+\mu_n}{n}$
However, for the variance, I can't figure out to average n variances. For only two I found this answer here
$\sigma^2 = \frac{1}{2}(\sigma^2_1 + \sigma^2_2) + (\frac{\mu_1-\mu_2}{2})^2$
But how about n variances?
thank you


texts: Turing machine different accepting states

texts: I want to design a Turing machine that accepts at most 3 0s. Now, I have designed one, which goes to accept state overtime it sees 1, 2 and 3 0s and rejects any further 0s. I wanted to know if it is okay for TM to go to accepting state from 3 different states?


texts: Pumping lemma problem - Choosing the right string to pump

texts:
I have a problem finding the right string to pump for the following language:

$$L_1 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$

Which string should I choose to pump? The problem is that I don't know how to handle the fact that I have $p+q$ and $q+r$?

Can I choose:
$$Z = a^{2n}b^nc^nd^{2n}e^s$$

Thanks in advance.


texts: for two languages in $NP$ does one of them karp reducible to another?

texts:
$\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$

I want to know is there any work around this theorem? or is it correct?


texts: Why does the experience propagation rule for checkers work in Tom Mitchell's book?

texts:
In Tom Mitchell's book "Machine Learning", Chap.1, a checkers game is used to illustrate how machine learning can be applied solve problems.

An experience propagation rule is described for iterative learning of a hypothesis. Suppose a game has been played and watched by the program, the state of the endgame is labeled 100 for winning and -100 for losing. For each of the states on the path toward the endgame, we label it as $\hat{V}(Successor)$, where $\hat{V}(state)$ is the current model output on some state. Then the model is trained by adding the new label, and iteratively, the model converges to a good checkers program.

Why does this experience propagation rule work? It is mentioned in the book that it works quite well for most chess games.


texts: What the the most efficient and effective VM ISA/computational model format backed by research?

texts:
The JVM and CLR are stack based machine are very efficient, mainly due to the investment in these platforms than an efficiency and effectiveness of stack based VMs.
For en entity that does not have that level of capital to invest in a VM, what should be the most efficient and effective set up for a VM in terms of:

easy to implement the VM
easy to implement JIT
easy to optimise JITing code
lower interpreter mode overhead
lower JITing over head
etc.

found in research.


texts: How to efficiently determine whether a given ladder is valid?

texts:
At my local squash club, there is a ladder which works as follows.

At the beginning of the season we construct a table with the name of each
member of the club on a separate line.
We then write the number
of games won and the number of games played next to each name (in the form: player wins/games).

Thus at the beginning of the season the table looks like this:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Any two players may play a match, with one player winning. If the player nearest the bottom of the table wins, then the position of the players is switched. We then repeat step 2., updating the number of wins and games next to each player. For example, if Alice beats Billy, we have

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

These matches go on throughout the season and eventually result in players being listed in approximate strength order.

Unfortunately, the updating happens in a rather haphazard way, so mistakes are made. Below are some examples of invalid tables, that is, tables which could not be produced by correctly following the above steps for some starting order (we have forgotten the order we used at the beginning of the season) and sequence of matches and results:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Given a table, how can we efficiently determine whether it is valid? We could start by noting the following:

The order of the names doesn't matter, since we have forgotten the original starting order.
The total number of wins should be half the sum of the number of games played. (This shows that the first example above is invalid.)
Suppose the table is valid. Then there is a multigraph - a graph admitting multiple edges but no loops - with each vertex corresponding to a player and each edge to a match played. Then the total number of games played by each player corresponds to the degree of the player's vertex in the multigraph. So if there's no multigraph with the appropriate vertex degrees, then the table must be invalid. For example, there is no multigraph with one vertex of degree one and one of degree three, so the second example is invalid. [We can efficiently check for the existence of such a multigraph.]

So we have two checks we can apply to start off with, but this still allows invalid tables, such as the third example. To see that this table is invalid, we can work backwards, exhausting all possible ways the table could have arisen.

I was wondering whether anyone can think of a polynomial time (in the number of players and the number of games) algorithm solving this decision problem?


texts: Calculating the Transfer Time for a Hard Disk

texts:
I know that transfer rate is data size over transfer speed - but according to the information given, I don't know what the data size is to calculate the transfer rate.  Am I missing something or was I really not given it?

The information given is as follows:

  A number of files are stored on a 10000RPM hard disk. The platters
  rotate clockwise. The heads move at the speed of 250 centimeters per
  second. The controller overhead of the hard disk is 0.2 milliseconds
  per I/O request. The data transfer speed is 100 MB/s.  Assume one I/O
  request is sent for every file. The average seeking distance is 1
  centimeter. Since a sector is very small, ignore the time to rotate it
  through under the head. Calculate the average time to fetch data for
  each of the scenarios below.

  a. 1 file of 10 sectors is fetched. The sectors are randomly distributed on the disk.

I know I need the transfer rate to calculate fetch time - but again - I don't know the data size so I don't know how to calculate it.


texts: Algorithm to explore every node in a graph

texts:
I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.

The following algorithm (in psuedocode) appears to gather every node but results in duplicate nodes (I think because the recursive 'paths' crossover at some points):

rFindAll(Node ID, Array currentpath) //current path passed by value
{
  Array connectedNodes = getConnectedNodes(ID);

  for_each_node (Node n : connectedNodes)
  {
     if(find(currentpath, n) == NOT_FOUND) // check to ensure id not in current recursive path
     {
        // every n is a node which is within the same graph as the original node
        currentpath.add(n);
        rFindAll(n, currentpath);
     }
  }

}

I was just wondering whether anyone has a better suggestion to do this. I've looked on google/wikipedia and there was nothing which would obviously help.

Thanks


texts:
I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) connexity rules.

There are well-known solutions to this problem, such as recursion on the immediate neighbors, or the scanline approach. The former takes 4/8 tests of the neighbor color per pixel, and the latter takes a little less as when a straight run of pixels is processed, one backward test is saved per pixel. I have heard of an article possibly published in 2006, which is based on outline following, but have no reference for it.

(Whether the actual implementation uses the recursion stack or an allocated array is not relevant for this question. Nor is the "fixed-memory" requirement for which solutions have been proposed.)

My intuition tells me that better could be achieved by avoiding the repetition of some neighbor tests. In an extreme case, you can fill a square starting from the middle and spiraling until you reach the boundary with just one test per pixel, as you know that all pixels inside the spiral have been filled.

So my question: do you know of any theoretical study on the required number of neighbor tests per pixel for flood filling ? (The question can be rephrased in terms of graph theory as a connected component labeling problem.)


texts: What textbooks includes explanations of advanced data structures found commonly in competitive programming?

texts:
While looking through some problems on CodeForces, I noticed that there were several problems that required knowledge of techniques that just aren't covered in standard algorithm texts.

Topics that I want to understand include

segment trees, least common ancestor, range-minimum query
Fenwick trees
heavy-light decomposition
interval trees
Hopcroft–Karp algorithm
implementations of tries
wavelet trees

There doesn't seem to be any book that comprehensively looks at any of those techniques. The only organized resource that I could find was a list of articles on GeeksForGeeks, but much of the site doesn't seem self-contained and linearly ordered the way a textbook would be. It's fine if not all of the techniques I've listed are covered, but I'd prefer a book that covered as much of it as possible. Any help?


texts:
I'm new to Computation Theory and trying to figure out the undecidability problems. Last night, I came up with the language of TM with a useless state:

  $\text{USELESS_TM} = \{ \langle M, q \rangle\mid q\text{ is a useless state in TM }M\}$

where q is a state that M never enters on any input w. The problem is simply defined as: "determining whether a Turing machine has any useless states".

The question wanted me to show that this language is undecidable using a reduction argument. I thought it would be logical to reduce EMPTY_TM to USELESS_TM, and using contradiction show that if USELESS_TM is decidable, then EMPTY_TM will be decidable (which we know it's not).

I wanted to step a little bit forward in grasping the concepts of USELESS_TM. Is it possible to modify this Turing Machine to another TM M without useless states in such a way that L(USELESS) = L(M)? I thought about just removing the useless states, as the machine never gets into those states, so the language won't change. But, is there another way by like modifying a TM's definition to ensure that it has no useless states?

UPDATE . I borrowed the first example from  Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Problems 5.13 --Textbook


texts: For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$

texts:
I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$
The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$
I understood that $S=\emptyset$ and $S=RE$ are trivial and
$S=\emptyset \Rightarrow L_\emptyset=\emptyset\in R$
$S=RE \Rightarrow L_{RE}=\Sigma^*\in R$
But can't understand what's going with $S=\emptyset$ and $S=\{\emptyset\}$


texts: Proof of the inclusion-exclusion principle

texts:
The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:

  THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION   Let $A_1,A_2,\ldots,A_n$ be finite sets. Then
  $$
\begin{multline*}
|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|.
\end{multline*}
$$
  Proof: We will prove the formula by showing that an element in the union is counted exactly once by the right-hand side of the equation. Suppose that $a$ is a member of exactly $r$ of the sets $A_1,A_2,\ldots,A_n$, where $1 \leq r \leq n$. This element is counted $\binom{r}{1}$ times by $\sum |A_i|$. It is counted $\binom{r}{2}$ times by $\sum |A_i \cap A_j|$. In general, it is counted $\binom{r}{m}$ times by the summation involving $m$ of the sets $A_i$. Thus, this element is counted exactly
  $$
\binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}
$$
  times by the expression on the right-hand side of this equation. Our goal is to evaluate this quantity. The binomial formula shows that
  $$
0 = (1-1)^r = \binom{r}{0} - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^r \binom{r}{r}.
$$
  Hence
  $$
1 = \binom{r}{0} = \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}.
$$
  Therefore, each element in the union is counted exactly once by the expression on the right-hand side of the equation. This proves the principle of inclusion-exclusion.

Although the proof seems very exciting, I am confused because what the author has proved is $1=1$ from the LHS and RHS.

Thus, is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $1$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra
summation sign should be appended before the expression in RHS. Could
someone please clarify?


texts:
I'm currently taking a numerical analysis class in college and we're covering floating point systems. For the most part, I have a good grasp on it. However, something I can't seem to visualize, and haven't seen any totally lucid explanations about after searching extensively, is spacing between floating point numbers. Also of note is that I'm talking about IEEE-754 here, but it applies to general systems too.
The Things I Do Understand:

The area between $[-1,1]$ is a denormalized area.
The areas after $1$ and less than $-1$ are where the normalized floating point numbers reside.
The floating point numbers between perfect powers of the base are uniformly spaced, but the spacing varies from one perfect power of the base to another.
The spacing between values between two perfect powers is proportional to the power on the left for positive numbers and the power on the right for negative numbers. (i.e. on a number line, the uniformly-spaced values between two low powers are closer together than between a higher power.)

What I'm Struggling to Understand

From my understanding, the machine epsilon $\epsilon$ is a fundamental unit of spacing with respect to the floating point number line. That is, between $[1,B]$ where $B$ is the base, all values are $\epsilon$ apart. Then, you can scale any arbitrary floating point number by that fundamental machine epsilon and that product is the uniform spacing for that floating point number's associated power range. Is this even a correct interpretation?
I also read that $\epsilon$ is an upper bound for relative error, so I'm not really sure how that fits into my explanation of it being an indivisible spacing unit.

One of the questions I haven't been able to answer is what the minimum and maximum spacing between two positive floating point numbers is. I can trick myself into thinking I understand why multiplying the x's associated $B^e \cdot \epsilon$, where x is an arbitrary floating point number and $e$ is that number's corresponding exponent, yields the upper bound on error and therefore spacing, so $B^e \cdot \epsilon$ would be the maximum spacing.
Minimum spacing truly boggles my mind right now, though. If the machine epsilon is the indivisible unit of spacing, then for example, how could we have more minimal spacing than between $1$ and $1 + \epsilon$? Wouldn't that just be left to the rounding rule used (if round-to-nearest, it would depend whether the number is closer to $1$ or $1 + \epsilon$, since it'll be rounded to one of those two).

Basically, if you could explain this in plain-english it would really help me get a solid understanding of what's going on at the number line level.


texts: Is this in-place merge algorithm efficient or not?

texts:
I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head elements of the second list, swaps them, and recurses on the four sublists. Code for the algorithm:

// Assuming that the subranges [start, mid) and [mid, end)
// are each sorted, this yields [start, end) being sorted.
void merge(int[] array, int start, int mid, int end) {
    // Check bounds
    assert 0 <= start && start <= mid &&
        mid <= end && end <= array.length;
    if (start == mid || mid == end)
        return;

    // Find tail section of first list
    // and head section of second list
    int left = mid - 1;
    int right = mid;
    while (start <= left && right < end
            && array[left] > array[right]) {
        left--;
        right++;
    }

    // Swap elements
    int n = right - mid;
    for (int i = 0; i < n; i++) {
        int j = mid - n + i;
        int k = mid + i;
        int temp = array[j];
        array[j] = array[k];
        array[k] = temp;
    }

    // Recurse on two pairs of sorted sublists
    merge(array, start, left + 1, mid);
    merge(array, mid, right, end);
}

An actual implementation can be found here.

So far I was able to establish these points:

The recursive algorithm terminates, and correctly merges two lists.
In the worst case when merging two lists that are $n$ elements each, there could be $O(n)$ recursion depth. For example, when merging [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and [0, 10, 11, 12, 13, 14, 15, 16, 17, 18], the 9 swaps with 0 and then recurses. Due to the stack space usage, it is clear that the algorithm is not "in-place" as hoped.
If both initial lists have roughly the same distribution (and are "balanced"), then we can expect the merge recursion depth to be $O(\log n)$ which is good.

My questions are as follows:

Does this merge algorithm have $O(n)$ time complexity or something worse? Because if it's worse, then the overall merge sort can't be in $O(n \log n)$. I want to know if it can degenerate in a way similar to how quicksort can exhibit $O(n^2)$ behavior.
Is there a way to reduce the worst-case stack space usage to $O(\log n)$ using tail recursion? I'm thinking about the trick used in quicksort where recursion is used on the smaller subproblem and tail recursion on the bigger subproblem.

Motivation: I'm interested in learning about in-place stable merge sort algorithms. I have a background of implementing a variety of sort algorithms, including the standard merge sort with auxiliary storage.


texts: Proof of correctness of reversal algorithm for array rotation

texts:
We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}.

One algorithm which does this goes as follows:

Reverse A[0..d-1] (0-indexing)
Reverse A[d..n-1]
Reverse A[0..n-1]

These three steps surprisingly rotate the array correctly. What is the math behind this algorithm? Why does it give a correct solution? It feels magical to me. I am not able to put up a formal proof of its correctness.


texts: Doesn't post-order traversal require subtrees to be evaluated separately?

texts:
Consider this tree:

If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in post order, as the rule is left-right-root. One of my university professors said the correct answer for the post-order traversal of a tree similar to the one above would be B, C, D, E, A, but in my understanding, it should be B, D, E, C, A.

Am I getting it wrong? Shouldn't I evaluate (C,D),(C,E) as a subtree and then go back to the parent tree?


texts: What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

texts: I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "magical" potential function which makes everything work. My question is can someone share their experience in developing a potential function for amortized analysis and the intuition behind it?


texts: Is my recursive algorithm for Equivalent Words correct?

texts:
Here is my problem.
Problem
Given two words and a dictionary, find out whether the words are equivalent.
Input: The dictionary, D (a set of words), and two words v and w from the dictionary.
Output: A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output “v and w are not equivalent.”
I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?
 EquivalentWordsProblem(v, w, D)
 1.m <- len (v)
 2.n <-  len (w)
 3.substitutions = [] #array to save substitutions
 4.if m != n:
 5.  return "v and w are not equivalent"
 6.else
 7.for i <- m to 1 <-1 do
 8.  for j <- n to j <- 1 do
 9.    if v[i] != w[j]:
 10.           substituted_word <- v[1…i-1]+v[j] #we substitute v[i] for w[j]
 11.              if substituted_word in D:
 12.                substitutions.append(substituted_word)
 13.                   return EquivalentWordsProblem(v[1…m-i], w, D) #recur on the string of length m - i
 14.   else:
         return EquivalentWordsProblem(v[1…m-1], w, D) #recur on the string decreasing its length by 1
 15.if len(substitutions) != 0:
 16.  return substitutions
 17.else
 18.   return (“v and w are not equivalent”)


texts: Machine Learning algorithms based on "structural risk minimization"?

texts: Which machine learning algorithms (besides SVM's) use the principle of structural risk minimization?


texts: Different PDA design processes -- both valid?

texts:
This video shows how to design PDA from a CFG:
https://www.youtube.com/watch?v=ZImtQBMSW_Y
Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement separate rules like so ("q loop" state in the pic):

The author of the vid claims that any CFG can be converted into PDA using this basic structure.
Yet, I find PDAs that look very different.
E.g., this one:

My question: Is the single-hub method not always applicable? What are the general guidelines for when to use it and when not to use it?
If you could also explain how the PDA from the second image works step-by-step verbally, I would appreciate it.


texts: How to generate intermediate code in more than 1 pass in compiler design?

texts:
I'm taking a compiler-design class where we have to implement our own compiler (using flex and bison).
In dragon book by V.Aho et al. They have mentioned backpatching to backpatch forward references  for control structure and boolean expressions but this needs only one pass .

I don't want to use backpatching for forward references .

How to do this without using backpatching ?

I am using LEX/YACC aka FLEX/BISON and C/C++ .


texts:
What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):

reversal of a string
concatenation of two strings
repetition of a string a finite number of times
search/match a string inside another string
match and replace a string with another string inside a string
split a string, at some specified positions, or according to matching result of another string
taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
...


texts: Recommendation for good book or online course on distributed programming

texts:
I am a computer science student in his final year on the university with several years of experience in software engineering. I want to take me to the next level in programming web applications.
I am looking for a good book or online course on the subject of distributed programming with in-depth understanding, and how to design and build large and scaled web applications professionally like facebook, amazon, google from scratch.
By the way, I will be happy to hear also about a good book or online course which explain about all the new technologist that web application can connect/interact with like: AI analysis, databases, cloud computing and so on.
Thanks in advance.


texts:
I would like to know how we can demonstrate these two problems :

$A \leqslant_p B$ implies  $\overline A \leqslant_p \overline B$
The complement of 3-SAT is co-NP-complete


texts: For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best compression level? One can think about splitting data as small chunks and for each small chunk iterate all possible (de)compression codes to get best compression. Is there any research or existing algorithms, utilizing ideas like that?


texts: Give an example of a language where both L and ¬L is not semidecidable?

texts:
I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper approach for this question or am I completely off mark?

I also have few other questions, give an example of a language where:
1) L ∈ D and ¬L ∈ SD − D?
2) L, ¬L ∈ SD − D?

For 1) I know D is closed under complement therefore ¬L must be decidable iff L is decidable. So there are no examples?

For 2) I know if both L and ¬L are SD, then L must be decidable. So there are also no examples?

Sorry for some these questions, I am 90% sure I am right but I'm learning everything by myself so I have no one to ask to be sure. Thanks for any help.


texts: What kind of automaton recognizes closed terms of the lambda calculus?

texts:
There seems to be an interesting model of computation involved in determining whether a term from some programming language has any free variables. It's a tree traversal that seems almost like the process to recognize a context-free language, but it requires a little more information: the set of variables in scope at any point. At the same time, though, recognizing such a language doesn't seem complicated enough  to require the full power a Turing machine. I suspect that type-checking and other kinds of reasoning we do about programs could also be phrased in terms of a model like this.
I'd like to come up with a crisp definition for this kind of tree-traversal process. I'm hoping that there's a class of automata that are known to solve just this kind of problem. I'm focusing on finding closed terms of the untyped lambda calculus because that seems like the simplest instance of this problem.
Is there a well-known class of automata below Turing machines that can recognize closed terms of the lambda calculus? And/or is there a well-known class of languages below recursively enumerable that contains "the set of all closed lambda-calculus terms" as a language?
I know that context-sensitive languages are a level in between context-free and recursively enumerable languages, and that there are various classes called "mildly context-sensitive", but I don't know enough about those to say whether they fit the requirements here.


texts:
Parsing s-expressions is almost trivial. This is true for both automated processes (and thus implies ease of implementation of such processes) and for a human readers of printed s-expressions. It is the latter property that is the subject of this question.

The main cause for this simplicity is the one to one correspondence between certain tokens, and (types of) nodes in the AST. That is:

( denotes the start of a list-expression,
) the end of one,
whitespace separates atoms

That is: one can almost* look at an arbitrary substring of a printed s-expression and infer the structure of the associated AST.

Is there a name for this property of being able to infer the structure of a text locally, that is without any reference to the surrounding text, and using a 1-to-1 correspondence of certain tokens on screen and nodes in the AST?

I'm tempted to call this "explicitly structured", but that seems rather imprecise.

*"almost", because the parentheses might be quoted or part of a string literal; if we assume a mechanism of pretty-printing with relevant syntax highlighting for those cases, the qualification "almost" may be dropped.


texts:
A widely used example of reductions, is a reduction of  $A_{TM}$ to  $HALT_{TM}$.

How to show the opposite reduction, meaning of  $HALT_{TM}$ to $A_{TM}$, if possible.


texts: Shortest path using less than or equal to m edges in a directed, weighted graph with negative cycles

texts:
I'm solving a problem:

  Given a directed, weighted graph $G$ that has $V$ vertices (vertex $0$, vertex $1$, ... ,  vertex $(V - 1)$) and $E$ edges and a positive integer $m$, describe an algorithm that finds the length of the shortest path from vertex $0$ to vertex $(V - 1)$ using less than or equal to $m$ edges. Note that the graph may contain negative cycles. If there is no such path, print "N" for that case.

First, I tried Bellman-Ford algorithm, but I cannot deal with negative cycles. Next, I tried one using recursive DFS, but it takes too much time! I think dynamic programming may solve this problem, but I don't know how to start with DP. Is there any fancy way to solve this problem in short time?


texts: Building a poly-time verifier given a poly-time decider

texts:
Can I build a polynomial time verifier for problem, given a non-deterministic polynomial time decider for that problem?

I assume I should modify the decider such that it will verify the certificate.
Can I use the given decider as is (without any modification)?


texts: Difficulty in understanding few steps in the proof: "The class $\mathscr{H}_{p,m}$ of hash functions is universal"

texts:
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\dagger$ and $\dagger\dagger$ respectively.
Designing a universal class of hash functions
$p$ is a prime number large enough so that every possible key $k$ is in the range $0$ to $p — 1$, inclusive. Let $Z_p$ denote the set $\{0, 1,..., p — 1\}$, and let $Z_p^*$ denote the set $\{1, 2,..., p — 1\}$.Because of the assumption that the size of the universe of keys is greater than the number of slots $m$ in the hash table, we have $p > m$.
We now define the hash function $h_{a,b}$ for any $a \in Z_p^*$ and any $b \in Z_p$ :
$h_{a,b} = ((a.k + b) \mod p) \mod m $.
The family of all such hash functions:
$$\mathscr{H}_{p,m}=\{h_{a,b}: a \in Z_p^* , b \in Z_p\}$$

Theorem: The class $\mathscr{H}_{p,m}$ of hash functions is universal.

Proof:
Consider two distinct keys $k$ and $l$ from $Z_p$, so that $k \neq l$. For a given hash function $h_{a,b}$ we let
$$r = (ak + b) \mod p$$ ,
$$s = (al + b) \mod p $$.
We first note that $r\neq s$. Why? Observe that
$$r — s = a(k — l) (\mod p)$$ .
It follows that $г \neq s$ because $p$ is prime and both $a$ and $(k — l)$ are nonzero modulo $p$, and so their product must also be nonzero modulo $p$
Therefore, during the computation of any $h_{a,b}$ in $\mathscr{H}_{p,m}$, distinct inputs $k$ and $l$ map to distinct values $r$ and $s$ modulo $p$; there are no collisions yet at the "mod p level." Moreover, each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$$^\dagger$:
$$a = ((r — s)((k — l)^{-1}\mod p)) \mod p $$,
$$b = (r — ak) \mod p$$ ,
where $((k — l)^{-1} \mod p)$ denotes the unique multiplicative inverse, modulo p, of $k — l$. Since there are only $p(p — 1)$ possible pairs $(r, s)$ with $г \neq s$, there is a one-to-one correspondence between pairs $(a, b)$ with $a \neq 0$ and pairs $(r, s)$ with $r \neq s$. Thus, for any given pair of inputs $k$ and $l$, if we pick $(a, b)$ uniformly at random from $Z_p^* \times Z_p$, the resulting pair $(r, s)$ is equally likely to be any pair of distinct values modulo p.
It then follows that the probability that distinct keys $k$ and $l$ collide is equal to the probability that $r \equiv s (\mod m)$ when $r$ and $s$ are randomly chosen as distinct values modulo $p$. For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most$^{\dagger\dagger}$
$$\lceil p/m \rceil - 1 < ((p + m - 1)/m) - 1$$
$$ =(p-1)/m$$.
The probability that $s$ collides with $r$ when reduced modulo $m$ is at most $((p - l)/m)/(p - 1) = 1/m$.
Therefore, for any pair of distinct values $k,l \in Z_p$,
$$Pr\{h_{a,b}(k)=h_{a,b}(l)\}\leq 1/m$$
so that $\mathscr{H}_{p,m}$ is indeed universal.

Doubts:
I could not understand the following statements in the proof:
$\dagger$ :Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$
why , "we can solve for $a$ and $b$ given $r$ and $s$" $\implies$ "Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $г \neq s$"

$\dagger\dagger$ : For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most $\lceil p/m \rceil - 1 $ .
How do we get the term $\lceil p/m \rceil - 1 $ ?


texts: Does word addressable memory have more bytes than byte addressable memory?

texts:
Well, my question - if word addressable memory has more bytes than byte addressable memory - is derived from the fact that in word addressable memory each address addresses a word and in byte addressable memory each address addresses a byte.
In the case of word addressable memory - If the word size is 4 bytes 32 bit architecture, for example, do i have 4*2^32 bytes in my memory?
And in the case of byte addressable memory -will i have 2^32 bytes in my memory?

How is it possible that the same ram, i.e given the ram size is 4 GB, would contain different number of bytes depending on byte/ word addressable memory?

1GB RAM has 1*1024*1024*1024 bytes in it. Say our architecture is 32 bit. So in the case of byte addressable memory there will be 4*1024*1024*1024 virtual addresses per program but in reality there are 1*1024*1024*1024 physical addresses, each points to a byte.
In the case of word addressable memory there will be 4*1024*1024*1024 virtual addresses per program - each address points to a word? So in this case there will be theoretically 4*4*1024*1024*1024 bytes available for each program ?
There will be 1*1024*1024*1024 physical addresses, each address points to a word. So there are actually 4*1*1024*1024*1024 bytes in the memory in this case?

As you can see I am super confused.


texts: Unique number to represent a combination of 5 numbers 1-39

texts:
This is a related question poker hand representation and I got a great accepted answer. The problem can be reduced to a virtual 39 card deck that from what I can tell is 16 bits.

I have 5 numbers 1-39 with none repeating. I need to uniquely identity those 5 numbers with the smallest possible number and not order dependent on the 5.  I am pretty sure the number is 2^16. From the accepted answer to the link you go 01, 10, 100, ... and then start folding back.  Then use an XOR on that matrix.  I tried but I cannot figure out when / how to start folding back.

What is the matrix / array?


texts: Calculate storage requirements for a data set

texts:
I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading.

I'm writing a bunch of integers to disk. Lot's of them.

Starting with the integer 2, I add it to another integer, write the result to disk, and start the process again using the result as the seed.

This pattern is helping me generate data I need for other research, but I need to apply this pattern until I've reached integers with a length of 10,000 digits or more.

So, here is my simple question: given a set of data of a known data type, how do I calculate the storage space required to store that set?

At the moment, I'm doing this incredibly simple task in Python, recording longs to disk as binary in a single file. But, on my very small machine, I was only able to store the integers my process produced with values between 0 and 42 billion.

Short of my goal of recording a data set with values between 0 and 1e10000.

Given that I have no exposure to formulas for calculating hardware requirements for storing data like this, I have no idea if I'm using the most efficient language and data type for storing as many integers as possible in as little space as possible.


texts: How to calculate least common multiple (LCM) for two numbers with constants (shifts)?

texts:
What's the most effective algorithm to calculate LCM for 2 numbers where each of them has their own "shift"?

Example:

We want to find LCM for 25 + 5 as c and 30 + 10 as c
Then for the first case, the sequence will look like this:

25*1+5, 25*2+5, 25*3+5, 25*4+5...

And the second one:

30*1+10, 30*2+10, 30*3+10, 30*4+10...

In this case, the result should be 130 - 5th member of the first sequence and 4th of the second one.


texts: Two recurrences for the change-making problem with repetition

texts:
The change-making problem with unbounded repetition is:

  Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$ and an amount $v$.
  Output: Can the given $v$ amount of money be made with these coins?

The first recurrence is based on the subproblems of
$C[w]$: can $w$ be made with these coins?

$$
  C[w] = \bigvee_{i: x_i \le w} C[w-x_i].
$$

The second recurrence is based on the subproblems of $C[i,w]$: can $w$ be made with coins $x_1, \ldots, x_i$?

$$
  C[i,w] = (C[i, w-x_i] \land w \ge x_i) \lor C[i-1, w].
$$
The recurrence consider both cases of whether $x_i$ is used or not.

Problem:
I think both recurrences are correct. Therefore, I want to understand their connections.

Specifically, how are they equivalent (if both are correct, of course) in terms of the subproblems they solve.

Can we transform one to another by, for instance, introducing a second variable to the first one or eliminating one variable from the second one?


texts:
Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass through all roads between the cities, not just the cities. The traditional shortest path algorithims do not work because they only calculate the shortest distance between 2 points, and don't guarantee passing through all of the roads. Here is a vague map of my problem.

For a solution to be valid, it must pass through every road in between the points labeled.


texts: Is there any recent study about percentage that computer spend on sorting?

texts:
I came across this on Art of Computer Programming long time ago

  Computer manufacturers of the 1960s estimated that more than 25 percent
  of the running time on their computers was spent on sorting, when all their
  customers were taken into account.

Is there any recent study about the estimated percentage that computer spend on sorting? 1960s is pretty old.


texts: Lower bound on worst case pancake number?

texts:
Given n pancakes, for each permutation we can compute the minimum number of pancake flips.  If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$.

I think I can prove that $P_n \geq n$.  My argument is that I can start from the sorted pancake, and do a "anti-sorting" of the pancake by first flipping at position n, then position at n-1, n-2, etc.

For example, the case of n=5 would yield 34251.

Sorting such a pancake would take at best n steps.

Am I doing something wrong?


texts:
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or domain name (U-label) consists of a string of Unicode characters, typically constrained to one language depending on the top-level domain (e.g. Greek letters under .gr), which is encoded into an ASCII string beginning with xn-- (the corresponding A-label).

One can build data models not only from the formal requirements that

each non-Unicode label be a string matching ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;
each A-label be a string matching ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; and
the total length of the entire domain (A-labels and non-IDN labels concatenated with '.' delimiters) not exceed 255 characters

but also from various heuristics, including:

lower-order U-labels are often lexically, syntactically and semantically valid phrases in some natural language including proper nouns and numerals (unpunctuated except hyphen, stripped of whitespace and folded per Nameprep), with a preference for shorter phrases; and
higher-order labels are drawn from a dictionary of SLDs and TLDs and provide context for predicting which natural language is used in the lower-order labels.

I fear that achieving good compression of such short strings will be difficult without considering these specific features of the data and, furthermore, that existing libraries will produce unnecessary overhead in order to accomodate their more general use cases.

Reading Matt Mahoney's online book Data Compression Explained, it is clear that a number of existing techniques could be employed to take advantage of the above (and/or other) modelling assumptions which ought to result in far superior compression versus less specific tools.

By way of context, this question is an offshoot from a previous one on SO.

Initial thoughts

It strikes me that this problem is an excellent candidate for offline training and I envisage a compressed data format along the following lines:

A Huffman coding of the "public suffix", with probabilities drawn from some published source of domain registration or traffic volumes;
A Huffman coding of which (natural language) model is used for the remaining U-labels, with probabilities drawn from some published source of domain registration or traffic volumes given context of the domain suffix;
Apply some dictionary-based transforms from the specified natural language model; and
An arithmetic coding of each character in the U-labels, with probabilities drawn from contextually adaptive natural language models derived from offline training (and perhaps online too, although I suspect the data may well be too short to provide any meaningful insight?).


texts: How do you find out if the polygon lies to the right of a regular vertex?

texts:
In section 3.2 of the book Computational Geometry: Algorithms and Applications (by Berg et al.), the authors describe a procedure to make a polygon y-monotone. The algorithm distinguishes vertices into $5$ different types: "start", "end", "regular", "split" and "merge" vertices.

A regular vertex is a vertex which has one of its neighboring vertices above it, and the other neighbor below it. A regular vertex can be on the left or right chain of the polygon.

Given a regular vertex $v$, how do I find out if the polygon lies to the right or left of $v$?

The polygon is stored in a doubly-connected edge list. The vertices have coordinates and are stored in a normal DCEL data structure along with the half-edges and polygons. It seems reasonable to expect an elegant solution that uses the DCEL.


texts: Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

texts:
Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of an unbounded power. It is known to be equal to $\mathsf{PSPACE}$.
Making the verifier a deterministic machine would make a complexity class $\mathsf{dIP}$ which is known to be equal to $\mathsf{NP}$.
However, if $\mathsf{P=BPP}$ would that mean that a deterministic verifier is as powerful as a probabilistic verifier, resulting in some implications believed to be false by the majority of computer scientists?


texts: Formal language representation of program

texts:
I have numerous records, composed of words. Each word gets translated into vectors, with a variable number of channels, provided that that word exists in a specific lookup dictionary.

For n number of words in every record, based upon c number of channels that each vector-based representation of the words possesses, a function f is fed this stream of data and outputs a probability p.

n and c are both constants.

How might this be represented in formal language?


texts: Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?

texts:
I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.

Example:

Set 1:

Some good product
Another product
Some name
Blah

Set 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

Set 1 contains "good" names. Set 2 contains "dirty" names.

I want: for every item from Set 2 (further: item2) find the longest item from Set 1 (further: item1) so that all words from item1 are contained in item2.

For the given example the pairs will be the following:

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

So far I couldn't think of anything better than brute force algorithm:

Split every string from Set 1 into words = we get a set of lists of words, let it be Set 3
Split every string from Set 2 into words = we get a set of lists of words, let it be Set 4
Pick up a list of words from Set 3 (further: list3), compare it to all the lists of words from Set 4 until find some list which is fully contained in the list3.

However it has pretty high complexity and works quite slow. My simple implementation takes about 1.8s to find 1 pair (Set 1 has 3mln items, Set 2 has 4mln items). If I implement same task using MySQL-fulltext indexes (it allows to search for strings which contain all given words) then 1 search takes about 0.4s. So I'm wondering whether there are some good approaches which could be applied here with small blood :)

My programming language is PHP7. The data is stored in MySQL DB.


texts:
I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here.

I'd started a simple test with the "Western Sahara - 29 Cities" (wi29) and found that my algorithm rapidly found a few better particular solutions than the proposed optimum.

I checked one of them manually and didn't find an error. So, I guess, here're the three options.

I did a mistake.
Wrong optimum.
Different problems were solved.

1 and 2. My solution tour is:

  17>18>19>15>22>23>21>29>28>26>20>25>27>
  24>16>14>13>9>7>3>4>8>12>10>11>6>2>1>5

(will list my checking calculations if requested)

Rounded length: 26040.76.
Optimal reference value: 27603.

I can't find a particular task descriptions and especially rounding policy for the TSPLib examples optimums. This is important, because they're looking rounded or discretized in another manner, but simple result rounding isn't looks like it.


texts: In reading the Wiki article on Simon's Problem, the article states that it takes exponential time(in the classical version) to discover the secret string S that is inside the black box. Why is this black box problem not considered to be a one way function and are there any cryptographic primitives based on the hardness of discovering the secret string S. Thank you!


texts: How Does Dynamic Heap Storage Have Something to Do with Heap?

texts: There are three typical ways to allocate memory for programs: static, stack and dynamic heap. However, when I look at the implementation of dynamic heap memory allocation from wikipedia , what I found is fixed block allocation, etc. So why is dynamic memory allocation called "heap" memory allocation? How does it have something to do with "heap"?


texts: What is the time complexity of this function?

texts:
This is an example in my lecture notes.
Is this function with time complexity $O(n \log n)$?.
Because the worst case is the funtion goes into else branch, and 2 nested loops with time complexity of $\log n$ and $n$, so it is $O(n \log n)$. Am I right?

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}


texts: Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

texts:
Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$.

  Find an algorithm that sorts the input in $O(n\log (\frac n k ))$ runtime.
  Find a lower bound for the minimal amount of comparisons in the worst case.

is pretty simple I think:

for each S_i
   mergesort(S_i[n/k])

But with 2. I get results that can't be right: in the worst case there would have to be at least $(\frac n k )!$ comparisons for each $S_i$ because the algorithm will have to pass each combination at least once, also, this is the amount of leaves at the lowest level of the decision tree.

This gives: $T_{worst}(n) = \Omega (k(\frac n k )!)$ which is a lot larger than $O(n\log (\frac n k ))$. So what am I doing wrong here?


texts: weight constrained shortest path problem variants

texts:
Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{e\in E_{p}} w(e) \leq W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$, where $W,K\in Z^{+}$.

This is Weight constrained Shortest Path Problem, and known to be NP-complete for undirected as well as directed even acyclic graphs. as long as $\delta$ and $w$ is not equal for all edges. Now if we move weight from edges to vertices and change $\leq$ of total weight constraint to $=$ then the new problem is:

Given a directed acyclic graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:V\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{v\in V_{p}} w(v) = W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$.

Is this problem known ? is this solvable in P time ? or this is NP-complete too ? I think even if we replace $\mathbb{Z}^{+}$ with $\mathbb{R}^{+}$ it will not change nature of the problem.

If we set $W=\vert V \vert$ then it tries to reach all the vertices which looks like hamiltonian path problem, but it is a DAG.

Update

I was trying to reduce it from Subset Sum as suggested by @D.W.

Given $X=\{1,2,3\}$ of size $\vert X \vert = n$ I can convert that to a graph of $n^{2}+n+2$ vertices. We can make $n$ layers of $X$ and connect every vertex with all vertices of next layer except itself. Keep a vertex with 0 weight on each layer. As show below.

But this reduction has 2 restrictions.

Every Layer is not complete bipartite (e.g. $2_{i}$ does not connect to $2_{i+1}$).
Every layer must have a vertex with 0 weight.

Now this does not prove the second problem for General purpose DAG. I can not connect $x_{i}\rightarrow x_{i+1}$ because that will change the original problem. So if there is a DAG that looks very similar to this one but have $n^{2}$ edges between each layer and have no 0 weight vertex this reduction does not apply to that graph.

Also in this formulation I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed


texts: Proof: There exists an irregular language L such that LLLL is regular

texts:
As title.

I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.

A senior gave me a hint that Lagrange's four square theorem might help, but I don't see how I can utilize it.

Thanks.


texts: How all values hash to the same value with a given formula

texts:
When looking at hashing, and given the following question:
Given ASCII values: a = 97, b = 98, c = 99, d = 100, e = 101

Given keys: {e, ae, be, ce, de, abe, ace, ade, bae, cae, dae, bce, bde, cbe, dbe}

If we choose: h(k) = k mod 2^6 to map these keys to hash tables indexes, what do you notice?

The answer to this is that all of them hash to 37 but when I try this on a calculator they do not and I do not understand how to get 37. I think this has something to do with the low order bits reference in CLRS and the fact that it is not using a prime number but if I add for example:
a + e = 97 + 101 = 198 % 64 = 6
b + e = 98 + 101 = 199 = 199 % 64 = 7
When I look at the the binary for 6 and 7 they do not end up being the same and neither of the values above ends up resulting in 37.
Any help understanding this is appreciated!


texts: Does approximation ratio depend on the input size $n$?

texts:
I have started study of approximation algorithms and have confusion about the definition of approximation algorithm. I have two textbooks: by Cormen and the second one by Williamson.

Cormen's textbook says

  If an algorithm achieves an approximation ratio of $\rho(n)$, we call it a $\rho(n)$-approximation
  algorithm.

Williamson's say

  An $\alpha$-approximation algorithm for an optimization problem is a polynomial time algorithm that for all instances of the problem produces a solution whose value is within a factor of $\alpha$ of the value of an optimal solution.

So, the first definition defines approximation factor depended on $n$, while the second one does not mention of dependence of $\alpha$ on $n$.

Also I have never seen (yet at least) something like for example $(n/10)$-approximation algorithm, but seen $2$-approximation, or $3/2$-approximation.

My question: could someone clarify the precise definition of the approximation algorithm? (Wikipedia didn't help much). In particular, why do we need the dependence on $n$ if all ratios seem to be constant?


texts: How is adversarial autoencoder better than an ordinary autoencoder?

texts:
An adversarial autoencoder helps us to impose a prior distribution $p(z)$ on the encoded values of the inputs, or $q(z)$.

On the contrary, an ordinary autoencoder (which we train like an ordinary neural network (comparing output to input using mean squared error) does not give us any control over the encoded distribution.

How does imposing a prior distribution help improve the accuracy of the GAN? I know both entities (discriminator and generator) play a minimax game boosting each other's capability, but how does improving discriminator and generator improve the weights for encoder and decoder to match input image $x$ correctly with the output image?

(image taken from Makhzani et al)


texts: Finding the point nearest to the x-axis over some segment

texts:
I have problem with solving the following exercise

  Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ find the first point that $s$ touches when moving upwards from the x-axis in time $O(\log^2n)$.

The preprocessing time is equivalent to sorting, so we can perform sorting by one dimension.

The query time is a little bit confusing - $\log^2$n. I would say it's $\log n$ binary searchs but it doesn't make sense.


texts: Blob detection as Constraint satisfaction problem?

texts:
In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to Constraint Satisfaction problem (as p/np complete)?

Black and white image with white blobs.


texts: Provably correct algorithm/CAS for checking term equalities

texts:
Within my research of term rewriting systems (TRS) I stumbled upon a paper (Siekmann, J., and P. Szabó. “The Undecidability of the DA-Unification Problem.” The Journal of Symbolic Logic, vol. 54, no. 2, 1989, pp. 402–414. JSTOR, JSTOR, www.jstor.org/stable/2274856.) that stated the following:

  We show that the DA-unification problem is undecidable. That is, given two binary function symbols $+$ and $*$, variables and constants, it is undecidable if two terms built
  from these symbols can be unified provided the following DA-axioms hold:
  $
 (x + y) * z = (x * z) + (y * z),\\
x * (y + z) = (x * y) + (x * z),\\
x + (y + z) = (x + y) + z \\
$
   Two terms are DA-unifiable (i.e. an equation is solvable in DA) if there exist terms to be
  substituted for their variables such that the resulting terms are equal in the equational
  theory DA.
   This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which
  an undecidability result has been obtained.

  [...]
   Hilbert's tenth problem presented to the International Congress of Mathematicians in his 1900 speech in Paris poses the question, if it is decidable whether a given polynomial equation is solvable in positive integers; a problem that was finally shown to be undecidable.

My resulting question is: Does this prove that there cannot be an algorithm / computer algebra system that, even for very restricted sets like $\mathbb{Q}$ with operators $+, -, *, /$, is provably correct when it comes to checking term equalities (for example), when distributivity and associativity hold?

The Wolfram documentation states that

  [t]here is a basic result in the mathematical theory of computation which shows that this [ reduce all expressions to some standard form] is, in fact, not always possible.

which would be needed for such a system.

I found the Richardson theorem which basically states that there may not exist an algorithm that decides if two expressions representing numbers are semantically equal, if exponentials and logarithms are allowed in the expressions.

This still does not answer my question for a set without such expressions, although it hints that this should be possible.

Not only complete answers but also further reading hints are appreciated.


texts:
With regards to introductory (beginner) Von Neumann computer architecture, how does a program change the order in which instructions are executed?

I know the control unit is responsible for retrieving the instruction from memory and then decodes and executes the instruction. Their connected by a bus. The control unit and ALU are together in the CPU.

I'm guessing different lines of code are stored in different addresses in the RAM?

Is it a easy question, and I'm just thinking its difficult?


texts:
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine an oracle solving 3SAT problem, and show that $BPP^{NP}\subset NP^{NP^{NP}}$? Is it because normally, the proof in complexity theory can be easily relativized by an oracle?


texts: Can parameters be contra- or covariant in Python?

texts:
I've just now studied about covariance and contravariance in static languages (more specifically C#). This concept is rather clear to me, however I'm in doubt on how this applies to dynamic languages like Python.

Since Python is duck typed (or structural typed) it seems to me that there is not even a notion of variance and covariance in this language?

If I'm not mistaking, things like contravariance and covariance are checked at compile-time in a language like C#, this is possible because a variable has a type, and the value it is bound to has a type as well and these have to match or be co(ntra)- or invariant. However, since there is no notion of typing at compile-time with a language like Python I don't know how to apply this concept.

Any thoughts?

My thoughts: The concept of covariance means that whenever we expect a type of X, any subclass of X will do as well. So, in Python this doesn't come up, because there is no type check to do this. The only check that happens is wether or not the object has the necessary implementations by means of methods and attributes.

In C# for example where we have a method:

void DoStuff(Person p)
{
    p.Dance();
};

We could very well call this method with an instance of a Student (if this is a subclass of Person).

Now, in Python, we could very well pass in a Bird object that would not be related to Person in any way in the inheritance hierarchy(except it would also inherit from object), as long as this bird implements Dance().

This is why I'm asking about this concept. From what I understand Python is covariant and contravariant in.. well, everything?


texts: For practical computing purposes, every algorithm is O(1)?

texts: I am taking a course in algorithm analysis and the professor is arguing that using the negation of the definition for Big O, it can be argued that, for practical computing purposes, both the running time and the memory usage of every algorithm is O(1). How is this possible? How can it be proven?


texts: Where to get proofs of open problems checked?

texts: I have found what I believe is a proof of related to an open problem in computer science.  I've written it up in LaTeX, and I am looking for a way to get it evaluated.  I know that cs.se/cstheory.se are not the appropriate forums to post this proof; what is the appropriate place to share my proof?


texts:
I have a question.
All finite languages can be decribed using a regular expression?


texts:
I have been reading about how to test the undecidability of a problem, and some tests talk about the reduction technique. For what I could understand of this technique is that if I want to prove that problem X is undecidable I can take a problem Y which has already been proven to be undecidable. Then by using logic or mathematical manipulation, I try to reduce or get an instance of problem X by modifying problem X, am I right?

So for example, if I want to test the undecidability of problem X, it would be fair if I pick up, for example, the undecidability of the detection of computer viruses, as stated by Cohen, as an undecidable problem by applying reduction to it, would that be fine?


texts: Is this a correct grammar for untyped lambda calculus?

texts:
I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this:

without left-recursion:
TERM         -> APPLICATION | ABSTRACTION
ABSTRACTION  -> LAMBDA LCID DOT TERM
APPLICATION  -> ATOM APPLICATION'
APPLICATION' -> ATOM APPLICATION' | ε
ATOM         -> LPAREN TERM RPAREN | LCID
LCID         -> 'a' | 'b' | ... | 'z'
DOT          -> '.'
LAMBDA       -> 'λ'

I assume that for writing the parser I do not necessarily need the productions that only expand into terminals.

Can this grammar be used to write a recursive descent parser that only does 1-token lookups? What would be the resulting AST for (λx.x)(λy.y) ?


texts:
Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.

I have quite a large bitmap (~100 Million bits) (e.g. 100100101001010001001...010010). The bitmap is just an example, it doesn't have to start with 1 or end with 0.

Now, I need to choose randomly any 0-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the  algorithm would be linear or O(n lnn) in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.


texts: What is the type theory judgement symbol?

texts:
In type theory judgements are often presented with the following syntax:

My question is what is that symbol in the middle called? All the papers I've found seem to use an image rather than a unicode character so I can't look it up. I've also not found any type-theory reference which says what that symbol is (they explain what it means however).

So what character is that symbol and what is its proper name?


texts:
$\Sigma=\{a,b\}$, $L=\{w\in \Sigma^* \Big| |w|=3n+5m, \ n,m\ge 0 \}$.
I need to build NFA automaton for $L$....

Now, I try it for hours but I don't have any idea how to solve it.
I know that any $x\ge 8$ can be written as $3n+5m, \ n,m\ge 0 $
So, the automaton accepts any word the her length is 8 or higher, but it doesn't accepts words at length: 1,2,4,7.
One more rule: $|Q|=5$....

Can you help me please and guide me how should I solve it?
Because I don't have any idea so far...
Any automaton  that I make accepts some of the words in the forbidden length...

Thank you!


texts: Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$?

texts: I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?


texts: Regexp substitution and finite-state transducers

texts:
Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, t are strings, sub(s, r, t) finds the first substring of s that matches the regexp r and replaces it with t.

Can this operation always be represented as a finite-state transduction?  In particular, are we guaranteed that for each r, t, there exists a finite-state transducer $T$ that implements the function s $\mapsto$ sub(s, r, t)?  Can it be done with a deterministic finite-state transducer?  If not, can it be done with a non-deterministic finite-state transducer?

Here's an example of a case that seems non-obvious to me.  Consider the regexp 00(00)*11, e.g., the operation sub(s, "00(00)*11", "2").  If we imagine trying to build a finite-state transducer for this operation, it seems like once it has seen 00 on the input, it has to keep reading 00's until it sees a 1 and not output anything until then (since it doesn't know whether this block will be of the form 0000...0011 or 0000..0010).  If it sees 0000..0010, then at that point has to emit all of the saved-up 00's.  But how does it keep track of how many to emit?  Finite-state machines can't count, so I can't see how to achieve this.


texts: A microkernel fully hardcoded in hardware?

texts: Does there exist a (micro-)kernel of an operating system that is fully implemented in hardware? That is, a kernel that is not stored in RAM, and loaded into CPU registers after an interrupt or system call, but is instead a fully hardcoded part of the CPU itself, so that a system call/interrupt never leads to a context switch?


texts:
My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be.

For instance, for SAT, the certificate could simply be be the assignment values. We just sub them in and see if it satisfies the expression.

But can't we just let the certificate by whether the string belongs or not? So for instance, for SAT, instead of the certificate being the assignment values, we let it be whether the expression is satisfiable or not. In other words, the certificate is the "answer".

If we let the certificate be this, can't be verify any string in polynomial time? Constant in fact, because we would just be returning the certificate itself, since the certificate is the "answer" (whether the string is part of the language or not)


texts:
A multiset is an unordered collection of elements where elements may repeat any
number of times. The size of a multiset is the number of elements in it counting
repetitions.

(a) What is the number of multisets of size $4$ that can be constructed from $n$
distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be constructed from $n$ distinct elements?

For part b, infinite is correct.

For part a, taking $n=3$ and elements $\{1,2,3\}$ we have multisets as:
$\{1,1,2,2\}, \{1,1,3,3\}, \{1,1,2,3\}, \{2,2,3,3\}, \{2,2,1,3\}, \{3,3,1,2\}$, for a total of $6$.

Similarly for $n=4$ and using elements $\{1,2,3,4\}$, we have $18$ multisets. There must be some formula, or we have to develop one!

I am in particular looking for a formula when there is a restriction on the number occurrences in the multiset.


texts: Mixed Integer Linear Programming application problem

texts:
I have a Mixed-Integer Linear Programming question.

There's this game called Islanders. Pretty graphics, it's about maximizing your score building a small city in a confined island.

Here's a quick rundown of the rules:

There are various building types
Every building type has a different size
Every building type has a different range (explained later)
Every building may give a non-zero base score when placed
Every building may have give a positive, zero or negative score based on what buildings are within its range when placed
Buildings already placed are not affected by newer buildings (their score contribution is not updated)

I thought it would be a fun exercise to formulate these rules into an MILP and see what comes out of it.

I have written the attached Python 3 program, using the PuLP library (link).
I have used the default solver (CBC), provided with the installation of PuLP.

There are currently 4 building types encoded, with their base score declared at line 61, the 4x4 cross-score matrix at line 64 and their dimension and range in lines 72 and 75.

In line 82 there is currently stated that there is 1 building of the first type and 3 buildings of the 2nd type to be placed optimally (N=5)

There are several decision variables:

px and py are each building coordinates
t is the build order (integer)
placed_before is a NxN array saying if building i is to be placed before building j (binary)
east_of, north_of have similar logic (binary)
covers states whether building j is in range of building i (binary)
x_overlaps and y_overlaps check whether two buildings are built on top of each other, which is restricted (binary)
gives_score is a NxN array saying if building i contributes to the score of building j (is whthin range is is placed before it, binary)

The constraints are as follows:

Lines 140-147 state the building order constraints, which form variable t
149-161 decide if buildings are east-west and north-east, used for later
163-183 establish whether buildings overlaps each other, in the east-west (x) direction and the north-south (y) direction
185-219 establish if building i covers building j, filling in the covers variable
222-237 enforces the separation of two buildings, if they overlap in both x and y directions
239-250 finds out if a building i contributes to the score of building j

Currently, the cost function under optimization is gives_score, to maximize the number of buildings which give score to another.

The issue:

Currently with 1 of the first building and 4 of the second, the optimization does not finish in reasonable time. 380 constraints are generated.
If instead you go for 3 of the second building type, the problem becomes tractable again, finishing in approx. 10s. 228 constraints are generated.
Also, if you disable the constraints of lines 222-237, the optimization manages to run, but the buildings overlap.

Any suggestions on the problem formulation or explanations on why this is such a hard problem?

Thank you in advance.

Bonus:
Here is an example optimal result for 1 of type-1 building and 3 of type-2:


texts: Sum of two elements in set evenly divisible by k

texts:
I have gone through this particular problem in hackerrank.

  You are given an array of $n$ integers, $a_0, a_1, a_2 , \ldots, a_n$, and a positive integer $k$. Find and print the number of pairs $(i, j)$ such that $i < j$ and $a_i + a_j$ is evenly divisible by $k$.

I wanted to make this work in $O(n)$ time. After lots of searching I found a solution online.

a = [1, 3, 2, 6, 1, 2]
k = 3
m = [0]* k
count = 0
for i in a:
    rem = i % k
    com = (k - rem) % k
    count += m[rem]
    m[com] += 1
    print(rem, com, count, m)
print(count)

This particular snippet works in $O(n)$ time. But I am having a hard time understanding whats going on mathematically, especially with rem and com variables.

Can anyone please explain me the aspect(mathematical) behind it.


texts: Agreeing on a Time in a Trustless Network

texts:
Imagine a chord-like network $N$. each machine $m \in N$ is directly connected to $N_m \subset N$.

Without relying on official timeservers, I want all machines to synchronize to some time with millisecond precision.

my algorithm is executed some time after a machine joined the network, and works as follows:

the machine asks each machine it is directly adjacent to what it
thinks the network time is, adjust for latency and subtract local
time from that
take the median delta of that list, and apply that
to the local time as the network time.

Intuitively I think that this method is self-stabilizing because the deviation, and its error should be normally distributed around a consensus, and the $\sigma$ of the delta should decrease over time.

Problem is, I think that a relatively small number of bad actors can poison the network: if only $|N_{m_0}|/2 +1$ of the machines in $N_{m_0}$ don't abide by the protocol and report a doctored time, $m_0$ becomes poisoned and starts trying to poison other innocent nodes in $N_{m_0}$, and so forth, until all of $N$ is poisoned.

I was wondering whether I was correct, and if you know of any papers on the topic, because this seems more complex than I originally thought. Is a blockchain really required?


texts: Are graphic cards using the Map-Reduce model when performing typical gaming rendering

texts: I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. However when reading about the graphic pipeline I am not sure if there is a point at which the Map Reduce model is used. If not, what kind of parallel computations (just the general model of them so I could read more about it) are done during the typical rendering process of modern graphics cards? If it is used, where would that be on the below pipeline?


texts: Heuristics vs meta-heuristics vs hyper-heuristics?

texts:
The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic".

The wikipedia page on hyper-heuristics states that they are "heuristic search methods that seeks to automate [...] the process of selecting, combining, generating or adapting several simpler heuristics".

Moreover, it also states that "The fundamental difference between metaheuristics and hyper-heuristics is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics."

This leaves me confused: it seems like the hyper heuristic page is contradicting the meta-heuristic page. How can a meta-heuristic search for heuristics, if its search space is the problem space rather than the space of heuristics?

What really is the difference between metaheuristics and hyperheuristics?


texts:
Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.
For each natural number $k$, we will have a formula $\phi$ of length $n$ that does the following: $\phi$ is satisfiable iff the assignment encodes a run of $M$ on $\phi$ of length $n^k$ that ends in the reject state.
Suppose SAT can be computed in time $n^k$, and let $\phi$ be the formula associated with $k$. If $\phi$ is satisfiable, then the satisfying assignment encodes a run of $M$ on $\phi$ ending in the reject state. If $\phi$ is not satisfiable, then by our assumption there is a run of $M$ on $\phi$ of length $n^k$ ending in the reject state. An encoding of this path satisfies $\phi$. Contradiction. Therefore, SAT cannot be computed in time $n^k$.
Any opinions?  I'm curious if anyone has an immediate reason why this wouldn't work.  (I'm quite aware that it would be difficult.)


texts: Examples of maximal paths in undirected graphs

texts: According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the graph happens to contain cycles?


texts: Find a regular language that becomes non-regular if you cut away the middle third of all words

texts:
Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$.
Show that $A'$ is not necessarily regular language.

This is an excercise of Sipser, I've no idea how to construct $A,A'$ please help someone


texts: How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language?

texts:
For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings made up of every other character in the strings in the original language). What would be the generalized construction technique for creating the new DFA that could be applied to any DFA to produce the same results?

I think there's something to it involving creating an NFA using lambda transitions from each state to the following state in the original DFA, then converting the NFA to a DFA, but that creates a DFA that accepts more strings than originally intended.

Any suggestions?


texts: Mathematical optimization with thresholded optimization function

texts:
Gradient descent can be used to minimize an objective function $\Phi:\mathbb{R}^d \to \mathbb{R}$, if we know how to evaluate $\Phi$ on any input of our choice.

However, my situation is a little different.  I have an objective function $\Phi$ of the form

$$\Phi(x) = \Phi_1(x) + \Phi_2(x),$$

where I can evaluate $\Phi_1$ on any input of my choice, but I don't have the ability to do that for $\Phi_2$.  Instead, for $\Phi_2$, I have only a thresholded (quantized) version of $\Phi_2$: I can evaluate $f_2:\mathbb{R}^d \to \{0,1\}$ on any input of my choice, where $f_2$ is defined by

$$f_2(x) = \begin{cases}
0 &\text{if } \Phi_2(x)\le t\\
1 &\text{if } \Phi_2(x) > t\\
\end{cases}$$

and $t$ is fixed.  You can assume that $\Phi_2$ is smooth and has all the nice properties you might like, but I can only evaluate $f_2$, not $\Phi_2$.  How can I search for an $x$ that's likely to make $\Phi(x)$ as small as possible, in this situation?  Is there any way to adapt gradient descent or other mathematical optimization method to this setting?

Why I think there might be some hope: if we find $x',\delta \in \mathbb{R}^d$ such that $f(x')=0$ and $f(x'+\delta)=1$, where $x' \approx x$ and $\delta \approx 0$, then we've learned some information about $\Phi_2$, e.g., that the partial derivative of $\Phi_2$ is likely to be large in the $\delta$ direction.  It seems like it might be possible to build an algorithm to exploit this kind of information.  Are there any techniques to handle this kind of situation?


texts: Studying for the graduate entrance exam at CSULA

texts:
I'm an undergraduate student, but not a computer science major. I'm thinking of switching to CS after I graduate. I found a program that seems to allow students to take a test and gain entry into their school without having majored specifically in computer science first.

Here's the link: http://www.calstatela.edu/sites/default/files/groups/Department%20of%20Computer%20Science/sample_assessment_test.pdf

What online resources (YouTube videos, online courses, etc.) would enable someone without workplace or coding experience to fully address each of the prompts on this entrance exam?


texts: DFAs that must reach a certain state at least once

texts:
I was given this question:

  Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0.

  Define the language A⊆Σ* to be the language consisting of all strings that are accepted by M and cause M to enter the state r at least once.

  Give a precise description (the 5-tuple definition) of a deterministic finite
  automaton N that accepts the language A.

My question is, wouldn't it be possible to define N as (Q,Σ, δ, q0, F) with F={r}? Unless I am sorely mistaken, it should be able to meet the question's criteria shouldn't it?


texts: Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?

texts:
I am reading about red-black trees in Introduction to Algorithms, Second Edition by Cormen. Pages 316, 317.

I don't understand why we need to rotate the given tree. See (c) and (d) in the attached picture.

The author says that the following properties of a red-black tree can be violated after a new node has been inserted:

the root is black;
children of a red node are black.

The second property is restored in (b). The first property wasn't violated because we didn't insert the tree root. So why do we need to perform any other actions after recoloring?


texts:
CLRS states that:

  For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{21}$ such that for any $i \in I$, we have $f_{12}(e_1(i)) = e_2(i)$ and  $f_{21}(e_2(i)) = e_1(i)$.

My understanding of the above statement says that, for example, if we have base 2 encoding of a problem, we can convert it to base 3 encoding of the problem in polynomial time and vice versa.

I wanted to confirm from the respected community if my understanding is correct, or am I having a flaw in my understanding?

Also, If I am correct, CLRS states one more thing: "unary encodings are expensive". I want to know, what do the authors mean by that? Do they mean to say that representing 8 by 11111111 is costlier than representing 8 by 1000?


texts: How to prove NP-hardness of a longest-path problem?

texts:
I have this question:

Input:
G(V, E) = an undirected graph, V={v1, v2, ..., vn} (V = set of nodes, E = set of edges)
where there is a path connecting from v1 to vn.

Question:
What is the maximum number of nodes you can visit when starting from v1 and ending at vn.
(including v1 and vn)
Each node can only be visited at most once.

I want to prove that this is NP-hard by reducing it from a known NP-complete problem, such as undirected Hamiltonian path or subset-sum.

However I don't know exactly how to do this and this is where I need help.

Can anyone help please?


texts:
I'm attempting to formalize some thoughts I've had about paths into data structures. For example, a path into a list of Ts might be a pair of an index with a path into a T; a path into a pair (A, B) would be the tagged union of a path into A or a path into B. Think of a path as a way to specify some small (atomic?) piece of a larger data structure—not unlike a lens, but here I'm emphasizing the structural decomposition of a data type as opposed to an arbitrary computation that satisfies the lens laws (maybe every path is usable as a lens, but not every lens corresponds to a path).

Strictly speaking, my first example about lists of Ts is a little sloppy, since a path into such a list l should have its index bounded by the length of l. The pair (Nat, path T) is more properly a path into an infinite list of Ts—or, equivalently, a path into a function Nat -> T.

So my first interesting observation is that I have an operator that turns exponentials into products and products into sums in a way that's awfully reminiscent of logarithms:

path (T^Nat) = Nat * (path T)
path (A * B) = path A + path B

That got me thinking about whether there's an exp T type as well. Leaving aside all restraint and sense of rigor, the terms of the usual series expansion for $e^x$ offer a hint:

$$e^x = \sum_{n\ge0} \frac {x^n} {n!}$$

A type-theory interpretation of $\frac {x^n} {n!}$ might be a bag (as in multiset) of $x$s of size $n$ (it's an $n$-tuple $x^n$ but we don't care about the $n!$ ways the tuple can be ordered), so then a value of type $e^x$ would be a bag of $x$s of any size.

So if bag and path might be inverses, then that's saying something like, the type of all bags of paths into a type T, if it exists, is isomorphic to T. For example, there's an obvious isomorphism between (bag A) * (bag B) and bag (A + B) (an isomorphism that doesn't work if you replace bag with list or set or some other collection type, which reinforces my intuition that bag is the correct interpretation of $e^x$).

Of course, this is all appealing-sounding nonsense. I haven't even formally defined what a path is, never mind all the abuses involved in pretending the series expansion of $e^x$ is an algebraic data type. path may also be an idea of limited use, since it's not at all clear to me what to think about something like path (A + B) or path Bool. But has anyone made a more careful study of these ideas? Searching for "type theory" or "algebraic data types" along with "logarithms", "paths", "bags", "multisets", etc. hasn't yielded anything like what I'm attempting to describe here.


texts:
I'm trying to write a function in Python that takes it argument as a Python list and returns a boolean value based on the truth vale of the proposition $E(x) \to \exists y \text{ s.t. } x=2y$, where here the proposition $E(x)$ means 'x is even'.

print(check_prop([-2,-1,0,1,2,3])) gives an output true

print(check_prop([-2,-1,0,1,3,4])) gives an output false

I don't quite understand how the truth value is true in the first case and false in the second.


texts:
From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?

$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in M such that $x \le a$ and $y \le b$

Another related question: is any minimal set also minimum?

It is trivial to find a minimal set in $|S|^2$ time complexity.


texts: I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it says that $O(|V|\log|V|+|E|\log|V|) = O(|E|\log|V|)$, because $|V|=O(|E|)$. What does $|V|=O(|E|)$ mean and why is it so?


texts:
I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.

I don't want assistance with the answer, but i do need help understanding the last part of requirements - "so that each queue operation takes a constant (worst-case) number of stack operations".

Does this mean that, given such a queue with n elements and another with n+1 elements, the number of stack operations will be the same, when enqueueing or dequeueing either one?  What does "worst-case" mean when dealing with a queue?

Also, with a question like this, is it implied that queues are the only data-structures needed and one would not need to introduce any additional data structures to reach a solution?


texts: Finding the Hamiltonian cycle that uses the least amount of straight lines

texts:
How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)?
Here's an example we have devised for 8x8:

Here is an example we have devised for a 6x6:

And can this be applied to a grid of any dimensions (apart from non-hamiltonian grids)?


texts: Once taught, should I feed back the network's actual output into itself in an Echo State Network?

texts:
I’m trying to make an Echo State Network (ESN) in Python and althought I already read many articles about it, still there are many points I don’t understand.

(I had trouble putting 'ESN' in context to see what it actually is, but looking at PyBrain's feature list and the description of aureservoir I could classify ESN like this: 'Machine Learning' > Networks > Recurrent Networks (RNN) > Reservoir Computing > Echo State Network (ESN).)

I've attempted to write a very basic ESN in Python and I'm not sure if I got ESN right, thus I'm asking this question.

What I did was to fed a teach signal to it through a feedback weight matrix. From this, the output weight matrix could be calculated.

Once the output weights are ready, I try to run the echo state network again. But should I still provide signal through the feedback matrix?

How do the network run after it was taught? Without the teacher, does it need the previous output instead, as if the previous output were the teacher signal?

The network is similar to this image and first Wback is fed from the teacher signal and then an 'y' is created replaying the network's states with the teacher signal but through the now known Wout. But should I use this 'frozen' 'y' in the subsequent time steps, or do I send the actual output back to the units through Wback each time?


texts: Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?

texts:
From Bernhard Korte, Jens Vygen, Combinatorial Optimization,

  Instances of LINEAR PROGRAMMING are vectors and matrices. Since no
  strongly polynomial-time algorithm for LINEAR PROGRAMMING is known we
  have to restrict attention to rational instances when analyzing the
  running time of algorithms.

I was wondering why does the absence of strongly polynomial time algorithms for linear programming imply restriction to rational instances?


texts: Describing monitors and semaphores in terms of the three properties of critical section problem solutions

texts:
Solutions to the critical section problem exhibit three properties: mutual exclusion, progress, and bounded waiting. When do we say, or do we at least say, that operating system-implemented semaphores and monitors possess all these three properties?

An example would be bounded waiting on semaphores. In bounded semaphores there's a limit on the queue. When the queue is full, is it still safe to say that there is bounded waiting?


texts: What is the difference between Transitive Closure and Join?

texts: In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?