texts: How do I convert the following GNFA to regular expression?

texts:
Here is a GNFA I made from an NFA.

I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it in when I generate the regular expression?


texts: Polynomial Hierarchy --- polynomial time TM

texts:
Consider, for example, the definition for $\Sigma_2^p$ complexity class.

$$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$

where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some polynomial $p$. Here, $M$ must be polynomial time. But polynomial in the size of what exactly? For example, if we choose (guess) some $u_1$, do I consider it to be fixed size when talking about time complexity of $M$? More precisely, should $M$ be polynomial only in the size of $x$?

An example. Consider the problem whether, given a graph $A$, there exists a graph
$B$ such that $B$ is subgraph isomorphic to $A$.

$$A \in L \Leftrightarrow \exists B \; \text{SubGraphIsomorphic}(A, B) = 1 $$

Now, subgraph isomorphism is NP-complete. If $B$ is fixed, then there is a TM
that implements $\text{SubGraphIsomorphic}$ in deterministic polynomial time. If $B$ is not fixed, then I cannot claim such a thing unless I know $\sf P=NP$. Is this problem in $\Sigma_{1}^{p}$, i.e. $\sf NP$? (Ok, this problem has trivial solutions, but I hope it helps to pinpoint my confusion.)

My confusion generalizes for all $\Sigma_{i}^p$.


texts: Data structure for efficient searching, when insertions and removals are only one-sided

texts:
I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of magnitude larger than what is typically used.

Through my application I can ensure that:

Inserted elements are always newer than all existing elements, i.e., if an element associated with a time $\check{t}$ is inserted, then $\check{t}>t_i ∀ i ∈ {1,…,n}$. Elements are inserted one by one.
Only the oldest elements are removed, i.e., if element $j$ is removed, then $t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$. Removals happen mostly one by one, but there is no direct harm if an element’s removal is delayed, as long as the fraction of spuriously stored elements remains smaller than 1.
Apart from inserting and removing, the only thing I need to do is find the two neighbouring elements for some given time $\tilde{t}$ with $\min\limits_i t_i < \tilde{t} < \max\limits_{i} t_i$. With other words I need to find the two elements $j$ and $k$ such that $t_j<\tilde{t}<t_k$ and $∄ l ∈ \{1,…,n\}: t_j<t_l<t_k$.

My criteria for the data structure are:

Finding elements as described above should be as quick as possible.
Inserting and removing should be quick.
The data structure is comparably simple to implement.

As long as we are not talking about a small runtime offset, each criterion has priority over the next.

My research so far has yielded that the answer is likely some kind of self-balancing search tree, but I failed to find any information which of them is best for the case of one-sided inserting or deleting, and it will probably cost me a considerable time to find out myself.
Also, I only found incomplete information about how well the trees self-organise and how quickly (e.g., AVL trees self-organise more rigidly than red-black trees), let alone how this is affected by one-sided inserting or deleting.


texts: What's the point of Indirect Addressing?

texts:
Indirect addressing allows you to reference memory locations, larger than the operand limit of a CPU.

i.e

1 | ADD 2 3
2 | #2
3 | *32000
...
32000 | #5

This will add memory location 2 and 3, 3 points to location 32000, so when it's evaluated, the effect is:

1 | ADD 2 32000

Even though 32000 may exceed the operand size limit.

My question is, why do this?

Why not simple have this:

1 | ADD 2 3
2 | #2
3 | #5

It saves time wasted on extra references to memory and space in memory.


texts: How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?

texts:
PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program:
$$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \  R \ \text{END}$$
First $P$ is executed. Then $Q$ is executed until $x_0 \neq 0$. Finally $R$ is executed. I have to prove that PRE-WORK-POST is Turing complete and I have chosen to prove that I can simulate any WHILE program through a PRE-WORK-POST program. I'm stuck on one of the tasks. Given that $P1$ and $P2$ are both WHILE program, then $P1;P2$ is also a WHILE program (by definition). How can I simulate this using PRE-WORK-POST? I'm not really sure how I can do this since LOOP programs don't allow for nested loops.


texts: Function is recursive iff its graph is recursively enumerable

texts:
So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere.
But how to prove that function is recursive if and only if the language {x#f(x) |x∈(Г -{#})*)} (graph) is recursively enumerable?


texts: What is the computational cost of automatic differentiation compared to symbolic and numerical differentiation?

texts:
Automatic differentiation is a set of techniques to numerically evaluate the derivative of a function.

Quoting from Wikipedia (emphasis mine):

  These classical methods run into problems: symbolic differentiation leads to inefficient code (unless done carefully) and faces the difficulty of converting a computer program into a single expression, while numerical differentiation can introduce round-off errors in the discretization process and cancellation. Both classical methods have problems with calculating higher derivatives, where the complexity and errors increase. Finally, both classical methods are slow at computing the partial derivatives of a function with respect to many inputs, as is needed for gradient-based optimization algorithms. Automatic differentiation solves all of these problems, at the expense of introducing more software dependencies.

However, I haven't been able to find precise statements on the differences in computational cost.
While I understand that this will be somewhat dependent on the particular implementation, are there general statements that can be made about it?

In other words, are there general statements that can be made about the computational cost of estimating the derivative of a function numerically as opposed to using automatic differentiation techniques?


texts: How would one implement a Frequently Used algorithm?

texts:
The iOS emoji keyboard has a Frequently Used section. Notably, this is different from a Recently Used implementation - the data structure behind it is not an array of emoji where once you use an emoji it is inserted in the array (after first removing it if it already exists). But neither does it appear to be implemented as if it were titled Most Often Used - it doesn't appear to simply be sorting by the symbols you've used the highest number of times. There are more smarts to it. It seems the algorithm is taking into consideration how many times you've used each symbol, but also when it was used, and sorting it on some combination. For example I recently used an emoji just one time and yet it appears in my Frequently Used list towards the end but before other emojis that I know I've used multiple times in the past but haven't used very recently.

If one wished to recreate the iOS Frequently Used algorithm, how would one do so, what exactly does this algorithm do?


texts: Matching relative order in subsequence of fixed length

texts:
I encountered this problem from game development which I will formulate in a more formal way:

  Given a sequence $A = a_1, a_2, \dots, a_m$ and a permutation of $\{1, \dots, n\}$, $B = b_1, b_2, \dots b_n$, find all $i$ such that for all $1 \leq j \leq n$, $a_{i + j}$ is the $b_j$th smallest element of $a_{i + 1}, a_{i + 2}, \dots, a_{i + n}$.

Example:

$A = 6, 1, 3, 4, 5$
$B = 1, 2, 3$
$i = 1$: $1, 3, 4$ matches the relative order of $1, 2, 3$
$i = 2$: $3, 4, 5$ matches the relative order of $1, 2, 3$

The brute force approach consists of sorting each subsequence of length $n$ and comparing the sorted indices to $B$, and this is done $m - n + 1$ times, thus resulting in a time complexity of $\mathcal{O}(mn \log n)$.

I have only managed to improve this very slightly, by sorting only the first subsequence in $\mathcal{O}(n \log n)$ time and then removing $a_i$ and inserting $a_{i + n + 1}$ which both take $\mathcal{O}(n)$ time, resulting in a time complexity of $\mathcal{O}(n \log n + mn)$.

I do realise that my approaches are very rudimentary and there should exist a much more efficient algorithm that runs in less than $\mathcal{O}(m n)$ time. Unfortunately, I cannot think of any relevant algorithms that I know of, and searching online with how I described the problem have yet brought any useful resources.


texts: Can you solve 2-sat problem when truth assignments of some variables are determined

texts: I am trying to find a assignment to satisfy a 2-sat statement. Problem is some of the clauses are 0 or x or 1 or x. I think the 1 or x clauses have no effect on the solution, but the 0 or x clauses determine the value for x. As I have clauses like ~x or y the determined value for x results in determining the value for y and so on. Can I solve this problem with Krom's procedure?


texts: Can Shortest Job First Scheduling be subject to convoy effect?

texts:
Look at the below table for example :

Look at the Non-Preemptive SJF table
Suppose if the burst time of process $P_1$ was a very large number compared to $7$, the processes $P_3,P_2$ and $P_4$ have to wait for a large amount of time till $P_1$ frees the CPU. No book or article that I've read mentions of SJF being a subject to convoy effect? Why not?


texts:
I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias:
two counters are used, which count amounts of 1's and 0's in the stream and when the difference is above the threshold, the next bit out ot the rng is forced to either 0 or 1.
I have concerns about this. This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right? Is this a valid concern? If yes, what are proper ways to deal with bias in RNG?


texts: Is there anything like equivalence classes in PDA (and more expressive ones, perhaps)?

texts:
The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases.  However, obviously, DFA cannot describe arbitrary programs.

Perhaps DFA can be extended (w/o becoming fullblown PDA), while still having the property that it can be paritioned into equivalence classes?

This question is, in part, based on my reading of Model-Based Testing of Reactive Systems, which spends most of its time talking about DFAs.


texts:
My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding something like this:

The search "x OR y" will result in 105 000 hits, while a search for only x will result in 80 000 hits, and a search for only y will get 35 000 hits. Why does the search "x OR y" give 105 000 hits, when the combined individual searches gives 115 000 hits?

For me this sounded strange, so I tested this myself, using the words bacon and sandwich.

Only bacon yielded 179 000 000 results
Only sandwich yielded 312 000 000 results
bacon OR sandwich gave 491 000 000 results

But for me it adds up: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OR sandwich)

Why could an OR query result in fewer hits than both individual queries combined?


texts: NFA: If alphabet {0,1} is given, are you allowed to build a NFA with only 0?

texts:
Let's say there is the alphabet {0,1} given and you are supposed to build a NFA for language L= {w | w includes two successive zeroes}.

So we are supposed to build a NFA for the language which only accepts words with two (or more) successive zeroes, where alphabet is {0,1}.

Now my question, is it allowed to build a NFA which only includes zeroes and no 1's?


texts: How to create a cellular automata rule to achieve a desired pattern?

texts:
Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is exhaustive and computationaly intensive.

Is there a way to derive the rule that would generate the desired pattern?


texts: A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

texts:
I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'):
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.

The first direction is OK. But the other is not, namely:

What I don't understand is why the author assumed that M will halt. We have that A is Turing-recognizable, and thus we are not sure we have a machine that decides it (and thus halts). Same for the complement of A which is also Turing-recognizable.
Thanks in advance


texts: Minimum path - robot motion problem combined with freeze tag problem

texts:
Alright, I am not entirely sure if this is the right place to ask this, but here goes:

I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and it can wake up other robots on the map by walking next to them. Once a robot is woken up by another, it can also traverse the map and wake up other robots. The goal is to awaken all the robots using the minimum possible path.

Below I added an example of how a solution to a certain data set would look like.

I refrain from providing input/output files because I only want to ask for insights into and algorithm in pseudocode or even natural language, but if those would help I could add them as well!

Thank you very much in advance and should I provide any more info, do not hesitate to tell  me!

EDIT #1:
         In the example, both robot A and robot B can traverse the path to C and D. The different colors show that in this example, robot B traversed the path to C and D.
         There are no cases where the robots hull interferes with the obstacles. The 'hull' can touch the obstacles. All robots have the same specifications.
         By minimum path I am trying to refer to the shortest time to wake up all the robots (i.e. time elapsed from when the first robot starts up until all robots are woken up).


texts: What strategies exist for handling/resolving ambiguity in parsers?

texts:
I define a parser as a context-free grammar with semantic actions for each production. It is not defined in what order the semantic actions run, just that the semantic actions of the non-terminals in a production run before itself does.

E.g. a (very) simple arithmetic language:

S -> E        { print(nt[0]) }
E -> E '+' P  { nt[0] + nt[1] }
E -> P        { nt[0] }
P -> P '*' X  { nt[0] * nt[1] }
P -> X        { nt[0] }
X -> N '^' X  { nt[0] ^ nt[1] }
X -> N        { nt[0] }
N -> N D      { 10*nt[0] + nt[1] }
N -> D        { nt[0] }
D -> '0'      { 0 }
...
D -> '9'      { 9 }

The concept of semantic actions are (to me) a clear way of turning a grammar into an actionable concept that explains that while two grammars might define the same language, they might not be equivalent.

This is why deterministic parsing (e.g. LL(1) or LR(1)) is unattractive to me, as you end up massaging your grammar to the wishes of the parser generator you're using.

As an example, if you use an unrestricted parser such as an Earley parser you can forget about having to massage your grammar into the requirements of whatever parser generator you're using and instead use the full behavior of the grammar. E -> E '+' P is left-associative and X -> N '^' X is right-associative, something that you can only express as such if you can use both right and left recursion.

However, if you give up deterministic parsing then CFGs can be ambiguous, so the above concept is still incomplete to me. Some people are interested in all ambiguous parses (e.g. natural language), but I am interested in augmenting a CFG parser as above in a way that resolves ambiguity.

What methods and techniques exist for augmenting an ambiguous grammar with additional info (which might already exist, e.g. the order in which productions are defined) or routines that allow ambiguous parses to be resolved/clarified to a unique unambiguous parse?


texts: Removing epsilon transition from context-free grammar

texts:
I have the following context-free grammar from which I have to remove epsilon transitions:

$S \to 0A0|0$

$A \to BC|2| CCC$

$B \to 1C | 3D | \epsilon$

$C \to AA3 | \epsilon$

$D \to AAB | 2$

By algorithm, I create $N_{0}$ that will hold all non-terminals that contain $\epsilon$ and in next steps add non-terminals that have rule that contains only non-terminals from the previous iteration of N e.g.

$N_{0} = \{\}$
$N_{1} = \{B,C\}$
$N_{2} = \{B,C,A\}$
$N_{3} = \{B,C,A,D,S\}$

Now I have to adjust rules, we can remove non-terminals in $N_{3}$ object from rules, thus we have to create all combinations without it e.g.

$S \to 0A0 | 00 | 0$

$A \to BC | B | C | CCC | CC$

$B \to 1C | 1 | 3D | 3$

$C \to AA3| A3 | 3$

$D \to AAB | AA | A | AB | B | 2$

We see that no non-terminal isn't useless, so is this the final context-free grammar? Or did I make mistake somewhere?

Thanks for answers and help.


texts: Sorting n weight disks with decision tree

texts:
I was refreshing some old tests about sorting algorithms, there was a question as follow:

Question: we have n weight disks with different weights and we want to sort them pair by pair, How many times we have to weight in worst case (maximum comparisons) to sort the whole disks?

the answer was $ \lceil \log n! \rceil $.

My issue is that I could not get to the answer and could anyone elaborate on how the answer is working?

Also one of the options was $ \lceil n\log n \rceil $, and as we know,
the order of $\log n!$ and $n\log n$ are same, So why shouldn't the
ceilings be equal too?

and How does having an ordered and distinct set of size n, matter in decision tree?


texts: How is a hypergraph different from a bipartite graph?

texts:
How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the original hyperedge. Alternatively, I could also start with a bipartite graph, designate one of the sets of vertices as the hyperedges, and connect these hyperedges with the vertices connected to the original vertices.

Is there anything wrong with this construction? Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?

I haven't read in detail what vzn is proposing here, but this got me interested in the question whether hypergraphs are really non-trivial generalizations of graphs. I googled for hypergraphs (and Wikipedia indeed also described the construction given above) and searched stackexchange and mathoverflow, but somehow hypergraphs are always treated as a non-trivial generalization of graphs, and somehow considered to be much more complicated than graphs. Don't read too much into this question, I have neither done an excessive literature research nor thought too deeply about hypergraphs. (Perhaps I even accidentally searched for multigraph instead of hypergraph, but I don't think so.)


texts: Connection between Pseudo random generators and hardness

texts:
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$.
According to Nisan Wigderson 1988, I know that if there exists $f\in E$ with $H_{avg}(f)\geq S(n)$ then there is a $S'(l)$-Prg where $S'(l)=S(n)^{0.01}$. For any general $S(l)$, a Pseudo-random generator, is called an $(S(l),\epsilon)$-Prg if for circuit family $C_{S(l)}$ of size $S(l)$ $|Pr_{x\in U_{l}}[C_{S(l)}(G(x))=1]-Pr_{x\in U_{S(l)}}[C_{S(l)}(x)=1]|<\epsilon$. Here $G$ is a pseudo random function $G:\{0,1\}^l\longrightarrow\{0,1\}^{S(l)}$, generates an $S(l)$ length strings from length $l$.
I was thinking if the converse is also true or not. Means, if we can show the existence of $S(l)$-Prg, then does it follows that there is $f$ with $H_{avg}(f)\geq S(n)$?


texts: What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?

texts:
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
In the post linked above, the user "plop" gives a great response where they claim, in particular, that a plane graph $G$ has a well-defined geometric dual. Paraphrasing, for any two drawings $G^*_1$ and $G^*_2$ obtained in the following way, there exists a unique planar graph $Y$, up to isomorphism, such that the plane graphs $G_1^*$ and $G_2^*$ are planar embeddings of $Y$. Consequently, we may write $G^*$ for either $G_1^*$ or $G_2^*$, and call it the geometric dual of $G$.
To obtain such a plane graph $G^*$ from $G$, draw a point in$^\dagger$ each face of $G$, and for each arc $e$ of $G$, draw a new arc passing once through $e$ connecting the points in the two faces $f_1$ and $f_2$ incident with $e$. Do this such that no two of these new arcs intersect.$^{\dagger\dagger}$ This new set of points together with this new set of arcs describes the plane graph $G^*$.
$^\dagger$To make complete sense of this construction, one needs at least the Jordan Curve Theorem, and according to "plop" also needs the Jordan-Shoenflies Theorem.
$^{\dagger\dagger}$By the way, shouldn't this also require us to use the fact that a topological subspace of $\mathbb R^2$ (or of $S^2$) is connected if and only if it is path-connected? (Otherwise I could imagine two curves technically not intersecting but with something pathological happening where the curves get arbitrarily close to each other and end up "crossing" while still being curves in the sense that they are topological embeddings of $[0,1]$. This is a little beside the point.)
I am ok with the above claim. My question is:
Does there exist a planar graph $X$ with two planar embeddings $G_1$ and $G_2$ such that $G_1^*$ and $G_2^*$ are the planar embeddings of nonisomorphic graphs $Y_1$ and $Y_2$? If so, what's an example construction. If not, why not?
Note: Wikipedia claims seems to claim that the answer is "yes", but doesn't provide an example. I put a [citation needed] tag, so maybe once this is resolved, we can link it back to here.

The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

https://en.wikipedia.org/wiki/Dual_graph


texts: criterion for two line segments intersecting

texts:
I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect.

My current algorithm tries the following:

the line $[(x_1, y_1),(x_2, y_2)] $ is determined by
$\boxed{f(x,y) = \frac{y - y_1}{x - x_1} - \frac{y_2 - y_1}{x_2 - x_1}  = 0}$.
I reasoned that if $y = mx+b$ is my line, I want a point such that $y > mx+b$ and one such that $y < mx+b$.
I want to check if that $f(x,y)$ has opposite signs if I set it on $(x_3,y_3)$ and $(x_4, y_4)$.  So the criterion I check right now is:
$$ \frac{f(x_3,y_3)}{|f(x_3,y_3)|}\;
\frac{f(x_4,y_4)}{|f(x_4,y_4)|} = -1
$$
Unfortunately in my visualization, I still see line segments intersecting.

Is there something wrong with my algorithm?  What is a correct way to check that two line segments intersect?


texts: Turing machine with k-tape, tape of output

texts:
Consider a Turing machine with input alphabet $\{a,b\}$ that computes the following function:

$$
f(w, v) =
\begin{cases}
w & \text{if } \operatorname{length}(w) > \operatorname{length}(v), \\
v & \text{otherwise}.
\end{cases}
$$

I wish to use a TM with two tapes, the first of which contains the input string, say encoded as $*w*v*$. I'm not sure, having read several books, which tape is the output tape in this case. For example, the output tape for a TM of two tapes is the input tape or the second tape? If I use three tapes, is it correct that one of them contains the input, another is a working tape, and the third is the output tape?


texts: How can a set of N players be split into M teams, given certain rules?

texts:
A lot of times, I’ve needed to split a given set of people into a given number of teams but with some complications, like:

Alice and Bob CANNOT be on the same team.
Carol and David just HAVE TO BE on the same team.

I feel like this is already a thing. There's gotta already be work in this problem. Where would I even start, in terms of an algorithm? It definitely can't be brute-forced.


texts: What Do Logical Operators In a Grammar Mean?

texts:
Is there a way to figure out what the following CFG accepts?

$\qquad\begin{align}
  S &\to S \vee T \mid T \\
  T &\to T \wedge F \mid F \\
  F &\to p \mid\; \thicksim p
\end{align}$

I'm confused by the boolean algebra symbols. I know the first is S or T, the second is T and F and the third is not p but I'm not sure how they affect the grammar itself.


texts: For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?


texts:
Given that this wave was sampled at a sampling frequency f:

Why does the wave sampled at a sampling frequency 3f/2 look like this?

What does 3f/2 mean? Does it mean that we sample every 2 waves 3 times?


texts: Calculating Time Complexity of Algorithm Using Incrementor Variable

texts:
I am trying to calculate the time complexity of an algorithm using n in the code below.

I have a working solution to a coding challenge to sort a stack using only another stack, and I've added a counter variable n that is incremented anywhere an element in the stack is pushed, popped, or held.

The following code is written in JavaScript:

const sortStack = (stack) => {
  let n = 0;
  sorted = new Stack();
  while (stack.storage.length) {
    tmp = stack.pop();
    n += 1;
    if (tmp >= sorted.peek()) {
      sorted.push(tmp);
      n += 1;
    } else {
      while (tmp < sorted.peek()) {
        stack.push(sorted.pop());
        n += 1;
      }
      sorted.push(tmp);
      n += 1;
    }
  }
  console.log("n: ", n);
  return sorted;
}

sortedStack = sortStack(s);
sortedStack.printContents();

If my calculations and usage of n are correct, then this algorithm has an input n of 6 (length of stack) with a final n of 30, which would give it a time complexity of O(N*5).

Is this correct?


texts: Two definitions of balanced binary trees

texts:
I have seen two definitions of balanced binary trees, which look different to me.

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

Does every tree that satisfies def. 1 also satisfy def. 2? What about the other way round?


texts:
What are the theoretical limitations that avoid the adoption of type polymorphism à la System F in current SMT solvers?
I work in the context of program verification and I am surprised by the great cost of not supporting polymorphism automatically. For instance, I cannot have polymorphic annotations because these are rejected by the solvers and have a very costly encoding. But these annotations are very handy especially in dealing with annotations of polymorphic functions.


texts: How many neurons is needed for UAT to hold?

texts:
The universal approximation theorem states that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of Rn, under mild assumptions on the activation function.

How many neurons is needed? For a function in 3 variables and one output.
And how many adjustable parameters does that give in the neural network?


texts:
A man has to travel for given number of days by bus.
He can buy either:

$1$ day ticket for $2Rs$ (valid for 1 day)
$7$ days ticket for $7Rs$ (valid for 7 consecutive days)
$30$ days ticket for $25Rs$ (valid for 30 consecutive days)

We are given an array, whose elements are the day numbers on which he travels.

For example, if the given array is
$\{1,3,5,8,9,10\}$, then he travels on these $6$ days. Now we have to minimize the cost of  his travel.
What would be the best approach to solve this problem?


texts: What's the difference between Row Polymorphism and Structural Typing?

texts:
The definitions I've stumbled across seem to indicate they express the same idea. That's that the relationship between record types is determined by their fields (or properties) rather than their names. Their Wikipedia pages also seem to indicate the same idea:

A structural type system (or property-based type system) is a major class of type system in which type compatibility and equivalence are determined by the type's actual structure or definition and not by other characteristics such as its name or place of declaration.

In programming language type theory, row polymorphism is a kind of polymorphism that allows one to write programs that are polymorphic on record field types (also known as rows, hence row polymorphism).

Are there any differences between them?


texts: Sending infinite frames in One-Bit Sliding WIndow Protocol?

texts:
I am reading Computer Networks by Andrew S. Tanenbaum and I wonder if there is a mistake in the protocol as I can't find any solution for the following scenario.

Suppose the transmitter (A) has only one frame (X) to send, and the receiver (B) has nothing to send. B receives X and sends a frame with an empty info field and with an acknowledgement from X to A. But with A, this triggers the event frame_arrival, which in turn triggers A to send an "acknowledgement" to B, again without any packet (because there was only one). And so that ping-pong of totally useless frames goes on and on. Is that an error in the protocol, in the pseudocode of the protocol, or am I wrong?

I suppose that sequence number frame_expected of A will not agree with the second acknowledgement of B.


texts: Brute Force Approach for LCS and its Time Complexity

texts:
I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am applying my brute force technique it's taking O(mn) (from my personal observation).
I would like to request you please read my approach clearly and visualize in mind and ask question for further clarification if needed.
My Approach is following:- Say we have two strings s1 = "ECDGI" , s2 = "ABCDEFGHIJ".
Now what I am doing is I chose either one of the given strings. For say, s1.
for i = 1 to n (n is the last index of s1), I am taking each value and comparing with the s2 in such a way that for a single character of s1 I am checking with all the characters of s2. Mathematically, ith value is checking through all jth value up to m (m is the last index of s2). Here, if I find any common character I just move to next character from both strings. Then just compute subsequence. I compute all the possible subsequence for each characters from s1 by running n loops. Finally, I compute the largest value.
From my understanding it's taking O(mn) time complexity overall.
So My Question is, " Is my Time Complexity Calculation right ? "

Trace :

i = 1, value = E, lcs = 3 [EGI]

i = 2, value = C, lcs = 4 [CDGI]

i = 3, value = D, lcs = 3 [DGI]

i = 4, value = G, lcs = 2 [GI]

i = 5, value = I, lcs = 1 [I]

Answer is = 4 (maximum lcs)


texts: Densely connected non overlapping subgraph

texts:
I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster.

I'm currently trying to detect community using Louvain algorithm, but it detects subgraphs with a low clustering coefficient (0.60) and when I detect maximal or quasi cliques they tend to overlap.

How can I compute a clique decomposition of an undirected graph with no overlap between clusters ?
Is there an algorithm with an implementation of it which can deal with my problem ?

Thanks


texts: Reducing co-NP and NP. (Karp and Turing)

texts: Why is it true that: If every problem in co-NP can be Karp reduced to a problem A, every problem in NP can be Turing reduced to A?


texts: while loop for bitwise conversion program

texts:
int counter(char c){
    int count = 0;
    while (c!=0){
       if((c & 1) !=0)
         count++;
       c = c >> 1;
}
}

I am trying to understand a program that counts the number of 1s in the binary representation of the input character. While I understand the & part and the count part, I don't get why we're checking for c!=0 in the while loop. I know each character is 8 bits. For instance, if the input character is "2" then the binary representation is 10. The count will be 1. So we start by checking the first binary number "1". Then we shift by 1 and it becomes 01? So then do we check 1 again? Or do we check 0? But if we check 0 then does the while loop not run at all?
An example of the steps would be really helpful.


texts: Rounding errors when converting floats to integers

texts: Is it possible to have a rounding error when you convert a floating point number which can only be in increments of 0.01 to an integer by multiplying by 100 first?  I would think that the lack of precision in representing floating point numbers is so small that it would never cause a rounding error when you only have to worry about 0.01 increments.


texts: What is your approach to unveil the boundary cases when designing an algorithm?

texts:
When designing an algorithm for a given problem, sometimes I find it hard to foresee or clarify to myself what the boundary/edge/corner cases are. Not being able to come up with a decent number of the possible boundary/edge/corner cases causes one to make implicit assumptions about the problem at hand, which yields overlooked cases not to be accounted for, which is not good.

When reviewing the classic "Programming Challenges" by Steven S. Skiena and Miguel Revilla, one can read the following:

  This is why it is so essential to review the specifications carefully. Even when you may be sure that your program is correct, the judge may keep saying no. Perhaps you are overlooking a boundary case or assuming something which just ain’t so. Resubmitting the program without change does you absolutely no good. Read the problem again to make sure it says what you thought it did.

I think it would be useful to sort come up with a method to, given a problem statement and the problem's input domain, assist the algorithm designer with unveiling boundary cases.

On one hand, knowing the upper and lower boundaries of your input data, helps you choose data types that can represent said values.

Another useful technique I do, is to ask myself, per each explicit assumption I can extract from the problem specification, what must exist for that assumption to be valid? For example, if I am told that all values will be given as a sorted array, does that mean that the given list will never be empty?

I would like to continue putting together a set of thumb rules to assist ourselves in uncovering boundary cases.


texts: Why do we not combine random number generators?

texts:
There are many applications where a pseudo random number generator is used.  So people implement one that they think is great only to find later that it's flawed.  Something like this happened with the Javascript random number generator recently.  RandU much earlier too.  There are also issues of inappropriate initial seeding for something like the Twister.

I cannot find examples of anyone combining two or more families of generators with the usual xor operator. If there is sufficient computer power to run things like java.SecureRandom or Twister implementations, why do people not combine them?  ISAAC xor XORShift xor RandU should be a fairly good example, and where you can see the weakness of a single generator being mitigated by the others.  It should also help with the distribution of numbers into higher dimensions as the intrinsic algorithms are totally different.  Is there some fundamental principle that they shouldn't be combined?

If you were to build a true random number generator, people would probably advise that you combine two or more sources of entropy.  Is my example different?

I'm excluding the common example of several linear feedback shift registers working together as they're from the same family.


texts:
I understand that computer memory in typical modern computing systems (such as the laptop I am asking this question from) is generally involatile but in some exceptions, such as RAM, the memory is indeed volatile.
Is RAM always volatile? Isn't there any "exceptional" kind of involatile RAM by humans somewhere?


texts: Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

texts:
Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O.

My idea is that since $B$ is usually much smaller than $M$ we can have

$O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{N}{M}\right) = O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{NB}{MB}\right)$

so $\frac{B}{M} <1$

but I'm new to complexity theory so I'm not sure if it's the correct reasoning.


texts: Difference between methods of converting from finite state machine to regular expression

texts:
I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:

q1(a)=q1
q1(b)=q2
q2(a)=q2
q2(b)=q3
qf3(a)=qf3
qf3(b)=qf3

My professor using a method

r(p,q,k+1)=r(p,q,k)|r(p,k+1,k)r(k+1,k+1,k)*r(k+1,q,k)

and he start from (1,3,3). He get r(1,3,3)=a*ba*b|(a|b)*, I understand that method but if a finite state machine is more complicated then it takes to much time, so I saw on internet and I saw here a method where I start like this

q1=epsilon+q1a, q1=a*
q2=q1b+q2a, q2=a*ba*
q3=q2b+q3a+q3b, q3=a*ba*b(a+b)*,q3=a*ba*b(a|b)*

Both regular expression look similar but I do not know is that the same? Can you tell me where is difference if difference exist?


texts: Conditions for a binary tree being balanced

texts:
Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.
If you disprove, the counterexample should consist of an infinite sequence of trees in the family rather than just a single tree, because the property is asymptotic.
A. There is a constant $c$ so that for each node of the tree, the difference in height between the two sub-trees is at most $c$.
B. There is constant $c$ so that the average height of each node in the tree is at most $c \log n$.

Now I proved A using induction, and I know how to disprove B using a single example, but I don't know how to do so using infinitely many examples.


texts: Isomorphism of a DFA and the minimal DFA

texts:
I have a DFA A, I minimize A and the minimized DFA obtained is M.
My question is if in general A and M are isomorphic?


texts: Repeated addition and comparisons of floating point numbers

texts:
In the following program where I repeatedly half an integer, it takes until i = 1074 for my integer to be equal to zero (I know that ideally the while loop shouldn't have ended, and the reason why it stopped was because of the memory limit of the computer).

a = 1.0
i = 0
while a != 0:
    a = a / 2
    i = i + 1
    print(a, i)

However, the next program, where I compare the halved integer using addition ends at i = 53.

a = 1.0
b = 1.0
i = 0
while a + b != b:
    a = a / 2
    i = i + 1
    print(a, i)

My question is why is there a big difference here?   Why does the first program go up to 1075 iterations, while the latter goes up to 53?

Also, when I tried a + b + c != b + c, it went up to just 52, furthermore

a + b + c + d != b + c + d

only went up to 51.  Why isn't there a big difference here?


texts:
Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions:

by the end of each day, you cannot be in the middle of a chapter.
You must read the chapters in order.

You also want to minimize the maximum number of pages read in a single day.

Now let's consider the brute force algorithm: look at every possible way of dividing the chapters into $d$ days, and compute the maximum number of pages read in a single day. There are $\binom{n+d-1}{n}$ ways to divide the chapters up (using stars and bars) and you must check the number of pages read in each day, ultimately by doing $n$ operations. So this algorithm takes $O\left(n\binom{n+d-1}n\right)$ time, which is pretty bad, but I can't think of how to improve it.

Imagine an analogous decision problem:

  Given a book with $n$ chapters, is it possible to read it in $d$ days such that you never read more than $k$ pages in a single day without violating the restrictions?

The decision problem seems to have a really easy greedy solution: Each day, read as many chapters as you can without exceeding $k$ pages. If you're done with the book after $d$ days, the answer is yes. Otherwise, the answer is no. This takes $O(n)$ time.

It seems weird that the decision problem would have such a simple solution but the original one doesn't. Can anyone think of how to do better than the brute force algorithm for the original problem?


texts: Hardness of a problem related to set cover

texts:
Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times in this subcollection.

If $k=1$, this is set cover. I would be interested to learn how to prove NP-hardness for $k=2$ and $k=3$.


texts: Are there Some Pairs Shortest Paths Algorithms?

texts:
I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes.

The properties of the graph are:

sparse
directed
positive arc weights
cycle-free
the subset of vertexes I am interested in is 1/14 of |V|

Currently I am solving this problem with johnsons APSP algorithm but I am interested if there are more efficient ways.

Keywords for further research or suggestions are welcome.


texts: theoretic possibility of building hardware exactly equal to any software

texts:
Is it possible in theory to build hardware with exactly same computing logic as any computer program? Or in other words: Is it possible in theory to implement any software in hardware?

That's my thoughts: if computers in general is finite automata so the software what is a product of computer is in general finite automata. So there is no principal difference beetween them. That's mean it is possible.

My questions are:

Is it possible or not?
If it is possible, am I correct with explanation?


texts: Compression of non-adjacent structure using grammar

texts:
I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string and use recursive substitution with non-terminal symbols to achieve compression.

What I'm wondering is whether there are classes of grammar and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence.

Take the following input sequence:

  XaXbXcYaYbYcZaZbZc

No two adjacent symbols co-occur more than once anywhere here, so the sequential compression techniques I mention will not compress this string any further, however there is a clear pattern to the sequence and it must be compressible. How is it possible to do so?


texts: Usual distances on DFAs (Deterministic Finite Automata)?

texts:
I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma.

Since the languages they describe (regular languages) can potentially have an infinite size, defining a distance is not a trivial matter.

Nevertheless, having a distance on these objects can be useful, in order to fit these in metric spaces, which allows for a range of things (in my case to assess the performance of an algorithm).

My only consistent idea so far is to create a distance similar to the edit-distance in labeled graphs on the minimized DFAs.

Does someone have ever heard of other distances ?


texts: Constraint Satisfaction: maximizing total value with no overlaps

texts:
Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value.

Out of all the bars available, we want to choose the set which maximizes the total value but with no overlap between the start points and end points of the bars. In the example above, the selected bars would be the following (in red):

What would be the best way to approach this problem computationally, for n number of bars being potentially large (several thousands) and [x,y] the possible bar positions being large as well?

I thought of a probabilistic approach, but are there deterministic approaches as well?


texts: Constructing inequivalent binary matrices

texts:
I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and j row AND the i and j column. eg. for $1\leftrightarrow2$
\begin{equation}
\left( \begin{array}{ccc}
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \end{array} \right) \sim
\left( \begin{array}{ccc}
1 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 \end{array} \right)
\end{equation}

Eventually, I will also need to count how many equivalent matrices there are within each class but I think Polya's counting theorem can do that. For now I just need an algoritmic way of constructing one matrix in each inequivalence class. Any ideas?


texts: Is there any way to combine multiple Hidden Markov Models trained from different sets of data? For example, I want to detect the phases of a sequential activity. I collect two sets of data by using two types of sensors: accelerometer, and video stream. I create two HMM models from the accelerometer and video stream, respectively. To increate accuracy, can I combine the two models?


texts: Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

texts:
I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language):

# set up vars & their domains
x_1 {1}
x_2 {0,1}
x_3 {0}
x_4 {0,1}
# constraints
(x_1 != x_2)
(x_2 = x_3)
(x_3 = x_4)
(x_1 != x_4)
(x_2 = x_4)

The objective is then to choose values from the domains of each variable so as to maximize the number of constraints satisfied.

More generally, in all of my instances, we have a fixed value of $k$. The domain of each variable is of size at most $k$. Every constraint involves two variables, and is an inequality or an equality constraint.

  When CSPs are studied from a theoretical viewpoint, is there a model that captures the above in a straightforward way?


texts: Validity of self refering state with linear temporal logic 'X' connective

texts:
Lets say we have model like the one above or a similar one where a node refers back to itself.

Now let's say if I want to know the validity of the formula:

$M, s_2 \models Xr$

Will this be valid or not. In my textbook it says :

$\pi \models X\phi$  iff $\pi^2 \models \phi$

If we are starting at state 2 then our path would be $S_2 -> S_2 ->  ...$

So, I'm not sure since state 2 is not actually transitioning to another states like State 0 or 1. Otherwise would transitioning to the same state in a path $\pi$ be enough to satisfy the "X" connective.


texts:
I hope this question is close enough to CS to be posted here. I need to write a method that will compute the perimeter of a simplex
https://en.wikipedia.org/wiki/Simplex in any dimension given only the coordinates of its vertices. Is such a function even possible? I have tried going for it, but ended up with loads of nested loops and nothing functional. Right now I have a class named Point and a class named Simplex which constructs a Simplex from an array of these points. Any help is appreciated.


texts: Will such an algorithm be feasible, will it be considered a poly time algorithm?

texts:
Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in  the worst case,
$O(p\mathrm{log}(p))$,
will it be counted as a poly time algorithm ? Or since $(p\mathrm{log}(p))$ is basically the logarithm of an exponent so it will inefficient. And such an algorithm will be infeasible or intractable.
Secondly what if we can cut down the complexity in the worst case scenario to,
$O(p\mathrm{log}(p)/5)/100 )$?

Will this complexity be considered same as the worst-case complexity?


texts: How is $\text{PCP}[O(\log n),O(1)]$ NOT P?

texts:
As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.

For $\text{PCP}[O(\log n),O(1)]$, won't there just be polynomial many possible routes, and checking all just cost polynomial time?

  In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.


texts: Equivalence of data-flow analysis, abstract interpretation and type inference?

texts:
@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of running the inference algorithm) of data-flow analysis, abstract interpretation, and type inference.

In some sub-cases (like between forward context-sensitive interprocedural data-flow analysis and abstract interpretation) the equivalence is relatively obvious to me, but the question seems more subtle for other comparisons.  For example, I can't figure out how Hindley-Milner type inference could be used to prove some of the properties that can be proved with flow-sensitive data-flow analysis.

What are the seminal references discussing the equivalences (or differences) between data-flow analysis, abstract interpretation and type inference?


texts: Multiprocessor Scheduling is NP-Complete

texts:
Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m disjoint subsets,  $A = A_1 \cup A_2 \cup \ldots \cup A_m$ such that we have:
$$
max \left\{ \sum _{a \in A_i} l(a): 1 \le i \le m \right\} \le D ?
$$

My attempt(Also hint from Garey & Johnson)
consider $m = 2$ and $D = \frac{1}{2} \sum _{a \in A} l(a)$. if so we have
$$
max \left\{ \sum _{a \in A_1} l(a), \sum _{a \in A_2} l(a) \right\} \le  \frac{1}{2} \sum _{a \in A} l(a) ?
$$

this implies that we should have $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$ and also $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$**(if we have such a partition!)**, otherwise we will have a contradiction because if for example $max$ was $\sum _{a \in A_1} l(a)$ we had $$
\sum _{a \in A_1} l(a)<  \frac{1}{2} \sum _{a \in A} l(a) \\
\sum _{a \in A_2} l(a)<  \frac{1}{2} \sum _{a \in A} l(a)
$$
and if we sum the last two inequalities we get this contradiction:
$$
\sum _{a \in A} l(a) < \sum _{a \in A} l(a)
$$

so now we know that they are equal, and we see that our problem is now an instance of partition(or subset sum with sum equal $B/2$ where $B$ is sum of all elements of A) and we know that partition is $NPC$ so our main problem is $NPC$ too by restriction.

Is my argument correct??


texts: How do I show T(n) = 2T(n-1) + k is O(2^n)?

texts:
This is a practice problem I've come up with in order to study for an exam I have in a couple of hours.

Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant.

First of all, 2^n is indeed the upperbound, right? Since I've made this problem up myself, I'm not 100% sure, but from what I have seen, this should be O(2^n).

If so, here's my progress:

We want to show P(n) is true for all n > n0, where P(n) is the statement "T(n) <= c * 2^n" (for some fixed c, to be determined)

For now, let's fix c at T(1).

Base case: n = 1

We want to show T(1) <= c * 2. Since c = T(1), our equation becomes T(1) <= T(1) * 2, which is trivially true.

Inductive step: Assume P(n - 1) is true for n > 1. We want to show that P(n) holds.

T(n) = 2 T(n - 1) + k, by definition
    >= 2 (c * 2^(n-1) ) + k = c * 2^n + k

Here's where I get stuck. How can we possibly show that c * 2^n + k <= c * 2^n for any value of c? Did I make a mistake somewhere?


texts: Finding smallest canonical cover from given set of functional dependencies

texts:
I did not find any book discussing this but I came across the problem. The given set of FD was:

$F=\{B\rightarrow A,D\rightarrow AC,B\rightarrow C,AB\rightarrow D,BC\rightarrow D\}$

Surprisingly the answer given was

$F_{min}=\{B\rightarrow D,D\rightarrow A,D\rightarrow C\}$

$B\rightarrow D$ wasnt present directly in the given FD set. So I realised I must be finding attribute closures first:

$A^+=A$
$B^+=BACD$
$C^+=C$
$D^+=ACD$

The non trivial ones are:

$B^+=ACD$

$D^+=AC$

Its easy from these that the smallest FD set would be $F_{min}=\{B\rightarrow D,D\rightarrow A,D\rightarrow C\}$. However the final non trivial attribute closure set was small and had easy pattern to deduce the smallest canonical cover. I was just guessing what if final non trivial attribute closure was more involved and did not contained any easy pattern, how would I have deduced the smallest canonical cover. Can anyone see any simple set of concrete steps for this?


texts: How to find unambiguous grammar for palindromes

texts:
I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.

S -> a S a
   | b S b
   | a
   | b
   | ε

Is there a way to convert this to an unambiguous grammar? Or is there another solution?


texts: Setting a cutoff for string distance filtering with different length strings

texts:
I'm working to filter a table of pairwise names (1.1 M rows) based on string distance algorithms. Most are names, though some are businesses.

Edit-based algorithms seem to be best, however in attempting to set a cutoff value for match vs. non-match, there is an issue with the length of the string.  In a 16 character string, a score of 4 is usually a good match.  But of course in a 4 character string, a score of 4 is a complete non-match.

What are good options for using a string distance algorithm, but scaling the scores relative to the length of the comparison strings? This doesn't seem to be built into any of the algorithms I've found.


texts: Dynamic programming: maximize the number of things to be bought

texts:
For example, for a product, we have a list of the number of products you buy and the corresponding price you pay with this number of products:

number = {1, 5, 8, 12}

price = {0.5, 2, 3, 3.6} (i.e. you pay 0.5 for 1 product, 2 for 5 products and so on)

Now I need to use a fixed number of dollars to buy as many number of products as possible. How do I do this using dynamic programming?

I understand how I minimize the cost if I have a fixed number of products I want to buy. But for a fixed amount of money, I get confused, since the price is of type double, I cannot do this with indexing the an array with the prices.


texts: Learn feature value range for a classification

texts:
Which domain does this problem belong to?

Given a set of products some are classified as cheap and some not. The task is to determine the price range (probabilistic) for cheap products.
Supervised classifiers arrive at a function and can classify a new instance but does not provide the range of feature values. This seems like a pattern recognition problem but I am not able to get which class of problems it belongs to.

There might be hundreds of features of the products (price being one of them) and the ask is to identify a profile of products (the range of values for various features) which are mostly classified as cheap. Could this be a rule mining problem?


texts:
I am a software engineer and after a discussion with some colleagues, I realized I do not have a good grasp of the concept serialization. As I understand, serialization is the process of converting some entity, such as an object in OOP, to a sequence of bytes, so that the said entity can be stored or transmitted for subsequent access (the process of "deserialization").

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?


texts:
I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps. I know that min-heaps generally support decrease-key. I was able to write the increase-key operation for a binary min-heap, wherein, I exchange increased key with the least child recursively. In the case of the Fibonacci heap, In this reference, they say that the Fibonacci heap also supports an increase-key operation. But, I couldn't find anything about it in the original paper on Fibonacci Heaps, nor could I find anything in CLRS (Introduction to Algorithms by Cormen).

Can someone tell me how I can go about implementing the increase-key operation efficiently and also without disturbing the data structure's amortized bounds for all the other operations?


texts: Find subgraphs that can only be reached by two nodes

texts: I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only connected to each other and A and F (don't have to be fully connected). Is there a name for this? And is there an algorithm for finding such subgraphs? The distance of A and F is defined by their shortest path: for example, if d=4, I would want to find all subgraphs where the shortest path between A-like and F-like nodes is at most 4.


texts: Determine endpoint of a graph given as a list of nodes + direct successors and predecessors

texts:
EDIT @20190313

I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and every node stores a list of adjacent nodes, its direct successors and predecessors. The graph is in fact highly non weakly-connected, in the sense that the number of its weakly-connected components is quite big. I must everyday find the weakly-connected components of the graph and determine sink nodes of every weakly-connected components, and know from one day to the next any new sink node for every weakly-connected components. (From one day to the next, only new sink nodes might be added, with their associated edges.)

I fix a type T once for all. (Concretely, T is a c# class, but that doesn't matter.) On T I have the notion of direct successor and direct predecessor. (Imagine the two notions modelled byt two T × T --> bool functions.) The notion is nice in the sense that t' is a direct successor of t if and only if t is a direct predecessor of t'. For an object t of type T I note d(t) the set (in the usual sense) of its direct predecessors and successors.

Each day I receive an xml containing the list of all (xml representations) of objects of type t, the representation of t "containing" d(t).

For an object t and an integer k>0 I note S(t,k) (resp. P(t,k)) the set of rank-k successors (resp. predecessors) of t, this set being recursively defined as S(t,1) (resp. P(t,1)) being the set of direct successors (resp. predecessors) of t, and S(t,k) (resp. P(t,k)) being the set of direct successors (resp. predecessors) of object from S(t,k-1) (resp. P(t,k-1)). Finally I note F(t,k) the union of S(t,k) and P(t,k), and G(t) the union of all F(t,k) for k>1.

G(t) as defined is only a set, but can be turned into a graph as follows : each object of G(t) is a node, and two nodes t,t' are connected by an arrow going from t to t' if t' is a direct successor of t. The graph G(t) is connected by contruction and I note B(G(t)) its end points : the objects x in G(t) that don't have any direct successor (i.e. such that S(x,1) is empty).

I note X the set of all objects from the xml, and G1,...,GN all graphs. They obviously partition X.

My task is the following : every day, for any object t from X, I have to be able to determine the set B(G(t)) as fast as possible and the graph G(t) as fast as possible. (I can imagine that the two tasks may not necessarily be related.) Of course, every day I can save all graphs and their endpoints, if that could help for the task the next day.

(From one day to the next the only changes that occur are new direct successors added to objects that are endpoints and deaths (meaning that we know that the dead object will never have direct successors anymore until its rebirth) and rebirth (meaning that the object can now start to have direct successors.)

What are my options here ?


texts:
Given a tree, where each node holds a unique number, each of these numbers is represented in $O(log\,n)$ bits. Describe an algorithm to calculate the greatest number $K$ there is.

I would like to get help with understanding the following :

"The number of all bits in all messages needs to be $O(K\times n \,log\,n)$ but the size of a message can be up to $O(log\,n)$"


texts: How do I model this expression maximization problem as a Knapsack problem?

texts:
Given two arrays of the same length $n$:

$A = \{a_1,a_2,\dots,a_n\}$,

$B = \{b_1,b_2,\dots,b_n\}$,

I have to maximize the following expression:

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}}$$

Where $k \lt n$.

Given the constraints:

Firstly, when you select a particular $a_i$ you have select it's corresponding $b_i$, and vice versa.

Secondly, you have to select exactly $k$ elements from the arrays. Where $k \lt n$.

Assumptions:

The assumption is that $A$ and $B$ both contain natural numbers only.

What I have tried:

I have tried sorting the arrays using the ratio $\frac{a_n}{b_n}$ in the non-decreasing order, but this gives an incorrect result since it's trying to optimize $\frac{a_1}{b_1} + \frac{a_2}{b_2} + \dots \frac{a_k}{b_k}$. That is different from my desired objective function.

I have also thought of treating the denominator as a knapsack but this does not make sense because there are no weights involved.

Any suggestion on what I can do to model this problem as a knapsack optimization problem?


texts: Designing CFG for sequences of words of which two arbitrary ones are reversals

texts:
Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $001001$ = $100100^R$. Give a context-free grammar for $L$.

So far I have come up with a rule that can generate the string that contains the hash symbol.

$ A \rightarrow$ $0A1\;|\;0A0\;|\;1A\;|\;0A\;|\;\#A\;|\;1A1\;|\;A0\;|\;A1\;|\;\epsilon$

How can I design a rule that generates the reverse sequence ? Also I wanna make sure that my rule is correct.


texts: Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

texts:
Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$.

Is $L$ decidable? Recognizable?

Given that membership in $L$ asserts something about $M$'s behavior on an infinite set of strings, it seems extremely unlikely to me that $L$ could be either. I have shown that co-$L$ is Turing-recognizable (I think): you can make an enumerator that tests each $M_1, M_2, \dots, $ for each $s_1, s_2, \dots$ and emits $M$ if it does not accept some $s$ in at most $200|x|$ steps.

Since co-$L$ is recognizable, either $L$ is not recognizable, or it is decidable. I can't imagine that $L$ is decidable. However, it definitely cannot be reduced to the halting problem, nor can Rice's theorem be applied to it (since the quality in question is the quality of halting in a particular number of steps, being able to decide it doesn't let us decide other arbitrary properties).

It seems to me that the best way to go will be to show that $L$ lets me recognize something that is unrecognizable, since the only problems it solves are ones which require me to run over infinite sets of strings. But I can't think of what this could be. I thought that maybe co-HALT would work, but I can't ever prove that a TM will never halt on some input.

I'm stuck. What direction should I go in?


texts: Number of paths starting from a given edge using adjacency matrix

texts:
I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that there is at most one edge between two nodes.
For example consider the graph depicted below:

For instance, we want to count the number of paths starting from edge $b$. They are: $b, bd, bdf, bdfg, bh$. So $F(q0, q2)=5$. ($F$ is the function that runs the counting algorithm). As another example $F(q4, q5)=2$.
Note that I want to count these paths for every two distinct nodes. So the output must be a matrix.
How should I write the algorithm? And what will be the complexity of that?


texts: What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

texts:
Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the hardware, it would be beneficial to the users to have a tool for deciding whether or not a job should be ran locally versus on the cloud. Two important factors would be how much time the user can afford to wait and the funds available to the user.
If we were only optimizing for cost, of course, we'd send every job to the local resources. It gets interesting when you optimize for both cost and time, considering there's a finite amount of machines locally (other users' jobs creates a queue) and the cloud can provide better/faster hardware.
Ultimately, say you have some amount of money and a time frame. After providing this information and a list of jobs (each with varying CPU nodes requested, memory required, estimated job time, etc.), this tool should be able to make a near-optimal decision about which jobs to run locally and which to run on the cloud.
Considering the optimization nature of this problem, Google's OR-Tools library looks great to start with. They provide guides (check left side bar there) to several "problem types". I'm having trouble deciding which category this problem falls into.
For those unable to visit the OR-Tools link, the problem types are:

Linear Optimization
Integer Optimization
Constraint Optimization
Assignment
Routing
Bin Packing
Network Flows
Scheduling

What problem type category does this best fall into, and what are some ideas on how to formulate said problem?


texts: I can't understand this example of PDA Automata

texts:
looking for old tests of Language Theory, I see this exercise:

Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$

They propose this solution:

Can anyone help me to understand what strategy they used?

Sorry for my english, is not my native language.

Thanks.


texts:
According to this article the following line of Lisp code prints "Hello world" to standard output.

(format t "hello, world")

Lisp, which is a homoiconic language, can treat code as data in this way:

  Now imagine that we wrote the following macro:

  (defmacro backwards (expr) (reverse expr))

  backwards is the name of the macro, which takes an expression
  (represented as a list), and reverses it. Here’s "Hello, world" again,
  this time using the macro:

  (backwards ("hello, world" t format))

  When the Lisp compiler sees that line of code, it looks at the first
  atom in the list (backwards), and notices that it names a macro. It
  passes the unevaluated list ("hello, world" t format) to the macro,
  which rearranges the list to (format t "hello, world"). The resulting
  list replaces the macro expression, and it is what will be evaluated
  at run-time. The Lisp environment will see that its first atom
  (format) is a function, and evaluate it, passing it the rest of the
  arguments.

In Lisp achieving this task is easy (correct me if I'm wrong) because code is implemented as list (s-expressions?).

Now take a look at this OCaml (which is not a homoiconic language) snippet:

let print () =
    let message = "Hello world" in
    print_endline message
;;

Imagine you want to add homoiconicity to OCaml, which uses a much more complex syntax compared to Lisp. How would you do that? Does the language has to have a particularly easy syntax to achieve homoiconicity?

EDIT: from this topic I found another way to achieve homoiconicity which is different from Lisp's: the one implemented in the io language. It may partially answer this question.

  Here, let’s start with a simple block:

Io> plus := block(a, b, a + b)
==> method(a, b,
        a + b
    )
Io> plus call(2, 3)
==> 5

  Okay, so the block works. The plus block added two numbers.

  Now let’s do some introspection on this little fellow.

Io> plus argumentNames
==> list("a", "b")
Io> plus code
==> block(a, b, a +(b))
Io> plus message name
==> a
Io> plus message next
==> +(b)
Io> plus message next name
==> +

  Hot holy cold mold. Not only can you get the names of the block
  params. And not only can you get a string of the block’s complete
  source code. You can sneak into the code and traverse the messages
  inside. And most amazing of all: it’s awfully easy and natural. True
  to Io’s quest. Ruby’s mirror can’t see any of that.

  But, whoa whoa, hey now, don’t touch that dial.

Io> plus message next setName("-")
==> -(b)
Io> plus
==> method(a, b,
        a - b
    )
Io> plus call(2, 3)
==> -1


texts:
I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $[0,1]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ non relevant. What I have tried so far is  removing edge values that are below median or 60% - 70% quantile. Another approach I have tried is to generate random graphs and calculate random edge similarity as $ randSim = \frac{\#edges\_drawn}{\#edges\_sampled}$  and remove edges with vales <= random similarity.
The issue I am facing is that the first approach is too arbitrary and very few edges are removed using the second approach. Do you have suggestions for other edge pruning approaches ?

Thank you.


texts: What is the benefit of using one to one thread mapping model instead of Many to Many or two level?

texts:
So in the silberschatz O.S book it says Windows uses one to one model (mapping user level threads to kernel level threads)

but why? i thought many to many and two level models are much better, specially two level model, so why not use the two level mode or many to many? whats the benefit compared to other models and isn't there some overhead and limitation(like number of threads) because of using one to one?

overall, if someone wants to create a new O.S, how should he know which model to choose?


texts: Hash values that are impossible to reach

texts:
I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits long. Technically, there are $2^{256}$ possible hash values that can be computed. Is it possible that a specific sequence of 256-bits cannot be generated using the SHA-256 algorithm?

This question is not specific to SHA-256 itself, but any hashing algorithm that follows a uniform distirbution pattern.


texts: Are there parallel algorithms that give more than linear speedup?

texts:
I'm wondering if there are any parallel algorithms whose runtime is not linearly dependent on processor count. (Assuming the problem-size remains constant for different processor counts)

For example, suppose p processors has a O(n^2) runtime and p+1 is O(n^1.5). To me, it seems if that were the case, you would just use the O(n^1.5) for p processors. You might want to use the O(n^2) if the overhead of the O(n^1.5) algorithm outweighs it's benefits. But if that were the case, the execution time vs processor count curve would still be bounded by n^1.5 (since execution time includes overhead).

There is also the case of super-linear speedup, when comparing two architectures. However, it seems the execution times are still linearly dependent on the number of processors (albeit the slope is > 1). The common case of super-linear speedup is from memory limitations. This should still be bounded by a linear function though, since memory access is inherently linear.

Apparently, branch-and-bound search algorithms can get super-linear speedup; but I haven't seen any data to determine whether these speedups are linear.
Are parallel search algorithms an example of greater than linear speedups? If so, what function are the speedups bounded by?


texts: Smallest string containing sets of letters

texts:
I am looking for a solution to this problem:
Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The sets have to be present as one substring, it is possible to duplicate letters in the final string, and it is also possible to permutate letters in one set.

E.g.:

abc|def|gabe (strlen = 10, sets are like: Set0, Set1, Set2)

Where the Set0 is starting at the index 0, Set1 is starting at the index 3, Set2 is starting at the index 7.

Another better solution is:

ab|egf|dabc (strlen = 9, sets are like: Set2, Set1, Set0)

Where the Set0 is starting at the index 5, Set1 is starting at the index 2, Set2 is starting at the index 0.


texts: What use are groups, monoids, and rings in database computations?

texts:
Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird.

All I could find is:

  Implementations of Monoids for interesting approximation algorithms,
  such as Bloom filter, HyperLogLog and CountMinSketch. These allow you
  to think of these sophisticated operations like you might numbers, and
  add them up in hadoop or online to produce powerful statistics and
  analytics.

and in another part of the GitHub page:

  It was originally developed as part of Scalding's Matrix API, where
  Matrices had values which are elements of
  Monoids, Groups, or Rings. Subsequently, it was clear that the code had broader application
  within Scalding and on other projects within Twitter.

What could this broader application be? within Twitter and for general interest?

It seems like composition aggregations of databases have a monoid-like structure.

Same question on Quora: What is Twitter's interest in abstract algebra (with algebird)?

I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups.  These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).


texts:
So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops.

What is the significance of self loops in it?

How is it related to flow in the graph?

Let there be a graph like this 1->2->3 and 2 has a self loop. So, can I interpret it like this-

1->2a--2b->3 ? where -- denotes an edge from 2a->2b and an edge from 2b->2a.

So, How would I represent this in a graph using adjacency list?


texts: Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

texts:
I am struggling with the following problem:
Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and machine N. In other words, is language { encodedMachine(M)#encodedMachine(N) | intersection of language of M and language of N is infinite } decidable?

Intuitively it feels like this is undecidable problem and halting reduction might be used to proof this, but I have no idea how to start this reduction.


texts: Shared randomness does not increase capacity of a noisy channel - Why?

texts:
Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?
This is mentioned in some notes (see paragraph before Section 4 of https://cds.cern.ch/record/613098/files/0304102.pdf) but I have not seen a proof or an intuitive argument for it yet. Any reference to where this is covered would also be appreciated!


texts: Maximum non-intersecting subset of circles

texts:
We are given a set of circles, stored by their center points in an array $A$.  In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$.  All the circles have radius of $k$.

I want to find a subset of circles such that no circles in this subset intersect with each other, such that this subset is as large as possible.

I'm asked to find a way to solve this using a backtracking algorithm.  Rather than to do it with brute force, is there a effective way to prune some of the branches?


texts: Can somebody please explain what the pumping lemma is?

texts:
I've had multiple lectures on the pumping lemma but still can't grasp exactly what it is...my main questions are as follows

What is the pumping lemma for?
How do you use it to prove a language is not regular (with an example please)

e.g. if L is in sigma and L is regular, prove that sigma*-L is regular

It doesn't need to be this exact example in case you think I'm trying to cheat for homework or something.

In lectures we've been doing this by using contradictions but I seem to only understand the answer and nothing else


texts: Find a pushdown automaton for { x#y ∣ x ≠ y }

texts:
I was told to built a PDA that recognizes the following language:

$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$

My attempt is basically to push $x$ to the stack for every $1$ and $0$ read. And then pop them for the second half. If it finishes and the stack is still not empty, it will be accepted. Or if it hasn't finished reading but the stack is empty already it will also accept.

Am I approaching this correctly?
I can easily do the CFG but I'm told that it's easier to do the PDA from scratch rather than converting it since it needs to be in CNF.

Any help appreciated


texts: Find an MST in a graph with edge weights from {1,2}

texts:
I've been asked the following question:

  Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph.

After a few clarifications, the algorithm should run in time $O(|V|+|E|)$. I believe we can do this because of the fact that there are two types of weight of edges.

I tried the following idea, which did not work (I had a contradicting example):

  Run BFS on the graph, and output the BFS tree.

I thought that shortest paths in this case would also mean easiest trees, but this is not the case.

I also tried to make each edge $e$ such that $w(e)=2$ into two edges of weight $1$ but my friend also gave a contradicting example.

Can you help please? This is not a homework question, this is a previous exam question as I am studying for my algorithms exam which is soon.


texts: Karatsuba Multiplication Rule in dividing a Number in two parts

texts:
In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example:

x= 1234
y= 2456

Then a = 12, b = 34, c = 24 , d = 56

What if the digits in each number are not even, or the same? What is the rule in dividing it into two parts?

Example:

 x = 12345
 y = 2478

or

 x = 12456778
 y = 241

Please help.


texts:
I would like a review for my algorithm for the following question:
A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$
Let G be a balanced network in which in-degree(s)=out-degree(t)=0
Find max-flow for G.
My Algorithm so far:

We will define the following capacity-function: $∀(u,v)∈E,f(ⅇ)=c(ⅇ)$
Run over the adj. list and update for every edge it to be our function, and return c(e)

I was also wondering how to prove its a max flow in the correctness part
Thank you


texts: maximum coverage version of dominating set

texts:
The dominating set problem is :

  Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ lies in $S$}\}$$

My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name.

  New Problem: Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(\subseteq V)$ of size $k$ such that $|N[S]|$ is maximized.

For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).


texts: Is there a difference between type safety and type soundness?

texts:
I've been trying to tease apart the definitions of type safety and type soundness and I'm having a heck of a time of it. I asked a professor recently and after a bit of thought he said that there really wasn't any difference. However after reading this
it seems like:

Type Safety is a property of the language that says that the application of functions (and operators) to data is meaningful (i.e. 1 / "Hello" is nonsense and is disallowed)
Type Soundness is a property of a type checking system that guarantees that its static type predictions are accurate at run time.

This is clearly just a single persons notes and I'm wondering if there is some standard within the PL community. I've done some searching and I haven't found a satisfying answer.


texts: Do computers actually use carry-lookahead adders?

texts:
There are plenty of details about carry lookahead adders such as Kogge-Stone, Lander-Fischer, etc. in college CS courses. They are described as "common in the industry".  However, I can't find any evidence (aside from maybe the Manchester carry chain) from recent times that they are actually used anywhere specifically. A Google search only returns pages of journals and academic research. At most, hypothetical implementations are given.

My question is, are there any specific places/implementations carry-lookahead adders are used? Or are they irrelevant to the real world?


texts: In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

texts:
The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test:

  It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for the compositeness of $n$.

In the Fermat primality test, if $n$ is not a Carmichael number, at least half of the bases $a$ are Fermat witnesses. Testing for non-trivial roots in the Miller-Rabin primality test however increases the minimum number of witnesses to $\frac{3}{4}$.


texts: A faster, leaner JavaScript for scientific computing: what features should I keep?

texts:
Here I'm really interested in lowering barriers to mathematical education.

Target:

I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-performance computing libraries (great lists of which are available through Sage and otherwise). And I want that, because I'd like to make it easy for people who learn JavaScript to get into scientific and numerical computing without having to learn Python (& company). (I know it's easy to learn Python, as I basically did it at some point, but this suggests that perhaps it'll be easy to compile some restricted subset of JavaScript to Python.)

Hypothesised method:

I'm primarily interested in a new language with minimal difference from JavaScript, because the market ("human compilers") I'm targeting are programmers who already know JavaScript. What I want to target those people for, is to give them a minimally different language in which to write code that compiles to faster C, in the manner that RPython and Cython do for Python. I'm willing to throw out a lot of JavaScript features, I just want to be careful to add a minimum number of features back in. I'll definitely be looking at Lua, Dart, ECMA Harmony (which has no formal date of release, or am I mistaken?), etc. as these are all close resemblances to contemporary (2012) implementations of JavaScript.

Questionable Motivations:

I'm personally willing to learn any language/toolset that gets things done faster (I'm learning Erlang myself, for this), but here, I am specifically interested in lowering the bar (sorry) for other people who may not have such willingness. This is just one of those "want to have my cake, and eat it too, so I am putting some time into researching the problem" situations. I have very limited prior experience in computer language design, but so far from a hacking-the-ecosystem point of view, the problem seems interesting enough to study, so, I hope to be doing more of that soon.


texts: Can an LTL formula uniquely be represented by an expression tree?

texts: Just like we can represent a mathematical expression uniquely with a binary expression tree, I was wondering if we could do the same for LTL formulae? Such that no two different looking LTL formula will have a same in order traversal.


texts: Check whether set of strings is prefix-free via lexicographic sort?

texts:
I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So {a, b} is prefix-free (has the prefix property) while {a, b, ba} is not prefix-free (lacks the prefix property) because the entire string b is a prefix of ba.

One can of course implement this with a double-loop for quadratic performance. In JavaScript (so you can pop open your browser’s JS Console and try it, if so inclined):

function isPrefixCode(strings) {
  for (const i of strings) {
    for (const j of strings) {
      if (j === i) {
        continue;
      }
      if (i.startsWith(j)) {
        return false;
      }
    }
  }
  return true;
}
isPrefixCode(new Set('a b c'.split(' '))) // true
isPrefixCode(new Set('ba b c'.split(' '))) // false

I think one can do better by sorting the set of strings lexicographically ($N \log N$), then comparing each element to its previous one (linear). So:

function isPrefixCodeLinear(strings) {
  strings = Array.from(strings).sort();
  for (const [i, s] of strings.entries()) {
    if (i === 0) {
      continue;
    }
    const prev = strings[i - 1];
    if (s.startsWith(prev)) {
      return false;
    };
  }
  return true;
}
isPrefixCodeLinear(new Set('a b c'.split(' '))) // true
isPrefixCodeLinear(new Set('ba b c'.split(' '))) // false

This linearithmic algorithm seems to work for the tests I’ve come up with (and ~100x speedup over the quadratic double-loop algorithm on a 1000-string example), but I’d like to ask

if this approach based on lexicographic sorting is guaranteed to work,
if this approach has a name, and
if the prefix property has a more common term in computer science, or
if there are other algorithms that can solve it.

(I found this question on StackOverflow, about finding whether any entry in a set of strings is prefixed by a specific given string, How to search whether a string is a prefix of strings stored in a set?, which is a related problem to mine, but here I want to consider not just any one string but all the strings in the set.)


texts: How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?

texts:
I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it says that

  "This pairing can be done in polynomial time, because the Turing machine has only constant size."

So their justification for saying that the reduction was done in polynomial time is that the Turing machine 'only has constant size'.

Why would this prove that the reduction was done in polynomial time?


texts: How can I prove that the high-degree independent set problem is NP-hard?

texts:
I'm learning about NP Completeness, and I have come across the following problem

The decision-version of the high-degree independent set (henceforth "HDIS") problem is stated as follows: Given a graph $G = (V, E)$ with $n$ vertices, does $G$ have an independent set of size $k$, consisting of vertices with degree at least $n/2$? Prove that HDIS is NP-complete.

I'm provided with a hint that I'm supposed to perform a reduction from independent set.

I was wondering if someone can please check my work.

First, HDIS is in NP because given a certificate (just a list of vertices), we can compute the degree of each vertex, and verify that no two vertices are adjacent and the degree of each vertex is at least $n/2$ is polynomial time.

Now we need to show that HDIS is as hard as any other NP-complete problem.

I was thinking about starting with an instance of independent set (so a graph $G = (V, E)$) and subsequently constructing a new graph $G'$ with every vertex whose degree was less than $n/2$ in the original graph removed. From here, I think that I can just call my oracle to HDIS and return "yes" if and only if my oracle returns "yes".

This is one of the first problems that I am solving, and I am wondering if someone can please tell me if this is correct?


texts: Languages accepted by modified versions of finite automata

texts:
A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide some transition for all elements of the input alphabet; in other words, the transition function $\delta : Q \times \Sigma \rightarrow Q$ should be a (total) function.

Imagine what we will call a doubly deterministic finite automaton (DDFA). It is defined similarly to a DFA, with two exceptions: first, instead of the transition leading from one state to one other state for every possible input symbol, it must lead to two distinct states; second, in order to accept a string, all potential paths must satisfy either one or the other of the following conditions:

All potential paths through the DDFA lead to an accepting state (we will call this a type-1 DDFA).
All potential paths through the DDFA lead to the same accepting state (we will call this a type-2 DDFA).

Now for my question:

  What languages do type-1 and type-2 DDFAs accept? Specifically, is it the case that $L(DFA) \subsetneq L(DDFA)$, $L(DDFA) = L(DFA)$, or $L(DDFA) \subsetneq L(DFA)$? In the case that $L(DDFA) \neq L(DFA)$, is there an easy description of $L(DDFA)$?

Proofs (or at least moderately fleshed-out sketches) are appreciated, if they aren't too complicated.


texts: Find an invariant in the minimum algorithm

texts:
I have the following simple algorithm to find the smallest element of an array $A$ of numbers:

m = A[0];
For i = 0 to A.length() do
    if m < A[i] then
        m = A[i];
    end
end
return m;

The complexity of this algorithm is $O(n)$ where $n$ is the length of $A$.

I would like to prove the correctness of this algorithm using an invariant. Yet I don't know which invariant is nice here.
Maybe something like: $m$ is the minimum of the subarray $A[1..k]$.


texts: Independent sets into which all the vertices of the graph can be split

texts: How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?


texts: Prove np-hard with reduction from scheduling resources

texts:
Lets say I have a set of destinations and another corresponding set of origins. I need to link each destination with one origin.A set of vehicles start from each origin towards their respective destination.The speed of every vehicle is provided.

In the network no two vehicles moving in opposite directions are allowed to move on a particular road at any instance of time,in brief there should not be any collisions on a road,if such a situation arrives,any one of the two vehicles which can collide on the road can wait till the other vehicle is passed or take some another path to reach its destination.In any situation no two vehicles can travel in opposite direction on the same road.

The graph can be thought of a road network where each edge in the graph represents the road and vertices in the graph can be thought of intersection of the edges.

The aim is to calculate the minimum time required for the last vehicle to reach its destination and also the path taken by each vehicle to reach its destination satisfying all the above constraints.

Now lets consider the segments of the road as resources ,that is a particular segment which joins two junction and the given set of origins and destination as process.Now i know that is NP-HARD,but i want to reduce this from some resource scheduling problem which is also NP-HARD.

The problem can be thought as a real life problem,so the size of the network can be very large comprising more than 100 vertices and more than 400 edges

Is there any np-hard scheduling problem which can be reduced to this problem in polynomial time?


texts: Worst case of subset construction (NFA to DFA)

texts: I am wondering what generic example there is so that an NFA with $n$ states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft et al. where the resulting DFA has $2^{n-1}$ states, reproduced here, but I am looking for a result with exactly $2^n$ states.


texts: Does this algorithm for permuting rows and columns of a matrix converge?

texts:
Given a binary matrix, define the magnitude of a row by reading off the numbers in it left to right and similarly for columns, reading the numbers going down. For instance, the row magnitude of the 1-st row of this matrix is 1001101, and for the 2-nd column it is 11.
1 0 0 1 1 0 1
0 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0
I would like to sort a matrix by doing the following:

reorder rows so that rows are ordered in descending order according to their row magnitude

reorder columns so that columns are ordered in descending order according to their column magnitude

repeat 1 and 2 until rows and columns are in a correct order

For the matrix above this would go as follows:
sort by rows (step 1)
1 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0
0 0 0 1 1 0 1
sort by columns (step 2)
1 1 1 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
1 1 1 0 0 0 0
sort by rows (step 1)
1 1 1 1 0 0 0
1 1 1 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
both columns and rows are in order, terminate procedure.
For the majority of matrices, performing steps 1 and 2 once won't be sufficient, since reordering columns will ruin the ordering of the rows. However, strangely enough it seems like 3 reorderings are sufficient to order matrices I've tried it on.
Despite not being able to find a counterexample, I struggle to see why this would be the case, and even more generally, what guarantees the algorithm won't get stuck in a cycle. Is there an existing name or more formal way to describe this algorithm and are there any proofs on its convergence?