texts: Eliminate equal sub-paths of directed cyclic graph

texts:
Suppose we have a directed cyclic graph and a list of paths.
What is the shortest way (including parallelization) of eliminating all equal paths and paths that are sub-paths of others?
For example, lets suppose that the vertices are marked by letters from A to Z (for simplicity lets suppose we have only 26 vertices.
The paths are:
[A->A->B->D->E->G->K->L->A]
[B->D->E]
[A->A->A]
[K->L->A->M->N->C]
[M->N]
...
The output should be:
[A->A->B->D->E->G->K->L->A]
[A->A->A]
[K->L->A->M->N->C]
I thought to first sort all paths by length and start with the longest.
Holding a dictionary of vertices (letters), where the key is the letter and the value is a dictionary of lengths of paths that start from this letter, and the value is the paths, and if there isn't a match of the current path with equal or bigger paths in the same letter, the path is saved in the results, and is inserted to the dictionary, each time removing the leading vertex. For examples --
We start with [A->A->B->D->E->G->K->L->A],
The dictionary is {A: {0, []}, B: {0, []} ... Z: {0, []}
Length of current path: 9
First vertex: A.
No paths that are 9-length that start with A, so we know that the path is unique.
Lets divide it, we should have:
{A: {9: [AABDEGKLA], 8: [ABDEGKLA]}, B: {7: [BDEGKLA]}, D: {6, [DEGKLA], E: {5, [EGKLA], G: {4, [GKLA], K: {3, [KLA]}, L: {2, [LA]}}
The next path (by length) is [K->L->A->M->N->C] :
No 6-lenght paths that start with K, so we know this is unique. Dividing it into:
{A: {9: [AABDEGKLA], 8: [ABDEGKLA], 4: [AMNC]}, B: {7: [BDEGKLA]}, D: {6, [DEGKLA], E: {5, [EGKLA], G: {4, [GKLA], K: {3, [KLA], 6: [KLAMNC]}, L: {2, [LA], 5: [LAMNC]}, M: {3: [MNC]}, N: {3:[MNC]}}
Next is [B->D->E], 3-length.
In B we have >= 3 path, so we compare -- BDE is a sub-path of BDEGKLA, so it's not unique and omitted.
Next is [A->A->A] - we have >= 3 paths in A, [AABDEGKLA], [ABDEGKLA], [AMNC], but AAA isn't a sub-path of any of them so it's unique and the dictionary is now:
{A: {9: [AABDEGKLA], 8: [ABDEGKLA], 4: [AMNC], 3: [AAA], 2: [AA]}, B: {7: [BDEGKLA]}, D: {6, [DEGKLA], E: {5, [EGKLA], G: {4, [GKLA], K: {3, [KLA], 6: [KLAMNC]}, L: {2, [LA], 5: [LAMNC]}, M: {3: [MNC]}, N: {3:[MNC]}}
I wonder if there is a more efficient way do do that.
Thank you.


texts: Complexity of generating non-uniform random variates

texts:
What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) hypergeometric variates in (expected) constant time (i.e. independent of the distribution parameters)?

There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).

For example, Stadlober (or similar here) mentions a "generalization [of the ratio-of-uniforms approach] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called uniformly fast, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.

However, in another paper, I found the following theorem: On a RAM with word size $w$, any algorithm sampling a geometric random variate $Geo(p)$ with parameter $p \in (0,1)$ needs at least expected runtime $\Omega(1 + \log(1/p)/w)$.

Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.


texts: Issue in comparing classifiers for pattern recognition

texts:
I have designed a classifier M which recognizes gestures and classifies it under any category always. A gesture is classified based on the hamming distance between the sample time series y and the training time series x. The result of the classifier are probabilistic values. There are 3 classes/categories with labels A,B,C which classifies hand gestures where there are 100 samples for each class which are to be classified (single feature and data length=100). The data are different time series (x coordinate vs time). The training set is used to assign probabilities indicating which gesture has occured how many times. So,out of 10 training samples if gesture A appeared 6 times then probability that a gesture falls under category A is

  P(A)=0.6
   similarly
  P(B)=0.3

and

  P(C)=0.1

Now, I am trying to compare the performance of this classifier with Bayes classifier, K-NN, Principal component analysis (PCA) and Neural Network.

On what basis,parameter and method should I do it if I consider ROC or cross validate since the features for my classifier are the probabilistic values for the ROC plot hence what shall be the features for k-nn,bayes classification and PCA?
Is there a code for it which will be useful.
What should be the value of k is there are 3 classes of gestures?

Please help. I am in a fix.


texts: Path in a vertex-weighted undirected graph

texts:
Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$.

Does there exists a path in $G$ with total weight $W$ that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?


texts: checking time for a circuit of size in polynomial k

texts:
On the page 1073 of CLRS(Introduction to Algorithms),

Given a circuit C, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if the circuit has k inputs, then we would have to check up to 2^k possible assignments. When the size of C is polynomial in k, checking each one takes Ω(2^k), which is superpolynomial in the size of the circuit.

Can I ask what is the reason that checking if one truth assignment is a satisfying assignment takes Ω(2^k)?


texts:
Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.

Is there any polynomial or pseudo-polynomial algorithm to sort the permutation with minimum cost?


texts: Finding the number of iterations to a recurrence

texts:
I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.

$$
\begin{align*}
S_0 &= S \\
S_{k+1} &= S_k - S_k \frac{\sigma}{1+\sigma}
\end{align*}
$$

Here $\sigma$ is a small value.

How can I find number of iterations? I know it is a geometric series but can't seem to simplify for number of iterations.


texts: Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

texts:
Several questions (1, 2) have been asked about this topic already but I am trying to be more specific.

In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is already on the stack is

    // It says w.index not w.lowlink; that is deliberate and from the original paper
    v.lowlink  := min(v.lowlink, w.index)

I understand that this rule is necessary to compute lowlink accordingly to its formal definition, which in Tarjan's paper is (emphasis is mine)

  LOWLINK(v) is the smallest vertex which is in the same component as v and is reachable by traversing zero or more tree arcs followed by at most one [back edge] or [cross edge].

What I do not understand is :

Would removing the emphasized restriction in the definition lead to a calculation with v.lowlink  := min(v.lowlink, w.lowlink) ?
Would removing the emphasized restriction lead to incorrect detection of a graph's SCCs (if so, I am looking for an example of such a graph) ? If not, would this modification guarantee that in a given SCC, all nodes ultimately have the same lowlink value (again, if not, I am looking for a counterexample) ?

I am currently at the following point (which might be wrong !) :

Let v and w be as in the code (exploring v's successors, w already on stack). v is on the stack too, and so is r, the root of v and w's SCC (in Tarjan's sense) (it is a common ancestor of v and w in the spanning tree).

For the proposed modification of the algorithm to yield a bad result, one needs to have w.lowlink < r.lowlink (this is the case where, by propagating the lowlink information back to r after finishing DFS, we will get an inconsistent value for r). For this to happen, w must have gotten its lowlink value from a vertex x discovered before r and belonging to a different SCC than r. But x needs to be in the stack when we were DFSing from w (if it were not the case, one would not have updated w.lowlink when reaching x because x is already discovered at that time). Since x is discovered before r, it is deeper in the stack than r, and thus it is still in the stack when we are DFSing from v. But then wouldn't all these nodes belong to the same SCC, rooted by x.lowlink ?


texts:
I have recently discovered term rewriting when I watched this video - https://channel9.msdn.com/Series/Beckman-Meijer-Overdrive/Beckman-Meijer-Overdrive-The-Lambda-Calculus-and-Food-Nutrition

It seems that term rewriting is a generalization of which lambda calculus is an instance.  A couple of the programming languages that are based on term rewriting that I've noticed are 'pure', and the wolfram language.

Now, it seems to me that the only examples of the usefulness of a TR programming language I've ever seen are in symbolic programming.

I'm interested in using TR to make an automatic inverse function creator.

You would have a few concrete rules like:

incr x = x + 1
decr x = x - 1
inverse incr = decr

Then you would have a rule that handles compositions of functions:

inverse (f(g x)) = inverse g (inverse f x)  // Probably not true; it's just an example.

I think TR would be useful in doing this because it gives access to the internals of a function.  However, a normal functional language that does this would work as well.

I'm guessing that TR is more than just useful for symbolic computing or inspecting function internals.
What's the "big picture" of TR, and would it be good to use for general programming?

Also, do the 'pure' and wolfram languages use full TR, or do they use a specialized form (perhaps to avoid things like non-confluence, whatever that may be)?


texts: Find two numbers in sorted array whose product is close to N

texts:
Given a sorted array of numbers, is there a good algorithm for finding two numbers in that array whose product is as close as possible to a given number N?

I know that there is a good O(n) (?) algorithm for the related problem of finding two numbers that sum to a given number N. You begin with ptr1 at the start of the array and ptr2 at the end, and if *ptr1 + *ptr2 > N you decrement ptr2, else increment ptr1.

But for multiplication, it feels possible this method could "miss" the optimal solution by overshooting it somehow? Is there a good way to solve the multiplication variant in something that isn't just O(n^2)?


texts:
I am aware of three approaches to prevent over-fitting of data when trying to model it on a neural net.

The first two approaches I know suggest to train on more data and employ bootstrap aggregating. The third approach is to use a model that has the right capacity, one that has enough to fit the true regularities but not the weaker/dubious regularities (the noise). However, I don't quite understand this 2nd approach. How do we create a distinction and choose a model that detects this? Can someone expand on the second approach? I am aware of ways to limit the capacity such as early stopping(which is self explanatory), penalty for peculiar weights, etc. But an explanation on why these specific methods limit the capacity to fit the right data but not the wrong one would be helpful.


texts: Complexity of many constant time steps with occasional logarithmic steps

texts:
I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.

Is it possible for this task to ever take amortized constant time, or is it impossible because the logarithm will eventually become greater than $k$?

If an upper bound for $n$ is known as $N$, can $k$ be chosen to be less than $\log{N}$?


texts: Why do the definitions of non-deterministic Turing machines look strange?

texts:
I read some definitions of the NDTM in several books. Something makes me confused.

Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply.

So, if $x \in L(M)$, then $M$ can always guess a branch which leads to $q_{accept}$. And if $x \not\in L(M)$, then $M$ just chooses an arbitrary branch until it enters $q_{reject}$. It seems that $M$ knows the result after reading $x$ because the rule which tells $M$ how to guess depends on whether $x$ is in $L(M)$.

It looks so strange!

Another definitions say that $M$ executes all branches in parallel.

That looks better. And it shows that if $x \in L(M)$, then $M$ halts when it enters $q_{accept}$ at the first time. However, the running time of NDTM is defined as the maximum number of steps that $M$ uses on any branch of its computation on any input. I am not sure if the definitions of the running time of NDTM are equivalent.


texts: Naming of Monte Carlo and Las Vegas Complexity classes

texts:
For Curiosity Sake, I was wondering if there was some history behind the naming of "Las Vegas" and "Monte Carlo" classes.
I've searched on the internet for quite some time now but I did not find a proper answer, is it just because they are probabilistic which gives them the "gambling" nature, or is there something more to the nomenclature?


texts: Doubt in effective memory access time in case of n level paging + TLB

texts:
I am getting confused with calculation of EEMAT(Effective memory access time). I decided to close the book and think on my own and make an equation. Please see whther this is correct or not. I thought a lot and also refereed google but i am lost. Please help!

Let TLB hit ratio = x.

TLB access time = c

main memory access time = m

page fault rate = p; page fault service time = S

First i will access TLB. In case of TLB hit i will directly access main memory(so time here = c+m in case of TLB hit)

If TLB Miss, then i will have to access via page table. I am assuming here n level page table(so n page tables needed to access main memory).

In case of TLB Miss, i will access page table(n level) --> it can be hit or miss. If page hit, then time = c+(n+1)m

If page fault, time = c+m+(n+1)m --> TLB access time + first i access page table to know that there is no valid frame in 1st level page table itself(i got another doubt here, in case of page fault in n level paging, valid bit is 0(invalid page) in 1st level or any of n levels or in nth level page table???) + n level page table access in main memory + finally main memory

So EEMAT = x(c+m)+(1-x){ (1-p)[(n+1)m] + p[S + m + (n+1)m ] }

Is this correct???

My another doubt:

in case of page fault in n level paging, valid bit is 0(invalid page) in 1st level or any of n levels or in nth level page table???


texts:
This is a Google interview question. I got it from a website.

You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You would like to rearrange source so that it equals to target. The only allowed operations is “swap a number with 0”. Find the minimum number of swaps?
e.g. {1,0,2,3} -> {1,3,2,0}  swap 0 with 3. one swap is enough.

My attempt on problem: If we consider arrays as strings we could use edit distance to convert source to target if other edit distance operations like insert,delete,replace etc are allowed but here only allowed operation is swapping.


texts: Are there any PSPACE problems that don't exist in NP-Hard?

texts:
The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it will naturally contain PSPACE problems.

However, I was specifically wondering if there were any PSPACE problems that were not in NP-Hard? (from my understanding, implying that they are easier than the hardest problems in NP).


texts: How to know if a code is Huffman or not without having the probability of each codeword?

texts:
I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way is look at whether or not the code is prefix. If not, then it's not a Huffman code. If yes, then we need to check if it gives the shortest possible length, but we don't know the probabilities. How do we ensure the code guarantees the shortest possible length in such case? To illustrate my question, let us look at the following two examples:

Example 1: $\{00,01,10,110\}$
The code is a prefix code, but is the length minimal? I mean it's a bit unusual for me to see Huffman code
for $4$ symbols that does not have one-bit codeword for one of its
symbol (the symbol with highest probability), but them I thought maybe
the first three symbols are equally probable. As such, I tried to find
the Huffman code for $\{0.33,0.33,0.33,0.01\}$ and got
$\{00,01,10,11\}$ with different orders (depending on the usage of
$0,1$ or $1,0$ in the tree). This led me to thinking that the code
under investigation might not be Huffman, yet I am still not sure.
Example 2: $\{01, 10\}$
Again another unusual prefix code as the obvious choice (and the one with minimal length) for two symbols would
be $\{0, 1\}$. But could it be the case that $\{01, 10\}$ can possibly
give a minimal length? I can not see any possible probabilities in
which this is the case, thus I believe this is not a Huffman code.

Am I on the right track? Does there exist an actual method to check whether or nor a code is Huffman without having the probabilities?


texts: NP-hard proof: Polynomial time reduction

texts:
As I understand, to show that a certain problem $P$ is NP-hard we can reduce a known NP-hard problem $Q$ to a problem in $P$. This reduction, say $f$, has to be polynomial time.

Could someone please explain is it necessary that $f$  maps each instance of $q\in Q$ to $P$ or can we map a selected  subset of $\tilde Q \subseteq Q$ to $P$? i.e. does pre-image of $f$ has to be be all of $Q$ or can it be a subset of $Q$?

Thanks


texts: Convert given string to Palindrome with given substring

texts: Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other character. Find minimum number of operations required.


texts: Removing vertices that belong to a given set from a graph

texts:
If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ in linear time ($O(V + E)$)? It can be assumed that checking if a vertex $\in B$ is $O(1)$.

My thoughts on this are-
If I represent $G$ as an adjacency list, this is not possible as I'd have to loop over all vertices and the vertices that they're connected to. So worst case would be $O(n^2)$.

In case I have an adjacency matrix, I feel like this would be possible in $O(n)$ as I could zero out the entire row and column of the vertices in $B$. However, actually getting rid of the vertices themselves would require shifting elements of the array so overall $O(n^2)$.

My end goal is to be able to perform graph traversals (specifically, finding strongly connected components in the set $G - B$) over the leftover subset in a directed graph. Would simply ignoring any edges leading to vertices in $B$ and ignoring any vertices in $B$ work just fine?


texts: Complexity of CFG grammar for a regular language

texts:
I know that each regular language can be generated by a CFG.
This makes, in one sense at least: context-free languages more general than regular languages.

Are there known results about the 'complexity' of regular languages in the CFG context? For example, is it true that every regular language can be generated by an unambiguous LL(1) grammar?  Or is something similar true?

The general question above comes from the attempts I made to build a 'simple' grammar generating $L=\{(ab)^i|(ba)^i : i\geq 0\}$.
None of the grammars I could build were 'simple'.


texts: Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)?

texts: What are the exact assumptions behind the use of UPGMA? Can I use a non-Euclidean metric? This may result in a non-Euclidean distance matrix. What kind of bias may I encounter if I do so? References are appreciated.


texts:
In the Set Cover problem we need to cover each element at least once.
I'm considering the case where I want each element to be covered at least $k$ times with constant $k$.

I consider the classic LP for the problem and randomized rounding.
Is it indeed the case that the modification of the LP from $\geq 1$ to $\geq k$ in the covering constraint and with the same rounding (up to the number of repetitions) works well for this variant as well?

It looks like it, but I'm not sure if I'm missing anything.


texts: Counting strings with balanced substrings

texts:
Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.

Given an integer $n$, find the number of strings of length $n$ consisting only of characters $ a,b,c$ such that all of its substrings of length $k$ are good.

Example:

$ n = 3 ,k = 2 $ is $6$,

$ n = 2,k = 1 $ is $0$

I could only solve when there are only two characters but can anyone help me how to solve when there are three characters.


texts: Largest weight-limited connected subgraph: NP-complete?

texts:
When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of having the longest network. Let's abstract that into the following problem:

Let a graph $G$ be given, $G = (V, E)$.
Associate a terraforming cost with each vertex, $C : V \mapsto \{0, 1, 2, 3\}$.
You're given some number of spades, $s$.

Your goal is to find a set of vertices $V^*$ such that:

You can afford to build on all of them, $\Sigma_{v \in V^*} C(v) \leq s$
They're all next to each other: the graph $(V^*, V^* \times V^* \cap E)$ is connected.
It is the largest such set: for all $V'$ which satisfy the previous conditions, $|V^*| \geq |V'|$.

The decision version takes a threshold parameter $k$ and asks "is there a vertex set $T$ with size $|T| \geq k$ and which satisfies the first two criteria?"

What is the complexity of this problem? By eyeball, it's obviously in NP; is it NP-complete? Is it well-studied under some name unknown to me?


texts: Why do we need value-returning functions?

texts:
I'm just a beginner at C++ programming. I am currently having hard time grasping the usage of value returning function and non-value returning function. Void functions are called non-value returning function but they can return value if we assign certain parameters, compute the parameters and call them in the main function. So, doesn't this defeat the purpose? I feel like I am getting this wrong, so some explanation here would be great!

Also, I see that void functions are easier to use, since I don't need to use " cout<< 'the void function' << endl; "
It seems easier and the value-returning function seems useless. I need explanation here as well as to why we need value-returning function.

Please bear with my questions and I am always ready to learn!


texts:
I am new in Computer Vision. Suppose you have 8 points (players in a basketball court) in a 2D image (png photo), that is we know the pixel coordinates of each. I would like to compute camera position w.r.t. the field. We have the actual dimensions of the field. Also, I can write the equations of two or three transversal lines in the field that are parallels lines from top view. With this data can we find a position vector of the camera w.r.t. the field ?

  Any idea on where to read about this ?


texts: A voting scheme where votes are scriptable

texts:
I am looking for literature on mathematical models of (political) voting schemes. Concretely, I am interested in models that allow votes of the following form:

"I am voting for $X$, but only if $>40\%$ of my peers vote for them, too. Otherwise, I'd like to vote for $Y$ instead."

In that sense, I'd like to consider votes to be scripts over some language. I got this idea from Bitcoin where money isn't actually sent to specific accounts, but rather scripts are given that determine who may redeem that money.

A naive model
To give you a more precise idea, I have come up with the following (naive) model of scriptable votes:
Let $C$ be a set of candidates, e.g. $C = \{\text{rep},\text{dem}\}$ for republicans and democrates. An election outcome $O \in \mathrm{ProbDists}(C)$ is a probability distribution on $C$. For finite $C$, this is known as a normalized histogram.
A vote $v$ is a mathematical function $v\colon \mathrm{ProbDists}(C) \to C$, which – given a putative outcome – decides which candidate to vote for.
In most elections around the world, all votes are constant functions: e.g. if you mark your cross for republicans, in the above model you would cast the constant function $v \equiv \mathrm{rep}$. And if you marked democrates, you would cast $v' \equiv \mathrm{dem}$ instead.
Importantly, our model also supports votes as in the quote above: $$v^\text{example}(O = \{p_\mathrm{rep}, p_\mathrm{dem}\})=\begin{cases}
  \mathrm{rep} & \text{if } p_\mathrm{rep} > 0.4\\
  \mathrm{dem} & \text{else}
\end{cases}$$
where the notation $O = \{p_\mathrm{rep}, p_\mathrm{dem}\}$ is syntactic sugar for extracting the probabilities assigned to $\mathrm{rep}$ and $\mathrm{dem}$, respectively. Here, you see that $v^\text{example}$ is a script over the usual mathematical language. But given some votes how do we determine the (final) outcome?
Let $V = v_1,\ldots,v_N$ be the multiset of cast votes. An admissible outcome of an election $(C, V)$ is an election outcome $O \in \mathrm{ProbDists}(C)$ such that the multiset $\{v_1(O),\ldots,v_N(O)\}$, interpreted as a normalized histogram on $C$, equals $O$. We can see this as some kind of fixpoint.
Examples. Let $C$ and $v := v^\text{example}$ as above.

For the election $(C, \{v\})$, i.e. with $v$ being the only vote, we have two admissible outcomes: $O_1 = \{p_\mathrm{rep} \mapsto 1, p_\mathrm{dem} \mapsto 0\}$ and $O_2 = \{p_\mathrm{rep} \mapsto 0, p_\mathrm{dem} \mapsto 1\}$. For $(C, \{v, v\})$, we have the same two outcomes. The same holds true for three, four, and arbitrarily many copies of $v$.

Consider a new kind of vote $w(O) \equiv \mathrm{dem}$ that always votes for democrates. The election $(C, \{v,w\})$ has two admissable outcomes: $O_1 = \{p_\mathrm{rep} \mapsto 0.5, p_\mathrm{dem} \mapsto 0.5\}$ and $O_2 = \{p_\mathrm{rep} \mapsto 0, p_\mathrm{dem} \mapsto 1\}$. In the latter case, the vote $v$ "noticed" that they will never be surrounded by a like-minded peer group of size $> 40\%$ and hence switched its candidate it voted for.

Research Questions
Concerning scriptable votes, some broad questions I'd be interested in are:

Does every election have at least one admissible outcome? If not, can we relax the conditions on admissible outcomes to just choose the best ones?

How much influence do individual votes have? Is the function that maps $(C, V)$ to a set of admissible outcomes continuous in some sense?

Are mathematical functions for votes really the best model? While if conditions like $p_\mathrm{rep} > 0.4$ sound reasonable (and interesting), should we perhaps disallow conditioning on equalities such as $p_\mathrm{rep} = 0.4578$? Perhaps votes should be scripts over a tailored domain-specific language. How do their properties such as being total (exceptions?) or deterministic (probabilistic?) affect the questions above?


texts: Is there a problem in this BN form language?

texts:
I am working on a simple text query language.  I am using the SLY parser, which itself is an LR parser/shift-reduce parser.  I am running into problems with the following language specification, but I don't understand why.  All I'm trying to do is appropriately group logical statements involving the operators AND and OR (in which AND gets precedence over OR and the statements are left associative) and "words", which is basically anything other than "AND" or "OR".  The language is below.  What is the problem?

LOGICAL ::= <WORD> <OPERATOR> <WORD>
        | <WORD> <OPERATOR> <LOGICAL>
        | <LOGICAL> <OPERATOR> <WORD>
        | <LOGICAL> <OPERATOR> <WORD>

OPERATOR ::= "AND"
            | "OR"

WORD ::= any string other than "AND" or "OR"

Also, for the record I don't know how to express "WORD" in a more formal way, so I'd appreciate any input.


texts:
Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$

$$
\begin{align*}
s_1&=x_1+x_2+x_3+x_9,\\
s_2&=x_1+x_2+x_4+x_9,\\
s_3&=x_1+x_2+x_5+x_9
\end{align*}$$

There are repeating subsums, e.g. $x_1+x_2+x_9$. If subsums are extracted and summed up separately, one needs 5 additions, while direct computation requires 9 additions.

In applied problem $N\sim10^6$, $M\sim10^9$ and many subsums are repeating. We expect significant speedup of the computation if the repeating subsums are recognized and extracted.  Each sum has about $K\sim10^3$ terms. The structure of the sums is fixed once and forever, so we can do some preprocessing based on the structure of the sums to find the best evaluation order.

More details as requested by gnasher729: the real data in $X$ are permanently coming from a telescope. The summing is performed in a processing program, which tries to find signals matching a certain signature (localized in the sky, periodic in time, having certain drift in frequency bands). We hope to find a method for accelerating the program, not going deeper into processing specifics, but analyzing its summation pattern.

Is there any algorithm for doing this?

Thanks comment by D.W., the task can be formulated as optimization of vectorial addition chain. In the example above the chain can be converted from a form
$$((-8,-7),(-6,1),(0,2)\downarrow,(-8,-7),(-5,4),(0,5)\downarrow,(-8,-7),(-4,7),(0,8)\downarrow)$$
to a form
$$((-8,-7),(0,1),(-6,2)\downarrow,(-5,2)\downarrow,(-4,2)\downarrow).$$
Here downarrows show the places where the sums $s_1,s_2,s_3$ can be saved. Non-positive numbers $(-8...0)$ denote the variables $(x_1...x_9)$, positive numbers enumerate intermediate sums. The second sequence is shorter and may be even optimal. For the application purpose it is enough to obtain the output sequence much shorter than the input one.

The equivalent question then: is there an algorithm for compression of vectorial addition chains?


texts: What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation because it eliminates nodes that have both edges pointing to the same node, eliminates nodes that have  removes  and removes terminal $2^n$ terminal nodes to just $2$, and but perhaps there is fundamental difference other then this?


texts: Computational approach deciding whether a set of Wang Tile could tile the space up to some size

texts:
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a more practical aspect. Say, if the program accidentally ("or systematically") find some "periodic structure", then it stops and tells me there exists periodic pattern. If during running, it enumerates all the use of tile and finds that it simply cannot tile the plane, then it tell me this set of tiles cannot tile the plane. Even if the program didn't stop, then after running some steps, it returns me a few most ordered patterns that that could "possibly tile the plane".

For practical purpose, I simply assume if the tessellation are up to some size (maybe 1000*1000) then I say "it could tile the plane practically".

So my most interested question is: is there any established programs or algorithms that "try" to help me analyze a set of tile even if it might not halt ("but I could define some imposed halting condition").

For context why I am interested in this problem, here's the links:

Coloring in lattice
Reference for Wang Tile
Periodic Tiling of Wang tile

Also cross posted to Math Overflow.


texts: Covering maximal number of sets using fixed number of elements

texts:
I've encountered some problem which seems general enough to have already been solved.

There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$.

For every $1 \leq j < k$ we need to find a subset $O' \subset O$ of size $j$ maximizing the number of sets $A_i$ contained in it.

What is the best algorithm to solve this? I've been thinking about reducing it to a problem in graphs or flow networks but still haven't arrived at a solution.


texts: Sipser exercise : variant of CNF is NL-complete

texts:
I'm stuck rather badly on a Sipser exercise, 8.21 in my edition:

  8.21 Let $CNF_{H1}$ = {<$\phi$> | $\phi$ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in $\phi$}. Show that $CNF_{H1}$ is $NL$-complete.

My problem is, if we remove the second condition (each negated literal occurs at most once), the language becomes $P$-complete, so we must use that second condition to get anywhere, but I have no idea whatsoever how to do that? I can't even prove that the language is in $NL$.

To deal with a clause $\lnot x_1 \lor x_2 \lor ... \lor x_n$, all of my efficient algorithms convert it to the equivalent $\lnot x_2 \land ... \lnot x_n \Rightarrow \lnot x_1$, and use that form to deduce in some cases that $x_1$ must be false. With such an approach, however, the second condition can't possibly help. If the negated $\lnot x_1$ appears twice, it simply means that we have more opportunities to deduce that $x_1$ is false, which can't hurt the algorithm?


texts:
Currently I self study CLRS book (Outside of any course, so I got no access to an instructor)

And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal.

Here's the algorithm:

INSERTION-SORT(A)
   for j=2 to A.length (= n)
      key = A[j]
      i = j-1
      while (0<i and key<A[i])
         A[i+1]=A[i]
         i = i-1
      end while
      A[i+1]=key
   end for
end procedure

I tried to formalize the proof with the following pre-post conditions:

Pre-Condition: $A=A_{org}$ and $j=2$ (I.e. $A_{org}$ holds the original values of $A$)
Post-Condition: The array $A$ consists of the same elements as in $A_{org}$ but in a sorted order that is $\forall i_1,i_2\in\{1..n\}, i_1<i_2\to A[i_1]\leq A[i_2]$.

My loop invariant is:
($p$ denotes the $p$'s iteration)

$I(p)="\text{The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$} \land \forall i_1,i_2\in\{1..j-1\}, i_1<i_2\to A[i_1]\leq A[i_2] \land j=2+p"$

Now when I try to prove the inductive step I got stuck and cannot proceed because of the nested $while$ loop and because of the informal sentence "The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$".

Any help on how to prove Insertion Sort rigorously and how to formalize the sentence "The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$" will be appreciated (I want my loop invariant to contain only mathematical symbols and not informal english phrases).

(BTW: I am trying to write the proof in the same style as in Susanna. Epp's Discrete Mathematics book)

Any help will be appreciated. Thanks.


texts:
Consider an array A[100] & each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement. Assume one block is read into cache in case of miss:

for(i=0;i<100;i++)
  A[i]=A[i]+10

each array element is of 4 word & each cache block size is 8 words, so we load 8 words into cache.

When program tries to read A[0], for the first time it will be miss. Hence it will be brought to memory (& also A[1]). Next, A[1] will be hit. So, it will be like :

A[0] - Miss
A[1] - Hit
A[2] - Miss
A[3] - Hit
.....

So hit ratio is 50% ? Am I wrong anywhere ?

I also have one more doubt. First when it tries to access A[0], it will be miss. And then when it brings A[0] to cache, CPU tries to access A[0] again, now it should be considered as hit ? Like,

A[0] (Read) - Miss
A[0] (Write) - Hit
A[1] (Read) - Hit
A[1] (Write) - Hit

If above is correct, then Hit ratio will be 75%.

Any help regarding this is appreciated.


texts: Are there decidable problems that are reducible to undecidable problems?

texts: I've seen a question asking if $A \le_m B$, then if $A$ is decidable, $B$ is also decidable. My initial intuition is that this is not the case, and that there are decidable problems that are reducible to undecidable problems. While I am not sure if this is completely correct, or even how to prove this if it is correct, I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?


texts:
I have the following language...

$$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$

Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is how to split the language into three parts, this is my attempt:

$p=a^j$

$q=a^jb^k$

$r=b^k$

I believe my attempt is incorrect but this is the extent of my knowledge on the subject. Can someone explain how to split the language properly?


texts: Prove (non-)recursiveness of a set of Turing Machines defined by behavior

texts:
I have a list of problems which I don't know how to prove (non-)recursive (save, I think, for the first), where $\mathcal{M}_n$ is the Turing-Machine with the Gödel-number $n$:

$\mathcal{R}=\left\{n:\mathcal{M}_n\text{ does not move right for any input.}\right\}$

$\mathcal{R}_\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not move right past the starting position for any input.}\right\}$

$\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not hang for any input.}\right\}$

Note: The model used within this question is one with a one-side-unbounded tape with the bound being on the left end, thus "hangs" means trying to move off the left end of the tape; the Turing-machine starts right of the input and has three options per step: writing or moving left or right, so no movement is necessary for a step.

I already researched and tried to find solutions of my own, but as Rice's theorem is not applicable, I failed at finding a direct proof of undecidability or proof by reduction (as I cannot think of a way to reduce any known undecidable problem to any of these); research includes:

http://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW7Sols.pdf
It seems sensible to perform a breadth-first-search for $\mathcal{R}$, though the presented solution would need to be modified to reflect the different model. This problem seems to be decidable.
Can an alphabet be extended in a reduction proof? (with sample problem)
This is quite precisely a question about $\mathcal{S}$, but the proposed reduction reduces the problem to a non-recursive problem, which obviously yields no result at all.

None of my own ideas worked out, thus I have little to show for; I had a vague idea of reducing $\mathcal{S}$ to $\mathcal{R}_\mathcal{S}$ by flipping the input (as well as the movements of the Turing Machine); the main problems are that I have no solution for $\mathcal{S}$ (although I expect it to be non-recursive), and a reduction would need to use an unbounded tape, which may (or may not) break the problem.

Thus, any help (or hint at methodology) would be greatly appreciated.


texts: Can someone clarify this unification algorithm?

texts:
I've been having trouble understanding a unification algorithm for first order logic, as I don't know what a compound expression is. I googled it, but found nothing relevant. I also don't know what a list means in this context. A list of what?

Edit: I think I've cleared up with compound expressions are and what lists contain in this context, from Yuval Filmus's answer. However, now I have other problems:

In Unify-Var, it uses the variable(?) val, even though val was never declared. Could {var/val} E theta (with E meaning is a subset of) instead be a function that returns whether var is already in theta, regardless of what value it's mapped to?
The algorithm seems to break when unifying compound expressions. To unify them, it breaks compound expressions into two lists: one for function symbols and one for arguments and then calls Unify on both individually. When trying to unify the list of function symbols, it breaks the list into individual function symbols and then calls Unify on each individual function symbol. But Unify has no case to deal with function symbols, so it just returns failure, even if the two function symbols to be unified are identical!

Thanks.

Pseudocode from Artificial Intelligence A Modern Approach (3rd Edition): Figure 9.1, page
328:

function UNIFY(x, y, theta) returns a substitution to make x and y identical
  inputs: x, a variable, constant, list, or compound expression
          y, a variable, constant, list, or compound expression
          theta, the substitution built up so far (optional, defaults to empty)

  if theta = failure then return failure
  else if x = y the return theta
  else if VARIABLE?(x) then return UNIFY-VAR(x, y, theta)
  else if VARIABLE?(y) then return UNIFY-VAR(y, x, theta)
  else if COMPOUND?(x) and COMPOUND?(y) then
      return UNIFY(x.ARGS, y.ARGS, UNIFY(x.OP, y.OP, theta))
  else if LIST?(x) and LIST?(y) then
      return UNIFY(x.REST, y.REST, UNIFY(x.FIRST, y.FIRST, theta))
  else return failure

---------------------------------------------------------------------------------------------------

function UNIFY-VAR(var, x, theta) returns a substitution

  if {var/val} E theta then return UNIFY(val, x, theta)
  else if {x/val} E theta then return UNIFY(var, val, theta)
  else if OCCUR-CHECK?(var, x) then return failure
  else return add {var/x} to theta

Figure 9.1 The unification algorithm. The algorithm works by comparing the
structures of the inputs, elements by element. The substitution theta that is
the argument to UNIFY is built up along the way and is used to make sure that
later comparisons are consistent with bindings that were established earlier.
In a compound expression, such as F(A, B), the OP field picks out the
function symbol F and the ARGS field picks out the argument list (A, B).


texts: To which character or characters does a Kleene star apply?

texts:
If you have a Kleene star applying to a set of characters not in any closure, does it apply to that whole string, or just the one character it belongs to? Any examples I search don't specify.

For example:

(A)BB*

Does this mean 1: one A followed by zero to an infinite number of BB's, or does it mean 2: one A followed by at least one B and zero to infinite number of B's?


texts: Prove that palindromes are not regular language without using pumping lemma

texts:
I came across this question. Palindromes are not regular: It is easy to prove it using pumping lemma. The problem is I want an explicit proof without pumping lemma. I came up with a solution. It goes like this.
Let us assume a language L which is palindrome so L can be expressed as x.xR where xR is reverse of x. If x is a regular language then xR will be too and hence the palindrome will be regular. What if x is not a regular language. Lets say x is 1^n0^n. It is not possible to draw a DFA for this as this string needs memory to keep the count of 1s so that it can add exact number of 0s. Since DFA doesn't have memory so it wont be possible to make a DFA for this, but xR = 0^n1^n and L=x.xR that is 1^n0^n.0^n1^n is still palindrome but not a regular language. So we can say palindromes are not regular.
I remember from my undergrad class to prove some language is not regular it is sufficient to give one negative example.
Will this approach work?


texts:
In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees :

1) The first one:
Node $a$ is parent of $b$ and $c$.
Node $e$ is parent of $a$ and $d$

2) the second one:
Node $a$ is parent of nodes $b$, $c$ and $d$.

Can we say that their topology are different, in the sense that the set of relations parents/children are different?


texts: Different context-free grammars for the same language

texts:
In context-free grammar, are both the following grammars correct for the same language?

$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$

(grammar one)

$S \to S_1 | S_2$

$S_1 \to A_1B_1$

$A_1 \to aA_1 | a$

$B_1 \to aB_1b | \epsilon$

$S_2 \to A_2B_2$

$A_2 \to aA_2b | \epsilon$

$B_2 \to bB_2 | b$

(grammar two)

$S \to S_1 | S_2$

$S_1 \to \epsilon | aA_1$

$A_1 \to aA_1 | aB_1$

$B_1 \to aB_1b | a$

$S_2 \to \epsilon | A_2b$

$A_2 \to A_2b | B_2b$

$B_2 \to aB_2b | b$

Is there a rule I could use to check whether the grammar is correct for the given language (other than trying all the strings that come to my mind)?


texts: Coordinated Attack Problem On The Arbitrary Graph

texts:
Let  consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack.

It's well known  that Two Generals' Problem represents a version of the Consensus Problem with unlimited number of the stopping failures, I think this is the only reason why Two Generals' Problem and Generals' Problem (with $n$ generals) don't have solution.

There is a proof of lacking solution for Two Generals' Problem (can be found in the textbook of Lynch).

The following is the exercise from the textbook of Lynch, that I have not solved so far.

Show that a solution to the (deterministic) coordinated attack problem (Generals' Problem) for any nontrivial connected graph implies a solution for the simple graph consisting of two processes connected by one edge. (Therefore, this problem is unsolvable in any nontrivial graph.)

Apparently, there is a reduction from an edge case to graph. But how to show it mathematically rigorous?

Addendum:

Can I say something like this?
When we are given the primary problem of Two Generals and they initial values $a_i$ (inclination whether to attack or not), we in arbitrarily add more dummy generals with the only requirement if $a_1=a_0=a$ for primary problem set all dummy's general input to $a$, otherwise set arbitrary input value $b \in \{0,1\}$. Find the solution on the graph, the solution on the graph is the solution for the primary problem.


texts: Classes and Algebras: Which begat which?

texts:
Way back in the day I took a course on discrete structures and learned about how the mathematical notion of an algebra is akin to the class data type.

But I didn't know enough at the time to ask whether algebras are used to model classes or whether classes are actually derived from algebras (historically, technically...in whatever sense of 'derived' you like).

Wikipedia and Google weren't much help. Anyone have any idea?


texts: Is a language with only a stack of fixed-size integers Turing-complete?

texts:
I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.

There is only one data type in it (integer, since that's the only data type brainfuck supports). It supports functions and subroutines (to which you can pass integers by value, but not arrays, though you can access an array in the global scope from within a function/subroutine) but it does not support recursion (all function and subroutine calls are inlined). It supports statically allocated arrays (size known at compile time) and has just one unbounded stack. You can store as many items as you like in the stack, unlike with arrays, but you only have one stack for your entire program.

I have these limitations to achieve a balance between ease of use, and fast generated code.

However, I never studied any of this stuff and I actually started this project to learn about compilers (by making one), therefore my question is:

From the above description, is this language turing complete?


texts: An exact solution for biclique vertex-cover problem on a bipartite graph

texts:
The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs).

It has been shown that "Biclique Vertex-Cover" is not fixed-parameter tractable unless P = NP in Covering Graphs with Few Complete Bipartite Subgraphs.

Most of the work in the literature proved the hardness of the problem in general/special cases. However, I need an exact algorithm for solving this problem on bipartite graphs. An approximate algorithm with a guarantee is also good (I'm aware of "Clustering and the Biclique Partition Problem", but it provided an approx solution for "Biclique Vertex Partition" not vertex-cover i.e. the provided solution is for disjoint bicliques not possibly overlapped ones).

Is anyone aware of an exact algorithm for "biclique vertex-cover" problem? Potentially, with time complexity analysis?

A naive algorithm, perhaps, would be starting from the whole bipartite graph to check for a biclique that covers all vertices (covering with one biclique). If not successful, we check subsets by removing one vertex and investigate if there exist two bicliques in this set that cover all vertices (trying to cover with two bicliques), and so on (trying to cover with more bicliques until reaching "k").


texts: Minimal DFA accepting strings whose length is divisible by $x$ or $y$

texts:
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:

If one of $x,y$ is a multiple of the other, then the minimal DFA contains $\min(x,y)$ states, and otherwise it contains $\operatorname{lcm}(x,y)$ states.

Is this true for all values of $x$ and $y$?
Also, what happens if we replace the condition "divisible by either $x$ or $y$" with the condition "divisible by both $x$ and $y$"?


texts: Best data structure for queries about subsets?

texts:
I am interested in finding a data structure that supports the following operations:

Insert Set: Insert a set into the data structure.
Decide Subset: Determine whether a given set is a subset of any of the inserted sets.

The most obvious way to implement this would be as a hash set of hash sets, but I think some performance gains could be had by exploiting common subsets among the stored sets. For example, if {1} and {1,2} were both stored, only {1,2} would need to be kept. Any ideas?


texts:
I'm trying to figure out how to prove or disprove the following statement:

  Infinite union of recursive languages is recursively enumerable.

I know how to prove that infinite union of regular languages is not recursive, but I can't figure out how to prove the statement above. Intuition is telling me that the statement is true, but I'm not sure. Does anybody know how would I go about it?

Any help is greatly appreciated.


texts: Can you apply neural networks to design algorithms?

texts:
I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math problems.

A few CS/math friends were teaching me about P=NP and I was wondering whether a potential way to identify an algorithm that can convert the exponential time it takes to solve NP solutions into polynomial time is to use a genetic algorithm that applies brute-force until such an algorithm is identified.

Apologies if I’m misunderstanding anything or being too naive. Thank you for your time.


texts: What are flops and how are they benchmarked?

texts: Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked though? Certain floating point operations are much heavier than others, so how exactly would a FLOP be a benchmark for computing power?


texts: For data-path cycles in MIPS, what determines wheter a control signal gets the "don't-care" value?

texts:
For example for the  sw command in MIPs, the control signal values are

ALUOp1: 0

ALUOp: 0

RegWrite: 0

MemRead: x

MemWrite: 1

Branch: 0

ALUsrc: 1

RegDest: x

MemToReg: x

Why do memRead, RegDest and MemToReg have the values of x? Why not just 0?


texts: Why we can't have FPTAS for strong NP complete problems

texts:
I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack.

But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the same but understood very less.


texts: timed automata - advance only in certain states

texts:
I am currently looking into timed automata for a project.
I am thinking about a timed automaton where a clock only advances when the automaton is in a certain state.
However, my little knowledge in the domain makes me wonder whether somebody already defined timed automata like that.

As an example:
I.e. I have a timed automaton with two states: L0 and L1.
My clock is c - the total time that the automaton spent in time L1.

The clock c should only advance when the automaton is in state L1.

(see upper part of drawing)

Solution with my existing knowledge (not very elegant):

I can see a way where I could use event-clock automata (1) to achieve this, by triggering an event a and on entering L1 the value of c is set to:
c := c - xa
where xa is the time since event a.
(See lower part of the drawing)

However, I'm not convinced of this solution as it is inelegant, further I'm not sure whether timed automata allow for the setting of clocks. So far I only read about reset to zero.

(1) http://pub.ist.ac.at/~tah/Publications/a_determinizable_class_of_timed_automata.pdf


texts: Stroke Width Transform: Gradient Direction and Rays

texts:
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

Now, up to this point I got lost on the second paragraph of section 3.1 of the paper, which is getting a gradient direction and finding the other point for the ray:
" ...then dp must be roughly perpendicular to the orientation of the stroke... " and " ... dp(dq = -dp±π/6) ... ". Does this mean I'll have to take a wild guess as to where the direction of dq is? or have I misinterpreted it?


texts: Why is the size of the search space 2057 in the 8-queen puzzle?

texts:
In the 8-queen puzzle, to reduce the search space, we can use an incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc., avoiding the slots that are already being occupied.

According to Peter Norvig's book, there are only 2057 possible sequences. Where does that number come from?


texts: Drawing Moore Finite State Machine Diagram

texts:
In an upcoming of an exam of 'Digital Techniques', we have to be able to design sequential circuits, and in particular we have to draw Moore FSM's when the equations for the output and next states are given. One of the exercises we could use to practice our skills is:

"A sequential circuits with two flip-flops A and B, one input X and one output Z is specified by the following equations:

A(t + 1) = X'(t) A(t) + X(t) B(t)
B(t + 1) = X'(t) A'(t)
Z(t)     = X(t) A(t)  + X'(t) B'(t)

Transform and implement the circuit described above as a Moore Finite State Machine (FSM) using only NAND gates and SR flip-flops. Give the state table, state diagram and logic diagram."

I am confused: Moore FSM's have outputs that only depend on the current state, not on the input. The next state, Z(t+1), can depend on the input, since Z(t+1) may depend on A(t+1) and B(t+1), which in turn may depend on the input.

My question is: how can we transform this into a Moore FSM? I have already derived the state table:

X(t) | A(t) | B(t) || A(t + 1) | B(t + 1) | Z(t)
 0      0      0         0          1        1
 0      0      1         0          1        0
 0      1      0         1          0        1
 0      1      1         1          0        1
 1      0      0         0          1        0
 1      0      1         1          1        0
 1      1      0         0          0        1
 1      1      1         1          0        1

I can not create a function mimicking Z(t) that only depends on A(t) and B(t). As we can see in the state table, A(t) = B(t) = 0 implies Z(t) = X'(t), something that seems to be unresolvable.

(Note: I am a first year student, so I don't know too much about FSM's and sequential circuits, but I'm not an idiot either.)


texts: Undecidability of the following language

texts:
So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to construct a $TM$ deciding $A_{TM}$. So by contradiction $A$ is undecidable. But what if the language was $\{ \langle M,w \rangle \mid \text{M accepts } w \text{ but on input } w^R \text{halts and rejects} \}$?

I was thinking to prove that it's r.e, we can construct a Turing recognizer, say $K$, which recognizes this language by simulating $M$ on $w$ and do whatever $M$ does. But how does the machine know what's $w$ and $w^R$? Non determinism maybe? Or am I looking at it the wrong way?

And to prove that it's undecidable would we use the same approach as that for $A$?


texts: Why octal and hexadecimal? Computers use binary and humans decimals

texts:
Why do we use other bases which are neither binary (for computers) nor decimals (for humans)?

Computers end up representing them in binary, and humans strongly prefer getting their decimal representation. Why not stick to these two bases?


texts: Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$? How to substitute arguments?

texts:
I'm having difficulties understanding lambda calculus, specially identifying what's a redex. Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$?

The book uses
$(\lambda u. z) [u \to (\lambda v. v)]$,

but isn't $(\lambda s. \lambda z. (\lambda u. z))[s \to (\lambda v. v)]$ valid too?


texts: Are there any interesting terms in pure LF or $\lambda\Pi$?

texts:
In my searching, I've seen that if Church numerals are encoded in a dependently typed Lambda calculus, that we can't derive induction or that $0 \neq 1$.

I know that LF and the dependently typed Lambda calculus (from the Lambda cube) are often used to model logic, but any actual systems I've seen based on this augment it with inductive data types, propositional equality, etc.

I'm wondering, can anything non-trivial be done in a pure dependently typed Lambda calculus, without adding inductive types or such? I.e. is there anything we can encode (i.e. length indexed vectors, equality, etc) and prove things about in a dependently typed lambda system that we can't in a Simply Typed System, or something like System F?

I know that dependent types don't give us anything extra for computability, but I'm wondering about expressiveness.


texts: How to compute multiplication in $ \mathbb{Z} / n\mathbb{Z} $?

texts:
Good day,

I have heard about the Montgomery modular multiplication, and the Barrett_reduction; (or any other) But in practice I don't understand how could I implement a multiplication algorithm in a Ring modulo n.

I am looking for such algorithm in an JavaScript environment using an accumulator.

Edit: I found what I was looking for:
To multiply A x B mod M: (Ai being each digits of A from left to right)

acc <- B * A0
i<-1
While i <= A.length-1 do
   acc <- (acc * 10 + B * Ai)
   while acc>= M do acc-= M end
   i++
End
Return acc


texts: How do I replace a D Flip Flop with a JK Flip Flop

texts:
Hello I have this circuit with this I want to learn about Mealey and Moore.

Is this a Mealy Automata? I would say yes because of the upper LED depends on the variables I got.

Otherwise isn't the line of J the next State? So it is a Moore because it only depends on its states?

Now I want to replace the D Flip Flop with a JK how could I do this?

I would just implement a JK to change it but I guess there are things that have to be done so the automata has the same outputs.
Any suggestions on how to do this?

Thanks


texts: Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

texts:
A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:

|               |
|       |       |
|   |   |   |   |

On the other hand, the following configurations would be invalid:

|
|  |
|  |  |

reason: 3rd tree should be higher than the 2nd one

|  |
|  |
|  |

reason: consecutive trees cannot have the same height

Given a sequence of physical trees in a garden, what is the minimum number of physical trees which must be cropped/cut in order to achieve the pattern desired by that gardener?

First, the heights of the physical trees in the garden can be represented by a sequence of integers. For instance, the three examples above can be represented as (3  1  2  1  3), (3 2 1) and (3 3).

Mathematically speaking, the problem maps to find the minimum number of negative sums which must be applied to a sequence of integers (a0, a1, ..., aN) so that each pair of consecutive integers (ai, ai+1) in this sequence alternates between strictly decreasing (ai < ai+1) and strictly increasing (ai > ai+1) .
Example: In (2, 3, 5, 7) , the minimum number of negative sums is 2. A possible solution is to add -2 to the 2nd element and then add -3 to the last element, resulting in (2, 1, 5, 4).

My search model is a graph where each node represents a sequence of physical tree heights and each edge represents a decrease of the height of a tree (from now on called "cut"). In this model, a possible path from the initial node to the goal node in the above example would be

initial node: (2,3,5,7)
action: sum -2 to a1
intermediate node: (2,1,5,7)
action: sum -3 to a3
goal node: (2,1,5,4).

I have used a breadth-first search to find the shortest path from the initial node to the goal node. The length of this shortest patch is equal to the minimum number of trees that must be cut.

The only improvement to this algorithm that I was able to think was using a priority queue that orders the possible nodes to be explored in increasing order 1st by number of cuts (as traditional BFS already does) and 2nd by the number of  "errors" in the sequence of integers in the node: triplets which do not match the required up/down pattern, ie. (ai < ai+1 and ai+1 < ai+2) OR (ai > ai+1 and ai+1 > ai+2), plus the number of consecutive equal numbers pairs  (ai == ai+1)  . This increases the probability that the goal node will be reachable from the first nodes with N-1 cuts in the queue when the times come to evaluate them. However, it is only useful to reduce the search space of nodes with N-1 cuts and not the complexity of the whole search.

The time required to execute this algorithm grows exponentially with the number of the trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up ?


texts: What are applications of computational models beyond P?

texts:
If I may summarize how I feel about collapse of the polynomial hierarchy:

Are intractable models of computation, including collapse of $\mathbf{PH}$  or $\mathbf{PSPACE}$ above but not down to $\mathbf P$ useful for any reason besides the off chance they might collapse? Obviously "useful" is broad - I would gladly be interested in answers outside of computer science, but I am wondering if their study helps us understand really anything besides them themselves.

I am taking complexity theory and have essentially been wondering this entire semester, if my increasingly fluency in problems of the form $\exists\forall\exists\forall...$


texts: Available algorithms for drawing (filled) Bézier paths

texts:
There are plenty of libraries around allowing to draw Bézier paths, but not that much information about how to implement one of those libraries.

The question is: What algorithms are used for drawing Bézier paths?

Current work:

Searching on Internet, I found many documents about drawing Bézier lines (unfilled) using segments. This is obviously not enough.

I implemented a pointInsideBezierPath function, it actually solve the equations in the standard algebraic way. Even if that could work on a GPU, I am concern about efficiency for drawing large Bézier with anti-aliasing.

I also had a look to convert the shape into triangles for fast drawing with the GPU.

To summarize, there are solutions, but I wonder which is the modern state of the art to this respect.

Edited:

  What are your requirements? How large are paths? What degree? What continuity?

Requirements: Well, setting requirements without understanding technical limits is not a good deal, but I guess the typical ones:

A Path is an ordered list of Bezier curves.
A Path is rendered by a stroke and a fill. Each accepting multiple rendering properties (color, gradients, etc.)
Rendering must allows anti-aliasing.
Joining point between bezier are limited only by it position
Rendering is limited by the rectangular and discrete size of the surface.

Size of Paths: any, performance is obviously affected.
Degrees: lines to cubic (1-3)

  I thought that recent GPU have it as built-in.

Not that I know about.

  BTW if you need some actual code then your question is off-topic here.

I know, I deliberately asked here and not in stackoverflow because I do not want code (way to broad anyway) but algorithms names, papers and comparisons.


texts: Problem in finding the floating point representation?


texts: Flaw with Cross Entropy Error in Neural Networks

texts:
I've recently been working on creating a neural network to classify handwritten digits. I implemented 1-of-N encoding such that there are the same number of output nodes as possible digits (The expected output is 0 for all digits' nodes except for the digit that was inputted, which would be 1).

Because this is a classification problem, I opted for Cross Entropy Error. I followed this model shown here: https://visualstudiomagazine.com/articles/2014/04/01/neural-network-cross-entropy-error.aspx
and also shown here:
http://www.mathworks.com/help/nnet/ref/crossentropy.html

The error function is:

$$-\frac1n\sum y\ln(\hat y)$$

Where $y$ is the expected output and $\hat y$ is the predicted output.

However, after I implemented my network I noticed a problem. Because this formula for cross entropy error does not account at all for the error of the predicted output for the nodes that have an expected output 0 (since the CE function multiplies all of those costs by the expected 0), the network tunes the weights/biases to always output nodes close to 1. Therefore, I end up getting a list of 1s. According to the CE cost function this is good because one of the outputs is spot on, but it doesn't even look at the other nodes' error  (which is huge), so it is impossible to decide on one output.

Maybe I'm missing something? I see the alternate CE function is

$$-\frac1n\sum y\ln(\hat y) + (1-y)\ln(1-\hat y)$$

but according to the MathWorks link above, it shouldn't be used for 1-of-N encoding where there are more than $N=1$ output nodes (Not sure why this is the case).

So my question would be:
Why is the first Cross Entropy Error equation viable for classification if it does not account for the error of the nodes where 0 is expected, as it always tends all the nodes to 1?


texts: Finding the timestamps of processes implementing Lamport's clocks

texts:
I have been asked this question, but don't know how to go about answering it.

Three process, which are implementing Lamport's clocks, are running and a lot of events are taking, place including some messages being sent between the processes. The arrows and circles represent in-processor events and messages being sent between process. Assume all clocks starts on 0 and the time goes from left to right. Provide the logical timestamps associated with each event.

To my understadning each circle will mean +1 increase in the proccess clock and the arrows means that it should add the time from where the process is from +1 to the process which receives the arrow. Is this a correct understanding of the task or am I missing something?


texts: Nondeterministic Logarithmic-space in directed graph

texts:
I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the following problem.

Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem.
To show that the problem is $NL-hard$, start from problem $s; t-connectivity$ and as an intermediate step, create a acyclic graph $G^a$ which is $s’; t’- connected$ if and only if the original graph $G$ is $s; t- connected$.

The author has set as hint: use the length of the paths of a vertex $x$ at a vertex $y$.


texts: show that in every infinite computably enumerable set, there exists an infinite decidable set

texts:
I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set.

As an attempt to solve the problem, I could only think of a proof by construction. Without loss of generality, let the alphabet be $\Sigma=\{0,1\}$. The construction goes as follows, suppose that $TM$ $M$ recognizes an infinite computably enumerable set $L$, we can form a decidable language $D \subseteq L$ as follows:

  1) lexicographically enumerate all input words $w$ in $\Sigma^*$ and repeatedly perform steps $a-b:$

    a) at the $k$th step, run $M$ on input words $\{w_0,w_1,...,w_k\}$ for $k$ steps, where words $\{w_0,w_1,...,w_k\}$ are lexicographically ordered

    b) if $M$ accepts an input word $w \in \{w_0,w_1,...,w_k\}$ from step 2, include $w$ in a temporary language $D_{temp}$

  2) partition the words in $D_{temp}$ into two, those starting with $0$ are $\in D$, while those starting with $1$ are $\not \in D$, along with all other words $\Sigma^* - D_{temp}$.

Step (1) does not loop in a word $w$ since each run of step (1) is limited for a finite number of $k$ steps. Is this construction okay ? Or did I miss something ...


texts:
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.

We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph.

If possible, describe one algorithm that is reduction-based (that is, make some modification to the graph so that application of Floyd-Warshall, or any other "known" algorithm, and then deciphering the answer will give the result, see http://en.wikipedia.org/wiki/Reduction_(complexity)) and one that is "direct" (that is, make some modification to Floyd-Warshall in order for it to solve this problem).


texts: Is SRM necessary to prove that a countable union of agnostic PAC learnable classes is nonuniformly learnable?

texts:
The following I believe is a direct proof of this fact. If a learner is tasked to be $\epsilon$-competitive with a hypothesis $h \in \mathcal H_n$, where $\mathcal H_n$ is agnostic PAC learnable, it should be sufficient to just agnostic PAC learn on $\mathcal H$.

Suppose $\mathcal H = \bigcup_n \mathcal H_n$ where each $\mathcal H_n$ is PAC learnable.

Fix $\epsilon,\delta,h \in \mathcal H$ where $h \in \mathcal H_n$. (The textbook Understanding Machine Learning implicitly assumes it's efficiently computable to assign $h$ to a $\mathcal H_n$, which I'm fine with.) $\mathcal H_n$ has the uniform convergence property with bound $m_{\mathcal H_n}(\cdot,\cdot)$ by hypothesis. Let m = $m(\epsilon/2, \delta, h) = m_\mathcal {H_n}(\epsilon, \delta)$. Take $S \sim \mathcal D^m$ and run ERM over $\mathcal H_n$ to return an $\epsilon/2$-accurate, $\delta$-confident PAC hypothesis $h'$ in $\mathcal H_n$. In particular $|L_S(h') - L_{\mathcal D}(h')| < \epsilon/2$ and $|L_S(h) - L_{\mathcal D}(h)| < \epsilon /2 $ with probability $1-\delta$ by uniform convergence. $L_S(h') \leq L_S(h)$ by the definition of ERM. Putting this together with triangle inequality and we have $L_{\mathcal D}(h') \leq L_{\mathcal D}(h) + \epsilon$ with probability $1-\delta$ as desired.

I think this proof is correct. I'm working through Chapter 7 of Understanding Machine Learning which prefers using the SRM paradigm to prove this result. It seems like a direct proof is possible, and perhaps SRM is important but it's certainly not needed in this chapter to prove this theorem.

Is this correct?


texts: Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

texts:
I'm trying to understand how the construction of simple grammars works.
In my textbook, there's the following example I am supposed to find a grammar for:

Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$. Find a grammar $G = (\Sigma, N, S, P)$ - where $N$ denotes the non-terminals, $S$ the start symbol and $P$ the production rules - such that $L(G) = L_1$, i.e. the grammar $G$ generates the language $L_1$.

These were my first thoughts analyzing the problem:

We need to have the same number of $a$'s and $b$'s
We need to have the same number of $c$'s and $d$'s
There needs to be at least one $a$ and one $b$
Examples of such a string: $aabbcccddd$, $ab$, $aabbcd$

Furthermore, let $\lambda$ be the empty symbol.
The start symbol $S$ should map to something like:
$$ S \rightarrow XY$$
Then
$$X \rightarrow aZb, \; Z \rightarrow X | \lambda$$
$$Y \rightarrow cYd | \lambda$$
Would something like that work? I'm confused because the textbook presented similar grammars and the production rules almost never used the empty symbol ($\lambda$).
Is it possible to construct this grammar without using $\lambda$?


texts: Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform

texts:
Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\dots, i_k}$ has distribution $U_k$ (uniform distribution on $\{0,1\}^k$).
Problem: Consider probabilistic algorithm $A$ that has oracle access to the input of length $n$. It means that algorithm $A$ can adaptively request $k$ bits of input (in more detail, $A$ can request one bit, then based on the oracle answer request another bit and repeat it not more than $k$ times).
Prove that if $D$ is $k$-independent distribution than $Pr_{x \sim D} [A(x) = 1] = Pr_{x \sim U_n}[A(x) = 1] $
First of all, I don't understand how adaptivity can potentially help the algorithm to distinguish the uniform distribution from a $k$-independent one. The second question is as in the problem.


texts: How to denote the space complexity in terms of output

texts:
Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage an algorithm needs, i.e. if I have a Turing Machine with three tapes, one for the input, one for the computation, and one for the output, I would like to express the size of each one of them.

Is there a standard way of doing so? If so, is there a reference?

Currently I am using the symbol $\textrm{DATA}$. As an example consider function $list(n) = (1,\dots,n)$. The respective algorithm $List$ for computing the function $list$ is s.t. $\textrm{TIME}(List(n)) \in \mathcal{O}(n)$, since we need to write $n$ symbols, $\textrm{SPACE}(List(n)) = \mathcal{O}(1)$, since we only need to store the current symbol, and $\textrm{DATA}(List(n)) = \mathcal{O}(n)$, since the output is a vector of length $n$.


texts: NPDA transitions to different states by taking same input and popping same top element of a stack

texts:
Suppose i have some NPDA and there is some transition functions defined as:

$\delta(q_{1},a,A) = (q_{2}, A)$

$\delta(q_{1},a,A) = (q_{3}, Z)$

Is it allowed?
I understand, that since the NPDA is nondetermenistic, it's possible to have transitions to different states with the same input character, but what about same element at the top of stack?
Thanks.


texts:
I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum.

public Double dotProduct(List<Double> v, List<Double> u) {
    Double dotProduct = 0;
    for (int i = 0; i < 128; i++) {
        dotProduct += v.get(i) * u.get(i);
    }
    return dotProduct;
}

Will strassen's algorithm perform better?


texts:
This is a homework problem that I have

In a multicore system, you are running the code on the right on each core, and it suffers from false sharing. You can assume t_id is set to a unique thread identifier (e.g. 0-15). How could you change the code to reduce false sharing?

for (int i=0; i<N; i++)
    totals[t_id] += a[i];

What I'm having trouble with is seeing where the false sharing is occurring. It says state t_id is set to a unique thread identifier, so doesn't that mean there's only 1 thread that's accessing the data here?

We only briefly went over false sharing, but from what I've learned false sharing occurs when a cache miss occurs because the data was invalidated previously due to an "irrelevant" data being written/read from a different cache. But if the thread is the same, then doesn't that mean it's the same cache being used to write/read? How would false sharing occur here?


texts: $L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

texts:
It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines.
It was mentioned somewhere that the language $$L = \{x\#x^R \mid x\in\{0,1\}^* \} $$ can not be accepted by a queue automaton. But the language is accepted by a TM. Can somebody explain this apparent contradiction?


texts:
Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs?

Long version and some background:

Before anyone asks, YES, it is a homework and I am not here to find an answer, but only clues to help me get this question right !

I'll translate the question from French :

  We call a universal program (also called interpreter) a program that
  accepts, as an input, another program and simulates it to produce the
  output of this simulated program. A universal program can also be used
  to simulate programs written in this very same language or in another
  language.

  You can suppose, using Gödel's coding, that the program to be
  simulated is given to the universal program in the register r1, and
  the input on which this program but be simulated in the register r2.
  The coding of the program could simply give out the characters of the
  program to be simulated in a table as well as its input registers in
  another table.

  Answer the following questions:

  a. It is possible to write a universal loop program for if-then
  programs?

  b. Is it possible to write a universal loop program for loop
  programs?

  c. Is it possible to write a universal while program for while
  programs? To reach a satisfying answer/proof lever, you could use
  the Church-Turing thesis.

Now the question, is where do I start with this ? My head's going in every direction at the same time, I'm just going crazy.

NOTES :

if-then programs are defined like this :

We consider a if-then program to be defined like a loop program, excepted that there are no loops, but an instruction "if rj then []" (rj is the register "rj", the j'th register)

I know for sure this has something to do with imbricated loops...

Any clues would be greatly appreciated !

Thanks a lot


texts:
I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time.
The setup is as follows:

-Up to 42 groups of 2 persons each.
-3 groups will be paired to be one team
-a game is played between 2 teams (6 groups) and takes 20 minutes
-3 games will be played at the same time, there will be 12 rounds of 3 games
-Every group has the same amount of games
-after every game, the teams change
-What I want to optimize:
 minimize the amount of times a group gets put in a team with another group
 they have already played with (if they played against them it is ok)
 Bonus: Minimize the games a group has to wait until their next game
 (Since only 3 games can be played at once (so 6x3 = 18 groups), there are a lot of
 groups who have to wait for the next round of games.)

I want the program to give me the pairings of the groups and a schedule, if possible.
I am giving the exact numbers, because if it can't be done in polynomial time, but the instance is small enough so exponential time does not matter too much, it is fine with me.
The solution does not have to be optimal, but should be close.

What is a good algorithm or heuristic for my problem?


texts: Algorithm for this problem on generating all permutations

texts:
I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an abstracted version of the problem so that I don't confuse anyone with the specifics.

The problem is like this:

I have a list of groups. each group might have an arbitrary number of elements with some weight in it. A valid vector comprises of exactly one member from each group and has members from each group in the list. The weight of a vector is the product of weights of the members in the vector. I want to find the sum of weights of all valid vectors.

for example:

Group 1:
Member 1, Member 2

Group 2:
Member 3

Valid Vector 1:
Member 1, Member 3

Valid Vector 2:
Member 2, Member 3

We need to find:
(Member 1 * Member 3) + (Member 2 * Member 3)

The groups don't intersect. Which means a member can belong to only one group.  What I am doing currently is a brute force like solution, where I start with creating a global list and populating it with the members of group 1. I then go to the next group (group 2) and extend the global list by multiplying each member of group 2 with each member in the global list. Thus completely replacing global list with all pairs of members from group 1 and group 2. In this manner, I keep extending the global list till I have processed all groups.


texts: How would the Internet work between planets?

texts:
Say that in the future there are people on other planets, e.g., Mars.  The one-way communication delay to Mars is between 3 and 21 minutes.

Say we want to connect the people on Mars to the Internet.  How would we deal with the communication delay? For example, we don't want to get request timeouts as fast as we have them normally (on Earth).  Would network protocols need to be adjusted or modified to deal with the increased latency?


texts: Propositional logic and connectives(translating to english)

texts:
I want to know some stuff about translating compound statements to english:

For the propositions below:

p: You have the flu.
q: You miss the final examination.
r: You pass the course.

I want to know how to translate the following compound proposition to english:

1). p or q or r.

I tried something like this:

You have the flu or you miss the final examination or you pass the course.

I was just wondering about the usage of commas.

2). (p implies not r) or (q implies not r)

I tried something like this:

If you have the flu, then you do not pass the course, or if you miss the final examination, then you do not pass the course.

Again, I was wondering about the comma usage.

Can someone please help?


texts: Reasons for why x - 1 and x -1 gives different result in some languages

texts: I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find any functions related to this


texts:
I'm familiar with applying the sutherland hodgeman algorithm for convex polygons(and even concave polygons with a slight modification) against convex clipping windows.

However, if I am to modify the sutherland hodgeman algorithm in such a way that I can clip a concave polygon against a concave window, is that possible?

My question is precisely this:

It's a question that has come in my exam and the only thing I thought of was using the Weiler Atherton algorithm, but that's no amendment to the Sutherland Hodgman approach and is a different algorithm altogether.


texts:
I was looking for non-recursive implementation of DFS algorithm.

I found the following pseudocode on this page.

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

From what I understand,  if we change the line 8 to be:

for all edges from v to w in G.adjacentEdges(v),if w is not discovered do

it would speed up the code, because whats the point of pushing already visited vertices on to the stack? Am I right in this assumption?


texts: Under which conditions a given program is deterministic on x86_64 machines?

texts:
Given a certain x86_64 "vanilla" binary, without micro-architecture instructions, which can therefore be executed by any x86_64 computer, what are the conditions for the result to be deterministic ?
Can we assume that without parallelization, without the use of entropy-generating instructions, the result will be "bit-perfect" on different CPU models ? If not: why ? Can the floating point implementation from different CPUs change the results ?
By deterministic, I mean the same inputs will always produce the same outputs. I also assume inputs are what we classically assume to be inputs: parameters of the programs that can be fully controlled by the user like what we can pass as command line parameters, for example.
To be clear, I'm not talking about the program generation, or the use of specific instructions on different micro-architecture, or scheduling differences, I'm wondering about the "best case scenario": is this best case scenario reproducible, and can we ensure some program will be reproducible ?


texts: What is spatial information in neural network?

texts:
The architecture of the CNN model contains several convolutional layers, non-linear activations, batch normalization, and pooling layers. The initial layers learn the low-level concepts such as edges and colors and the later level layers learn the higher level concepts such as different objects.
At a lower level, the neurons contain information for a small region of the image, whereas at a higher level the neurons contain information for a large region of the image. Thus, as we add more layers, the size of the image keeps on decreasing and the number of channels keeps on increasing. The downsampling is done by the pooling layers.
For the case of image classification, we need to map the spatial tensor from the convolution layers to a fixed length vector. To do that, fully connected layers are used, which destroy all the spatial information.
For the task of semantic segmentation, we need to retain the spatial information, hence no fully connected layers are used. That’s why they are called fully convolutional networks.

Can anybody elaborate that what is spatial information in CNN and how it relates with FCN?


texts: Given a set of 2D vectors, find the furthest reachable point

texts:
Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$
  Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$
  for all subsets of $S$ (obviously $|P|=O(2^n)$). In
  words, $P$ is the set of all possible vectors we can form by adding
  vectors from $S$.
  What is the length of the longest vector in $P$?

An idea:
(An easy observation is that if all $v_i\in S$ are in one orthant (or quadrant?) we just have to add them. If the vectors are in on hyperplane this is not true.)
Start from an arbitrary vector $v_1\in S$, get the next one $v_2$ (either left or right) and add $V=v_1+v_2$. Generally, at each step $V=V+v_i$. Continue this while $|V|$ is increasing.

At some time we find $v_j$ such that $V=V+v_j$ shortens. Set $V=V-v_1+v_j$ and continue. The idea is to maintain a "window" where we add all the vectors inside. If the next vector (the one side of the window) does not add, remove the first one (the other side of hte window).

I know I am not clear enough but hope you get the idea.

Is this correct? Am not sure...
An other ideas/approaches?

(This, of course, can be generalized to any dimension $k$. I mentioned the 2D case because it is easy to visualize.)

I am looking for algorithms with polynomial time on $n=|S|$.

Related problem: lattice problems.

Let set $S$ be the basis of the lattice $L$. Then $L$ is defined as
$$L(S)=\{\sum_{i=1}^{n}a_i v_i \mid v_i\in S, a_i\in\mathbb{Z}\} $$

Our set $P$ is a special case if, instead of $a_i\in\mathbb{Z}$ we let $a_i\in \{0,1\}$.


texts: Packing rectangles to generate a sprite sheet

texts:
I am writing a sprite sheet generator tool in adobe AIR, and I have to force with the question: How to pack a collection of 2D rectangles to smallest possible 2D rectangle with power of two. (like 1024x444).

I think that this question is NP-Hard. I found good answer for it here.

I thought about another option. What if I cut my rectangles to smaller rectangles. Will this make my life easier?

My XML data will be more complicated, and I am not sure how this will effect the performance of the application that will use the cut sprite sheet.

How ever the difficulty of such problem is probably belongs to P.

Do you think it's possible? What am I missing here?


texts: Through how many levels must cache writeback propagate?

texts:
Suppose that my multicore computer system has the diagrammed memory caches.

+---------+---------+-------------------+
| CPU 1   | CPU 2   | CPU 3   | CPU 4   |
+---------+---------+---------+---------+
| Level 1 | Level 1 | Level 1 | Level 1 |
| cache   | cache   | cache   | cache   |
+---------+---------+---------+---------+
|      Level 2      |      Level 2      |
|      cache        |      cache        |
+-------------------+-------------------+
|                Level 3                |
|                cache                  |
+-------------------^-------------------+
                    |
                    v
                   RAM

Consider a cache line CPU 1 has already loaded and written to, so that the cache line is already dirty in CPU 1's level-1 cache.

CPU 2 now writes to an address in the same cache line. What happens?

To maintain coherency from the perspective of CPUs 3 and 4, is the cache line in question automatically invalidated at level 1 and level 2? That is, does the system have to write the cache line all the way back to level 3? Or does writing it back to level 2 suffice?

If all the way back to level 3, then isn't level 2 pointless? (Surely the answer is no, but why?)

REASON FOR THE QUESTION

This question might interest other readers for various reasons, but I ask because I have been reading Intel's Software Developer's Manual and some interesting documents from the Linux kernel source. Those writings are telling me all about memory barriers, SFENCE/LFENCE instructions and the like; and I am trying to get all the relevant concepts straight in my head. Nevertheless, to the extent of my ability, I have tried to phrase the above question without tying the question to the x86 architecture. I ask today not for minute details of SFENCE/LFENCE, but rather ask for a brief conceptual orientation.

For information, so that you can pitch your answer at my level if you wish, I hold a master's degree in engineering but no C.S. degree.


texts: Disjoint paths of length at most L and the number of nodes to remove to vanish this property - Inequality

texts:
Given an graph $G$ and two, randomly chosen, non-adjacent nodes, let's call them $s$ and $t$,
we make the following two notations:

$P_L(s,t;G)$ = the maximum number of internally disjoint paths (paths that don't have any node in common, except s and t) with a length at most $L$ (L ranges from 1 to |G|).

$K_L(s,t;G)$ = the minimum size of a set of nodes (s and t not included in the sets) with this property - if we remove  the set of nodes, the result is that there are no more paths of length at most $L$, from $s$ to $t$.

I have to prove the inequality
$$ P_L(s,t;G) \le K_L(s,t;G) $$
and specify the values of $L$ (L ranging from 2 to |G|) for which the relation satisfies the equality too, for any chosen graph G and nodes s,t.

The first idea that comes to my mind is to start a discussion based on the values of $L$ and try to prove the relation by induction. Any ideas how?


texts: Search algorithm with constraint of proximity to another point

texts:
Let us consider a plain search algorithm (Dijkstra being one example) which will calculate the shortest path from A to B.

Now introduce the additional constraint that the path must be as close as possible to a third point, C, without necessarily going through it (thus breaking down the route into an A–C and a C–B portion would not work).

A real-world example would be “go from Munich to Lyon via Milan”: a human driver would not take this as a requirement to pass through downtown Milan, but would understand that the route over San Bernardino and through the Fréjus tunnel is preferred over the route along the shores of Lac Léman.

For a route graph, this could be phrased as “find the path from A to B which has the least sum of length and shortest distance between C and any point on the path”.

Is there a standard algorithm (or variation of a standard algorithm, Dijkstra preferred) which satisfies that constraint?


texts:
Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be a counterexample?

Recall the following definitions.

Perfectly balanced node: A node of a binary tree is said to be perfectly balanced if the absolute difference in the number of vertices in its left subtree and its right subtree is atmost 1.

Perfectly Balanced Tree: A binary tree is called perfectly balanced if all its nodes are perfectly balanced.

Trivial Fact: The height of a perfectly balanced tree is $\Theta (\log n)$ where $n$ is the number of nodes in the tree.


texts:
Good evening!

I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form:

$$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$$

Then, tried to estimate the number of recursive calls that would be used by the method call binomial1(100, 50, .25)

public class Binomial {

    public static double binomial1(int N, int k, double p) {
        if (N == 0 && k == 0) return 1.0;
        if (N < 0 || k < 0) return 0.0;
        return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        double p = Double.parseDouble(args[2]);
        StdOut.println(binomial1(N, k, p));
        StdOut.println(binomial2(N, k, p));
    }

}

I think I have $2^N$ recursive calls of binomial1, that is to say 10000 calls with our exemple. Because of this line:

return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);

I would like to explain it better... I think my answer is too intuitive: each time I call the algorithm, I call it twice until N reach 0.

How to improve with an implementation that would be based on saving computed values in an array?


texts: Grammar still ambigous after removing left recursion LL(1)

texts:
I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion:

S -> a b S
S -> S a b
S -> c d
S -> a d

in production number 2  there is left recursion which I removed and I got:

S -> a b S F
S -> c d F
S -> a d F
F -> a b F | EPSILON

But it is still ambigous?