texts: How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

texts:
The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the lists of document ids two for word1 and word2, and find the intersection in linear time (similar to merge in merge sort).

But how would the search engine efficiently retrieve documents in some specified order , like page rank for example? Since the inverse indices for each word are already sorted by document id (to enable the merging described above), there seems to be no way to sort them also by page rank. (For instance, for "word1" the index might have ids :  5, 11, 19 where these documents have page ranks 3, 1, 2 respectively).

Retrieving the documents by document id first and then sorting by page rank at query time can be impractical if the number of documents to sort is large (say, millions), and especially if the user just wants the top page or two.


texts: What are the uses of Markov Chains in CS?

texts: We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?


texts: What is meant by problems not in NP but in NP hard?

texts:
If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too.

Why doesn't it then mean that all NP-Hard are NP (i.e. NPC)?

But, if there is something with exponential verification i.e. outside NP and since it can be reduced to an NPC problem in polynomial time which means it is also verifiable in polynomial time (As we assumed above). Isn't it? Which might say that all NP-hard is NP-complete...

I'm unable to grasp what is NP-hard but not NPC here? What is wrong in this reasoning?

Are there any problems which are outside Recursive Enumerable Languages in NP-Hard? Is that even possible?


texts: Comments on "Which combinatorial problem is similar to this problem?"

texts:
Regarding the post Which combinatorial problem is similar to this problem?, it is quite hard to believe that, in the absence of information on the cost function, there is no algorithm better than exhaustive search to tackle this apparently easy-to-understand problem. I surfed the Internet and found something called the Weighted Constraint Satisfaction Problem, and I wonder whether this can be of any use in this case.
Any advise would be much appreciated.
EDIT: The problem I have at hand is a regression problem where each of $p$ inputs, $x_1, x_2, x_3, \cdots, x_p$, needs to undergo a variable transformation using one of $q$ functions from a set of available functions $F = \{ f_1, f_2, f_3, \cdots, f_q \}$. The cost function is the Mean Square Error (MSE) defined as $MSE = \frac{1}{n} \sum_{k=1}^n (y_k - \hat{y}_k)^2$, where $n$ is the number of samples and for each $k$, $y_k$ is an experimental value and $\hat{y}_k$ is the predicted value computed by some method (e.g., as from a Gaussian Process Regression) using the transformations ($f_j(x_i)$) as input variables. This method must be also selected from a set $M = \{ M_1, M_2, M_3, \cdots, M_m \}$ of widely different available methods. The objective is to decide which function transforms each one of the $p$ inputs and which method to use such that $MSE$ is minimum. There are no constraints whatsoever. I think in this case there is no structure to take advantage of since the cost function changes form depending on the choice of the method.


texts:
a^2n b^(2n+1) is a regular language.
I am not able to decompose it in xyz so that I can pump any power of y as per pumping lemma. Please help me out.


texts: Are isomorphic (untyped) lambda expressions semantically equivalent?

texts:
"Isomorphic" is defined as having the same shape of syntax trees and the same bindings of variables. However, the variable names might be completely different. In other words, it is to say that we have a graph isomorphism between the two expressions (the graph being the syntax tree with variable linking included as edges).
The intuition behind this is that assuming we are given the isomorphism, it is always possible to rename the variables and obtain the other expression.


texts: Minimal positive difference of a mulitset of real numbers

texts:
Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut,  I'd like to ask the following questions:

Given a multiset of real numbers $B$, how hard is it to compute the minimal positive difference $\delta_\min$
$$\delta(B_1,B_2)=\left|\sum_{b\in B_1}b-\sum_{b\in B_2}b\right|$$
taken over all partitions $B_1\cup B_2=B$ of $B$ such that  $\bf\delta(B_1,B_2)>0$?
How hard is it to find a lower bound $\delta_- >0$ for $\delta_\min$?

Observe that (2) is easy for rational numbers, as you can compute the least common denominator $d$ and every positive difference is a multiple of $\frac{1}{d}$.

Assume that all $b\in B$ are from some subset (closed under addition and symmetric difference) of $\mathbb{R}$ for which we do have a representation by finite strings and all basic operations are performable in at most polynomial time.


texts: Estimating size of state space search problem

texts:
Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?


texts: Rules regarding Chomsky Normal Form (CNF) grammars

texts:
I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:

Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?
Can I use a single variable (a non-terminal) twice on the right-hand side of a single rule?

For instance, is the following grammar properly in Chomsky Normal Form?  Is it OK that I have two rules with $S$ on the left-hand side?  Is it OK that I have $X$ twice on the right-hand side of the second rule?

$$S_0 \to S$$
$$S \to XX$$
$$S \to XZ$$
$$\vdots$$


texts:
I have labeled examples coming in on the fly, thus I need to create a classifier from sequential data instead of a static example set. Incoming data is fully labeled, there are no unlabeled examples. Each incoming example has a number of features.

E.g. let X by an incoming example with 3 features

X := (day = sunday, weather = sunny, season = summer, label = go to the beach)

I want to incrementally train a classifier such that whenever I see the next occurance of (sunday, sunny, summer) I want the classifier to suggest going to the beach.

Due to memory restrictions I am unable to keep the entire set of training examples.

Can you point me to adequate online/incremental learning algorithms for such a particular problem?


texts: Representing Integral domains in computer memory?

texts:
Earlier I wrote this question about an algorithm computed on an integral domain.  However as commented I didn't suggest any particular ways of storing an integral domain in computer memory.  I set out to do this but found it a particularly difficult task.

It is in fact impossible to store all the integral domains in memory because the fields are uncountable1 and are a subset of the integral domains.  However I am not concerned with fields because they don't have any primes anyway.

How might one represent non-field integral domains in computer memory?  Is the set of all non-field integral domains countable?  If it is uncountable is there any useful subset of them that can be represented in computer memory?

1: The rationals are a field.  Every polynomial extension of a field is also a field.  Thus the number of polynomial field extensions of $\mathbb{Q}$ is the powerset of the irreducible polynomials on $\mathbb{Q}$ which is uncountable.


texts: Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$

texts: I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here looking for a hint. I don't want a full answer, but would really appreciate a few words to point me in the right direction. This is not a homework exercise.


texts: Get the maximum sum of n items below a threshold

texts:
Consider a modified Knapsack Problem where:

The number of items to be included is fixed.
The value of each item is equal to its weight.

Therefore, given a set of numbers, a threshold and the number of items to use (n), I want to get the subset of n numbers that produces the highest sum below the given threshold.
Having already asked this question a year ago and not being able to fully understand the given answers, this time I'm asking for something a little different. The dynamic programming solution to the 0-1 Knapsack Problem only became clear to me when I got to see the recursive approach first:
def knapsack(w, ws, vs, n):
    # if num of items or weight left is 0 value is 0
    if n == 0 or w == 0:
        return 0
    # if item doesn't fit return best val without item
    if ws[n - 1] > w:
        return knapsack(w, ws, vs, n - 1)
    # otherwise, return max of best vals with and without item
    include = knapsack(w - ws[n - 1], vs, w, n - 1) + v[n - 1]
    not_include = knapsack(w, vs, w, n - 1)
    return max(include, not_include)

So, if I were to solve my problem using a recursive approach (for educational purposes), what would that look like? And optionally, how would it be translated to a dynamic programming solution?


texts: Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?

texts: One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in B\}$ so $C=A’ \cup B’$ and he define the function $f(w)=0w$ if $w \in A$ and and $f(w)=1w$ otherwise. I suspect this function is turing-computable. Suppose $A$ be $\overline{HP}$ which is not RE. How we can decide if $w \in A$ ? Even i ask myself can we realy prove that such a mapp-reduction always exist ?


texts: Does a language have a regular expression if and only if it is regular?

texts: I know that if a language has a regular expression it is regular, is the other way also true?


texts: Time Complexity of a Union Find algorithm

texts:
I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows:
input: data: array of sorted n integers
input: n: size of data
input: c:a positive integer between 1 and n-1

delta = Array(n-1)
map=HashMap()

for I =1 to n-1 do:
delta[i] = data[i+1] - data[i]
map.Insert(delta[I],i)
end

heap=MinHeap(delta)
uf = UnionFind(n)

for I =1 to c do:
t=heap.deleteMin()
x=map.Search()
uf.Union(x,x+1)
end
return uf

To my knowledge
the first for loop runs in O(n) time, building the heap takes O(n), and the second for loop would run at O(n^2) times dominating the other complexities.


texts: What does it mean that a core supports 2 threads?

texts:
I understand that a process may have multiple threads, and that a processor may have multiple cores to run processes in parallel.

But I can't understand how a core may allow multiple threads, what does it change from a core with one thread support?


texts: What's the difference between user registers and kernel registers?

texts:
I am reading Operating Systems: Three Easy Pieces, but I can't fully understand the following paragraph. It's from the 6th chapter of the book. I think it's self-contained, so I quote here.

Note that there are two types of register saves/restores that happen during this protocol (context switch). The first is when the timer interrupt occurs; in this case, the user registers of the running process are implicitly saved by the hardware, using the kernel stack of that process. The second is when the OS decides to switch from A to B; in this case, the kernel registers are explicitly saved by the software (i.e., the OS), but this time into memory in the process structure of the process. The latter action moves the system from running as if it just trapped into the kernel from A to as if it just trapped into the kernel from B.

I understand that OS need to save some registers to do context switch, but what does it mean by saying user registers and kernel registers? What are the differences between them?
Thanks!


texts: What does "satisfactory definition" mean?

texts:
I am reading the book Artificial Intelligence (A modern approach) by Stuart Russell and Peter Norvig. While reading the book, I saw the below sentence in the book.

The Turing Test, proposed by Alan Turing (1950), was designed to provide a satisfactory operational definition of intelligence.

Now the question is, what does the writer mean by saying satisfactory definition?
Does it have a special mathematical meaning (like as we say in some problems: f(x) satisfies some conditions)? or does the satisfactory adjective just mean good enough (as stated in Longman dictionary)?


texts: In a set of sentences, how could I determine the fewest sentences that contains all characters?

texts:
So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.
So it would look like:
Easy
1. APQ
2. DL
3. RTE

Intermediate
1. FSMG
2. NDA
3. LOXCW

Advanced
1. GEW
2. ZAY
3. IVK

My question is: How could I go about finding the smallest set of strings that contain all the characters?
In this example, I would not need Easy 2 or Advanced 1 because their characters appear elsewhere in the set and they don't offer any characters not found elsewhere. Is there a type of algorithm best suited for this?
I can't just do a map lookup to see if I have come across a character before because I am looking for the smallest set. Also, I want to make sure, for instance, if I skip Easy 2 that I don't skip Intermediate 2 and Intermediate 3 since that's where I found the D and L that allowed me to skip Easy 2.
As for my real-world application, I have 4135 strings (about 100-200 characters long) split into 6 levels of difficulty, and these strings are sentences in Chinese. These strings have about 4000 unique characters combined. I'm basically looking for which sentences are worth learning and discard the ones that don't offer much/any new characters. Difficulty is mostly irrelevant, but I may run the algorithm within difficulties, then across the board.
Any help would be greatly appreciated.


texts:
If A and B are Turing recognizable, is A - B Turing recognizable?

I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability.   For example, if A is context free and B is a regular language A - B would result in a language that is sill Turing recognizable.

However, does this become a question about emptiness?  Two Turing recognizable languages equal to each other leave an empty set.  Is the empty set Turing recognizable?  I would still say yes.

Not sure if I'm thinking about this correctly...


texts: Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances

texts:
We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state.
Show that there exists an algorithm, that converts such NFA to DFA in polynomial time. We don't need that algorithm to work if given automata is not such a NFA.

I think we need to construct DFA with $2^{10}$ states, such that every state would correspond to some run in the NFA - but im not sure about the details.

Any ideas?


texts: Can current quantum computers decide languages that Turing Machines cannot?

texts:
I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to reductions got me thinking about all the Quantum Computer craze.

As such my question is as follows

  Does there exist some language L that is not decidable by a Turing Machine, but is decidable by a quantum computer?

My hunch is no, as from what I understand about Quantum Computers, you can simulate them (albeit slower) using a Turing Machine. However my knowledge of Quantum Computing is limited to a 1.5 hour lecture from Microsoft on YouTube, and I would assume there was a lot more in the way of recent developments that I am not knowledgeable enough to understand


texts:
I am looking into Hindler-Milney type system and I am trying to add support for
the pair type. In Pierces book, he introduces special language constructs for creation of pairs and getting their elements.

What I am interested in is the following. What if I don't introduce new constructs, yet use special functions with this signatures:

$$pair: \alpha \rightarrow \beta \rightarrow \alpha \times \beta $$

$$proj1: \alpha \times \beta \rightarrow \alpha$$

$$proj2: \alpha \times \beta \rightarrow \beta $$

If I use Wand's algorithm for type inference, after collecting all equations between type expressions and solving it a bit, I get the following equation
for $((pair\; 2\;) 4): \tau$:

$$\alpha \rightarrow \beta \rightarrow \alpha \times \beta = Int \rightarrow Int \rightarrow \tau$$

It seems to me that the unification algorithm should infer at the end that $\tau = Int \times Int$. Is this true?

Do I really need a special construct for pairs? Is there something conceptually wrong with this? Probably their is, so it would be great if someone could point me out.

Note that I would also prefer using special constructs as that way looks cleaner and easier to program with; this question is just for my complete understanding of the subject.


texts: Is the number of NP-complete problems finite?

texts:
It should be straight forward to show that there are infinitely many NP-hard problems:

Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and yields a yes answer iff a vertex $x \in V$ exists which, when removed from $V$ yields a new graph $G'=(V\backslash\{x\}, \{(u,v) \in E\,|\, u \neq x \land v\neq x\}$ which is a positive instance of $3COL$.

$R1V3COL$ can indeed be reduced to 3-colorability problem (which is proven to be NP-complete) by (as an example reduction) simply removing a vertex from $G$ and testing if $G$ is 3-colorable. If $G$ is not 3-colorable remove another vertex from $G$ and test it. Repeat until there are no vertices left for testing.

Therefore we know $R1V3COL$ is an NP-hard problem.

We can now reduce $R2V3COL$ to a $R1V3COL$ problem (by a similar concept as shown above for $R1V3COL$ to $3COL$ to show that $R2V3COL$ is in NP-hard and so on for every Remove n Vertices 3-COL problem. In other words we can always reduce $R(n)V3COL$ to $R(n-1)V3COL$. Therefore we know that there have to be infinitely many NP-hard problems and we are done.

Now to my Lemma:
I cannot think of a simple proof to show that a certain problem with infinitely many variations (like $R(n)V3COL$) is also in NP to prove NP-completeness and therefore prove that infinitely many problems are in the subclass NP-complete.


texts:
first post on this amazing community, always been a lurker, so I'm sry if my formatting sucks. I'm having a really hard time trying to solve this problem:

Given m graphs each composed of the same n vertexes, find all the pairs of equal graphs(not isomorphic).
OBLIGATION: it is possible to elaborate an algorith that does better than checking every pair of graphs.

This algorithm has to be written in C, so it must be pretty "raw". My initial idea is to create an array of Graps and for each graph I store an array containing the Degrees of my vertex, if two graphs have different degree's array then I reject the pair of graph. This method kinda creams off some of the pair but for the worst case it's bad, because if I have m/m equal graphs I'll have to check every pair anyways.
I have no clue on how to solve this problem, any suggestion is highly appreciated.


texts: If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language?

texts:
If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free?

I am aware that if $L_1$ and $L_2$ are context free languages then the language $L_1 \cap L_2$ is also context free but cannot quite connect the dots. If someone could help out that would be great.


texts: Finding topologically sorted connected components in directed acyclic graph

texts:
I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am finding it surprisingly hard.

Assuming a directed acyclic graph, is it possible to simultaneously find the list of connected components while at the same time topologically sorting the nodes in each of the components?

To clarify, the output would be a list of components, where each component is a topological order of the nodes contained in that component.

Bonus points if the list of connected components is sorted following the insertion order of nodes in the graph (i.e. the first connected component will contain the first node ever inserted in the graph, regardless of global topological order; etc for subsequent components).


texts: Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

texts:
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.

Any ideas along these lines would be much appreciated.

Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value


texts: Computing a boolean function with a small formula

texts:
Suppose that $x = (x_1,\ldots,x_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose  $y = (y_1,\ldots,y_m)$ is a binary vector and that $F(x,y)$ is a binary formula  of size $k.$ Here by size  I mean the number of leaves in $F.$

Suppose I have vectors $S = \{s_1,\ldots,s_n\}$ such that for any $x \in \{0,1\}^n$ there is a $s \in S$ such that we have $$ F(x,s) = f(x).$$

I need to prove that in this case I can express $f(x)$ as a boolean formula of size $O(n\cdot k).$

What would be the idea about this?

Since for every input $x$ we have an $s \in S$ one could encode the specific $s$ for every one of the $2^n$ possible inputs but this would give a too large formula.

Edit. The original text  as it appears in the book "Extremal combinatorics with applications to computer science 2ed."


texts:
I work at a company and i got to a seminar we're they told us to solve this problem below in the picture
Is there an algorithm that can help me solve this question.
I thought about a randomized algorithm after that i get stuck?


texts: How to solve linear equation with binary tree

texts:
I'm working on a school project that takes in a simple linear equation and has to return the value of $x$. The code I have transforms $x + 3 = 3x - 2$ into a binary tree format like so:

        =
      /   \
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

With the expression in this format could someone please explain how can I obtain the value of $x$.
Any help is appreciated - if you have an alternative method that may make it easier I'd love to hear it.


texts: Hyper parameter and complexity in $K$ nearest neighbors

texts:
I'm wondering if choosing K in the Nearest Neighbors Classifier can be stated as model selection, since the computational complexity is getting higher, the higher K is.

My understanding is: since the complexity increases it means, that K is a hyper parameter.

Am I getting the concept of hyper parameters correctly?


texts: What does one mean by addressing capability of a microprocessor?

texts: I read in a book that the Intel 80286 microprocessor has an addressing capability of 16 MB. Does this mean it can process 16 MB of data at a time? Please explain what is actually meant by addressing capability.


texts: Ternary decision tree for the lower bound of comparison sort with 3-way comparisons

texts:
All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook)

Now what if each comparison yields strictly 3 outcomes, i.e. <, =, >? (the input array is allowed to contain repeated elements)

The bound is probably still Ω(nlgn), but I'm not sure how one would draw the (not necessarily full) ternary decision tree (still with unique leaf nodes); this kind of tree is mentioned in the proof of the water jug problem.


texts:
I was reading an article on Find the smallest binary digit multiple of given number. The problem is - We are given a decimal number N, we need to find the smallest multiple of N which is binary digit number.

There is an optimization done i.e. if a string with same mod value is previously occurred we won’t push this new string into our queue. The explanation given is-

Let x and y be strings, which gives same modular value with n. Let x be the smaller one. let z be another string which when appended to y gives us a number divisible by N. If so, then we can also append this string to x, which is smaller than y, and still get a number divisible by n. So we can safely ignore y, as the smallest result will be obtained via x only.

How can we say that, we can also append this string to x, which is smaller than y, and still get a number divisible by n ?

And how can we say that the smallest result will be obtained via x only?


texts: How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

texts:
I see many algorithmic problems that always reduce to something a long the lines of:

You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ time.

Obviously the $O(n^2)$ time solution is to consider all pairs, however, is there any way we can maximize the expression in $O(n)$ without knowing something else about properties of $h$?

One idea I thought of is to fix $j$, then we need to find $i^*$ from $1$ to $j-1$ that is equal to $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ or $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ and since $j$ is fixed, then we need $\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$.

However, I see no way of getting rid of the $j$ dependent terms inside. Any help?


texts: frequency of elements in array in $\mathcal{O}(n) ? $

texts:
I have an array of 64-bit integers of length $n$ and I want to find the frequency of each element in $\mathcal{O}(n)$? is that possible?
my idea was to use a hashmap but it seems to me that the adversary would always be able to find a pathological case.


texts: Clarification in model precision term for Gaussian Processes

texts:
Following the blog post, where the dropout in the deep learning models has been approximated to a Gaussian process. Research paper and its appendix.

Looking at the suggestion of the author from the blog post that the variance in the prediction is given by the following piece of code. I found it counterintuitive as the predictive variance is directly proportional to the number of observations. tau -- which author refers as model precision.

I have tried to go through the research paper but it seems I don't have enough skills to comprehend the reasoning behind it.

Shouldn't the variance decrease with the more observations?

probs = []
for _ in xrange(T):
    probs += [model.output_probs(input_x)]
predictive_mean = numpy.mean(prob, axis=0)
predictive_variance = numpy.var(prob, axis=0)
tau = l**2 * (1 - model.p) / (2 * N * model.weight_decay)
predictive_variance += tau**-1


texts:
Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's complement arithmetic, which performs additions modulo $2^w$ with wraparound semantics. That's easy — but the sum may overflow the register size, and if it does, the result will be wrong.

If the sum doesn't overflow, I want to compute it, and to verify that there is no overflow, as fast as possible. If the sum overflows, I only want to know that it does, I don't care about any value.

Naively adding numbers in order doesn't work, because a partial sum may overflow. For example, with 8-bit registers, $(120, 120, -115)$ is valid and has a sum of $125$, even though the partial sum $120+120$ overflows the register range $[-128,127]$.

Obviously I could use a bigger register as an accumulator, but let's assume the interesting case where I'm already using the biggest possible register size.

There is a well-known technique to add numbers with the opposite sign as the current partial sum. This technique avoids overflows at every step, at the cost of not being cache-friendly and not taking much advantage of branch prediction and speculative execution.

Is there a faster technique that perhaps takes advantage of the permission to overflow partial sums, and is faster on a typical machine with an overflow flag, a cache, a branch predictor and speculative execution and loads?

(This is a follow-up to Overflow safe summation)


texts: Asymptotics of a function that decreases as n increases

texts:
A homework assignment asks me to state the complexity in Big-O notation of the function
$$f(n) =  7n – 3n \log n + 100000 $$

I graphed this function and decreases all the way down to zero nearly its entire lifespan.
Therefore I concluded that the complexity is bounded by a constant and has the complexity $O(1)$.

Is this correct?

Also out of curiosity, what is the Big-Omega of this function is? The best it could ever run is also O(1).
What about Big-Theta? I'm having trouble getting my head around these.


texts: Computational Complexity of Exponential Expression Divisibility?

texts:
Garey and Johnson mentions the problem of 'Exponential Expression Divisibility" as "Not known to be in NP or co-NP, but solvable in pseudo-polynomial time using standard GCD Algorithms".

Pseudo-polynomial compared-to/in-terms of what value/variable? Can someone help with the explicit complexity measure of the problem?


texts: Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

texts:
Are there languages $L_1$, $L_2$ such that such that
$$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$
and two other languages such that
$$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$
And if so, what are they? How can i go about finding these?


texts: How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)

texts:
I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three main multithreading techniques:

Cooperative/Coarse-Grained/Block  Multithreading
Preemptive/Fine grained/Interleaved Multithreading
Simultaneous Multithreading

My question:  Under what circumstance is each method of multithreading considered to be the optimal one to use? I assume one or the other will perform better with a higher number of cores, repetitive instructions, low/high remote access latencies or low/high remote cache miss rates, etc.

This means that if I were to create a simple program in Java with two versions, one using multithreading and the other not, I want to be able to see the largest possible processing time difference between the two versions.

P.S Can they all even be implemented at the user level (i.e. coded into commercial software)?


texts: Can polymorphism be simulated by lazy type operators?

texts:
In the definition of lambda cubes, type polymorphism is distinguished from type operators/constructors.

I have the nagging feeling that type polymorphism can be constructed through type operators using lazyness. This may be extremely convoluted but I always felt polymorphic types where just functioning "as if" waiting for a concrete type.

Here's an example...

Take (+1)::Num a => a -> a, (+1) pi is Floating whilst (+1) 1.1 is Fractional.

This level of polymorphism above can be constructed through the use of a "universal delayed type constructor" F and a type operator G designed for (+1). Where,

F :: X -> f -> a -> X a

I've tried to upper case type signatures to represent types and lower case for terms.

And where,
G :: a -> B
G ( _ ::Integral) = Integral
G ( _ ::Fractional) = Fractional
G ( _ ::Floating) = Floating

Note that G's implementation is partial, I've not actually said how (+1)::Floating -> Floating  is implemented differently from (+1)::Integral -> Integral .

Therefore, F G (+1) achieves the same as (+1) with polymorphism above. This is a simple example, I may need to go a second level (i.e. operators on type operators) to simulate polymorphic type operators.

So, is true that polymorphism can be simulated by type operators? I'm probably wrong but I don't understand why. Can anyone help?

[EDIT]

My question was ill-posed. I didn't have the concept quite formed in my mind. It actually was triggered by Pierce's comment when a polymorphic function meets a type argument, the type is actually substituted into the body of the function. Based on that, polymorphic functions felt very close to type operators: type operators work on types, polymorphic functions crystalize into proper functions when given a type. I felt that polymorphic types could be replaced by some kind of (recursive) type operator that "fetched" the proper type. I forgot however that polymorphic types have kind $*$ whilst type operators have kind $* \rightarrow *$. So that's at least one difference.


texts: How to get best path from a set of path using Q-Learning?

texts:
I have 10 data sets (lat and long) of the same path. I started from point A and stopped in point B and did this 10 times for a single route to get the data. While collecting the data, there were some fixed obstacles and some random obstacles. So, I avoided them. Doing this 10 times created a fixed curve in every dataset and some other ghost curves (as I avoided human and other obstacles). I want to remove these ghost curves and keep the actual curves in every dataset. Then I want to select one optimal path from these 10 paths. So can anyone suggest me what machine learning algorithm would be best fit for this work and if it can be solved using q-learning?

1 is actual obstacles. 2 is ghost obstacle.

I want like this.


texts: what is the relationship between entropy and variance?

texts:
Consider a simple Bernoulli variable X
X = 1 with probability p
X = 0 with probability (1-p)

The variance is simply p(1-p). The entropy is -p*ln(p)-(1-p)*ln(1-p) Both are measures of uncertainty. What is the advantage of entropy then?
Thanks!


texts: Complexity Values for Specific Code/Functions

texts:
(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive square) root, and the floor function. We write a (Sage) program that involves a "for-loop" execution for $f(x)$ values ranging from 1 to $n$ with $n$ arbitrarily large. Is the time complexity of the program linear? I'm assuming the basic operations run in, essentially, $\mathcal{O}(1)$ time (even for large numbers). So, eight (constant-time) operations for each element within the for-loop is $8n$, which is $\mathcal{O}(n)$.
(2) Same as above, except we add a pair of "if" conditions to each execution within the loop. So, for each element (1 to $n$), we compute $f(x)$ and request 'if (f(x)).is_integer()==1', then 'if (f(x))%2==0', print(x); break'. If either conditional fails, simply continue the for-loop sequence. Wouldn't this also be $\mathcal{O}(n)$ complexity? Worst case, we have ten (constant-time) operations for the entire loop (i.e., eight mathematical operations and two conditionals per loop element): $10n\rightarrow\mathcal{O}(n)$?


texts: What is the difference between quantum TM and nondetermistic TM?

texts:
I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do not touch on that. Are these two models one and the same?

If no,

What are the differences between quantum TM and NDTM?
Is there any computation which a NDTM would do quicker than Quantum TM?
If this is the case then quantum TM is a DTM, then why is there so much fuzz about this technology, we already have so many DTM. Why to design a new DTM in the end?


texts: Show that problem of Shortest-Path in digraph is in NL

texts:
Look at solution to exercise 2, please.
Exercise and solution is derieved from:
https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

  $$ShortestPath = \{(G, k, s, t)| \text{the shortest path from $s$ to
> $t$ in $G$ has length $k$}\}$$ (a) Prove that $ShortestPath$ is in
  $NL$.

  (a) Solution:   We construct a $NL$-machine for ShortestPath as
  follows: on input $\langle G, k, s, t\rangle$, first compute $r_{k−1}$
  (the number of vertices reachable from $s$ in at most $k − 1$ steps).
  Then, on input $\langle G = (V, E), k, s, t\rangle$ and $r_{k−1}$ on
  the work tape,

d ← 0
flag ← FALSE
for all w ∈ V do
p ← s
for i ← 1 to k − 1 do
non-deterministically pick a neighbor q of p
if p = w then
d ← d + 1
if w = t reject
if w is a neighbor of t then
flag ← TRUE
if d < r_{k−1} reject
if flag then accept else reject

I don't know why it is so complex.
Tell me please, why direct and simple algorithm is not ok:
Check if there exists path from $s$ to $t$ of length $1$
Check if there exists path from $s$ to $t$ of length $2$
...
Check if there exists path from $s$ to $t$ of length $k-1$
If there exists path of length $\le k -1 $ then reject. Else check if exists length of $k$ and accept if exists.

In other words we check one be one each length. We can check existence of path thanks to non-determinism. We launch number of visited nodes and check if we end up in $t$


texts: Efficiently count frequency of n-grams at start of words

texts:
I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as:

aaaaa
aaaab
aaaac
aaaad
.....

and I have a txt file (organized in rows) with all English words. I have to find how much time every 5-gram is at the beginning of a word. I'm using this code:

def frequency(five-grams, dict):
    result = {}

    for gram in five-grams:
        freq = 0
        for word in dict:
            if word.startswith(gram):
               freq = freq + 1

        result[gram] = freq

    return result

However this method takes too long (after hours the algorithm is still running). Is there a more efficient and faster method?


texts: What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

texts:
What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems remain feasible? Can one tell in advance?

I am particularly interested in scheduling problems and what to know as to how the uncertainty in information (e.g. processing times of jobs) affects the difficulty of the problems. I believe the problem becomes more difficult when information is uncertain. Is it true?


texts: Finding a maximal independent set in parallel

texts:
On a graph $G(V,E)$, we do the following process:

Initially, all nodes in $V$ are uncolored.
While there are uncolored nodes in $V$, each uncolored node does the following:

Selects a random real number and sends it to all its neighbours;
Compares its number to the number of its neighbours; if its own number is strictly smallest, then the neighbour paints itself red and notifies all its neighbours.
If a neighbour became red, then this node paints itself black.

For example:

Suppose the graph is a path: a-b-c-d-e.
Suppose the numbers in the first step are: 1-2-0-3-4.
Nodes a and c are painted red; nodes b and d are painted black.
In the second step, only node e remains uncolored; it is trivially minimal so it paints itself red.

MY QUESTION IS: what is the average number of steps that this process takes before all nodes are colored?

My current calculation leads me to an $O(1)$ estimate, which seems too good to be true. Here is the calculation:

Consider a node $v$ with $d$ neighbours. The probability that $v$ will be the smallest among its neighbours is $1/(d+1)$. If this happens, then $v$ and all its neighbours will be colored. So the expected number of vertices colored each step is $(d+1)/(d+1)=1$ per node. Hence the total expected number of vertices colored each step is $O(n)$, so in $O(1)$ time all nodes will be colored.

If this analysis is wrong (which is probably the case), then what is the actual number of steps?

EDIT: As noted by @JukkaSuomela, the algorithm described above is due to Metivier et al, 2011 and is explained and analyzed in these lecture notes. They prove that the run time is $O(\log n)$.

But, I am still not convinced that this analysis is tight. In all graphs I checked, it seems that the algorithm completes in $O(1)$ expected time.

My question is now: what is a worst-case graph in which this algorithm indeed requires $O(\log n)$ steps in average?


texts: What is the usage of a decision problem for an optimization problem like the longest path problem?

texts:
I just read this definition for the longest path problem:

  LONGEST PATH
  Input: A graph $G=(V,E)$, an integer $k$.
  Question: Is there a path with at least $k$ vertices in $G$

This seems a decision problem and a certificate can be verified easily. But, what is the usage of such a problem? Isn't the main concern finding the longest path in the graph? I guess that would be an optimization problem, and verifying a given certificate can't be done in polynomial time, so that is not $NP$. right?

If yes, then what is the usage of the decision problem (which is $NP$) and what is its relation to the main problem?

My question is different from  "NP-complete" optimization problems because I also asked about the relationship between a decision problem and a relevant optimization problem, and how a decision problem may help us in solving the optimization problem, and basically what is their usage in such cases.


texts: What is time stamp in asynchronous transmission?

texts:
I am new to CS, and learning asynchronous transmission.

  Asynchronous Transmission typically also uses SYNC word/bits to
  provide occasional time stamp for receiver to synchronise its clock to
  the transmitter clock.

Could anyone explain more specifically how time stamp synchronizes the transmitter and receiver clock to reduce clock skew between them (such as the process or mechanism used)?

Thank you.


texts: Minimum-average-cost subtree that is not necessarily spanning

texts:
I'm looking for an efficient algorithm for the following problem:

Input: a rooted tree (undirected) with a cost on each edge.  It could be considered directed away from the root (or towards the root).

Output: a subtree from the root that has the minimum average cost per edge.

There are some results for minimum average-cost spanning trees, but in this case the output is not necessarily spanning.

In the tree below, where A is the root of the tree:

The subgraph containing nodes A and B has average cost mean(6) = 6
We can improve on the average cost by including node C to get mean(6, 5) = 5.5.
The optimal subgraph includes nodes A, B, D and E, but not C, to get mean(6, 7, 1) = 4.67

A greedy algorithm would be a depth-first search that appends edges that lower the mean.  But such an algorithm would miss the optimal subgraph, because it wouldn't append the edge to node D with cost 7.


texts: A Formal Grammar: defining English counting numbers?

texts:
I would like to define a grammar that produces and recognizes the counting numbers of the English language.  I created the production rules below based on the assumption this is context-free, but I am not entirely sure thats the case.  Is this a context-free or context-sensitive grammar?  If context-free, do my production rules look ok?
For example:
"one hundred twenty two" $\in \Sigma^*$ which has the semantic meaning $b^2+2b^1+2b^0$
"one thousand two hundred thirty three" $\in \Sigma^*$, $b^3+2b^2+3b^1+3b^0$
I understand context-free production rules are $N \rightarrow \alpha$ and context-sensitive $\alpha N \beta \rightarrow \alpha \gamma \beta$, where $N$ is a non-terminal and $\alpha,\gamma$ are terminals or non-terminals.
I considered CFG production rules in Backus Naur Form as follows, but am unsure if it's correct:
<S> := "zero" | <b3> | <thou> | <mill> | <bill> | ""
<num99> := <ones> | <teens> | <tens> | <tens> <ones>
<num99opt> := <num99> | ""
<b3> := <ones> "hundred" <num99opt> | <num99>
<b3op> := <b3> | ""
<thou> := <b3> "thousand" <b3op>
<thouop> := <thou> | <b3op>
<mill> := <b3> "million" <thouop>
<millop>:= <mill> | <thouop>
<bill> := <b3> "billion" <millop>
<tens> := "twenty" | "thirty" | ... | "ninety"
<teens> := "ten" | "eleven" | ... | "nineteen"
<ones> := "one" | "two" | ... | "nine"


texts: Origin of Mersenne Twister tempering parameter 'd'?

texts:
Short version: common MT (and MT64) implementations have a tempering parameter 'd' (a bit mask). The papers I've looked at describing MT don't include it. Where is it from? When was it added?

Long version! :)

I'm looking at using a family of MT's with different parameters (for reasons). Nishimura published this paper describing a 64-bit MT implementation and a number of alternatives for the A matrix and (u,s,t,l,b,c) tempering parameters. Like the original 32-bit MT paper, this describes the tempering procedure as:

y := x xor (x >> u)
y := y xor ((y << s) and b)
y := y xor ((y << t) and c)
z := y xor (y >> l)

However, real implementations *(3) *(4) and the parameters described in the MT Wikipedia page have an extra bit mask parameter (referred to as 'd'), applied to the first step of the tempering procedure:

x ^= (x >> 29) & 0x5555555555555555ULL;
x ^= (x << 17) & 0x71D67FFFEDA60000ULL;
x ^= (x << 37) & 0xFFF7EEE000000000ULL;
x ^= (x >> 43);

I don't want to just 'blindly' use the tempering parameters that exclude the parameter 'd' without understanding what it's for... but I can't seem to find any references for why this 'd' parameter was added. (Presumably, it's an improvement...)

Any ideas on what it's for, any references to why it was added?


texts: Equivalence of logical Formula (Kripke structures)

texts:
Can someone explain me how to find if these formulas are equivalent with Kripke structures?

AG(Fp or Fq) , A(GFp or GFq)

AGF(p and q) , A(GFp and GFq)

AFG(p and q) , A(FGp and FGq)

Thank you in advance for your help :)


texts: Relation between mathematical functions and trees?

texts:
I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.
Is there a good way to model a tree in terms of functions?


texts: Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

texts: Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) that given three points returns true if they are non collinear and false otherwise. Is there an efficient algorithm to generate a list of random points such that no 3 points in the list are collinear? The points coordinates x y are integers, the amount of points is N and the grid size is RxC, I know that there is a restriction between N and R C, so I am fine if the algorithm relies in some assumption (e.g RxC is way bigger than N)


texts:
The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with it but I can't figure it out. What's the problem?

FWIW, those tiny signs are stars which are necessary for C-style comment: "/* comment */"
  The loop in the state three is "except *"


texts: Is resolution complete or only refutation-complete?

texts:
Going through some knowledge representation tutorials on resolution at the moment, and I came across slide 05.KR, no77.

There it is mentioned that "the procedure is also complete".

I think this completeness can not mean that if a sentence is entailed by KB, then it will be derived by resolution. For example, resolution can not derive $(q \lor \neg q)$ from a KB with single clause $\neg p$. (Example from KRR, Brachman and Levesque, page 53).

Could anyone help me figure out what is meant in this slide? Is the completeness of slide refer to being refutaton-complete and not a complete proof procedure?


texts: What is the limit for Turing machines with 2 states and 3 symbols that halt?

texts:
I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, it is based on a Turing machine that doesn't halt.

If we consider only computations that do halt (that end on an additional accepting state), the set of initial configurations that produce such computations could be considered a formal language. In that case, what would be the limitation to the class of languages that could be defined by those machines (with 2 states and 3 symbols)? Could they be specified using regular expressions?

Any help is appreciated.

The following TM halts and accepts iff the initial configuration is $(d_{1}01^*[1]d_{2} + d_{3}[0]d_{4})$, where $d_{i} \in \Sigma^\infty$, and $[x]$ (with $x \in \Sigma$) denotes the position of the tape head.


texts:
I have a question regarding buchi automatons. The automata for the LTL formula, G(Xa->b) is as the attached picture. Why dosen't a have to be true in order to make the automaton correct?

My suggestion

Best regards


texts:
In IDE's we can drag a small continuous collection of pixels in a particular configuration to a place on the screen .This collection of pixels are called as controls .

Corresponding to every control, there are various kinds of event handlers,like for a button , some subroutines for events like "double click" , "single click" are available ,for a grid there might be "right click ", "gaining mouse focus" event handlers might be available .

The collection of available event responding subroutines,from what I could conclude , further depend on the framework or library we are using.

Now let us imagine that we have certain hardware with us and only one programming language available and we are accommodating some aliens in this world for whom , nose, is a very important sense organ for communication .Avoiding the concerns of scientific  feasibility of such creatures let us say that to provide input to anything they exhale and inhale air into some device .
And to meet their requirements we might need programs that can manipulate the fragrance that they are smelling , like ,let's say we need a computer program for a messaging app that is to be designed for them to be able to emit the smell of rose at the receiver's end when the sender scratches the screen and many more .

Now given such a situation , if I want to design a GUI for them or may be (OUI,olfactory user Interface ) how can I make my systems compatible with their method of input and output .I mean how can I design event handlers for them like , "One nostril snort event ", "double nostril snort event ","deep inhale event " and many more that we can imagine .

What are the changes that I would require :

Do I need to add some new things in my programming language ?
Do I need to change my hardware (counting out their input device ,namely ,snake :P) ?
Do I need to change my OS ?

P.S :  I asked this question ,because,to put in the most general manner and basically  I wanted to deconstruct and see from the bottom , how can computer programs(including the OS ,which in essence is also a computer program ) control hardware and as such I might get a better idea on how to direct myself in learning about all this.


texts:
And how do I solve this?
I know this is a decimal and we have to convert it to an exponent. I want to know how I would solve this and the steps as well so I will be able to solve questions similar to this in the future. Thank you


texts:
I'm formalizing some properties of lambda calculus in Coq and I have some problems proving termination of substitution. My terms are defined as:

Inductive Term :=
  TVar: nat -> Term
| TAbs: nat -> Term -> Term
| TApp: Term -> Term -> Term.

and I have a way of generating fresh variables using a function

fresh: Term -> nat

satisfying:

Lemma fresh_is_fresh:
  forall t,
    ~ FV t (fresh t).

and similarly a function fresh2: Term -> Term -> nat for obtaining a fresh identifier wrt. two terms.

I now want to define a standard notion of capture avoiding substitution:

Fixpoint substitute (t1:Term) (t2:Term) (x:nat): Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

Obviously, Coq cannot see that this definition is terminating, so I need to provide a custom measure, so that the code is something like the following:

Program Fixpoint substitute (t1:Term) (t2:Term) (x:nat) {measure ???}: Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

Now my question is: What is the correct measure to use here? And how I do use it to prove the obligations which arise using this measure?


texts: In Probabilistic Graphical Models, are Cliques and Clusters the same?

texts: I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are the cliques and clusters the same?


texts:
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.

It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such that A*B=S where S is a semiprime number. I added the conditions that A != 1, B != 1 and A <= B, then added the value of S to the formula make sure the assignment is unique. The only way to satisfy the formula is to put the values of primes A and B in correct order in the input bits.

In 1-in-3SAT, we force that exactly 1 literal should be true in each triplet and two others false. If exactly 2 literals are true we can flip all the iterals in the clause to get an equivalent 1-in-3SAT clause (in other words 2-in-3SAT is the same problem).

Basic observation: While a regular OR clause eliminates 1 possibility out of 8, a 1-in-3 clause eliminates 5 possibilities out of 8.

3SAT can be reduced to 1-in-3 SAT, such that if the 3SAT formula is satisfiable then so is the reduced formula.

However, reductions do not seem to preserve the number of assignments, by introducing new variables without forcing their value.

Can Unique 3SAT be reduced to Unique 1-in-3SAT...

Without knowing the correct assignment?
If not, while knowing the correct assignment?


texts: What kind of Neural Network (if any) could fit two sets of data points?

texts: I have two datasets, one of animal migration patterns (collected over the course of a couple years) that consists of many points on an x, y plane (latitude, longitude), and the other of ocean surface temperatures (also a set of lat, long points). What kind of neural network can be used, if any, to see some pattern, or correlate the two sets, so that I could alter the temperature data and have the network predict how the migration pattern changes? Is this a feasible use of an artificial neural network?


texts: turing machine logic instead of something

texts:
Lets assume I have this turing machine:

And I have a $\Sigma = \{0,1,2,3,4,5\}$.

Now my question is can I simplify the transaction from $A$ to $B$ ?

Is there any way so I can write - when the read value is not $2$, write $x$ and move to right?


texts: How to properly compare performance of a prototype against a baseline

texts:
Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average).

I have m queries/problems that I run on each software with a timeout T. I record the raw running times $b_1,\dots,b_m$ of B and $t_1,\dots,t_m$ of P.  It could be that for some (few) problems B is still faster than P, moreover it could be that there are very short times such as 0.01s or considerably longer ones, for instance, 3000s. Now my question is, what is a good measure to compare the performance of B and P quantitatively on average?

A straightforward (but probably crude) measure could be just computing the average running times $b_a = \frac{1}{m}\sum_{i=1}^m b_i$ and $t_a = \frac{1}{m}\sum_{i=1}^m t_i$, and taking $\frac{b_a}{t_a}$.

A variation of this measure is taking the average of times when both systems didn't timeout and counting the number of timeouts, although not sure how to get just one measure from these four values.

These two measures do not address one my concern related to the variance in the values of the times. For instance, for $m=2$, $b_1=2500$s, $t_1=8$s, $b_2=2000$s and $t_2=1000$s, the first measure is 4.4643. Does it mean that P performs on average 4 times faster? Would it be more reasonable to take the average of the normalised times $\frac{1}{m}\sum_{i=1}^m \frac{b_i}{t_i}$? In this case it would be equal 157.25 and, seems to me, would better reflect the performance gains.

And again, a question is how to take timeouts into account properly.

I am sure that there should be standard approaches to comparing performance of two systems(for instance, databases), but I wasn't able to find anything quickly. I would also be grateful to see an explanation why one measure is better than the other, and what are the standard measures (at least on the scientific community).


texts: Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

texts:
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?

If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \  j\neq ki \} $ is context free (as it can be presented as a finite union of context free languages in a similar way to the example here: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?)

I think that it's not context free but have failed to prove it.
By reading other questions on this site I noticed this interesting observation: CFL's in $a^*b^*$ are closed under complement as can be seen here: Are context-free languages in $a^*b^*$ closed under complement?

So our language $L$ is context free if and only if $ \bar L = \{ a^ib^j \mid \ \ i\ \mid\ j \ \} $ is context free. I tried using the pumping lemma but  to no avail.

Thanks in advance


texts: Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

texts:
I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ refer to the language that a given CFG generates $\Sigma^*$, and let $ALL_{REX}$ refer to the language that a given regular expression generates $\Sigma^*$ (and since for each regular expression there is a regular grammar, we can also say that the equivalent regular grammar generates $\Sigma^*$).
From what I got, we have:

$ALL_{CFG}$ is not decidable, it is also not Turing-recognizable. Let $\overline{A_{TM}}$ refer to the language that a TM $M$ does not accept input word $w$. We can reduce $\overline{A_{TM}}$ to $ALL_{CFG}$ in polynomial time using computation histories. The reduction constructs a CFG which generates all possible words where: 1) the first characters do not match $w$,  2) the last characters do not match accepting configurations, and 3) characters do not match valid transitions of $M$'s configurations. Thus, $A_{TM}$ does not accept $w$ iff the CFG generates $\Sigma^*$ (i.e. there are no accepting computation histories). Since the reduction maps $\overline{A_{TM}}$ to $ALL_{CFG}$, and $\overline{A_{TM}}$ is not Turing-recognizable, $ALL_{CFG}$ is not Turing-recognizable.

$ALL_{REX}$ is decidable since it is decidable if a finite automaton accepts $\Sigma^*$. However, the acceptance problem for any regular language $R$ can be polynomially reduced to the language $ALL_{REX} - f(R_M)$, where $R_M$ is a TM that decides $R$, and $f(R_M)$ is a similar reduction of computation histories as outlined above.  In more detail, $f(R_M)$ is the regular grammar that generates all possible words where  1) the first characters do not match $w$,  2) the last characters do not match rejecting configurations, and 3) characters do not match valid transitions of $R_M$'s configurations. The decider for $ALL_{REX} - f(R_M)$ checks if it is empty (which means that $f(R_M)$ is equal to $\Sigma^*$). If empty, then there are no rejecting computation histories and $w \in R$. (In Sipser, he used something like this to show EXPSPACE-completeness for $ALL_{REX} - f(R_M)$)

I would like to ask:

From above, both regular grammars and CFG could generate computation histories of a TM, and both could generate $\Sigma^*$. But what is it with the fundamental power of the CFG's grammar that makes it valid to reduce $\overline{A_{TM}}$ to $ALL_{CFG}$, but it is not possible for $\overline{A_{TM}}$ to be reduced to $ALL_{REX} - f(A_{TM})$ ? I know that we cannot reduce $\overline{A_{TM}}$ to $ALL_{REX} - f(A_{TM})$ since $ALL_{REX} - f(A_{TM})$ is decidable, while $\overline{A_{TM}}$ is not Turing-recognizable... But I would like to understand this in terms of the difference in generating power between CFG's and regular grammars via their rules.

For instance, from what I read, CFG's permit the rules $A \rightarrow BC$, where $B$ and $C$ are strings of variables and terminals. On the other hand, regular grammars only permit rules in the form of $A \rightarrow aB$, where $a$ is a terminal. I would like to ask: why does incorporating rules of the form $A \rightarrow BC$ to a grammar, give it enough generating power such that it is already valid to reduce $\overline{A_{TM}}$ to the grammar (i.e. to the CFG).


texts: Why is this problem listed as "Dynamic Programming"

texts:
I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:

  Nikita just came up with a new array game. The rules are as follows:
   Initially, there is an array, , containing integers.
  In each move, Nikita must partition the array into non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets point; otherwise, the game ends.
  After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array .
  Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

In going over the algorithm that would be used to solve the problem, it seemed evident to me that you could simply write a recursive function where each recursive call would be made iff the sums of the elements in both halves of the array are equal. Otherwise, the game (the algorithm) ends. Since you would, in the worst case (running time wise), be dividing the array log(n) times where n is the array length, you would get a running time of O(logn).

The only thing that I could see dynamic programming helping with here may be the recalculation of the sums which I guess could be avoided by calculating the sums from the bottom up but I'm not really seeing an optimal substructure here. Also, you would be increasing the space complexity seemingly unnecessarily.

So why/how is dynamic programming being used here?


texts: Distinction between 2 languages.One is regular the other is not

texts:
whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.

given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \mathbb{N}\}$

$L_2=\{(01)^{n}0(10)^{n} |n \in \mathbb{N}\}$

The only difference between $L_1$ and $L_2$ is the $0$ in the middle.
$L_1$ is non-regular but $L_2$ is .

In the appendix page in the workbook it's written that:the intuition used in L1 is that I need to remeber an infinite states, and then using the "Pumping Lemma" they disproved that it is regular. It also says that L2 is regular and it is possible to build a DFA for the language.

I am not looking for answers for how to solve this, just why this notion of "machine have to remember an infinite states" is not applicable to $L_2$ because it seems that in $L_2$ the machine needs to remember how many times $01$ appeared then after $0$ machine needs to repeat the same number of time for $10$.

I also use this webpage:https://www.geeksforgeeks.org/how-to-identify-if-a-language-is-regular-or-not/

A bit over year ago I asked about the statemnets written there and they told it is not fully reliable(theorem no. 5 : "concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.")

Why language is not regular

Before trying to draw a DFA or disaproving using pumping lemma I use these theorems, but as it seems it maybe unreliable.

The questios are: why L1 is regular and L2 is not(I understand that one can be described via dfa and the other is not, just why L2 is not supposed to remember an infinite states).

and if the link for "geeks for geeks" can be used, to help to decide if language  is regular or not?(I know that the only way to determine is by building dfa or pumping lemma=> these are the only 2 ways I've so far as a student studied,but before wasting time in the exam for building "DFA" for non regular language I need some sort of "hunch" as to choosing to disaprove by pumping lemma or building a DFA).


texts: If $A \leq B$, $B \leq \overline{A}$, and $B$ is r.e., is $A$ recursive?

texts:
We know that $A ≤ B$, $B ≤ \overline{A}$ and $B$ is recursively enumerable. Is $A$ recursive or not?
I tried negating whats given, but didn't achieve much. I know that from the very first inequality that $A$ is also recursively enumerable. I assumed whether $B$ is also recursive or not to maybe get to a contradiction of some sort, but I always ended up with "sometimes recursive, sometimes not".


texts:
I am working for the first time on building a unsupervised learning model to detect suspicious transactions using DBSCAN, Do I train the model on all data columns(Columns like account number, transaction date, transaction details ) or only on the ones that I want to detect suspicion (money withdrawal and deposit columns)?
This is the data set that I am working on https://www.kaggle.com/apoorvwatsky/bank-transaction-data
Please help me


texts: Chinese postman problem, but criteria = visit each vetex at least once

texts:
Chinese postman problem, but where the postman have to visit each vetex at least once.

Is there a name for this problem?

What is the ideal algorithm to solve this problem?


texts: Does the way that PageRank is heavily skewed lower the effectiveness of TF-IDF calculations?

texts: PageRank is heavily skewed in that a small proportion of webpages have a high PageRank score while most of the others have a very low PageRank score. Does this undermine the effectiveness of the TF-IDF function? For example, if PageRank scores were to be combined with TF-IDF scores, then for a few of the webpages, the TF-IDF would make very little difference, as they would have a high PR score, correct? And for the majority of the webpages with low PageRank, the TF-IDF score would tend to dominate, right?


texts: find all edges in a weighed tree that are heaviest edges in some cycle

texts:
Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$:

Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all the edges in the cycle are not of heavier weight than $e$.

Find an algorithm that computes $U$.

I have found an algorithm to do it using a modified version of Kruskal algorithm and the union find data structure in $\mathcal{O}(|V|+|E|\alpha(|V|,|E|)$.

My TA said that it can be computed using a linear time algorithm, can you help? I thought of something about modifying the Prim algorithm and then using $10$ Queues for each weight.


texts: What is the difference of Process synchronization management between Windows and Linux?

texts:
I am looking for some explanation about process synchronization management in windows OS and Linux OS and what they do about the critical section and mutual exclusion.
I will be so grateful if someone offers me a research or paper about it.


texts: Finding minimum distance between two convex polygon

texts:
We have two disjoint convex polygon $P,Q$, each with size $n$ , how we can find minimum distance between two convex polygon $O(\log n)$?
We think for each points in  $P,Q$ we must check to find minimum distance that time complexity is $O(n^2)$.


texts:
Is there an efficient classical algorithm that generates samples from the uniform distribution (or a distribution that is close to the uniform distribution in total variation distance), over the set $\{0, 1\}^{n}$, for a fixed $n$?
We can easily express the uniform distribution in terms of a formula:
$Pr(X = x) = \frac{1}{N}$, for each $x \in \{0, 1\}^{n}$ and $N = 2^{n}$.
My guess is that any distribution that can be expressed in terms of an explicit formula can be efficiently sampled from, but I can't find a concrete proof.


texts:
When we are trying to learn a new language without any help from native speakers, the first thing we need is something/someone to correct our grammatical mistakes/improper word selection.

So is there any research done on building tools to help critique our spoken language? I often hear people saying that the more you try to speak, the better you get, so I'm wondering if automated tools could help provide feedback on our attempts at speaking in the new language.


texts:
I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called MagicCardMarket, which is kind of an Ebay for trading cards. The problem is that the site doesn't have a proper optimization tool, so I'm trying to make it myself. (I found some other site that does this, but you have to pay for it and I'm learning a lot already doing it myself.)

The first thing I do is gather a bunch of information. The most important parts being how many and what cards the buyer want. Then I gather all the articles that comply with these cards and throw away all the bad ones (those who's quality is too bad, or language is incorrect, ...) Articles are basically instances of those cards being sold, with info about their seller and cost. So now I have a list of cards, and for each card a list of articles for those cards, and for each article a cost and seller (and from this seller I can get the shipping cost, this can depend on how many cards are bought from a single seller, though most of the time it stays almost constant.)

So now I'm looking for an algorithm to get all the cards you want, as cheap as possible. Taking into consideration that when I buy from more sellers, the shipping cost will go up.

Are there any algorithms I should look at, that might lend themselves to this problem very nicely? Or perhaps some general tips for these kinds of algorithms? It's the first time I'm trying to make this kind of algorithm, so I wasn't sure what to search for either.

The easiest way would probably be to just get all possible combinations, and check which is the cheapest, though most cards will have several hundreds of articles associated with them, and most of the time you'll have 60 to 80 cards you want to buy (a full deck.) So I don't think this is a good way, it uses enormous amount of ram and takes a lot of time. I'm also writing it as a web-app, preferably something that can also work on mobile phones.

Thanks a lot!

PS. I wasn't sure if this is the proper forum to ask this, please redirect me if I was wrong.


texts: Rotation matrix between two objects - alignment

texts:
I am trying to align two objects based on the notion of points and their correspondence, but struggling to find a solution.

I have two objects A and B. However, they are rotated in a different direction, and therefore I would like them to align. I have a notion of some correspondence between the points in object A and in object B.

The initial idea that I had looks as follows. Pick two points( let's call them center and end point) in A, and then pick the corresponding points in B. Then measure the angle between them.

I believe that I could get an angle between them, but I am not sure how would that translate to the rotation matrix. I was also wondering whether it is not better to split it into different axes , and then perform multiplication. However, I am not sure how would I proceed with that.

Could anybody give me advice whether my approach is ok, or possibly provide a way of obtaining a rotation matrix for the whole object based on those vectors?

My idea:

Let's say that I have object A, and two points:

A0 = [2,4,6]

A1 = [3,5,7]

Then I calculate a vector

A0A1 = [1,1,1]

Then I find a corresponding two points in object B:

B0 = [4,8,12]

B1 = [2,7,5]

Then B0B1 = [-2,-1,-7]

Now I would calculate the angle


texts: adder in logisim using only 2-input-NAND gates

texts:
I want to build an adder in logisim only with 2-input-NAND gates. The adder consists of 2 inputs (1 x constant 1 and 1 x arbitrary number) and an output.

The first thing which came into my mind is a 8-bit full adder but maybe there is an easier solution for this (because of the constant 1). Has anyone an idea? THX


texts: Can we enumerate all probabilistic Turing machines (with bounded error), like we do for deterministic Turing machines (when using diagonalization arguments against deterministic Turing machines)? If not, does this mean we cannot diagonalize against BPP machines?


texts: Where can I find working code in 2020 that implements the Futamura projections? I can find lots of stuff explaining the theory but no actual implementations.


texts: Usefulness of a linked list with a cycle

texts:
Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it?

(You could argue that a car without its front shield is not corrupted, if the owner intends for it to be like that, so lets understand the word "corrupted" in a sense of "damaged into state that it is useless".)

One of the possible ideas that I got is that it can represent some sort of a computation: the initial "non-cycled head" of the list can be viewed as the initialisation phase, whereas the "cycled tail" can serve as a never-ending computation. However, this reasoning is a bit Texas Sharp-shooter fallacy to me.

Any ideas?


texts: Proving that the failure of algorithm W implies that the program is not typable

texts:
How one does prove that if algorithm W failed for a given program $e$ and context $\Gamma$, then there is no substitution $S$ and type $\tau$ such that $S\Gamma \vdash e : \tau$ ?

The original paper states that from the completeness proof one can derive that "it is decidable whether $e$ has any type at all under the assumptions $\Gamma$". However, I didn't found this proof in the literature.

The algorithm W has some failures cases: the unification algorithm failed, an identifier was not found in the context, a recursive call failed, etc.

I more interested in the hard cases, the easy ones I can do myself.

One hard case seems to be the failure of the unification.
In this case we know about the soundness and completeness of both recursive calls and, also, the non-existence of a unifier for $S_2\tau_1$ and $\tau_2\rightarrow \alpha$. How those informations can be used to prove $\neg \exists \tau \:S, S\Gamma \vdash e_1 \: e_2 : \tau $ ?

This part of algorithm W may be relevant here:

  $W(\Gamma, e_1\: e_2) =$

  $\quad (\tau_1,S_1) \leftarrow W(\Gamma, e_1)$

  $\quad (\tau_2,S_2) \leftarrow W(S_1\Gamma, e_2)$

  $\quad S \leftarrow \mathrm{unify}(S_2\tau_1, \tau_2\rightarrow \alpha)$ where
  $\alpha$ is fresh

  $\quad$return $(S\alpha, S \circ S_1 \circ S_2)$

There are other hard cases, but I will be accepting an answer if it is about at least this one.

EDIT:

In Damas' PhD thesis, the pages 74-82 are the completeness proof of algorithm W.
After this proof there are two corollaries about the existence of principal type schemes. After that the thesis changes to subjects no related to my question.


texts: Determining if given languages are regular or recursively enumerable

texts:
I came across following problem:

  Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
  $L_1 =\{M|M$ accepts at most 2016 strings$\}$
  $L_2=\{M|M$ accepts at least 2016 strings$\}$
  If $L=L_1\cap L_2$, then which one of the below is correct?
  A) $L'$ is recursively enumerable
  B) $L\cap L'$ is recursively enumerable
  C) $L\cup L'$ is recursively enumerable
  D) $L$ is recursively enumerable

The solution given was:

  $L_1$ by definition is regular language (“atmost”).
  $L_2$ by definition is recursively enumerable (“at least”).
  Recursively enumerable languages are closed under regular intersection. Hence, $L = L_1 ∩ L_2$ is recursively enumerable. Thus option D. Recursively enumerable languages are not closed under complementation. Hence $L’$ is not recursively enumerable. Hence option A is wrong. And since $L’$ is not recursively enumerable, options B and C are also wrong.

My doubt

I am struggling with how $L_1$ is regular and $L_2$ is recursively enumerable, that is with first two sentences:

  $L_1$ by definition is regular language (“atmost”).
  $L_2$ by definition is recursively enumerable (“at least”).

Usually language definition specifies criteria on format of input string which will allow us to reject or accept it. But here the definition specifies how many strings the language has or its corresponding Turing machine accepts.

I found this similar sounding problem, in which the answer gives membership algorithm and hence proving language in that problem is indeed recursively enumerable. But I feel this does not applies in my problem. Correct? Or the problem is incorrect in telling number of strings languages can accept instead of format of acceptable strings?


texts: Is there a procedural way to find minimum s-t cut without guessing cuts?

texts:
I was reading about max flow theorem and there I saw scenario where the min s-t cut is found. But wherever I searched they did it after knowing the max flow  or by guessing the cuts by iterating almost all .

Is there a logical way to arrive at the minimum cut (with the paths) without knowing the maximum flow or guessing the cuts ?

Added thought:
In a graph of say N vertices, and say one is source 's' and other is sink 't'. So there are 2^(N-2) possible s-t groupings. This is huge even for N = 8. So is iterating all the only way to get the answer. I was told that it is being asked in exams. Is it fair to ask such an itertative procedure in exam of limited time. How can one be sure that he has arrived at the correct answer without checking all (or without being given the max flow value)? For eg. finding the min cut as explained here .


texts:
If a graph with $v$ vertices is represented in the form of adjacency matrix .

Then, adding a new vertex to the existing graph requires how much time ?

Is it $O(v^2)$ or $O(2v)$ .

We have the adjacency matrix of the graph with $v$ vertices , by adding a new vertex we have to enter a row (for edges leaving the new vertex) and a column(for incident edges of new vertex) and an entry for self loop . So ,there is a need to update $2v+1$ new entries. So i am in favor of $O(2v)$. Did i miss something ? Is there any need for creating new empty matrix of size $(v+1)^2$ and then copying $v^2$ existing elements and updating remaining $2v+1$ entries of new vertex , which takes $O(v^2)$ time.

Thanks in advance .


texts: Understanding How to Flatten a Nested Function System

texts:
There are at least two ways to flatten out a nested function. Both of them need to keep a certain amount of state to accomplish this. The two ways are:

By creating several boolean variables for each part of the function.
By creating a tree data structure that is navigated.

Say we have this function system:

function a(p) {
  var x = b(p)
  var y = c(p)
  return x + y
}

function b(p) {
  var x = d(p)
  var y = e(p)
  var z = f(p)
  return x - y * z
}

function c(p) {
  return p * 2
}

function d(p) {
  return c(p) + 3
}

function e(p) {
  return 3 * c(p) + 2
}

function f(p) {
  return 1 - d(p)
}

Then the first part of it could be represented by boolean variables (1) like this:

a_start
a_end
ab_start
ab_end
abd_start
abd_end
abdc_start
abdc_end
...

Then the evaluation would be along the lines of:

if (!a_start) {
  a_start = true
}
if (a_start && !ab_start) {
  ab_start = true
}
if (a_start && ab_start && !abd_start) {
  abd_start = true
}
if (a_start && ab_start && abd_start && !abdc_start) {
  abdc_start = true
}
if (a_start && ab_start && abd_start && abdc_start && !abdc_end) {
  abdc_val = p * 2
  abdc_end = true
}
if (a_start && ab_start && abd_start && !abd_end && abdc_end) {
  abd_val = abdc_val + 3
  abd_end = true
}
if (a_start && ab_start && abd_start && abd_end) {
  ab_x_val = abd_val
  ...
}

It gets confusing really quick and I'm not sure (a) if I'm exactly doing it right or (b) if it's even possible this way. But it seems like it is. In addition, all of these boolean checks would add up, so I'm not sure it would be as efficient as the nested method.

The other way (2) is instead creating a tree data structure and navigating that. This is roughly how it would look:

var base = {}
while (true) { ... } leads to:

a = { label: 'a', parent: base }
b = { label: 'b', parent: a }
d = { label: 'd', parent: b }
c = { label: 'c', parent: d, val: p * 2 }
next = c.parent = d
d.val = c.val + 3
next = d.parent = b
b.val = d.val
...

This seems closer to the stack approach like in normal iterative techniques.

The questions are:

If it's possible to represent the nested function system as (1) boolean expressions with a while loop and/or (2) a tree datastructure with a while loop.
If so, if it is possible to do it as efficiently (or more efficiently) than the corresponding nested version in either (1) or (2).
If either way (1) or (2) is "better" than the other. (I am not considering the nested version as part of the better equation, since the nested one is easiest to understand). It seems that way (1) is closer to a rule-based system, and uses minimal memory, while (2) is less brittle, a bit easier to understand, and might have better performance, but might use more memory. Also, (1) seems like it might be more robust, in that you can be at "multiple places at once" theoretically (so you could do multiple nesting branches at the same time), whereas in (2) you're always at one point in the tree. Also, I don't think I am modeling (1) correctly, since each iteration it will reevaluate the same expression over and over again until the booleans are false. This doesn't happen in the tree version. Maybe the booleans need to be more like the tree nodes somehow...
If there are any alternative "iterative" (flat) ways of simulating the nested function that would be helpful to be aware of.


texts: Binary strings such that the sum of 0's is not equal to twice the sum of 1's

texts:
Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$.

I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.


texts: How to find size of each tree in a forest?

texts:
Let $T$ be a tree with $n$ nodes. If I remove $k$ edges from $T$, I will have $k+1$ new trees i.e. a forest of $k+1$ trees.

How do I calculate the number of nodes in each of these new trees formed?

I need to do this for $q$ queries.

My approach:
I can remove the $k$ edges from the original tree and run DFS on each nodes from which edge was deleted and find the size of the new tree. And then join the nodes back after getting size of each tree.
But this is not optimal, can anyone suggest a better approach.


texts:
Let M be a Turing-machine with tape alphabet = {0, 1} that does not
  move beyond the first 64 cells of its tape. Is the problem "Does M
  accept any word?" decidable?

I would say it does not accept any word because we can have words longer than 64 characters.
I would say it does because if it accepts any word, we don't care about the length. It always goes into accepting state.

Can someone please explain this to me?


texts: What is the difference between Big O, Omega, and Theta?

texts:
I know that this question is asked a lot of time but I don't understand or I think, I got lost when I was reading Introduction to algorithms
They said, "It is not contradictory, however, to say that the worst-case running time of insertion sort is Omega(n^2), since there exists an input that causes the algorithm to take Omega(n^2) time.".
I read many articles that Omega is the best-case. As I understand correct me if I'm wrong, that the best-case is Omega notation and why they said, "since there exists an input that causes the algorithm to take Omega(n^2) time.", I don't understand why they called it worst-case and why I can call it Omega(n^2), isn't Big O for worst-case.
Also I don't understand they said, "Theta is notation is a stronger notion than Big O".
Why is that? and When should I call an algorithm that it's Big O of whatever, Theta or Omega?
Because I'm confused and I don't know which one is for or how to use them.


texts:
Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering down sentences).

Can any pure regex be converted into BNF? (ABNF, EBNF, etc.)

Are there well known algorithms (or existing library implementations) that can perform the conversion?

The language I wish to convert from is actually not the standard language of regular expressions, but one that conditions on word taggings which are provided per word (part-of-speech tags that come along with the text). So it is a variant of regular expressions, which operates at the word level rather than the character level.

Thanks!


texts: What approach to solve an open shop problem with following constraints

texts:
Say we have an open shop scheduling problem with following constraints :

No wait-time between operations of a job
Multiple job types (meaning each job type has different set of operations eventhough their intersection might not be empty)
No wait-time between each operation on the same machine (machine must not be idle from the moment it has taken an operation until it has finished all its tasks)
Some machines have multiple instances say $k_i$ instances (so the constraint that no machine can process multiple job at the same time is transformed to cannot process more than $k_i$ jobs at the same time)
The operations are partially ordered (making it close to a flow shop problem but the order is only partial meaning that some operations must happen before or after others but some can happen in any order)

The classical objective is to maximise makespan but here what I would like to  know is the maximum number of each type of jobs (with respect to a known distribution of the types) I could pack inside a given time frame.

What would be the algorithms/paradigms you suggest ? I'm going for constraint programming (OR-tools more precisely) but I'm not finding any alternative, is there any (proprietary software as a black box algorithm not excluded) ?

Additionnal informations : the number of machines is small but not 2 (~10) and the number of jobs is depending on the time frame but can be reasonably estimated to 10-100.


texts: Minimum Number of Edges Added to a DAG to get Unique Topological Order

texts:
The question is simple:

  Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has a unique topological ordering?

I initially approached this in a greedy way: determine the longest vertex-disjoint paths, then try to merge them head to tail. This seems to not work for parallel paths however, because we may break constraints imposed by the DAG. Since an equivalent goal is to impose a Hamiltonian Path on the graph, we could always use two or fewer edges to merge parallel paths such that we end up with one long path. Perhaps we could alternate between greedily merging longest paths in succession, then merging parallel paths and repeating. I'm not convinced this will be optimal however.

For any pair of unordered nodes $A$ and $B$ it seems we have the following 4 options:

$A$ and $B$ have no common ancestor(s) nor common descendant(s).
$A$ and $B$ have common ancestor(s) but no common descendant(s). ($\land$ structure)
$A$ and $B$ have no common ancestor(s) but do have common descendant(s). ($\lor$ structure)
$A$ and $B$ have common ancestor(s) and have common descendant(s). ($\diamond$ structure)

With this, my next idea would be to go through all pairs of unordered nodes and determine which of these 4 cases it falls into, then add an edge between the nodes that would decrease the set of unordered nodes by as much as possible. Would this greedy strategy work either? I cannot think of any edge cases that would prevent this from working, but a greedy proof of this also does not seem to work.

Is there a polynomial time algorithm to answer this question? If not, is there a reduction from an NP-complete (or NP-hard) problem?

Maybe a related question would be "Given an undirected graph $G$, what is the minimum number of edges needed to be added such that the resulting graph has a Hamiltonian Path?" However, this question seems implicitly more difficult because it's NP-complete just to determine if $G$ has a Hamiltonian path, so I would think the problem becomes easier in a DAG.


texts: Clarification on halting predicate computability

texts:
I am tackling the halting problem right now and its remarkable theorem. My book states $\text{HALT}(x,y)$ is true if $\psi^{(1)}_{\mathcal P}$ is defined and conversely $\text{HALT}(x,y)$ is false if $\psi^{(1)}_{\mathcal P}$ is undefined.

The purpose of the theorem, of course, is showing that $\text{HALT}(x,y)$ is a not computable predicate. I will report the extract of the proof given:

Suppose $\text{HALT}(x,y)$ were computable. Then we could construct the program $\mathcal P$:

$$[A]\;\;\;\;\;\text{IF HALT}(X,X)\text{ GOTO } A$$

It is quite clear that $\mathcal P$ has been constructed so that

\begin{equation}
\psi^{(1)}_{\mathcal P}=
\begin{cases}
\text{undefined} \;\;\; \text{if HALT}(x,x) \\
0 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{if ~HALT}(x,x)
\end{cases}
\end{equation}

I don't understand how $\psi^{(1)}_{\mathcal P}$ is undefined if $\text{HALT}(x,x)$ is true, shouldn't $Y$ be equal to $0$ by default and moreover how could a non-terminating program be defined can have $0$ as output value. What am I missing here?

Edit: $\psi^{(1)}_{\mathcal P}(x)$ is the value of the output variable $Y$ at the terminal snapshot.


texts: Strong NP-completeness of numerical perfect matching

texts:
This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness.
Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each number in $L$ with a number in $M$. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*m_i$.
The problem is to decide the existence of a perfect matching with some given cost $C$.
Is this problem strongly NP-complete?


texts: Is it proven that quantum computation is no better at solving NP complete problems than classical computation?

texts: Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?


texts: Removing and reinserting elements to minimally mimic a changeset

texts:
Let's say that there is a tower of blocks labelled from top to bottom $1$ to $n$. Somebody comes along and removes a block and reinserts it somewhere in the tower (making space as needed). As they move these blocks one at a time, they write down in order which index they moved a block to (index starting at 1). For example, they take the block 5 from the 5th index and squeeze it into between the 6th and 7th making it the 7th index. They write down "block 5 to index 7". They can make as many moves as they like and move each block as many times as they like.

Note that the index "moved to" is the index of the block after the removal and insertion are complete.

Someone else finds the changeset the original person created. Knowing the size of the tower and having the list of changes, they must write another changeset that would have the same results as the first but with at most one move per block and the moves must take place in the order that the blocks were originally moved in without latter duplicates. This also means that only blocks of the original changeset can be moved.

I came up with one which is to repeat the steps in order excluding those where the block is moved again later. This seemed to work in some cases but not all.

Is there an algorithm to solve this problem?


texts:
Is it required that a NP-hard problem must be computable?

I don't think so, but I am not sure.


texts: Number of leaf nodes in n-element red-black trees

texts: Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?


texts: Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets

texts:
The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)

Is there an algorithm to generate all the possible combinations?


texts: Compute sum of edges in paths from source to target node?

texts:
Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u <v (see the graph below). The weight $w(u,v)$ on each edge is a positive number. For a given node $i$, I am interested in computing the  following term $s[i]$ defined as follows:
s[i] is sum of weights on any edges (w.o duplicates) of some paths from the source node 1 to the node i.
For example, in the below graph s[6] =  3+ 2+ 10 + 20 + 200 + 100 = 335.
I am struggling how to come up with a linear time w.r.t $|V|$ and $|E|$ to compute $s[i]$ for a given node $i$.
I am thinking of using dynamic programing. For example, suppose we already can compute $s[j]$ up to $j<k$, to compute $s[k]$ we might attempt $s[k] = \sum_{i} s[i] + w[i,k]$ if there is an edge $(i,k)$. For example, to compute $s[6]$ we need $s[4]$ and $s[5]$,
So $s[6] = (s[4] + 200) + ( s[5]+ 100) = (3+200) + ( (3+2+20+2+10) +100) $ but this approach fails since we did not take into account that  the edge $(1,4)$ is shared in computing $s[4]$ and $s[5]$. The edge $(1,4)$ should be summed one time in $s[6]$.


texts: Modelling of minimal NOR-circuit problem with CP

texts:
I'm currently working on a Constraint Programming problem which I find difficult to model.

Here 's the definition of the problem :

" Given a specification of a Boolean function f(x1, ..., xn) in the form of a truth table, to find a NOR-circuit (meaning only NOR gates) satisfying the specification that minimizes depth (and, in case of a tie in depth, with minimum size).
In order to simplify the problem, several assumptions are made:

• Only NOR gates with 2 inputs and 1 output can be used: more general
NOR gates with more inputs are not allowed (i.e., the fan-in of NOR
gates is always 2).

• The output of a NOR gate can only be the input of a single gate:
outputs cannot be reused as inputs of more than one gate (i.e., the
fan-out of NOR gates is always 1).

• In addition to the input signals of the Boolean function to be implemented, constant 0 signals can also be used as inputs of NOR gates.
Constant 0 signals as well as input signals can be used as many times
as needed as inputs of NOR gates. On the other hand, the circuit does
not need to use all input signals. Similarly, the constant 0 signal does
not have to be used if it is not needed."

Source : https://www.cs.upc.edu/~erodri/webpage/cps/projects/Q2-16-17/proj.pdf

Since this is the first time that I'm confronted to this kind of problem, I'm having difficulties finding "good" decision variables. Maybe I'm missing something trivial ...

Do you have any idea/hint on how to model this problem ?