texts: Is it possible to build short proofs of arbitrary folds over a huge list?

texts:
With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False

My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations over a big list using some clever trick similar to Merkle Trees?

Formally

Given those 5 values:

H :: String -> Uint256, a fingerprint function
H(X) :: Uint256, the fingerprint of a dataset
F :: String -> String, an arbitrary computation
Y :: String, the claimed result of F(X)
A short proof

I need a verify function that returns true iff F(X) == Y, without having to run F(X); perhaps not even having the whole original dataset X.

Specific example

Suppose that you have a huge dataset (20 GB) distributed through a network of 100 computers that don't trust each-other. Is there any way for a computer to generate a claim such as the sum of this dataset is 1650874919052809!, so that other nodes are able to probabilistically verify that claim is correct, without actually running sum dataset?


texts: Closed network system that use OSI model to connect to another network?

texts:
The OSI model can be used for LAN and WAN networks, allowing the interconnection of [vendor] closed systems and it only informs what each layer have to do.

Someone said that this phrase is false, because OSI (Open Systems Interconnection) model, "as the name says", only allows the connection of "open systems".

So I'm wondering if there is any vendor closed network that, nonetheless, can communicate with another network using as the middle man an OSI based network. As I see it, in the broad sense of the phrase, two closed systems don't need to be directly connected to be interconnected, they can use a middle man.

Searching I only found about closed systems in the sense that they can't be freely joined.

Is that phrase true or false?


texts: Really confused about latency with pipelining

texts:
I finished watching a video about pipelining https://www.youtube.com/watch?v=eVRdfl4zxfI
which I thought made sense.
Latency is the amount of time it takes to complete each instruction. Even with pipelining, the time it takes to complete an instruction is still the sum of the time it takes for every stage, in this case it's 20ns.

But then I did a bit more studying and found out the latency is supposed to be time for the longest stage to finish execution + the "cost" of pipelining, rather than the sum of time it takes to execute all the stages?
http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/perform.html

Is there something I'm missing?


texts:
Consider the Minimum Spanning Tree Problem on an undirected graph
G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all
be different. If the costs are not all distinct, there can in general be
many distinct minimum-cost solutions. Suppose we are given a spanning
tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some
minimum-cost spanning tree in G. Can we conclude that T itself must
be a minimum-cost spanning tree in G? Give a proof or a counterexample
with explanation.


texts: Problem on finite state machines in the feynman textbook

texts:
I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says

  Suppose we feed a sequence of 1's and 0's - a binary number -
  into a machine. Design a machine which performs a pairwise sum
  of the digits, that is, one which takes the incoming digits two at a time  and adds them, spitting the result out in two steps. So, if two digits come in as 00, it spits out 00; a 10 or 01 results in a 01 (1+0 = 10+11!); but a 11 results in binary 10: 1+1 = 2, in decimal, 10 in binary. I will  give you a hint: the machine will require four states.

I don't ask you the answer. Just I don't understand what this is asking.
For example, when the input sequences are (00)(01)(10)(11)(10)(00), output sequences should be what?

Thanks in advance.


texts: SimRank++ on a weighted graph (why the formula reflects the influncee of the weight)

texts:
In the paper "Simrank++：Query Rewriting through Link Analysis of the Click Graph"(http://www.vldb.org/pvldb/1/1453903.pdf), the formula to compute the similarity between $q$ and $q'$ is as follows:
\begin{align}
s_\mathrm{weighted}(q,q') =&\ \mathrm{evidence}(q,q')\cdot C_1\cdot\\
&\sum_{i\in E(q)}\sum_{i\in E(q')} W(q,i)W(q',j)s_{\mathrm{weighted}}(i,j)
\end{align}

The paper defines the notion of consistency : If $\mathrm{Var}(v_1) = \mathrm{Var}(v_2)$ and $w(i_1; v_1) > w(i_2; v_2)$, then $\mathrm{sim}(i_1; j_1) > \mathrm{sim}(i_2; j_2)$. But for the example in the  figure 6 of the paper as follows, the variance of flower and orchids in (1) and the variance of flower and teleflora in (2) are all $0$. Meanwhile, the normalized weight value of Teleflora.com in (1) and (2) are the same. According to the simrank++ formula, the similarity between flower and orchids in (1) and the similarity between flower and teleflora in (2) are the same. My question is that, how the different weights on the edges of (1) and (2) can reflect the difference of the similarity?


texts:
I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS primality test, and I believe this works for COMPOSITE as well.

As for FACTOR,

$$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ divides } m\} $$

from what I have read it seems that it is in $NP \cap Co-NP$. I see that it is in $NP$ since a certificate would consist of a prime divisor of $m$ less than $r$. But what kind of certificate can establish that there is no such prime divisor (in polynomial time)?


texts: Proving a language as undecidable without using reductions

texts:
Let's say our Σ is 0 and 1. I want to disprove the following:

  There can be Turing Machines that accept only 1's, i.e. 1, 11, 111,
  etc. Therefore, all languages that have strings of 1's are
  recognizable.

My first step to proving this is by providing a language such as $One$, that accepts only if $w$ contains only $1$'s. There is a theorem that stated that $One$ is decidable iff $One$ and $\overline{One}$ are recognizable.

So, if I were to prove either one of them as unrecognizable, then I should be good. $\overline{One}$ I'll define as the set that doesn't contain 1 in it (i.e. episolon, 0, 00, etc). Creating a turing machine that simply goes right and accepts if we reach end without hitting a one, rejects if we do hit a one seems to work for this case. Could a language be created that isn't recognizable?


texts: Do all algorithms aim to solve decision problems?

texts:
An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more abstractly considered decision problems? Is the ultimate reason for a calculation, data processing or automated reasoning to solve a higher decision problem?

Thank you and forgive my ignorance.


texts: A syntactic property of computing systems: is non-coding DNA universal?

texts:
One of the surprising aspect of the genome for lay-people is that it
contains important non-coding DNA parts, which does not mean that they are
all useless. I never paid so much attention to the fact, until very
recently, when I realized that the same is apparently true of all
computing formalisms I can think of ... but maybe I forgot some, which
is part of my question.

If you consider finite state automata, you can always add an arbitrary
finite chain of unreachable states, which may be read as the Gödel
number of whatever statement you care to add to the FSA,
whether a copyright statement or a complete formal proof that it
recognizes a regular expression in some a priori chosen formalism.

But the same is actually true of CF grammars, of Turing Machines, of
Post Correspondence Problems, of lambda-expressions, of Primitive
Recursive programs, or of Partial Recursive programs, to name some of
the more important computing formalisms. Actually I cannot think of a
computing formalism that does not have that syntactic
feature. This is also true of programming languages, often as an
official syntactic feature called comment, which is not strictly
necessary, but does save time and space.

I recently used the property to prove (hopefully correctly) that all
primitive recursive functions can be implemented as a recursive set of
Turing Machines. This may not be a very deep result, but my understanding from that proof is
that the phenomenon is very general and may have other consequences.

To be precise about definition, I think one could call non-coding part
of a formalism instance those parts that can be identified by a uniform
decision procedure as computationally irrelevant.

Question:
Is the property as general as I make it? Has it been analyzed more
thoroughly, including causes (is it unescapable?), consequences, and
theoretical or practical uses? Does it have a name?

I think that the property could somewhat be implied by general
theorems about computability. But why should that extend to very
simple formalisms like FSA.

My guess is that, given the above definition of non-coding part, it
may be that for simpler formalisms like FSA there is a uniform
recursive procedure that can remove all non coding parts: that
procedure could be made part of the formalism specification, thus
contradicting my universality statement. But such a procedure would
not exist for a Turing complete formalism (Rice theorem?). And the fact remains that even the simpler formalisms we use are defined with this "comment" potential, even if it might be removable by a restriction to normal forms.


texts: Making an algorithm that picks a unique random number in fixed set more efficient

texts:
I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have designed an algorithm that can generate a unique number in a range then check if it isn't in the list of account numbers and then add it to the list.
My Issue is that as the number of available account numbers decreases the more times the algorithm will need to generate new numbers which will create exponential overhead. especially when generating 6+ digit long account numbers.
My solution to this problem was after x number of attempts I would run a second operation that would find all missing account numbers in the list and return one at random. This would work but leaves me with the same problem.
Flowchart of my Algorithm

Country Code is part of the user registration and each country has it's own selection of sortcodes
so the hierarchy is:
CountryCode > Sortcode > Account Number
The only other solution That I can think of that would remove the overhead issue and give me a unique random number in a set, would be to pre-generate the set of numbers in random order and then pick off the top number until the set is empty. However, I'm not sure where this list would be kept when the application isn't running and I feel generating the numbers at runtime would be more suitable.
If you need any further information I will provide.


texts: What extent of difference is considered significant in runtime?

texts: I have a task to test the time required to evaluate a specialised function and a generalized function that aims to get the same output, and conclude whether there is a speed advantage of using one over the other. It turns out that the time in milliseconds differ by roughly 0.835ms. My question is whether a difference of 0.835ms is considered significant in the programming world to be called a speed advantage? If this is insignificant, is there a value that is considered significant so that I have a better idea?


texts: Comparing turing based programming languages

texts: According to Turing thesis, Can we say all programming languages that support turing machine like C have same power for solving problems and performing algorithms? In other words is there any algorithm or problem that one of them can solve it and the other can't?


texts:
A group of computer scientists associated with numerical analyst Yaroslav Sergeyev have published numerous publications recently on a scheme proposed by Sergeyev that uses terms like Infinity Computer, numerical infinitesimal and numerical infinity, claiming that the approach facilitates the solution of many problems.

The mathematicians (including logicians) have been for the most part sceptical but there are a few exceptions, such as Elemer Rosinger and Gabriele Lolli. How have these ideas been received by computer science professionals?

Note. On 19 dec '17 a retraction page was created for this issue.


texts: what is a good source for learning how to design a programming language?

texts: I am trying to find a good resource for learning on how to design and create a new programming language. It seems like a search for books in amazon raises some difficulties, because the vast majority of results are about programming languages, not on how to design them.


texts: The general term for folds is a catamorphism. The general term for unfold is an Anamorphism. Is there an equivalent term for map?  I know that a map is a type of fold however restriction is significant.  Also it would be useful to have an alternative term to use when the word “map” is ambiguous.


texts: What are the k-collections described in ch. 8 of "An Introduction to the Analysis of Algorithms" by Sedgewick

texts:
In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.

My confusion is how to identify the k-collections. A k-collection is defined as:
"to be a word that consists of k different letters with the last letter in the word being the only time that letter occurs"

Exercise 8.6 of the book asks to find all the 2-collections and 3-collections in Table 8.1, where that table shows the configurations of 4 balls in 3 urns

If I give it a try, I'd say a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end, but I'm pretty sure I"m wrong.

Can anybody help providing an example of a k-collection (2 or 3-collection) from Table 8.1? Thanks


texts:
I wrote the worst algorithm in the world.
Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute.
So I concluded that the equation for the number of operations is as follows:

$$n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots + n!\,.$$

Can we fold this sequence to some nice equation which will give us exact number of operations needed to complete this algorithm?


texts: Rice's theorem for non-semantic properties

texts:
Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false).

But there are other properties of Turing Machines that are not decidable. For example, the property that there is an unreachable state in a given Turing machine is undecidable$^{\dagger}$.

Is there a similar theorem to Rice's theorem that categorizes the decidability of similar properties? I don't have a precise definition. Any known theorem that covers the example I have given would be interesting for me.

$^\dagger$ it is easy to prove that this set is undecidable using Kleene's Recursion/Fixed Point theorems.


texts: Finding a small element in a changing array

texts:
Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like.

The array is initialized to zeros.

The goal to to support two operations:

Update(k,v) - sets $A[k]=v$.
Small() - returns an index in which the element is smaller than or equal to the median.

Assuming that finding a small item has to be done in $O(1)$ time, how fast can we perform updates?

Some notes:

You can use preprocessing to initialize any data structure you wish before the sequence of updates starts.
I'm only looking for deterministic algorithms. A randomized algorithm for this problem is trivial.
Making update run in $O(\log n)$ is straightforward (e.g. using a balanced BST).

Can we improve to $o(\log n)$ or show an $\Omega(\log n)$ lower bound?


texts: On deterministic weighted graph isomorphism from randomized

texts:
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$ where $s=\Omega(n^\alpha)$ where $\alpha\in[0,2]$ and the edge weights are picked uniformly. We can think of the second graph as being generated as follows: Input the weighted first graph to a black box and the black box returns the second graph based on some mechanism.

For every $n$ fix a set of weights.

For every input graphs you assign weights uniformly from a distribution. Then you feed in the input graph, weights and the second graph to the black box and the black box returns you the weighted second graph. Then you have to decide isomorphism on these two weighted graphs. So the probability is over all assignments of weights (the weight set is fixed for every $n$ in some worst case way). If this has an algorithm that is in $\mathsf{BPP}$ then in theory it should be conjecturally derandomizable.


texts: Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?

texts:
It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using Tseitin transformation:

$$
Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \Phi \Rightarrow Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \exists x ((\neg{x} \vee \Psi) \wedge \Phi[x/\Psi] ),\ Q_i \in \{ \exists, \forall \}
$$

(For details, see for example here). My two questions are:

Can any formula of the form $\forall z_1 \ldots \forall z_n \exists
    z_{n+1} \ldots \exists z_m \Phi$ be turned into an equisatisfiable
formula of the same form (so beginning with $\forall$ and with just
one alternation of quantifiers) in CNF using Tseitin transformation?
I'm assuming Yes, since Tseitin transformation only adds
existential quantifiers ($\exists$) right before $\Phi$.
Can any formula of the form $\exists z_1 \ldots \exists z_n \forall
    z_{n+1} \ldots \forall z_m \Phi$ also be converted into an equisatisfiable formula of the same form (so beginning with $\exists$ and with just
one alternation of quantifiers) in CNF in polynomial time? I'm assuming No since Tseitin transformation would give us the form $\exists z_1 \ldots \exists z_n \forall
    z_{n+1} \ldots \forall z_m \exists x_1 \ldots \exists x_l \Phi'$ and I'm not aware of any other polynomial time transformation useful in this case.


texts: Solving recurrence equation $T(n)=T(n^{2/3})+17$

texts:
How can the following recurrence equation be solved by one of three main ways:

$$T(n)=T(n^{2/3})+17$$

I have tried solving it by the iteration way. However it does not work for me since I can't find the equation with $i$, i.e the generic equation.


texts:
We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do:

for j=I+1 to N:
  if A[j]<A[I]:
    A[j]=0

The Queries are not independent of each other so we need to use the changed Array everytime.

I have given a lot of thought but was able to come up only with brute force solution with complexity of O(Q*N). Can anyone tell a better solution?

Eg:-

Array- 4 3 4 3 2, Query-3 2
After Query 1(Index 3, element 3)- 4 3 4 3 0
After Query 2(Index 2,element 4)-4 3 4 0 0


texts: Simultaneous buffer access in the bounded buffer problem

texts:
Galvin and various other resources only allow either the producer or the consumer to access the buffer at a time, the common code is as follows:
//Producer code

While(true)
{ down(empty);
  down(mutex);
  buffer[in] = item;
  in = (in+1) % buffer_size;
  up(mutex);
  up(full);
}

//Consumer code

While(true)
{ down(full);
  down(mutex);
  item = buffer[out];
  out = (out+1) % buffer_size;
  up(mutex);
  up(empty);
}

Here empty and full are semaphores which count the number of empty and full buffers. Mutex is initialised to 1, empty to buffer_size, full to 0.
I understand that multiple producers or consumers accessing the buffer at a time results in a race condition, but in my opinion a producer and a consumer can simultaneously access the buffer at a time without any problem. The solution given below seems to be fitting the constraints more precisely, so my question is, is there any problem(bounded wait not being satisfied, race condition, etc) in letting the producer and consumer access the buffer simultaneously like so?
While(true)
{ down(empty);
  down(producer_mutex);
  buffer[in] = item;
  in = (in+1) % buffer_size;
  up(producer_mutex);
  up(full);
}

While(true)
{ down(full);
  down(consumer_mutex);
  item = buffer[out];
  out = (out+1) % buffer_size;
  up(consumer_mutex);
  up(empty);
}


texts:
When I read the word "state" I think of a global object with a bunch of properties like the "application state". But it seems that in automata that the state is pretty much just an empty value.

Wondering what specifically the data structure is for automata states in general.

For example, the following comes from here:

  An alternating register automaton over A consists of: a finite set $Q$ of states with a distinguished
  initial state $q_0 ∈ Q$ and a set of accepting states $F ⊆ Q$, a finite set $R$ of registers, and a transition
  function
  $$δ : Q×A×Tests(\mathscr{R}) → B+(Q×P(\mathscr{R}))$$...

Register automata have a "memory" which I associate with state, but it seems clear it is separate from the actual states in $Q$. Just looking for the data structure for state, if it's just an incremented integer, a string label, or something else, typically.


texts: Are there algorithms for proving two finite state machines are equivalent?

texts: Suppose we call two finite state machines equivalent if they "perform the same computation" - they accept the same language, or they produce the same output for any given input. Is there an algorithm for checking if two finite state machines are equivalent?


texts: Unambiguousness and determinism of CFGs for them to be LR

texts:
I came across this statement:

  Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.

I was guessing what could be the characteristics of such grammars?

Then I came across this question which very well asks:

  Why does there exist a conflict even though it is not ambiguous grammar?

The answer does not give straight answer to above "Why". But definitely says this:

  A context-free language is LR(k) precisely if it is deterministic.

In this context, I have following guessings which I want confirmations for:

All LR grammars are unambiguous, merely because they need to be deterministic and set of deterministic languages is proper subset of unambiguous languages.
In other words, unambiguous languages which are non LR are those which are non deterministic.
Dragon book says we can enforce association and precedence to ensure unambiguousness of grammar by resolving conflicts. I also read that we do left factoring to convert non deterministic grammar to deterministic grammar.
I am quite confused about what actually converts non LR grammar to LR after considering above two sentences and point 2. Is it enforcing association and/or precedence or left factoring. I feel it should be left factoring given determinism is absolutely necessary than unambiguousness and there must exist some ambiguous grammars which do not turn to LR by enforcing association and/or precedence. Am I correct with this?
Left factoring eliminates FIRST-FIRST conflicts in LL grammarref. But does it help to eliminate SHIFT-REDUCE and REDUCE-REDUCE conflicts in LR grammars?


texts: Can I use machine learning/ANNs to predict the outcome of a simulated horse-racing game based in probability?

texts:
I know ML is used in real horse-racing and other sports, where team/player history matters and can be used as a predictor for future games.

What about for "simulated" games, where the outcome is decided by probability?

Here's an example of what I mean:

Suppose there are 3 tracks T1 to T3, and 12 horses H1 to H12. Every week, all 12 horses are randomly assigned to the 3 tracks (4 horses per track) and assigned betting odds, ranging from 2-to-1 to 15-to-1. The horses in a track are also given a random type of feed (e.g. the horses in T1 might be given hay, while the horses in T2 might be given barley. The feed is random per track.)

As the player, you can place up to 8 bets on all 3 tracks. As the week goes on and other players place bets, the horse odds may increase or lower. At the end of the week, the horses race and you win back some money if your bet(s) hit.

In terms of available data, we know:

The starting and current odds of each horse.
The win history of each horse (for example, H1 might win 55-65% of the time).
The overall strength of each horse.
The feed given at each track.
The above data for the past 1000 races, including the winners.

Only the odds are known to influence the outcome of the race for sure. It is unknown if the other variables (history, strength, feed) affect the outcome, or by how much.

I ask because, even though past history is given, there's a good chance the winners are simply decided by the current race's odds rather than by history. Since this is a simulation, the outcome is likely decided by randomly generating a number for each track and seeing what range it falls into.

Given the above information, would this something a machine learning algorithm or neural network could predict reasonably accurately? And if so, what would be a good starting point to look at?


texts: How to compare the output of a neural network with his target?

texts:
I am coding a neural network implementation, but a I have problems in the design. I was wondering about how to compare the output with the target, my neural networks has three outputs

 groups = {'Iris-virginica':[0,0,1], 'Iris-setosa':[0,1,0], 'Iris-versicolor':[1,0,0]}

I know I must translate each output to 0 and 1.

I meant if my result is Iris-virginica and my output is more or less: [0.999979082561091, 0.9999918549147135, 0.9998408912106317], the subtraction would yield the following result:

[-0.999979082561091, -0.9999918549147135, 0.000159]

Is that correct, or I need to follow a different approach. Is possible train my net with 0, 1 and 2 values. Do I need to know any more?


texts: Is Kolmogorov-random nonsensical for small numbers?

texts:
The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string.

Aren't nearly1 all strings shorter than a certain length2 going to be Kolmogorov-random?

If a random Turing machine is chosen, then programs that output short strings will almost always be longer than the strings. If the programming language used for measurement is optimized for outputting a short string, then only the complexity of a subset of short strings can be made lower than their length. For example, if a Turing complete language defines $0$ as an operation that outputs 0 and halts, the program for outputting 1 and halting is forced to be longer than the length of its output.
The exact length below which this occurs will depend on the programming language chosen. The length is 41 bits using 5 state, 2 symbol Turing machines.


texts:
The following is a quote from Sipser's "Introduction to the theory of computation"

  A Turing machine $M$ accepts input $w$ if a sequence of configurations
  $C_{1}, C_{1}, \ldots , C_{k}$  exists, where

  $C_{1}$ is the start configuration of $M$ on input $w$,
  Each $C_{i}$ yields $C_{i+1}$ , and
  $C_{k}$ is an accepting configuration.

The "if a sequence of configurations $C_{1}, C_{1}, \ldots , C_{k}$  exists" is a bit confusing. This is a deterministic TM, so there is only one sequence of configurations for a given machine and word, right? For instance, wouldn't the following do as a definition?

  A Turing machine $M$ accepts input $w$ if the state in the final configuration in $M$'s run on $w$ is an accepting state

Obviously, one has to formally define first what the run of a machine on a given word means.


texts: Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?

texts:
I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.

Is this reasoning correct or is there more to it?


texts: Is is possible to create a SUBSET-SUM instance that each subset is "unique"?

texts: Given a SUBSET-SUM instance $S$ with a weight $W$, is it possible to create, in polynomial time, a new non-empty instance $T$ (at most the same length as $S$) with weight $M$, that for each non-empty subset of set $T$ and its sum $s$, it has a unique $(s-M)^2$, and that a subset of $T$ adds up to $M$ iff a subset of $S$ adds up to $W$?


texts:
In the context of information flow, when you talk about the property of variables being tainted, do you speak about "taintness" or "taintedness"? Both occur online, both sound weird to me.

An example from http://www-verimag.imag.fr/~potet/PUBLI/mdv10.pdf:

  To achieve that, we propose to perform a taint dependency analysis
  whose objective will be twofold: 1) to compute the variable taintness
  at each program location; 2) to extract from the program source the
  whole dependency chains between each vulnerable statement and the
  corresponding inputs leading to this vulnerability.


texts: Transforming a bounded knapsack to 0/1 knapsack

texts:
Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-:

Example: Lets says I have 3 types of items

$n=3$

$p_j=\{10,15,11\}$

$w_j=\{1,3,5\}$

$b_j=\{6,4,2\}$

$c = 10$

Here $n$ denotes the number of types of items, $p_j$ denotes the profit gained by including 1 item of a that particular type, $b_j$ denotes how many items of a particular are available. And $c$ denotes the total capacity of the knapsack.

So for each item of a particular type I transform the item by including all the various ways of adding it, so for the first item, since there are 6 of them I include in my transformed array all 6 ways of taking them ie. $(1,1*p_j),(2,2*p_j)..$ and so on. Example, the expansion of the first item would be:

$(1,10),(2,20),(3,30)...(6,60)$

So now the expanded array would contain $6+4+2=12$ elements.

Now if I use that against the standard dynamic programming approach for 0/1 knapsack problem would I be able to get the optimal solution ?

This text(page 3) introduces an algorithm that converts a bounded knapsack to 0/1 knapsack by adding $\sum_{j=1}^n \lceil log_2(b_j + 1) \rceil$ terms for each item. I am just wondering why that even works ?

An extract from the text reads the following:

  Notice that the transformations introduces $2^q$ binary combinations.

Can someone tell me how that works ? And if the above described way actually can lead to the optimal solution.


texts: Complete the following table by specifying the scope of each declaration

texts:
I'm having a hard time understanding this question. Can each declaration have more than one scope or can a declaration have more than one scope?

If it's the later it would be:

Declaration              Scope
int a = 1;               B1
int b = 1;               B1
int b = 2;               B2
int a = 3;               B3
int b = 4;               B4

Or can it have more than one scope:

Declaration              Scope
int a = 1;               B1, B2, B4
int b = 1;               B1
int b = 2;               B2, B3
int a = 3;               B3
int b = 4;               B4

I'm sorry if this is a simple question. I just want to make sure what I'm doing is correct.

Thanks.


texts: UV Projection of 3D shape onto 2D images

texts: Given a 2D image of a human face and the corresponding 3D shape, how do I project the shape onto the images to extract texture patches from them to form a partial UV map?


texts: Quantum Computing - Relationship between Hamiltonian and Unitary model

texts:
When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone, Guttman) - work by designing a Hamiltonian and some initial state, and then letting the system evolve according to the Schrödinger equation for some time $t$ before performing a measurement.

Other algorithms - such as Shor's Algorithm for factoring - work by designing a sequence of Unitary transformations (analogous to gates) and applying these transformations one at a time to some initial state before performing a measurement.

My question is, as a novice in quantum computing, what is the relationship between the Hamiltonian model and the Unitary transformation model? Some algorithms, like for the NAND tree problem, have since been adapted to work with a sequence of Unitary transformations (Childs, Cleve, Jordan, Yonge-Mallo). Can every algorithm in one model be transformed into a corresponding algorithm in the other? For example, given a sequence of Unitary transformations to solve a particular problem, is it possible to design a Hamiltonian and solve the problem in that model instead? What about the other direction? If so, what is the relationship between the time in which the system must evolve and the number of unitary transformations (gates) required to solve the problem?

I have found several other problems for which this seems to be the case, but no clear cut argument or proof that would indicate that this is always possible or even true. Perhaps it's because I don't know what this problem is called, so I am unsure what to search for.


texts:
Does this problem have a solution with $o(n^2)$ time complexity?  If so, what would be an example of such a solution?

  Given $N$ integers in the range $[−50\ 000,\ 50\ 000]$, how many
  ways are there to pick three integers $a_i$, $a_j$, $a_k$, such that $i$,
  $j$, $k$ are pairwise distinct and $a_i + a_j = a_k$? Two ways are
  different if their ordered triples $(i,j,k)$ of indices are
  different.

I have come up with a $\theta(n^2)$ solution, but it exceeds the specified time limit for the ninth test.  I believe I could parallelize my $\theta(n^2)$ solution using multi-threading, but that is generally not in the spirit of the problems on this website.  That is what makes me think there is a $o(n^2)$ solution.  However, I have not been able to come up with a faster solution myself using either divide-and-conquer or dynamic programming.


texts:
I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?" I believe that the answer is NO, however, the Theorem 5.30 states something different.

There are two problems concerned in this question. One is $A_{TM} = \{ <M,w>\ |\ M \text{ is a TM and accepts } w\}$ and the other is $EQ_{TM} = \{ <M_1,M_2>\ |\ M_1, M_2 \text{ are a TMs and } L(M_1) = L(M_2)\}$.

On Page 238, the Theorem 5.30 is stated as follows:

  Theorem 5.30 $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.

The proof is by mapping reduction of $A_{TM}$ to $\overline{EQ_{TM}}$, and at the same time, reduction from $A_{TM}$ to $EQ_{TM}$. This way, it has shown:

$\overline{EQ_{TM}}$ is Turing-undecidable.
$EQ_{TM}$ is Turing-undecidable.

Note that this reduction does not show that either of $\overline{EQ_{TM}}$ or $EQ_{TM}$ are not Turing-recognizable, since $A_{TM}$ is Turing-recognizable.

On the other hand, on Page 209, we have the following definition

  A language is co-Turing-recognizable if it is the complement of a Turing-recognizable language.

which is accompanied by Theorem 4.22:

  Theorem 4.22 A language is decidable iff it is Turing-recognizable and co-Turing Recognizable.

Therefore, we can obtain the following Corollary: If a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable.

Therefore, it is shown on Theorem 5.30 that $\overline{EQ_{TM}}$ and $EQ_{TM}$ are Turing-undecidable. This does not tell me anything more than the following proposition:

  Either $EQ_{TM}$ or $\overline{EQ_{TM}}$ or both are not Turing-recognizable.

However, the Theorem 5.30 states something stronger.

Am I missing something?


texts: what is the relationship between increasing the number of cores and scalability?

texts:
Whenever I increase the number of cores the speedup will increase. with this increasing can I consider the system as scalable?

I mean based on the speedup obtained for a different number of cores e.g. 10,20,30, is the system scalable with the increase of cores?


texts:
I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my robots so that they all control a comparable part of the area.

I was looking at Voronoi diagrams but I cannot find how to determine the location of the points.

Sorry if this is not very clear, I am not even sure what I am looking for.


texts:
In a simple architecture(not considering parallel architecture) how exactly this can be performed in a single clock cycle:
P:R1 <- R2, R2 <-R1
where R1 and R2 are registers and P is a control variable.

I do not exactly understand when does this microoperation gets completed on the rising edge of the beginning of the cycle or just before clock transition.


texts:
This question is from my complexity theory course.

  How to change the standard DPLL algorithm for SAT in order to solve 3-SAT
  instances?

The general DPLL algorithm for SAT is defined:

Algorithm DPLL
  Input: A set of clauses Φ.
  Output: A Truth Value.
function DPLL(Φ)
   if Φ is a consistent set of literals
       then return true;
   if Φ contains an empty clause
       then return false;
   for every unit clause l in Φ
      Φ ← unit-propagate(l, Φ);
   for every literal l that occurs pure in Φ
      Φ ← pure-literal-assign(l, Φ);
   l ← choose-literal(Φ);
   return DPLL(Φ ∧ l) or DPLL(Φ ∧ not(l));

I know that a 3-CNF formula $F$ belongs to 3-SAT if $F$ contains only clauses with 3 literals. But i don't know how to modify DPLL in order to run faster for 3-SAT


texts: Applying Master Theorem to: T(n) = T(n - 2) + n^2

texts:
I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:

T(n) = T(n-2) + n^2

Am I wrong in thinking that I cannot apply Master Theorem to this equation? If it can be applied, I am unsure how, as the variable T(n-2) gives no value for "b" which would usually be used to solve with master theorem.

If it can be solved with Master Theorem, how would it be solved? If it cannot be, how would one go about solving this specific recurrence relation?

Thank you in advance for any help and clarification!


texts:
We are given the following letters with the respective frequencies:

\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{matrix}\end{equation*}

For that I have applied the Huffman code and I got the following tree:

Now it is asked for the total weight of the code. How do we calculate that?

Do we maybe use the formula $\displaystyle\sum_{c\in C}f(c)d(c)$ ?

Then we have $$2\cdot 4+3\cdot 4+5\cdot 3+6\cdot 3+7\cdot 3+4\cdot 4+4\cdot 4+8\cdot 3+10\cdot 3+11\cdot 3=193$$ Is that correct?


texts: How to find an axis-aligned hyper box whose set of integer points minimizes Jaccard distance to a given finite set of points $X \in {\mathbb Z}^d$?

texts:
So I saw this question posed on math.se for $d=3$. Suppose we are given a finite set $X \subset {\mathbb Z}^d$ of $n$ points. The goal is to find a hyper box of integer points $ B = [k_{1,1},k_{1,2}] \times [k_{2,1},k_{2,2}] \times \ldots \times [k_{d,1},k_{d,2}] $ so that the Jaccard distance $d(X,B)$ is minimized. The Jaccard distance is $d(X,B) = 1 - |X \cap B| / |X \cup B|$.

So obviously we can just restrict the range of the box to be defined by coordinates of points in $X$ in the appropriate dimension. So there are "only" $O(n^{2d})$ boxes to check. Furthermore, the Jaccard distance can be computed in constant time if $|X \cap B|$ is known, because $|X|$ is known and $|B|$ is easily calculated.

So, since the original problem was formulated for $d=3$, it occurred to me that the computation of $|X \cap B|$ could be reduced to $O(\log ^{d-1} n)$ time (instead of naïve $O(n)$ time) using a modified layered range tree that returns counts of points that satisfy a given range query.

However, I could not think of any way to avoid testing all possible hyper boxes, especially if $X$ is dense. Thus my speed-up is very minor compared to the overwhelming complexity of checking all boxes. Is there a way to speed up to better than $O(n^{2d} \log^{d-1} n)$ time, and if nothing else, at least in certain cases, like if $X$ is dense or sparse?


texts: Different between left-most and right-most derivation

texts:
I am a beginner started learning theoretical computer science. I just came through context-free grammars.

So my question is: what is the different between left-most and right-most derivation?

Because both of them gave me the same parse tree.


texts: If a sparse language is NP complete, then are all languages in NP in P/poly?

texts: If a Sparse Language is NP complete, then are all languages in NP in P/poly? I know that sparse languages are in P/poly, but does a polynomial time reduction give an addition to the circuit that is super polynomial? A sparse language is such that $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n} | \leq p(n)$ for some polynomial $p(n)$.


texts: LP formulation and integer solution existance

texts:
I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix.

We have $m$ pieces of contiguous land parcels $\{1,...,m\}$ and $n$ agents with a simple valuation function that assigns $0$ to all the subset of parcels but $S_i = \{l,l+1,l+2,...,k\}$ for which it assigns $v_i(S_i)$. We would like to find such an allocation of agents to the parcels that maximizes welfare (sum of obtained values).

Let’s define $S=\{S_1,S_2,...,S_n\}$. My try for a relaxed LP is as follows:
$$\max \sum\limits_iv_i(S_i)*x_i\\
s.t.\\
x_i\leq 1 \ \forall i\\
\sum\limits_{x_i: S_i\in T} x_i\leq 1\ \forall T\subseteq S: \cap T \neq \emptyset, T \textrm{ is maximal}\\
x_i\geq 0$$

First off, is it the correct formualtion? I add the second constraint to mean „for each set of agents with contiguous set of parcels that share at least one parcel, and which is a maximal set with that property, only one agent at most can get its desired plot of land”. In other words, I sum $x_i$’s of those agents who chose their subset of lands sharing at least one plot. I do not want repetetiveness so I only take maximal amount of agents with that property each time.
The other constraints are just relaxed constraint in $x_i$ which means that either agent $i$ gets his desired set or not.

Secondly, I do not really see why would constraint matrix be totally unimodular. It will have an identity matrix in is upper part and sth that cannot be specified in general in its bottim part. Perhaps there’s some simpler LP formulation that I haven’t thought of?
I must add I did not leverage the form of the sets valued by the agents anywhere, so it can be that I am missing something.

I kindly ask for your help.

Example:
We have $3$ plots of land $\{1,2,3\}$ and $3$ agents with valuations $v_1(\{1,2\})=2$, $v_2(\{2,3\})=3$, $v_3(\{3\})=2$, so $S_1=\{1,2\}$, $S_2=\{2,3\}$, $S_3=\{3\}$. Then the corresponding LP is
$$\max v_1(S_1)*x_1 + v_2(S_2)*x_2 + v_3(S_3)*x_3\\
s.t.\\
x_i\leq 1 \ \forall i\\
x_1 + x_2 \leq 1\\
x_2 + x_3 \leq 1\\
x_i\geq 0$$
The contraints mean that "at most one from $S_1$ and $S_2$ can be chosen and at most one from $S_2$ and $S_3$".


texts: Can an FO formula with infinite length be expressed with an infinite set of finite formulas?

texts:
I'm confused as to why we can't write formulas of infinite length in FO. For example, to express reachability, I understand the proof that there cannot be a single formula for it, but it is expressible with a set of formulas?

Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

On the other hand, can an infinite set of finite formulas be joined by conjunctions to obtain an equivalent formula of infinite length?


texts: What is an intuitive way to explain and understand De Morgan's Law?

texts:
De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms.

Is there a more intuitive explanation for why this works rather than just remembering truth tables? To me this is like using black magic, what's a better way to explain this so that it makes sense to a less mathematically inclined individual?


texts: Why do we have different algorithm for MST when graphs are directed?

texts:
What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ?
What cases are not covered in using Prim's algo for finding MST for directed input?


texts: Types of reductions and associated definitions of hardness

texts:
Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. The types of reductions:

Turing reduction: $M_{A}$ can make multiple queries to $O_{B}$.
Karp reduction: Also called "polynomial time Turing reduction": The input to $O_{B}$ must be constructed in polytime. Moreover, the number of queries to $O_{B}$ must be bounded by a polynomial. In this case: $P^{A} = P^{B}$.
Many-one Turing reduction: $M_{A}$ can make only one query to $O_{B}$, during its the last step. Hence the oracle response cannot be modified. However, the time taken to constructed the input to $O_{B}$ need not be bounded by a polynomial.
Equivalently: ($\leq_{m}$ denoting many-one reduction)

  $A \leq_{m} B$ if $\exists$ a computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

Cook reduction: Also called "polynomial time many-one reduction": A many-one reduction where the time taken to construct an input to $O_{B}$ must be bounded by a polynomial.
Equivalently: ($\leq^{p}_{m}$ denoting many-one reduction)

  $A \leq^p_{m} B$ if $\exists$ a poly-time computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

Parsimonious reduction: Also called "polynomial time one-one reduction": A Cook reduction where every instance of $A$ mapped to a unique instance of $B$.
Equivalently: ($\leq^{p}_{1}$ denoting parsimonious reduction)

  $A \leq^p_{1} B$ if $\exists$ a poly-time computable bijection $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

These reductions preserve the number of solutions. Hence $\#M_{A} = \#O_{B}$.

We can define more types of reductions by bounding the number of oracle queries, but leaving those out, could someone kindly tell me if I have gotten the nomenclature for the different types of reductions used, correctly.
Are NP-complete problems defined with respect Cook reduction or parsimonious reduction? Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

If I am not wrong, the class #P-Complete is defined with respect to Karp reductions.


texts: Language of all strings that has exactly 1 triple b

texts:
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.

Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.

Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.


texts: Using function composition to turn a function into point free one

texts:
In Tacit Programming page on wikipedia, it is stated that the point free version of

p x y z = f (g x y) z is
p = ((.) f) . g

and that the point free version of

mf criteria operator list = filter criteria (map operator list) is
mf = (. map) . (.) . filter.

I can not figure out how can we get from one side to the other, in either way. Would you please show me a step by step explanation of why those equivalences hold?


texts: Examples of Context-sensitive grammars which produces non-indexed language

texts:
Well known example of Context-sensitive grammar which produces language $\{a^nb^nc^n|n\geq 1\}$ is widely used in various papers. But actually, while this language is definitely context-sensitive, it is also belongs to smaller subset of CS-languages: it is indexed language, because it can be described with indexed grammar as well.

What I'm looking for, it is example of Context-sensitive grammar which produces non-indexed language. From this paper it is known that language $\{(ab^n)^n|n\geq 1\}$ is not indexed. But there is no described grammar for this language.

So could somebody describe CS-grammar for given non-indexed language example, or provide with any other example?


texts: Complexity of forming a min heap out of a given array with k inversions

texts:
If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly higher than its descendant (all nodes have distinct key values).

This isn't an interview question, but is something that I thought of while learning about heaps. Searching for it on google gives zero hits.

Back when we learnt arrays and how to sort them, we were told that sorting arrays requires $\mathcal{O}(n + k)$ ($k$ = number of inversions) time complexity in insertion sort. I wonder if something similar exists for making a heap out of a given array.

I attempted to approach this problem in the following way. Assume a full binary tree (one with number of nodes equal to $2^h - 1$ ($h$ = height)). Note that we perform the sift down operation only when there exists an inversion. In the best case, the input array is already sorted so complexity is just order $n$, no sift downs are performed. In the worst case, input array is reverse sorted, so each internal node needs to be sifted down. That's summation of $\frac {(n + 1)}4 + \frac {(n + 1)}8\cdot2+\frac {(n + 1)}{16}\cdot3+\ldots= n-1$ siftdowns (solving it as a arithmetico geometric sequence) in the worst case, plus having to loop through the entire array .

In a more general case, I would say that we are visiting each node internal node once, performing a comparison with its children for cost $c$, and if it is out of place, perform a siftdown for additional cost $d$. If $i$-th internal node undergoes siftdown $k_i$ times, then we can formulate the total complexity as:

$$=\sum_{i=1}^{(n + 1) / 2}(c\cdot(k_i+1) +d\cdot k_i)$$

(as you always perform comparisons one more time than total number of siftdowns, except when you reach leaf node, which I approximated away)

This gives us:

$$=(c+d)k+\frac{(n+1)}2\cdot c$$

This suggests to me that that in worst case reverse sorted array, the order should be $n^2$, as the number of inversions $k$ is of that order. However, that we already know is not the case. Where is my analysis going wrong then?


texts:
Can anyone show me step by step how to do a proof on self referential structures.

For example, this example is in scala

lazy val y : Stream[Int] = 1 #:: (y map (_ + 1))

How do I prove that y is a stream of natural numbers. #:: is stream cons in scala.

Also this example is from wikipedia

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

How do I prove fibs is a stream of fibonacci numbers.

I'd really appreciate if someone over here can spell out a nice detailed proof step by step for me. I don't really see how to apply inductive reasoning to any of the above.


texts: For a cycle with $n$ vertices, how many distinct chords are possible?

texts:
Note: This is almost certainly an elementary problem with a well known solution. Therefore pointers to existing references will be accepted as good answers.

  Question: Given a cycle with exactly $n$ vertices, how many distinct chords are possible?

This question is motivated by the definition of chordal graph, which only requires the cycles in the graph to have chords if the cycles have four or more vertices.

Doodling on paper I realized that this is because, for the smallest possible number of vertices in a cycle, namely three, the existence of a chord is impossible. But as soon as the cycle contains at least four vertices the existence of a chord is possible.

For the four-vertex cycle, it seems that there are only two possible chords. Since a chord is formed between two distinct vertices in a cycle, and $2$ might be the first term in a sequence of coefficients of the form $\binom{f(n)}{2}$ for some $f(n)$, I thought that the solution might be similar to the handshake problem and involve $\binom{n}{2}$ or $\binom{n-1}{2}$ somehow.

But this seems to fail already when $n = 5$, because instead of getting $\binom{4}{2} = 6$, which I had expected, instead I counted 5 distinct chords. So then I thought that maybe the answer is the Catalan numbers, since after $1$ they start with $2,5,\dots$, have a form similar to the $\binom{n}{2}$ from the handshake problem, and show up in all sorts of unexpected places.

But this conjecture also fails, since for the cycle with $n=6$ vertices I counted 9 (or maybe 8) distinct chords, and this obviously isn't the third non-unit Catalan number 14, nor is it $\binom{5}{2} = 10$. I somewhat expect the numbers/sequences to differ for odd and even number of vertices however, for a reason analogous to why a graph is Eulerian if and only if each of its vertices has even degree.

I would like to know the answer not only out of sheer curiosity, but also for some intuitive insight into how one can then go on to count the number of possible chordal completions of a graph (which one then uses to calculate the treewidth) -- that is all outside the scope of this question however.


texts: All strings in which every substring 000 appears after every 1

texts:
I found this given problem as follows:
Write a regular expression where all strings in which every substring 000 appears after every 1.
Now, I also found the answer from Illinois university study material which is available online. The given answer is as follows:
(1+01+001)*0*
However, I think this is not the correct answer as the RE can generate the given strings as 1, 10, 1010010 and so many. So the RE is not properly justified to the given problem.
Please, help me to get the correct information. Thanks for your kind consideration.


texts: 'Traders's Route' problem optimization algorithm

texts:
I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know).  Say there exist N cities, with some arbitrary distance d between each city (not all need be the same distance), and as a trader, you want to make the most money possible in one day.  You've figured out you can travel at most D units before the day ends, so we have a total distance restriction.  Each city has a merchant which is willing to buy and sell items to you, and you've already figured out in advance that for any city, you have a set priority list pertaining to each city of which items to buy, and in what order, with every item on every list decreasing in potential profit value (each merchant need not have the same number of items for sale).
Now, how the problem works is that you start at some city C1 and buy item #1 from your priority list pertaining to C1, which if you sell at another city will net you a relative profit of P1 , you then travel to another city (exhausting the distance d between them so now you can travel at most D - d), sell the item from C1 and purchase item #1 from C2 with its own profit of P2.  You continue traveling city to city, exhausting items from each merchant until you're unable to reach another city before the day ends.
NOTES: Every merchant will buy every item you bring them. You can revisit cities.  You can visit a city with no more items to sell and they still buy your items from you, but you leave that city empty handed.  You cannot sell items to the merchant you bought them from.  You can only take one item at a time. You are given all relevant information regarding the profits of items, which items you'll buy if you visit each city and in what order, etc.
Given all of D, N, the P's of each item, your starting city, the distances between each city, and your priority purchasing list for each city, the problem is now determining your route in advance as to maximize total profit (P1 + P2 + ...).
I am in fact looking for an algorithm to solve this in any way faster than brute-force. I've tried to think of a way using dynamic programming to no luck, so implementing this in a non-brute-force fashion has so far has resulted in failure, and am curious if anyone else has the skills and background to create an algorithm that isn't just running through every combination.  I believe this problem to be NP complete, though I haven't attempted proving it.  Many thanks to all who read, and doubly so to those who'll attempt a solution.  Any help, ideas, or questions are appreciated.


texts: Regularity condition in the master Theorem in the presence of Landau notation for f

texts:
There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition is satisfied when f is only provided as a $\Theta(g(n))$, which is actually what happens most of the time when we don't want to bother detailing the exact expression for $f$.

From my understanding, I believe that nothing can be assumed without additional information on f. In the example provided on wikipedia of $T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos{n})$ we have $f(n) = \Theta(n)$ since $(2 - \cos{n}) \in [1, 3]$. Yet $f$ does not satisfy the regularity condition and we therefore cannot deduce that that $T(n) = \Theta(n)$.

Going down the definition of $f(n) = \Theta(g(n))$, we have $n_0 \geq 0$, $c_0 > 0$ and $c_1 > 0$ such that for every $n \geq n_0$ $c_0 g(n) \leq f(n) \leq c_1 g(n)$. Let's assume $g(n) = n^c$.

Given a Master Theorem instance of $T(n) = aT\left(\frac{n}{b}\right) + \Theta(n^c)$, we are in case 3 of the Master Theorem when we have $a < b^c$. Now to check the regularity condition we need to check that $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k < 1$. We therefore have that for $n \geq n_0$
$$
  \begin{aligned}
    af\left(\frac{n}{b}\right)
      &\leq a c_1 g\left(\frac{n}{b}\right)\\
      &\leq a c_1 \frac{n^c}{b^c}
  \end{aligned}
$$
and
$$
  \begin{aligned}
    kf(n)
      &\geq k c_0 g(n)\\
      &\geq k c_0 n^c
  \end{aligned}
$$
assuming $n > 0$, we therefore need that
$$
  \begin{aligned}
    k c_0 &\geq \frac{a c_1}{b^c}\\
    k &\geq \frac{c_1}{c_0}\frac{a}{b^c}\\
  \end{aligned}
$$

In the Wikipedia example, we have $\frac{c_1}{c_0} = 3$ and $\frac{a}{b^c} = \frac{1}{2}$. We would therefore need that $k \geq \frac{3}{2}$ which contradicts $k < 1$.

Now when $f$ just comes out of a loop intrication without inner tests that would make the worst and best cases different, $f$ is a polynomial, and we just use its dominant power as a $\Theta$. I believe what saves us is that we can choose the $n_0$ in the Landau notation, and by increasing it we can have $\frac{c_1}{c_0} < \epsilon$ for any $\epsilon > 1$. And since $\frac{a}{b^c} < 1$, we can always find some $n_0$ such that for any $n \geq n_0$, the regularity condition is satisfied.

Is this sound ? Can we use the generalized Akra-Bazzi Theorem to just not bother ?


texts: How to map the tapes of a single tape Turing Machine into a “2-tape” Turing Machine which has only an initial state and an end state

texts: so i am struggling with demonstrating that every single tape TM can be simulated by a 2 tape TM with only two states. I don't really understand how we can prof this with only 2 states.


texts: Space complexity of a variant of st-connectivity

texts:
Consider a variant of STCON, called 2STCON, which is defined like this:
$$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$
This means the only difference to the "normal" STCON is that there are two paths instead of just one between $u$ and $v$.
I need to show that 2STCON belongs to NL.
What is the  best way to approach this problem?


texts: XOR of three integers where each pair's XOR is the other integer

texts:
I have three positive integers, a, b, and c. I know that $a\oplus b\oplus c=0$, so I got that each pairwise xor has to be the other positive integer. $a\oplus b=c$, $b\oplus c=a$, and so on, but I can't find a, b, and c.

There are lots of solutions, (I'm pretty sure), I'm just trying to code a quick way to find all of the solutions


texts: What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

texts:
How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches and the number of transitions?
An NDTM has a finite number of states, a finite number of input symbols and a finite number of transitions--but presumably the number of branches used grows as you feed larger and larger strings to it--how, mechanically, does this work?
if the number of branches keeps growing as word size grows does this not imply an infinte number of transition rules need be spelled out in the definition of NDTM (since there are an infinte number of word sizes) or do # of transition rules and # of branches not have a one-to-one relationship like this?


texts: Show that there are infinitely more problems than we will ever be able to compute

texts:
I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot follow his reasoning, in practice what he says is this:
we can state a decision problem as string of $0$ and $1$ which in practice is the truth table of the function.
He goes on to say that a decision problem is an infinite string of bits while a program is a finite string of bits and up to here no problem. What I don't understand is the continuation of the proof from this point on: Decision problems are in $\mathbb{R}$ cause you can put a decimal point before the string representing the problem, thus obtaining the decimal part of a real

 for example if you have 0111011010101010101... it could become x.0111011010101010101...

A program is "just" an integer in $\mathbb{N}$ cause it is a finite string of bits. The point that I fail to understand is how it is possible that a decision problem is comparable to a real number instead of an integer ... I mean, if we use the argument of "put a dot in front of the number" could not the same reasoning also be applied to the number of possible algorithms that can ever be produced?


texts:
This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.

Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, and there is a destination vertex which we do not know, until we reach that vertex. The task is to find out the destination, with in the smallest number of steps.

The brute force way will be traversing the entire graph which we must reach the destination as it is connected. However we want to improve this due to the following information: Each vertex has its own coordinates which is known. Upon reaching a vertex, including the starting vertex, we can know the relative direction of the destination from the current vertex, calculated by the coordinates differences. So we can use this information to eliminate some impossible vertexes and narrow down the target.

Is there any suggestion for the algorithm?

I can think of a naive way is to assume each possible vertex (given the hints obtained) are equally-likely, and I want to minimize the expected number of steps (i.e. each edge has equal weight). I can look for each of the neighboring vertex, and compute the distance between each possible destination to the neighboring vertex and sum them up (i.e. getting average). And we choose to move to the one with the lowest sum.


texts: Why don't hard drives actually delete data?

texts:
As far as I understand it, when you delete a file from trash/recycle bin the file isn't actually erased from memory but is instead marked as being okay to be over written.

So, my question is as to why this is the case. Is it simply for speed/convenience reasons or is actually deleting data just a much harder (or impossible) thing to do?

I ask because of the potential security vulnerabilities, such as reselling older hardware and etc.


texts: How does one go about designing a system that never crashes?

texts:
I read somewhere that the Apollo Guidance Computer was designed in such a way, that, although it is hugely less powerful than the average smartphone, it was dependable to the point that it "never crashed". My questions pertaining to this were:

Is designing such a digital system possible, even in the '60's ?
What are the constraints that one would want to look out for when attempting to design such a digital system that "never crashed", using today's technology?


texts: What's the definition of a (deterministic) formal language?

texts:
Definitions

According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses is deterministic. According to him it means "strictly predictable", which means its only interpretable in a single way. So one input can't map to two outputs.

Confusion

If I'm given any example of a language that humans invented, I can't tell nor elaborate whether it's a formal language or not. Some of these examples are natural languages (English, French, Dutch, etc.), UML, Math, notesheets, programming languages, markup languages, braille.

In my teachers powerpoint presentation, he explained a natural language is not formal because it's dependent on context (Unless I understand the definition of "deterministic" wrong, deterministic is the opposite of context dependency. By context dependency I mean, a sentence or a word can have two different meanings, e.g. You were right. But also Make a right turn at the light Thus a natural language is not deterministic).

But then a few slides later he said a formal language doesn't have to be deterministic, which makes me wonder why he would use context dependency as an argument to explain formal languages in the first place.

Question

What makes a language formal? Perhaps you can elaborate by using the examples given above. And what makes a language deterministic? Is it correct that deterministic is the opposite of context dependency?

N.B.
Wikipedia isn't making much sense to me, and I've read that the article about formal languages is quite a mess because people have different opinions on it.


texts:
Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?

I do not mean that the input is the infinite set of positive integers. Think of the input as coming on a single wire carrying a non-negative integer.


texts: Proving the equivalence of an LTL and a CTL formula

texts:
For a lecture I am attending, we have to prove that

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big).$$

That is, we need to prove that for the CTL formula $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$, the LTL formula $\big(a \textsf{U} (b \land \square a)\big)$ is equivalent to it. I know how I would go about trying to disprove it, that is, by providing a transition system that fulfils one but not the other, but I am at a complete loss about how to prove something like this.

Note that we use $\square$ instead of $\textsf{G}$.

Edit:

I managed to prove $$\big(a\textsf{U}(b\land\square a)
\big) \equiv \square a \land \lozenge b$$ if that's any help.


texts: Why are some programming languages "faster" or "slower" than others?

texts:
I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I have a few question regarding this:

Why does this happen?
What governs the "speed" of a programming language?
Has this anything to do with memory management?

I'd really appreciate if someone broke this down for me.


texts: Is complement of diagonal language countable?

texts: I tried to find out how to arrange the complement of diagonal language, but I failed. So I'm about to believe that it's not a countable language. Could you, please, help me?


texts: Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language?

texts: Is the complement of every semi-decidable language a semi-decidable language?


texts: Translation of natural language to logic

texts: Given a statement in natural language, what can be said about how many possible translations there are in first-order-logic? What happen if we take a more complex logic like second-order logic and what if we take a less complex one?


texts: Best data structure for storing an ordered list, where each item is located on a separate server?

texts:
I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible.

The first idea was to implement a basic linked-list where each item of the list is an RSS item. Being on the network, this means that to retrieve the latest 10 feed items, I need to wait sequentially until each node returns from the network (so that I can follow the pointer to the next item in the linked list).

Skip lists make this more concurrent as each node also gives me back pointers to other portions of the list and I can request more items in parallel.

However, I'm looking even further for something that follows more closely my users need: there will be more requests of the latest portion of the feed rather than the older portion. With this requirement in mind, I'd be looking for a structure that can perhaps allow me to achieve higher concurrency closer to the head of the list (where latest feed items are), and less concurrency (with more sequential properties) as users get towards the end of the list.

My thinking is that skip lists achieve the same level of concurrency across the entire list, so perhaps there's something I can use to make it "very concurrent" at the beginning and "less concurrent" at the end rather than "same concurrency" all along.


texts: Why do we believe that PSPACE ≠ EXPTIME?

texts:
I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME.  If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, then how can there be a class of problems that experience greater exponential time blowup and do not make use of exponential space?

Yuval Filmus' answer is already extremely helpful.  However, could anyone sketch my a loose argument why it might be the case that PSPACE ≠ EXPTIME (i.e. that PSPACE is not a proper subset of EXPTIME)?  Won't we need exponential space in order to beat the upperbound for the total number of system configurations achievable with space that scales polynomially with input size?  Just to say, I can understand why EXPTIME ≠ EXPSPACE is an open matter, but I lack understanding regarding the relationship between PSPACE and EXPTIME.


texts: Is finding arbitrary length cycles in a graph NP-Hard?

texts: My intuition says yes. I think so because if we could find arbitrary length cycles, couldn't we just look for an n length cycle and then solve HAM-CYCLE? But I saw a post that seems to suggest a polynomial time method for finding cycles! I feel as if perhaps I do not understand something here.


texts: Factorial usage within proof using the pumping lemma

texts:
We are going over the pumping lemma in class and we recently went over the following example:

Let
$$ L = \{ w \mid w \text{ has a different number of 0s and 1s} \} $$
Consider
$$
s = 0^P1^\left(P+P!\right)
$$
$ s $ can be divided into $ s = xyz $
Consider
$$
y = 0^m; 0 \leq m \leq P
$$
Let
$
i = \frac{P!}{m} + 1
$

$$
xyz = 0^\left(P + \left(i - 1\right)m\right)1^\left(P + P!\right) \notin L
$$

Forgive me if the example is not put together well. This example didn't quite get finished in class. Feel free to expand on this if need be.

However, my question is how does one know to use a factorial in the first place when approaching this proof?


texts: Efficient algorithm for finding weakly connected components

texts:
We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to search a bit to actually find the term).

The most obvious solution would be to do a BFS or DFS on all unvisited nodes and the number of connected components would be the number of searches needed. This is actually what Wikipedia suggests for weakly connected components, too.

My question is if there is a known algorithm that can find these components faster? Or is the BFS/DFS version fast enough (not sure exactly what for)?


texts: Proving that CFLs are closed under even-ness using grammars

texts:
This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2.

  Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the strings in $L$ that have even length. Then $L_{even}$ is context-free.

The question is to prove this theorem using two of three different methods: using grammars, PDAs, or a theorem about language intersections.

I can very easily find a proof using PDAs (maintain your current odd/even status using the stack), and intersections (intersect with $\Sigma^*_{even}$, which is regular) - but I can't think of how to do it using properties of grammars. I suspect either Chomsky or Greibach Normal Forms comes in handy here but I'm not sure how.


texts: Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

texts:
The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$,
The reason for this bound is that those algorithms are using the division by two devide and conquer method and as such they generate a binary tree that begins at a root and from there on branches two times from each node until it reaches the bottom to produce exactly $n$ leaves at the bottom level.
Since it is a binary tree, it has exactly $log_{2}(n)$ levels from the root down to the leaves and as such it costs $log_{2}(n)$ "computational decisions" to generate the tree and $n$ decisions to walk over all leaves, so $n*log_{2}(n)$ looks absolutely valid at first.
I don't argue about the factor $n$ before the $log_{2}(n)$,  what I argue about is,  why is it everywhere such a strict advocating consensus about to always use $log_{2}(n)$ in computer science.
Imagine for example instead if I don't use the binary devide&conquer method, but if I adress the indices of the list which are prime numbers, using the values of those indices as representational values to compute the differences of the indices between the primes. The resulted tree structure from such an algorithm will have many more branches than two at most of the nodes and the generated tree size will be much much lower.
An computational approximation of an list with 1000000000 and the assumption of having 10 splits instead of two would result in 270 times less computational decisions when the $log_{10}(n)$ insead of the $log_{2}(n)$ would be used and I'm quite confident that this can be relaxed to an even much smaller tree in general, if I'm not oversimplifying it at least.


texts: Maximal Matching of nodes that fall into four categories

texts:
Nodes have values. Node n's value is denoted n.val. Two or more nodes can have the same value.

A node n is a category 0 node or more simply a '0' node iff n.val % 4 == 0.
A node n is a 1 node iff n.val % 4 == 1.
A node n is a 2 node iff n.val % 4 == 2.
A node n is a 3 node iff n.val % 4 == 3.

Nodes can be matched as follows:

Two nodes which have the same value cannot be matched.
a 0 node can be matched to a 1 node, a 2 node, or a 3 node. We will abbreviate this fact as (0 | 1,2,3 ).
a 1 node can be matched to a 0 node, a 2 node, or a 1 node as long as both nodes don't have the same value. Using our abbreviation, ( 1 | 0,1,2 ).
a 2 node can be matched to a 0 node, a 1 node, or a 3 node. Abbreviated as ( 2 | 0,1,3 ).
a 3 node can be matched to a 0 node, a 2 node, or a 3 node as long as both nodes don't have the same value. Using the abbreviation, ( 3 | 0,2,3 ).

Under these very specific circumstances, can you help me find an efficient maximal matching algorithm?

Whichever maximal matching we achieve, the following statements must be true:

If any 0 nodes are unmatched, then all 1, 2, and 3 nodes must be matched.
If any 2 nodes are unmatched, then all 0, 1, and 3 nodes must be matched.
If any 1 nodes are unmatched, then all 0 and 2 nodes must be matched. Furthermore, all the unmatched 1 nodes must have the same value. It is also possible for some 3 nodes to be unmatched (see next statement).
If any 3 nodes are unmatched, then all 0 and 2 nodes must be matched. Furthermore, all the unmatched 3 nodes must have the same value. It is also possible for some category 1 nodes to be unmatched (see previous statement).

I have tried matching in the following manner, but don't know if it is optimal:

  While there are unmatched nodes, try first to match all '0' nodes to '1' nodes, then '2' nodes, then '3' nodes in that order. Once you do this, either some '0' nodes are unmatched, in which case you are done, or all '0' nodes are matched, in which case pick the next biggest category which has unmatched nodes and try matching the nodes in that category to nodes in the same or bigger categories. So for example, if you have unmatched '1' nodes, first try to match those to other '1' nodes, then either you have matched all '1' nodes and move on to the next category with unmatched nodes, or you still have some unmatched '1' nodes, in which case you try to match as many '1' nodes as possible to '2' nodes. After this, either all '1' nodes will be matched or all '2' nodes will be matched. Etc...

I just have not found a way to know whether this approach leads to a maximal matching or not.

If you have a better approach or can shed some light on the optimality of my current approach, I would really appreciate it.


texts: Complexity of parity game solving compared to PLS, PPA, and PPAD

texts:
Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or PPA ("Polynomial Parity Argument")? Add PPP ("Polynomial Pigeonhole Principle") if you want, even so this would probably mean that it is already contained in PPAD ("Polynomial Parity Arguments on Directed graphs"), and hence in PPA.

Or is it rather the other way round and parity game solving can be shown to be hard for PLS or PPAD? But that would be surprising, since a recursive algorithm that solves parity games is known (even if it is not efficient in the worst case).

Edit 12 March 2017: I recently learned that parity game solving has been shown to be possible in quasipolynomial time. Here are the quoted references:

  Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.

  A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.

  Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak


texts: Is a particular string regular (e.g is '010') regular?

texts:
If the alphabet is $\{0,1\}$, then is the string '010' regular?

I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.

For pumping lemma first we have to take $w$ only in the language (here the language is just '010') So $w=$ '010'. I choose $k = 2$ then the new string $w=xy^kz$ has length more than 3 so it is definitely not '010', which means this language is not regular!

What am I missing?


texts: Is the minimum weight independent dominating set np-complete in chordal graphs?

texts:
I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to contradict that exact statement.

Moreover, I have found another reference [2] saying that in chordal graphs, it is polynomial time solvable. So which one is it?

Note: I am just trying to reference this result in a project of mine. No need for a proof.

Edit: I am referring to this piece of the introduction: "Domination and most of its variations are NP-complete for chordal graphs (even for the subclass of split graphs) with the exception of independence domination (see [3]). On the other hand, an unpublished proof for the NP-completeness of the weighted independent domination in chordal graphs by the author 20 years ago..." Then in my reference [2], it also states that the weighted version is polynomial time solvable, yet here they say that there is an NP-completeness proof. Am I missing something fundamental?

The weighted independent domination problem is NP-complete for chordal graphs by G. J. Chang (2004)
Fundamentals of Domination in Graphs by T. W. Haynes, S. Hedetniemi and P. Slater (1998)


texts: Abstract machine that can recognize repetition

texts:
Let $C$ be an infinite set of characters.  I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$.

For example, if ${x,y,z} \subset C$, and $k = 3$, it should recognize $xxx$ but not $ddd$ or $xyz$.  (The same char must be repeated.)

Since $C$ is infinite, a finite state machine cannot recognize this.  A Turing machine trivially can.  But we don't anything like the power of a Turing machine; simply extending the FSM with a single register that points to a member of $C$ is enough.

My question is: What's the simplest formal abstract machine that is powerful enough to recognize this? Is there a standard extension to FSM's that enables them to recognize this? If I have more complicated versions of this machine (e.g. Move from state 2 to state 3 if you encounter a $k$ repetition of a $C$ char), what's the best way to express them?


texts:
The language is:
$$
L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \}
$$

My attempt at an answer:
$$
(a \cup b)^{3k}
$$

This will work if the a OR b can change for each instance in the string that is (3k) long. If not, what can I do to fix this?


texts: Minimize range of distances between two sets of points

texts:
I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A and B such that the range of distances between the points is the smallest.
For example, consider $n=3$, $A_1 = (0,0)$, $A_2 = (1,0)$, $A_3 = (3,0)$, $B_1 = (1,1)$, $B_2 = (3,2)$, $B_3 = (-1,0)$.
The best pairing will is $A_1 \text{ and } B_1$, $A_2 \text{ and } B_3$, $A_3 \text{ and } B_2$, because the distances are $(\sqrt{2}, 2, 2)$, giving the smallest range of $2 - \sqrt2$.
Ideally, I am looking for a solution which is able to solve the problem quickly (<5 seconds) for $n=300$.
The naive solution of trying all n! permutations is clearly too slow. I also thought about finding all n^2 combinations of distances, sorting them, and then removing the extremes until no possible pairing exists, but I don't know how to determine whether removing one possible connection will make it so no pairing exists.


texts: How many bits we can negate using two/three NOT gates?

texts:
How many bits we can negate using two/three NOT gates ?

I am newbie at this subject so I ask for help. It is about circuits.

Edit
After reading link given in comments by @D.W I think that I can negate bits without NOT gates. I know that it is impossible, however I don't know where I am wrong.

Simply, I can sort bits, then I can find $i-$th bit that it is first bit $1$ in sorted sequence.
so, $b_{1,...,i-1}=0$ and $b_{i,...,n}=1$. Now, I now where  I should return $0$ and where $1$. So I write in circuits something like:

b_0 -> 1 = c_0
b_1 -> 1 = c_1
...
b_{i-1} -> 1 = c_{i-1}
b_i -> 0 = c_i
...
b_n -> 0 = c_n

Then, I sort bits $c_1,...,c_n$. I didn't use NOT gates, the trick was to using constants $0$ and $1$.
Where am I wrong ?


texts: Church-Turing Thesis and computational power of neural networks

texts:
The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine.
The paper
"Analog computation via neural networks" (Siegelmannn and Sontag, Theoretical Computer Science, 131:331–360, 1994; PDF) claims that a neural net of a certain form (the settings are presented in the paper) is more powerful. The authors say that, in exponential time, their model can recognize languages that are uncomputable in the Turing machine model.

Doesn't this contradict the Church-Turing thesis?


texts: Proof that there are same number rotation moves in any binary tree with both children compulsory

texts:
I am working on this project where I am required to find the theoretical proof for following.

I have a particular type of binary trees, where

1) each internal node will definitely have two children.

2) There are n leaf nodes and can be assumed in order 1 to n from left most to right most.

Now this is clear that there are multiple such trees. And I am performing tree rotation (https://en.wikipedia.org/wiki/Tree_rotation) operation in any of one internal node of the tree.

I was thinking that in any such type of tree with n leaf nodes there will be guaranteed n-1 internal nodes and total n-2 possible rotation moves. (The rotation is only valid if the rotated tree also has the two given properties i.e. an internal node with just left node as leaf node cannot be right rotated.)

I have tried various resources but couldn't find any proof for it. I have tried it myself but not able to reach to a solution. I'd be glad if someone can help me out here.

EDIT:

I could get to one possible proof, please see if it's correct.

There are 3 parts of the proof:

a) With these rotation moves, you can convert to any of the tree into a completely left branching tree, I have the proof for it and it's well known in graph theory.

b) Any rotation moves preserves the number of possible rotations in the tree. This is critical, I will prove it in the end.

c) In any left branching tree, out of total n-1 internal node, everyone except one can be right rotated. So total n-2 rotations.

All 3 together gives that total n-2 rotations possible.

Now the critical (b) part:

From the wikipedia image on the link (https://en.wikipedia.org/wiki/Tree_rotation), the number of rotations for subtrees A, B ,C remains the same and reverses for P and Q. So the total moves will remain same.

I can give more details for the above statement if required, but it's hard to write it here.


texts:
Can a DPDA be created for a Language which includes the null string?

The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a state, a is some input, and Z is a stack-character.

Also, if you have a transition Delta(q,lambda,Z), you can't accept any other input from that state.

So, back to the original question. Can a DPDA accept a language which lambda and anything else?


texts: Karloff's algorithm applied to sparse graphs

texts:
I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph.

Karloff [1, p.6] has given a map-reduce algorithm called "Finding  an  MST  of  a  Dense  Graph  Using Map-Reduce" which finds an MST of $G$ by randomly partitioning the vertices into $k$ different equally sized sets $V_i$ and then finding a MST for $V_i \cup V_j$ for all $i,j$.

will it provide correct output if we will apply this algorithm to a sparse graph, i.e., a graph for which $|E| < N$, instead of a $c$-dense graph? Will it work correctly?  If it will, why is the paper making the assumption  here $|E| = m \ge N^{1+c}$, if their algorithm works for sparse graphs too?

A Model of Computation for MapReduce. Howard Karloff, Siddharth Suri, Sergei Vassilvitskii.  ACM-SIAM Symposium on Discrete Algorithms, 2010.


texts: Small o-complexity of $(\sqrt n)^\sqrt n=$

texts:
show that $(\sqrt n)^\sqrt n=o(2^{n^{0.6}})$

i just know that small o-complexity of $\sqrt n=o(n)$ but how to prove this


texts: context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

texts:
Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Generate a cfg of $L_n$

For n = 1, 2, 3

Informally, x is in $L_n$ means
    some palindrome of at least length n is a substring of x that occurs
    exactly at the midpoint of x.

for $n = 1$

$S \to 0S0 | 1S1 | 0S1 | 1S0|0 | 1 | 00 | 11$

for $n = 2$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | \epsilon$

for $n = 3$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | 00 | 11 | \epsilon$

would this be right?

Say I changed it to $|y| > |z|$ or $|y| < |z|$ how would this differ?


texts:
Context: I'm operating a service with 5 accounts simultaneously servicing tens of millions of users. The accounts using the service have extreme bursts due to various campaigns by each account and the incoming requests from one account can suddenly go up 100x. All our queries are about equally expensive, so it makes sense to do rate limiting locally on each backend server instance, since the limits then automatically scale with the number of nodes started by an autoscaler. What I want to do is give each account a fixed percentage of the total capacity, but allow the accounts to burst up to the full capacity available.
Question: A regular CBQ algorithm would handle the above problem for a router. However, routers are a bit special in that putting things on a queue is asynchronous and there's a separate worker that pulls packets of the queue. However, I would prefer to be able to maintain a software architecture where the throttle or not decision can be done locally in the request handler without a separate queuing layer. This will reflect what the algorithm can do. In essence, would like to have a rate limiter algorithm that can support the following API:
// Register HTTP URI handlers.
float fractionA = 0.4;
float fractionB = 0.6;

RateLimiter root = new RateLimiter(capacity);
RateLimiter limiterA = root.getChild(fractionA);
RateLimiter limiterB = root.getChild(fractionB);

router.registerHandler("/serviceA", new ServiceAHandler(limiterA))
router.registerHandler("/serviceB", new ServiceBHandler(limiterB))

The handler for both services would then implement throttling as follows:
if (limiterA.throttle()) {
  // return rate exceeded error
}

// handler implementation

In other words, the call to throttle() would need to be able to decide by itself whether it can proceed with the request or not. It would return true whenever it's using a less than 40% share of the total capacity or if we're not throttling the other service and it's using less than 60% capacity. Are there hierarchical rate limiting algorithms that would make such an implementation easy?
I would also be happy if anyone knows of any survey article of different rate limiting algorithms, so I can dig into the topic myself.


texts:
I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$.
But I still confused, in case of $L\in \overline{SAT}$ is it mean:
if $\varphi\in L$ then all interpretations are satisfy and
if $\varphi\notin L$ then exists interpretation that unsatisfy
OR vice versa
if $\varphi\notin L$ then all interpretations are satisfy and
if $\varphi\in L$ then exists interpretation that unsatisfy
please if you downvote write explanation of why


texts: Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

texts:
I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk stating specifically that :

  If a transition graph has a walk labeled $w$, then there is a walk w of length no more than $\Lambda + (1 + \Lambda)|w|$ where $\Lambda$ is the number of $\lambda$ transitions in the graph.

The book does not define $|w|$ which is causing part of my confusion. I'm assuming $|w|$ is the length of the label of the walk. So in this case it would be 1 when going from $q_1 \to q_0 \to q1$ because $a$ is the only labeled edge.
I am trying to understand this concept and how it works because when I have tested out this claim it has not held true.

Here is the test I did with this NFA

$q_1$ is the final state. So assuming you were trying to find the length of the walk $a$, the label would indicate that the length is 1 (e.g. $\delta^* (q_1, a)$) . However due to the lambdas you actually have $\lambda \lambda a$ to go from $q_1 \to q_0 \to q_1$.

This theorem doesn't hold with my math though because it is defined as Λ + (1 + Λ)|w| where Λ is the number of λ-edges in the graph.

Since there are two λ-edges (and it doesn't state whether it means λ-edges in the walk itself or in the graph in total...) this would then be 2 + (1 + 2)|w|. So thats 2 + 3|w|. This clearly is more than 3, which is the length of q1 -> q1 of λλa.

What am I missing here? Any help is greatly appreciated.

This comes from Peter Linz "An Introduction to Formal Languages and Automata" 5th edition.

Some more information about the argument for this claim:

  While λ-edges may be repeated, there is always a walk in which every repeated λ-edge is separated by an edge labeled with a nonempty symbol. Otherwise, the walk contains a cycle labeled λ, which can be replaced by a simple path without changing the label of the walk.

Also the book never names this as a theorem or lemma or anything of the sort so it has been very difficult to find online resources about this topic.


texts: How to find the minimum number of states of a deterministic finite automaton accepting a given language

texts:
Let

$L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets.
$L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of 1s divisible by 5}\}$.

What will be the minimum numbers of states in the DFA accepting $L$?

My approach is to create a grid like this:

I am getting 5 x 3 = 15 states.

How can I apply Myhill Nerode theorem to solve this kind of problems?
I don't understand this theorem at all.


texts: I was asked to perform merge sort by iterative method. I solved it as follows: I first stored each of the elements of the array given in another array say $A$. Then I sent entries of $A$ two by two for merging(was given that the function for merging is known and it merged two arrays at a time). This function returned the merged array which I stored in another array $B$. After I was done with all the elements of $A$ I deleted $A$ and copied each of the entries of $B$ in $A$.I allocated memories for $A$ and $B$ dynamically. I repeated this for $log(n)$ times and each time I halved the size of $A$ and $B$. Is my algorithm correct??