texts: How to tell if a grammar is LALR(1) formally?

texts:
There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations possible for the grammar). Is there a similar formal criterion of a grammar being $\operatorname{LALR}(k)$ or specifically $\operatorname{LALR}(1)$?
For context, I am interested in looking into grammar transformations that preserve the property of being $\operatorname{LALR}(1)$ (for example, does eliminating right recursion in an $\operatorname{LALR}(1)$ grammar result in a grammar that is still $\operatorname{LALR}(1)$?)


texts: Difference between inverted page table and a standard one?

texts:
I know that for standard page tables each process would have its own page table and for inverted the OS would have it.

But other than this what are the main differences between a standard page table and an inverted one?


texts: Turing Machine to return all prime numbers

texts:
My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.

So no matter what the input is, we should ignore it. I think it would be sufficient to add another tape with cells $1^*,2,\dots,n$. Now, I would use Sieve of Eratosthenes algorithm as follows:

Move a head to the right until the head encounters an unmarked symbol.
Mark the symbol with a star and write it down to another write-only tape representing the output, i.e. the symbol is a prime number.
Now, for $n$ being prime, I am supposed to mark every $n$-th symbol with a star. I am not sure how to do it.
Reset.

For the third step, I think I should utilize another marking mechanism to denote a gap between the beginning and the prime resolved in that round. Then, I would be moving that "window" and whenever the beginning of the "window" would reach the prime, I would mark the symbol at the end of the "window" with a star. Not sure how to express this formally.


texts: Minimum number of moves in this Graph Coloring "Game"

texts:
You're given a graph $G = (V, E)$ and a set of colors $C = \{c_1, \cdots, c_v\}$, and the task is as follows:

Color the vertices using the colors in $C$.
Remove any edges that have differing colors for its endpoints (of course, if a vertex eventually has all edges removed, it can be deleted - but it is not necessary).
Repeat the above two steps until there are no edges left in the graph.

Suppose that $k = |V|$ is the number of vertices, $m = |E|$ is the number of edges, and $v = |C|$ is the number of colors. I am interested in the quantity $p(k, m, v)$, which is the smallest number of iterations of the above algorithm given $k, m, v$. Of course, we need $v \ge 2$ (couldn't remove any edges otherwise), and $p(k, m, v) \le m$ because we can color one edge at a time. We can also denote this quantity by $p(G, v)$.

Based on a combinatorial object that is equivalent with respect to this procedure (perfect hash families), when we have the complete graph $K_k$, one can prove that $p(K_k, v) = \lceil \log_v(k) \rceil$. So of course $p(k, m, v) \le \lceil \log_v(k) \rceil$ if $G$ is a simple graph.

But the more interesting case is when we have $G$ be a hypergraph. Here, we remove hyperedges that are rainbow (i.e., every vertex in the hyperedge is a distinct color). Based on PHFs, there are lower and upper bounds for $p(G, v)$ when $G$ is the complete $t$-uniform hypergraph. In general, $p(G, v) \in \Theta(\log k)$ for these graphs, but the hidden constant heavily depends on $v, t$.

Are there references that have looked at a similar problem for hypergraphs?


texts:
(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)

Looking at Wikipedia page for Binary Trees, I've noticed this assertion that the number of rooted binary trees of size $n$ would be this Catalan Number:
$$C_n = \dfrac{1}{n+1}{2n \choose n}$$

But I don't understand how I could come up with such a result by myself? Is there a method to find this result?

Now, what if the order of sub-trees (which is left, which is right) is not considered? For example, from my point of view, I consider that these two trees are the same:

   /\   /\
  /\     /\

Would it be possible to apply a similar method to count how many of these objects have exactly $n$ nodes?


texts:
I would appreciate some help with this question.

The 32 bit numbers below represent a MIPS instruction. identify the different fields and state which instruction it is. give the assembler source code that can be converted into this instruction.

001000|10001|10010|0000000000001111

I separated the bits and I know the first 6 bits are the opcode and given the opcode it means Addi. The last 16 bits are the immediate value which I have converted to 15. I do need help with the registers and converting the binary into the register number. I have looked everywhere and can not find an explanation. Any help would be appreciated. i know the structure takes this format:

Addi, t,s, 15


texts: LL(1) parsing table of left-recursive grammar

texts:
I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:

S -> Sa | b

According to the professor parsing table looks like this:

If the leftmost nonterminal is S and the input is 'a', the production is nothing.
If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b.

So if input is just b, then it is correct, it will go directly to production b.
But how will it go to production Sa for input b?


texts:
What are the disadvantages of storing a playlist as plain text in a text file?

This is what I thought:

The main disadvantage of storing the play list as plain text is its simplicity. The basic conceptual structure of the rows of values can be very inefficient and inappropriate for data sets with complex structure. The low-level format of storing everything as characters with one byte per character is very inefficient in terms of amount of computer or phone memory required. It can also lead to massive redundancy (repetition of values). The speed of access and space efficiency for large data set is also not ideal. The second disadvantage is the fundamental structure of plain text file format means that each line of the file contains exactly one record or case in the data set. This only works well when a data set only contains information about one type of object. However, this is not the case as storing the playlist would mean that we also need to store all the information about the songs such as the name and song time. So there would be information about two different types of objects. A plain text file format does not allow for sophisticated data models. A plain text format is unable to provide appropriate representation of complex data structure like a playlist.

Now my question is instead of storing the playlist as plain text in a text file, what would be a more suitable way of storing objects? Please explain. Thank you.


texts: Prove propositional formula is a tautology

texts:
I need to show this formula is a theorem of propositional calculus. I tried assuming antecedent and proving consequent but didn't work for this proof. Do I need to show it is equivalent to true? How should I start? It's not possible to use truth tables.

$(p \rightarrow q) \rightarrow (p \wedge r \rightarrow q \wedge r)$

Background:

In my class, there is no mention to it but I think this form of logic it's called Equational Logic.
Probably, it's based on this book: A Logical Approach to Discrete Math
by David Gries

EDIT:
I was asked to provide more details on the type of proof needed. In my class, I am not allowed to use truth tables to prove this proposition. This is an example:


texts:
An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one.  Got the first one but not the second.

What is the modern standard way to search a graph (assume undirected) given no other context? I've a notion that it might have something to do with Dijkstra's algorithm but IDK what. It makes sense that one way is to simply traverse the graph until you find the item you are looking for but it sure doesn't seem optimal.


texts: Generating bit sequence containing every possible of length 1...n

texts:
Generating sequence containing every possible bit sequence of lengths from $1$ to $n$ is trivial - just generate every possible sequence of length $n$.

But how do you generate the shortest sequence containing every possible bit subsequence of lengths from $1$ to $n$ (using the fact that subsequences may partially overlap)?

What complexity class does that problem belong to?


texts: Using A* to find the word closest to an input rejected by a finite automaton

texts:
In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton after inputting something that is not accepted by said automaton.

It uses A* search to efficiently search for the closest match and has a heuristic function f = g + h, where g is the cost (0 or 1) of an edit operation needed to transform character at index i and h is the number of characters from the input word which is not found along the path from the current state.

I'm not sure if I'm correct in my understanding, but for the function f=g+h, g is the cost of the edit operation depending on the path it takes, so it can only be 0 or 1 while h is the number of non matching future characters from the list when compared to the next state's list of symbols?

What would the process be like for a word such as ddddat or hhhhat? I don't think I read anything about this sort of case being handled unless I missed it.


texts: Is the complement of the Hamiltonian Path problem known to be in $\mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is not in $\mathsf{NP}$.


texts: Why does Prim's algorithm keep track of a node's parent?

texts:
There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of  a node's parent.  In Dijkstra's algorithm, the parent of the node needs to be tracked in order to follow the chain back to the original node to determine the distance from the source, however since Prim's algorithm only requires knowledge of the distance from the minimal spanning tree, rather than a specific node, there would be no reason to track the parent.

Please refer to the following pseudocode as reference:

PRIM(V, E, w, r )
  Q ← { }
  for each u in V do
    key[u] ← ∞
    π[u] ← NIL
    INSERT(Q, u)
  DECREASE-KEY(Q, r, 0)    ▷ key[r ] ← 0
  while Q is not empty do
    u ← EXTRACT-MIN(Q)
    for each v in Adj[u] do
      if v in Q and w(u, v) < key[v] then
        π[v] ← u
        DECREASE-KEY(Q, v, w(u, v))


texts: Location Selection Algorithm in Solar Engineering

texts:
This is a practical problem in energy generation with heliostats.

We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One hub can support 12 harnesses (a kind of cable) and one harness can support 16 heliostats; namely, one hub can support 192 heliostats. The cost of deploying a hub and harness per meter are given. In other words, every harness starts from a hub and can connecting at most 16 heliostats. Deployment of a hub results in a cost. Also, the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness. However, there is no distance from heliostats to its connecting harness.

Currently my approach is to use k-means to cluster the whole region and run greedy on distance from harness for each split region, though I do not think this is a good approach.

This is a pattern generated by my algorithm. As you can see, some harness only support 1 or 2 heliostats and result in a waste of harness.

Our job is to optimize the cost. In the end, the algorithm should return locations of hubs, harness topology patterns, and the total cost.

Can anyone enlighten me potential algorithms on this?

(Every point on the image is a heliostat, there are 40981 in total)

----------- Updated 14/12/2016 -----------

More details on the question, thanks D.W's suggestion:

Coordinates of heliostats are given. These coordinates correspond to real-world metrics (meters).
The placement of hubs are not constrained. However, one harness cannot be longer than 45 meters due to voltage requirement.

----------- Updated 15/12/2016 -----------

The classification on "furthest" in "the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness": Furthest is in the sense of "last", not "furthest" in the sense of "having the largest Euclidean distance from the hub"


texts: Context-sensitive grammars without permutation rules

texts:
Permutation rules are called those which are of the form $AB\Rightarrow^*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages.

My question is: are any examples of context-sensitive grammars, which doesn't contain any permutation rules but still able to produce non-context-free languages?

1) Book, R.V. International Journal of Computer and Information Sciences (1973) 2: 129. doi:10.1007/BF00976059. More generally permutation rules have form of $Y_1 \dots Y_m\rightarrow Y_{\pi_1}\dots Y_{\pi_m}$, where $\pi$ is some permutation of $\{1\dots m\}$.


texts:
As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.

Here after the recursive call we just assign the result to another variable.
Can we consider this code as tail recursion?

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head

        head_ = head
        head_next = head.next
        head_next_next = head.next.next

        head_next.next = head_

        head_.next = self.swapPairs(head_next_next)

        return head_next


texts:
I was asking to prove that

  For any directed graph, when we perform BFS, for each cross edge $(u,v)$,
  there is some time when both vertices $u$ and $v$ appear in the queue.
  (In other words, we have a queue like this: $Q = \langle v_1,v_2,..u,..,v,..v_k \rangle$.)

However, when I draw some graph; I've encountered this example

If we perform BFS starts from $a$, then what is the edge of $(f,c)$? clearly, if what I was about to prove is correct, $f$ and $c$ will never appear in the queue at same time during the whole execution of BFS. So $(f,c)$ is not cross edge. Then what edge is this ? It can't be back edge; since $c.parent$ is $a$, and $f.parent$ is $e$. they aren't tree edge, nor forward edge.

So what I am asked to prove is not correct?

So I guess that the statement only holds for undirected graph?


texts: Systematic approach or algorithm for designing a pushdown automata that accepts a langauge

texts:
I understand that designing automatons is mostly a creative process but, a month ago I was having a discussion with a classmate about designing a NPDA or a DPDA that accepts a non-trivial language (trivial meaning, it is straightforward to design a PDA that accepts it) and he gave me a solution while mentioning an algorithm that he used to arrive at said solution.
his solution was correct but used nearly twice the number of states than my solution which was also correct (both solutions used NPDAs). unfortunately I don't have access to him to ask about what he meant by an algorithm, anymore.

I looked in both Sipser and Linz books and I didn't find anything about such an algorithm or systematic approach.

If you know of such thing please demonstrate with your own language of choice.


texts: Can Turing machines simulate the unbounded minization operator applied to a partial function?

texts:
I am a little bit confused with the unbounded minimization ($\mu$ operator of the $\mu$ recursive functions).

The $\mu$ operator is $\mu(f)(x) = \min(n | f(x, n) > 0)$ and the operator is said safe if we only apply it to functions such that for every $x$, $f(x, n) > 0$ for some $n$. In that case, every recursive function is total and every such function is computable with a Turing machine. The proof simulates every initial function and every operator with a Turing machine. Particularly, for $\mu$, the machine applies $f(x, n)$ for each $n \in \mathbb{N}$ until $f(x, n)$ is not 0.

This can be done because the operator is safe. The machine halts on every input.

When the operator is not safe, we can create partial functions as $\mu(f)(x)$ may be infinite (and thus undefined). Considering Turing machine, partial functions is not a problem as we can state that the machine does not stop if the input is not defined for the fonction. However, I cannot prove that the unbounded and unsafe minimization operator can be simulated by a Turing machine.

Indeed, if $f$ is partial, we can define $\mu$ as $\mu(f)(x) = \min(n | f(x, n)$ is defined and $f(x, n) > 0)$. In that case, there may exist $n = \mu(f)(x)$ and $m < n$ such that $f(x, m)$ is not defined. And, in that case, the machine that was used on the safe case does not halt anymore. Due to the halting problem indecidability, it is not possible to determine if $f(x, n)$ is defined or not.

So, my question is : Are the partial recursive functions (with unsafe operator $\mu$) equivalent to partial functions computable by Turing machines?


texts: In s-t directed graph, how to find many small cuts?

texts: Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in weight). How do I do that?


texts:
I understand how radix sort works and how to implement it, but I don't understand why it works.

Are there any underlying mathematical or logical principles that it relies on?


texts: How do programs like Apache Airflow/ Luigi determine shortest path and how does that relate to graph theory?

texts: I am looking for a simple layman's term explanation on how do programs like Apache Airflow or Luigi (or any Task/ETL schedulers) determine the shortest path to complete a certain task and make it possible to parallelize it? And how does that, if any, relate to graph theory?


texts:
I was going through TM here and encountered a term "Dovetailing".

What is exactly the dovetailing in Turing Machines?

Can anyone mind to provide a good explaination with some examples?


texts:
This is the problem I am dealing with:

Given a set P of n points in general position, let a graph G be defined as follows:

The vertex set is P. Two vertices, a and b, are joined by an edge provided there exists an axis parallel square S with a and b on the boundary and no other point of P in the interior of S.

I need to prove or disprove that G is a near-triangulation where every face except the outerface is a triangle and the outerface is a cycle.

Thanks in advance


texts: Is it NP complete to decide whether a graph has $k$ disjoint triangles?

texts:
I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$
but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in polynomial time. Then I'm stuck here.

Could anyone help me out here?


texts: Is the Kleene star of an intersection contained in the intersection of Kleene stars?

texts:
I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*) $$
I think that it's true since this can be rewritten as $$ \bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$$ and in general, $$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$$
I may be wrong since it has been a long time since i have done anything with set theory, and this is taken as given.
Thanks


texts: Show that UPrime = {1^n : n ∈ N is prime} is in P

texts:
I have this question to solve. According to my understanding, it basically requires a turing machine that outputs lines on the tape, with the number of the lines being any prime number.

My idea is to take the AKS test's conclusion and making a case that since, calculating primes is a problem that can be solved in polynomial time complexity as already proven by AKS, hence this problem is also in P.

Is this the right way? what would be a more formal/mathematical way of expressing this if it is?


texts: Divide an integer into the sum of consecutive positive numbers

texts:
Today I am trying to solve an classical problem:

  For any $n\in \Bbb{N}^+$, If it can be represent as the sum of consecutive positive numbers, find out them.

For example:

$$15 = 1+2+3+4+5$$
$$15=4+5+6$$
$$15=7+8$$

And I have an ugly method, its time complexity is: $O(n^2)$. I use two for loop to exhaustion all possibilities.

for(int i=1;i<n;i++)
{
    for(int j=i;j<n;j++)
    {
        sum+=j;
        if(sum==n)
        {   //print out the answer
            for(int l=i;l<=j;l++)
            {
                cout << l << "+ ";
            }
            cout << endl;
            break;
        }
    }
    sum = 0;
}

I think there may be exist a more effective solution, But I am failed until now.  Please help me.

for i from 1 to n
{
   for j from i to n
   {
       sum <- sum + j
       if sum equal n
       {
          print the result
       }
   }
   sum <- 0
}


texts: Recurrence relation with a number value (not n)

texts:
I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form

$$T(n) = aT\big(\frac{n}{4}\big) + n$$

I'm stuck when the equation has a numerical term, like

$$T(n) = aT\big(\frac{n}{4}\big) + 3$$

Using a recursion tree, what gets multiplied at the first, second, third level? And what is the sum of the work done?


texts: DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

texts:
We can form DFA accepting binary numbers divisible by $n$.

For example DFA accepting binary numbers divisible by 2 can be formed as follows:

Similarly DFA accepting binary numbers divisible by 3 can be formed as follows:

We can follow a well defined procedure to form these types of DFAs.
However can there be any well defined procedure or better to say logic for forming DFAs accepting numbers of of the form $n^k$?

For example, let us consider DFA accepting all numbers of the form $2^k$.
This language will be $\{1,10,100,1000,...\}$, thus have regex $10^*$. We can form DFA as follows:

I tried forming DFA for $3^k$ and similar ones? But was not able to do so. Or is it just that its pattern of $2^n$ binary equivalents which was making it possible to create DFA and we cannot form DFA accepting all binary numbers of the form $n^k$ for specific $n$?


texts: minimizing the maximum between a degree of a tree and its height

texts:
I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically.

If I set $k = \frac {\log n}{\log \log n}$, then the height of the tree is
$\log_\frac{\log n}{\log \log n}(n) = \frac{\log n}{\log \frac {\log n}{\log \log n}}$.

What is the asymptotic height of that tree, is $$\frac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\frac{\log n}{\log \log n})$$ and if so, is this optimal?


texts: What is the impact of locality principles on the pipelining techniques?

texts:
I know what are both locality principles and pipelining techniques. But I can't see any sort of interconnection between the two things.

How can locality principles impact pipelining techniques?


texts: what's analogy learning algorithm ? differences from induction learning algorithm?

texts: I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?


texts: Algorithm for assigning 2 list of different objects into connected slots optimally

texts:
I would to optimally assign objects into slots. There are 2 lists of 2 different elements that have to be assigned. An element from list 1 must be grouped with an element from list 2 into one slot.
The slots are linked (they have 1 or 2 adjacent slots).
There are some constraints on an exact number of slots that an element from list must be assigned to (each element in list has a specified number of slots that it has to be assigned to, in order to have a solution).
Also, each grouping of elements from one list with elements from the other list gets a group type (the type of the group is given by the element in the first list).
And another constraint is that element from list 2 must participate in certain number of groups with the type(s) that it can give to the group.
The slots have to be filled optimally; they don't have to be all filled, but the better solution is where an element from a list is assigned to as many connected slots as possible (as opposed to participating in many slots that are not connected between themselves)
Example: students (list 1) haves classes (group types) that they have to attend. They must attend certain number of classes (they have a constraint to participate in a certain number of classes of each type; e.g. 3 math classes).
Teachers (list 1) have classes (group types) that they can teach. Teachers (list 1) can teach certain types of classes (group types) and have a certain number of hours (slots with a certain group type) they must fill. E.g. a teacher can teach math and must give 10 math classes (to fulfill its quota)
Of course, all this has to be scheduled, into time slots, so it would be better if both teachers and students are assigned to many connected slots (they attend consecutive classes and dont have big gaps, i.e they attend slots that have only one or none connections with the other slots to which they are assigned to).
I have looked around a bit and found this to be either modeled as graphs and do some "perfect matching" or that this could be treated a "constraint optimization" problem (part of general scheduling).
Suggestions on which algorithm to use/how to model this? Or just tips what to look for/at?


texts:
Hi guys I was given this question:

  Prove or disprove that the following language is context-free: $$ L = \{ \alpha 2 \beta : \alpha,\beta \in 1(0+1)^*, [\alpha]_2 < [\beta]_2 \} $$ where $[x]_2$ is the numerical value of the string $x$ interpreted as a positive number in base 2. For example, $[1110]_2 = 8+4+2 = 14$, $[10100]_2 = 16 + 4 = 20$, thus $1110210100 \in L$, while $111021110 \notin L$ and $1010021110 \notin L$.

I can't figure out either way if its context free or not. When I was trying to prove it was context free with a DPDA I got stuck because I don't know how to compare two binary strings when one is in reverse of the other because when you put the string left of the 2 into a stack and pull it out it comes out reversed. Because of this I can't compare if one is bigger than the other if they are the same length.

On the other hand I tried using the pumping lemma to prove its not context free. For a string $ 1^{m}210^{m} $ I can show for two cases when $ v^{k}xy^{k} $ is composed of just 1's on the left side or right I can either underpump or overpump. For the third case when $ v^{k}xy^{k} $ is composed of the run of 1's on the left and the 0's on the right pumping in either direction doesn't seem to make the left binary number the bigger value.

I am stuck with either direction I have tried so could somebody point me in the right direction?


texts: Dijkstra's algorithm to compute shortest paths using k edges?

texts:
I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ edges. Assuming we have no negative edge weights at all, can we use Dijkstra's algorithm for the same?

My thoughts/algorithm:
I was wondering if instead of having a $dist[u$] array (storing the best known distance from s to u), we could use a $dist[u][k]$ table to store the best known distance from $s$ to $u$ using at most $k$ edges (dynamic programming maybe?), and similarly have the priority queue with $(u,n)$ tuples as keys. We can then terminate the algorithm when the tuple popped off the priority queue is $(t,n)$ where t is the target destination and $n <= k$?


texts: Vectorization vs Asynchronous parallelism

texts:
I have taken a course "Programming for Performance" in my college and in the first week of the course, I have come across vectorization and Asynchronous Parallelism. But I am unable to figure out what is the relation and difference between the 2 of them. In the slides, the professor has provided something like this-->

What does it actually mean that parallelism is finer-grained and course-grained?
Also here is another instance where he has tried to point out the difference, here we are given 2 code instance and tried to explain the concept, but I am not able to get that.

What I got is that, in the first one both vectorization and asynchronous parallelism is not possible, since there is a data dependency, but in the second one vectorization can be done as there is no dependency, but asynchronous parallelism is not achievable since, say we have this 2 instances
A(1) = A(2) + B(2) |  A(2) = A(3) + B(3)
So in this case the A(2) may get overwritten by the second instance even before the 1st instance of the code is executed, hence Asynchronous Parallelism is not possible.
Is my understanding of this right?


texts: Average number of comparisons in sorted insertion

texts:
The questions is pretty simple: Given a sorted array of N elements, what is the average number of comparisons made in order to add a new element (let's call it x) in its correct position?
I am using linear search for that task.

So far, I've tried to solve it this way:

# of Comparisons     Probability of A[i] > x (Not sure if correct)
     1                         1/n
     2                         1/n
     3                         1/n
     4                         1/n
    ...                        ...
     n                         1/n

Hence, the expected value would be:

$$E[x] = \sum_{x=1}^{n}x \cdot Pr(X=x)$$
$$E[x] = 1 \cdot Pr(X=1) + 2 \cdot Pr(X=2) + 3 \cdot Pr(X=3) + ... + n \cdot Pr(X=n)$$

Using $$Pr(X = n) = \frac{1}{n} $$ for all n,

$$E[x] = \frac{1}{n} \cdot \sum^{n}_{i=1}{i}$$

and finally
$$E[x] = \frac{n+1}{2}$$

Still, I'm not sure if this is the correct way to solve it, since I'm not sure about my 1/n assumption.

Any insights would be helpful!


texts: How do I solve these questions regarding homomorphism?

texts:
Questions:

Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
Now, give a second example of a homomorphism but this time using two different alphabets, Σ and Γ, for languages A and B, respectively.

Questions to stack overflow:

How do I give the examples above? Do I make the state diagrams? Do I show it through the tuple-definition?
What are some examples of the questions above?


texts: An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

texts: Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$. Of course, this depends on many factors, hence I propose to listen your ideas rather than exact results. May be, is there an article or book, which discusses this topic?


texts: Is Dots and Boxes complementary to the game of Go?

texts:
I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go.
Here's a rough comparative construction starting from the rules of Go:

Start with a checkerboard that contains a grey stone on every red tile.
Each grey stone does not limit the freedoms of player stones, but is initialed by whichever player fills its last open neighbor.
Captured neutral stones may correspond to moves in a normalized game of Go translating red tiles as neighbors.

Little is needed to demonstrate that both games share a focus on encircling quanta of space. The extra move requirement in D&B is a larger distinction, somewhat alleviated by the shared notion of territory. The player who manages to capture more territory has the ability to make more moves, the difference being whether extra moves are afforded midgame or postgame.
My question is whether rule extensions in the above outline, or by others, formally embed D&B with co-Go. The main conflict I see is that D&B is strictly an additive game, where Go can be rewritable. Those versions of Go look to be more compatible with DSPACE.
I suspect that I am stumbling across a few pieces of well-established game theory in the study of regular planar graphs and related subjects. Would anyone kindly point out whether this perspective that D&B and Go are similar is in error?


texts: Why does the cumulative order in which nodes are first visited with Iterative deepening is effectively breadth-first

texts:
I have had comparative algorithm exercise to do about algorithm propoerties such as completeness, time complexity, memory complexity... I discovered Iterative deepening depth-first search algorithm.

On Wikipedia, it is said that it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

I know what breadth-first algorithm is but I don't understand that last sentence... What does it actually means?


texts: How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

texts:
According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he drew the argument from two facts:

Probability of finding $i^{th}$ min cut $\geq\frac{2}{n(n-1)}=\frac{1}{n\choose 2}$
Event of finding $i^{th}$ min cut is disjoint.

So just adding up the probabilities he proved the upper bound of $n\choose 2$.

Now if we consider a tree, as a graph, with $n$ nodes, then we will be able to conclude $(n-1)$ min cuts which is less than $n\choose 2$ cuts ($ n\geq3)$. Am I missing something here?


texts: What topics are related to "concept drift"?

texts:
The term "concept drift" specifically relates to a model changing over time.  However, a similar phenomenon may manifest in, e.g., spatial data, where a topographical model changes behavior at a land/water boundary.  Another example may be in modeling the properties of a chemical substance, which change in behavior across a phase-change.  In general, this sort of situation where a "global" model does not apply is ubiquitous, and I am trying to accumulate examples and related research.

What other terms and research relate to this global-model problem?


texts: What is the generating algorithm for the "komb" instances found on satcompetition.org?

texts: For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the  International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT problems with planted solutions labeled "barthel," "qhid," and "komb." I have been able to determine that "barthel" is referring to this procedure, and "qhid" is referring to this procedure. The "komb" instances may refer to this procedure, based on the references given in the article here on pages 60-62. Note on page 61, in the first sentence of section "Our Approach," 3 references are given, namely, the first 3 references given above. Can anyone confirm the procedure for generating the "komb" instances in the SAT Competitions? (See satcompetition.org for more details.)


texts: What is the difference between transmission delay, queuing delay, and processing delay?

texts: My book defines queuing delay as the time the packet waits to be transmitted onto the link. It defines transmission delay as the amount of time required to push all of the packet's bits onto the link. It defines processing delay as "the time required to examine the packet’s header and determine where to direct the packet". I do not completely understand the difference. The first two sound very similar and processing delay sounds like it is part of one of the other two. Can anyone explain me the difference?


texts:
For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know much about, to solve it).

As input we obtain a matrix (3x4) of connections ("|" or "-") which we must decode in the least amount of movements, to avoid that the bomb explodes. As an output inform one of the possible solutions.

The decoding consists in that the matrix must contain only characters "-". To achieve this they tell us that if we move an element of the matrix, both the values of the column and row of the matrix change. For example if I move the element (0,0) of the matrix in this case the "-" change to "|" and vice versa in the column 0 and row 0. In the image (where (1) represents the input matrix and (2) the decoded matrix) a solution to inform would be:

move (0,3) and  then (2,1)

How to design an algorithm that solves this problem without using backtracking directly?


texts:
I have to find computational complexity of an expression for Euclidean distance

d(x,y)= {(x1-x2)^2 + (y1-y2)^2}^1/2

But I have certain confusion because of which I am unable to proceed. Firstly there are two variables. Secondly since there is a root ,what will be  its effect? If there were no roots, I can understand its worst case complexity would have been O(n^2).

I will really appreciate if someone can enlighten me in this regard
        Thanks in advance for your spending valuable time!

Update

I assume that my program will run on abstract machine RAM.


texts:
I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ?

Example of use of absolute values:

Minimize |a+b+c| + |a-c| s.t.
 |a| + b > 3
 | |a| - |b| | <= 5
 | |b| - 3 | = 0


texts: How to search an almost sorted array faster than O(n) time?

texts:
Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1.

Develop an efficient recursive algorithm to find j such that A[j] = z, where A[1] ≤ z ≤ A[n]. The algorithm must be more efficient that O(n).

Binary search was my first thought but you would still have to search through both halves because it doesn't have to be from low to high.


texts: The set of all vertices, such that each vertex in the set has a path to exactly $k$ vertices

texts:
I need to find algorithms for both undirected and directed graphs, with no assumption on them being connected. Also the algorithms must be $O(V+E)$, where the undirected one should not depend on $k$.

I have ideas for both, i'm just not very sure about the directed version, because I'm not sure on how to approach the correctness proof.

For the directed version, I thought about finding all the SCC's with two DFS runs, and then running a topological sort on the graph created by representatives from each SCC. Afterwards, i'll flip the edges and start a DFS from the end vertex. For every SCC node I visit i'll increment a counter by the number of nodes in the SCC I visited. If while vising a SCC node the counter shows $k+1$ nodes, all the nodes in the SCC will be added to the set. At this point the algorithm will go back as though we reached a leaf.

For the undirected version, I can just do run a BFS/DFS for every disconnected component to find all the connected components. If a connected component has exactly k+1 nodes, then all the nodes in that component belong to the set.

Any help regarding the directed version will be great, thanks!


texts: Probability of k-clique in a random graph

texts:
I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$.
$X_k$ is the random variable which count the number of k-cliques in a random graph.
I already know $E[X_k] = \binom{n}{k}(\frac{1}{2})^{\binom{k}{2}}$.
I don't know exactly how to find the exact value of k.
I know $P[X_k \geq 1] \leq E[X_k]$ for Markov inequality but I'm not sure that this is helpful.
Thanks in advance


texts: Do I require loading in this example of load store architecture?

texts:
I'm currently revising for my Concurrent Programming exam and I'm going through the past papers and one question poses the following process:

Process P1
 integer x;
1a: x = a + a;
1b: b = x;
end P1;

and asks the following question:

  Rewrite processes P1 to take into account execution using a ‘load/store’
  architecture.

For 1a  I have broken it down into this:

load a into R
add a to R
store R into x

Where R refers to the register as per my notes.

My trouble lies in 1b. Do I need to load x into R before I store R into b or can I simply bypass the register and store x into b.


texts: Regular expression for the strings without a particular substring

texts:
How can we design a regular expressions without particular substrings.
The goal of this is to create language L which won't contain a particular substring (i.e. 110)

for the case of a regular expression without substring $110$, I Was thinking of: $\require{cancel}\cancel{(101)^*+}(010)^*+(10)^*+(\cancel{1}1)^*+(\cancel{0}0)^*+(01)^*$ but is that over excessive?

Then for example, I crossed out (101)* because obviously if you have two of those 101101, a subset of that will be 110, which we don't want.

Notes:

Question has been edited since it gained attention in the past few days. Also see comment for justification.


texts: KD-Tree implementation with lat/lon coordinates

texts:
I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use euclidean distance instead ?

If not, can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ?


texts: Why is C's void type not analogous to the empty/bottom type?

texts:
Wikipedia as well as other sources that I have found list C's void type as a unit type as opposed to an empty type. I find this confusing as it seems to me that void better fits the definition of an empty/bottom type.

No values inhabit void, as far as I can tell.
A function with a return type of void specifies that the function does not return anything and thus can only perform some side-effect.
A pointer of type void* is a subtype of all other pointer types. Also, conversions to and from void* in C are implicit.

I am not sure if the last point has any merit as an argument for void being an empty type, as void* is more or less a special case with not much relation to void.

On the other hand, void itself is not a subtype of all other types, which as far as I can tell is a requirement for a type to be a bottom type.


texts: Determining if $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} is not a regular language using Pumping Lemma?

texts:
In short, is this similar to how $a^nb^n$ is not a regular langauge?

$L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}

For instance, if we have the string  $w=a^psb^p$, and we know that $|xy| \le p$, there would simply be a disproportianate amount of a's or b's regardless of where we put $y$ ?


texts:
Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-costs are compared and where they aren't, so which version is the right one? What is the benefit of doing either?

g-cost: Cost from start to node

h-cost: Heuristic from node to end

f-cost: g-cost + h-cost

Edit: From  Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"

"Select the open node n whose value of f is smallest. Resolve ties arbitrarily, but always in favor of any node n ∈ T."

It is stated that "T" is the goal set (I thought there was only one goal node?)

My interpretation is that if the goal node is in the open set, then it should be picked first, meaning resolving ties via h-cost is certainly a correct way because h(end) = 0.


texts: Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem

texts:
My question is not for a solution to the problem, though I do need to put thought into it but rather my question is if this conceptual problem has a name or has been addressed at already in computer science.

I want to create a list of numbered defines, each uniquely mapped, and divided into groups based on type. The goal is a design that does not require renumbering or shifting when reaching the end of the previously allotted space for a certain type. An example may help

    // Dogs (1 to 3 available)
    define DOG_1            1
    ....
    define DOG_3            3

    // Cats (4 to 6 available)
    define CAT_4            4
    ....
    define CAT_6            6

    // Pigs (7 to 10 available)
    define PIG_7            7
    ...
    define PIG_10           10

Now if I want to add space for more dogs it requires shifting etc.

This problem seems similar to something found in memory allocation/fragmentation. I want to find literature that addresses the problem if it exists.

Thanks,
Godrick


texts: Can a schedule with cyclic precedence graph still be serialisable?

texts:
We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict serializable.

One way of Testing conflict serializability is using Directed graph as mentioned http://www.cburch.com/cs/340/reading/serial/index.html

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (*) we can say maybe this schedule be a serializable . (i.e we cannot surely determine it's serilizabe or not, just we know it's not conflict serializable)

My inference is right? any idea?


texts: Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

texts:
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$

As pointed out by sdcvvc, a word in this language can also be described as the concatenation of two words of the same length the hamming distance of which is 2 or greater.

I think it's not context free but I'm having a hard time proving it. I tried intersecting this language with a regular language (like  $ \ 0^*1^*0^*1^* $ for example) then use the pumping lemma and \ or homomorphisms but I always get a language that is too complicated to characterize and write down.


texts: Ski design usaco problem alternative solution

texts:
problem statement for SKICOURSE is this

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property
to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.

and Naive way of doing this problem is like this

The problem can be solved with different approaches. A simple idea is of course brute-force -- try all possible elevations and find the minimum amount. We can try all possible values as follows: try the modification for elevation interval (0,17) then (1,18), (2,19), ..., (83,100). For each elevation interval (i,i+17), we need to calculate the cost for each hill j:

If the elevation of hill j, say hill[j], is in the interval (i,i+17) then there is no cost.
If it is less than i then the cost increases by (i-hill[j])^2
If it is greater than i+17 then the cost increases by (hill[j]-(i+17))^2

Is there any better way of doing this i mean if limits exceed drastically


texts: Is monoid the category for untyped lambda calculus?

texts: If cartesian closed categories are the model for simply typed lambda calculus, then can it be said that a monoid is a categorical model for untyped lambda calculus?


texts: how to determine the optimal value of k for constructing the k-nearest neighbor graph?

texts:
I want to build a non-oriented k-nearest neighbor graph for use in a clustering method (unsupervised learning). The nodes of the graph correspond to points defined in a multidimensional real space and the edges to the distances between the points. This graph must be optimal (not strictly speaking) on two criteria. The first one is that it should not be very time-consuming to build. The second is that it must be a connected graph. Based on these two criteria, how could one automatically determine k for a given dataset?

Thank you in advance for your clarification and answers.


texts: Is potential causality relation equals to set of consistent happens before relations?

texts:
In a book dedicated to distributed algorithms, I found the following definition - potential causality diagram is consistent with happens before diagram if potential causality relation between system events is a subset of happens-before relation. So far so good.

But then I have read following claim potential causality diagram equals to the set of happens before diagram to which it consistent with. But how that is possible? I mean that cardinality of potential causality relation is less than the cardinality of happens before relation to which it consistent with. How may potential causality relation be composed of union of such happens-before relations? I agree that potential causality relation may be composed of a set of happens-before relations, but from my point of view happens before relations in such case should be subsets of potential causality relations? Could you explain what I missed?

Update: Quotation from the book. "Given a potential causality diagram $(E, \xrightarrow{p})$, a happened before diagram $(E, \rightarrow)$ is consistent with it if $\xrightarrow{p}\subset \rightarrow$.

is consistent with

Observe that $e_2 ->f_4$ but $\neg(e_2 \xrightarrow{p} f_4)$. A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it.

Vijay K. Garg. Elements of Distributed Computing (Kindle Locations 301-302). Kindle Edition.


texts: Is there a linear sorting algorithm given an oracle that finds kth smallest item?

texts:
Given a machine that can compute the kth smallest item of an Array A in $O(\sqrt n)$ time. Find a recursive function that can sort A in linear time corresponding to $n$ which is the length of A.
First I tried to optimize some of the sorting algorithms I knew using this new property but the best I could do was $O(n^{3/2})$ and currently I'm wondering whether if it is possible or not.


texts: Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?

texts:
I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by:

$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$

the number of turing machines with $n$ states and $k$ tape symbols is $(2kn+1)^{kn}$.

However, looking at the definition, shouldn't it be $(2kn)^{kn}$ instead?


texts: Is paradox recognition paradoxical or not paradoxical?

texts:
Russell's paradox: The set that contains all the sets that do not contain themselves. Does it contain itself? It contains itself if and only if it does not contain itself.

Russell's paradox for the lambda-calculus: The functions that may not be applied to themselves when combined with themselves, they negate themselves.

lambda calculus uses anonymous functions called lambda-expressions. So, the paradox re-stated in lambda-calculus terms becomes:

The lambda-expressions that may not be applied to themselves when combined with themselves, they negate themselves.

If such a lambda-expression is encoded into a string w, then input to a Turing machine, will the Turing machine (Paradox Recognizer machine) accept it? not accept it: reject it? or loop forever?

Thanks in advance for your comments.

Rafee Kamouna.


texts: Problem easy for humans and hard for general purpose machine learning, not needing external context?

texts:
There are many problems that people can solve more easily than a machine learning algorithm.  Often this is attributed to the extra context we have access to.

Image segmentation is an example of a problem that people are good at, but algorithms are not good at, probably because people have lots of external contextual knowledge they bring to bear on the problem.  To date, the best techniques use a human in the loop, such as this technique called click carving from HCOMP 2016.

Are there problems that people can solve more easily than most or all machine learning algorithms, where people do not need to depend on access to external context?

Here is another example that is easy for people but hard for a particular algorithm implementation called XGBoost.  A human can easily fill in the missing shapes with 100% accuracy, but XGBoost cannot score above 50% accuracy, and its accuracy drops as it gets more training data.  Neural networks also seem to have difficulty with this problem.

Note that the person does not need external knowledge about the problem that the algorithm does not have, in order to perform better.  All the person needs to see is the configuration of shapes, and they can guess from that what the missing shapes are.  The only information the human needs is that the simplest description of the data is most likely the best description, and that the training data is randomly sampled.  Both items of information are used in designing XGBoost, and most ML algorithms for that matter.

Are there other concrete examples like this?  Historically, the XOR problem showed that single node perceptrons were inadequate, leading to today's neural network.  Besides that, I do not know of any other historical examples.


texts: Why updating only a part of all neural network weights does not work?

texts:
I am having a problem with my program of deep neural network using Theano. In my deep neural network, I have several layers of neural network to predict an output given a certain input. Because of an issue when compiling theano, I have to debug my program step-by-step. Since Theano gives me an error when updating weights of some layers, I perform a check by calculating the derivatives of only the last layer (using tensor.grad if you know Theano). But if I do that then the network will not update properly and the cost does not decrease and the output is nowhere close to the true output. It seems like updating the weights of only the last layer does not seem to train the network to learn.

Is it mandatory to update all weights of all layers in a deep neural network to decrease the cost? What I understand is that if I fix the values of all weights except the weights of the last layer, it should still be able to predict correctly after many rounds of training (of course, the only layer that is learning is the last layer, but I accept that, I only needs the predicted values to be close to my true values while training).

I hope my explanation make sense to you. If you do not understand any part, I will gladly provide you more information.


texts: Weaker conjectures to prove in order to arrive at P =/= NP

texts:
We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the much sought-after truth.

My question is the following: if tomorrow a proof of P $\neq$ NP would appear, what would be all the CS open problems that such a proof would solve?


texts: Spatial index search that returns sorted results

texts:
I need to perform a spatial index search while also sort the results by one of the dimensions.

Backstory:

I have a map with lots of 2D objects and when the user interacts with the map I need to filter only those objects that are inside the screen rectangle and at a visible distance (not bigger than the whole screen, not smaller than a single pixel). To do this, I want to use a 3D R-tree library.

I do not understand the math but I found a library that perfectly suits my needs, so far so good.

But things get complicated. Sometimes I need to draw labels for map objects that are so small they not even visible. The user will see the label and he will zoom to the object. (This is not a regular map). So I filter all objects that are inside the screen rectangle, are smaller than the whole screen and bigger than 0. So far so good. To draw only labels that do not overlap I will use another spatial index tree (2D). But I need to start drawing labels for the big object first, drawing labels for smaller objects only if there is a space on the screen. That means I need the results of the 3D spatial search sorted by the Z distance (or Z size).

The number of results from the spatial search can be huge, simply calling a sort function is not feasible. I could sort all the objects by Z size during initialization, but then won't know which are inside the screen rectangle. I need to somehow combine the efficiency of the R-tree with the ability to have sorted results.

Is there a variant of R-tree that will return search (intersection) results sorted by one of the dimensions, efficiently?


texts: Which parser has the highest reduce moves?

texts:
From what I have learned the number of reducing moves in the parsers are
generally in the order

LR(0)>= SLR(1) >= LALR(1).

But I am unable to understand where should I place CLR(1) in this category?

Is it CLR(1)>=LR(0)>= SLR(1) >= LALR(1) ?


texts: Why use binary search trees when hash tables exist?

texts:
Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n).

So, in a course on data structures, is the study of BST's of any value except as a historical note?


texts: Proving equivalence of two Turing machines

texts:
I have the following Turing machine: A 2R-3L-TM is similar to a standard TM with the change in which the head can only move either 3 cells to the left or 2 cells to the right (those are the only possible moves).
and I want to prove equivalence between 2R-3L-TM and standard TMs (one tape and the head can move single cell right or left only). I only want to prove one side, meaning that for every standard TM M_1, there is a $2R-3L-TM, M_2, s.t L\left(M_1\right)=L(M_2)$. I started the proof on the right side but not sure how to prove the triple left side, my proof so far:
Let M2, a TM with 2R-3L, a set of states Q and transition function \delta. Let us define an equal standard machine, M2. We would do so by describing how TM M1 works in the implementation level:

If M1 moves to the right, do the same for M2 however mark the position with ‘ * ‘     transition to a new state at which the machine always moves to the right and then transitions to the original target of the RR transition
If M1 moves to the left...

How can I continue my proof and is my proof for the right side correct?


texts: Axis aligned rectangles: why is A an ERM in the case of infinite domain?

texts:
I'm working on a problem 2.3a in Shalev-Shwartz/Ben-David's Machine learning textbook, which states:

An axis aligned rectangle classifier in the plane is a classifier that assigns 1 to a point if and only if it is inside a certain rectangle. Formally, given real numbers $a_1\leq b_1, a_2\leq b_2,$ define the classifier $h_{(a_1, b_1, a_2, b_2)}$ by
$$ h_{(a_1, b_1, a_2, b_2)}(x_1, x_2) = \begin{cases}1&\textrm{if $a_1\leq x_1\leq b_1$ and $a_2\leq x_2\leq b_2$}\\ 0&\textrm{otherwise}\end{cases} $$
The class of all axis aligned rectangles in the plane is defined as $\mathcal{H}_\mathrm{rec}^2 = \{h_{(a_1, b_1, a_2, b_2)}:\textrm{$a_1\leq b_1$ and $a_2\leq b_2$}\}$...rely on realizability assumption.
Let $A$ be an algorithm that returns the smallest rectangle enclosing all positive examples in the training set. Show that $A$ is ERM (empirical risk minimizer).

I don't understand why $A$ would be ERM, when the domain/instance space is infinite. Below is the counterexample I considered to this claim.
For simplicity, consider the one-dimensional case, where the rectangles would be intervals. Sample instance $x\sim \mathcal{U}_{[0, 1]}$ from a uniform distribution over $[0, 1]$, where the labeling function $f:[0, 1]\to\{0, 1\}$ is defined by
$$
            f(x) = \begin{cases}
                1 &\textrm{x = 0 or x = 1}\\
                0 &\textrm{otherwise,}
            \end{cases}
        $$
then the realizability assumption holds as there exists an $h^*$ whose rectangle described by the singleton $\{1\}$ has an error set $\{0\}$ of measure $0$. However, in the case of a particular sample
$$
            S = \{0, 1/4, 1/2, 3/4, 1\},
        $$
the smallest rectangle $A$ is the interval $[0, 1]$, and the consequent classifier $h_A$ has an empirical error of $L_S(h_A) = 3/5$. In contrast, the classifier $h^*$ has empirical error $L_S(h^*) = 1/5$, a lower error than the classifier described by $A$, even though it doesn't contain all positive examples. Therefore $A$ does not minimize empirical error.


texts: Is impredicative Set consistent with the excluded middle?

texts:
While studying Coq, I found a few references that impredicative Set might not work well with classical axioms, in particular the axiom of choice.

I'm working on a dependent type system based on the calculus of constructions (with Prop and Set), on which I intend to add Peirce's law on sets, as in the computability side it represents call/cc (capturing/resuming the whole computation).

My question is: is the calculus of constructions* with an impredicative Set, with the excluded middle working on sets (precisely, forall P: Set, ((P -> False) -> P) -> P being of type Set), without the axiom of choice, consistent? I didn't manage to find a reference for that.

(* Would inductive types make any difference, from CoC to CIC?)


texts:
In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?

Example- $(1,3,4)$ are denominations of coin.
If I want to pay $Rs.6$ then the smallest coin set would be $(3,3)$.
This solution set cannot be found by greedy Algorithm because it does not satisfy $(\frac{4}{3} > \frac{3}{1})$.


texts:
I have developed two algorithms and now they are asking me to find their running time.
The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are addition and multiplication.

In general for lists the running for these two operations are ($x,y$ are the lists lengths):

Addition: Time $O(x+y)$, space $O(x+y)$
Multiplication: Time $O(xy \log(xy))$, space $O(xy)$

Can someone help me to find the running times of my algorithms?
I think for the first algorithm it is like stated above $O(x+y)$, for the second one I have two nested loops and two lists so it should be $O(xy)$, but why the $O(xy \log(xy))$ above?

These are the algorithms I developed (in Pseudocode):

 PolynomialAdd(Poly1, Poly2):
 Degree := MaxDegree(Poly1.head, Poly2.head);
 while (Degree >=0) do:
      Node1 := Poly1.head;
      while (Node1 IS NOT NIL) do:
         if(Node1.Deg = Degree) then break;
         else Node1 = Node1.next;
      Node2 := Poly2.head;
      while (Node2 IS NOT NIL) do:
         if(Node2.Deg = Degree) then break;
         else Node2 = Node2.next;
      if (Node1 IS NOT NIL AND Node2 IS NOT NIL) then
         PolyResult.insertTerm( Node1.Coeff + Node2.Coeff, Node1.Deg);
      else if (Node1 IS NOT NIL) then
         PolyResult.insertTerm(Node1.Coeff, Node1.Deg);
      else if (Node2 IS NOT NIL) then
         PolyResult.insertTerm(Node2.Coeff, Node2.Deg);
      Degree := Degree – 1;
 return PolyResult;

 PolynomialMul(Poly1, Poly2):
 Node1 := Poly1.head;
 while (Node1 IS NOT NIL) do:
      Node2 = Poly2.head;
      while (Node2 IS NOT NIL) do:
           PolyResult.insertTerm(Node1.Coeff * Node2.Coeff,
                              Node1.Deg + Node1.Deg);
           Node2 = Node2.next;
      Node1 = Node1.next;
 return PolyResult;

InsertTerm inserts the term in the correct place depending on the degree of the term.

 InsertTerm(Coeff, Deg):
 NewNode.Coeff := Coeff;
 NewNode.Deg := Deg;
 if List.head = NIL then
    List.head := NewNode;
 else if NewNode.Deg > List.head.Deg then
    NewNode.next := List.head;
    List.head := NewNode;
 else if NewNode.Deg = List.head.Deg then
    AddCoeff(NewNode, List.head);
 else
    Go through the List till find the same Degree and summing up the coefficient OR
    adding a new Term in the right position if Degree not present;


texts:
I am currently learning assembly programming on wombat 4, I am looking at Frame pointers. I understand exactly what a frame pointer is: it is a register and are used to access parameters on a stack. But i'm confused on how they affect the program counter and why they are preferred over normal registers.

Could some one explain, please.


texts: How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

texts:
$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
                           $\mid \textbf{other} $

This grammar is called as Dangling Else Problem . However the ambiguity is resolved by parser as described as follows

  In all programming languages with conditional statements of this form, the first parse tree is preferred.
  The general rule is, "Match each else with the  closest unmatched then"

It is rarely built into productions

$\textbf{stmt} \to$ $ \textbf{matched_stmt}$
                          $\mid $ $\textbf{open_stmt}$

$\textbf{matched_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ matched_stmt $ \textbf{else}$ matched_stmt
                          $\mid $ $\textbf{other}$

$\textbf{open_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ matched_stmt$ \textbf{else}$ open_stmt

However this grammar is also ambiguous . Moreover no grammar is there that could eliminate ambiguity problem of Dangling else problem . Hence we can say that dangling else problem in also inherently ambiguous

Source : Compilers: Principles, Techniques, & Tools -Aho & Ullman

My question is How to prove that  Ambiguity is still present  in this resolved Production of Dangling Else Problem   ? What I know is that if two different parse trees are possible then the grammar in ambiguous . Does any such parse trees possible for the resolved grammar ? If so could u please give an example parse tree for the same


texts: What determines the entropy of a program's source code?

texts:
a few days ago I asked a question about the limits of compression:
Can PRNGs be used to magically compress-stuff?

The idea common to all the answers was that if you consider all programs
of length < k (Let's call this set $C_k$), then there is only a finite number of possible outputs generated by programs in $C_k$ (let's call that set $S_k$).

In the comments, I asked a followup question roughly equivalent to  "what determines which messages are possible outputs?" and have been thinking about this ever since.

It seemes clear that what determines that is the program that executes
the program. If we ignore TM's and think in terms of source code, then
the output of a piece of code depends only on the syntax and semantics
of the programming language. So the language design determines
the contents of $S_k$. There are some interesting corollaries:

All program transformations that do no affect the AST nor enlarge the program beyond k bits will produce programs that generate the same output.
All refactorings, which might alter the AST but preserve all input/output
relationships, will do the same if they do not inflate the size of the source code.
a PL that provides multiple constructs ("There's more then one way to do it")
for achieving the same result (control flow constructs, for example) will , generally speaking, have more programs of length < k which generate the same output and so a smaller $S_k$ then a similar but "slimmer" PL.

This brings me to the following question: If I consider all programs
in $C_k$ that generate the same output (it's an equivalence relation)
and then proceed to compress them, what would be the results? Would
the equivalent programs compress down to roughly the same size or not?
Does the compressability depend on the meaning of the program (which
is identical) or the bit sequence (which is not)?

A statement given in the answers to the previous question is
that the entropy of a bit sequence determines how compressible it is.
Is that entropy determined by the input/output relationships encoded
in the program, or by it's bit-representation in language X?
What's the right way to think of this?

update
Since a program describes a computational process
rather then merely output, the notion of equivalence
suggested really doesn't indicate me much about
the relative complexity of programs which are equivalent
by that definition.


texts: Running time for algorithm to compute the minimum size dominating set

texts:
I'm trying to write an algorithm to compute a minimum size dominating set of an undirected graph G(V,E).

I think the following works:
1) Sort vertices by number of edges (descending)
2) Add the first vertex to the set D (which will be the dominating set output)
3) Delete all vertices connected to D by one edge
4) Add the next vertex
and then repeat until you run out of vertices.

I was wondering what the running time of this would be?


texts: Are regular grammar languages defined from "accepting" states?

texts: In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular grammars too? They are defined by using 4 sets (terminal, non-terminal, initial non-terminal, rules) so there is no such thing as "accepting states" at the definition. The language of a regular grammar are the words that can be produced from that grammar, but do they always end in an "accepting" state?


texts: Learning a small disjunction using an input distribution of our choice

texts:
I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form

$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}.$$

I don't know the values of $i_1,\dots,i_k$, but I do know $k,n$.  My goal is to recover $i_1,\dots,i_k$ from the value of $f$ on randomly chosen inputs, using as few evaluations of $f$ as possible.

There's a twist.  I can choose any efficiently sampleable distribution $D$ on $\{0,1\}^n$ that I want, depending on $k,n$.  A referee will pick $f$, randomly sample many values of $x$ from $D$ (iid), and then give me $(x,f(x))$ for each such $x$.  Then, my ultimate task is to infer $i_1,\dots,i_k$.

I'm looking for an efficient algorithm to select $D$ and then recover $i_1,\dots,i_k$, given the pairs $(x,f(x))$.  How efficiently can this be done?  What distribution $D$ is optimal?  The most relevant complexity measure is probably the number of pairs needed.  Randomized algorithms are OK.  I'm particularly interested in the regime where $k \ll n$.

This is a generalization of a prior question of mine, where I showed that if we take $D$ to be the uniform distribution on $\{0,1\}^n$ then $\Theta(2^k \lg n)$ pairs are necessary and sufficient.  However, it seems likely that the uniform distribution is not optimal.  I suspect we can do better by choosing a distribution $D$ that is biased towards values of $x$ with lower Hamming weight.

On first glance, it feels like maybe we can restrict attention to distributions $D$ that is symmetric (i.e., $x$ and $\pi(x)$ have the same probability, for all permutations $\pi$ on the $n$ bits).  For instance, we could consider a distribution $D$ where the bits of $x$ are iid Bernoulli(p), for some parameter $p$.  Is this right, and if so, what is the optimal distribution $D$ and how many pairs does this mean we will need?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).


texts: In the Traveling Salesperson Problem, is the shortest tour the same regardless of the start/return city? How do you prove it?

texts: This is the form of the problem where you start at a city, visit every other city, and return to the start city. Since you "return" to every city in the completed cycle, it seems intuitive that the cycle would be the same regardless of the starting city.


texts: How to show all false outputs in a circuit?

texts: I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks!


texts: More the number of for loops greater the problems solved

texts:
This is more a formal language theory question.

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

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

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

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

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

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


texts: Is this DO LET sugar considered pure Lambda calculus and nullipotent / side-effect-free?

texts:
I'm thinking these familiar concepts of DO and LET/LET* in the context of Lambda Calculus (LC).

LET is an abbreviation for this LC expression:

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

and LET* is an abbreviation for this LC expression:

(LET* a 1 b 2 e) = (λ a . (λ b . e 2) 1)

where e is the body of the function. LET* just enables to use former variable inside latter variable in the following way:

(LET* a 1 b a e) = (λ a . (λ b . e a) 1)

DO is an abbreviation too and can be used in conjunction with LET's to achieve same than LET*:

(DO (LET a 1) (LET b 2) e) = (λ a . (λ b . e 2) 1)

So I have three different shorthands to construct LC expressions. Now, my questions is that is this syntactic sugar throwing me out from pure LC (or functional programming in general sense) and am I introducing side effects by this syntax?

In a way it looks like it, but on the other hand these three shorthands are only abbreviations and they translate to Lambda Calculus expressions that are well defined and reducible as any LC expressions.


texts: Help me identify the type of Knapack Problem I am dealing with

texts:
I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the problem itself.

The Problem

I have a theoretically large model train track with dozens of short identical trains on it. I need to buy some power supplies to power my model trains.

The track is split in to equal length sections. I have a data structure that describes the power consumption for each individual length of track based on the movement of the trains. Each length has a peak power consumption (for example, when a train needs to accelerate), and an RMS power consumption.

I need to hook my track up to the power supplies, but I can only power contiguous lengths of track for each power supply. I can't power track section 1 with power supply A, then skip track section 2 and power track section 3 with the same power supply A. I have to power either track section 1, 2, and 3, or just 1 and 2, or just 1.

There is only one type of power supply that has a peak and RMS power output limit. When looking at a combination of lengths of track, I combine their power profiles to get a new RMS and peak power for the combined section. If one of these values goes over the power supply limit, it will not work. Assume that no individual length of track on its own will violate the RMS/peak limit of a power supply.

You cannot/will not have more than 1 power supply per length of track.

You can have at most 10 lengths of track on one power supply. You cannot have 11+ lengths of track hooked up to one power supply. The cord is not long enough.

The goal is to FIRST minimize the number of power supplies (these things are expensive) I have to purchase and THEN determine the most optimal distribution of power such that no power supply is loaded significantly heavier or lighter than any other.

Another way of looking at it is:

Limits

All knapsacks have the same capacity (10 items max).
All items have the same volume.
All items have different weights (densities).
All items come in a specific order (a circuit) and must be put into a knapsack with only adjacent items.

Goals

Minimize (optimize) the number of knapsacks first.
Distribute the items as equally as possible such that no backpack is lighter or heavier than it should be.

Considerations

I might be asking more than one question here: One about optimization and the other about the knapsack classification.
Is this actually a knapsack problem since the items don't have a value/profit?
Does the adjacent/contiguous limit I put on the problem make it easier or harder to solve?
Should I be considering anything from graph theory because my track is like a bunch of nodes and edges? Or is that an unnecessary complication.

The question still remains: Classify the type of knapsack problem, or at least extract the correct one from the above problem statement.

Please point me in the right direction.

Notes

The weights can be rounded to integers if that helps.


texts: Machine learning algorithm(s) for recognizing simple graph patterns

texts:
I generate some simple graphs based on usage stats of a website, and they may look like these:

I call the 'pattern' on the left 'convergence', and the 'pattern' on the right 'divergence'. The terms 'convergence' and 'divergence' are loosely and visually defined, and they simply means that the two curves either become closer and intersected (decreasing difference in Y while increasing in X) or become apart (increasing difference in Y while increasing in X)

Of course, the curves may neither converge nor diverge. An extreme case of such case is they may evolve more or less parallel to each other.

My problem is to recognize the convergence and the divergence patterns. This may be trivial as done visually by human, but I want to automate the task using an algorithm, and likely a ML algorithm. "Pattern recognition' comes to mind as a (broad) area relating to this kind of problem.

I have some very high-level idea about a possible approach: first manually label some existing graphs as 'convergence', 'divergence', or 'other', and then use a set of these categorized graphs/images to 'train' the ML algorithm in the hope that the algorithm can recognize the patterns on its own after proper training.

My specific questions are:

What are the recommended ML algorithm(s) for this problem? And any pointer to the theory and implementation of such algorithm(s) is appreciated.
I may be terribly ignorant, but: does such a ML algorithm operate on the graph/image directly or does it operate on the underlying data points that make up the graph? In other words, what would be the input to the algorithm? A series of images or a bunch of numbers?


texts: Algorithm for searching in BST with only <

texts: How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.


texts: Proving NP hardness in Puzzle with SAT reduction

texts:
Introduction

I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1 and  Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf  on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

  x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

  x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

  ¬x4 = valid grids and puzzles not following shift(L)

  ¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that the language used to generate these grids never have missing instances?


texts: Algorithm to sort elements of an array under uncertainty

texts:
I have an array of $n$ elements. Each element is basically the mean of gamma distribution and the actual value of the element is picked from that distribution. Assume the parameters of distribution (scale and shape) are different for different elements and not known.

Now I wish to sort these means so that, after replacing each mean with a value randomly chosen from the corresponding gamma distribution, the probability that the realization is in sorted order is as large as possible.  Is there an efficient algorithm for this task?


texts: Data structure and structural relationships

texts:
“Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values, they involve important structural relationship between the data elements.”

  Knuth, Art of Computer Programming, vol. 1 (Fundamental algorithms), 3rd edition, p. 252.

My question is what does “structural relationship between the elements” mean. How are these structures different from any mathematical structure?


texts: Is there a single valid definition for a Turing Machine, or is it mutable?

texts:
I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook.

My textbook says the following:

$$M=\langle Q,\Sigma,\Gamma,\delta,q_{0},q_{accept}, q_{reject} \rangle$$

where:

$Q$ is the set of states,
$\Sigma$ is the input alphabet not containing the blank symbol $\sqcup$,
$\Gamma$ is the tape alphabet, where $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$,
$\delta: Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$ is the transition function,
$q_0\in Q$ is the start state,
$q_{accept},q_{reject}\in Q$ are the accepting and rejecting states, respectively, and $q_{accept}\neq q_{reject}$

While Wikipedia states

  Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  $Q$ is a finite, non-empty set of states
  $\Gamma$ is a finite, non-empty set of the tape alphabet/symbols
  $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols
  $q_0 \in Q$ is the initial state
  $F \subseteq Q$ is the set of final or accepting states.
  $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

There are obviously a few similarities, but there are a few differences as well. Namely the ordering of the items in the 7-tuple $M$. Also, my textbook has three entries for separate special states, and the Wikipedia entry has only two - My book doesn't have a special element just for the blank character.


texts: Analyzing rules of articles in languages

texts:
I'm interested in finding a solution for the following problem:

problem space: any language that has more than 1 article
let's take German language as example. So the articles in German are "der", "die", "das". - every word has an article as prefix and you must use the article. for example you can't say just "Auto"(car), you must say "das Auto".
If you are not a native German speaker, you have bad luck, because you have to memorize the article too, when learning a new word, since there are only 3-4 rules to know which word takes which article. And those rules are perhaps about max. 10% percent of the vocabulary. (for example if a word ends with "-ung", it takes "die")

So here comes the funny part: as a non-native-German-speaker, i wanted to analyze the language from an IT-point of view and asked some friends of mine random words with the following properties:

first I reduced the input set from "any German word" to "a German word", for which no known article rule exists".
then I extended the input set with "made up words", which do not exist.

Every candidate had the same answer for German words, which should be not surprise. But when I asked them per word "why do you think/feel that the article of the word is "der/die/das"?" they couldnt give an answer. They just know it, without knowing why.

Here comes the real hammer: every candidate had the same answer for any made-up non-German word. I say anything, make any meaningful voice, and they all give the same answer (ie. article).

I'm pretty sure that I'm not the first human being in the world who made thoughts about this topic. And I'm interested in any scientific papers/research about that topic.
By the way, what I definitely do NOT need is, any method (like neural networks) which outputs a pure mathematical function. I thought about following possibilities:

focusing on feelings of subjects psychologically (I think it can be managed with colors somehow etc.)
analyzing the words statistically according to their syllable structure

Where can I begin? What are your suggestions? Are there any Machine Learning research about that topic?


texts: Reduce set partition search to decision?

texts:
I'm a little lost and don't know how to approach this problem.

  Show the partition search problem can be poly-time reduced to the
  partition decision problem, the partition decision problem takes an
  input set of numbers and returns true if there is a subset of the
  initial set that sums up to half the total sum of the initial set.

With problems like ham-path search, clique search and SAT search, the key was to build the solution one piece at a time using the results from the decision "oracle". But I need to know how to approach this problem.

Initially, I thought about removing elements from the set while verifying if there is a partition in the remaining set, which led me nowhere. Now I'm wondering if adding elements to the initial set would have any results.
I noticed if the initial set has a partition, adding elements to the set would then only have a partition if the added element is even, but I don't see how this can generate a subset of the original set that satisfies partition search.
Am I going off the wrong track? Any pointers would be appreciated.


texts: I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never heard about it and I don't understand how it may have deeply contributed to the computer theory. It seems quite cited in academic papers though.


texts: What kind of LTL formula can be represented by DBAs

texts: I am looking for the portion of LTL formula that can be expressed by deterministic buchi automata. Is there any classification of this such?


texts: How balanced is a binary tree in the average case?

texts:
For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's a generalization, but it's also a reasonable one.
But in real algorithms, we're typically not interested in the rare worst case performance, much less the best case performance. Rather, we're interested in how the algorithm performs in typical use. This begs an interesting (and useful) question: How balanced is a binary tree on average? Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?


texts: Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph

texts:
Given is an undirected weighted graph with N nodes, with each node having a property/Value.

Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a constraint on the maximum distance/weight than can be traversed over the entire graph i.e. the sum of edge weights of best path found should not exceed the the constraint specified on the weight. The best path should begin and end at the same node.

I am trying to solve the above as a knapsack problem while using Djikstras,seems too complex to put in code. Would appreciate some help with alternate methods if my thinking is wrong.


texts: Can you have three consecutive black nodes in red-black search tree?

texts: Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma has been made that red-black trees with $n$ internal nodes have height at most $2\log(n+1)$, would this proof still hold for such a black tree?


texts:
How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann function as an asymptotic upper bound?

Edit: I want to make it clear that I am interested in the time complexity of computing Ackermman's function and whether the time complexity of computing any primitive recursive function is asymptotically bounded by the time complexity of computing Ackermman's function. I am not interested in the actual values of those functions.

I am asking because I remember seeing an assertion of my second question in an old book but no proof was shown and no time complexity for computing Ackermman's function was listed, so the assertion was by no means rigorous.


texts: Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete?

texts:
Once we fix a polynomial time deterministic verifier V(input, certificate), its corresponding NP problem is the question: For this input, does a (polynomial size) certificate exist such that V(input, certificate) returns True?

The associated counting problem (#P class) is: How many certificates exist such that V(input, certificate) returns True?

#P is not a "decision problems" class, but a class of counting problems. The closest traditional "decision problems" class is PP, which has problems of the form: Do the majority of the certificates result in V(input, certificate) returning True?

I am interested in the decision version of the counting problem associated with a certain NP-complete problem + verifier, which would be: Given the input instance and a positive integer number K: Are there at least K different certificates such that V(input, certificate) returns True?

This decision problem is clearly equivalent to the counting version (via a Binary Search). If I am not mistaken, the class of all these "decision versions of the counting problems associated to NP problems" is exactly as hard as PP since:

1) Any of these "counting-decision" problems can be reframed as some other majority problem, by choosing an ad-hoc verifier definition where a lot of certificates are manually deemed to be True or False such that there are at least K True certificates in the original if and only if the majority is True in the resulting problem. Just as a simple example to illustrate the reduction idea, if there where 8 possible certificates, and we want to know whether there are at least 3 True ones, we might propose a different verifier having 11 possible certificates: for the 8 original ones it just checks normally, and for the other three it immediately returns True without looking at the input. Since the majority of 11 is 6, this new verifier accepts a majority of certificates exactly if the original one accepts at least 3.

Thus, all of these problems are in PP.

2) The corresponding "counting-decision" version for any PP-complete problem will obviously be PP-hard, since solving the original majority problem is simply solving the $(input, \left \lfloor \frac{  totalCertificates}{2} \right \rfloor + 1)$ problem. Thus, such problems are PP-complete.

So now, at last, can I clearly state my question, which is a "more sofisticated version" of the same idea shown in MAX,MAJ variants of NP complete problems:

Is there any NP-complete problem such that the decision version of its counting problem (which is in PP) is not PP-complete?

For example, in the case of Subset-Sum the associated decision problem I'm interested in would be: Are there at least K nonempty subsets of zero sum?

Since K is free and not limited to be near half of the certificates, the argument of the other answer does not apply.


texts: Is the term page replacement actually a misnomer?

texts: My understanding is that "page replacement" entails replacing the contents of a frame to bring in a new frame in it's place corresponding to a new page. Since it is not the page, but the frame that changes, shouldn't this process be called "frame replacement"?


texts: Chained operations on sequences with two operators

texts:
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?

Can we learn from matrix chain multiplication? A generalization of matrix chain multiplication is defined as:

  Given a linear sequence of objects, an associative binary operation on those objects, and a way to compute the cost of performing that operation on any two given objects (as well as all partial results), compute the minimum cost way to group the objects to apply the operation over the sequence.

What happens if we put two binary operators? Can the algorithm for Matrix chain multiplication be further generalized (or how can we otherwise solve this problem) to two binary operators in a binary expresion tree, given the cost functions of these operations? In particular, multiplication and addition, which complicates things further by allowing distribution. Also, does it matter that mind that some of the numbers can be negative, allowing reduction in size of intermediate results (see Overflow safe summation)?

Also, how does this relate to  Graph Reduction?

I also remember learning about database query optimization which seemed to do something similar to determine how early to execute particular joins to keep the intermediate values smaller.