texts: Are supersets of non-regular languages also non-regular?

texts:
I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid?

Since $L_1$ is not regular, there does not exists a finite automata $M_1$ such that $L_1$ is the language of $M_1$. Pick $x\in L_1$. So $x \in L_2$ and suppose that $L_2$ is regular. Then there exists a finite automata $M_2$ such that $L_2$ is the language of $M_2$. Since $x \in L_2$ and $L_2$ is regular, there exists a state $s\in S$ such that from the initial state in $M_2$ there is a path $x$ to this final state $s$. Since this holds for all $x \in L_1$, we can construct a finite automata which language is $L_1$, so $L_1$ is regular, so we reached a contradiction, so $L_2$ is not regular.

Can this be done easier?


texts: Maximal subsets of a point set which fit in a unit disk

texts:
Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$.
Moreover, each $P_i$ is maximal, i.e., no unit disk can cover a subset of $P$ that is a strict superset of $P_i$. Visually speaking, if we move a unit disk that covers $P_i$ to cover a point not in $P_i$, then at least one point which was inside that disk will become uncovered.
Here is an example:

In the above figure, there are three maximal subsets.
I don't know whether this problem has a name or was studied before, but here are my questions.

Can $k$ be exponential with respect to $n$?
If not, then can we find those maximal subsets in polynomial time w.r.t. $n$?

I think that there are exponentially many such subsets because of the following argument:
Suppose that the points are centers of some disks with radius $1/2$. If a subset of such points fit in a unit disk, then they form a clique. Since there are exponentially many cliques in a set of disks, then there should be exponentially many maximal subsets of this particular set of points that fit into a unit disk.


texts: Trie traversal to maximise XOR in a tree but with a condition

texts:
Input:I am provided with x and y.

x is a 32 bit non negative integer and y is some node-id of the tree.

So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie.

Now here is the extra condition:

I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum.
How can we find this out efficiently? Preferably in O(log n).


texts: How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

texts:
Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.

I am having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)

For example:

Sequence: [A, C, C, C, A, B, Y, B] is made up from 2 subsequences, namely [A, C, C, C, A], [B, Y, B]

So, therefore, my output for this example would be 2.

Thanks in advance!


texts: Fill in objects that pop out from background?

texts: I need some help with a program that will fill in objects that pop out from the background. For example I have this picture and would like to get an output like this.  I don't know how to do this though (obviously otherwise I wouldn't be asking). And I was wondering if there was some way of filling in objects that don't match the background. The only other thing is that the background isn't always going to be white for example the background could be a blue blanket with a brown dog on it. In that picture it would fill the dog in Black. The last thing about this is that the object that will be filled in will always be centered in the image.


texts: Algorithms that achieve better compression for more data

texts:
I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression".  Could super compression be achieved through recursive compression algorithms?

Here's the kind of algorithm I'm contemplating.  The binary file is first scanned, to identify patterns. After this, the file is rewritten such that the patterns are encoded, e.g., if there is a sequence of 100 $0$'s, it could be represented as $xxx 0$ where $xxx$ represents that the $0$ occurs 100 times.

After this is done, the algorithm is then called on the generated compression file, until a file with no patterns is produced. The header of the file will contain how many times the algorithm was run, so the file can be decompressed.  Will this work to achieve super compression?


texts: Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

texts:
I'm interested in the complexity of a particular variant of 1-in-3 SAT. Assume, as is usual, that clauses are allowed to be of length 1, 2, or 3. Then add the restriction that for any clause of length 3, at least one variable must be "unique," meaning it must appear in no other clause.

Another way to phrase this is, for each clause, at most two variables can be "non-unique" and appear in other clauses.

What is the complexity of this variant of 1-in-3 SAT?


texts: Is it possible for a syscall to pack together different places in memory?

texts:
While programming with buffers like uint8_t* in C++ I often arrive at situations on where I'm forced to do copies. For example, if I receive packets in chuncks from the world and I want to parse something big that is formed of these packets, I'd have to create a bigger buffer and store them, in this buffer, sequentially as they arrive. Then I can parse this big buffer efficiently.

Since the kernel can have virtual memory through page tables, shouldn't it be possible for someone to create a syscall that gets a pointer to a list of all these small buffers (and their sizes), and create a big virtual buffer that acts as if I've copied all the mini buffers inside it?


texts: Determining interests from Twitter text using Latent Dirichlet Allocation

texts:
I would like to  determine interests or hobbies that people have given their Twitter timeline data. Their timeline is their historical collection of tweets.

The result I am trying to achieve is to automatically label a user with a collection of interests such as:

Finance
Photography
Android Development

I have tried using a topic model, LDA, using an individuals tweets as the corpus but I am not so sure about the applicability of the results. LDA gives a collection of terms associated with the topics it found. This requires some manual interpretation to distinguish what the interest is.

For example you might get some results from LDA like the following:

[Twitter, Java, time, work, day]
[code, IPhone, mobile, look, job]
[football, fantasy, team, pick, score]

I can generally pick out the topics people are interested in here but its just the key word or topic identifier I am interested in not the other contextual terms like team, pick or score in the last example. Ideally I would like to transform these term-based results into something like the following interests:

[Twitter, Java]
[IPhone, Mobile Development]
[Fantasy Football]

I have considered how to do this using a supervised approach. Given your categories of interest and using a bag-of-words model with a naive Bayes classifier the task would be to determine which category the topic terms belong to.

This requires labelled data for each category of interest which could be quite time consuming to create. Is there a possible unsupervised learning approach that could work?

I may have gone down the wrong path using topic models, if so, what existing textual research areas could help.

Not looking for a complete solution to the problem, just any suggestions, references or links would be appreciated.


texts: Hardness of approximation for online algorithms

texts: Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds on competitive ratio conditioned on hardness of some other problem?


texts: Is it possible to build DFA for odd-length words with 1 in the middle?

texts:
$L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$

So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and after $1$. A limited DFA for the length less than 6:

How can I expand it so that it would accept any length words? Is it possible?

I tried putting cycles in it, but as I already said, then I just cant keep track of the number of chars after $1$ to be equal to that before. In other words 1 to be always in the middle.


texts:
I have a bivariate function like

$
f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y}
$

and I want to find its global maximum over a range of
$
x \in [0, 200] \text{, and } y \in [300,50000]
$

What kind of algorithms I can use to find the global maximum. I want to have keywords for searching and finding materials.

Are there any java library which I can use to solve these kind of problems?


texts:
Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$.
For eg. Let the array be $1,2,3$ then my answer will be calculated as-
$(2-1)$.$(3-1)$.$(3-2)$=$2$
As number of elements in the array could be large (upto $10^5$) I am looking for solution of order $nlogn$.
I have tried representing array as a polynomial but could get anything out of it.
Please help.


texts: Partition an infinite regular language into 2 disjoint infinite regular languages

texts:
Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, and $L_1$ and $L_2$ are both both infinite and regular.

So far, I thought of:

using the pumping lemma such that
$$ \begin{gather}
  L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\
  L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\
\end{gather} $$
but couldn't prove that they are dijoint or covering $L$ completely.
Using the regular language partitions $\Sigma^*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.


texts:
Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b.

$$(b^{d+1}-1)/(b-1)$$

This holds true for all positive integer values of b, including 0, with the exception of b=1.

If b = 1, we would be dividing by 0. Which, well, we all know is not a "legal mathematical move". However, if b = 1, the number of nodes would be equal to the height of the tree + 1.

I'm not sure exactly what my question is. I just feel like it's weird that a tree with branching factor 0 would have 0 nodes, a tree with branching factor 2 would have $$(b^{d+1}-1)/(b-1)$$ nodes
,
but calculating the number of nodes of a tree with branching factor 1 would be impossible using the same formula.

I don't know what I'm missing. Why isn't there a formula that calculates all nodes in a tree that includes branching factor 1 (or rather, why doesn't this formula include b = 1?)? Or does a tree need a branching factor that is anything else than 1 (but larger than -1?) to qualify as a tree? I'm a bit confused. Help is greatly appreciated.

(Not sure if I got all the facts right here. Please forgive me if I didn't)


texts: Conway's Game of Life: Is it really P-complete?

texts:
Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete problems are difficult, if not impossible, to parallelize.  However, most software for evaluating the Game of Life is parallelized.  The algorithms aren't even that hard to understand.  This seems to be in conflict.  What is going on?  Is Wikipedia wrong, or do I misunderstand something?


texts: Why did Apple include dedicated a neural network "processor" in standard consumer products?

texts:
Not sure if this is the right place, but I guess it is better than Reddit and I couldn't find any discussion.
I was wondering why Apple include a neural network "processor" and can't help but feel that is a waste as a prospective ML Engineer, so it is very likely that I am missing / in ignorance of something so wanted to ask what it is.
Two reasons come to my mind:

Apple will allow a distributed cloud computing on its products (Feels expensive if that is the only reason.).

Improved security. All personal bio-data (fingertip, face, speech) will be stored locally, while processing will be done on wholly local or quasi-local with some calculation going to servers safely.

Does anyone have any idea?


texts: Hash table collisions: why use a linked list if we can use a hash set?

texts:
One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked list? The lookup time would then be constant. For example, in C++ the hash table could be defined as:

unordered_map<int, unordered_set<int>> m;


texts: Dennis Ritchie citation for "the C declarator syntax is an experiment that failed"?

texts:
I've often heard that the C declarator syntax described as "an experiment that failed." I've seen claims that this sentiment is also shared by its creator Dennis Ritchie. Does anybody have an actual citation for this?

I'm doing a related project and writing the documentation for it and it would be nice to have said citation.

FWIW, I have found where Bjarne Stroustrup said it during a Slashdot interview:

  The flip side of this is that you have to deal with old mistakes and with compatibility problems. For example, I consider the C declarator syntax an experiment that failed. Nevertheless, I adopted it for C++. The alternatives and improvements I considered at the time would not have improved matters. I rate is as a minor problem. The more serious problem is to maintain closeness of language definitions as C evolves.

but I'd rather have a citation from Ritchie if one exists.  Yes, I tried Googl'ing for it (which is how I found the Stroustrup citation), but nothing for Ritchie.


texts: Factoring algorithms after number field sieves

texts: It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. So are there faster algorithms after GNFS for classical computers? Note that the 1980s and 1990s saw a series of new factoring algorithms, including elliptic curve and quadratic sieve. And then progress stopped.


texts: Given 5 curves, find the maximum total you can get for each possible level

texts:
Problem

Constraints

I have a collection of curves, $C$. It is a two dimensional array. The inner array contains rational numbers, where the next is greater or equal to the previous.

$$C_{k.i} = v\\
\{k \in \mathbb{Z}: 0 \le k \le 5\}\\
\{i \in \mathbb{Z}: 0 \le i \le 99\}\\
\{v \in \mathbb{N}: 0 \le v \le 1\}\\
C_{n.i} \le C_{n.j}\\
\{j \in \mathbb{Z}: i \le j \le 99\}
$$
I have $n$ levels.

$$\{n \in \mathbb{Z}: 0 \le n \le 5 * 99\}$$

Example

C = [[i / 100 for i in range(100)]] * 5
n = 20

Task

For a given $n$ split it into five non-negative integer indexes. Which are used to index each curve and sum the result to get the total, $t$.

$$
n = a + b + c + d + e\\
t = C_{1.a} + C_{2.b} + C_{3.c} + C_{4.d} + C_{5.e}$$

For each $n$ find the maximum $t$ for a given $n$. And what the values for $a$, $b$, $c$, $d$ and $e$ are.

Solution

The way I solved this was through brute force:

Build list of tuples to store the maximum, $o$.
These tuples are (total, list of products).
Find the value for all products of $a$, $b$, $c$, $d$ and $e$.
For each product find the total of the curves, $t$.

If $o_{n.0} = t$ append [(a, b, c, d, e)] to $o_{n.1}$.
Otherwise if $o_{n.0} \lt t$ set $o_{n}$ to (t, [(a, b, c, d, e)]).

Output $o$.

In Python this can be expressed as: (variable names correlate with the ones defined above)

import itertools

o = [(-1, [])] * 495
for prod in itertools.product(range(100), repeat=5):
    n = sum(prod)
    t = sum(c[i] for c, i in zip(C, prod))
    if o[n][0] == t:
        o[n][1].append(prod)
    elif o[n][0] < t:
        o[n] = (t, [prod])

This runs in $ki^k$ time, which is rather slow.

Question

I think the performance can be improved by using caching or a fancy algorithm.
Can this algorithm's performance be reduced by an order of magnitude?

Ideas

I though running through all values of $n$ adding the highest value $v$ to a running total.
And adding the running total to the output.

This would run in $O(kn)$ time.

But this doesn't work correctly as if there are any curves that start off with a small gradient then the gradient increases to overtake all the other curves. It wouldn't be selected.

I thought about finding the maximum value a curve can be at the provided level.
Then running through output and the maximum curve from $n$ backwards to see if there are any other totals that are greater than the current one.

This seems like it might work, and might run in $O(n^2)$ time, which is significantly smaller than $O(ki^k)$.

However I think it has similar problems to the above solution that I can't think of yet.

I've thought about vectorizing the curve into, $l$, straight lines. I'm not sure what this complexity is, but I'll call it $v$.
From this it is easy to compare vectors to see which have greater starting points, and then a greater coefficient.
Precomputing the intersections, $s$, also allows you to know when to switch to a different vector efficiently.

I've not fully thought this through, but it seems like it could be something like $O((lk + s)n + (lk)^2 + v)$.


texts: What's the formal definition of Big-O notation for functions of more than one variable?

texts:
For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$.

What I don't know is the meaning of $O(g(n_1, n_2 \dots n_k))$ for $k > 1$ totally ordered variables. What's the formal definition?


texts: Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node)

texts:
In following answer (LINK: https://bitcoin.stackexchange.com/a/58908/41513), it has been shown that for Asynchronous Byzantine Agreement:

  "we cannot tolerate 1/3 or more of the nodes being dishonest or we lose
  either safety or liveness."

For this proof, the following conditions/requirements has been considered:

  Our system is asynchronous.
  Some participants may be malicious.
  We want safety.
  We want liveness.

A fundamental question is that:

With considering the well-known paper titled: "Impossibility of Distributed Consensus with One Faulty Process" (LINK: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

showing that:

no completely asynchronous consensus protocol can tolerate even a single unannounced process death,

Can we still assume that the network is asynchronous ? As in that case the network cannot tolerate even one faulty node.


texts: Finding shortest path between two nodes with a set of forbidden nodes

texts: I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am allowed to visit at most one node from the set of forbidden nodes?


texts: How can I store the bit pattern in the register with value

texts: How can i write instruction in Main memory with using Machine language? I have a problem with righting instruction to store the bit pattern in the register R with value XY. Can anybody solve it?


texts:
Given a cubic graph, I want to color its vertices in 2 colors (Say A & B).

A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, vertex colored A has neighbors  A B B is considered Good, and a vertex colored A has neighbors A A B is considered "Bad")

I suggest the following algorithm:

Pick a random uncolored node
Color it in a way that 2 of its neighbors are X, and the last one is Y (Sometimes of course the neighbors are already colored and we determine from that what color the node needs to be and its neighbors also)
Color the node Y

Running this algorithm seems to work, but I couldn't find an example that it doesn't. And even worse - I cannot even understand how to even begin the proof that this algorithm is correct (if at all)

I feel like I need to use the fact that this is a cubic-graph. But I cannot seem to understand how would that help me here.

EDIT (Observations):

It seems that if I get to pick X uncolored nodes, may graph would have at least X "good" nodes (According to the algorithm)
That X would be at least |V|/4

I want to start by proving that there can be more than |V|/4 "Good" nodes, because in all of my examples there are at least |V|/2 "Good" nodes.


texts: Maximum flow with Edmonds–Karp algorithm

texts:
I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.)

If we first follow path S - A - C - T , we will get max flow equals to 1 as we cannot take path S - B - C - T (residual flow from C -- T became 0). I am also assuming that while doing BFS when we reach to t from c, we are stopping our BFS search and returning path. There is D left in the queue but we will ignore it as we have got one augmenting path. On next iteration we will move to B as S -- A edge residual capacity is 0.

If we first follow path as S - A - D - T and then S - B - C - T , we get max flow as 2.

I think, I am missing some basics, I belive algorithm does not dependend on which path I take first.

Thanks in advance.


texts: Why are combinators important in lambda calculus?

texts:
I just recently learned a little about the lambda calculus, from the brief intro in the text Programming Language Pragmatics and this outstanding 4-video sequence from Adam Doupé. Basically I learned the gist of lambda calculus, $\alpha$-conversion and $\beta$-reduction, a bit of Church numerals, addition/subtraction, and the $Y$ combinator.

In this I learned the concept of a combinator, i.e. that it is an abstraction with no free variables. Simple concept. And there seemed to be this idea I kept reading between the lines, that we can/should turn non-combinator abstractions into combinators by wrapping them in abstractions that bind the free variables. For example, we can take the abstraction $(\lambda x. xy)$ and wrap it in $(\lambda y. \lambda x. xy)$ to bind the $y$.

But it was never really explained why it is important or useful to prefer combinators.

I'm assuming its because combinators allow us to easily combine expressions (surprise surprise) without the need of any externally-supplied variables. So in other words we could evaluate an arbitrary-length series of combinator applications without having to provide any initial conditions ahead of time. Which to me sounds like the equivalent in programming of avoiding global variables so as to avoid looking up values outside the current scope, in order to make it easier to understand the program and reduce errors. It also seems to align with the idea of a "pure functional" language that has no variables and no side-effects, which would imply such a language is effectively a series of combinator applications.

Is that correct?


texts:
I am looking for a better explanation (research level, papers) to answer:

Why translating a program from one high-level programming language directly into another is difficult?

Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply because I am unaware of such results, but you are very much welcome to correct my ignorance.

I understand that at the core of the argument can say something like one-to-one mapping for such translation simply does not exists.

In general, I am not comfortable with terminology used in my own question.

We know from text books: Low-level language - each command or object of the language has one-to-one mapping to CPU commands (e.g. Assembler). All other languages are High-level.

Is there a way to reformulate the question into FSA formalism like with  regular languges, or some other formalism. But I don't think Church–Turing thesis can help here - it is not about computability or existence of a proof.

PS

My motivation is very simple - I want to discuss/answer how difficult is such a problem for example in translating PHP to Java. Please note that direct translation is indeed a mapping of language commands or objects  (e.g. HipHop does not qualify).

Probably any pragmatic solution would be indirect translation, i.e. in order to (partially) convert a program P written in high-level language A into a high-level language B:

(complexity lowering) convert codebase of program P from A to low or inter-mediate level language C
(shared codebase) resue parts of converted codebase of program P by calling commands in low or inter-mediate level language C from high level language B


texts: Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a way to do it faster than Floyd-Warshall's $O(|V|^3)$?


texts: Are the frequencies of the Huffman encoding of 3 characters unique?

texts: I have to figure out the frequencies of 3 letters for Huffman encoding of {0, 10, 11}. One suggestion is in the order {$\frac{2}{3}$, $\frac{1}{6}$, $\frac{1}{6}$} as given in part (a) the 2nd slide of page 3 here. My question is whether the last 2 character frequencies need to be evenly split. Could we not have had {$\frac{2}{3}$, $\frac{2}{18}$, $\frac{1}{18}$}? Or could the 3 character frequencies be entirely different say {$\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$}?


texts: Proving that any CF language over a 1 letter alphabet is regular

texts:
I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:

Let $L$ be a context free language. So, $L$ satisfies the pumping lemma. Let $p$ be $L$'s pumping constant. Let $L = L_1 \cup L_2$ where $L_1$ consists of $w$ where $|w| < p$ and and $L_2$ consists of $w$ where $|w| \ge p$. We have a single letter alphabet and since $L_1$ has a restriction on the length of its words, $L_1$ is a finite language. Finite languages are regular so $L_1$ is regular. If I can show that $L_2$ is regular, I can use the fact that the union of regular languages is regular. But I am struggling on showing that $L_2$ is regular. I know that since $w \in L_2$ has to satisfy $|w| \ge p$, by the pumping lemma, $w$ can be written as $w = uvxyz$ where $|vxy| \le p$, $|vy| > 0$ and $\forall t \ge 0$, $uv^txy^tz \in L$. Since we have a single letter alphabet (say the letter is $a$), $uv^txy^tz = uxz(vy)^t = uxz(a^{|vy|})^t \in L$. Now what?


texts: An underestimated tradeoff between Memory and the Effectivity of Computation?

texts:
Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form such as runtime?

(A good purely theoretical startig point to work with could really be a number sequence...)


texts:
I've given a task and wonder if there are any better solutions.

Inputs of task are:

Distance of district pairs
Population of pairs

Goal is:

Find n districts at which its population and districts x miles range districts' population is max.

Extra information:

Unique district size is tens of hundreds.

As an example, if I pick up district A, population will be A's population plus other districts' population which are less than x miles far away from it. Total population will be   n districts at which population is calculated as I mentioned.

What I've tried:

Brute Force
Generic Algorithms

What I planning to do:

A* Search

My question is, there may be any other solution (optimal if possible) instead of these one. i.e. sorting districts by their population, merging x miles nearest to them into one until I get n districts.

Any ideas?


texts:
Can someone help me to store the factorial of large numbers such as 100! efficiently?

UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving. The true challenge is to find a data compression scheme that achieves a significant compression ratio, but with a lighter computational complexity than recomputing the factorial(s) from the argument.

More precisely, can you design an algorithm to produce all decimal digits of $n!$, for $n\le N$, using $o(N\log N!)$ storage and small computational cost, such as the lower bound $O(\log n!)$.


texts: given an AVL tree with $size$ value to any vertex $v$ in the tree (which is the size of the tree rooted in $v$), is it possible to tell for a given value in the tree, what its order in the sorted group in $log (n)$ time complexity?


texts: Why Finite Automata are restricted in reading the input?

texts:
Well, I should have posted this question before Why NFA is called Non-deterministic?. Anyways now this is pondering in my mind.

Why people who came up with this automaton theory restricted the input format of it as a read-only, symbol-stream tape.

Is it not so that if we provide random accessible input tape (as in case of many computer programs) to the automaton it will be more powerful? (however it is purely my intuition having no standard proofs)


texts: In a DFA, does every state have a transition on every symbol of the alphabet?

texts: If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?


texts: Why can humans solve certain "undecidable" problems?

texts:
High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where a and b are open terms on the simply typed lambda calculus, finds a substitution S such that aS => bS, where => stands for "has the same Bn normal form". Yet, humans can solve that problem efficiently. For example, given the following problem:

a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

Any human with sufficient knowledge on the lambda calculus will be able to notice F is the "double" function for church numbers, quickly coming with the solution that

 F = (λ a b c . (a b (a b c)))

My question is: if that problem is undecidable, how can humans quickly and effortlessly solve it?


texts: How did it happen that Algol 60 was an improvement on its successors?

texts:
The original statement referred to by this question is:

  The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

(From the appendix of a very readable report on programming language design by C. A. R. Hoare. I read that report because I wanted to ask this question, not the other way round. Reading that report made it clear to me that the original statement is even more true than I thought when I decided to ask this question.)

The intention of this question is to better understand the sociological and political aspects of the events, not the detailed technical merits. The politically accepted successors of Algol 60 (at the time) like Algol 68, PL/I or Ada were badly feature bloated, while really improved successors like Algol W or Simula were never widely used. The surviving members of the Algol language family seem to prefer naming Pascal as their great-grandfather instead of Algol, even so Pascal seems to be just another descendant of Algol. (C or Smalltalk are not descendants of Algol, because their syntax and underlying principles are too different. C++ on the other hand might be considered as a legitimate descendant of Simula, embodying many of the same underlying principles, adopting the C syntax and legacy only for political reasons to avoid the fate of the Algol like languages.)

An account of the history of types in programming languages made me realize that even the type system of Algol 60 was still quite unfinished. It seems that it would have been easy to just finish the type system and fix some other minor annoying details for the next revision of the language. But instead... ???
Most of my math books use Algol for their pseudocode, and it looks much nicer than the C pseudocode in the few books that don't use Algol. So I always wondered why Algol actually died.


texts:
Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing the opposite access to be slower.

This is somewhat surprising, since I think I remember that physical RAM is actually a 2 dimensional structure. And looking at the free part of this article. It seems like there exists a burst mode for accessing multiple elements from the same row.

Why does this burst mode not exist for columns, and why do programming languages not allow for true two dimensional storage of data? This would allow for "row major"/"column major" agnostic designs, which would probably speed up a lot of linear algebra libraries. Which would then trickle down to statistics and machine learning.

(Crosspost from StackOverflow)


texts:
I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $l(p)$, that can solve the problem in time $t$, then Universal Search will solve the problem in a time $2^{l(p)+1}t$ at most.” How do they arrive at this number? Here is what I tried.

If we put all programs in a list, it looks like $e,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,\ldots$
Generally, the first occurence of a program of length $l$ is at the $n$th position, with $n=2^l-1$.

Now, I have encountered two different dovetailing procedures in the literature. The first describes executing program 1 every second step, program 2 every second of the remaining steps, program 3 every second of the remaining steps etc. This leads to the following execution sequence of the programs $n=1,2,3,4,5,6,\ldots$:
$1213121412131215121312141213121612\ldots$
At step $i$ then $n$th program will have been run for $i/2^n$ steps. In the example above $i=34$. Thus, for $n=1,2,3,4,5,6$ we get $17,8,4,2,1,1$ (rounded) which is roughly correct.

Now, suppose there exists a program $p$ that computes a string $x$ in time $t$, whose position is $n$ in the lexicographic enumeration. This means that it will be the value of our time step $i$: $t=i/2^n=i/2^{2^{l(p)}}$. Therefore, $i=2^{2^{l(p)}}t$, which doesn't match the claim $2^{l(p)+1}t$.

In a different description, the execution is done in phases such that the first $i$ programs are run for 1 step at phase $i$. Therefore, before phase $i$, the $n$th program will have been executed $i-n$ times. We require the $n$th program to be executed $t=i-n$ times. Then, we get $i=2^{l(p)}+t$, which is the number of phases. The number of time steps to get to phase $i$ is $i^{2}/2$ (the area of the triangle). Hence we get $\left(2^{l(p)}+t\right)^{2}/2$, which is much larger than $2^{l(p)+1}t$.

Looking at the expression $2^{l(p)+1}t$ it looks like every program up to length $l(p)$ is executed for exactly $t$ time steps. But I thought, Levin search allocates execution time such that shorter programs are favoured?

Where is my mistake? Any help is greatly appreciated.


texts:
I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances between the $K$ points is smallest. A brute-force way is to search all combinations of $K$ points from the $N$ points. However, $K \ll N$. For example, $K$ is 5 and $N$ is 100. It is infeasible to search all ${100 \choose 5}$ combinations.

Actually, the distance between points is a metric to measure the difference between elements in the set, so it is better to describe the problem using graph rather than computational geometry.

I have read Clique problem on wiki, but I think the setting is different from my context here.

More info: The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set.


texts: the convention for declaring arrays in pseudocode

texts:
I have a very simple question.
What is the right standard convention to use for declaring arrays?

I understand that for a simple declaration of a variable as an integer, this is the convention:

DECLARE myVar : INTEGER

What about for an integer array of 10 elements?

DECLARE myVar : ARRAY[1,10] of INT

or

DECLARE myVar[1,10] : ARRAY of INT

or something else?


texts: Proving that an equal partition does not exist

texts:
We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.

To prove that an equal partition exists, it is sufficient to show a partition.

What is the shortest way to prove that an equal partition does NOT exist?
Apparently the only way to prove it is to show all the partitions and show that they are not equal. Is there a shorter proof?


texts: How can every regex be accepted by an infinite number of finite automata?

texts:
In The (New) Turing Omnibus by A K Dewdney, chapter 2, it says:

  Moreover, for every regular expression there is an automaton which accepts the language symbolized by that expression. Thus, in a sense, regular expressions capture precisely the behavior of automata in terms of the language they accept. However, for every regular expression there are an infinite number of automata which accept that language.

But for a simple regex, e.g. a, I can think of exactly one finite automaton that corresponds to it: (start state) -a-> (accepting state). I don't see how there can be an infinite number. What am I missing?

For context, at this point in the book he has not yet introduced DFAs vs NFAs, and all examples of automata so far have been DFAs.


texts: Scientific soundness of computer science papers

texts:
First of all, this question relates to an issue that affects several areas of science, but since StackExchange doesn't have a meta science section I'll make it specific to computer science, which is pertinent because the solution to the bigger problem may actually come from computer science.

In the context of the news that Springer and IEEE published more than 120 nonsense papers my question is as follows:

What rigourous set of methods can we apply to the process of publishing scientific papers so that we can quickly verify the reproducibility of the experiments?

We already have systems like Turnitin that are highly efficient at detecting plagiarism, yet I don't know of any system that can score a piece of work on its scientific soundness.

Is there any ongoing work related to this? I found out about Semantic Publishing whilst composing this question, but I have no idea what other approaches, if any, are being actively worked on.


texts: Are there hardware lock implementations without test-and-set or swap?

texts:
Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these?

Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, namely, interrupt disabling, test-and-set and swap?


texts: Can an operating system without api still work?

texts: In theory operating system is a special program run by itself without help so that also mean normal program can still run by itself mean that the need for api is not must have so finally can we have an os without api ?


texts: Mathematical Induction Problem from Concrete Abstractions

texts:
This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem:

  Exercise 2.16
     Consider the following procedure foo:

(define foo
  (lambda (x n)
    (if (= n 0)
        1
        (+ (expt x n) (foo x (- n 1))))))

  Use induction to prove that (foo x n) terminates with the value
          $$\frac{x^{n + 1} - 1 } {x - 1}$$

  for all values of x != 1 and for all integers n >= 0. You may assume that expt works
     correctly, (i.e., (expt b m) returns $b^m$). Hint: The inductive step will involve some algebra.

I've watched a video on induction on Khan Academy and read the induction material in the book, but I can't connect the dots to solve this problem.

Edit:
I am stuck at the Inductive step. My work:
Base Case:

(foo x 0)
(if (= n 0)
    1)

returns $1$ and

$\frac{x^{0+1} - 1} {x - 1} = \frac{x - 1}{x - 1} = 1$

So for the inductive hypothesis: Assume (foo x k) terminates in $\frac{x^{k+1} - 1}{x - 1}$ for all $k \geq 0$. Then for $k+1$:
I essentially add $k+1$ for the assumed formula above, so:
$\frac{x^{k+1} - 1}{x - 1} + k+1$. What I get is a long equation that I have no idea what to do with.


texts:
I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$.

I would like to select a subset $S$ of the columns that maximizes the ratio $$\left(\sum_{j\in S}a_{1j}\right) / \left(\sum_{j\in S}a_{2j}\right)\,.$$

Can this be done efficiently?  Is this a known problem?

For example, if

$$A=\begin{pmatrix} 1 & 2 \\ 2 & 3\end{pmatrix},$$

then the best thing to do is to choose the second column. Because, (i) if I choose column $1$ I will get $1$ as the sum of the first row and $2$ as the sum of the second row, (ii) if I choose column $2$ I will get $2$ as the sum of the first row and $3$ as the sum of the second row and (iii) if I choose column $1$ and column $2$ I will get $3$ as the sum of the first row and $5$ as the sum of the second row.


texts: Some Questions related to Linear programming

texts:
I have some question related to the Linear Programming problem:

If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite optimum solution. My question is what is the meaning of "finite" here?
If we need to solve LP using the simplex method, we need to transform any constrain that is written as an inequality equation to equality equation using the addition of the slack variables, so my question is by doing this modification did we change the problem? I mean that we have added an extra variable so I think that we have created a new constraint?
Also to solve the LP using simplex method, we need to have a maximization problem, so if we have to minimize an objective function, in this case to transform it to a maximization problem all we need to do is to negate the coefficients? For example, we need to minimize $3x+y=2$; is this equivalent to maximizing $-3x-y=2$?


texts: How does one deduce small step operational semantics?

texts:
This question arises from my reading of "Types and Programming Languages" (WoldCat) by Benjamin C. Pierce.

For the small step operational semantic evaluation rules for the arithmetic expressions (NB) in Figure 3-2 on page 41, there is the rule

  $pred\;(succ\;nv_1)\rightarrow\;nv_1$

My understanding is that it is to keep out invalid input like

  $pred\;(false)$

but how did he come to that exact syntax for the rule? Is there some algorithm that is used to massage the rules into the necessary form? Is there some book or paper that explains how to formulate rules for small step operational semantics?

Note: I am aware that there is a forum dedicated to questions for the book here.


texts: Any evidence that one way functions exist?

texts:
There is no known proof that one way functions exist. But what is the heuristic evidence that they exist?

I sometimes read that the existence of cryptography is heuristic evidence that they exist. E.g. the ciphertext from a block cipher like AES is easily computable if you know the plaintext and key, but the key is not easily computable if you know the plaintext and ciphertext.

This is seen as evidence that AES might be a one way function, but to me it simply suggests that we don't know how to invert AES. In other words, it seems like this is an algorithm-search problem that is very hard (finding the key inversion algorithm), not that that algorithm doesn't exist.

Is my reasoning correct? Whether it is or not, what is the heuristic evidence that one way functions exist?


texts:
I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows:

  Assume a rightmost derivation
  $\require{AMScd}$
  \begin{CD}
  S @>{\text{*}}>> \alpha X\omega @>{}>>\alpha\beta\omega
\end{CD}
  Then $\alpha\beta$ is a handle of $\alpha\beta\omega$.

When I referred the Dragon Book, it says:

  if $\require{AMScd}$
  \begin{CD}
  S @>{\text{*}}>> \alpha A\omega @>{}>>\alpha\beta\omega
\end{CD}
  then production $A\rightarrow\beta$ in the position following $\alpha$ is a handle of $\alpha\beta\omega$. For convenience, we refer to the body $\beta$ rather than $A\rightarrow\beta$ as a handle.

So which one is correct? Is $\alpha\beta$ called as handle, or just $\beta$?


texts: Information capacity of Ternary-based system over Binary-based

texts:
Some researchers are trying to get a memory cell capable of having 3 states instead of 2.

1) How many memory cells, in principle and as a rough estimate, does a typical 1 megabyte memory chip has? is it 8*1024 cells?

2) If you have N memory cells, each has x logical levels, what is the number of possible representations that we can get out of it? is it x^N representations?

Let's take Binary system as an example. Say we have 8*1024 memory cells. We can store
only one of the possible 2^N representations in each cell, so at the end the number of stored bits is just N=8*1024.
Now, for Ternary system, the gain is log2(3) ~ 1.58 times so we can store ~ 1.58 * 8 * 1024 "bits" or 8*1024 "trits".

Correct?
EDIT: sorry I meant 8*1024*1024.


texts: Whats is the meaning of polynomial run-time in input size ?

texts:
If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ?
Why ?
Doesn't the algorithm run in exponential time anyway ?
How the input size affects ?
Thanks.


texts: Complexity of set oprations in algorithm

texts:
I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership).

Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone used them as $~\mathcal{O}(1)$ in his paper?

What minimum complexity should I assume for these operations? References are welcome.


texts:
Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). Denote the indices of bins having balls as $x_1, \cdots, x_{2k}$ in ascending order ($x_1 < x_2 < \cdots < x_{2k}$). We define the score of a configuration as $\oplus_{i=1}^{k}(x_{2i}-x_{2i-1}-1)$, where $\oplus$ is "bitwise exclusive or", or "xor". I'd like to count for each possible score, how many configurations are there?

Range: $n \leq 10^5, k \leq 50$. I've tried dynamic programming: let $f[i][j][s]$ be the number of configurations with $i$ bins, $2j$ balls, $s$ scores, but the time complexity is too high. I was wondering whether we may count the configuration more efficiently.


texts: Fast algorithm for max-convolution with concave functions?

texts:
I'm interested in a discrete max-convolution problem, which is to compute
$$r(c) =  \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$
for all values $c=0, \ldots, C$, where $x=(x_1, \ldots, x_k)$ is a vector of non-negative integers.

If we assume that $f_k$ are all concave functions i.e., $f(i+1) - f(i) \le f(i) - f(i-1)$, how efficiently can $r = (r(0), \ldots, r(C))$ be computed?

Follow-up: what if $J$ of the $f_k$ functions are not concave?


texts: Minimal connected subgraph containing 4 specific vertecies

texts:
Let $G$ be an undirected weighted connected graph with non-negative weights on the edges,
and let $v_1, v_2, v_3, v_4$ be 4 vertecies in $V[G]$.

The goal: find a connected subgraph of $G$ with minimal weight (the sum of weights of the edges in the graph) that includes $v_1, v_2, v_3, v_4$.

Any polynomial algorithm will suffice.
A correctness claim will be appriciated.

I've come up with an example that any shortest path between $v_{1-4}$ isn't in the subgraph:

In this example, the best subgraph would contain all the vertecies, and the edges in the middle of weight $2$, and not the direct shortest paths between $v_{1-4}$ of length $3$, so running Dijkstra's algorithms between the $4$ edges doesn't directly help with the solution.

Also, the solution is a tree because any cycles only add cost.


texts: Detect assigned variables in expression in linear time

texts:
Let's say I have the lambda calculus extended with set! for assignment.

e ::= x
   |  (lambda x . e)
   |  (e e)
   |  (set! x e)

What I would like to do, is walk through a program in this language, and add an annotation to each lambda expression denoting all of the assigned variables in it.

So for example, we could put it in the following language:

e ::= x
   | (lambda x . ae)
   | (e e)
   | (set! x e)

ae ::= (assigned (x ...) e)

(In this example we could say x ... is a set for constant time access if we would like to.)

The most trivial algorithm which walks down each structure and combines each expression is $O(n^2)$. (Assuming we have constant time set access.)

The algorithm will look something like this:

(define (ae e)
  (match e
    [`(lambda (,x) ,e)
     (define-values (e* a) (ae e))
      (values `(lambda (,x) (assigned ,a ,e*))
              (set-remove a x))]
    [`(,e1 ,e2)
     (define-values (e1* a1) (ae e1))
     (define-values (e2* a2) (ae e2))
     (values `(,e1 ,e2)
             (set-union a1 a2))]
    [`(set! ,x ,e)
      (define-values (e* a) (ae e))
      (values `(set! ,x ,e)
              (set-add a x))]
    [x
     (values x (set x))]))

(I did take some liberties in this algorithm because having an immutable set means it will be $O(log(n))$, rather than $O(1)$, but that is easily fixable by using a mutable set and adding and removing the elements at the start and end of the recursion.

The problem here is the set-union, which, at best, can be $O(log(n))$ (sure, there are some representations that are $O(1)$, but those representations, as far as I know, do not also have $O(1)$ additions and removals.

There is another, more complicated algorithm that walks down the expression, and mutates the outer expression when it sees an assignment. This however, is $O(n^2)$ because it will have to mutate (at worst) $O(n)$ expressions when it get's there. The program that would cause this behavior would look something like this:

(lambda x . (lambda a . ... (lambda z . ((set! x 1) ... (set! x 1))) ...))

So, is there a linear time ($O(n)$) algorithm that can find all of the assigned variables in every lambda expression in a program?


texts: How does the forget layer of an LSTM work?

texts:
Can someone explain the mathematical intuition behind the forget layer of an LSTM?

So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), but I'm also assuming it's a matrix. Then the forget vector is calculated by concatenating the previous hidden state and the current input and adding the bias to it, then putting that through a sigmoid function that outputs a vector then that gets multiplied by the cell state matrix.

How does a concatenation of the hidden state of the previous input and the current input with the bias help with what to forget?

Why is the previous hidden state, current input and the bias put into a sigmoid function? Is there some special characteristic of a sigmoid that creates a vector of important embeddings?

I'd really like to understand the theory behind calculating the cell states and hidden states. Most people just tell me to treat it like a black box, but I think that, in order to have a successful application of LSTMs to a problem, I need to know what's going on under the hood. If anyone has any resources that are good for learning the theory behind why cell state and hidden state calculation extract key features in short and long term memory I'd love to read it.


texts: Schedule repeating jobs of fixed length and different weights

texts:
I have a scheduling problem that I am not sure is a known variant with known algorithms. It does appear like bin packing problem at first, but after imposing the constraints, I am not sure what it becomes.

There are $n$ atomic Jobs, $J_1, J_2, ... J_n$, each with same length, say 1-hour.

These jobs have weighs, $w_1, w_2, w_3, ... w_n$

The scheduling time is divided into interval of same length (1-hour) $t_1, t_2, ... t_T$

During each scheduling interval, $t_i$, a set of Jobs can be run in parallel as long as their total weight remains at or below a constraint $C$ .

(If we were just required to schedule these jobs and finish everything at the earliest possible time, this would exactly be a regular bin-packing problem.)

However, we have a release time and deadline constraint on the jobs as follows:

For each job, such as $J_i$, there are two set of constraints:

$H_{i,j}$ => The maximum number of times job $i$ can be executed in time interval $t_1$ to $t_j$
$L_{i,j}$ => The minimum number of times job $i$ should be executed in time interval $t_1$ to $t_j$

In other words, each Job must be run multiple times but should respect the above constraints.

It might be helpful to note that, for a given $i$ (that is for a given job), the $H_{i,j}$ and $L_{i,j}$ are staircase functions with constant width.

The problem is to check if it is possible to schedule the jobs (into the time slots $t_1, t_2, ... t_T$ by satisfying the above constraints)

Does this problem sound familiar?

Thank you.


texts:
I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me.

Lamport defines the "happened before" partial order, which I understand. Then he says that "Another way of viewing the definition is to say that a -> b means that it is possible for event a to causally affect event b".

Consider now two events a and b that are message receptions at a process P1, such that a occurs before b. Further more, suppose a and b are the only two events ever occurring at P1. According to the happened-before relation definition, we have a -> b (which makes sense, since P1 observed those event in this order).

However, I don't see how it is possible for event a to causally affect event b. Those two events are totally unrelated and could have happened in a different order.

What am I missing here?


texts: How does the Earley Parser store possible parses of an ambiguous sentence?

texts:
I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two?

the grammar im talking about is the following:

S -> VP NP
VP -> V VP
VP -> VP PP
NP -> NP PP
NP -> Det N
PP -> P NP

so you while parsing could either attach a PP to an NP or to an VP.

my question is detail is how the graphical chart would look like, meaning the positions of predict, scan and complete. I was assuming that both parses would be stored in one (big) chart. So S' will then be found in, let's say, s[0][8] and s[0][16] ? Is that right?

An attached image or link with a graphical chart parsing through an ambigous sentence would help.


texts: Transforming a byte with a subset of a small, fixed set of values and xor into any other value

texts:
If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, each affecting a single bit 0x80, 0x40, ... 0x01: every possible value is represented by some combination of operations from any given starting point.

But, clearly there are other sets of eight values which achieve this. For example 0b1xxxxxxx, 0b01xxxxxx, 0b001xxxxx, 0b0001xxxx, 0b00001xxx, 0b000001xx, 0b0000001x, 0b00000001 clearly satisfy these criteria and are a relatively large set of such values (as the x's can be distinct). (Proof: use the first value to get the msb correct then the second to get the second-msb correct, etc).

However, some sets clearly do not have this property, for three bits 0b101, 0b110 and 0b011, for example, clearly do not as every operation preserves parity.

I am interested in various aspects of the above property from a practical standpoint for a numerical computational model. I am not a theoretical computer scientist, but have studied these things in the last century, so I am vaguely aware that what I need to look at may amount to groups, Galois Fields, LFSRs, etc.

Could someone point me in the right direction so that my learning can be more directed than random flailing around textbooks and wikipedia? Just some signposts as to the names of the relevant fields of study, the great theorems/problems/categories and their names, the useful techniques, etc, would be fine.


texts: Big-O notation for Polynomial Time Complexity

texts:
Recently we had a quiz where one of the question were -
Q: Asymptotic notation for polynomial :

 - 2^Ο(n)
 - Ο(n log n)
 - n^Ο(1)
 - None of these

I know that Polynomial time complexity is $\mathcal{O}(n^c)$, where $c$ is an arbitrary constant.

But then I checked it up on Wikipedia, and it got me confused.
According to Wikipedia, Polynomial Time Complexity is $2^\mathcal{O(log n)} = poly(n)$, where  $poly(x) = x^\mathcal{O(1)}$.

So my questions are -

What is the $Big-O$ notation for Polynomial Time Complexity
and how is it $2^\mathcal{O(log n)} = poly(n)$ ?
What will be the answer for the quiz ?   I have answered None of these .

Also it has got this line - In the table, poly(x) = x^O(1), i.e., polynomial in x.

What does polynomial in x means ?


texts: How to give the nearest text that the user has written

texts:
In my database I have 1500 food dishes, not all are single words, there are compound words like "cheese with dried fruit and nuts". And I have them in 5 languages (de, en, fr, es, it).
My question is how could I do it so that given a text it gives me a prediction of the 5 dishes that are closest to that text.
For example, if the user search for "roquefort with almonds" as closest would return "cheese with dried fruit and nuts" and other 4 results with other dishes.
I have thought about using the Word2Vec model but I am not sure how to start (I am quite a novice) if I should do transfer learning, or how.
Could someone guide me on how to approach the solution to this problem?


texts: Algorithm complexity of this program is O(n) or O(n^3)?

texts:
I am very much confuse that why complexity of this program is O(n)?

 int j = 0;
 int i;
 For (i = 0; i < n, i++) // O(n)
 {
      For (i = 0; i < n, i++)//O(n)
      {
        While (j < n)// O(n)
       {
        Statement; j++;
       }
   }
 }

I am totally new to Algorithms. Any help and explanation will be appreciated.


texts: is it possible to find the maximal min cut in polynomial time?

texts: A maximal minimum cut is a minimum capacity cut with the largest number of edges.


texts: Why do I get really different results with my benchmarking code I made?

texts: I'm doing research work for my last year in high school. My work is about processors and for the experimental part i've coded an app that can mesure how many Floating Point Operation can a processor do in one second. My problem is that i get really different results depending when I execute my benchmark, I can get 5,6 GFlops and then 5 seconds later I can get 1,6 GFlops. How is this possible? Isn't measuring a processor aproximate speed with how many floating point operations per second can do useful? If not, what ways are useful to get an aproximate result of how fast is a CPU.


texts: Longest substring with consecutive repetitions

texts:
I want to find the longest substring which is repeated without any gap between the repetitions.  That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $x$.

What I mean is the following cases:

In "aa"         I want "a"    with a position of 0 and repetition of 2
In "aaab"       I want "a"    with a position of 0 and repetition of 3
In "abc"        I want ""     (false or whatever)
In "abababc"    I want "ab"   with a position of 0 and repetition of 3
In "aaabbbb"    I want "b"    with a position of 3 and repetition of 4
In "eabcdabcde" I want "abcd" with a position of 1 and repetition of 2
In "cababcab"   I want "ab"   with a position of 1 and repetition of 2 (not 3, because of the "c" between the three "ab"'s)

I've been looking at various suffix and prefix algorithms, but none of them has the "no gaps" part build into it. Both LCP arrays and Suffix arrays seems to suffer from this.

Googling for "Longest repeated substrings" gives me algorithms which e.g. find "hello" in "abcdehellofghijhelloklmn", but this is not what I want.


texts:
In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142):

A language $L$ is in NP if there is a turing machine $M$ with the following properties.

If $x\in L$ then there exists a witness string $w$ such that $M$ halts in the state $q_Y$ ("yes state") after
a time polynomial in $|x|$ when the machine is started in the state $x$-blank-$w$.
If $x \not \in L$ then for all strings $w$ which attempt to play the role of a witness, the
machine halts in state $q_N$ ("no state") after a time polynomial in $|x|$ when $M$  is started in the
state $x$-blank-$w$.

This definition is motivated by the factoring decision problem, where they identify "witness strings" $w$ with possible factors of $x$.
My confusion is, based on how NP is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $x$, start the factoring turing machine $M$ in the state $x$-blank-$w$ for all $w < x$, and check whether the machine ever halts in $q_Y$. Since there are $O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $x$ has factors in polynomial time.
Clearly this shouldn't work, but I am unsure where the flaw in my logic is.


texts: Is there a name for defining recursive functions as an infinite list of input/output pairs?

texts:
Recursive functions are usually defined by directly calling a function inside its own body.

Nat = Z | S Nat
double Z = Z
double (S x) = S (S (double x)))

What if, instead of defining them this way, we just enumerated two recursive datatypes and zipped them?

To be more descriptive, mind the following functions/types:

enum Nat = [Z, S Z, S S Z, S S S Z ...]
elem (S S S Z) (enum Nat) = 3
[4,5,6] !! 1 = 5
zip [1,2,3] [4,5,6] = [(1,4), (2,5), (3,6)]
# a b = \x -> (zip (enum a) (enum b)) !! (elem x (enum a))

That is, enum enumerates elements of a recursive datatype, elem, !! and zip are just as defined by Haskel. Now, using #, there is an interesting way to define some recursive functions.

Even = Z | S (S Even)
double = Nat # Even

This makes double equivalent to:

double x = [(0,0),(1,2),(2,4),(3,6)...] !! x

In other words, instead of defining the function recursively, we just created an infinite list with the input/output pairs of that function, by zipping two recursive datatypes together. I never heard of this approach being used, so my question is: this there a name for this? Any relevant papers? What kinds of functions can be defined this way?


texts: proving L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular

texts: I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?


texts: How do I simplify this boolean expression?

texts:
I have constructed truth tables to prove that:
$ABC + ABC'+ AB'C +A'BC = AB+AC+BC$

How do I prove it by simplifying the expression? I know that I can simplify:  $ABC + ABC' = AB(C+C')=AB$. However I can't repeat this for $AB'C$ or $A'BC$, to get the answer I desire.

I'm fairly new to boolean algebra and have tried to use the basic identities to figure it out, but can't seem to get there.


texts: How is momentum an approximation of Hessian based optimization?

texts:
In the answer to "what is the Hessian" at this site:

https://stackoverflow.com/questions/23297090/how-calculating-hessian-works-for-neural-network-learning

the person answering the question concludes by saying

"Fun fact, adding the momentum term to your gradient based optimization is (under sufficient conditions) approximating the hessian based optimization (and is far less computationally expensive)."

I have tried to understand this point and look online but am not sure what is meant by the momentum approximating hessian based optimization. How is momentum like hessian based optimization?


texts: How can a spinlock progress when it's busy-waiting?

texts:
I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives signal(lock) or release(lock) from other processes. This causes busy waiting and hence CPU cycles are wasted.

My doubt is, if CPU is continuously checking the value of lock variable in loop, then how will some other process completely execute critical section and release the lock as executing critical section also needs CPU and CPU is busy checking the value of lock in other process?


texts: Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

texts:
Given a graph $G=(V,E)$ with $|V|=n,|E|=m$. I am reading a $\textit{brute force}$ solution to determining whether each candidate vertex cover of size $k \leq n$ is a vertex cover. The graph does not have loops.

As per page 2 of the notes here we have:

1) $C(n,k) = O(n^k)$ $k$-subsets of $V$
2) $O(kn)$ time to check whether a subset is a vertex cover

I am considering 2).

What I would think of would be to take each edge in our graph, for which there is a maximum of ${n \choose 2} = O(n^2)$, and check the candidate subset to see if at least one of the vertices is an endpoint of the edge, which would take $O(kn^2)$ checks.

I am not sure how the author arrived at $O(kn)$ operations, any insights appreciated.


texts: What is the intuition behind Heap's Algorithm?

texts:
I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set.

What I can't understand is why if n is even the letter swapped is i and when n is odd the letter shifted is at position 0.

I know it works but what is the intuition behind it ?

How come when n is odd there is always an unique letter in the beginning ? While if n is even the unique letters are from 0 to n-1 ?

The pseudo - code that I am looking at is -:

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
        generate(n - 1, A)
    end if


texts: How do 2-3 FingerTrees generalize to bigger branching factors?

texts:
FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to amortize per-node overheads better, or to improve lookup performance at the cost of update performance.

For example, we might want branching factors of 31-32 as in RRB-trees, or branching factors of 16-32 as in B-trees. How should the size of the Digits change to accommodate these branching factors? More generally, are there algebraic conditions on the size ranges of Nodes and Digits which are sufficient to guarantee the asymptotics (logarithmic access to the middle; constant-time access to the ends) of FingerTrees?


texts: Dynamic programming and multiple optimal solutions

texts:
I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not possible and one of my solutions can't be found this way?

From this YouTube video we are given the problem of finding the optimal rod cuttings for maximizing profit.

The rod has a length of $n=5$, and the possible ways to cut with its respective values in parenthesis are $1(2)$, $2(5)$, $3(7)$ and $4(8)$. By setting up a matrix as in the video we end up finding that the optimal solution is $12$. By backtracking this we are only able to find one of the solutions $1,2,2$ and not the other solution consisting of $2,3$.

My question is, how can I combine dynamic programming with some sort of best sequence sum algorithm so that I am able to backtrack both solutions? The algorithm he proposes uses the max of the previous subproblem, however, that might not be the only solution as a combination of the current subproblem might also be feasible.

The matrix proposed in the video looks like this (rows are the possible cuts and columns are the rod length):
$$
\begin{bmatrix}
    0 & 2 & 4 & 6 & 8 & 10 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
\end{bmatrix}
$$


texts: solve non-homogeneous recurrence relation

texts:
I'm attempting to solve the recurrence relation

$$T_{(n)}=4T_{(n−1)}+(n+5) 3^n$$
with the conditions:

$n>0$
$T(0)=0$

I know the solution must be in the form $$T_{(n)}=T_h+T_p $$

but I think I'm making a mistake since when I calculate $T_h$ it gives me 0, and also don't know how to guess the $F_{(n)} = (n+5)*3^n$ int the non-homogeneous part.


texts: Which algorithm to detect errors in 32bit data with 8bit parity

texts:
I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking.

Overall, a group is likely transmitted without error, but when there is an error transmitting a group, there are probably multiple bits wrong.

If I use one parity bit per group, I have a 50% chance to detect a wrong group. But I don't need to know which group of a message is wrong, I want to check the entire message.

I want 100% chance of detecting if one group of the message is incorrect, regardless of how many bits are flipped in that group. If possible, I also want to be able to check wheather two neighboring groups have been switched.

Which algorithm should I use for error checking / How should I code the data?


texts: Find m smallest elements in an array of size n where m = n/2

texts:
So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ time.

What I was thinking of doing was use the SELECT algorithm to find the kth smallest element until $k = m$, but this way the complexity would be $n/2 \cdot O(n) = O(n^2)$.


texts: Subgraph Isomorphism checking in Multigraphs

texts:
I am considering the following problem:

Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs
Question: Find a subgraph in G which is isomorphic to H

Is there any algorithm available for checking subgraph isomorphism in Multigraphs (specifically for multiple edge types) ?
If yes, what is the complexity?


texts:
I'm working on an I/O generator program for a distributed file system. The problem I need to solve can be worded as a set of requirements:

Reproducible (i.e. given some initial condition, the algorithm must produce the exact same file system).
Concurrent (or at least concurrency-friendly). Since file system itself is distributed, the I/O generator needs to work with it from multiple computers. Friendliness in this context means that I'd like to maximize the amount of work done independently by each connected computer, each connection from that computer to the file system and each thread operating on that connection.
Parametrized (i.e. users of the I/O generator should be able to control parameters s.a. how many files are created per directory, how deeply the directories can be nested, similar for symbolic links etc.).
Supervised error generation. When generating I/O for the testing purposes it is also important to generate legitimate errors, s.a. trying to rename a non-existing file, or renaming an existing file into another existing file and so on.
Re-entrant (i.e. the state of the algorithm could be saved and the algorithm could be restarted from a given state).

Now, I am fully aware you aren't going to write a pseudocode answering to all the bullet points above... that'd be crazy if you could.  What I'm hoping for is if you could point me to white papers / research / existing solutions. I'd be also thankful if you had partial answers, s.a. how to generate a random directed graph with fanout in a given range. Or, how to generate a tree concurrently. I'm more interested in the "algorithm" part of the question rather than in solving other more technical problems. I listed the technical problems in order to maybe give a general idea of what the algorithm needs to be used for.


texts: Toda's theorem says that $PH \subset P^{PP}$.  Does this imply any relationship between $PH$ and $PP$ that does not involve oracles?  Does it imply either that $PH \subset PP$ or that $PP \subset PH$?  Is it known or conjectured whether either of those hold?


texts: If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?

texts:
I got recently confused when I noticed that there exists 2 types of polytime reductions, which lead to 2 different concepts of NP-hardness.

This is well explained in the answer to this question:
Can one show NP-hardness by Turing reductions?

While a Karp reduction is required to show whether a problem is NP-Hard or co-NP-Hard, with Cook (aka Turing) reductions one only shows that a problem is "Cook-NP-hard", in a sense which does not distinguish NP-hardness from co-NP-hardness. More precisely,

In a Karp reduction, you map each instance $I$ of Problem $A$ to an instance $f(I)$ of Problem $B$, where $f(I)$ can be computed in polytime, and such that
$$I \text{ is a Yes-instance for $A$} \iff f(I) \text{ is a Yes-instance for $B$}.$$
If $A$ is (Karp-)NP-Hard, this shows that $B$ is (Karp)-NP-Hard, too.
And if $A$ is (Karp-)co-NP-hard, this shows that $B$ is (Karp)-co-NP-Hard, too.
In a Cook-reduction, you assume that there exists a polytime procedure $F$ to solve Problem $B$, and you show that Problem $A$ could be solved by calling this procedure a polynomial number of times.
If Problem $A$ is known to be NP-hard, this shows that $B$ is (cook)-NP hard, but this does not tell us anything about the membership of $B$ in (Karp)-NP-Hard or (Karp)-co-NP-Hard.

1) In my understanding, Karp reductions only apply to decision problems, while we can show that any kind of problem is Cook-NP-Hard, is that correct?

2) If I want to prove that a problem is NP-complete, is it enough to show that this problem is Cook-NP-hard, and then to show that this problem is in NP? Similarly is a problem is Cook-NP-hard and in co-NP, does it prove that this problem is co-NP-complete?

3) A perhaps equivalent formulation of this question is as follows: While there is a distinction between the notions of Cook- and Karp-NP-Hardness, is there a real distinction between the notions of Cook- and Karp-NP-Completeness?


texts: Asymptotic runtime of recursive algorithm uisng subsitution method

texts:
I need to solve this question using the substitution method:
$T(n) = 3T(n/2)+2n$ if  $n>1$ otherwise,  $T(n) = 1$
Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$
$$a^{\log_b n} = n^{\log_b a}$$

I made some attempts at it but I haven't been able to recognize the pattern. It looks to me that it will be  $\mathcal{O}(n \log n)$ but I'm having a hard time proving it.

The substitution method: Substitute the right-hand side of the equation into any recursive instances that appear on the right-hand side:
$$T(n) = c + T(n-1)$$
$$T(n) = c + [c + T((n-1)-1)] = c + [c + T(n-2)]$$
$$T(n) = c + [c + [c + T(n-3)]]$$
$$...$$
$$T(n) = c+c+...+c + T(0)$$
$$T(n) = nc + T(0)$$
So $T(n) \in  \mathcal{O}(n)$


texts: Is there any defined programming model for 'Self-Learning' NPUs?

texts:
Qualcomm is creating a Neuromorphic Processing Unit or an NPU called zeroth.

IBM is also working on a brain inspired chip under Synapse program.

Standford's Neurogrid might be a similar example.

Neuromorphic systems are inherently based on mixed signal and analog chips. Considering a wide application of neuromorphic computers in the field of robotics, how must be the software applications defined and process in the computer. Do we need a specialized programming language for that?

How are such systems programmed?


texts: With Memoization Are Time Complexity & Space Complexity Always the Same?

texts:
I am studying Dynamic Programming using both iterative and recursive functions.  With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of the problem.

When evaluating the space complexity of the problem, I keep seeing that time O() = space O().  This is because we will have to cache all the results, but once we cache them it is O(1) to retrieve

Examples of this are

Dice Sum Problem - count the number of ways N dice can roll a certain Sum.   Time  O(num dice * target Sum)    Space  O(num dice * target Sum)     https://stackoverflow.com/questions/19719439/calculate-the-number-of-ways-to-roll-a-certain-number
Coin Change Problem  -  count number of ways to make change for a certain money amount given a list of coins.   Time  O(num coin denominations * value to make change from)    Space - same as time    https://stackoverflow.com/questions/28910971/dynamic-programming-coin-change-problems

My question is,  with Memoization, will the space & time complexity always be the same ?   If not, why not ?

Edit - Clarification

This question is regarding the Space complexity of the recursive solution.  I have solved the iterative solution using smaller space complexity before, i.e. keeping only a single row in the matrix.   However for the recursive solution, I have never seen a recursive approach where items are deleted from the memoization table.   I suppose you could combine recursion + iteration to only keep a single row in the memoization, but I have not seen an example where you start at the pure end, and only keep limited space.


texts: Minimal set of rows and columns covering all non-zero entries in matrix

texts:
Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns in $I$.

What I have tried

Create an intermediate column (between $s$ and $t$) for every column and row.

For every column, draw an edge from that column to $t$ with a capacity equal to the number of $1$s it has in it.

For every row, draw an edge from that row to $t$ with a capacity equal to the number of $1$s it has in it.

Take the cut between this intermediate column and $t$, calculate the entry with the most capacity, add that to set $I$.

For the selected row or column, remove all $1$s from that column and recalculate the network flow.

Continue to do this until the flow is $0$, i.e., all $1$s have been accounted for.

Examples
1 1 0
1 0 0
1 0 0

We would take column 1, and row 1 here.
1 1 1
0 0 0
0 0 0

We would take row 1 here.
Is there a better approach?


texts: Proof that this sorting algorithm sorts the input

texts:
I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it.

def sort (A ,i ,j ):
 if ( i +1 < j ):
  k = (j - i +1) // 3
    sort (A , i , j -k )
    sort (A , i +k , j )
    sort (A , i , j -k )
 else:
   if ( A [i] > A [j]):
     swap( A[i] , A [j])

I don't really know how to tackle this question. I know you're supposed to show that the algorithm terminates and then find some loop-invariant to show that the algorithm does what it's supposed to do. Maybe I could apply some induction here ?


texts: Reading elements of a countable set with Turing machine

texts:
I have a basic question about the behavior of a potential Turing machine.

Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$.

Suppose that we want to construct a Turing machine $M$ that, on any input, simply writes each element of $S$ on a tape in order $s_1, s_2, \ldots$. (I realize that $M$ will never halt.)

  But we can construct such an $M$ if and only if our particular bijection
  $\mathbb{N} \to S$ is computable, correct?  Or is knowing that $S$ is countable somehow enough?


texts:
I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:

  We are given K Rectangles. The dimensions of $x$-th Rectangle is ($N_x \times M_x$), where $1\leq x \leq K$.
  From each rectangle $x$ , Alice Cuts  a rect. of dimension ($P_x \times Q_x$), where $1 \leq x \leq K$ ,
  from the Top-Right Corner and trashes the cut portion.

  Initially Alice placed a robot, at the top left corner of each rectangle. He is very interested to find the number of ways, each robot can reach the bottom-right corner (target) using the following rules:

  The robot can only move 1 unit right* or the robot can only move 1 unit downward.
  The robot cannot move upward, can't move even left and can't move even diagonally.
  The robot can move on rectangle boundary.

  The number of ways can be very large. Thus, Answer = (Number of ways) mod 10^9+7.

Constraints is very large:

1<=K<=10
2<=(Nx,Mx)<=5*10^5
1<=Px<Nx
1<=Qx<Mx

The Time Limit is just 1 second.

Example:

K=1

N1=2 M1=2

P1=1 Q1=1

Answer: 5 ways

I had solved the easier version of this problem (Using Pascal triangle + Combinatorics), when no portion of rectangle is cut/removed. But I don't know how to solve the above modified problem, where a small rectangle is cut from top-right Corner of the original rectangle.


texts: Find approximate 'best' matching pairs by calculating the fewest possible weights

texts:
My specific problem is as follows:

Given two list of texts (in the order of 5 to 50 items)
Find best matching pairs with their corresponding matching score (weight)
Where each item can only be matched once with another item (from the other list)
While minimizing the calculation of the weights (Levenshtein edit distance in my case)
Every score can be between 0.0 (no match) and 1.0 (perfect match)
I may only require pairs to be matched, that meet a certain threshold

Because the edit distance is quite expensive to calculate, it is the bottleneck.
At the same time, I may be able to exclude some edges by calculating the upper limit (if they don't meet the threshold).
I guess this could be a special case of the assignment problem.
Assuming the size of list 1 is n and the size of list 2 is m.
It seems in order to apply most common algorithm, one need to calculate all of the scores between all possible pairs.
i.e. in this case it would be n * m
One approach I tried to far is:

Copy list 2 to remaining list 2
For each item 1 in list 1

Find best match meeting threshold of item 1 in list 1:

Copy remaining list 2 to temp list 2
Sort temp list 2 by approximate score between item 1 and each item in temp list 2 (in descending order)
Remove items from temp list 2 where approximate score is below threshold
For each item 2 in temp list 2:

Calculate a expensive score between item 1 and item 2
If expensive score is 1.0: Return pair between item 1 and item 2
If expensive score is meeting threshold: Save item 2 as best matching item 2

Return pair between item 1 and best matching item 2

Remove item 2 of matched pair from remaining list 2

I am thinking this can probably be improved by initially using the first found matching pair meeting the threshold.
And then later see if unmatched item 1 can be matched with an already paired item 2, whereas item 2 could also be matched with another item 1.
Do any existing algorithms address a similar problem?
Additional Note: Edit Distance Approximations
Currently I am using the following two approximations (both used by Python's difflib):

Based on the length, we can calculate the maximum score we could get (e.g. if item 1 is only half the length of item 2 then the score can't be more than 0.5)
Intersection of character counts


texts: Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

texts:
I am having difficulty with one of the exercises in the Dragon Book:

  Exercise 2.4.1(c): Construct recursive-descent parsers, starting with
  the following grammars:

  $$S \rightarrow 0S1\ |\ 01$$

Yet, for constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

  $$FIRST(0S1) = \{ 0 \} \hspace{2em}\&\hspace{2em} FIRST(01) = \{ 0 \}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?


texts: Multiple matching in Maximum Flow problem?

texts:
I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such:

Assume there are x restaurants, each with a capacity q, and y people, each of which can only eat from one restaurant. The x restaurants can only serve the people within radius r of its location. Try and find the maximum number of people that can be served by a restaurant and what restaurant each one must eat from.

My approach was to split it up into something similar to the bipartite matching problem. Have the x restaurants on one side and y people on the other. Then, I'd have a start node which connects to every restaurant using a directed edge of capacity q. Then, I'd connect all the y people with a directed edge of capacity 1 to a sink node, t. Lastly, I'd connect every restaurants to all the people within radius r using a directed edge of capacity 1.

Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could (for example, let's say we have two restaurants each with capacity 2, 4 people, and the first restaurant connects to the first three people and the second connects to the last two; then, if the path from the first restaurant to the third is augmented in the algorithm, we can only serve 3 people instead of an optimum of 4). My workaround to this is maybe augment an s-t path with the least amount of incoming edges to the person (so a situation like the above can be avoided), but this clearly slows down the efficiency significantly of the algorithm, as well as making it much more difficult to provide an argument saying it's optimal.

Is there any literature concerning problems like these, or any suggestions on how I can improve my approach? Thanks!


texts: Is deciding whether there is a non-constant solution to a functional inequality with polynomial arguments decidable, with 2 variables?

texts:
So suppose we have a functional inequality with polynomial arguments in $2$ variables, $\sum_i c_i f(p_i(x,y)) \geq 0$, where $c_i$ are say given integer constants and $p_i$ are given polynomials, say with integer coefficients. We want the inequality to hold for all $x,y \in \mathbb{R}$.

Is it a decidable problem to determine whether there are non-constant real-valued functional solutions for $f:{\mathbb R} \to {\mathbb R}$?

A recent problem of this flavor came up on math.stackexchange, which was to determine any non-constant solutions to $f(x) + f(y) \geq f(x + y) + f(xy)$. I wondered whether it was possible to determine the existence question with an algorithm rather than ad hoc analysis.


texts: Clarification on MapReduce description in textbook

texts:
I am reading through chapter 2 of of the free textbook "Mining of Massive Datasets" (http://www.mmds.org/).

On page 28 the following is stated:

"It is reasonable to create one Map task for every chunk of the input file(s), but we may wish to create fewer Reduce tasks. The reason for limiting the number of Reduce tasks is that it is necessary for each Map task to create an intermediate file for each Reduce task, if there are too many Reduce tasks the number of intermediate files explodes."

I am not sure I follow why each Map task creates an intermediate file for ALL Reduce tasks. It seems to me that the Master (being the programmatic element that delegates tasks) would delegate the output of any given Map task to a single Reduce task. Certainly multiple Map outputs can go to the same Reduce task, but it seems wasteful to store a pointer to all of the Reduce tasks. What am I missing?


texts: Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?

texts:
In this question

Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have reached a contradiction or the current boolean formula cannot be simplified anymore.

ratchet freak answered that this method doesn't work on all inputs.

I have new idea:

Instead of using karnaugh maps let's use Quine McCluskey algorithm to simplify the entire/whole boolean formula by simplifying subformulas and if you have reached a contradiction then return "unsatisfiable" as answer.

If the current boolean formula cannot be simplified anymore then return "satisfiable" as answer.

Does the new algorithm work?


texts:
This is a follow up to my earlier questions on coinduction and bisimulation.

A relation  $R \subseteq S \times S$ on the states of an LTS is a bisimulation iff $\forall (p,q)\in R,$
$$
\begin{array}{l}
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
\text{ and } \\
\text{ if } q \stackrel\alpha\rightarrow q'
   \text{ then } \exists p', \;
   p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R.
\end{array}
$$

This is a very powerful and very natural notion, after you come to appreciate it. But it's not the only notion of bisimulation. In special circumstances, such as in the context of the $\pi$-calculus, other notions such as open, branching, weak, barbed, late and early bisimulation exist, though I do not fully appreciate the differences. But for this question, I want to limit focus just two notions.

  What are late and early bisimulation and why would I use one of these notions instead of standard bisimulation?


texts:
In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement.
However if I write the truth table for implies ($\Rightarrow$) if $\alpha$ is false implies that $\beta$ is a true sentence as shown in the table below in the fourth row.

\begin{array}{cc|c}
    \alpha & \beta & \alpha\Rightarrow \beta\\
\hline
    T & T & T\\
    T & F & F\\
    F & T & T\\
    F & F & T
\end{array}

Now this should be false according to the model checking approach, since there could be models in which $\alpha$ is false but $\beta$ is true given that $\alpha$ entails $\beta$.  This is further supported by the book on artificial intelligence by Peter Norvig that states that $\alpha\vDash\beta$ iff M$(\alpha)\subseteq M(\beta)$, where $M(\alpha)$ is the set of all models where $\alpha$ is true.


texts: which arrangement gets favoured in naive shuffling for a given numbers from 1 to n according to the algorithm given?

texts:
algorithm:
a=[1,2,3.....n]
for i in (1,n+1):
    j=rand(1,n+1):
    swap(a[i],a[j])

let us say that n=3:
132
213
231
these 3 are 5 times possible
and
123
312
321
are 4 times possible....

similarly
for n=4
2143 occurs maximum number of times = 15 times
and 4231 and 4123 occurs min times i.e 8 times only....

i figured it out for n=1,2,3,4;
but i am not able to figure out the permutation which is maximum possible and minimum possible.


texts:
I am a layman in computer science.
How do the command we input in a computer, which is a software component, changes into a hardware component. For example, if I want to play a song, I will just click the song and the audio starts to emit from the speakers. So how does in general these things happen?


texts: Can the human brain be considered Turing complete?

texts:
I'm not a student in computer science, but from what I understand from the Wikipedia article on the topic, a programming language is Turing complete if it can emulate another Turing complete language's algorithm.

Now if we consider that languages like Java, C, C++ and so on are considered Turing complete, and that all algorithms implemented in programmation are by necessity first formulated in our brain, does this mean the human brain is Turing complete?

Also a human can simulate the processes going on in a processor (or we couldn't have been able to build them), but a processor can't simulate a human brain, so how is the human brain placed in terms of Turing equivalence?


texts: Computational cost of using dictionary in floating point opertations

texts:
I would like to know the computational cost of using/accessing a dictionary.
This should depend on the length of the dictionary. Say a dictionary $D$ has $n$ elements.

What would be the cost of accessing one of those elements in terms of simple floating point operations (addition, subtraction, multiplication, division)?


texts: Combinatorial optimization - is there a formal name for this problem?

texts:
I am looking for a formal name and an algorithmic approach to the following problem.

Given is a set of services each coming with a price:

{s1, 300}
{s2, 400}
{s3, 800}

Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:

{p1, {s1, s2}, 600}
{p2, {s2, s3}, 1050}
{p3, {s1, s3}, 950}
{p4, {s1, s2, s3}, 1250}

Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.

For example:
Services to order :{s1,s2,s1,s3,s2,s3,s1}

possible Solutions:

{p4, p4, s1} : 2800
{p1, p1, p3, s3} : 2950

In this case the first solution would be the winner.

An exhaustive approach will quickly explode because it is O(n!) or even worse.

What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?


texts: How would I build a parser generator for a context free grammar using Pushdown Automata?

texts:
I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc.

I am at the point where I have lexer generation down pat. That is, I have defined a way to specify token definitions from regexes and split an input string into tokens based on those definitions.

Now I am to the point of building a parser by specifying BNF productions for a grammar. Based on my initial research, I need to convert the grammar to a pushdown automaton. What I've read has told me that I need to do so in 3 steps:

Convert the grammar to Chomsky Normal Form (all productions have either a single terminal or two non-terminals).
Convert from Chomsky Normal Form to Greibach Normal Form (all productions have either a single terminal or a terminal followed by a sequence of non-terminals).
Convert from Greibach Normal Form to a Pushdown Automaton.

There are clear enough algorithms for doing these three steps. However, I am not sure how to go about the actual running of the PDA once I have it. My problem is not with how a PDA works, but with ambiguity.

Basically, I have the following questions:

Should I account for the fact that a grammar may be ambiguous, or is it a reasonable constraint on the grammar writer to enforce that the grammar be unambiguous?
If I allow ambiguous grammars, will this add significant overhead to the process of running the PDA? Is there a performant way of running a non-deterministic PDA?
While on the topic of determinism, can an ambiguous grammar generate a deterministic PDA?
Will an unambiguous grammar always generate a deterministic PDA?
I know that determining whether a grammar is ambiguous or not is undecidable, but is there a heuristic that works in most cases?

Basically, in my work on the lexer portion of this parser, I was able to transform non-deterministic finite automata to deterministic finite automata, which allowed me to run the lexer in basically linear time, but I understand that this is not possible to do with pushdown automata, so I'm curious what implications this has on the parsing process, and how I might go about doing this.