texts: Can area-partitioning lose included points due to floating point precision?

texts:
I'm currently partitioning a big area $A$ into $n$  areas $B_i$ such that
 $$\bigcup_{i=1}^n B_i  = A$$

I have geo-coordinates which I know are in $A$ (also with the finite precision of floats).

Obviously, for every point $p$ in $A$ there has to be an area $B_i$ such that the point is in $B_i$. Formally:

$$p \in A \Rightarrow \exists i: p \in B_i$$

But due to floating point precision, I wonder if it could happen that for all $B_i$ the B_i.intersects(p) method returns false. Formally:

$$\forall i: \neg B_i.\texttt{intersects}(p)$$

All areas are polygons and neighboring polygons share some points which define the polygons.

If the answer is yes, then an example would be good. It would be awesome if one could also quantify the probability of this.

(In my current case, I use shapely.)


texts: What is a fixed point in the context of Roger's fixed-point theorem?

texts: In the Wikipedia article on Rogers' theorem, it is stated that all total computable functions have a fixed point.  The notation is a little hard for me to understand; a symbol is used that is used to denote "semantic equivalence."  I do not know what semantic equivalence is; I would appreciate it if someone could shed some light on what a fixed point is in this context, and on what semantic equivalence is in this context.


texts:
The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number.

The only thing I have achieved is to get an automaton that recognizes
$(a^n)(b^n)$ but that's only part of what I need.

Thanks a lot for your help.


texts:
Operate on an image by performing Median Filtering in a 3x3 window.
Operate on the resulting image by performing, again, Median Filtering in a 3x3 window.
Can the resulting image be obtained from a single Median filtering?

my initial thought is that it can be done with the right mask. maybe a median next to a median.
but i'm not sure.


texts: Sorting an array of length $n$ with $k$ distinct elements

texts:
There is an integer array that contain $n$ numbers, in the array there are $k$ distinct elements up to $k = 50$.
Is it possible to sort this array in linear time, by using only comparisons?

I know that comparison sorts cannot perform better than $\mathcal O(n\log n)$, so maybe I have to show a sort function that sort this array in less than $\mathcal O(n\log n)$, and it will be a contradiction.


texts: Show that the following language is not recursive:

texts: $L = \{w \mid M_w \text{exists and it accepts a word } x_1 = 0x \text{ if and only if it accepts } x_2 = 1x\}$ ($x \in \Sigma^*$, so $x_1$ is starting with a 0 and $x_2$ is obtained from $x_1$ by changing the first 0 to a 1).


texts:
I search good articles or books on neural network. unfortunately i don't a lot of time and only now i started to research this field. so i actually search a good source that will give the fundamental (basic theory and tools to understand complexed neuroal networks).
any suggestion?


texts: How to find online nodes in real-time in graph?

texts:
There is group of nodes. There are three type of nodes:

leader node .
follower node - connected to one or more leader directly or indirectly.
vagrant node - no connected to any leader directly or indirectly.
We can dynamically connect any node to any other node .

link(node1, node2)

unlink(node1, node2)
After random link and unlink operations

listNotConnected()
should return list of vagrant node or unconnected nodes .

How to find list of nodes which are not connected to leader ? How to find it in real time ?


texts: How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points

texts:
I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how important it is to avoid them). I want to find the smallest number of clusters that group together the 8 target points (in groups of 2-8), while maximizing the distance away from the unwanted points - it's also important that not only do the desired points making the cluster have to be far away from the unwanted points, the interior points of the shape made by the cluster also need to be maximally distant from the unwanted points.

My current train of thought is as follows, but I'm open to suggestions (psuedocode):

for combination in all possible combinations of 2-8 target points
  combination.score = 0
  for each unwanted point
    combination.score += distance(combination, unwanted point) * unwanted point.priority

Then I'd use a simple greedy algorithm to find the groupings with the highest scores that contain all the desired points. The one outstanding question I haven't quite figured out yet is how to find the distance between an arbitrary point and a shape made up of n points in 512-dimensional space.

For context, the 512-dimensional coordinates are coming from a Tensorflow model, which I mention because I'm aware of machine learning techniques for reducing dimensionality, but am unsure of what approaches would be appropriate here or what to look for in comparing those/if that would help reduce the complexity of this problem.

This is the Tensorflow model in question if anybody is curious


texts: Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

texts:
I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality, and completeness, I would like to go a bit further than that and compare the sparseness of the tree, the branching factor, solution depth, etc. I would like to compare the algorithms (A*, BFS, DFS, IDS tree-search algorithms (i.e. without keeping a list of visited nodes)) pairwise and ask the question what would be the situation where one or the other would be preferred.

So far I have written down everything I can think of and I would like to know:

Is what I have written down correct?
Is there something I have missed for specific comparisons?
Is there something I missed for all of them? I.e. some specific quality I did not think of?
Something I struggled with was which algorithm to prefer if the tree is sparse/dense - I took an educated guess for most of them but I am uncertain of my answers. If anyone has any guidance in that part, it would be terrific.

I have also added some questions here and there. I realise this is a lot but I greatly appreciate any help - any hints are welcome as well.

1 DFS vs IDS

When to prefer DFS?

If the solutions are frequent deeper in the tree

When to prefer IDS?

If you need at least one of them: optimality, completeness
If the tree is infinite (as DFS might get stuck)
If the solution is located in the upper part of the tree
If the solution is located deep in the tree and they are infrequent

Is there anything that can be said about sparseness/denseness for IDS here?

2 DFS vs BFS

When to prefer DFS?

If the tree has a large branching factor (BFS gets slow with wide trees)
If solutions and frequent and located deep in the tree
If there is a limit to how much memory can be used

When to prefer BFS?

If at least one of the two is required: optimality, completeness
If the tree is infinite
If the maximum depth is much larger than the branching factor
If you know that the solution is now far from the root of the tree
If solutions are rare and located deep in the tree
When the tree is sparse (unsure why)

3 DFS vs A*

When to prefer DFS?

If the heuristic of A* is poor
If the goal is optimality and the A* heuristic is not admissible
If solutions are frequent and located deep in the tree

When to prefer A*?

If the tree is infinite
If the tree is dense (unsure why)
In general blind search is slower than heuristic search, therefore for a good enough heuristic, A* should be prefered

Is there anything that can be said about the branching factor here?

4 BFS vs A*

When to prefer A*?

If memory space is limited
If the tree has a high branching factor
If the tree is dense
Although the complexity of queue is slightly better than that of priority queue, A*'s time complexity is usually better than BFS's time complexity with a good enough heuristic

When to prefer BFS?

If the tree has a low branching factor
If the tree is dense
If the heuristic is poor
If the heuristic is not admissible and optimality is required

Is there anything that can be said about frequent/infrequent solutions here?

5 BFS vs IDS

When to prefer IDS?

When a lower space complexity is required and somewhat lower time complexity is acceptable

When to prefer BFS?

If the solution is in the upper part of the tree as it is less costly to generate the nodes once

I am a bit lost here - is there anything else that can be said about finiteness, denseness, frequency of solutions of the graph?

6 A* vs IDS

When to prefer IDS?

When the A* algorithm has a poor heuristic
When optimality is required and the A* heuristic is not admissible
If there are limitations to the amount of memory available

When to prefer A*?

In general blind search is slower than heuristic search, therefore for a good enough heuristic, A* should be prefered


texts: DFA that accepts any integer $n$ such that $n \bmod 7 =1$

texts:
It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.

Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.


texts:
Most modern compilers split their syntax analysis into
a lexical phase that is followed by a parsing phase.
The lexical phase is given by a regular expression, while parsing
is guided by a context-free grammar.

What class of languages can be recognised this way?
Context-free languages, or can we get into context-sensitive
languages?


texts: Creating Map of Unknown Space without being able to see obstacles

texts:
I'm trying to create a program where I have a user walking around a random space that contains obstacles, but I can't see where the obstacles are. The point is that as a user walks around, based on where they are traveling, the program creates a rough map of places where there aren't any obstacles (if the user is able to go over some point, there isn't an obstacle there).
Anyone have any ideas of how to approach this, or could direct me to any sources? I've looked into how GPS and other forms of mapping work but the difficulty with this program is that I don't have a pre-built map to go off of, I essentially have to create a map of a random space while blindfolded.


texts: Finding the longest repeating subsequence

texts:
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ such that $w=w' \cdot w' $. That is, $w$ is a string whose halves appear twice in a row. Note that $w$ is a subsequence of $s$, but not necessarily a substring.

Examples:

For 'ababccabdc' it will be 'abcabc', because 'abc'='abc' and 'abc' appears (at least) twice in 'ababccabdc'.

For 'addbacddabcd' one option is 'dddd' because 'dd' appears twice (I cannot use the same letter several times, but here i have 4 'd's so its ok), but its of lebngth 4. I can find a better one of length 8: 'abcdabcd', because 'abcd' is a substring of 'addbacddabcd' that appears twice.

I'm interested in finding the longest repeating subsequence. This is also called "finding the longest/largest square", but I've read many articles in which a square is defined for a substring and not for a subsequence.

I can easily use a brute force algorithm that will take $O(n^3)$ by iterating on all options for a breakpoint in the string, and then I will have two strings in which I'll be looking for largest/longest common subsequence, but each check will take $O(n^2)$ using a dynamic programming technique, so the entire time will be $O(n^3)$. I found a more efficient algorithm for longest common subsequence which takes $O(\frac{n^2}{\log n})$ , so the running time will be $O(\frac{n^3}{\log n})$.

I am looking for a more efficient algorithm for longest repeating subsequence problem. Perhaps my idea of iterating over all breakpoints wastes too much time, and can be reduced to less iterations. Or perhaps an algorithm with a different attitude can solve this problem.

I've searched in many journals and previous questions, and most of the results I found were about a substring and not about a subsequence.

I've also read that this can be done using suffix trees, but this too was relevant to substrings and I am not sure if such an idea can be extended for subsequence.

I'm looking for a solution that runs in time $O(n^2)$. If there exists one in time $O(n \cdot \log n)$ that will be even better (I am not sure if such exists).


texts: Floyd's Cycle detection algorithm | Determining the starting point of cycle

texts:
I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)

I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.

Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?


texts: Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

texts:
The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So the total points is $\sum_{i=1}^{n}x_ip_i$. Our rule is that we cannot have three consecutive $1$'s, and we want to know what is highest possible points we can get from a length-$n$ sequence.

I propose an algorithm, but I find examples that leads to non-optimal solution. My algorithm basically goes as follows: let $P(k-1)$ be the highest possible points we can get for the length-$(k-1)$ sequence, with points $p_1,\ldots,p_{k-1}$, and it corresponds to an optimal length-$(k-1)$ sequence $s_{k-1}$, then I add an $1$ at $k_{th}$ position if it's possible to do so. If it is not possible to add $1$, then the previous 3 terms must be $011$. Then I compare $p_k,p_{k-1}$ and $p_{k-2}$, and put two $1$'s at two positions with the highest points, and put $0$ on remaining position. Hence I get $P(k)$, and $P(n)$ is computed by computing each $P(i)$.

However, consider the example of $n=4$, and $p_1=1,p_2=3,p_3=2,p_4=4$, this algorithm will produce $0101$, and $P(4)=7$, while $1101$ will have $8$ points.

Anyone has a suggestions on what is a true algorithm for this problem? Thanks!


texts: Is there any strategy to brute force search?

texts:
I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space.  This might be naive of me, but I imagine that how I choose to enumerate through the search space could greatly affect whether or not my algorithm works well in practice.

Consider the following decision problem as a simplified example.

Input: A polynomial $p(x)$ with integer coefficients and a natural number $k$.

Question: Does there exist $i \in [k]$ such that $p(i) = 0$?

Now, there could be many different algorithms for solving this problem, but I decide to choose a brute force approach.  Consider the following strategies for enumerating through the search space.

Ascending Strategy: I could check if $p(1)$ is 0, then $p(2)$, then $p(3)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Descending Strategy: I could check if $p(k)$ is 0, then $p(k-1)$, then $p(k-2)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Popularity Strategy: I could store a small list $L$ of most popular solutions and try those first before trying the numbers in $[k] - L$.

Sieve Strategy: I could do a sort of sieve enumeration.  I try all numbers divisible by 2 in $[k]$, then numbers divisible by 3 in $[k]$, then 5, then 7, then 11, then 13, and so on.  (Assuming that I have access to some large pre-computed list of primes.)

Randomness Strategy: Maybe there is an interesting enumeration strategy that utilizes a large string of random bits.

Basically, I'm looking to answer the following questions about brute force search algorithms:

Question A: Are there any benefits to choosing a specific enumeration strategy?

Question B: Are there any examples of search problems where in practice you would choose an interesting enumeration strategy?  I feel like there may be some search problems where in practice a variant of the Popularity Strategy works effectively.


texts: Show that boring boolean circuit belongs to NP-complete class

texts:
We say that a boolean circuit is boring if it returns the same
  result for $>\frac34$ possible input, where we have $n$ input gates.
  Hence, boring circuit returns the same output ($0$ or $1$) for
  $>\frac34 2^n$ inputs.   Prove that checking if boolean circuit is boring is NP-complete

Can you help me? I have no idea how to start. I tried to reduce $3$-SAT but no result.


texts: How to prove that concatenating a language A and A* is commutative?

texts:
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is a language, then
\begin{align*}
AA^* & = A(A^0\cup A^1\cup\cdots) \tag{Definition of $A^*$}\\
     & = A^1\cup A^2\cdots        \tag{Distributive law}   \\
     & = (A^0\cup A^1\cup\cdots)A \tag{Distributive law}  \\
     & = A^*A.
\end{align*}
Is this enough? I'm thinking that in order for it to be a proper proof, I have to show that $AA^*$ and $A^*A$ are subsets of each other. That is, take an element $s = xy$ where $x\in A$ and $y\in A^*$ and show that $x\in A^*$ and $y\in A$ (and vice versa). However, I get stuck very early when doing that method.


texts: Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?

texts:
COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational numbers, graphs, grammars, semantics etc. are very concisely represented.

However, since I grew to like the proof assistant, I was wondering whether there are libraries for uncountable structures, like real numbers, complex numbers, probability bounds and such. I am of course aware that one cannot define these structures inductively (at least not as far as I know), but they can be defined axiomatically, using for instance the axiomatic approach.

Is there any work that provides basic properties, or even probabilistic bounds like Chernoff bound or union bound as a library?


texts: What are some research papers or techniques that deals with fitting clothes on a human?

texts: Given an image of a dress (from different angles), what could be ways to fit it on a human image (again multiple angles corresponding to dress)? Any link to research papers or tutorial regarding this?


texts: Balanced allocation-Hash table- overflow probability

texts:
My question is related to this:
Hash-Table in Practice

In [1] page 7, it is said that  if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ elements with a high probability.

Question 1: Why is $O()$ used in the above estimation?

Question 2: Does it mean the probability that a bin contains more than the above value is negligible?

[1]. http://www.pinkas.net/PAPERS/FNP04.pdf


texts: Complexity of union-find with path-compression, without rank

texts:
Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of $O(\alpha(n))$ (where $\alpha$ is the inverse of the Ackerman function).  However, it does not mention the running time of path compression without union rank, which is what I usually implement myself.

What's the amortized time complexity of union-find with the path-compression optimization, but without the union by rank optimization?


texts: Time complexity of Dynamic Array via repeated doubling

texts:
When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the new one? Correct?

So to compute the complexity we have 1 + 2 + 4 + 8 + .... number of steps? Correct?

But

 1 + 2^1 + 2^2 + .... + 2^n  =  (2^(n-1) - 1)  ~  O(2^n).

However it is given that

 1 + 2 + 4 + ... + n/4 + n/2 + n  ~  O(n).

Which one is correct? And why? Thanks


texts: Which grows asymptotically faster, $\log \sqrt{n}$ or $4 \log n$?

texts:
I have been looking at the question as to which grows faster asymptotically; $\log \sqrt n$ or $4 \log n$.  I have applied L'Hopitals rule and ended up with 1/8.  This would imply that they grow at same rate.
Graphically $4 \log n$ is always above $\log \sqrt n$.  Also from a perspective that $4 \log n$ is $\log n^4$ would imply intuitively that growth of $4 \log n$ is faster asymptotically
There appear to be contradictions.


texts: How does equality works for qubit-vectors?

texts: A bitvector of length N has 2^N different values. How many different values has a quantum bit vector of length N? Is it possible to test two quantum bit vectors for equality?


texts: 2-3 tree: Sum of leaves in a given range

texts:
I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which their key is within a given interval. The time complexity of the function needs to be $O(\log n)$.
I thought about saving for each internal node the sum of the leaves in its subtree, but I don't know how to continue from there.


texts: String membership in hash set time complexity

texts: Given a string s and a hashset of strings words, what is the time complexity of the operation: s in words? Assume all strings have length M. My current guess is O(M) to compute the hash of s, O(1) to find that bucket in the hash table, and O(M*number of strings in the bucket) to compare the strings in the bucket and the s , so a total of O(M*number of strings in the bucket). Not assuming any fancy string comparison algorithms here--want to focus more on the other parts.


texts:
A graph G has n vertices and m edges
The Minimum Cycler of G is a set S of edges of minimum total weight such that every cycle in G contains at least one edge in S.
Devise an algorithm that finds the Minimum Cycler in O(m log n) time
My Approach-
Consider a cycler S. We can reduce our focus only to the cycler with minimal
set of edges. ie. if we remove any edge from the cycler than it ceases to
remain a cycler. Because all other cyclers are not useful or won't anyways
count as one with minimum edge sum.
Now given a reduced cycler (or a minimal one) my target is to prove that
G\S is a spanning tree.
To show this we will have to prove that :

G\S is acyclic
G\S is connected

(1) is trivial as if G\S has a cycle than S is not a cycler.
(2) Suppose G\S is disconnected. Let E be the minimal set of edges that
we can add to G\S to make it connected. So we have G\S+E.This cannot have   a cycle because otherwise E won't be the minimal set of edges which will make
it connected. Now consider S-E. Will this be a cycler is one question and
whether S will have some edges in common with E is another. S-E will be
a cycler because if there is any cycle in G than that had an edge in S
I am stuck here unable to extend this argument to reach its final stage


texts: How to generate inputs to evaluate the performance of an implementation?

texts: How can we assert that the performance of an implementation matches the expected performance defined in terms of Big-$\mathcal{O}$ and friends by generating best/worst case inputs? I'm thinking of a table whose columns are input length, expected running time, actual running time. Are there general methods for generating inputs for evaluation?


texts: How to perform matrix multiplication in Mixing Columns step of AES?

texts:
I am studying AES and trying to implement it. But I am having difficulty understanding the Mixing Column step. In that step we have to perform matrix multiplication between the state matrix and another fixed matrix. Here is the example given in the material I am studying from:

I am not getting the 03*2F part. How did it turn into (02*2F)xor2F? Is the material correct or does it have some mistake?
Edit:
I got that 3 = 2 xor 1 hence 3 x 2F = (2 xor 1) x 2F = (2 x 2F) xor 2F but what in case if 4 x 2F? 4 = 2 xor 6 so (2 xor 6) x 2F then what?


texts: Matrix multiplication randomised verification - error probability

texts:
Let s  say we have an algorithm that takes as input 3 matrix A,B and C

  $$ \text{Input} :A,B,C \in Mat(n\times n)$$
  $$\text{Question} :\text{is } A\cdot B=C$$

the algorith works as follow ;

$$ \text{if }(A\cdot B)_{ij}=C_{ij} \Rightarrow A\cdot B=C  $$
$$ \text{if }(A\cdot B)_{ij} \neq C_{ij} \Rightarrow A\cdot B \neq C  $$

with random chosen $i$ and $j$  .

I have to find in this case the error probrabilty. Can someone please give me some hints.

This problem looks a bit like  the freivalds algorithm, somehow i think i have to drive a trick with it so solve mine but i am not sure .


texts: What is meant by interrupts in the context of operating systems?

texts:
I've decided to read Operating Systems Concepts by Silberschatz, Galvin Gagne (8th edition) over the summer. I've gotten to a topic that's confusing me - interrupts and their role as it relates to operating systems.

The text says that an operating system will begin a first process such as "init" and then wait for an "event" to occur and this event is usually signaled by an interrupt. The text also says that the interrupt can come from either the hardware or the software. How does this work, in a little more detail? Is the operating system driven by interrupts?

I am just looking for some big picture understanding.


texts: How to determine agreement between two sentences?

texts: A common Natural Language Processing (NLP) task is to determine semantic similarity between two sentences. Has the question of agreement/disagreement between two sentences been covered in NLP or other literature? I tried searching on Google Scholar but didn't get any relevant results.


texts: Does this DFA describe this regular expression?

texts:
For the expression (ab)*ba I came up with the following (very poorly drawn):

However, this was not the correct answer - apparently the solution requires five states. I don't understand why my DFA doesn't describe the expression. My interpretation of the expression is "ab any number of times, followed by ba". Is this correct?


texts: Propositional logic --- syntactical completeness

texts:
Lets consider propositional logic. We say a proof system for propositional logic is syntactically (negation) complete if for every $\alpha$, either $\alpha$ or $\neg \alpha$ are provable within the system, i.e., $\Sigma \vdash \alpha$ or $\Sigma \vdash \neg \alpha$. (I assume standard definitions for $\Sigma$ and $\vdash$).

It seems to be me that no sound proof system for propositional logic could prove $p$ or $\neg p$ from empty set of sentences, where $p$ is a propositional atom. So, propositional logic is not syntactically complete.

Now, it is to my understanding that this is kind of completeness Godel was considering in his Incompleteness Theorem for FOL. Since FOL (with abuse of terminology) subsumes propositional logic, it trivially holds that FOL is not syntactically complete either. This seems to simple, so I am wondering what am I doing wrong? Or his proof focused on Peano arithmetic specifically?

Related: link


texts: Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

texts:
In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.

I have not been able to solve this one:

  The set of strings of 0s and 1s, beginning with a 1, and interpreted
  as an integer, that integer is prime.

My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).


texts: Is the undecidability of a given problem undecidable?

texts: Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is that yes, undecidability of a given problem is undecidable, because the above algorithm seems reducible to the Halting problem which cannot be solved using a Turing machine. However, the human mind seems to be able to determine the undecidability of a given problem, and thus the above algorithm is constructable (Unless of course, there exist problems so unimaginably hard that it is impossible to determine if they are undecidable or not). So, which one of these guesses is the correct one, and why? Is undecidability undecidable or decidable?


texts: What restrictions apply to query and target vector encoding on fast-forward neural networks?

texts:
I'm currently studying fast-forward multi-layer neural networks with back propagation, in the book I see that all query and target vectors are binary-encoded, this makes me believe that this is the only allowed encoding, yet all other neurons in the hidden layers and output layer can take on any real value between 0 and 1.

Now I am creating my own neural network and I want to classify an image by using the RGB values of every pixel as input neurons in some way.

So now my question is, as the title states, what restrictions apply to the encoding pattern used for query and target vectors?


texts: What is the simplest quantum algorithm to visualize a quantum computation?

texts:
I'm interested to visualize how a simple quantum computation can be done, step by step. Can you help me?

I need any simple example of how qubits can be used to make a computation.


texts: Hardness of finding a true or a false assignment into a generic boolean formula?

texts:
I read some research that analyzes the hardness of SAT solving in the average case.
In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less between 4 and 5) in which solving the formula is hard. But it is easy (between 0 and 4) high probability of satisfiable assignment and high probability of unsatisfiable assignment after ratio 5.

My question is, what about a generic formula that is not in normal form. We can say something about its hardness?


texts: Decidability of a language of Turing Machine descriptions

texts:
Given the language

  $\{ <M> \mid\:$ M is a Turing machine           and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$

How can one prove that this language is decidable?


texts: Persistent Homology vs Clustering Methods

texts:
How do persistent homology and clustering methods for data point clouds differ? I'm specifically interested in the application to gene expression data of cancer patients, but any example works.

I understand that a hierarchical clustering method might impose 'nearness' on two points (patients) that are ancestrally related (have similar gene expression profiles), but in order to find the interesting groups you have to manually choose a threshold for nearness, and this criterion can often obscure the interesting biology (e.g. a few of the patients that survived are mixed in with some that died based on nearness of gene expression values; with the enormity of some datasets, the small details that would set a few special patients apart from a large sub-group are lost).

From what I gather, persistent homology, with an appropriately chosen metric, has better results because it doesn't partition the data and break it apart to find the interesting sub-groups. Rather, it plays with the geometry of the data in some way that allows for the elucidation of these details that clustering methods would generally obscure. How does this work, generally?


texts:
Let's consider the following algorithm to multiply squares matrix:
A is a matrix of NxN.
r_i, r_j defines interval of rows. For example r_i = 2, r_j=3 means the second and the third rows. c_i, c_j means the same as r_i, r_j but for columns. We assume that N = 2^s for some s.

mul(A, B, r_i, r_j, c_i, c_j){
if(r_i != r_j){
   r_m = floor((r_i+r_j)/2)

   mul(A, B,  r_i, r_m, c_i, c_j)
   mul(A, B, r_m+1, r_j, c_i, c_j)
} else if(c_i != c_j){
   c_m = floor((c_i+c_j)/2)
   mul(A, B, r_i,r_j, c_i, c_m)
   mul(A, B, r_i, r_j, c_m+1, c_j)
}else{
 for i = 1 to N:
    C[r_i][c_i] += A[r_i][i] * B[i][c_i]
 }

}

And the most important:

Complexity of that algorithm takes: T(n) = 4T(n/2) + n = O(n^2)

And it is not correct. The correct answer is O(n^3). Why my computation is incorrect.


texts: Can a Turing Machine simulate every possible Turing Machine?

texts:
Related to my answer on this question, I'm not sure of a detail.

Assume you have a Turing Machine which simulates all possible Turing Machines all at once (meaning it does not "page" its data, i.e. it can't erase data from one "process" to write data from another "process"; it must keep all "processes" "in memory" at the same time).  Then, this Turing Machine must simulate itself, because it is a Turing Machine and the definition of this machine is that it simulates all possible Turing Machines.  It must also simulate the simulation of itself, and the simulation of that, and so on, infinitely recursive.  Therefore, this Turing Machine must have infinite data on its tape.

My question is, can this Turing Machine exist, and why or why not?


texts: Having trouble understanding how to prove a language context free?

texts:
I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses Backward Operation.
Let B be the language {w|w = BW(w) and has equal number of a's and b's}, where Σ={a,b} and BW(L)={cn,…c0∣c0,…cn ∈ L},c^i∈Σ. Prove that language B is not a context-free language.
Help would be highly appreciated.


texts: How to do -8 x -8 in a 4 bit booth multiplier?

texts:
In the general case of an n bit booth multiplier, the maximum negative value is -2n-1. So with 4 bits we can represent -8 x -8 (M=1000, Q=1000). Now if we follow Booth's algorithm for multiplying n-bit numbers:

count
A
Q
Q-1
Operation

4
0000
1000
0
Initial Conditions

3
0000
0100
0
(00) Shift and decrement count

2
0000
0010
0
(00) Shift and decrement count

1
0000
0001
0
(00) Shift and decrement count

1
1000
0001
0
(10) A <= A-M

0
1100
0000
1
Shift and decrement count

The result is 110000002 = -6410 which is clearly not correct. Am I missing something? Is this just a limitation of Booth's algorithm? I have a hard time believing this isn't a known issue, but I can't seem to find any source that even mentions it.
I can see the issue is when we need to do A<=A-M, since the result should be +8 in this case which can't be expressed in 4-bit 2's complement. How would this be addressed in an actual hardware implementation of Booth's algorithm?


texts: How many sequences in a prefix code can be compressed by m bits?

texts:
I have a little understanding problem with Appendix A ("Universal Codes") in the paper "Shannon Information and Kolmogorov complexity" by Gründwald and Vitanyi (Link).

At the end of page 50, they say something corresponding to:

  For each Prefix-code, the fraction of sequences of length $n$ that can be compressed by more than $m$ bits is less than $2^{-m}$.

Either this is a writing mistake or I should make a break from reading.

It is easy to see, that the number of strings with length $n$ and compression length smaller than $m$ is smaller $2^{m-n}$ for a prefix-code because there are simple not enough "shorter" words.. Did they mean this information?

It is also easy to understand, that the Kraft-Inequality $\sum_{x\in X}2^{-l(x)}\leq1$ holds for a prefix code  with source word set $X$ and the compression length $l(x)$ for strings $x\in X$.

Is that only a writing mistake? Respectively can you tell me an explanation?


texts:
How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?

I know that the Wikipedia article has a section on it, but it uses a lot of mathematical notation which I am unfamiliar with it. I also found the following paper: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf However the paper is very long and provides a complete analysis of asymptotic analysis rather than just giving a definition. Again the frequent usage of mathematical notation made it very hard to understand.

Could someone provide a definition of asymptotic analysis without the complex mathematical notation?


texts: Automata with minimal number of states using reverse

texts: So, by the Bzozowski theorem, if A is DFA  det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an DFA which is NOT minimal (the min. automata have 2 states ) but det(rev(A)) is the same automata (obviously  det(rev(det(rev(A))) is also the same). Can you tell me what am I doing wrong ? Tnx.


texts: Dynamic Programming solution for finding shortest distance to travel between points

texts:
So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be traversed in any order, so let's do them in the order of the example set.

This leads us having to travel the distance $40+50+140 = 230$. A better option would have been to travel the order of $\{190, 100, 50\}$ which gives the distance $50+90+50 = 190$.

I want to try to set up a dynamic programming solution to this problem. I realize that at each step I have to consider the option of traveling to all available points (i.e discover all possible paths, and comparing them all to find the shortest one)

First things first I'd want to set up a recursive formula for the problem, but I can't seem to find out how... I feel like once I have a recursive formula the rest should work itself out.


texts: Can each VLIW sub-instruction execute any instruction?

texts: say that you have a 128 bit (32*4) VLIW word. Can each 32 bit sub-word contain any operation (ADD,CALL,BRANCH,...) if there are no hazards or can each sub-word only specify one functional unit (so if the BRANCH functional unit doesn't get used, that sub-word becomes a NOP)?


texts: Why do we need full-fledged workstations running massive OSes with massive software?

texts:
I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of change/bloat/costs to all the security and privacy issues -- one thing that really stikes me hard is:

Why do normal people need computers that are so powerful and complicated?

In decades past, we used simpler, less powerful computers to perform all kinds of tasks, without the issues we face today.

I'm not suggested we swap out current computers for thin clients.  I'm simply saying that current computers seem more powerful than necessary for vast majority of tasks that any person employed by an average company would logically need.

Even in the early 1990s, computers had advanced to the point where "all basic input/output tasks" were "solved". If I were running a company, I would create a minimal computer terminal which runs a minimal OS, and which just boots up and displays a "browser-like" interface that talks over HTTPS to my "mainframe".  I'd use a simple username/password system, with no password resets or two-factor auth, and once logged in, the employee would see only the sections that are relevant for them, coded by me.  For example, a secretary would see a basic form where she can input appointments, list current ones, etc. A different kind of employee, whose job is just to deal with customer support, would only see a minimal list of current support tickets and only have the ability to respond to these in a manner which cannot be misunderstood or abused.  I'd log every action so that I can later look up exactly who messed up or went rogue.

I notice that modern systems don't seem to work that way.  Instead, we have full-fledged PCs with expensive, bloated, and insecure Microsoft or Linux software.  We spend enormous amounts of time, effort, and money to educate employees on how to use it, maintain it, and deal with all the problems that inevitably arise from exposing the general public to such complicated systems.

Why is this?  Why is the only choice between a complex Windows system, a fragile Linux, or some kind of ChromeOS thin client that exposes my data to Google?  Why don't we have a privacy-respecting, minimal thin client OS that can't do anything but display basic HTML, basic CSS and connect over HTTPS, has no system storage or ability to change it, and is just something you hook up to a standard display and network cable and mouse and keyboard.

I realize one still needs to administer the server/mainframe, but presumably this could be done by skilled professionals, rather than the general public.

Can you help me understand why computing works this way today?


texts: (DROP) Data Reduction Algorithm - How it works?

texts:
I am studing a PHD framework which the propose is to reduce the dataset with the most representative samples for training a classifier. Maybe I am loosing something, but I could not undestand a specific part.

Basic this is the algoritm 1 proposed:

Question 1: line 7 says it will union 'edge (s,t)'. What it means? It means that Z'2 (output) will be a set of edges with s and t from different cluster-id's?

And I am asking it because the second algorithm in thesis is the following:

I am not sure if I understood how it L list is generated because some edgs did not make sense by the figure below:

Question 2 Why 6 and 7 has the same element (triangles)? It not should be different, once the edges (from algorithm 1) are from different cluster-ids?

This is the link for thesis: http://repositorio.unicamp.br/handle/REPOSIP/275528?locale=en (page 21-22)


texts: Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

texts:
(Please note, this is not a duplicate to Shortest path with exactly $k$ edges  OR  Shortest path with a fixed number of edges. What I want is a better algorithm)

The problem under consideration is to find single-source-shortest-path of at most $k$-edges (simple paths only). What we have is very special case: a Directed Acyclic Graph (DAG) $~G(V,E)~$ with positive edge weights.

  A preliminary solution to the problem is to run Bellman-Ford to $k$-iterations with parallel relaxation on all edges.

Bellman-Ford solution for finding usual shortest-paths, is generally known to be worse in complexity for graphs with positive edge weights. But it is the only algorithm, which possesses the very special property of identifying all $k$-edge optimal paths after $k$-iterations, provided we relax the edges parallelly. This eventually finds all shortest simple paths after at most $|V|-1$ iterations.

So simply by stopping the Bellman-Ford algorithm after $k$ iterations, we can find the desired shortest-path of at most $k$-edges from the given source. Also note that, Bellman-Ford algorithm is a classic instance of Dynamic Programming(DP) and the truncated version proposed above is a DP as well.

It seems dynamic-programming/Bellman-Ford algorithm (truncated to k-iterations & parallel relaxing of edges) will solve this problem with $O(k|E|)$ complexity. But can we do better at least on a graph with non-negative weights? At least, for a Directed Acyclic Graph(DAG) with non-negative weights!

I think it is a legitimate question to ask for a better algorithm, given that we have a much better alternative for usual shortest-path algorithms on graphs with positive weights, namely the Dijkstra's algorithm. Interesting question here is this: Does it extend to finding $k$-edge optimal paths?  This is definitely not immediate, since unlike Bellman-Ford, Dijkstra's doesn't have this property of $k$-edge optimality at $any$ iteration.

(Worse thing is that even the constant-factor saving modifications to Bellman-Ford, proposed by Yen, are no more useful for truncated Bellman-Ford.
I have a strong hope to have something better!)


texts: How do I use the Myhill-Nerode theorem to show that a language is not regular?

texts:
My language is the repetition of 0 to a length that's a power of 2:

$L = \{ 0^k \mid k=2^n, n \geq 1 \}$

I want to know how to use the Myhill-Nerode theorem to show that this language is not regular.

This is my first attempt at doing this although I am confident that I am wrong:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.


texts: Optimal strategy in repeated cake-cutting

texts:
Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob's preferences, but she assumes that they come from a uniform distribution.

What is the strategy that maximizes Alice's expected total value?

Here is my solution so far.

Let's assume that the cake is the interval $[0,1]$. Alice cuts the cake by choosing some  $x\in [0,1]$. Let $h\in[0,1]$ be a point such that Bob is indifferent between the cake to the left of $h$ and the cake to the right of $h$. Let $V(x)$ be Alice's valuation of the interval $[0,x]$; it is a continuous and increasing function of $x$. Then:

If $h> x$, then Bob picks $[x,1]$ and Alice gets $[0,x]$ and gains $V(x)$.
If $h< x$, then Bob picks $[0,x]$ and Alice gets $[x,1]$ and gains $V(1)-V(x)$.
If $h=x$ then, let's say Bob picks a piece at random  so Alice gains on average $V(1)/2$.

If Alice knows $h$, then she has a simple optimal strategy:

If $V(h) > V(1)-V(h)$, then select $x^* = h-\epsilon$, for some $\epsilon>0$, and gain $\approx V(h)$.
Otherwise, select $x^* = h+\epsilon$, for some $\epsilon>0$, and gain $\approx V(1)-V(h)$.

Initially, Alice does not know $h$, so she assumes it is distributed uniformly in $[0,1]$. If Alice cuts at $x$ and Bob chooses left, this tells Alice that $h\in[0,x]$; if Bob chooses right, this tells Alice that $h\in[x,1]$. So, using binary search, Alice can estimate $h$ to an arbitrary precision. This seems to be an optimal strategy when $n\to\infty$: spend a lot of rounds initially for getting an accurate estimate of $h$, and use this estimate from then on to get the optimal possible value.

I am stuck at the case where $n$ is finite and small. The question bogs me even for $n=2$: what is the optimal first cut?


texts: Calculating CPU throughput on a single cycle vs multicycle datapath

texts: When calculating the throughput of a CPU, how does it differ when it is implemented with a single cycle datapath versus a multicycle datapath? If for example the CPU is running 1 GHz freq, then obviously it would have 1,000,000,000 clock cycles per second...and in a single cycle, it takes 1 CPI. So what would be the throughput? And how would it be different in the multicycle datapath where clock cycles differ between instructions?


texts:
What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it?

(beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to NPI?, if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$)

Is there an example of a decision question which is known to be $co-NP /\ NP$ or $NP /\ co-NP$? (and great consequences of such a thing existing in the even that P not the same as NP)
Do we know anything about how BPP, RP, co-RP or ZPP intersect NP or co-NP? (apart from the fact that $(P \subset (ZPP = RP \cap co-RP)) \subset BPP$ and hence whatever intersection with NP and co-NP follows just from this)


texts:
We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two SEPARATE cliques $K_1$ and $K_2$ of size $\dfrac{N}{2}$ (where $|V| = N$). My speculation is that $\mathcal{G}_{2K}$ is in NP and the corresponding existential problem is NP-complete, but I can't find any reduction form any well-known NP-complete problem.

Hence the question is: Is $\mathcal{G}_{2K}$ in P or it's NP-complete?

The question I asked is equivalent to these two questions:
1. Given graph $G=(V,E)$ and integer $k$, can we partition the vertices into two disjoint cliques of size $k$ and $|V|-k$.
2. Given graph $G=(V,E)$ can we partition the vertices into two independent sets of size $k$ and $|V|-k$?


texts: Why do we need increase_key procedure in max priority queue?

texts:
Since if I want to increase the priority of a specific node, how do I find the node without linear searching it.

I need to pass the index to this function, which is in a way a bottleneck. So the question is, how can I avoid it? Or exactly this data structure doesn't provide any solution for this problem?

Link: web.cse.ohio-state.edu/~lai.1/2331/4.heapsort.pdf | Chapter 5: Priority Queues


texts: Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

texts:
This question is about section 2.3 of Wilf's ``Algorithms and Complexity''

https://www.math.upenn.edu/~wilf/AlgoComp.pdf

in which he analyses the complexity of a recursive computation of the chromatic polynomial of a graph, based on the relation
\begin{equation}
\label{eq: recurrence}
P(K;G)=P(K;G-\{e\})-P(K;G/\{e\}) \qquad (1).
\end{equation}
Here $P(K;G)$ is the number of ``proper colourings'' of $G$ with (as I understand it) at most $K$ colours (that is, colourings of the vertices using at most $K$ colours, such that no adjacent pair of vertices shares the same colour). The graph $G-\{e\}$ is the result of deleting edge $e$ from graph $G$, and the graph $G/\{e\}$ is the result of contracting edge $e$ in graph $G$. It turns out that $P(K;G)$ is indeed a polynomial in $K$, of degree equal to the number of vertices of $G$.

By defining $F(V,E)$ as the maximum cost (over all such graphs) of applying to a graph $G$ with at most $V$ vertices and at most $E$ edges, this recursive algorithm to compute $P(K;G)$, Wilf deduces from (1) that
\begin{equation}
\label{eq: F recurrence}
F(V,E) \leq F(V,E-1)+cE+F(V-1,E-1) \qquad (2),
\end{equation}
with $F(V,0)=0$. Here the term $cE$ accounts for the effort of contracting the edge $e$, which requires us to modify the descriptions of any edges adjacent to the vertex that gets deleted.

Wilf seeks an upper bound of the form $F(V,E)\leq f(E)c$, and notes that the unique $f$ satisfying $f(E)=2f(E-1)+E$ and $f(0)=0$ will provide such a bound. He computes the exact solution $f$ of this last recurrence relation, which solution he approximates by $f(E)\sim2^{E+1}$.

He then derives another upper bound on $F$, by defining $\gamma(G)=|V(G)|+|E(G)|$, the sum of the number of vertices and the number of edges of $G$, and observing that $\gamma(G-\{e\})=\gamma(G)-1$ and $\gamma(G/\{e\})\leq \gamma(G)-2$. Then, letting $h(\gamma)$ denote the maximum amount of work done by the algorithm on any graph $G$ for which $\gamma(G)\leq \gamma$, Wilf claims that
\begin{equation}
\label{eq: h recurrence}
h(\gamma)\leq h(\gamma-1)+h(\gamma-2) \qquad (3)
\end{equation}
for $\gamma \geq 2$.
With $h(0)=h(1)=1$, the solution of this last recurrent inequality is that $h(\gamma) \leq F_{\gamma}$, the Fibonacci number.

Finally, combining the two bounds, he obtains that the time complexity of the algorithm is
\begin{equation}
O \left ( \min(2^{|E(G)|}, \phi^{|V(G)|+|E(G)|}) \right ),
\end{equation}
where $\phi$ is the golden ratio. Provided the ratio of $|E(G)|$ to $|V(G)|$ is large enough, the second bound is sharper than the first.

My question is, how in (3) was Wilf able to omit a term like $cE$ from (2) ?


texts: How to do compare-and-increment different locations with in memory MVCC?

texts:
I'm reading the paper An Empirical Evaluation of
In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) says:

  To perform a read operation on a tuple A, the DBMS searches for a
  visible version by comparing a transaction’s T-id with the tuples’
  begin-ts field.  If it finds a valid version, then the DBMS
  increments that tuple’s read-cnt field if its txn-id field is
  equal to zero (meaning that no other transaction holds the write lock)

Here is the image in Figure 2c:

The confusion point is about how it actually does this operation atomically: Read location A (txn-id), if its value is equal to 0 then increment location B (read-cnt)

Atomic operation in C/C++ does compare-and-swap only for a single memory location, however, in this case we are dealing with two memory locations. Is there any other CPU intrinsic for this operation, or another trick is employed?


texts: Does there exist a conservative algorithm to determine if a certain property is satisfied at a certain part of a program?

texts:
...

x = a / b;

For the above code, for example, is there a way to determine whether b could be zero at the time of division, even if the answer isn't 100% decisive? Can this algorithm generalize to check any property at a point of a program?


texts: Help understanding a problem with inclusion/exclusion

texts:
I am trying to understand how to use inclusion/exclusion in algorithm.

I think I understand the basic example of what the inclusion/exclusion principle is: the principle is in general illustrated using a venn diagram and the objective is counting the elements of the sets. The principle says that ou first over-count the intersections, then exclude the intersections, then include the intersections of the intersections...

I can see the logic in this formula, and what it achieves.

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

My object is to understand how to use IE as to resolve other problems than the above. I know it is possible to use it to solve problems such as: #Ordered Set Partitions, Graph Colouring, #Bipartite Perfect Matchings, Counting Hamiltonian Cycles, etc.. as I find it in literature. E.g.: http://arxiv.org/pdf/1105.2942v2.pdf

But when I read the paper above, I can understand only problem 6 which is related to the same sets counting problem as above. Somehow, I cannot seem to grasp the concept of how IE is used to solve any other problem than the above.

Would someone please be able to explain the IE principle using an example different than the set counting? Thanks!


texts:
I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where:

Set $A$ has an incomplete set of preferences (not all of $B$ is included)
Set $B$ has no preferences whatsoever.

I want to find an $A$-optimal matching (e.g, for any $(a_1 \rightarrow b_1), (a_2 \rightarrow b_2)$, then either $b_2$ is lower than $b_1$ or does not appear in $a_1$'s preferences, and likewise for $a_2$) between $A$ and $B$, respecting $A$'s preference lists, and where ties between members of $A$ are broken randomly. I've been trying to apply the Gale Shapely algorithm to this problem, with random preferences for B, but it appears to have degenerate cases where the above criterion is violated.

A pre-rolled solution to this problem seems to be somewhat elusive, potentially because it's so obvious. There's a related SO question, Stable marriage problem with only one side having preferences, which states the no-preference issue, but the answers only cover how to check for a perfect matching, which does not necessarily guarantee the optimality of the result with respect to $A$'s preferences. Is there an algorithm that produces an $A$-optimal matching?


texts: Iterative Depth First Search for cycle detection on directed graphs

texts:
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.

How should I approach this?


texts: Randomized meldable heap - meld is oversimplified?

texts:
On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps:

function Meld(Node Q1, Node Q2)
 if Q1 is nil => return Q2
 if Q2 is nil => return Q1
 if Q1 > Q2 => swap Q1 and Q2
 if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)
 else Q1.right = Meld(Q1.right, Q2)
 return Q1

But isn't this oversimplified? We choose recursively to meld with either the left or the right child. But this isn't always necessary, if Q1 has no or one child you can immediately stop the melding process by putting Q2 in the missing spot. I propose this instead:

function Meld(Node Q1, Node Q2)
 if Q1 is nil => return Q2
 if Q2 is nil => return Q1
 if Q1 > Q2 => swap Q1 and Q2
 if Q1.left is nil => Q1.left = Q2
 else if Q1.right is nil => Q1.right = Q2
 else if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)
 else Q1.right = Meld(Q1.right, Q2)
 return Q1

I've found experimentally that this reduces the average height by roughly $0.3$ and the maximum height of the tree by roughly $1.3$, both gains seem fairly consistent for various $n$ (I'm seeing the same gains for $n = 10, 10^3, 10^6$) when inserting uniformly random elements.

Two questions:

Am I missing anything? Isn't this just strictly better?
The average and maximum height gains are surprisingly consistently in the neighbourhood of $0.3$ and $1.3$ respectively. Can these values be rigorously justified?


texts: What are the underlying mechanisms allowing us to unsend an email?

texts:
I am currently studying Computer Networking, and I was reading about the different types of Application Layer Protocols. In the book I am reading (Computer Networking: A Top-down Approach) it is mentioned that: "Once the client
sends a message into its socket interface, the message is out of the client’s hands and is
“in the hands” of TCP."

For the sake of example, I thought of the option we have of cancelling the emission of an email?
Is this functionality simply implemented via a time-window of seconds before emission or is their an actual procedure I do not know of ?

Do please correct my assumptions as I am afraid I might be off topic on several points

Thank you in advance.


texts: In Big-O notation, what does it mean for T(n) to be upper bounded by something

texts:
I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? from references, but I still do not understand (even graphically), what does it mean when we say:

  T(n) = O(f(n)) if and only if there are constants c and g such that:
  T(n) <= c*f(n), where n>=g

Specifically, we say that T(n) is upper bounded by c*f(n). What does that actually mean and why does it matter? Does it have to do with eliminating constant factors and low-ordered terms?

Sorry if question is kind of confusing, and thanks for the help!


texts: What are the minimum requirements for a language to be considered Turing Complete?

texts:
Possible Duplicate:
  Are there minimum criteria for a programming language being Turing complete?

I overheard a conversation on the topic and the conclusion that one gent came to was that in order to be Turing complete, given one has infinite storage, all one needs is a conditional control structure and a jump instruction.

Is this true?

If it is true, and Turing completeness requires that the language that is Turing complete be able to simulate every instruction available in another Turing complete language, how do those two simple elements achieve that?


texts: How are alphabetic characters programmed into a computer?

texts:
I'm no cs student, I'm a programmer. I have a couple of questions and a few assumptions that I will make here (correct me if I'm wrong please).

From my understanding is that all the sequences of 1 and 0's that computers execute are just representations of actual data or instructions that tell other hardware on a system what to do like telling a graphic card to change a pixels color on the monitor.

01100001 being the representation of the letter "a" and that this sequence of bits has been chosen by the fathers of computing/ascii or what have you to represent that letter, it could just as well have been some other sequence right?

All computer systems have agreed that those bits mean the letter "a" for all of the computers around the globe to be interoperable, if there were no standards in place for this the internet would be a mess.

What I want to know is: where is the information stored on a computer that tells it that these sequences of bits here mean/represent the character "a"? Is it in the OS or directly on the motherboard or am I just completely wrong?


texts: Can I use the Quine-McCluskey to simplify a CNF which is not a product of maxterms?

texts:
As I understand it the Quine-McCluskey method allows you to start with a set of maxterms (or minterms), and combine them pairwise in a systematic way into a smaller set of clauses with a smaller set of variables in some (hopefully most) of the clauses.   I understand how to apply the method, given a set of maxterms.

My question is: if I start not with a set of maxterms, but with an arbitrary set of clauses in a CNF (analogously in a DNF), can I apply the same approach to "combine" compatible terms?  Or must I first expand the CNF into product of maxterms?   The latter would make the algorithm exponential in worst case, and the former would seem to be quadratic in best case.

When I look at the QM method, it is not immediately obvious to me which part of the algorithm really depend on the initial set of clauses being maxterms.


texts:
I tried to use machine learnign in matlab using bagoffeatures to captures features and teach the code betwee two types of plots. However, bagofFeatures could not detect ant features.
this is my plot:

How does bagofFeatures work? and would work on my plot if I changed the color og point depending on their high?


texts: Given a set of points, find all collinear subsets

texts:
General problem

Given a space $S$ which is $N$-dimensional, bounded, and quantized
Given a set $P$ of unique points
Find the set of collinear subsets of $P$, each containing at least 3 points
One point can exist in multiple subsets

Specific problem

I am creating a 4D, 5 by 5 by 5 by 5 tic tac toe game. Each dimension is bounded by $\left(0,4\right)$ and quantized by $1$. I have a set of points within that space. Each point is associated with a player (the number of players is not bounded), so that could be treated as an additional bounded, quantized dimension.

I need to find any and all combinations of 5 points (played by the same player) that are collinear.

Question

What is an efficient way to do this?


texts: Was there an attempt to make reusable regular expressions?

texts:
In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating point number, a zip code or a telephone number. (Zip code may become particularly unwieldy).

Suppose you could define a grammar for parsing floating point numbers, and then give it an alias, once defined you would be able to reuse this in regular expressions you use afterwards. In some fictional language this could look like this:

float := /[+-]?(\d+|\d*\.d+)(e\d+)?/
sum := /(?R<float>)+(?R<float>)/

This, in principle, wouldn't change anything in terms of expressive power (unless you allow self-reference), but it seems like it could make the practical implementations of regular expressions more concise?

So, my question is: has any language implemented anything like that? Or, and if not, then what would be the reason for not doing so?


texts: Choose N pairs of (job, time slot) with a constraint on the number of different jobs

texts:
I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of other predefined constraints. We refer to a particular pair of (job, time slot) as a "shift".

I'm not optimizing the entire workforce at once but instead I assign one person at a time.* Here's an overview of how I modeled the sub-problem:

Enumerate the set $S$ of all possible shifts ($|S| = |J|\times|T| = 90$ in my case)
Use an objective function related to the number of people already assigned to each shift (and the need for that shift)
Find solution $x \in \{0,1\}^{|S|}$ that associates to each element of $S$ a value in $\{0, 1\}$

The constraints are the following:

Each person can be assigned up to N shifts (depending on their preference)
Up to 2 shifts during the same day
No consecutive shifts except when the job remains the same
Each person can do only up to two different jobs during the entire event

I managed to encode all the constraints as a linear program except the last one. Any idea on how that could be done ? If that is not possible at all (which I suspect), what tool can I use to solve this problem ?

* I know that is sub-optimal, but finding a better algorithm will probably be the subject of another question ;)


texts: Proving a language is not regular using the Myhill-Nerode Theorem

texts:
I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.

$\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\}$
$\{w \in\{0,1\}^{\ast}\mid w\text{ is not a palindrome}\}$

For the first question, I did the following:

I considered the set $\{0^n1^m \mid{} m,n\ge 0\}$. To prove that this set is pairwise distinguishable by the original language, I said that for all $m$ and $n$, $0^n1^m$ is distinguishable from all previous $0^i1^m,\:0\:\le i\le n-1$ because there exists a $z=0^n$ such that $0^n1^mz$ is an element of the original language but $0^i1^mz,\:0\le i\le n-1$ is not an element of the original language.

I first want to ask whether this was indeed the correct way to do the proof?

I am also quite confused for the second question as I can't even seem to find a string that is part of the language but is a palindrome. All the strings other than the empty string in that language are not palindromes. So I am quite confused on how to approach the problem.

Any help would be highly appreciated!


texts:
I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.

However one thing still bugs me - I can't yet work out how this simple seeming algorithm can "know" which move to make first - whether to the destination peg or the spare peg.

I can see it depends on whether there is an odd or even number of discs, and I understand how the algorithm works, thanks to this great article: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

It's just that first move that remains a mystery to me. Any clarification musch appreciated.

def hanoi(n, from_peg, to_peg, spare_peg):
    if n == 1:
        print("Moving disc from " + from_peg + " to " + to_peg)
        return
    hanoi(n-1, from_peg, spare_peg, to_peg)
    print("Moving disc from " + from_peg + " to " + to_peg)
    hanoi(n-1, spare_peg, to_peg, from_peg),

print (hanoi(4, 'A', 'C', 'B'))


texts:
As part of a project i'm doing I have been looking for a way to find common values between 2 arrays including duplicates.
For example;
A = [2, 2, 3, 5]
B = [2, 2, 5]
would return the array;
Common values = [2, 2, 5]
I have attempted using sets, and the intersection function, but neither gave duplicates
Any help appreciated


texts: Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?

texts:
We have a set of $n$ products, each $i$th product can be kept in a
  temperature between $c_i$ and $h_i$.

  We have to buy fewest number of fridges for these products. The
  fridges can only have a fixed temperature.

For me I think of this problem as intervals of product temperatures that are placed on the axis.

My idea to solve it is to see which product's temperature range overlaps with most other products temperature ranges, then we can place these products in one fridge.

But the algorithm for this would be inefficient..

What's a simple greedy solution for this? any ideas?


texts: Implementing Dynamic Programming Solutions

texts: I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion.  My confusion comes from implementation.  Here is a specific question.  Every question I look at builds its grid differently, for example, 0,1 knapsack you go back down the row and up one.  For coin changing its just back down the row.  For Fibonacci and stair steps its the sum of the last two.      If I am tasked with a Dynamic Programming problem is there any kind of base approach I can take to building out my grid?


texts: Competitive ratio of the ski rental problem

texts:
Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ratio for a deterministic (and non- deterministic) algorithms:

Let's say that renting costs 1 dollar a day and buying costs 10 dollars.

Buy the skis on the day before, this means that you can decide to buy the skis and never use them even once: So if you decide on an algorithm that rents for 9 days and buys the skis on the 9th day, skiing for exactly 9 days (which is the worst-case input for that algorithm) would cost (9 + 10)/9 = 2.111...
Buying the skis on the current day: So you wake up on the morning of day N, you know already you can ski - and then decide if you want to buy  or rent. This changes the competitive ratio of the algorithm in the worst case (for the input: skiing for exactly 9 days) to be: (9+10) / 10 = 1.9

The second method was presented in the Wikipedia article as well as in Algorithm Design and Application by Michael T. Goodrich and Roberto Tamassia. However -it is never written explicitly when does the buying of the skis occur.

My question here is - Are these 2 problems completely different from each other? and the first one can never have a competitive ratio of 2 or less ?


texts: Is there a model of computation, that tries to be realistic?

texts:
For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory.  Secondly Turing machines are not really convenient IMHO for proving things about everyday algorithms on an everyday computer.

I want a model that makes computations in a ring, namely $\Bbb{Z}_p\times \dots \times \Bbb{Z}_p = (\Bbb{Z}_p)^k$, where $p$ is prime (for a good reason... later on that).  Since that's what bytes on a computer look like they look like values in $\Bbb{Z}_8$ and even some of the instructions on those bytes on modern computers cause wrap around that looks like that of $\Bbb{Z}_8$.  It's obvious to me that any computation on my home PC can be done with computations in said ring.  But of course I'd have to prove that formally if I wrote a paper.  I can already write conditional assignments of a memory slot (element of $\Bbb{Z}_p$), as the value of a polynomial in $\Bbb{Z}_p[x_1, \dots, x_k]$.

It's hard to find literature on this, but to me it seems so obvious that this is a nice approach and I'm shocked that no one's considered this yet.  Or have they?  Links please...


texts: Return destinations for an expression-oriented programming language

texts:
I am designing a programming language and I want to give everything the ability to return a value. For example, if I use a block as a right-hand side value, I can assign it to a lvalue:

sum := {
    if (a < 0) { a := -a; }
    if (b < 0) { b := -b; }
    return a + b;
};

Also, if and while statements could return a value, and there is no need for something like a ternary operator then.

After a bit of research, I have found that Rust is capable of doing this. And this is great for language design, because it significantly reduces the number of language constructs needed. You don't really need a do-while loop, as that's just a while loop with a braced condition:

do {
    foo();
} while (a > 0);

Is equivalent to:

while {
    foo();
    return a > 0;
}{}

Also, with ignored variable bindings, you can create continue and break statements for loops:

// Break
_ := while (a > 0) {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};
// Continue
while (a > 0) { _ := {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};}

I like the idea of having less language constructs, because the language is expressive enough to do this without labeling and goto statements.

But as I was thinking about this, two things popped into my head:

Are these just very abstract lambda expressions?
How could the 'return destination' be labeled so we can return from a very nested expression even right out to the function? I think I would probably need some extra notation for that.


texts: Placing items into compatible bucket types to find an optimal total value

texts:
Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a bucket type iff the item is able to be inserted into a bucket of that type. The goal is to insert the items into the buckets such that the total value of the inserted items is highest.

For example:

Items:
compatible with       | value
A,B,C                 | 17.641
A,B,C                 | 14.821
A,B                   | 14.274
A,B                   | 13.755
A,B                   | 12.240
A,B                   | 12.240
B,C                   | 11.960
A,B                   | 10.270
A,B,C                 | 9.958
A,B,C                 | 8.552

Buckets:
bucket type           | capacity
A                     | 2
B                     | 3
C                     | 4

Solution:
bucket                | values
A                     | 17.641, 12.240
B                     | 14.274, 13.755, 12.240
C                     | 11.960, 9.958, 8.552, 14.821

Is this problem a special case of any existing problems? I am finding it hard to envision an algorithm to solve it, but I feel that a good solution would require passing over the item list multiple times and maintaining a queue of best matches for each bucket type.

What would be the wost-case complexity of the resulting algorithm? Could a situation with 5 bucket types and 30 items explode in computational expense?


texts:
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must recur to the blossom algorithm.
The explanations that I found (1. here, 2. and here) are based on the fact that the direction that I choose to start exploring an odd loop in the Depth First Search (DFS) could make me miss an augmented path.
But it seems to me that this issue can be solved by considering the same vertex distinct during the DFS if I am entering it through a matched edge or an unmatched one, why isn't this enough?
To be more precise, what I mean is that during a DFS, you still avoid loops, so you stop if you enter a node that is already in the path between the root and the current node, but you still explore nodes that you have visited in previous paths if you are entering them from a different type of edge (matched or not matched).


texts: Why time complexity of union-find is $O(lgN)$ with only "Union by Rank"?

texts:
I'm studying time complexity of Union-Find data structure.

I saw time complexity of union and find function depends on some conditions.

without anything: $O(N)$
with Union by Rank: $O(\log N)$
with Path Compression: $O(\alpha(N))$ which is inverse Ackermann function.

I understood $O(N)$ because of skewed tree of disjoint set. But, I cannot understand $O(\log N)$. I looked on Wikipedia and Stack Overflow, but I couldn't find it. How can I prove second time complexity?


texts: Does topological sort exist for any complete directed acyclic graph?

texts: Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which the left node has edge into the right node. Maybe this is the question about existence of Hamiltonian path in every complete DAG?


texts: CFG notation meaning in making LL parse table

texts:
I have problem of interpreting Context-free grammar notation in making LL(1) parse table.

To make LL(1) parse table. Two rules are shown below:

If A -> α is a production choice, and there is a derivation α =>* aβ, where a is a token, then add A -> α to the table entry M[A,a].
if A -> α is a production choice and there are derivations α =>* ε and S\$ =>* βAaγ, where S is the start symbol and a is a token(or $), then add A -> α to the table entry M[A, a].

From the second theorem, I can't understand the meaning of S\$ =>* βAaγ.

I know the meaning of S =>* βAaγ, which means start symbol can be derived to βAaγ.

But what's the meaning of S\$ =>* βAaγ ? (The only difference is the existence of $)


texts: n mod 4 asymptotic analysis best case and worst case

texts:
if 0==(n mod 4) then
  do somthing ϴ(n^2)

else if 1==(n mod 4) then
  do somthing ϴ(n^3)

else if 2==(n mod 4) then
  do somthing ϴ(n^4)

else if 3==(n mod 4) then
  do somthing ϴ(n^5)

what is best case and worst case for this algorithm?


texts: On the complexity of Unique Coverage Problem restricted to geometrical settings

texts:
I come to you with a problem I have been struggling with for the past few weeks. I would like to classify (complexity) a special case of Unique Coverage. To set the mood on, I will start by introducing the Exact Set Cover and Unique Coverage problems. I will then go over the special cases I am interested in.

Set covering problems come in a wide variety of variants. The classical decision problem Exact Set Cover consists in, given a ground set $\mathcal{U}$ and a set of subsets $S\subset \mathcal{P}(\mathcal{U})$, deciding whether there exists $S'\subset S$ of cardinality such that every element of $\mathcal U$ is covered by at exactly one set in $S'$.  This problem has been extensively researched, and not suprisingly classified as NP-complete (NPC).

Unique Coverage is a natural optimization variant of the Exact Set Cover problem. In this problem, the input is the same as before $(\mathcal{U},S\subset \mathcal{P}(\mathcal{U}))$ but the goal is now to find $S'\subset S$ maximizing the number of elements from $\mathcal{U}$ which are covered exactly. Obviously, Unique Coverage is harder than Exact Set Cover since an instance of the latter is positive if and only if the former admits a solution covering $|\mathcal U|$ elements. Exact Set Cover being NPC, the decision variant of Unique Coverage is NPC as well.

Geometrical variants of the Unique Coverage problem have been studied as well. In a geometrical setting, the ground set $\mathcal U$ is assumed to be a set of points in a space, and the subsets of $\mathcal U$ are induced by geometrical objects (polyhedrons,  balls, whatever).

Above line ends the introduction on exact set cover and unique coverage. My questions follow

Erlebach and van Leeuwen [1] prove Unique Coverage to be NP-hard for unit disks in the plane. I am wondering whether the problem stays hard in the following even-more-special cases.

The unit disks are all centred in the same disk $D$ and the points to cover lie outside $D$.
The points to cover all lie in a connected area $Z$ such that two disks intersect at most once in $Z$.
The combination of the two cases above.

At first I was fairly confident the first two cases were hard. Then I found two articles.

Chan et al. [2] results on sets of pseudo-disks can be used to prove that the Exact Set Cover is polynomial in case (1).
Baysan et al. [3] show that the classical Set Cover problem in case (1) is polynomially solvable.

Their results kind of convinced me that the special cases I am considering are in fact easy to solve. Yet, I haven't managed to prove it and am running out of steam. Thus this post, to exchange on the subject (if you think of any paper vaguely related to the problem, or you have worked on similar settings...)

Thank you very much if you read this far.

MrTapir.

[1] T. Erlebach and E. J. van Leeuwenn. Approximating Geometric Coverage Problems. 2008

[2] T. Chan and E. Grant. Exact Algorithms and APX-Hardness Results For
Geometric Packing and Covering Problems. 2014

[3] A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model. 2008


texts: In what bases is the language $a^n$ regular?

texts:
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular
$$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$
I think it's regular only for bases which are a rational power of $a$, but I couldn't come up with any proof of that.
Is that correct? How can you prove it/find a counterexample?


texts: Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

texts:
I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ comparisons is optimal as we cannot do better than it, which means that we need to show that running time of algorithm which finds the minimum of a set of $n$ elements is $\Omega(n)$.
This is what the text says to justify the lower bound.

We can obtain a lower bound of $n - 1$ comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum.

Now I could make the thing out in my own way as:

What I have done is a top down comparison, but the authors by their words "Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum." seems they are pointing to some bottom up approach which unfortunately I cannot make out.
How,
"That every element except the winner must lose at least one match" $\implies$ "$n-1$ comparisons are necessary to determine the minimum".


texts:
I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across online are somewhat inaccurate and confusing.

Specifically, the concept of gap problems wasn't completely clear to me. It was presented to us that gap problems are a way to formulate decision problems from approximation problems. However, it seems to me that a gap problem isn't precisely a decision problem (or, let's say, a language), but rather a set of decision problems/languages that satisfy two common conditions.

For example, I would think that gap-$IndependentSet[a,b]$ could be defined as the set of all languages $L$ such that:

If $G=(V,E)$ has an independent set of size $>b$ than necessarily $G\in L$
If $G=(V,E)$ doesn't have an independent set of size $>a$ than necessarily $G\notin L$

If such a definition for a gap problem is valid, then I think two more definitions need clarification:

A gap-preserving-reduction isn't in fact a proper Karp reduction, because it doesn't map a single language to another language. Rather, it maps certain "good inputs" to other "good inputs" and "bad inputs" to other "bad inputs", without having any requirements about the rest of the inputs.
A gap problem cannot be an element of a complexity class (such as $NP$), but rather a subset of the class. In that case, saying that a certain gap problem is $NP$-complete would actually mean that all languages in the problem are $NP$-complete

Is this a valid way to think about the subject? Am I just confusing myself? Should I stick to the basic intuition and not try to define approximation related concepts in these terms?


texts: Calculating worklist with live variable analysis

texts:
I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes.
The algorithm I am following to calculate the worklist for live variables is as below

Can anybody explain to me for my example given below, what would be my initial worklist and how the worklist algorithm would be applied to this?
x = 1   /*block 1*/
y = 23  /*block 2*/
x = 100 /*block 3*/
print x+y /*block 4*/

for simple understanding I have taken this code, I have calculated below equations for In[n] block only as I am not able to understand how this algorithm works for out[n].
in[4] = use[4] U (out[4] - def[4])
       = {x, y} U { }
in[3] = use[3] U (out[3] - def[3])
       = { } U { y }
in[2] = use[2] U (out[2] - def[2])
       = { } U { y } - { y }
in[1] = use[1] U (out[1] - def[1])
       = { } U {  }

Now, even though I calculated these equations I am not sure how to use it in worklist? And at end how to does the worklist gets empty?(Algorithms - Nielson book slide 15)


texts:
By reduction I mean the following:

  Problem X linear reduces to problem Y if X can be solved with:
  a) Linear number of standard computational steps.
  b) Constant calls to subroutine for Y.

If a problem X reduces to a problem Y, is the opposite reduction also possible? Say

X = Given an array tell if all elements are distinct
Y = Sort an array using comparison sort

Now, X reduces to Y in linear time i.e. if I can solve Y, I can solve X in linear time. Is the reverse always true? Can I solve Y, given I can solve X? If so, how?


texts: Why do the following algorithms for Quadratic Primes perform so differently?

texts:
I'm trying to solve for https://projecteuler.net/problem=27, and I have to optimize one part of the implementation from slow() to fast(). Why do they perform so differently? I'm guessing branch predictions, but I don't quite understand how they are different to the optimizer. The code is in javascript.
function primes(n) {
    const P = new Array(n).fill(1)
    P[0] = 0
    P[1] = 0
    for (let i = 2; i <= n; i++) {
        for (let j = 2*i; j <= n; j += i) {
            P[j] = 0
        }
    }
    return P
}
const P = primes(1_000_000)

function slow(a, b) {
    for (let i = 0; ; i++) {
        if (P[i*i+a*i+b] == 0) {
            return i - 1 // the reason why it's slow is probably because of the fork-away of return inside the loop.
        }
    }
}

function fast(a, b) {
    let i
    for (i = 0; P[i*i+a*i+b] == 1; i++) {}
    return i // so this optimization works as long as we only need 1 index value
}

function qp(n, algo = npc) {
    let max = 0
    let maxa, maxb
    for (let a = -n; a <= n; a++) {
        for (let b = -n; b <= n; b++) {
            // here's the trick. CPU can optimize if it can SOMEHOW predict the branch pattern, which probably goes all the way false.
            // if we write npa(), we are nesting another loop-branch within, and then CPU refuses to take a guess on the outer loop.
            const i = algo(a, b)
            if (i > max) {
                max = i
                maxa = a
                maxb = b
            }
        }
    }
    return [maxa, maxb]
}

// pretty much that same:
fast(-61, 971)
slow(-61, 971)

// huge difference:
qp(200, fast)
qp(200, slow)

Here are some benchmarks in chromium:
     |   n |  time
slow | 100 |   165
     | 200 |  1090
     | 400 | 10176
fast | 100 |    12
     | 200 |    27
     | 400 |    99


texts: Termination of Z combinator with call-by-value

texts:
I am trying to build my own λ-calculus interpreter. So far it supports both call-by-value and normal order.

I now want to try recursion via fixed points. The $Y$ combinator works with normal order, tested with the faculty function $$\text{fac} = \lambda f.\lambda n.\text{iszero}\,n\,1 (\text{mul}\,n\, (f(\text{pred}\,n)))\text{,}$$
and for example my interpreter yields $Y\,\text{fac}\,3 \stackrel{\text{NO}}{\rightarrow} 6$. (I'll write behaviourally equivalent Church numerals as decimal numbers)

As far as I know for call-by-value I will need the $Z$ combinator instead:

$$Z = \lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\text{,}$$

as $Y$ would cause an immediate infinite regression.

My problem is, I fail to understand how $Z\,\text{fac}\,0$ is supposed to terminate. It also does not terminate in my interpreter, but I want to understand it manually first.

After some steps call-by-value should arrive at:
$$Z\,\text{fac}\,0
\\=\lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\,\text{fac}\,0
\\\stackrel{\text{CBV}}{\rightarrow}(\lambda x. \text{fac} (\lambda y. x x y)) (\lambda x. \text{fac} (\lambda y. x x y))\, 0
\\\stackrel{\text{CBV}}{\rightarrow}\text{fac} (\lambda y. (\lambda x. \text{fac} (\lambda y'. x x y')) (\lambda x. \text{fac} (\lambda y. x x y')) y) \, 0
\\\stackrel{\text{CBV}}
{\rightarrow}\text{fac}\,F\,0\stackrel{\text{CBV}}{\rightarrow}\text{iszero}\,0\,1\,a\text{,}$$

where the omitted term

$$a=\text{mul}\,0\, (F\,(\text{pred}\,0))$$ contains

$$F=\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,y$$ again.

Now, $\text{iszero}\,0\stackrel{\text{CBV}}{\rightarrow}\lambda t.\lambda f.t$, s.t.

$$\text{iszero}\,0\,1\,a\stackrel{\text{CBV}}{\rightarrow}(\lambda t.\lambda f.t)\,1\,a\stackrel{\text{CBV}}{\rightarrow} (\lambda f. 1)\,a\text{.}$$

If our language had a branching construct that would ignore the $a$ branch we'd be done, but with call-by-value we have to evaluate $a$ to a value, i.e. an abstraction.

$a=\text{mul}\,0\, (F\,(\text{pred}\,0))$ and $\text{mul}\,0$ will be another abstraction so next I have to reduce $F\,(\text{pred}\,0)$.

$\text{pred}\,0\stackrel{\text{CBV}}{\rightarrow}0$, so we reduce $F\,0$.

$$F\,0 = (\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,y)\,0 \stackrel{\text{CBV}}{\rightarrow} (\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,0\stackrel{\text{CBV}}{\rightarrow}\text{fac}\,F\,0$$

And now we're back at square one. Am I doing something wrong?


texts:
I have been struggling in the search for a modern fast "consequence finder". That is, an implementation based on state-of-the-art theory; things of the ilk of Z3, Prover9, OTTER, etc.

To describe what I mean by "consequence finding" (and please correct my term usage if it's inappropriate):

Given a satisfiable and consistent set of clauses C, where a clause is a finite disjuction of literals, wherever there is some atom $p$ in some clause $\phi = p \lor \alpha$ and $\lnot p$ in some clause $\psi = \lnot p \lor \beta$, we add the new clause $\alpha \lor \beta$ to C (provided it cannot already be found in C). This is what I understand as the process of performing Resolution.

Assuming we generate all possible new clauses from C, contintually adding generated clauses, and trying to find new clauses again, we will have C'.

As a very small example, on the input:

$(\lnot p \lor q) \land (p \lor r)$

$(\lnot p \lor q) \land (p \lor r) \land (q \lor r)$ would be the output.

If we now remove subsumed clauses from C', i.e. clauses which are of the form $\alpha \lor \beta$ where there exists some other clause of the form $\alpha$, then we have a set of clauses C''.

I want C''. I was under the impression that there would be tools like those mentioned to generate this set since C'' is essentially what would remain when having performed vanilla resolution on a satisfiable set of clauses.


texts: Decide if binary encoded number is divisible by 3

texts:
Let's consider the language over $\{0,1\}$ containing such words $w$ that:
$$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + ..  + m_n \mod 3 = 0$$

($m_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class.

The first problem is:  How to decide whether $m_i$ is divisible by $3$?

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is:
$v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\
2^{2k} \mod 3 = 2$$

Please hint me.


texts: How a computer ensures that a location in RAM is empty

texts: When we declare a variable, how does it get stored in a memory? How does the compiler know from within millions of memory locations which ones are currently not in use or are empty so that it can store the variable there? If it traverses each memory location the whole memory address space and checks on each location whether it is used by some other process or not, it will take like forever until it can allocate memory for a single variable.


texts:
OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges.

How can I show OddPath is NL?
I think about it for a long time, the main problem is that I don't know how to get length of the shortest path in non-deterministic log place.

I tried to use coNL = NL to attack this problem. The problem become "find G with the shortest path with even number of edges". Again, I can't deal with "shortest path".


texts: Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?

texts:
Every conjunctive normal form (CNF) formula can be converted to nonlinear system of equations, where each clause becomes an equation in the system and:

If A and B are logical/boolean variables and defined as A∈{T,F} ∧ B∈{T,F} or (A,B)∈{T,F}2 where

{T,F}2={T,F}⨯{T,F} = {(T,T),(T,F),(F,T),(FF)}

Then:

A=x, ¬A=1-x, B=y, ¬B=1-y and A∨B=x+y-x•y

That's how the left side of each nonlinear equation in the system is computed.

The right side of each nonlinear equation in the system is obviously the constant natural number 1.

Finding a solution to this nonlinear system of equations is finding satisfying assignment to the given CNF formula.

That way SAT is reduced to the problem of solving nonlinear system of equations in polynomial time, thus the problem of solving nonlinear system of equations is NP-Hard, because of the fact that SAT is NP-Complete.

But I think that there already exist algorithms that solve nonlinear system of equations in polynomial time and space complexity, if so then also SAT can be solved in polynomial time and space complexity too.

Do I wrong in everything I said?

It sounds too good to be true and

If it's too good to be true, something's wrong.

quote from John Allison.


texts:
I've got 30 elements which has to be  grouped/sorted into 10 ordered 3-tuple.
There are several rules and constraints about grouping/sorting.
For example: Element $A$ must not be in the same tuple same unit $B$.
Element $C$ must not be right in front of element $A$, etc.

I am searching for an approximated algorithm:

We don't need to achieve the exact optimum
It is OK for some rules not to be satisfied, if it helps to fulfill more rules.

Do you know of any algorithm/proceeding that solve this problem or a similar one?
I fear to solve it in an optimal way, you have to try out every possible solution-> $2 ^ {30}$

EDIT: Sorry for the bad explanation. I am trying to make it a bit clearer:
I got 30 elements for example: $\{1,2,3,\ldots,30\}$.
I need to group them into 3-tuples so that i get something like: $(1,2,3)$, $(4,5,6)$,$\ldots$,$(28,29,30)$.

There are several constraints. For example:

1 cannot precede 2 in an ordered tuple, so, for instance  $(1,2,3)$ is not a valid tuple.
5 must be together with 4.

Those constraints can be broken and its possible that there is no solution where all rules can be fulfilled. An solution is considered as good if the amount of rules broken is "low".

Hope that makes it clearer and thanks for the help so far.