texts:
I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed.

I got stuck in proving that, if P is closed under nonerasing homomorphism (replacing all characters with nonempty string), then P = NP.
With nonerasing homomorphism I cannot delete the characters, but I can get rid off the information by overwriting it e.g. with 0s.

I'm trying to complete the following idea:

Checking whether a given assignment to propositional formula makes it true is in P class.

Let s be the 0-1 string encoding both the formula and particular assignement.
I'm trying to find such nonerasing homomorphism H over 0-1 alphabet that H applied to string s will erease (overwrite with something that
will destroy information) the particular variables assignment but I must be able to read off the formula.

Have anyone the idea how such a homomorphism could look like? (only 2 letter alphabet is allowed).


texts:
I got this question for homework:

Decide if this language is context free or not:
$\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$.

Intuitively I think it's not context-free because a $PDA$ can't remember the places of all the $1$'s in $x$.
I tried using the pumping lemma but couldn't find the right example to show the language is not context-free.
I'd be grateful for any lead.


texts: Prove that Language is not Regular using closure(s)

texts:
I'm having a really tough time trying to comprehend proofs via closure and pumping lemma.
None of the examples I can find are similar to the one's im looking to prove.  Can anyone explain if I'm totally missing the mark here or is this valid?

Question:
Prove that
$$
L = \{0^x 1^y 2^{x+y} \mid x \ge 0 \text{ and } y \ge1\}\qquad\text{is not Regular.}
$$

Must use Closure(s).
Your "destination" should be
$$
\{ a^z b^z \mid z \ge 1\}, \qquad\text{ which we know is not Regular.}
$$

Start with $L$

(show a sequence of operations and results)

End with $\{a^z b^z\}$ which is not regular

Answer:

If $L$ is regular then $L'$ must be regular
$$
L' = \{(0^x)' (1^y)' (2^{x+y})' \mid x \ge 0, y \ge1 \}
$$
Let $E$ be an element of $L'$ where $E = \{a^z b^z \mid z\ge 1\}$. Since we know $\{a^z b^z \mid z\ge 1\}$ is not regular from using pumping lemma, etc.
$L$ is not regular


texts: Why have additional symbols on a Turing machine?

texts: What is the point of non-binary printed letters on a turing machine? I understand that these need to be omitted to get a computable number, but why are they used in the first place?


texts: Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality

texts:
I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $\text{weight}(u,v) \le \text{weight}(u,w) + \text{weight}(w,v)$ for all vertices $u, v, w$).

My first naive try was to use an algorithm for solving the all-pairs-shortest-path-problem and compare the result to the vertices connecting two nodes directly.

However, I think this might be overkill. Is there any better way to check?

Thanks a lot.


texts: How can primitive recursion be a special case of minimization?

texts:
In several posts on StackExchange and elsewhere, I have seen claims that you only need to show you can construct constants, successor, projection, composition, and minimization to prove a language Turing-complete, since primitive recursion is allegedly a special case of minimization. But as I have been thinking about it, I don't see how minimization can be used effectively at all without primitive recursion.

Minimization searches for zero
The only way to get zero without primitive recursion is a constant zero
So any application of minimization must either:
Return a constant zero all the time (since there is no way to do conditionals either w/o p.r.), or
Return the input unmodified, since any number of successors other than zero would never return zero

So if every minimization must either return constant zero or zero only when the input is zero, how can you construct any function more powerful than this? Or is this a false assumption?


texts: Pagerank is equivalent to degree centrality

texts:
Can someone explain why pagerank defined for undirected graph with no damping factor is equivalent to the degree?

$\sum_{j\in N(i)}{\frac{p(j)}{d(j)}} = d(i)$

I looked up every book I could, but they all say it's trivial and skip the proof, making me feel stupid.


texts: Finding the number of square prefixes of a string in linear time

texts:
Let square denote a concatenation of two identical, nonempty
  strings. Given a string $w$, devise an $O(|w|)$
  algorithm that counts the number of prefixes of $w$ that are squares.

My initial idea was to use the prefix function $P$ from the Morris-Pratt algorithm ($P[i]$ is the length of the longest proper prefix of $w[1..i]$, being also its suffix), which can be calculated in linear time. Then, for each even index $i$ (we do not need to consider prefixes of odd length, as those obviously cannot be squares) the corresponding prefix $w[1..i]$ is a square if $P[i] = i/2$ and is not a square if $P[i] < i/2$.

Now, the missing case which I am unsure how to handle is $P[i] > i/2$. For example, let's consider the two strings: $abababab$ and $ababab$. The longest proper prefix-suffix of each of them is bigger than half the length of the string (6 and 4 correspondingly), yet the first one is a square and the second isn't.

Can anyone point me to an observation needed to resolve the missing part of the algorithm? Or is the idea to use the $P$ array wrong and a different approach should be applied to this problem?


texts: What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm? If so, how ?


texts: create two- or three-tape Turing machine to recognize the language $0^{2^n}$

texts: I am creating a two-tape Turing machine to recognize the language $\{0^{2^n}|n\geq 0\}$. My idea is to put an input string, such as 0000, at the first tape, and use the second one to count the number of 0s in binary form (as a suggestion at A two-tape deterministic Turing machine that recognizes an exponential string).  Every time Turing machine read a single 0, increase the counter (on the second tape) by 1. My difficulty is to write clearly the transition function, namely $\delta$, such as, I don't know how many states this Turing machine should have.


texts: monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies

texts:
I'm working on exercise 16.3-5 of CLRS:

  Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.

Perhaps I'm misunderstanding the question, but how can the lengths be monotonically increasing? In order for the code to be optimal, the binary tree representation must be full (like the StackExchange CS logo), e.g. every node with degree either 0 or 2 (if it's not full, then it cannot be optimal, since the code could be shortened by promoting the child of a node with degree 1, as discussed in exercise 16.3-2). That means there exists at least one pair of leaf nodes at the same depth, and depth is the same thing as the codeword length.

The Huffman code is optimal, and it always begins by merging two characters, so again there's at least a single pair of leaf nodes that will be at the same depth and hence same codeword length in the resulting tree.

Is it a typo, e.g. should it read "monotonically increasing except for the final two characters, which have the same length" or maybe even "monotonically non-decreasing"?

In fact, there is a trivial counterexample: suppose there are only two characters 'a' and 'b', with frequencies 0.6 and 0.4 respectively. The optimal code is clearly 'a'=0 and 'b'=1, or vice versa. However, the codelength is 1 for both characters, so clearly is not monotonically increasing.


texts: Is this classic puzzle book game NP-complete?

texts:
There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked out just like a cross-word, and some squares have a letter already pre-written in them. The goal is to write each word from the list once and only once in the puzzle, where each word is written either horizontally (left to right) or vertically (top down) into non-blacked out consecutive squares, and when you write a word, the two squares flanking the ends of the word must either be blacked out or off the board. Also for the letters pre-written into some squares, the words written that overlap these squares must respect the pre-written letter.

Now, if we assume a fixed size alphabet for the words, is deciding whether we can fill the board with a valid solution using exactly each word on the list once and only once an NP-complete problem, if the side length of the board is not fixed?


texts: A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

texts:
It is known that a PDA with two stacks is equivalent to a TM.

On the other hand a PDA with one stack is capable to recognise only context-free languages.

Hence there is a kind of a gap between the class of PDA with one stack and the class of PDA with two stacks which should be capable to recognise only context-sensitive languages.

I feel like it should be already an examined question, but I couldn't find an answer: what restrictions should we apply to a PDA with two stacks in order to make it equivalent to a Linear-bounded automaton?


texts: Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

texts:
It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$  worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: if insertion is allowed to affect only a small part of the list, then there's no way for it to always keep the entire list in a structure that allows for constant time element access.

Is there any proof (or counterexample) of this?


texts:
Here is the regular expression I made for it

This is my first answer, used the naive method aka don't know what am doin' method.
$$
\epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( (a|(b^*a))ba^*\right) \right) ^*
$$

this is my re-worked answer, with the state removal method.

$$
\left( a^* \cup (b)(a \cup bb^*a) \right) ^*
$$

steps taken :

Add a new start state and a new final state.
Add epsi transitions to the new states.
Remove Q2
Link between Q1 and Q3 is now $a \cup bb*a$
Remove Q1
Add a new link between Q0 and Q3 with $ (b)(a U bb*a)$ label
Remove Q0
There are three paths. a*, the big regex and the start with epsi
$\epsilon \cup a* \cup (b)(a \cup bb*a)$
Remove Q3
We get $\epsilon \cup \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$ =$ \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$

My questions are:

Is my regular expression correct ?
What happens if it loops ?

To be clear, let's say we have the string aababaaaaabab

I think that string is recognized by the NFA, but I'm not sure it is by my regular expression.

does the $^*$ at the end cover it correctly ?

ps: As suggested I moved this from math.se


texts: Maximizing a sequence of items under order and pairwise restriction

texts:
Suppose I have a number of items $\{A ... Z$} which are ordered accordingly. Each item has an associated weight, for example $W_A$. Between all items, there's a criterion $c$ which determines whether they fit together. So if $A$ and $B$ don't fit together, maybe $A$ and $C$ do, and then the next fitting neighbour from $C$ would have to be found.

The goal is to find a chain $S$ among these items that has the items in the original order, all subsequent items meet $c$ and that maximizes the sum $\sum_{i \in S} W_i$. A naive approach would completely explode in runtime I suppose. Does anyone have a way in mind to liken it to a solved problem?


texts:
i read that First-Order Logic is strong enough to formalise all of Set Theory and thereby virtually all of Mathematics. How would you express in First-Order Logic the theorem:
 3SAT is NP-complete?


texts: My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're suppose to do at this step   I understand that you're suppose to verify the correctness of a solution but how do I do that?


texts: Interpolation: How to generate 3D objects from 2D cross-sections?

texts:
Consider a sphere sitting on an $xy$-plane, and take 2D slices parallel to the $xy$-plane at various heights of z. Suppose we take 10 slices, evenly spaced along the $z$-axis, and now have 10 images of circles each with a corresponding $z$.

My goal would be a function that could learn from these 10 slices, such that if I were to input a new value of z, it would draw a circle (that is ideally close to the correct circle at that height).

Would there be a way to train something like a neural network to take the height z as the input, and output circles corresponding to the slice of a sphere at a particular height?

Such a method should scale to multiple dimensions. For example, if I had some multidimensional object I wished to reconstruct using slices of that object. Note that the parameter corresponding to slices may now be a vector.

EDIT:
The goal is to interpolate between 2D shapes that do not have simple analytic solutions. For example, one image is a circle and another is a rectangle.

The problems I am facing are where there are no simple analytic solutions for new shapes as a function of z. Imagine that there exists a very rugged non-linear 3D object (like the cross section of a person) - but we can only determine a few slices of this object as it is computationally expensive for some reason. We wish to interpolate between these few slices and generate a 3D object. Such a solution should also work for strange multidimensional shapes beyond 3D.


texts: Order-preserving update of a sublist of a list of mutable objects in sublinear time

texts:
Description

Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to "B", my derived list looks like ["B"].  Next, if I change my source list's "d" to "D", the derived list should look like ["B","D"].

Is it possible to make the insertions and removals in the derived list, while maintaining order, in faster than $O(n)$ time, $n$ being the size of the list?

Finally, I'd like to be able to know the index of where the insertion or removal takes place in the derived list in faster than $O(n)$ time.

An idea that doesn't work

I could keep the derived list in a tree, sorted by the source index. This way, when I needed to insert my item in derived tree-list, it would take $O(log n)$.  However, I would not be able to know that index of that insertion without walking the entire tree.

Thanks for your help!

Problem Statement

Let $S$ be an ordered list
Let $Si.filterProperty$ be $true$ for some elements in $S$
Let $F$ be an ordered list of all elements in $S$ where $Si.filterProperty$ is true

Let $T(i)$ be a function that:

Sets $Si.filterProperty$ to $true$
Inserts $Si$ into $F$, ordered in the same fashion as $S$
Returns the index in $F$ where $Si$ was inserted

Can $T$ and its side effects be faster than $O(n)$?

Any list-like data structures can be used within these constraints:

Insertion and side effects of insertion are faster than $O(n)$
We must know the index of the newly inserted item into $F$


texts: What are the differences between symbolic execution and SAT solvers?

texts:
My understanding is that symbolic execution only deals with specific paths and bad patterns, while SAT solvers, or satisfiability modulo theories in general, provide a much more robust analysis of the program.

Could someone validate the statement above and (briefly) explain the differences between these two formal verification methodologies?


texts: Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

My question is about this part.

[Convolutional codes have been popular in practice because it is easy to factor the uncertainty of a bit being a 0 or a 1 into the decoding.]

Why is it easy to use convolutional codes to factor the uncertainty of a bit?

Is it because the convolutional code circuit is designed in such way as to handle uncertainty properly? I couldn't really find the exact answer. I think the answer has something related to the fact that a convolutional code is not a linear code but I couldn't really understand exactly why a convolutional code is special to handle uncertainty.


texts:
Consider n buckets that contain from 0 to x items. From time to time something is added (moved, removed) to (between, from) any bucket(s).

Once in a while runs something that will have to calculate what items have to be moved from their bucket to another with minimal amount of moves so number of items in each bucket will be almost equal.

Is there a name for this algorithm?


texts: What advantage does Tangaroa offer over PBFT?

texts: Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should I use Tangaroa and when PBFT?


texts: Finding number of numbers dividing n^m exactly p times

texts:
Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times.

Mathematically, I have to find number of distinct $x$ such that
$$ n^m \equiv 0 \mod x^p \qquad\text{and}\qquad n^m \ne 0 \mod x^{p+1} $$

(From UVa Online Judge)

What approach could be better than brute force?


texts: How does the Galil's rule work on Boyer-Moore algorithm?

texts:
I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page.
And why with this rule we go to a linear time complexity?


texts: Metaprogramming taken to an unnecessarily high level- how can a program write not just other programs, but a programming language?

texts:
So basically, automated language-oriented programming. I've tried finding info on this concept, but have had some trouble, probably because my brain is having a bit of trouble grasping the subject while thinking about it. It could be better defined as metaprogramming going to a deeper level- rewriting the programming language it is written in as well as or instead of the program itself.

Theoretically, through this a program would be able to operate on an infinite number of levels. I think this should be a key part of artificial intelligence, as we humans have written numerous programming languages all on top of each other and from scratch, so our programs should be able to as well.

How or why someone would ever do this is not the question. The better question is, "why not?"

If you are able to answer this question, don't worry because I have more to back it up. What programming languages would be best for this kind of thing, and what are some terms I can use in the future to better describe and grasp this concept?


texts: Proof of lemma from Hong's article about multi-threaded max flow algorithm

texts:
I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem.

  Lemma 3. Any trace of two push and/or lift operations is equivalent to either a stage-clean trace or a stage-stepping trace.

And

  Lemma 4. For any trace of three or more push and/or lift operations, there exists an equivalent trace consisting of a sequence
  of non-overlapping traces, each of which is either stage-clean or
  stage-stepping.

Pdf version of the article can be found here


texts: Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?

texts:
In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of vertices). But how can we talk about a polynomial time reduction if we generate exponential-size numbers?

I guess that this is the key why Vertex Cover is strongly NP-complete and Subset-Sum is only weakly NP-complete. But I didn't get why it is in fact a polynomial time reduction.


texts: What does actually happens on tile hashing

texts:
I am going through Richard Sutton book about Reinforcement Learning and I just encountered the tile coding method. I understood pretty well the principles, however, at the very end of the section, tile hashing is mentionned.

  Hashing produces tiles consisting of noncontiguous, disjoint regions ran-
  domly spread throughout the state space,  but that still form an exhaustive
  partition.  [...]  Through hashing, memory requirements are often reduced by large
  factors with little loss of performance.  This is possible because high resolution
  is needed in only a small fraction of the state space.

I understand how hashing can consequently limit memory requirement, but I cannot visualize how hashing would work for tile coding. How can collisions be handled if tiles are spread randomly ? How are the tilings represented then ?

I have been doing some research, however, most of the ressources lead directly to the mentionned book.


texts: Worst case $O(n \ln n)$ in place stable sort?

texts:
I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm.  Does anyone know of any good resources?

Just a reminder, in place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space.  Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.

For example, naive merge sort is worst case $O(n \ln n)$ and stable but uses $O(n)$ extra space.  Standard quicksort can be made stable, is in place but is worst case $O(n^2)$.  Heapsort is in place, worst case $O(n \ln n)$ but isn't stable.  Wikipedia has a nice chart of which sorting algorithms have which drawbacks.  Notice that there is no sorting algorithm that they list that has all three conditions of stability, worst case $O(n \ln n)$ and being in place.

I have found a paper called "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola, which claims to have a worst case $O(n \ln n)$ in place stable mergesort variant.  If I understand their results correctly, they use (bottom-up?) mergesort recursively on the first $\frac{1}{4}$ of the array and the latter $\frac{1}{2}$ of the array and use the second $\frac{1}{4}$ as scratch space to do the merge.  I'm still reading through this so any more information on whether I'm interpreting their results correctly is appreciated.

I would also be very interested in a worst case $O(n \ln n)$ in place stable quicksort.  From what I understand, modifying quicksort to be worst case $O(n \ln n)$ requires selecting a proper pivot which would destroy the stability that it would otherwise normally enjoy.

This is purely of theoretical interest and I have no practical application.  I would just like to know the algorithm that has all three of these features.


texts: Name of this rearranging/sorting problem?

texts:
You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from the same class are always grouped together, that is they form a contiguous subarray.
For example:
$$
\begin{align*}
&[2, 1, 3, 3, 2, 2] \longrightarrow [2, 2, 2, 1, 3, 3], \text{ or} \\
&[2, 1, 3, 3, 2, 2] \longrightarrow [1, 2, 2, 2, 3, 3], \text{ or} \\
&[2, 1, 3, 3, 2, 2] \longrightarrow [3, 3, 2, 2, 2, 1].
\end{align*}
$$
Three other valid arrangements remain.

What is this problem called in literature?  Is there an efficient algorithm for it?


texts: Error lower-bound for an algorithm for vertex cover

texts:
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \emptyset$.
Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.
For every edge $e$ in $e_1, e_2, . . . , e_m$

if both endpoints of $e$ not contained in $B_0$, then
flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B_0$ with $|B_0
| \ge c|OPT|$?


texts:
EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th bit indicates whether the word contains the i-the letter in the alphabet.

As I was tackling an interview problem I came up with this tree-like data structure. Actually it IS a binary tree that is maximum 26(English alphabet size) nodes deep.
Basically the problem is:

  There are a set of dictionary words and a set of license plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the letters in the license plate, irrespective of the order of characters

This data structure is specifically designed for the problem of finding words from a given list containing all letters from a set of letters.
 I call this operation getSupersetWords().

It can also be used for finding words containing ONLY a set of letters.(In fact my empirical tests show that this is the use case giving the best performance gain over linear search (over 16 times faster on average for a list of 73k English words)).
I call this operation getSubsetWords().

To give you an example:

Lets say we have list of words = [ “cat” ,”dog” “cow”, “case”].

On query getSupersetWords([‘a’, ‘c’]) we get [“cat”, “case”].

On query getSubsetWords(['c', 'o', 'w', 'a', 't']) we get ["cat", "cow"].

How to add a string to this data structure ?
As I said earlier the data structure is a binary tree.
 At every level of the tree we make a decision. If the word contains the next letter of the alphabet(we start from 'a' at level 1) we go right, else we go left.
 If we have made all the 'right' possible decisions for the given word we place it in the current node.(A node contains a reference list of strings).

How to answer a query from this data structure ?
Now to answer a getSubsetWords() query we traverse the tree recursively in DFS making both decisions if the query contains the character at the current letter, or 'left' if it doesn't and adding the words at the given Node to a list
(this is VERY confusing to type out...but not so much in code :/).

It sounds confusing, that's why I made a simple diagram illustrating the idea.

Assume we have a list of strings = {"a","aaa","baa","ab","bb"}.

Now If we had 'z' in the list the tree would be 26 nodes deep, but because the 'biggest' letter is 'b' We only need 3 levels.

The circle shapes are lists of strings, the rectangles are the nodes.
I was wondering if this structure is something I have 'invented' or it is already well known, (Which probably is the case :).


texts: Are syntax and semantic just 2 structures such that one is a model of the other?

texts:
The syntax of a language is a structure.
The semantic of a language is a structure.
The semantic of a language is a model of its syntax.

And that's all ? The duality syntax/semantic is just model theory applied to languages ?

(A short answer could be ok; I have already read the wikipedia pages !)


texts: Citation for finding node disjoint paths using maximum flow

texts: We can find  the maximum number of vertex disjoint paths in a directed graph using maximum flow algorithm keeping the node capacity and edge capacity to one. I could not find the reference paper for this technique. Please let me know the citation for this technique.


texts: Counting number of perfect squares in an subarrays

texts:
A sequence is good if the bitwise AND of all its elements is a perfect square.

So counting number of "good" sequences, in a subarray .

For example : in [1, 2, 3]

There are 6 sub-sequences:

So there are 3 "good" sequences

Can you suggest an efficient approach to count them ?


texts: Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time

texts:
I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible.

I tried to work with Min-Max Fibonacci heaps and pointer to median, but got stuck.

I believe the $Insert$ operation can be done in $O(\log n)$ amortized-time.

Any help is appreciated.


texts:
After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult for me to find examples of natural L complete problems. (Here "difficult" means article behind paywall and google book with limited number of shown pages.)

The typical natural L complete problem should be complete for L under AC0 many-one reductions, and the proof that it is in L should not use (or reveal) SL = L. Take this list:

undirected graph acyclicity
undirected graph accessibility problem (UGAP)
undirected s-t connectivity (USTCONN)
directed tree s-t connectivity
tree isomorphism
product of two permutations for disjoint cycle representation

(I believe that all problems in this list are L complete, but I don't know which are natural. I know that UGAP=USTCONN is not natural. I guess that both undirected graph acyclicity and directed tree s-t connectivity are natural. I am unsure whether tree isomorphism and product of two permutations are complete under AC0 many-one reductions, but at least I know that showing they are in L does not reveal SL = L.)

How can I learn more about the natural L complete problems on the above list? Are there other interesting L complete problems missing on the above list?

My motivation for looking for L complete problem is the question of the relation between NC1 and L. After learning that L ⊆ EREW1 (and the hint that directed tree s-t connectivity should be L complete), my suspicion that NC1 = L got quite strong, since NC1 ⊆ L and NC1 ≈ EREW1 (one is logarithmic time in uniform circuit model, the other is logarithmic time in the weak exclusive read/exclusive write PRAM model).


texts: Wrapping the complexities of alternative algorithms: What is the proper "term" for it?

texts:
Suppose that we have two algorithms for the same task (e.g. search):

AlgC: has bounded worst-case complexity, e.g. O(n.logn)
AlgH: is a heuristic algorithm that is experimentally faster than AlgC, but there is no tight complexity bound for AlgH.

If we want to have an algorithm that is FAST but also has a guaranteed computational complexity, we can use some simple tricks. For example:

We can run AlgC and AlgH simultaneously in an interleaved fashion (or in parallel), and once any of them finishes the task, we stop the other one. This ensures that AlgC binds the complexity, while the execution is as fast as AlgH.
We can also run AlgH for a limited time (e.g. a factor of $n.\log n$) and if it hasn't finished, we run AlgC.

What are such techniques called in Algorithm's community? There should be a proper term for that, right?


texts: Check for common element in two arrays using FFT

texts:
My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that there is a simple $O(n\log(n))$ algorithm to solve this problem using sorting and binary search.)
The tasks hints that we should consider the following product to solve the problem:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
I know how to use FFT to multiply polynomials efficiently, but somehow I seem to overlook something.


texts: Respresting data when I have to move back and forth

texts:
I am having data where I would be given customers and there priorities. The priority would be food type and there flavours.

In total there are N food type and 2 flavour (spicy and non spicy) so in total there are 2N choices to make.

Each of the customer has a set of food types they like and they are satisfied if there is atleast one of there prefered food types prepared.

There is exactly one food type made with a certain flavour so if we have a spicy food type then we cannot have the same non-spicy food type.

For each customer you make atleast on food type that they like
for example there are three customers and they have different food priorities (italian, chinese, meditiranian) and amongst any of it they can choose spicy and non-spicy.

In first case, If the customer 1 has priority that he wants spicy italian and customer 2 wants non-spicy italian then it is not possible

In the second case, If the customer 1 has priority of non-spicy italian, customer 2 has priority of spicy italian and non-spicy chineseand customer 3 has priority of meditaranian spicy. So, this is possible as all the three customer demands can be met.

// n customers
(1st row for 1st customer)// number_of_food food_type non_spicy=0/spicy=1
...

The data for the case 1 would be represented as

2
1 1 0
1 1 1

The date for case 2 would be represented as

3 // customers
1 1 0
2 1 1 2 0
1 3 1

So, finally, the question, how can I represent this data so that I can move/traverse through the data in more efficient way.

Because if I make a certain choice for a customer A and then for a customer B which I encountered further in the list I see that the priority for the customer B is the same as A then I have to move back to customer A and see its other choices and switch him to select other choices and then I have traverse to through the list again moving forward from customer A until customer B.

I am just looking for some hint on this and the name of data structure and algorithm and the reason for choosing that. From that point forward I can look into how it works and code myself.


texts: Lamport Timestamps: When to Update Counters

texts:
In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following:

Each process $Pi$ increments $Ci$ between any two successive events.
If event a is the sending of a message m by process $Pi$, then the message $m$ contains a timestamp $Tm = Ci(a)$.
Upon receiving a message $m$, process $Pi$ sets $Ci$ greater than or equal to its present value and greater than $Tm$.

However, the algorithm as it is described on Wikipedia (and other websites) is a little different:

A process increments its counter before each event in that process.
When a process sends a message, it includes its counter value with the message.
On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.

This leaves me with the following questions:

Should be increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.
When a message is received by process $Pi$ Lamport states that $Pi$ logical clock should be set to $max(Tm + 1, Ci)$. However, the Wikipedia article says that this should be $max(Tm, Ci) + 1$. Is Wikipedia wrong?


texts: How to find percentage of CPU time consumed during DMA operation?

texts:
Q) Consider 1MBps hard-disk is interfaced to the processor in a cycle stealing mode of DMA whenever $64$ bytes of data is available in the buffer,then it is transferred to main memory (1 word = 64 bits) and machine cycle time is 2 micro sec. Then,

1.) Percentage of CPU time consumed for DMA operation is ?
2.) Percentage of CPU time consumed for DMA Operation if burst mode is used?

Given Solution :
1.) For Cycle Stealing Mode
1 word = 64 bits = 8 bytes is transferred in one  cycle.
Since total 64 bytes is to be transferred So total number of cycles $= 64/8 =8 $,
1 cycle time = 2µs , So time for 8 cycles is = 16µs
Now time taken by disc to transfer 64 B is  $(64)/10^{6}=64µs$
Hence % of CPU Time consumed = Data Preparation Time / Data Transfer time $= (16 / 64)*100\% = 25\%$
My Doubt : How does the above formulae give the % time consumed by CPU  or basically where CPU spends time during a DMA transfer and why are we dividing by the disk transfer time.

2.) For Burst Mode : Since all data is transferred at once so only 1 cycle is needed for data transfer i.e. 2 µs
So % CPU time consumed = Data Preparation Time / Data transfer Time
=$(2/(2+64))*100\%$ =~ $3\%$
My Doubt : Why are we adding the 2 in burst mode.


texts: Lower bound on number of (different) circuits of given size?

texts:
For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$.

Say two circuits $C_1$ and $C_2$ are different if the function they compute is different, that is, there is an $n$-bit string $x$ such that $C_1(x) \neq C_2(x)$. The $O(s(n)^{s(n)})$ bound above is an upper bound on the number of circuits of a given size. Is there a known lower bound on the number of different circuits with size at most $s(n)$ for different values of $s(n)$ (e.g., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{\textsf{polylog}(n)}$, or $s(n) = 2^{n^\varepsilon}$)?

Clearly such a bound must be strictly smaller than the $O(s(n)^{s(n)})$ bound since there are pairs of circuits with different structures (and even different number of gates) and which nevertheless compute the same function (i.e., they are not "different" as defined above)—but how smaller can it be?


texts: Minimum number of givens for General Sudoku of size $n^2 \times n^2$

texts:
Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens).

What is the minimal number of givens for a size $n^2 \times n^2$ board? Is there a table of "best-known" minimal values?

I'm speculating that there is only an asymptotic/approximate bound as the $n=3$ case was not known, let alone higher values of $n$. For $n=4$, the best-known is 55, and $n=5$ is 151.


texts: Graph Partition Across Cluster - Minimize Largest Matrix Size

texts:
I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix (representing the neural connectivity), and I want to split the $n\times n$ matrix into $k$ smaller $n \times (n/k)$ matrices. From there each machine will do some expensive computations on it's assigned matrix. Additionally, I can remove empty rows from the $n \times (n/k)$ matrices before distributing to the machines (so that they are $\leq n \times (n/k)$). So my question is: how do I split the matrix into $k$ sub-matrices, so that I can minimize the size of the largest sub-matrix.

My graph theory knowledge is limited, and so any references or direction would be great in lieu of an explicit answer if there are already resources out there that are related to this kind of problem.


texts: How does CFS prevent a long sleeping task from occupying the CPU?

texts:
The Completely Fair Scheduler executes the task that has so far received the least share of CPU time and is thus the most 'disadvantaged'.
So if a task sleeps for a really long time, say 3hrs, how does CFS prevent this task from being executed for the next like 3hrs (to adapt its CPU share to the much larger values of the other tasks)?

Or does CFS do so at all? Or did I get something wrong?

Thanks in advance :)


texts: Reference for counting the number of paths in a DAG

texts:
Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .
Is there a reference or name for the algorithm?   If not, are there well known applications?


texts: How to generate random strings from Context-Free Grammar in GNF

texts:
I need to generate random strings given a grammar in Greibach Normal Form.

The naive approach would be to generate a random integer n and perform n traversals of production rules, as every traversal adds exactly one symbol to the string. The problem with this approach is that the choice of productions to expand cannot be entirely random, as some planning is required to ensure that at length n it is possible to terminate at an empty string.


texts: E-Unification: “Goal seeking” pattern matching between directed trees

texts:
Preamble

Suppose we have some symbols x, y, ... and wildcards (ξ), (ζ), ... which have any meaning. Wildcards are said to ‘match’ any symbol: wildcard (ξ) matches symbol x under the mapping {(ξ): x}. Now suppose we can construct directed trees from these symbols and wildcards. The notion of matching should extend to these trees, like this:

  x                 x
 / \               / \
a   y   matches  (ξ)  y   under the mapping {(ξ): a, (ζ): b}.
   / \               / \
  z   b             z  (ζ)

It is easy to implement an algorithm which takes two trees like those above and gives the necessary mapping. (Does it have a name?)

I want to introduce certain ‘equivalence relations’ <n> between trees. For instance, if I wanted to capture the notion of the symbol f being commutative and associative, I could write:

       f         f
<1>:  / \   =   / \     # commutativity f(ξ, ζ) = f(ζ, ξ)
    (ξ) (ζ)   (ζ) (ξ)

        f         f
       / \       / \
<2>:  f  (χ) = (ξ)  f   # associativity f(f(ξ, ζ), χ) = f(ξ, f(ζ, ξ))
     / \           / \
   (ξ) (ζ)       (ζ) (χ)

This is where things get interesting, because I now want to implement a more intelligent matching algorithm which, given a set of equivalence relations like those above, is able to perform ‘indirect’ matches like this:

  f                          f
 / \  (indirectly) matches  / \  under the mapping {(ξ): x}...
y   x                     (ξ)  y

                f  <1>  f                            f
   ...because  / \  =  / \  which directly matches  / \ .
              y   x   x   y                       (ξ)  y

Question

How would one go about finding an algorithm which is able to transform a given tree (via given rules) so that it ‘matches’ another tree?

Is there a name for this kind of problem?

More examples

Matches aren’t always unique. Ideally, the algorithm should be able to find all of them.

   f                 f
  / \               / \
 x   f   matches   f  (ξ)  under {(ξ): y, (ζ): z} or {(ξ): z, (ζ): y}...
    / \           / \
   y   z        (ζ)  x

         ...using rules <1> and <2>.

A quintessential demonstrative example:

For brevity, define the symbols 1, 2, 3, ... in terms of 0 and a unary symbol s:

1 = s(0), 2 = s(s(0)), 3 = s(s(s(0)))...

Now, define two transformation rules s(n) = +(n, 1) and s(+(n, m)) = +(n, s(m)):

       +      s
<1>:  / \  =  |
    (n)  1   (n)

     s       +
<2>: |  =   / \
     +    (n)  s
    / \        |
  (n)  (m)    (m)

Check this out:

            +
5 matches  / \  under {(ξ): 2}, because...
          3  (ξ)
                     <1>          <2>
...5 = s(4) = s(s(3)) = s(+(3, 1)) = +(3, s(1)) = +(3, 2) which matches 5 with {(ξ): 2}.

   (as trees:)
       s   s  <1>  s  <2>   +       +                  +
...5 = | = |   =   |   =   / \  =  / \  which matches / \  with {(ξ): 2}.
       4   s       +      3   s   3   2              3  (ξ)
           |      / \         |
           3     3   1        1

(I apologise for the size of this question. I don’t have a background, so feel free to improve this post.)

Perhaps you can direct me to some reading, or set me off in the right direction? Thanks heaps!


texts: Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to "connect" all points

texts:
I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, allowing for some minimal deviations.

For example, given the points (0,0)-(50,50)-(100,100), the path can be optimized by only specifying (0,0)-(100,100) which will also cover the center point. In case of (0,0)-(49,49)-(100,100) I still want to allow the same line segment of (0,0)-(100,100), as the distance (e.g. euclidian) from the point to the line is small (by a user defined parameter).

What is the minimum number of line segments needed that satisfies the distance condition and how can the segments be determined. Is there a "good" heuristic which is simpler or more efficient while providing comparable results?


texts:
It is well-known that an infinite union of regular languages is not necessarily regular, since every language can be written as a union of singletons. What about infinite concatenations?

Let $\{ L_z : z \in \mathbb{Z} \}$ be a family of languages, cofinitely many of which contain $\epsilon$. We can define the infinite concatenation of the family as the collection of all words of the form $w_{i_1} \ldots w_{i_n}$, where $i_1 < \cdots < i_n$ and $w_{i_j} \in L_{i_j}$. (The definition makes sense if we replace $\mathbb{Z}$ with any linear order.)

  Is the infinite concatenation of a family of regular languages necessarily regular?


texts:
I read that in a paging scheme memory management, some os's have a paging daemon that wakes up periodically to inspect the memory of the RAM. This is to ensure that modified pages can be scheduled to write back to disk before page fault happens and it also makes it more efficient to have a pool of free frames rather than having all frames used when a page fault occurs. OS periodically moves pages from RAM to a "pool of free page frames".

1) My question is since the pages are moved to this pool of free page frames, then it must be stored somewhere into RAM ? because the OS can easily retrieve the pages should if the frame it was evicted from has not have pages put inside. So is there memory reserved to store this "pool of page frames" in OS reserved memory ?


texts: What's the difference between subtyping and inheritance?

texts:
In object-oriented programming, I have learned the concept of subtyping and inheritance.
I thought they're the same thing, in the beginning. But I was told that they're totally different.

So what's there difference? What's there relationship?


texts: If the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

texts:
From Wikipedia:

A 32-bit register can store 2^32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common representations, the range is 0 through 4,294,967,295 (2^32 − 1) for representation as an (unsigned) binary number, and −2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1) for representation as two's complement.

So if the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

From a similar standpoint, if the integer representation used is "−2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1)", so does this mean that the register cannot handle numbers greater than 2,147,483,647?


texts: Find shortest prefix to generate original string by overlapping

texts:
Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\{0,3,8\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.


texts:
A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

The following lattice has 9 unique max length paths from {} to {1,2,3,4,5}, which can be obtained by a depth first search.

(The graph is directed, with arrows pointing down)

Is it possible to write a function that generates the N'th path without enumerating paths 1..N-1.

see: https://math.stackexchange.com/questions/510911/computing-all-simple-paths-in-a-distributive-lattice-in-parallel for more problem details.


texts: Proof strategy to show that an algorithm cannot be implemented using just hereditarily terminating procedures

texts:
I am taking my question here from there. Consider the following scenario:

You are given a fixed programming language with no nonlocal control flow constructs. In particular, the language does not have

Exceptions, first-class continuations, etc.
Assertions, in the sense of “runtime tests that crash the program if they fail”.

Remark: An example of such a language could be Standard ML, minus the ability to raise exceptions. Inexhaustive pattern matching implicitly raises the Match exception, so it is also ruled out.

Moreover, you are forced to program using only hereditarily terminating values. Inductively, we define hereditarily terminating values as follows:

Data constructors (including numeric and string literals) are hereditarily terminating.
Applications of data constructors to hereditarily terminating arguments are hereditarily terminating.
A procedure f : foo -> bar is hereditarily terminating if, for every hereditarily terminating x : foo, evaluating the expression f x always terminates and the final result is a hereditarily terminating value of type bar.

Remarks:

Hereditarily terminating procedures need not be pure. In particular, they may read from or write to a mutable store.

A procedure is more than just the function it computes. In particular, functions do not have an intrinsic asymptotic time or space complexity, but procedures do.

Hereditarily terminating procedures formalize my intuitive idea of “program that is amenable to local reasoning”. Thus, I am interested in what useful programs one can write using only hereditarily terminating procedures. At the most basic level, programs are built out of algorithms, so I want to investigate what algorithms are expressible using only hereditarily terminating procedures.
Unfortunately, I have hit an expressiveness ceiling much earlier than I expected. No matter how hard I tried, I could not implement Tarjan's algorithm for finding the strongly connected components of a directed graph.
Recall that Tarjan's algorithm performs a depth-first search of the graph. In addition to the usual depth-first search stack, the algorithm uses an auxiliary stack to store the nodes whose strongly connected components have not been completely explored yet. Eventually, every node in the current strongly connected component will be explored, and we will have to pop them from the auxiliary stack. This is the step I am having trouble with: The loop that pops the nodes from the stack terminates when a given reference node has been found. But, as far as the type checker can tell, the reference node could not be in the stack at all! This results in an extra control flow path in which the stack is empty after popping everything from it and still not finding the reference node. At this point, the only thing the algorithm can do is fail.
This leads to the following...
Conjecture: Tarjan's algorithm cannot be implemented in Standard ML using only hereditarily terminating procedures.
My questions are:

What kind of proof techniques would be necessary to prove the above conjecture?

What is the bare minimum type system in which Tarjan's algorithm can be expressed as a hereditarily terminating program? That is, what is the bare minimum type system that can “understand” that the auxiliary stack is guaranteed to contain the reference node, and thus will not add a control flow path in which the auxiliary stack is empty before the reference node has been found?

Final remark: It is possible to rewrite this program inside a partiality monad. Then every procedure would be a Kleisli arrow. Instead of
val tarjan : graph -> scc list

we would have something like
val tarjan : graph -> scc list option

But, obviously, this defeats the point of the exercise, which is precisely to take out the procedure out of the implicit partiality monad present in most programming languages. So this does not count as a solution.


texts: Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

texts: Given a cryptographic fingerprint of a collection, K == hash(X), an arbitrary function F, and a value Y, is it possible to build a short proof that F(X) == Y that doesn't require having X? I.e., a proof that Y is the result of applying F to some X such that hash(X) == K?


texts: premiss of reduction rule (abst) of pure type systems

texts:
$$(abst) \:\frac{\Gamma, x: t_1 \vdash t_2: t_3 \quad \Gamma \vdash (x: t_1) \to t_3: s}{\Gamma \vdash (x: t_1. t_2): (x: t_1) \to t_3}$$

In this rule, why is $(x: t_1) \to t_3$ required to be an inhabitant of some sort? Isn't assuming $t_1: s$ enough?


texts: What is the difference between apprenticeship and imitation learning?

texts: There are many sub-domains of reinforcement learning, two of which are apprenticeship and imitation learning - but that appears just to be two different names for the same thing?


texts: Is there a query language variant of Turing Completeness?

texts:
By this I mean a theory where you can say Language X is Query Complete so that you know that language is able to do any sort of query? I'm guessing not because some queries would run into things that a language would have to be Turing complete to work?
Why do I wonder - well you might have a relational database and a graph database and someone might say anything that can be done in the relational database can be done in the graph database (albeit at different speeds) so I would like if there were some terms DB A and DB B are both Query Complete - or if not that if there was a way to categorize levels of "query completeness" (I'm just going to assume my ill defined concept is totally understandable to everyone) so one can say stuff like "DB A is query level 4 but DB B is at query level 3, but of course much faster because of those limitations."
I sure hope (so as to not feel like a bigger idiot than normal) that the answer to this question isn't just a flat No.


texts: LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

texts:
Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure we dont end up at 2-node, we push the red link down when both the left and left of left of this node are black (if the cmp < 0) by the code below

// Assuming that h is red and both h.left and h.left.left
// are black, make h.left or one of its children red.
private Node moveRedLeft(Node h) {
    assert (h != null);
    assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

    flipColors(h);
    if (isRed(h.right.left)) {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
    }
    return h;
}

The fact is before we invoke this function, there is not any check if this node is red. So, This must be one of the characters of LLRB. Actually the image below just show this.

But how to prove this?


texts: How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge?

texts:
I know that regular language can be used for pattern matching , context free language is used  for syntax  matching and context sensitive for semantic or meaning of the sentence . But i have found it hard to visualize how the total process takes place. for example say we want to justify a statement of any language then how should i start to form a full sequential generation of the grammars that correctly depict the language.

what i think is as follows. say we want to first match the first characters of the statement , now we try to feed the input into many of the automata that are operating on the background and then if any of them reaches the final state we have a match and issue a token of its class like is it data type , identifiers etc but at the same time we check that if there is other automata that matches the same pattern like for 'int' there exist two automata that reaches final state one is for keywords and other is identifier but we then check for priority. now after assigning each sequence of characters a class we done with pattern matching and now move on to syntax , now we use CFG but from here i do not know how we will proceed ,so please tell me how we  process from here. also if you find anything wrong here tell me, its much appreciated.


texts: Why is exact nearest neighbor search hard in high dimensional spaces?

texts:
I started research on nearest neighbor search in IR a couple of weeks ago.
I am still very new to this field, but what I discovered so far from literature is:

1) For the exact nearest neighbor search problem, there are only efficient algorithms, if the dimension of your dataset is $<10$. With increasing dimension every e.g. tree-based algorithm seems to degrade to a linear search.

2) For datasets with a very high dimension (lets say $d > 10000$), the only feasible way of doing nearest neighbor search seems to be using mapping based approximations like LSH (locality sensitive hashing).

Most of the papers I have found so far are more about the technical details of specific techniques to solve the problem. But, before diving deep into these details, I would like to understand the problem in a more abstract way.

So my $\textbf{question}$(s) are:

a) What are theorems/theories, which describe, why tree based methods degrade to linear search, as dimension grows?

b) Are there theorems/theories, which explain the general feasibility of exact nearest neighbor search, depending on the dimension of the data?

c) Are there theorems/theories, which explain, why we need to give up exact nearest neighbor search and go to approximate nearest neighbor search? Do they give hints about the relation of the quality of the approximation (e.g. the success probability of hashing) and the dimension of the data?

I am sorry to ask three questions now, but as they are so strongly related to each other and as I am yet not experienced enough to ask the (maybe existing) unifying meta-question, I hope it is still ok.

edit:

To be more precise: I am interested, if there are theorems in the literature for the (quantitative) relations between:

1) The quality of an approximation of NN-search (e.g. the probability of success that an algorithm returns the true NN).

2) The (intrinsic/metric) dimension of the data.

3) The query time.

4) The space requirements.

From my limited knowledge of this field, I see the tradeoff between this properties, and I understand, why high dimensions can make distances "not meaningful". But, except for some results for theoretic bounds for specific techniques, I do not know any general theory or any general theorems for this fact yet. I would be very thankful, if you (the community) can give me hints, where to invest further research, where I may find, what I am searching for.


texts: Is this definition of a "complete graph" correct?

texts:
Is it correct to say that:

"A complete graph is a graph in which each vertex is connected to all other vertices in the graph"

That's how I always thought about it, the official definition is different (I know that).


texts:
One of the features the compiler for my programming language is supposed to have is the ability to draw AST-es, to make it easier to detect when syntax doesn't mean exactly what the programmer meant. That part of my compiler is runnable in a browser, you can see it here.
Thus far, I've come up with an algorithm that successfully draws diagrams like this one:

However, it fails to print good diagrams for expressions with "deeper" AST-es, such as even: 1+2+3+4+5
The diagram it draws for that one is a lot wider than what's needed to make it legible, so much so that it's illegible because of that.
So, which algorithm would you use to draw AST-es?


texts:
So I was reading about ZKP on wikipedia, the abstract example in summary goes like this:

  Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B together (see diagram) without revealing the secret word to Victor.

  Peggy takes a random entry not know to Victor
  Victor shouts to Peggy to come out of path A or B (randomly choosen)
  and so it follows that she must know the secret word in order to come out of the path that Victor chooses without revealing to Victor the secret word. Victor builds confidences the more times this is done.

However, why is Victor not allowed to see which path Peggy chooses to enter from? As this does not reveal any extra information about what the secret word is.

Why can't Victor see which way she enters and asks her to demonstrate the 4 possibilities, that is:

Enter from A and exit from A
Enter from A and exit from B
Enter from B and exit from A
Enter from B and exit from B


texts: Is there a decision algorithm with time complexity of Ө(n²)?

texts:
Is there a decision problem with a time complexity of Ө(n²)?

In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².

I thought about searching for the biggest number in matrix but the problem is that matrix is an input of O(n²) so the solution is linear.

It doesn't need to be known problem, a hypothetical one would suffice as well.

EDIT
I looking for a regular programing problem - not a Turing Machine.

It's could be an arrays, strings, graph etc.


texts: Precomputation for partial products in monoids

texts:
Suppose I have a sequence of elements $a_1,\ldots,a_n$ in a group and I want to compute, for varying $1\leq i\leq j\leq n$, the product $b_{i,j}:=\Pi_{i\leq k\leq j}a_k$. Then I can do a precomputation of all $b_{1,j}$ and later determine each needed $b_{i,j}$ as $(b_{1,i-1})^{-1}b_{1,j}$.

The cost is $O(n)$ group operations and $O(n)$ additional time for the precomputation, and $O(1)$ operations and $O(1)$ additional time for each access. Clearly optimal. So far so good.

Now what if I don't have inverses (that is I have a monoid instead of a group)?
The best I can come up with is a binary-tree like precomputed data structure. The cost of access would increase to $O(\log n)$. Can that be improved?


texts: Is solving a quadratic equation using Turing machine impossible?

texts:
I've just started Algorithms at university. There's a task to write an algorithm for a Turing machine to solve quadratic equations. The task doesn't specify if it's x^2+bx+c or ax^2+bx+c. I've searched whole bunch of information over Russian and English Internet.

I did find articles, which say it's not possible because we've got real numbers A, B, C. Please confirm if that's true. I may not get it correct.. But I think that's impossible. I still don't know how to prove my thoughts.

Thanks in advance!


texts: Is every undecidable language reducible to any other undecidable language?

texts:
For the undecidable languages I have seen so far , I am able to give a reduction from one language to other . Is it the case that every undecidable language is reducible to every other undecidable language?

If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.

Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .


texts: Average number of slots needed in slotted-Aloha

texts:
Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same slot. Transmission is as follows: when base $i$ has a packet to transmit attempts with probability $p_i, i=1,2$. Different stations make the random selection independently and corresponding probabilities are $p_1=0.5, p_2=0.25$. Initially the station 1 has 2 packets for station 2, while the other has no package.

What is the average number of slots in order all packets reach their destinations? Then if station 1 has 1 packet for station 2 and station 2 has 1 packet for station 1, what is the average number of slots? We are using slotted-Aloha.


texts:
I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I understand. It's because for each node, we could theoretically relax edges going to each vertex so it is $n * n$ times, respectively $n(n-1)$.

On the other hand, I can't figure out why this complexity isn't $O(|E|+|V|)$. For each $v \in V$, we relax only those edges $e$, which weren't computed yet. If vertex $v$ is already computed (red on gif above), we don't need to work with it anymore.

So can I say that in one way, it is true that Dijkstra is in $O(|V|)$, but if we can put into the computation number of edges, I can say that it is in $O(|V|+|E|)$?


texts: I cleaned up my computer and found 50GB of old cache on it and it made me wonder, why do computers keep old cache files?


texts: Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

texts:
In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first constructs a minimum spanning tree.

In order to prove this algorithm is a 2-approximation algorithm, the author claims that:

The weight of the minimum spanning tree $T$ is less than the cost of the optimal tour.

I am wondering if the minimum spanning tree(which is acyclic) of $G$ ensures that its weight is necessarily smaller than any tour(which is cyclic) of the same graph $G$

PS:

The original claim is:


texts: The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\text{BQP} \not\subset \text{NP}$?  Are there any specific problems known or suspected to be in $\text{BQP}$ but outside of $\text{NP}$? If so, what's the simplest known example?


texts:
The well known SAT problem is defined here for reference sake.

The DOUBLE-SAT problem is defined as

$\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\}$

How do we prove it to be NP-complete?

More than one way to prove will be appreciated.


texts: Need help constructing a Deterministic Finite Automata with AT MOST

texts:
I am stuck with constructing an DFA that has at most in it.

The question I am stuck with is:

  Design an DFA that accepts all strings over {0, 1} that contain at most two 00’s and at most three 11’s as a substring.

An answer in a form of a graph would be perfect but if someone can explain in plain words, I will appreciate that as well.


texts: Is the language of all DFAs that accept the empty language regular?

texts:
Is $E_{DFA}$ in the class of regular languages?

$\qquad E_{DFA} =  \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$

My argument is that it is because all of the DFAs in $E_{DFA}$ can be reduced to a DFA that only accepts on no input. Is this right?


texts: What does synchronous and asynchronous mean in computer science?

texts:
Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example :

Synchronous and asynchronous circuits.
Synchronous and asynchronous calls.
Synchronous and asynchronous messages.

I never really understood the real meaning of those terms, and also the common sense that different usages of synchronous and asynchronous have.

So my question is : What does synchronous and asynchronous really mean in computer science ?


texts: When does short term scheduler pick the next job?

texts:
So I have the following scheduling algorithm:
If we use a round-robin scheduler under which the CPU visits existing processes in order of their priorities (from highest priority to lowest priority) spending 3ms on each process. Assume that the CPU is not preempted from a process until the process has received its full time quantum.
So I'm confused when the short term scheduler decides which job will be scheduled next.
So for example if we have P1 with priority 0, p2 with priority 1 and p3 with priority 2 (lower priority number = higher priority) all in the ready queue. Then initially p1 is scheduled. Then once p1 finishes its time quantum what happens next?
1)Does short term scheduler context switch p1 with p2 (so p2 is now running) and THEN puts p1 in the front of the ready queue (as it has higher priority than p3)
2)Does p1 get put at the front of the ready queue THEN short term scheduler picks p1 to be run again.


texts: Ways to publish new result for NP-complete problem

texts: I am working on an NP-Hard problem. The state-of-the-art algorithm for my problem runs in O(3^n) time using dynamic programming approach. I changed the way the dynamic program works for my problem and it reduces the time complexity to O(n2^n). But, the main problem with my approach is the optimal result. More than 95% of the time my approach is giving the optimal output. Is there any way to publish my work by showing the results for the different data set. I am unable to prove the approximation ratio. Please give me any suggestion regarding this. Note: The Input size is 2^n


texts: Can we detect perfect matchings in P? in NP? in coNP?

texts:
This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question.
Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.

The class NP is a superset of class P . It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP . To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.

More precisely, if L is a set in P consisting of elements of the form (x, w), then the set
M={x:∃w,|w|≤|x|k and (x,w)∈L},

is in N P .
Let G = (V, E) be a graph. G is said to have perfect matching if there is a subset M of the edges of G so that

No two edges in M intersect (have a vertex in common); and
Every vertex of G has an edge in M.
Let MATCH be the set of all graphs that have a perfect matching. Let ~MATCH be the set of graphs that do not have a perfect matching. Let o(G) be the number of components of G that have an odd number of vertices.

Tutte’s Theorem: G∈MATCH if and only if for all subsets S of V, the number of components in G − S (the graph formed by deleting the vertices in S) with an odd number of vertices is at most |S|. That is,
G∈MATCH↔∀S⊆Vo(G−S)≤|S|.
Which of the following is true?

MATCH∈NP and ~MATCH ∉ NP
~MATCH ∈NP and MATCH ∉ NP
MATCH ∈ NP and ~MATCH ∈NP
MATCH ∉ P and ~MATCH ∉ P
None of the above

How to approach such type of questions ?


texts: 2 qubits, correct way CNOT a 3rd qubit with the 1st?

texts: Suppose I have 2 qubits in the state a|00>+b|01>+c|10>+d|11>.  And suppose I want to perform some operation between only the 1st qubit and a 3rd qubit - for example a CNOT operation.  What would be the correct way to do this multiplication?


texts:
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.

$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$

Is my hypothesis true or is this language parseable with an LL(1) parser?

One can use this simple grammar to describe $L$ (of course it is isn't LL(1) parseable):

S -> ε
S -> A
A -> aA
A -> aAb
A -> a
A -> ab


texts: Is it possible that the universe of types could be closed?

texts:
I asked a pretty vague question. I wasn't able to make it precise, but I can now. It seems to be out of the scope of the previous question, so I open another one.

In dependently-typed languages such as Agda or Idris, it's possible to define a universe inductive-recursively. However, W-types are known to have bad computational characteristics in traditional intensional type theories. Therefore, you need to be able to add new definitions of inductive data types anytime.

My question is, will HoTT improve this situation? That is, to have a closed universe. I know the general formulation of HIT is yet to be discovered, and that people seem not to be able to figure out induction-recursion, so I kind of suspect an definitive answer in the status quo. Still going to give it a chance though.


texts: Sequence Alignment with general gap penalties: proof of optimal substructure

texts:
I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works.

However, I have merely seen hand-waving explanations for the optimal substructure property for sequence alignment using a general/arbitrary gap penalty function (I realize that concave penalties are normally used but the the substructure will be the same for concave and arbitrary case)...

Can anyone provide a formal proof of what the optimal substructure is for the general (or concave) gap penalties?

Thanks


texts:
I have two vector points $p_1$ and $p_2$. Each point has a color value $c_1$ and $c_2$.
Now using linear interpolation, I would like to get the color value at point $p_3$.

Concrete example:

$\qquad \displaystyle p_1 = (1, 3) \text{ with } c_1 = (2, 4, 1)$
$\qquad \displaystyle p_2 = (4, 4) \text{ with } c_2 = (3, 1, 2)$

What color does $p_3 = (2,3)$ have?


texts:
I was trying to solve the question given below.

Algorithm :

Using divide and conquer technique, divide the input till we get a very small size array's ( let us say of size 2 ). Solve these small size array's in a brute force way. In the Merge phase it will take $\mathcal{O}(n)$ time to sum both arrays, if we get a positive sum then one contigious array will be sufficient to cover all positive numbers.

Runtime : $T(n)=2T(n/2)+\mathcal{O}(n)$

Which implies $\mathcal{O}(n\log n)$ runtime Algorithm.

Question: How to prove that one can't solve the above problem in time better than $\mathcal{O}(n\log n)$?


texts: Exponential separation between NFAs and DFAs in the presence of unions

texts:
For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an exponential separation between the two complexities, at least when the size of the alphabet is unbounded. Indeed, consider the language $L_n$ over the alphabet $\{1,\ldots,n\}$ consisting of all words not containing all symbols. Using the Myhill-Nerode theorem it is easy to calculate the DFA complexity $2^n$. On the other hand, the NFA complexity is only $n$ (if multiple initial states are allowed; otherwise it is $n+1$).
Problem 1.65 of Sipser's Theory of Computation concerns the DFA covering complexity of a language, which is the minimal $C$ such that $L$ can be written as the (not necessarily disjoint) union of languages of DFA complexity at most $C$. The DFA covering complexity of $L_n$ is only $2$.

Is there an exponential separation between NFA complexity and DFA covering complexity?


texts: Coloring of a K-ary tree using minimum paint Buckets

texts:
I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem.

Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to assign some colour to each node.

Also, each node has a value associated with it which is equal to the number of units of paint required to color it (this value is <= X (defined below) ).

Now you have an infinite number of bucket of paints each having different color available to buy but a fixed capacity of 'X' units which is same for each bucket (X <= 30).

Also there is a constraint that you can only choose a node for coloring once all nodes lying on the path from root of the tree to this particular node have been colored so you always have to start coloring from the root and then proceed.

The buying operation is sequential (You only buy the next paint bucket once you have completely used the previous).

Also each node should be completely colored with one color only. So, if you choose a bucket of paint and color a node using some units of paint from that bucket and there is no available node satisfying the constraint which you can color using the remaining paint from that bucket, then you will have to throw this bucket and buy the next bucket of paint for the next node.

You need to find out the minimum number of cans of paint that you will have to buy to color all nodes of this tree.

The best possible solution that I could think of was doing a DP with a bitmask as a state that denotes the nodes that I've not chosen so far but that has an asymptotic complexity of O(2^N * N) which is too slow for the given values of N. Can somebody think of a solution that works for the given constraints?


texts: Is this contradiction ? uniform hypergraph maximum matching has no constant factor approximation but it is bounded by minimum vertex cover

texts:
I have been so confused for a while!! Please help me with this, thank you very much in advance!!

Given hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.
A subset $M \subseteq E$ is a matching if every pair of edges from $M$ has an empty intersection.

k-uniform hypergraph is a hypergraph with edges of size k.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, which means $X_J$ is the collection of all edges that containing $v_j$.

My question: The below three statements are contradict.  If (1) Maximum matching problem has no constant approximation, (2) minimum vertex cover has k-approximation, and (3) maximum matching and minimum vertex cover are bounded by each other, why one has no constant approximation while the other has???

Maximum matching problem (is equivalent to maximum independent set problem in dual hypergraph) is NP-hard and cannot be approximated to a constant fact unless P = NP.
https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Approximation_algorithms
Minimum vertex cover in k-uniform hypergraph is k-approximation
https://pdfs.semanticscholar.org/ac41/1c620fed0d6a620e2dd007f4dca9e27e2e95.pdf
The cardinality of maximum matching set $\le$ cardinality of minimum vertex cover
$\le k* $ cardinality of maximum matching set .

PROOF: According to the Duality theorem, cardinality of maximum matching set $\le$ cardinality of minimum vertex cover number.

In addition, in k-uniform hypergraph, consider a maximal matching set $I$ of $H$. Let $X$ be the set of vertices contained in the edges of $H$ and $\tau$ be the cardinality of maximum matching set. Because every edge has size $k$, the size of set $X$ is at most $k \cdot \tau$, otherwise, those edges are not independent.

Because $X$ is the set of all vertices in this hypergraph,  $X$ intersects with every edge which means $X$ is a vertex cover.

Therefore, the cardinality of  minimum vertex cover $\le$ cardinality of $X \le k \cdot \tau$.

Hence the cardinality of maximum matching set $\le$ cardinality of minimum vertex cover
$\le k* $ cardinality of maximum matching set.


texts:
Does the rule of $n ^ a$ dominate $n ^ b$ if $a > b$ apply here as well?

My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.


texts: PCA, Eigenfaces, Face recognition: formula 8

texts:
In this paper -> https://www.cs.ucsb.edu/~mturk/Papers/jcn.pdf by Turk and Pentland, 1991, pg 76, formula (8) quote "... The simplest method for determining which face class provides the best description of an input face image is to find the face class k that minimizes the euclidean distance. (epsilon_k)^2 = || omega - omega_k||^2 (8)..."

omega^T = [w_1,w_2,...,w_k] is a vector of weights that we get from projecting any face onto a face space.

To classify some unknown face f we project f onto a face space and get some vector of weights omega_f. Is this formula trying to say that we simply take the magnitude of of all weight vectors(so omega_1 -> omega_n assuming we used n faces to create the face space) minus omega_f and we get some result epsilon_i, where epsilon_i^2 = || omega_f - omega_i||^2. Now are we trying to find min(epsilon_i) and then do we say this omega_f which corresponds to face f is recognized as omega_i which corresponds to some face i if epsilon_i is less than theta_epsilon.

is my translation of this formula correct ? the author speaks of a choosing threshold theta_epsilon but I cannot see where or how it is chosen ?


texts: Can generalized Turing machines compute all reals?

texts:
Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.

In this entry it is said:

  A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape

Does that mean that, theoretically, generalized Turing machines, cannot compute all reals? Can generalized Turing machines do (fully) hypercomputation (theoretically)?

(I know that there is strong evidence against hypercomputation. I'm asking this only from a theoretical perspective)


texts: Maximum number of vertices in undirected graph

texts:
I'm studying about time complexity of Kruskal's algorithm.

But there are two opinions to express time complexity as $O(|E|\lg|E|), O(|E|\lg|V|)$.

I know $O(|E|\lg|E|)$ is occurred from sorting by non-decreasing order of vertices.

But I don't understand of $O(|E|\lg|V|)$. This answer explains by $|E|\le|V|^2$, however from my knowledge, maximum number of vertices in undirected graph is $|E|\le\frac{|V|(|V|-1)}{2}$.

What is right time complexity for Kruskal's algorithm?


texts:
I am completing a final year project for hand gesture recognition using Hidden Markov Models
I have a fair understanding of Hidden Markov Models and how they work using simple examples such as the Unfair Casino and some Weather examples.
I am looking to implement multiple Hidden markov models where each model corresponds to a single gesture, similarly to this paper where the observed states are the angles between the coordinates of different points. This would create a sequence of numbers from 0 to 18 as seen in Figure 3 and Figure 4. .
What would the hidden states be in terms of this scenario?
The weather example has the observations 'Walk', 'Shop' and 'Clean' which would be the numbers 0-18 in the hand gesture case, however I do not know what the states 'Rainy' and 'Sunny' would correspond to in the hand gesture scenario.
Edit:
I am generating a sequence of numbers that will correspond to a certain gesture using the method mentioned above. I will then use that sequence to train a HMM and will then test that HMM using another set of recorded numbers similar to the training set. Here is an example of my scenario:
Recorded data of observed states (theta) during a gesture:
observations = [0,1,4,15,4,3,1,0,19,18,17,16,15,15,16,3,1,1,0,18...]

Recorded data of test gesture:
test = [0,2,4,15,4,2,1,0]

My goal is to create  a model from the first set of observations (which will be much longer as the gesture will be recorded many times) and determine the likelyhood of the test gesture to be from said model.
Will I need to generate a hidden state to create an accurate model of the gesture or can I just use unsupervised training for a model?
If i do have to use supervised training, should I create the hidden states using quadrants (i.e. 0-90 degrees = quadrant1, 90-180 degrees = quadrant2...)?


texts: Given consumer grade hardware,what is a reasonable upper bound for size of search space?

texts:
There's a gacha RPG I'm trying to get better at.
I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output.
The equations themselves aren't complicated: mostly linear ones, with the odd division and factorial with small integers (less then n=10) thrown in.
I'm trying to differentiate between "easy", "tough but doable if you know what you're doing" and "don't even think about it".
I suspect I'll have to simplify the problem further, but is there a way to know at which point brute force becomes unreasonable before committing to code? I only have access to consumer grade hardware (and google colab).


texts: Subgraph isomorphism on star multi-graphs with labelled edges

texts:
My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example, and two reformulations below. The second reformulation is equivalent to an unbalanced assignment problem with a binary cost matrix.

Original Formulation

I have two star multigraphs: A small pattern, and a large target. The graphs may have multiple edges between a single pair of nodes. The edges of each graph have labels from some small set of labels. I am looking for the most efficient algorithm to check if there exists a subgraph of the target which is isomorphic to the pattern.

Example

Consider the pattern

and the target

where edge colors represent labels. There is a subgraph of the target consisting of the nodes 1, 2, 3, and 5 (and some edges that I haven't given names) which is isomorphic to the pattern graph. Note that the subgraph need not be a node-induced subgraph, and is not in this case.

Reformulation 1

Enumerate the neighbors of the center of each graph: $1, 2, \dots n_{\mathrm{pattern}}$ and $1, 2, \dots n_{\mathrm{target}}$. Define $A_{i,j}=1$ if node $i$ in the target has at least as many edges of each type to the target's center as node $j$ in the pattern has to the pattern's center. If the constraint is not met, then $A_{i,j}=0$. The problem becomes: Given a binary matrix $\mathbf{A}$ with more rows than columns, does there exist a permutation of the rows such that the main diagonal is all ones?

Reformulation 2

You are given $n_{\mathrm{target}}$ workers to perform $n_{\mathrm{pattern}}$ tasks, where each worker is competent in only a subset of the tasks. Does there exist an assignment of workers to tasks such that each task has at least one competent worker assigned?


texts: Push–Relabel Maximum Flow Algorithm $x_f(s)\leq0$

texts:
I'm looking at Push–Relabel Maximum Flow Algorithm (or Goldberg-Tarjan Algorithm) and trying to solve some homework question.
As part of the answer I'm trying to prove $x_{f}(s)\leq0$
  during the entire algorithm run (where $s$
  is the source, and $x_{f}:V\to\mathbb{R}$
  is the excess function $x_{f}\left(u\right)=\underset{v\in V}{\sum}f\left(v,u\right)$
 ).

I feel like this somehow should be trivial, but no matter what I've tried, I was unable to prove it.

I know pushes into $s$ are possible
 , just not sure how to show they don't make $x_{f}\left(s\right)>0$
 .

I assume the proof would be by induction, as at the start $x_{f}\left(s\right)\leq0$
  since the initialization step saturates all of $s$
 's adjancet nodes.

If we assume $x_{f}\left(s\right)\leq0$
 , we have to show that after one iteration of the algorithm it still holds.

Relabel is trivial since it doesn't change the flow.
A Push from nodes unrelated to s is trivial as well.
A Push from s to any other node would decrease $x_{f}\left(s\right)$
so that is trivial as well.
I'm only left with the case $Push\left(u,s\right)$.

Help or direction would be appreciated,Thanks!


texts: Divide self-intersecting polygon into simple polygons

texts:
My question is similar to question here Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects.

I have to divide it into simple polygons and tessellate them later.

I have an issue how we currently select the edge after the intersection point is encountered.
Right now we select an intersecting-edge which makes the smallest angle with the preceding edge.
This approach simplifies some intersecting loops (e.g. horizontal '8' is divided into two 'o' loops).

But this approach has some issue. Say two polygons one inside another. Such polygons are not divided into two loops.

I plan to select an intersecting-edge which makes the largest angle with the preceding edge. This way I can get the outermost loop first and than I will form the internal loops with remaining edges.
This will solve the problem for 'two polygons one inside another'. (This will fail for cases such as 'horizontal '8''. But this is OK as such case is handles while tessellating polygon)

Are there any known/unforeseen problems with this approach?


texts: Remove parallel edges in a directed graph in linear time

texts:
Is there a $O(|V|+|E|)$ algorithm to find and remove all parallel edges in a directed graph? I'm stuck because each idea I've thought of boils down to $deg(v)^2$ comparisons per $v$ which is of course not linear.

Thanks.


texts: How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

texts:
I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression.

Now there is a theorem for the last structure above:

  The complexity of any sequence of m operations of Makeset, Union and Find, n of which are of Makeset, on a Quick Union by rank and path compression is in the worst case equal to $O(m\,\, G(n))$. Where $G(n)$ is the inverse of the  Ackerman function

And this one is the Kruskal algorithm in pseudocode. Let $G=(V,E)$ be an undirected, connected and weighted graph, where $V$ is the set of vertices and $E$ the set of edges, then the following algorithm returns a Set $A$ that contains the edges of the Minimum Spanning Tree.

Kruskal(Graph G) {
    Set A

    For every vertex v in V {
         Makeset(v)
    }

    Order the edges in E in ascending order by weight

    For every edge (u,v) {
        If find(u) != find(v) {
            union(u,v)
            A = A + (u,v)
        }
    }

    Return A
}

Let's go back to my problem.
I understand that the second loop is executed at the worst $m$ times (the number of edges). Hence the number of operations of union and find is $m$, while the number of makeset is $n$ (the number of vertices).

The book where I'm studying, after making similar observations says that the complexity of the above operations equals to $O((m+n)\,\,G(n))$ and I don't get why.
Of course, the other complexity to order the edges is $O(m\,\, log\, m)$ so the final one is:
$O(m\,\, log\, m) + O((m+n)\,\,G(n))$
But $m>n-1$ then
$=O(m\,\, log\, m) + O((m)\,\,G(n))$
However $m<n^2 \implies log\, m < 2log\, n \implies log(m)=O(log n)$, so
$=O(m\,\, log\, n) + O((m)\,\,G(n))$
$=O(m\,\, log\, n)$

Can you explain to me how to get the $O((m+n)\,\,G(n))$ complexity from the algorithm?


texts: Propositional logic of arguments and undercuts

texts:
The setting

An argument from a set of formulas $\Delta$ is a pair $\langle \Phi, \alpha \rangle$ such that

$\Phi \subseteq \Delta$
$\Phi \nvdash \bot$
$\Phi \vdash \alpha$ (this is what I am wondering about)
There is no $\Phi' \subset \Phi$ such that $\Phi' \vdash \alpha$.

I am trying to think of how this undercut works.

If $\langle \Phi, \alpha \rangle$ and $\langle \Phi, \beta \rangle$ are arguments,then:

$\langle \Phi, \alpha \rangle$ rebuts $\langle \Phi, \beta \rangle$ iff $\alpha \vdash \neg\beta$
$\langle \Phi, \alpha \rangle$ undercuts $\langle \Psi, \beta \rangle$ iff $\alpha \vdash \neg\beta \wedge \Psi$

The exercise

The original statement is
$$\langle\{\gamma,\gamma\rightarrow\neg\beta\},\neg(\beta\wedge(\beta\rightarrow\alpha))\rangle \quad \text{undercuts} \quad \langle\{\beta,\beta\rightarrow\alpha\},\alpha\rangle$$

I believe these two should both be arguments.

$$\{\gamma,\gamma\rightarrow\neg\beta\} \vdash \neg(\beta\wedge(\beta\rightarrow\alpha))$$

My attempt

The left side is

$$\{\gamma,\gamma\rightarrow\neg\beta \} \vdash \neg\beta$$

The right side is

$$\neg(\beta\wedge(\beta\rightarrow\alpha)) \vdash \neg(\beta\wedge\neg\beta\vee\alpha) \vdash \neg\alpha$$

Is my proof right? What is the next step?


texts: Logarithmic space verifier with unbounded witness

texts:
this is a HW question, but its considered a bonus question so I'd appreciate a direction.

Definitions:

The actual question:

**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.

My thoughts on the question:

My intuition is that C2 = NL, because NSPACE(O(f(n)) ⊆ DTIME(2^O(f(n))), so for a verifier for a language in C2 as defined in the question, as it anyway runs in logarithmic space will run in polynomial time and therefore it won't be able to read more than a polynomial length witness so it doesn't add power. I already proved that the set of languages that are decided by a logspace verifier with read once witness tape and polynomial length witness are NL.

So more formally:

For Nl ⊆ C2, then for a language L that is in NL and decided by a logspace NTM M, it feels to me like I could just treat the witness as a configurations sequence that describes the choices that M did, and just check the validity of the transitions according to the delta function of M and accept only if all transitions are valid and the last configuration is accepting. This will need logarithmic space. So L in C2 (basically this is the same as bounded length witness case).

For C2 ⊆ NL:
This feels harder. Denote L as a C2 language that is decided by a verifier as defined in the question. When I think about this, the verifier can read from the witness tape without writing the content to the work tape, so it could read the whole witness and still remain in the logarithmic space bound, and it would be equal to a NTM that performs |w| (length of the witness) of non deterministic choices while using logarithmic space on its work tape. Basically it means the NTM makes unbounded number of choices.

So on one hand, I don't think the definition of a NL NTM bounds the number of non-deterministic decisions (as long as the space complexity holds). So even with the arbitrary number of non deterministic choices, the complexity class is still NL because the space complexity doesn't change. But on the other hand, this means a "deeper configuration graph" and it feels like the time complexity of this NTM is greatly increasing and it doesn't feel right.

So in the case that the number of choices doesn't affect the complexity, this will mean that C2 ⊆ NL cause every time the verifier reads a character of the witness, we can make a non deterministic choice for that character and simulate the verifier.

But if this is wrong, then I'm not sure how to proceed.

I would appreciate pointing me to the correct direction, thanks!

*** Again, this is not for submission, by I would really like to solve it.