# Question
Title: Can a self-learning appliance be developed?
I have heard of machine learning systems that can learn from trials of data what effect it should have, but I was wondering is it possible to make a learning appliance that builds on past data? Instead of only receiving new entries, once the database is big enough to begin going over it and doing pseudo consideration, drawing conclusions about the data and adding yet more entries to its database purely from looking at its past results? I suppose such a thing would probably eat up memory quickly unless it had a threshold of entries it was allowed to create. (In theory it would take a long time to get it to a state where it can become sentient in that way, through many trial sets before it begins thinking on its own.)

An application of such a thing would go beyond just determining what the best way to optimize code is, or how to beat a player in a game, but a machine that can actually build its own personality.

# Answer
> 2 votes
You may be thinking of some combination of online and offline learning.

Online learning only use new examples to base its learning on, and modifies the model at each step.

Offline learning looks at all available data, then fixes its model and uses that model on new data.

There is some use in creating new examples from existing ones, but this is typically done by hand, as to emulate possible variations expected to appear in actual data (and typically only if you don't have enough data). There isn't much use in automating this, as any conclusions it draws from the data will already be reflected in the model - if we add entries based on these conclusions, and in turn use these to draw new conclusions, either the conclusions will remain exactly the same (i.e. there's no point in adding them), or we'll start to lean towards conclusions not corresponding to the original data, which is not a good idea.

The only way AI can build its own personality, is if you program the potential to do so into it. There's no way AI can suddenly become sentient after playing 1000000000000 games of chess if it's only been taught to play chess and only knows about chess.

# Answer
> 1 votes
The problem with machine learning is the model. The model dictates what will be predicted. You can use a J48 decision tree to model your data and then you can find the best possible configuration for this J48 decision tree (i.e. the one that makes the most accurate decisions). You can even use a tournament model which uses many *different* models, but the **model** is still be whatever your composite, finite, models are.

If you look at scientific history you see that it is the *models* that make breakthroughs--that extend our understanding of nature. The Ancient Greeks had a model of epicycles which explained the orbits of the planets, then Copernicus explained it differently (a different model) which then led to Newton's theory of gravity--then Einstein created a *new* model, the model of General Relativity.

So your "self-learning" algorithm must be able to come up with new "remarkable" models--models which use a different logic from previous ones. This logic cannot be known a priori and thus must come through random chance. A computer with infinite computing power and infinite memory could try *all* possible models and choose the correct one from all of these. Obviously such a program would not realistically compute the correct model in a realistic time frame (as in the age of the universe). You could try some sort of "greedy" algorithm which tries only models which support known "good" models. But, in doing so, you would rule out all models which are completely *unlike* previously tried models.

If you were to honestly look at current research, this is how it is done. New people come in with new models, most of which are complete nonsense. However, every so often, a new person comes up with a *new* model which *does* solve the problem previously unsolvable.

If you really want to create a self-learning algorithm, you have to do two things: 1) you have to create an algorithm capable of asking any question and 2) you have to create an algorithm capable of solving an arbitrary question. It becomes recursive then: if the algorithm can solve an arbitrary question, then it can solve the problem of generating an arbitrary question, then it can solve that problem better and better (as it recurses). Each problem generates questions, which it can then solve recursively.

---
Tags: algorithms, machine-learning
---


# Question
Title: In RSA, must $p$ and $q$ have the same number of bits?
Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that bitsize of p and q must be same. BUT after calculating, i found that bit size could be different also. But time complexity will increase. Can anyone help me?

# Answer
The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = pq$, and the running time of some factoring methods (notably ECM, the elliptic curve method) depends on the size of the smallest prime factor of $n$. Therefore to get the most "bang for the buck", you would like $p,q$ to be both as large as possible under the constraint on the size of $n$ (which determines the speed of encryption and decryption), and so of roughly equal size.
> 7 votes

# Answer
I think it is not required to same bit size but sufficiently large to solve it via factoring it.

Since, anyone knows `n = pq`, prime factor of n can be found to calculate its private key. If your q is too small say 19, and p is very large say 1000 bits prime number, you can easily get p from n just dividing it by a small number. So, both number p and q must be sufficiently large. They cannot be exact of same size but almost equal in size. Size is too large.
> 0 votes

---
Tags: cryptography
---


# Question
Title: What is the fastest algorithm for finding all shortest paths in a sparse graph?
In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall which is $O(V^3)$ but very fast per iteration?

How about if the graph is weighted?

# Answer
> 35 votes
Since this is an unweighted graph, you could run a Breadth First Search (BFS) from every vertex $v$ in the graph. Each run of BFS gives you the shortest distances (and paths) from the starting vertex to every other vertex. Time complexity for one BFS is $O(V + E) = O(V)$ since $E = O(V)$ in your sparse graph. Running it $V$ times gives you a $O(V^2)$ time complexity.

For a weighted directed graph, the Johnson's algorithm as suggested by Yuval is the fastest for sparse graphs. It takes $O(V^2\log V + VE)$ which in your case turns out to be $O(V^2\log V)$. For a weighted undirected graph, you could either run Dijkstra's algorithm from each node, or replace each undirected edge with two opposite directed edges and run the Johnson's algorithm. Both these will give the same aysmptotic times as Johnson's algorithm above for your sparse case. Also note that the BFS approach I mention above works for both directed and undirected graphs.

# Answer
> 8 votes
You can try to make a version of Floyd-Warshall that is faster on sparse matrices.

First, let us recall what this algorithm does:

Let $M$ be a matrix of distances. At the beginning of the algorithm $M\_{i,j}$ is the weight of the edge $i \rightarrow j$. If this edge does not exist then $M\_{i,j}=\infty$.

The algorithm has $V$ steps. In step $k$ of the algorithm, for every pair of nodes $i,j$ we set

$$M\_{i,j} \leftarrow \min\\{M\_{i,j}, M\_{i,k}+M\_{k,j}\\}.$$

Clearly if $M\_{i,k}=\infty$ or $M\_{k,j}=\infty$ then no update needs to be performed. Thus, in the first steps of the algorithm, we only need to perform roughly $deg\_{in}(k) \cdot deg\_{out}(k)$ comparisons where $deg\_{in}(k)$ and $deg\_{out}(k)$ denote the number of incoming and outgoing edges of the $k$-th node respectively. As the algorithm progresses, more and more entries of the matrix $M$ are filled. Hence, the last steps might take much longer.

Note that we need an efficient way to iterate only over non-infinite cells in the $k$-th row and column of the matrix. This can be done by keeping a set of incoming and outgoing edges for every node.

It appears that the first steps of the algorithm can greatly benefit from sparsity. For example, a randomly constructed graph with $E=O(V)$ suggests that the first iteration ($k=0$) is only $O(1)$ steps. If the graph is split into many connected components then the matrix $M$ would remain relatively sparse throughout the algorithm and the total runtime could be as low as $O(V)$. On the other hand, if the graph contains just one connected component, then the last iteration $k=|V|$ is expected to take $O(V^2)$ steps. In this case the total run-time could be $O(V^3)$. As large as the non-sparse version.

# Answer
> 6 votes
There is Johnson's algorithm, whose running time is $O(V^2\log V + VE)$.

---
Tags: algorithms, graphs, shortest-path
---


title: $NP\subseteq TIME[O(n^{\log n})]$

text:
# Question
Title: $NP\subseteq TIME[O(n^{\log n})]$
Is it more plausible that $NP\subseteq TIME\[O(n^{\log n})\]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.

# Answer
It is definitely more plausible, for the simple reason that $NP \subseteq TIME\[O(n^{\log n})\]$ is implied by $NP \subseteq P$. However, it is conjectured that $NP$ requires exponential time (this is known as the *Exponential Time Hypothesis*), and so both statements are conjectured to be false.
> 6 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, np
---


# Question
Title: parsing at semantic level due to ambiguities
I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment

```
pin_value <= bus(5)

```

can be interpreted as picking a child of the bus by index. Here the bus is a signal (an object). However, it can also be that paranthis are applied to a type

```
int_signal <= integer(1.1)

```

which should be interpreted as type conversion.

I wonder. The elaborator should take the parse tree, instantiate objects and tie them together resolving the names. However, the parser has no idea if the prefix at the parensis is a type or array. So, it treats all parensis as indexed objects.

```
simple_assignment ::= target <= value_expression { , value_expression }
value_expression ::= name | literal | function_call | type_conversion
name ::= simple_name | indexed_name
indexed_name ::= prefix ( expression { , expression } ) // example: REG_ARRAY(5)
type_conversion ::= type_mark ( expression )

```

I do not see how can I distinguish between value\_expression and type\_conversion at syntactic level. My parser parses both as indexed\_name and name resolution, when fails to find array object, falls back into type conversion. I am asking if such case analysis it the only way to handle the problem or more strighnforward approach exists that I am missing?

# Answer
> 4 votes
There is no reason to "distinguish between value\_expression and type\_conversion" since, according to the grammar a *type\_conversion* is a *value\_expression*.

You probably mean to distinguish between *indexed\_name* and *type\_conversion* ... and possibly also *function\_call*, but you do not give its syntax, so I am not sure.

I do not know VHDL, but it may be that the syntax you have is the syntax used to explain the language to users, not the syntax actually used in the parser. The parser could simply use a grammar that does not distinguish between *indexed\_name* and *type\_conversion*, and leave the distinction for a later processing stage, when the lexical entities have been identified and their "nature" is known: array, type or function name.

Alternatively, and more likely, it is possible that symbol tables are built as the program is parsed, and when an identifier is found by the lexer (lexical analyser), the lexer will look in the table and will tell the parser whether it is a *type\_mark* or a *prefix* (i.e., array identifier) before the parentheses. Then the parser can proceed with the proper rule for *type\_conversion* or *indexed\_name*.

---
Tags: formal-grammars, parsers, ambiguity
---


# Question
Title: What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?
Whilst reading up on Xorshift I came across the following (emphases added):

> The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush:
>
> `[snip code]`
>
> This generator is one of the fastest generator passing BigCrush; however, **it is only 1-dimensionally equidistributed**.

Earlier in the article there's the following:

> `[snip code]`
>
> Both generators, as all xorshift\* generators of maximal period, emit a sequence of 64-bit values **that is equidistributed in the maximum possible dimension**.

What does it mean for a sequence to be equidistributed in one dimension vs. multiple dimensions vs. not at all?

# Answer
> 5 votes
This website provides the answer:

> A `xorshift*` generator with an n-bit state space is $n/64$-dimensionally equidistributed: every $n/64$-tuple of consecutive 64-bit values appears exactly once in the output, except for the zero tuple (and this is the best possible for 64-bit values). A `xorshift+` generator is however only $(n/64 − 1)$-dimensionally equidistributed: every $(n/64 − 1)$-tuple of consecutive 64-bit values appears exactly $2^{64}$ times in the output, except for a missing zero tuple.

In the case of a `xorshift+` which uses 128 bits of state, `n/64 - 1 = 128/64 - 1 = 2 - 1 = 1`, so the Wikipedia article was correct in stating that that particular generator is only 1-dimensionally equidistributed.

---
Tags: randomness, statistics, pseudo-random-generators
---


title: Odd Parity Function

text:
# Question
Title: Odd Parity Function
I am trying to define a Odd Parity Function that takes three 1 bit inputs and will output a 1 if the 3 bits are odd as a Boolean function.

```
1 1 0 = 0
1 0 0 = 1
0 0 0 = 0
1 1 1 = 1

```

I understand this has a relationship to XOR as I can define this with 2 parameter as

```
X xor Y = (XY')+(X'Y)

```

My assumption is the function will look like this

```
(X xor Y) xor Z = (((XY')+(X'Y))Z')+(((XY')+(X'Y))'Z)

```

**Can this function be simplifed?**

# Answer
Your question is addressed (for the parity of $n$ bits) by Troy Lee, who shows in his paper The formula size of PARITY that the (optimal) formula size (number of literals) of parity on $n = 2^\ell + k$ bits (where $0 \leq k \< 2^\ell$) is $2^\ell (2^\ell + 3k)$. In your particular case, $\ell = k = 1$ and so the formula size is $10$, matching your formula, and showing that it is tight under this complexity measure.
> 2 votes

---
Tags: logic, boolean-algebra, xor
---


# Question
Title: Can a Multi-Tape Turing Machine have an infinite number of tapes?
So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes.

I'd assume not since this would give an infinite transition function?

# Answer
> 8 votes
You need a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

Notice that it especially the number of *heads* should be bounded. Sure, you can use a 2d TM, however, there is still only one head in this model. If you would allow an infinite number of heads, then the configuration of a TM would be infinite. This will cause a lot of problems and would give a quite different model of computation.

# Answer
> 4 votes
You can have infinitely many tapes. Suppose that your transition function is of the following form:

* Each state $s$ is associated with a head number function $h(s,x)$.
* When at state $s$, if the symbol under head $h(s,x)$ is $\alpha$ then change the symbol to $\beta(s,\alpha)$, move the tape $n(s,\alpha)$ steps to the right, update the variable $x$ by the amount $c(s,\alpha)$, and switch to state $t(s,\alpha)$.

The variable $x$ is potentially unbounded, so we access an unbounded number of tapes.

This can be implemented in C and so results in a computable model. One-tape Turing machines can be simulated, so this model is Turing-complete.

You can think of many other models of this sort. For example, and finite number of tapes can be consulted at a time, any finite number of tapes can be modified, any number of heads moved, and so on. We can use several variables rather than just $x$, we can allow more indirect reference, and so on. We can even allow $d$-dimensional tapes. Use your imagination.

One could object (following other answerers and commenters) that the *correct* formulation of a Turing machine with infinitely many tapes allows referencing all of them at the same time; our model can support that to some extent, for example operations of the following sort:

* Write $\alpha$ on all tapes.
* Make a certain transition only if all but finitely many symbols under all heads are $\alpha$.

And so on. As long as the description of the machine is finite and the operations reasonable, the machine can be simulated by a program in C or by a Turing machine. What is *not* allowed is a machine with an infinitary description, but as far as I'm concerned "infinitary description" is an oxymoron.

---
Tags: turing-machines, machine-models
---


title: NP Problems with unique solution

text:
# Question
Title: NP Problems with unique solution
Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.

# Answer
> 12 votes
Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.

UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".

US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be zero proofs, or 2+ proofs, as long as there is not exactly one.

---
Tags: complexity-theory, decision-problem, np, cryptography
---


# Question
Title: Functional dependencies with the same key?
let's consider a table with

```
carID | hireDate | manufactory | model | custID | custName | outletNo | outletLoc

```

I want to evaluate all the **functional dependencies** to bring in first, second and then third normal form.

* Functional dependencies

```
carID,hireDate -> custID

```
* Partial dependencies

```
carID->manufactory, model, outletNo**

```
* Transitive dependencies

```
custID->custName
outletNo->outletLoc

```

Since a car is in a outlet only I have in the partial dependecies this:

```
carID->manufactory, model, outletNo**

```

However this leads to anomalies in insertion (imagine adding a car with no outlet), so should not that be like this?

```
carID->manufactory, model
carID->outletNo

```

But isn't this still an normalisation anomaly?

# Answer
> 1 votes
I think you're misjudging what an insertion anomaly is. It does make sense for the FD to be

```
carID -> manufactory, model, outletNo**

```

since this is just a way to say that the same `carID` always has the same `manufactory`, `model` and `outletNo`.

Now, if you leave aside for a moment `custId` and `custName`, and you decompose the relation this way:

```
R1(carID, manufactory, model, outletNo), R2(outletNo, location)

```

you see that this is a fine decomposition that meets 3NF and is **free from insertion anomalies**: infact you just cannot have, for example, the same `carID` in two distinct `outlets`, or the same `outletNo` with different `location`.

You're right that adding a car with no `outletNo` would be no good since `outletNo` is a foreign key to R2, infact most DBs won't allow you to do such a thing. But this is a different story. Not providing values for mandatory fields is just wrong, and that of course doesn't mean the *design* of the database is not correct.

---
Tags: database-theory, databases
---


# Question
Title: What is the intuition that 2-phase locking achieves serializability (also known as before-or-after atomicity)?
I am learning 2-phase locking and its unclear to me how it achieves/guarantees before-or-after atomicity (i.e. serilizability).

I went to the following notes

http://ocw.mit.edu/resources/res-6-004-principles-of-computer-system-design-an-introduction-spring-2009/online-textbook/atomicity\_open\_5\_0.pdf

on page 9-73 it argues informally:

"Informally, once a transaction has acquired a lock on a data object, the value of that object is the same as it will be when the transaction reaches its lock point, so reading that value now must yield the same result as waiting till then to read it. Furthermore, releasing a lock on an object that it hasn’t modified must be harm less if this transaction will never look at the object again, even to abort. A formal argument that two-phase locking leads to correct before-or-after atomicity can be found in most advanced texts on concurrency control and transactions"

But I didn't really understand the argument and it seems that a formal proof is not trivial or maybe too complicated. So I was seeking an alternate intuitive argument to its correctness. I don't really understand why that is the reason but if someone else has a better way of explaining it or a different perspective, it would be greatly appreciated!

# Answer
> 1 votes
I'll try to phrase it from an intuitive perspective.

Anomalies occur when there are **conflicts**, i.e. when two different transactions write on the same object (clearly if they only read stuff nothing can go wrong). For example, here:

```
r1(x), r2(x), w1(x) // at this point, r2 read garbage

```

2PL is a way to prevent this kind of stuff from happening by putting a lock on every object a transaction deals with, and removing the locks when it's done. The lock can be a **read lock** (when T reads an object) or a **write lock** (when T writes an object) and the rules are simple:

1. refuse a read-lock if a write-lock (from a different T) already held
2. refuse a write-lock if *any* lock (from a different T) already held.

The idea behind these is that you don't want T2 to read something that T1 is going to overwrite (see the first example), and you don't want T2 to write onto something that was previously read or written by T1.

With 2PL, when T wants to read/write on an object it will ask permissions to put a lock on it, and this permission will be granted (or denied) based on the two rules above.

In the example I gave you, with 2PL T1 would have a write-lock on `x` so `r2(x)` would not happen *before* `w1(x)` because the read-lock would not be granted (rule 1).

---
Tags: database-theory
---


title: Negative numbers in Subset-Sum

text:
# Question
Title: Negative numbers in Subset-Sum
If I have a set $A$ with positive and negative numbers, and a number to find C.

It is possible to reduce the problem to one with only positive numbers in set $A$?

I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?

# Answer
Hint: Let $A = \\{ a\_1,\ldots,a\_n \\}$. Choose a large number $M$ and consider the set $\\{ M + a\_1, \ldots, M + a\_n, M, \ldots, M \\}$ ($n$ times the number $M$) and the target $nM + C$. If you want an actual set, instead of taking $n$ times the number $M$, take $M,2M,4M,\ldots,2^{\lceil \log\_2 n \rceil}M$ (we assume that $0 \notin A$; otherwise, remove $0$ from $A$).
> 8 votes

---
Tags: np-complete
---


# Question
Title: Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?
On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a kernel of a certain operating system has been rigorously verified with a modern program verification system. Could hence bugs of the genre of Heartbleed be prevented from occurring via application of program verification techniques today or is this yet unrealistic or even principally impossible?

# Answer
To answer your question in the most concise way - yes, this bug could have potentially been caught by formal verification tools. Indeed, the property "never send a block which is bigger than the size of the hearbeat that was sent" is fairly simple to formalize in most specification languages (e.g. LTL).

The problem (which is a common criticism against formal methods) is that the specifications you use are written by humans. Indeed, formal methods only shift the bug-hunting challenge from finding the bugs to defining what bugs are. This is a difficult task.

Also, formally verifying software is notoriously difficult due to the state-explosion problem. In this case, it is especially relevant, since many times in order to avoid the state explosion, we abstract away bounds. For example, when we want to say "every request is followed by a grant, within 100000 steps", we need a very long formula, so we abstract it to the formula "every request is eventually followed by a grant".

Thus, in the heartbleed case, even while attempting to formalize the requirements, the bound in question could have been abstracted away, resulting in the same behavior.

To sum up, potentially this bug could have been avoided by using formal methods, but there would have had to be a human specifying this property in advance.
> 6 votes

# Answer
Commercial program checkers like Klocwork or Coverity might have been able to find Heartbleed since it is a relatively simple "forgot to do a bounds check error," which is one of the main problems they are designed to check for. But there is a much simpler way: use opaque abstract data types that are well tested to be free from buffer overrun.

There are a number of "safe string" abstract data types available for C programming. The one I'm most familiar with is Vstr. The author, James Antill, has a great discussion about why you need a string abstract data type with its own constructors/factory methods and also a list of other string abstract data types for C.
> 5 votes

# Answer
If you count as a " *program verification technique* " the combination of runtime bound-checking and fuzzing, **yes this particular bug could have been caught**.

Proper fuzzing will cause the now infamous `memcpy(bp, pl, payload);` to read across the limit of the memory block `pl` belongs to. Runtime bound-checking can in principle catch any such access, and in practice, in this particular case, even a debug version of `malloc` that cares to bound-check the parameters of `memcpy` would have done the job (no need to mess with the MMU here). Problem is, performing fuzzing tests on each kind of network packet takes effort.
> 4 votes

# Answer
Using a tighter language doesn't just move goal posts around from getting implementation correct to getting the spec right. It is hard to make something that is very wrong yet consistent logically; which is why compilers catch so many bugs.

Pointer Arithmetic as it is normally formulated is unsound because the type system doesn't actually mean what it is supposed to mean. You can avoid this problem completely by working in a garbage collected language (the normal approach that makes you also pay for abstraction). Or you can be much more specific about what kinds of pointers you are using, so that the compiler can reject anything that is inconsistent or just can't be proven correct as written. This is the approach of some languages like Rust.

Constructed types are equivalent to proofs, so if you write a type system that forgets this, then all kinds of things go wrong. Assume for a while that when we declare a type, we actually mean that we are asserting the truth about what is in the variable.

* int\* x; //A false assertion. x exists and does not point to an int
* int\* y = z; //Only true if z is proven to point to an int
* \*(x+3) = 5; //Only true if (x+3) points to an int in same array as x
* int c = a/b; //Only true if b is nonzero, like: "nonzero int b = ...;"
* nullable int\* z = NULL; //nullable int\* is not the same as an int\*
* int d = \*z; //A false assertion, because z is nullable
* if(z != NULL) { int\* e = z; } //Ok because z is not null
* free(y); int w = \*y; //False assertion, because y no longer exists at w

In this world, pointers can't be null. NullPointer dereferences don't exist, and pointers don't have to be checked for nullness anywhere. Instead, a "nullable int\*" is a different type that can have its value extracted to either null or to a pointer. This means that at the point where the non-null *assumption* starts you either go log your exception or go down a null branch.

In this world, array out of bounds errors don't exist either. If the compiler cannot prove that it's in bounds, then try to rewrite so that the compiler can prove it. If it cannot, then you will have to put in a the Assumption manually at that spot; the compiler may find a contradiction to it later on.

Also, if you can't have a pointer that is not initialized, then you won't have pointers to uninitialized memory. If you have a pointer to freed memory, then it should be rejected by the compiler. In Rust, there are different pointer types to make these kinds of proofs reasonable to expect. There are exclusively owned pointers (ie: no aliases), pointers to deeply immutable structures. The default storage type is immutable, etc.

There is also the issue of enforcing an actual well defined grammar on protocols (which includes interface members), to limit the input surface area to exactly what is anticipated. The thing about "correctness" is: 1) Get rid of all undefined states 2) Ensure logical *consistency*. The difficulty of getting there has a lot to do with using extremely bad tooling (from the point of view of correctness).

This is exactly why the two worst practices are global variables and gotos. These things prevent putting pre/post/invariant conditions around anything. It's also why types are so effective. As types get stronger (ultimately using Dependent Types to take the actual value into account), they approach being constructive correctness proofs in themselves; making inconsistent programs fail compilation.

Keep in mind that it's not just about dumb mistakes. It's also about defending the code base from clever infiltrators. There will be cases where you have to reject a submission without a convincing machine-generated proof of important properties like "follows the formally specified protocol".
> 4 votes

# Answer
Static analysis tools like Coverity can indeed find HeartBleed and similar defects. Full disclosure: I cofounded Coverity.

See my blog post on our investigation of HeartBleed and how our analysis was enhanced to detect it:

http://security.coverity.com/blog/2014/Apr/on-detecting-heartbleed-with-static-analysis.html
> 2 votes

# Answer
automated/formal software verification is useful and can help in some cases but as others have pointed out, its not a silver bullet. one could point out that OpenSSL is vulnerable in that its open source and yet used commercially and industry-wide, widely used, and not nec heavily peer reviewed prior to release (one wonders if there are even any paid developers on the project). the defect was discovered basically through code review post-release, and the code was apparently reviewed pre-release (note though there is probably no way to track who did the internal code review). the "teachable moment" with heartbleed (among many others) is basically better code review ideally before release esp of highly sensitive code, possibly better tracked. maybe OpenSSL will now be subject to more scrutiny. another option is refactoring code to use more secure/safe API libraries to construct the code operations which are less subject to security lapses through programmer errors.

more bkg from media detailing its origins:
> 1 votes

---
Tags: cryptography, correctness-proof, security, software-verification, program-correctness
---


# Question
Title: Complexity of finding the pseudoinverse matrix
> How many arithmetic operations are required to find a Moore–Penrose pseudoinverse matrix of a arbitrary field?

If the matrix is invertible and complex valued, then it's just the inverse. Finding the inverse takes $O(n^\omega)$ time, where $\omega$ is the matrix multiplication constant. It is Theorem 28.2 in Introduction to Algorithms 3rd Edition.

If the matrix $A$ has linearly independent rows or columns and complex valued, then the pseudoinverse matrix can be computed with $A^\*(A A^\*)^{-1}$ or $(A A^\*)^{-1}A^\*$ respectively, where $A^\*$ is the conjugate transpose of $A$. In particular, this implies an $O(n^\omega)$ time for finding the pseudoinverse of $A$.

For general matrix, the algorithms I have seen uses QR decomposition or SVD, which seems to take $O(n^3)$ arithmetic operations in the worst case. Is there algorithms that uses fewer operations?

# Answer
> 8 votes
First of all, people tend to forget that $\omega$ is an infimum. Whenever we write $O(n^\omega)$, we actually mean for all $\gamma \> \omega$, there is an algorithm running in time at most $C\_\gamma n^\gamma$, where $C\_\gamma$ is a constant depending on $\gamma$ (possibly $C\_\gamma \to \infty$ as $\gamma \to \omega$).

Keller-Gehrig showed (among else) how to present a matrix $A$ in *rank normal form* in time $O(n^\omega)$. If $A$ has rank $r$, then a rank normal form of $A$ is $$ S \begin{pmatrix} I\_r & 0 \\ 0 & 0 \end{pmatrix} T $$ for some invertible $S,T$ of the appropriate dimensions; see also Algebraic Complexity Theory, Proposition 16.13 on page 435.

Rank normal form is similar to the rank decomposition mentioned in the Wikipedia article, $A = XY$ where $X$ has $r$ columns and $Y$ has $r$ rows. Indeed, we can take $X$ to be the first $r$ columns of $S$, and $Y$ to be the first $r$ rows of $T$. Given this decomposition, Wikipedia gives a formula for the pseudoinverse using only Hermitian adjoint, matrix multiplication and matrix inverse. Therefore the pseudoinverse can be computed in time $O(n^\omega)$.

---
Tags: algorithms, linear-algebra
---


# Question
Title: How can an artificial neural net change the sign of a weight?
My neural net is having trouble switching the sign of a weight. The issue is that the deltas applied to the weight are proportional to that weight, so when it gets closer to zero, the deltas become smaller and are never sufficient to get it past that point. I tried adding a momentum term with 5% of the previous iteration contributing to the current iteration without success.

In my example I have a very simple neural net with one input and one output and no hidden layer. The transfer function in the neural net is a sigmoid, and the function I am trying to learn is also a sigmoid. Specifically: $y = S(10 x - 5)$ where S is the sigmoid function. The neural net gets to a point where its internal weights are essentially generating a function very close to $y = S(2x + 0)$. At this point it gets stuck because the fitted function is sometimes above and sometimes below the desired function, but the weight on $x$ needs to go up and the weight on the constant term needs to go down. I ran it for 1,000 epochs and 100,000 epochs and it stays in the same place. The initial weights were 0.6 and 0.2, so it made improvements over that.

How can a net get over this hump? Should I not be scaling the weight delta by the weight value?

Here's the reference I'm using for computing the weights for back-propagation. I am using a learning rate of 0.05 and apply the deltas after each training example. The x-values (input) used in training are 0.00, 0.01, 0.02, ... 0.99, 1.00. I always play them in order.

Thanks for your help.

Note: I originally posted this on stack overflow and was directed here.

# Answer
> 4 votes
Your problem stems from the fact that the equations in the link you provide refer to *linear* neural networks. Your network is not linear, as it has a sigmoid activation function. So you need to include its gradient in weights correction. Wikipedia explains how to do it pretty well. Here is an example Python script, which learns your target function in 1000 epochs achieving average error of order $10^{-3}$ in exactly the same conditions as you describe. Increasing the number of epochs makes the error smaller.

**Note:** this is **NOT** a recommended implementation of a neural network - just a demonstration script written on a whim.

```
import math

def sigmoid(x):
    return 1.0 / (1.0 + math.exp(-x))

class Network:
    def __init__(self, w, b):
        self.w = w
        self.b = b

    def __call__(self, x):
        return sigmoid(self.w * x + self.b)

    def propagateError(self, x, error, output):
        dEdW = error * output * (1 - output) * x
        dEdB = error * output * (1 - output)

        self.w += 0.05 * dEdW
        self.b += 0.05 * dEdB

def target(x):
    return sigmoid(10 * x - 5)

n = Network(0.6, 0.2)
# Training
for it in range(1000):
    for i in range(100):
        x = 1.0 * i / 100
        output = n(x)
        t = target(x)
        error = t - output
        n.propagateError(x, error, output)
# Testing
te = 0
for i in range(100):
    x = 1.0 * i / 100
    output = n(x)
    t = target(x)
    error = t - output
    print("Desired:",t)
    print("Actual:",output)
    print("Error:",error)
    te += error
    print("---")

print("Average error:",te/100.0)

```

---

Output:

```
('Desired:', 0.0066928509242848554)
('Actual:', 0.012425919415559344)
('Error:', -0.005733068491274489)
---
('Desired:', 0.007391541344281971)
('Actual:', 0.013550016530277079)
('Error:', -0.006158475185995108)

...

('Desired:', 0.9918374288468401)
('Actual:', 0.9855607114050042)
('Error:', 0.006276717441835888)
---
('Desired:', 0.9926084586557181)
('Actual:', 0.9867575913715647)
('Error:', 0.005850867284153405)
---
('Average error:', -0.0013496485567271077)

```

# Answer
> 0 votes
For reference, I put together a very simple two-layer implementation. I looked at many articles but, this Wikipedia article was most useful for me. Here's my implementation in C#

```
using System;

class Program
{
    static double Sigmoid(double x)
    {
        return 1.0 / (1.0 + Math.Exp(-x));
    }

    static double Target(double x)
    {
        return Sigmoid(-10 * Sigmoid(5 * x) + 7);
    }

    // Very simple 2-layer net with one input and one output node.
    // Both use a Sigmoid transform.
    // The target function is chosen to be a convolution of two sigmoids
    // The output of the net is by definition a convolution of two sigmoids, so
    // it should be possible to fit this function exactly.
    static void Main(string[] args)
    {
        double w01 = 0.5; // Weight from constant term to layer 1 node
        double w11 = 0.5; // Weight from input to layer 1 node
        double w02 = 0.5; // Weight from constant term to layer 2 node
        double w12 = 0.5; // Weight from layer 1 to layer 2

        for (int epoch = 0; epoch < 1000; ++epoch)
        {
            double totalError2 = 0.0;
            for (double x = 0.0; x <= 1.0; x += 0.01)
            {
                double t = Target(x);
                double y1 = Sigmoid(x * w11 + w01);
                double y2 = Sigmoid(y1 * w12 + w02);
                double e = t  - y2;

                totalError2 += e * e;

                // Second Layer
                double dEdV = e * y2 * (1 - y2);
                w02 += dEdV;
                w12 += y1 * dEdV;

                // First Layer
                dEdV = dEdV * w12 * y2 * (1-y2);
                w01 += dEdV;
                w11 += x * dEdV;
            }
            Console.WriteLine("Root Mean Error: {0:0.000} Weights: {1:0.000} {2:0.000} {3:0.000} {4:0.000}",
                Math.Sqrt(totalError2/1000), w01, w11, w02, w12);
        }
    }
}

```

---
Tags: neural-networks
---


# Question
Title: Not able to simplify a sum over reciprocals of $\log i$
Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.

Here in this case, I have reached until this point: $$ \begin{align} T(n) &= T(n-2) + 1/\lg n \\ &= T(n-4)+ 1/\lg(n-2) + 1/\lg n \\ &= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1) \end{align} $$ Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):

$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$

Now at this point I am not able to find out $\sum\_{i=1}^n 1/\lg(2i-1)$.

On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$, and my solution drills down up to here: $$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$

How do I evaluate such sums?

# Answer
The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$: $$ \int\_0^n f(x) dx \leq \sum\_{i=1}^n f(i) \leq \int\_1^{n+1} f(x) dx. $$ In your case, $f(i)$ is in fact non-increasing, and in that case we have $$ \int\_1^{n+1} f(x) dx \leq \sum\_{i=1}^n f(i) \leq \int\_0^n f(x) dx. $$ For example, we can estimate $$ \int\_2^{n+1} \frac{dx}{\log x} \leq \sum\_{i=2}^n f(i) \leq \int\_1^n \frac{dx}{\log x}. $$ Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce $$ \sum\_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$ In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so $$ \sum\_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$ If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.
> 6 votes

---
Tags: recurrence-relation, discrete-mathematics
---


# Question
Title: Problem with derivative of sigmoid activation function
I'm following Jeff heatons book 'Introduction to Neural Networks with Java'. To get node deltas, we need to calculate $f'(sum)$. In the very first row for Training Element #1, we need to compute $f'(1.13) \cdot 0.25$ which Heaton evaluates to $0.045$.

Using my calculator, I get $f'(1.13)=-0.13$ (derivative of sigmoid activation function), then I multiply by $0.25$ to get $-0.0325$. I've been trying to figure out for days how heaton does his calculation but no success yet. Kindly assist.

# Answer
The derivative of a sigmoid is always positive. Here's my math: `Sigmoid(1.13) = 0.7558`

I computed this on Wolfram Alpha

The derivative of a sigmoid `y=S(x)` is `y * (1-y)`, so `0.7558 * 0.2442 = 0.0451`
> 0 votes

---
Tags: mathematical-analysis
---


# Question
Title: Is my analysis of this recurrence relation correct?
The following recurrence relation,

$$T(n)=16T(\frac{n}{4}) + n^2$$

has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since

$$\log\_4{16} = 2$$ and

$$\log\_n{n^2} = 2$$

Where $b = 4$, $a = 16$, and $c = 2$, such that $f(n) = n^c$

What I'm *not* sure about is the end runtime complexity.

What I've come up with so far is

$$T(n) = \theta(n^2log\_2{n})$$

...since the Master Theorem states that, for case 2 situations, $f(n)$ must be within the set of $O(n^clog^kn)$, where $k$ is some constant in which $k \ge 0$.

My reasoning was to substitute 0 for $k$, which led to $\log\_2^1{n}$ in the result, as the result requires that $T(n) = \theta(n^clog\_2^{k+1}{n})$.

In a nutshell, while I know the first portion of the analysis is correct, and that this *is* a case 2 situation, am I correct in the reasoning behind the logarithmic portion in the ending runtime analysis?

# Answer
The Master theorem (roughly) states that in case two,

$\qquad\displaystyle f \in \Theta\left( n^{\log\_b a} \log^{k} n \right) \implies T \in \Theta\left( n^{\log\_b a} \log^{k+1} n \right)$.

That is, once you have identified the recurrence as case two by finding $k \geq 0$ so that $f$ is in this $\Theta$-class, the theorem *automagically* spits out the final result -- no further reasoning on your part necessary.

To be specific, in your case $a=16$, $b=4$ and $f : n \mapsto n^2$; therefore, $f \in \Theta\bigl( n^{\log\_b a} \log^{k} n \bigr) = \Theta\bigl( n^2 \log^{k} n \bigr)$ with $k=0$ and you get

$\qquad\displaystyle T \in \Theta(n^2 \log n)$.

Two comments:

* You use base $2$ for the logarithm in the final result. It should be $b=4$ (check the proof of the Master theorem) but it luckily does not matter; all logarithms share the same $\Theta$-class.
* You talk about "runtime analysis"; this is not specific to runtime functions, and the recurrence at hand is unlikely to accurately describe the runtime of any algorithm. See also here.
> 2 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Number of iterations of the Euclidean algorithm
I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says:

> The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log\_2 a$ iterations.
>
> 1. Since $\log\_2 a$ is the size of the input,
> 2. calculation requires a linear number of iterations.
> 3. The algorithm therefore has polynomial runtime.

I don't get how he could deduce (2) from (1), and (3) from (2); until now, the only concept of theory that he gave us is that to represent a positive integer, we need $1+\log\_2 x$ bits.

# Answer
> 6 votes
There's very little to deduce.

The number of iterations is linear in the size of the input because the size of the input is $2+\log\_2 a + \log\_2 b$ and the number of iterations is $2\log\_2 a$, which is less than $2(2+\log\_2 a + \log\_2 b)$, so is less than twice the length of the input. Hence, (2) holds.

Each iteration requires only a polynomial number of steps: all it does is tests and simple arithmetic operations, all of which can be done in time polynomial in the number of bits involved. Therefore, the total required time is some linear function (the number of iterations) times some polynomial function (the cost of each iteration), which is another polynomial function. So (3) holds.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?
In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of vertices). But how can we talk about a polynomial time reduction if we generate exponential-size numbers?

I guess that this is the key why Vertex Cover is strongly NP-complete and Subset-Sum is only weakly NP-complete. But I didn't get why it is in fact a polynomial time reduction.

# Answer
> 8 votes
The key is indeed that the numbers are expressed in binary. As you observe, the numbers could have a value that is exponential in the size of the vertex cover instance. If the reduction "wrote them out" in unary when computing the Subset-Sum instance, this would take exponential time. However in binary, writing down the bits of the number (i.e. computing their representation in the Subset-Sum instance) only takes polynomial time.

Just to emphasise the distinction, it only takes 7 digits to write out 1,000,000 in base ten, so writing it down takes about 7 steps. If we did it in unary, it would take about a million steps. The same thing is happening in the reduction, if it were using unary, it would not be polynomial in the size of the graph, but in binary - because what we're measuring is the number of steps taken to write it down - it is polynomial.

---
Tags: np-complete, reductions
---


title: LK-$\phi$ proof of $\exists y Pby$

text:
# Question
Title: LK-$\phi$ proof of $\exists y Pby$
I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on:

> Let $\Phi = \\{Pafa\\}$, where $P$ is a binary predicate symbol and $f$ is a unary function symbol. Give an $LK-\Phi$ proof of $\exists y Pby$. You do not need to show exchanges and weakenings.

My intution for these questions is very little unless it is blatantly obvious over what to do, but I do know that in the system $LK$ we have a $LK-\Phi$ proof if we have $A\to A$ or $\to A$ where $A\in\Phi$. So in this situation I think I set this up as the following:

$$\to \exists y Pby$$and then I would have a sequent above it where I would apply the $\exists R$ rule, which would create the sequent above as: $$\to Pba$$ but from here I am not sure at all what to do whether I need to rely on some sort of trick or anything? Any help would be greatly greatly appreciated, this is for an exam I am studying.

# Answer
> 3 votes
First of all, let me recommend then you use parentheses. So $\Phi = \\{P(a,f(a))\\}$, and you're trying to derive $\exists y P(b,y)$ from this.

If it were $\exists y P(a,y)$ instead, the proof would be very simple. You start by using the $\Phi$-rule to deduce $\vdash P(a,f(a))$, and then using the $\exists R$ rule you deduce $\vdash \exists y P(a,y)$.

As it stands, you cannot deduce $\exists y P(b,y)$ from $\Phi$ since $\exists y P(b,y)$ is not logically entailed from $\Phi$. For example, consider the interpretation in which $f$ is the identity and $P(x,y)$ is true only if $x=y=a$. Then $\Phi$ holds but $\exists y P(b,y)$ is false. Since LK-$\Phi$ is sound, you cannot deduce $\exists y P(b,y)$ from $\Phi$.

---
Tags: logic, proof-techniques
---


# Question
Title: Concrete and simple applications for bipartite graphs
I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.

# Answer
> 3 votes
Assignment Problem would be one such example:

> There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.

Hall's Marriage Theorem would be another:

> Imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.

The Mutilated Chessboard Problem can be solved using The Hall's Theorem:

> Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

# Answer
> 1 votes
There are loads conceptually simple and interesting such problems here: http://uva.onlinejudge.org/

I don't remember the actual problem numbers, though, but you can search the forum for bipartite graph problems.

---
Tags: graphs, bipartite-matching
---


title: Finding a finite model

text:
# Question
Title: Finding a finite model
Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this:

> Suppose $L$ is a language which includes an infinite list $c\_1,c\_2,\cdots$ of constant symbols. Let $\Gamma$ be a set of sentences $\Gamma = \\{c\_i \neq c\_j \mid i,j\in N, i \< j\\}$. Let A be a sentence such that $\Gamma \Rightarrow A$. Prove that $A$ has a finite model.

I am not sure whether I would prove this via a contradiction (i.e., assume $A$ has an infinite model, or if I show a finite model that works or some how assume that we can have an infinite model and then use some sort of compactness to show it can be finite. I am a little all over the place with this question, please any help would be great!

# Answer
> 2 votes
Note that you're looking for a model of $\\{A\\}$, not of $\Gamma \cup \\{A\\}$ (which obviously has no finite model since all the constants need to be pairwise distinct).

Proof by contradiction would be “assume $A$ has only infinite models or no model at all”. This isn't likely to lead anywhere.

Compactness could let you find a model of some set of sentences but you'd still have to prove the existence of a finite model at some point. Anyway, there is an easy direct proof.

The smallest model of a set of sentences is the one that collapses all the ways in which the differences between elements don't matter. You don't have to go all the way to apply this intuition: you can find a smaller model by collapsing some elements that don't matter. Here, you have an infinite number of constants; to find a finite model, you'll have to map infinitely many to the same element of the model (possibly to several elements).

In particular, if some constants do not appear in your theory at all, they can all be mapped to the same model element.

> The theory is $\\{A\\}$. This is a finite theory, consisting of (one) finite formula. Only a finite number of constants appear in this formula. Let $C(A)$ be the set of constants that appear in $A$. Define $\mathscr{M}: c \mapsto c$ if $c \in C(A)$, $c \mapsto c\_1$ if $c \notin C(A)$. Then $\mathscr{M}$ satisfies $A$.

---
Tags: logic, proof-techniques
---


# Question
Title: What does $\{$ a set $\}^{+}$ mean in the context of languages?
I came across this notation and I don't know the meaning of it, or if it's a typo: $\\{$ some set $\\}^{+}$

What does the + mean, i.e., the plus operator applied to a set?

# Answer
> 7 votes
This is the Kleene plus. It stands for $$ L^+ = \bigcup\_{i \geq 1} L^i. $$ Here $L^i$ is the set of concatenations of $i$ words from $L$. In words, $L^+$ consists of all concatenations of one or more words from $L$. A related operator is the Kleene star $$ L^\* = \bigcup\_{i \geq 0} L^i, $$ which also allows the empty string ($L^0$).

For example, if $L = \\{a\\}$ then $L^+ = \\{a,aa,aaa,aaaa,\ldots\\}$ while $L^\* = \\{\epsilon,a,aa,aaa,aaaa,\ldots\\}$. If $L = \\{a,b\\}$ then $L^+ = \\{a,b,aa,ab,ba,bb,aaa,\ldots\\}$. If $L = \\{aa,b\\}$ then $L^+ = \\{aa,b,aaaa,aab,baa,bb,aaaaaa,\ldots\\}$.

---
Tags: formal-languages, terminology, regular-languages, sets
---


title: Prove not context free

text:
# Question
Title: Prove not context free
How can we prove that:

$$ L = \\{ w\_1\\#w\_2 \mid w\_1 \in w\_2;\\; |w\_2| \> |w\_1|;\\; w\_1 , w\_2 \in \\{0, 1\\}^\*\\} $$

is not context-free?

The language defines $w\_1$ as a sub-string of $w\_2$, and they are separated by a $\\#$. This is easy with the CFG pumping-lemma for a slightly different language with $|w\_2| \ge |w\_1|$ by using the special case of $|w\_2| = |w\_1|$ (i.e. $w\_1 = w\_2$).

But here, $w\_1$ is a proper sub-string of $w\_2$ so I can't do the same. I fail to push the string out since we can always pump, for example the first symbol of $w\_2$.

# Answer
> 1 votes
For large enough $p$, consider the word $w = 0^{p+1}1^{p+1}\\#0^{p+1}1^{p+2} \in L$. Mark the part $1^{p+1}\\#0^{p+1}$. According to Ogden's lemma, we can write $w = uxyzv$ such that $xyz$ contains at least $1$ and at most $p$ marked symbols, and $ux^iyz^iv \in L$ for all $i \geq 0$. The pumped part $xyz$ cannot lie all to the right of $\\#$ since then pumping it down would result in a word not in the language (here we crucially use the fact that only the $0^{p+1}$ part to the right of $\\#$ is marked). It also cannot lie all to the left of $\\#$ since then pumping it up would result in a word not in the language. It follows that the part of $xyz$ to the right of $\\#$ is of the form $0^k$, and the part of $xyz$ to the left of $\\#$ is of the form $1^\ell$ (otherwise, there would be more than $p$ marked symbols). However, pumping up, the resulting word is not in the language. This contradiction shows that $L$ is not context-free.

---
Tags: formal-languages, context-free, proof-techniques, pumping-lemma
---


# Question
Title: Maximizing the Sum of a Subset with Excluding pairs
I have a set of nodes S where all the nodes of an arbitrary integer value. I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset. Given a subset of S, how can I determine the largest possible Sum of that subset taking into account the exclusion pairs.

Example:

S = (x1:50, x2:20, x3:30, x4:15, x5:70)

Exclusion = {(x1,x2), (x4,x5), (x2,x4)}

Starting set = (x1,x2,x4,x5)

Best Possible Sum = (x1,x5)

# Answer
Your problem is known as *maximum-weight independent set* (more often, simply *maximum independent set*). We think of the $x\_i$ as vertices in a graph, each constraint corresponding to an edge $(x\_i,x\_j)$. An independent set is a set of vertices with no edges, which is exactly your condition.

Unfortunately, maximum-weight independent set is NP-complete, and $n^{1-\epsilon}$-hard to approximate (for every $\epsilon\>0$) even when all weights are the same.
> 3 votes

---
Tags: graphs, sets
---


# Question
Title: How do I "tell" a simple perceptron/adaline neural netrork its output can't be negative?
I have made and trained a simple neural network which now seems to produce outputs reasonable in all the aspects but one: it gives negative values from time to time even though the outputs are always either 0 or 1 (positive) in all my treaining samples (the actual neural outputs show to be more or less close to the answer most probable but never actually reach them, I consider this ok). Won't "telling" the network what output values are just impossible improve its performance.

Perhaps my mistake is in choosing activation functions. As far as my input values domain is (-1, 1) I use TANH for input neurons, but I have no idea what is the logic to choose hidden and output neurons activation functions and so I set the same (TANH) for all of them (update: I have just noticed that I have mistakenly chosen linear activation function for the output layer while inpit and hidden layers use TANH).

Clearly a negative value means "the answer is very probable to be zero" in this case and it works just fine from the practical point of view but it still gives me a sense that I am doing something wrong.

# Answer
You can put the logistic function on top of the output:

f(z) = 1/(1 + exp(-z)).

You will also need to adjust the cost function accordingly, i.e. use log loss: https://www.kaggle.com/wiki/LogarithmicLoss
> 2 votes

---
Tags: neural-networks
---


# Question
Title: Boyce-Codd Normal Form vs. 3rd Normal Form
Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?

# Answer
> 2 votes
Because they are two different concepts.

A schema satisfies **3NF** iff for every functional dependency in the relation such as `X -> A`, `X` is a key **or** `A` is prime (part of the key).

A schema satisfies **BCNF** iff for every functional dependency in the relation such as `X -> A`, `X` is a key.

You can clearly see from these definitions that every BCNF must also satisfy 3NF. However, precisely for the reason that to achieve BCNF you may need some extra splitting on the relations, it could be impossible to preserve all the FDs.

I'll give you an example: say you have a relation

```
R(A, B, C, D, E)

```

With FDs:

```
ABCD -> E
E -> BCD

```

This relation is in 3NF since `E` depends on the key and `BCD` is prime; however, since BCNF doesn't have the prime clause, the relation fails BCNF due to `E -> BCD`.

On the other hand, when you break down the relation to meet BCNF

```
R1(E, B, C, D), R2(A, E)

```

the FD `ABCD -> E` is lost because of the over-splitting we had to do.

---
Tags: database-theory, normal-forms
---


title: Algorithm to find Dominance Frontiers

text:
# Question
Title: Algorithm to find Dominance Frontiers
The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9). We start with the *immediate dominators* of each control-flow graph node `B` already calculated and stored in `idom[B]`:

```
for each B in all basic blocks
    if size of Predecessors(B) >= 2
        for each P in Predecessors(B)
            runner = P
            while runner != idom[B]    # idom is the immediate dominator
                DF(runner) += B
                runner = idom[runner]

```

My question is about the `Predecessors` set. Do they refer to the direct predecessors ("fathers") of `B` or to all of them that lead to `B`?

# Answer
`Predecessors(B)` is just the set of direct predecessors of `B`. The "fathers", not the more distant ancestors.

Dominance frontier nodes must be join points in the graph, and a node can only be a join point if it has more than one predecessor.
> 3 votes

---
Tags: compilers
---


# Question
Title: Linearithmic lower bound for 1-D "distinct" closest pair of points problem
The 1-D **distinct** closest pair of points problem is as follows: Given a set of n **distinct integer** points on real line, find a pair of points with the smallest distance between them, here the distance between two points p\_i and p\_j is absolute difference of their values, i.e, |p\_i-p\_j|.

A naive way to solve this problem is to sort the points and check distance of each consecutive points in sorted order and take the minimum of such distances and this takes O(nlog n) time.

My question is can we do better than that? Can we solve it in o(n log n)(note the little-oh) time? If not, then how to show an omega(nlog n) time bound for this problem?

Note that, if the **distinctness** criteria was not there we could have shown a lower bound using Element Distinctness Problem.

# Answer
Given $n$ integer points $p\_1,\ldots,p\_n$, not necessarily distinct, consider the set of points $2np\_1+1,2np\_2+2,\ldots,2np\_n+n$. The new points are distinct by construction, and the minimal distance is smaller than $n$ iff the original points were not distinct. So an algorithm for your problem can be used to solve element distinctness.
> 7 votes

---
Tags: algorithms, data-structures, sorting, lower-bounds
---


# Question
Title: Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?
You have a Turing machine that only processes input on the form $0^\*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete?

The set $0^\*$ is countably infinite, since you can make the bijective function $f(x) : 0^\* → \mathbb{N} $:

$f(x) = length(x)$

Where $length(x)$ is the length of the string (so you treat them as Peano Numbers).

I understand that the set of all programs (the programs that a Turing machine can run) are countable, and that the set of a Turing machines are also countable. But, can the set of string that the Turing machine can process (with no guarantees of halting) only be countably infinite (as in this case), or does it have to be uncountable?

My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers, e.g. $B^\*$, where $B = \\{0,1\\}$, which has a cardinality equal to the real numbers. It seems to me that, although you can encode any integer with the language $0^\*$, you can't encode an arbitrary language. The problem is: how can you encode recursively enumerable languages when all you have is unary notation? If this is indeed impossible (though I have a feeling it is possible; I can't see how the representation of numbers should be a fundamental hindrance), then it turns out that this particular Turing machine is *not* Turing Complete (or maybe you would say that it is not really a Turing machine).

# Answer
> 6 votes
It looks like Turing machines remain Turing-complete when the alphabet is restricted to have one symbol, $0$. First, preprocess your input by replacing every $0$ with $0\square$, where $\square$ is the blank symbol. Now, you can simulate a 2-symbol alphabet by using $0\square$ to represent zero and $\square0$ to represent one.

> My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers

This is incorrect. A language is, by definition, a set of finite strings and there are only countably many finite strings over any finite alphabet (proof: you get a bijection with the natural numbers by treating each string as a number written in base-$k$, where $k$ is the size of the alphabet). However, there are uncountably many different languages and that observation along with the countability of the set of Turing machines lets you deduce that there must be some undecidable langauges.

> It seems to me that, although you can encode any integer with the language 0∗, you can't encode an arbitrary language.

This is also incorrect. You can encode any natural number $n$ with the single string $0^n$ and, therefore, you can code any set of natural numbers with a unary language, i.e., a subset of $0^\*$. And you can code any set of natural numbers as a language. You can also code any language over an alphabet of size $k\>1$ by using the base-$k$ trick I described above.

---
Tags: turing-machines, turing-completeness, machine-models
---


# Question
Title: Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?
So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set elements so that the linear combination of set elements equals a target sum) are NP-complete. Is there some fairly easy reduction from 0/1 subset-sum to subset sum with multiplicities? This seems perhaps non-trivial, because just because there is a solution with multiplicities doesn't mean there is a 0/1 solution.

Some ideas I had that don't seem to work: For element $s$, solve the subset sum with multiplicity problem both for total sum $S$ and $S-s$ with element $s$ removed from the set. Then try to argue that $s$ either is or is not included in the 0/1 solution depending on the answer.

# Answer
> 3 votes
This answer on CSTheory describes a reduction from 0/1 subset-sum to the unbounded knapsack problem (UKP). That does exactly what you want. The intuition is that UKP is basically subset sum with multiplicities, since UKP lets you put as many copies of an item as you want into your knapsack.

---
Tags: complexity-theory, combinatorics
---


# Question
Title: Is the way an OS schedule threads related to parallel computing?
From Wikipedia:

> Operating systems schedule threads in one of two ways:
>
> **Preemptive multitasking** is generally considered the superior approach, as it allows the operating system to determine when a context switch should occur. The disadvantage of preemptive multithreading is that the system may make a context switch at an inappropriate time, causing lock convoy, priority inversion or other negative effects, which may be avoided by cooperative multithreading.
>
> **Cooperative multithreading**, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping point. This can create problems if a thread is waiting for a resource to become available.

I wonder if in parallel computing (writing and running parallelized programs in OpenMP, OpenMPI, pThread), which of Cooperative multithreading and Preemptive multitasking is/are used, or does the way OS scheduling threads have nothing to do with the multi-process or multi-thread within a parallelized program?

# Answer
There is a relationship between what Wikipedia is calling "preemptive multitasking" and running multiple threads in parallel, but it's somewhat indirect.

Suppose you have two threads of computation that are independent (the memory locations they touch are non-overlapping). Then we say that those two threads can run *concurrently*. "Preemptive multitasking" is a way of giving the illusion that the threads are running concurrently, even though we only have a single physical processor. The single processor gets interrupted (usually by some timer hardware) every once in a while (e.g., 100 times a second), and chooses which thread to run. Since the processor is switching back and forth so quickly it is hard to tell that you aren't running simultaneously on two (slow) processors.

If you actually run the two threads on two different processors then you are really running in parallel, and there is no switching back and forth to share a single resource.

The similarity comes up because in both true parallelism and preemptive multitasking *any* ordering of the instructions between the two threads is possible. Thus if there is any sharing of resources, memory, or locks you need to reason about the correctness of that sharing by proving that nothing bad can happen in any possible interleaving.

With cooperative multithreading you break the illusion of having multiple processors. If a thread gets scheduled it runs as long as it wants to (and *knows* that the other thread is *not* running) and only gives up the processor by calling some system call (often called something like `yield()`.) On the one hand, you've lost the illusion of two processors, which is problematic if one of the threads forgets to `yield()`. The advantage is that you *know* when the the threads are switching back and forth, so the number of possible interleavings you need to reason about is much smaller.
> 3 votes

---
Tags: operating-systems, parallel-computing, threads
---


# Question
Title: Is there a Context-free grammar for this language?
Is there a `Context-free grammar` for the following language:

$L=\\{ x\\#1^m|x \in \\{0,1\\}^\* \text{ and the $m^{\text{th}}$ char in $x$ is 1} \\}$

If so what is it? Because i couldn't find any. I also tried to prove there isn't (by the Pumping lemma for context-free languages), but it's given that a `Context-free grammar` does exist and I found an error in my "proof".

So what would be the grammar?

---

Here's the big picture of my proof:

Let's choose $m=n\_0$ and take the word $w=0^{n\_0}1\\#1^{n\_0+1}$ (so that $x$ is what's on the left side of $\\#$) .

According to the lemma, $w$ can be written as $uvxyz$ and some conditions hold...

$|vxy| \leq n\_0$

therefor, $vxy$ include only zeros ($0$'s).

Now let's choose `k=2` and pump it up:

we get: $w\_2=uv^2xy^2z$

which means, the number of $0$'s is now:

$n\_0 + |v| + |y| \geq n\_0 + 1$

(since $|vy| \geq 1$) .

Hence, the $m$th number (the $n\_0$th in our case) is not $1$. It's actually $0$.

Hence, $w\_2$ doesn't belong to $L$. Contradiction.

Hence, $L$ isn't `Context-free`.

---

I think i know where's my mistake in the proof:

$vxy$ isn't necessarily only $0$'s. It could have the last $n\_0-1$ zero's and a $1$.

# Answer
> 3 votes
Here is a PDA for this language. While reading $x$, the whole of $x$ is pushed onto the stack. After encountering $\\#$, the PDA pops some non-deterministic amount of symbols, then verifies that the top symbol is $1$, and pops $m$ symbols. It acceptes if the stack is empty.

Variant: instead of popping a part of $x$, while reading $x$ the PDA non-deterministically stops pushing symbols into the stack; it only does so after reading a $1$.

As for a CFG for this language, here is the idea: $$ \begin{align\*} &S \to \Sigma^{m-1} 1 T 1^m \\ &T \to \Sigma^\* \\# \end{align\*} $$

I'll let you construct an actual grammar based on this idea.

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: How do we know any problem is in NP-complete if we don't know all problems in NP?
A problem is NP-complete if:

1. It is in NP.
2. All problems in NP can reduce to it.

It's number 2 that I'm concerned with here. I would be highly surprised if we knew *every* problem in NP. Based on that assumption, how do we know for sure that any problem is NP-complete? For example, how do we know that there's not some problem we don't know of that will reduce to the Boolean Satisfiability problem, but not the Clique problem? Or would such a problem be NP-Intermediate and therefore need P != NP to exist?

# Answer
We *do* know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-complete by encoding the statement "Machine $M$ accepts $x$ given non-deterministic choices $y$" as a logical formula for every non-deterministic Turing machine; for a machine running in time $T$ and space $S$, the encoding has length roughly $O(TS)$, so when $M$ is polynomial time, the encoding has polynomial length. The corresponding SAT formula states that "for some $y$, machine $M$ accepts $x$ given non-deterministic choices $y$". This formula is satisfiable iff $M$ accepts $x$.

Having proven that one problem is NP-complete, there is no need to do this encoding again. To prove that some other problem $L$ is NP-hard, it is enough to reduce SAT to $L$. Every problem in NP is reducible to SAT, and via the auxiliary reduction, to $L$. This is the way NP-hardness results are proved nowadays, by reducing from some NP-hard problem.
> 13 votes

---
Tags: complexity-theory, np-complete, np
---


# Question
Title: Searching for a string of numbers in a large digit sequence
How would one search for a string of digits in a large digit sequence? For example, I'd like to search for `351814` in Euler's number. I'm not too keen on computer science, I'm a pure math major, so I don't really know how to begin. I also wouldn't know how to run said code.

**Any help would be greatly appreciated.**

# Answer
Use your web browser. You can get the first 2 million or so digits in this link, and then use your browser's searching facilities. I was able to locate `351814` within the first 2 million digits (though not within the first 1 million digits, available in a separate link). By the way, I found both links on Wikipedia.
> 4 votes

# Answer
Are you asking for a method to going about doing this using a programming language or an algorithm you could implement?

Assuming you had a string containing the digits of Euler's Number you could use a built in function like the following:

(In Java) : `eulerNumberString.indexOf("351814");`
(In C++) : https://stackoverflow.com/questions/13195353/how-to-find-substring-from-string

If you want an algorithm the simplest I could think of would be to go through the string of digits from start to end looking for the start of your sequence. Once you find it, say "3" in your example, you would check to see if the next five digits are "51814". If not, then start from the next character after that "3" (you could optimize this) and look for the next "3" to try again.
> 0 votes

---
Tags: algorithms, search-algorithms, strings, binary-search
---


# Question
Title: Why linear transformation can improve classification accuracy when the dimensionality of data is high?
Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset. When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more complicated and the classification accuracy decreases. One way to over come this problem is to use linear transformation, i.e., perform classification on $Y=XR$, where $R$ is an $n\times p$ matrix, and $p\leq n$. I was wondering how linear transformation simplifies classification? and why classification accuracy increases if we do classification on the transformed data $Y$ when $X$ is noisy?

# Answer
> 7 votes
Multiplying by the $n * p$ matrix decreases the dimensionality of the data set. Think of this as projecting the highly dimensional space into a smaller dimensional space. For example, you could do principle component analysis and project it into a small space. This way things that are correlated together are projected into the same dimension and if one of those correlated dimensions is off because of noise, then it would be cancelled out by the values in the other correlated dimensions.

You have to choose your matrix $R$ in a way that essentially averages together things that reinforce each other and reduce noise. Principle component analysis is one way of choosing such a matrix.

---
Tags: machine-learning, data-mining, linear-algebra, matrices, classification
---


# Question
Title: How can I identify that a restricted variant of Boolean SAT remains hard or not?
While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I though of it) and searched, but could not find anything useful.

Consider this variant:

> Suppose $f$ is a boolean function in $n$ boolean variables, but with this extra property, that $f$ is increasing. I have thought of $n$ boolean variables, $X\_1, \ldots, x\_n$ as representation of subsets of a set with $n$ elements, and if some subset like $X$ satisfies $f$, then all $Y$ s.t. $X \subseteq Y$ satisfy $f$, too. *What I want is finding the **collection** of all minimal $X$ where $f$ satisfies each of them, but not any $Z$ where $Z \subsetneq X$?*

Is this problem still hard?

If I consider the $x\_1, \ldots, x\_n$ as a number, then increasing property of $f$ helps solving it in polynomial time, just a binary search suffices! So, I made it a little bit harder.

Any help, even offers of search terms is appreciated.

# Answer
> 5 votes
Your problem cannot be solved in polynomial time, for a boring reason: the size of the output might be exponential in the time of the input. Therefore, there is no hope for a polynomial-time algorithm.

For instance, consider the boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$ that outputs $1$ if its input vector has at least $n/2$ ones (i.e., its Hamming weight is at least $n/2$), and $0$ otherwise. This function can be represented by a polynomial-size monotone formula. However, there are exponentially many minimal $x$ such that $f(x)=1$. In particular, each $x$ of Hamming weight $n/2$ is such a minimal input, and there are ${n \choose n/2} \approx 2^n/\sqrt{n}$ such inputs.

So, there's no hope.

As Andrej Bauer points out, a related problem (testing whether there exists an input of Hamming weight at most $k$ that causes the boolean function to output $1$) is also NP-complete; see Prove NP-completeness of deciding satisfiability of monotone boolean formula.

---
Tags: complexity-theory, np-hard, satisfiability
---


# Question
Title: What is the significance of primitive recursive functions?
I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive functions?

# Answer
The halting problem is undecidable, but one might object that for most programs, it is easy to check whether they halt or not, by looking for any obvious infinite loops. Conversely, if you wanted to *ensure* that your program always terminates, you could do so by bounding a priori the number of loop iterations for every loop. For example, consider the pseudocode for repeated squaring:

```
def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   result = 1
   while y > 0:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
   return result

```

How do we know that this procedure always terminates? One way would be to a priori bound the loop:

```
def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   bound = y
   result = 1
   loop bound times:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
     if y == 0: break
   return result

```

Now it's clear that this program terminates, and if we haven't made a mistake elsewhere, the two programs would produce the same output.

> Primitive recursive functions are those computed by programs in which all loops are bounded and there is no recursion.

While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:

1. Is every computable function presentable in this form?
2. If not, what is the relation between this class and all computable functions?

To answer 1, one can show that certain computable functions which grow "too fast" are not primitive recursive, for example the Ackermann function. Conversely, every function whose growth rate is "reasonable" is primitive recursive. And every computable function can be stated in the form $f(x) = \psi(\min\_y \phi(x,y))$ for primitive recursive $\phi,\psi$, where we think of $\phi$ as a predicate.
> 6 votes

# Answer
When I took my computability course, we were introduced to this in the following way:

Primitive recursion is a natural way of defining a computation (probably obvious if you have a math mind, for a programmer it's easier to understand that recursion is a loop backwards).

So once you master primitive recursion, you wonder: is that all there is in computation?

Well, it turns out it's not. First, you're missing undefined values. Ok,so you can extend primitive recursion to partial primitive recursive functions.

Still, there are some (complete) computable functions that are not primitive recursive. Well, Ackermann is one of it. So that is why the Ackermann function is important. It turns out that 'recursion' is "primitive recursion + minimization", and while it cannot be proven, it seems, that's all there is to computation.

So primitive recursive functions are important as they are

1. simple formalism
2. base for the definition of recursion

Not sure - maybe someone else will know - but I think before Ackermann came up with his function, mathematicians thought that computable = primitive recursion + partial functions.
> 1 votes

---
Tags: terminology, computability, machine-models
---


# Question
Title: Can This Property (Representative Property) Be Generalized?
I recently came across with a question that asks for the greatest subset of a given set, which includes relatively prime elements.(Randomly selected item from a set is always relatively prime to all others.) My approach was eliminating the subsets depending on if the subset satisfies the rule. Which means testing one by one all possible subsets. In order to determine which subset is going to be tested, I have choosen the following way:

Let S be a set and "n" is the size of the set. Since there are 2^n possible subsets, all computer needs to do is to check all possible subsets. However, the question is in which way and regarding what property. In other words what would be the "rule" for computer to do it.

I came up with a method which I call "Representative Property". By using ones and zeroes I could represent all the elements of the set to indicate their existance or absence in the subset which is going to be tested.

İf n=5, then There is 32 possible subsets. Starting from 2^n -1 in which case 31, converting 31 to binary we get "11111". What binary 11111 represent is all the elements of the set is included in the subset which is going to be tested.

By incrementing that value by one I could get 11110,11101,11100,...00010,00001 where "1" stands for existance of the element and the "0" is vice versa.

This is the code for who wonders all work...

```
import java.util.Scanner;
import java.util.ArrayList;

public class Quest_1 {

private static boolean isRelativePrime(ArrayList<Integer> newInfo) {
    int j;
    for(int i=newInfo.size()-1;i>=0;i--){

        for(int k=i-1;k>=0;k--){
            j=2;
            while (j<newInfo.get(k)||j<newInfo.get(i)){
                if(newInfo.get(k)%j == 0 && newInfo.get(i)%j== 0)
                    return false;
                j++;
            }
        }
    }
    return true;
}
public static String reverse(String source) {
    int i, len = source.length();
    StringBuffer dest = new StringBuffer(len);

    for (i = (len - 1); i >= 0; i--)
        dest.append(source.charAt(i));
    return dest.toString();
}
public static String binary(int i, int k){

    int count = 0;
    String empty ="";

    while(i>0){

        if (i%2==0)
            empty = empty +"0";
        else
            empty = empty +"1";
        i = i/2;
        count++;

    }

    while(count < k){
        empty = empty+"0";
        count++;
    }
    empty = reverse(empty);
    return empty;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.print("Kaç eleman? ");
    String binary;
    int max = 0;
    int componentSize = scan.nextInt();

    ArrayList<Integer> info = new ArrayList<Integer>();
    ArrayList<Integer> newInfo = new ArrayList<Integer>();
    for (int i = 0;i<componentSize;i++){

        info.add(scan.nextInt());

    }
    for(int l=0;l<info.size();l++)
        System.out.println("***----****------****** "+info.get(l));
    for(int k=(int)Math.pow(2, componentSize)-1; k>0; k--){
        // takes the string.if "1" add,then compare.if relatPrime is true omit, else leave it
        binary = binary( k, componentSize);
        int index=binary.length()-1;
        while(index >= 0){

            if(binary.charAt(index)=='1')
                newInfo.add(info.get(index));

            index--;
        }
        if(isRelativePrime(newInfo) && max<newInfo.size())
            max = newInfo.size();
        index=newInfo.size()-1;
        while(index>=0){
            newInfo.remove(index);
            index--;
        }
    }
    System.out.println("here is the max: "+max);
}

}

```

Now here comes the question. Can this way, I mean representing the computations with numbers , be generalized?

For example: there is a password whose length is 5. "1" stands for a, "2" for b and etc.

or for chess games, by decrementing the test case number, Can all the possibilities be evaluated ? And what is this process called,checking all the possibilities?

I am majoring CS, first semester. Therefore, I am open to all suggestions.

(I am really sorry for everything wrong, I'd really appreciated,if you kindly warned me.)

# Answer
What you're suggesting is a very simple example of *combinatorial enumeration*. In your case, you're enumerating the power set $$\\{0,1\\}^S.$$ List the items of $S$ in some arbitrary order: $S = \\{s\_1,\ldots,s\_n\\}$. We can write $$ \\{0,1\\}^S = \\{0,1\\}^{s\_1,\ldots,s\_{n-1}} \cup \\{0,1\\}^{s\_1,\ldots,s\_{n-1}} \times \\{s\_n\\}. $$ This means that a subset of $S$ is either a subset of $\\{s\_1,\ldots,s\_{n-1}\\}$ or such a subset together with $s\_n$. There are $2^{n-1}$ of each, so the corresponding equation on cardinalities reads $$ 2^n = 2^{n-1} + 2^{n-1}. $$ The idea is to think of this in terms of intervals: $$ \[0,2^n) = \[0,2^{n-1}) + \[2^{n-1},2^n). $$ (Here $\[a,b) = \\{a , a+1 , \ldots , b-1 \\}$.) We can encode an arbitrary subset of $S$ by recursively encoding a subset of $\\{s\_1,\ldots,s\_{n-1}\\}$ as some integer $x \in \[0,2^{n-1})$, and then putting it in the first interval $\[0,2^{n-1})$ if $s\_n$ is not in the subset, or in the second interval $2^{n-1} + \[0,2^{n-1}) = \[2^{n-1},2^n)$ if $s\_n$ is in the subset. What we get is the binary encoding of the subset which you describe.

More generally, if each element can receive one out of $B$ colors, we get base $B$ encoding (in your case $B = 2$ since each element is either "in" or "out"). The number of colors can even vary depending on the element: if there are $B\_i$ possible colors for $s\_i$, then we get a mixed base notation. A good example is $S\_n$, the set of permutations of $\\{1,\ldots,n\\}$, which can be described in the following way:

1. Put $n$ at one of the $n$ available spots.
2. Put $n-1$ at one of the $n-1$ available spots.
3. Go on until you put $1$ the only available spot.

Here $B\_i = i$, and we get a way to enumerate permutations.

This method works even more generally. For example, using the recurrence for Catalan numbers, we can encode binary trees. Using Pascal's identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$, we can encode $\binom{\[n\]}{k}$ (subsets of $\\{1,\ldots,n\\}$ of size $k$). And so on.
> 1 votes

---
Tags: algorithms, decision-problem, numeral-representations
---


title: Algorithm to find and add prime numbers

text:
# Question
Title: Algorithm to find and add prime numbers
How would one write code to find and add the prime numbers between 4 and 5 million? I need a code that can find all such numbers, and then add them together. I'm not too keen on computer science, so I wouldn't know even where to begin. (I'm a math major).

Any help is appreciated. Also any advice on how to compile and run the code would be helpful.

**PS** I know the answer is one of the following: 294185048443, 303141243820, 294095048847, 277319432363, 453190021165, or 210569014847.

# Answer
```
sage: sum([x for x in range(4000001,5000000,2) if x in Primes()])
294095048847

```
> 1 votes

---
Tags: algorithms, primes
---


# Question
Title: How is it possible for a problem to be NP-Complete under polylog-time reductions?
I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I *think* SAT was one of them).

This confuses me - it seems to me that this is a violation of the nondetermistic time hierarchy. If SAT (or whatever) can be solved in $NTIME(n^c)$ for some $c$, and any $NP$-problem can be reduced to SAT in $O(n^k)$ time for some fixed $k$, then it seems that we can solve any $NP$ problem in $O(n^{c+k})$ nondetermistic time -- obviously false.

So, it seems to me that SAT (or whatever) can only be NP-Complete under polytime reductions, and that for any polynomial, we can find a problem whose reduction to SAT takes *more* than that polynomial amount of time.

What am I missing?

# Answer
What you probably heard was that many problems are NP-complete under *logspace* reductions, for example 3SAT. All this means is that (say) the algorithm in Cook's theorem can be carried out in logarithmic space, and that many reductions among problems can be carried out in logarithmic space. Wikipedia contains a relevant discussion of various notions of reducibility and their relation to NP-completeness.
> 1 votes

---
Tags: np-complete, reductions
---


# Question
Title: web content "mining" using supervised learning tequniques
We're accessing an API of a web system for obtaining product information. We require some additional information, which is not available through the API. This information is publically available for each product visually - through the source code for each item on its item page. We've written an algorithm which parses this information from the web page for each item, but that will be highly ineffective in the long run, since the algorithm will simply stop working if and when they decide to change the source code ( for example - redesign of the front end ).

I feel like there should be a supservised learning approach to this problem, however I'm unaware if there exist such solutions.

What are some good aproaches to this kind of problems ?

Regards.

# Answer
In short, this is probably difficult.

Your question is not fully specified, since you did not write the details of the data you are parsing and since estimating the possible changes to it is a matter of guesswork.

Once this web site changes format, then if we assume that the products remain the same, you are essentially looking at **supervised learning** task: given a list of known product web pages, make an "extractor function" that outputs the desired field.

If you are lucky and all the product pages are identically structured then this problem might be quite easy. You simply need to identify the path to the node of the HTML in which the desired information lies. On the other hand, if the web pages have a varied structure, or no structure at all, then the problem may be much more difficult.

There are some academic works in these areas, but don't get your hopes up. Look for the keywords "automatic web extraction".
> 2 votes

# Answer
You are crawling the web for some structured information inside the web pages.

There is an infinite number of ways to represent the information in a web page (like java scripts); it means that it's impossible to have an automated system to do that for you completely. I think, this process must be handled by a person up to a level.

My suggestion is this:

1. Once you finished your parser,
2. select a sample page (one of the product pages) for testing whether that structure remained the same or not,
3. once in a while, try to check if the structure is changed,
4. if your program realized that structure is changed, then it can try to learn the pattern by looking up the information, or if it wasn't successful it can send you some feedback about the structure that is changed and you must handle it via new parser.

if the products are changing and you cannot select a sample product to check the structure, I suggest:

1. Write a regular expression for the pattern of information in the web page,
2. Check if the regular expression returns anything or it's not valid anymore,
3. If the regular expression is not valid, then the structure is changed and you need to come up with a new one
> 1 votes

---
Tags: machine-learning, data-mining
---


title: What is a mod b if a < b?

text:
# Question
Title: What is a mod b if a < b?
So when you are decrypting an encryption with modular arithmetic, I know the modulus operator (%) gives the remainder of a/b, but what if a is less than b?

For example, 5%2 is 1, since the answer is 2 remainder 1. But for something like 2%9, how do you find the answer?

# Answer
> 7 votes
If $a,b$ are both positive integers, then we can always write $a = kb+\ell$ where $0 \leq \ell \< b$. We call $\ell$ the *remainder* and $k$ the *quotient*. In your first example, $5 = 2 \cdot 2 + 1$ so `5 % 2 == 1`. In your second example, $2 = 0 \cdot 9 + 2$, so `2 % 9 == 2`. More generally, if $a \< b$ then `a % b == a`.

There is also a rule for signed integers, but unfortunately I can't remember it. Also, `0 % x == 0` whenever $x \neq 0$, and `x % 0` will cause an exception ("division by zero").

# Answer
> -3 votes
The answer is 9. 2 / 9 is 0r9. The modulus operator returns the remainder of integer division, since 9 goes into 2 0 times the operator returns 9.

---
Tags: mathematical-foundations
---


# Question
Title: Proving that a language does not belong to a language class by using more specific instances of that language
You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does *not* belong to a certain class of languages, you might think that it will be more convenient to prove it by using a subset of that language. The problem is that a subset of a language does not necessarily belong to the same language class as the superset language. For example: with $\Sigma = \\{0,1\\}$, $\Sigma^\*$ is a regular language, while $ A = \\{ 0^n1^n \mid n \geq 0\\} \subseteq \Sigma^\* $ is a context free language.

(I have fallen in the trap of trying to use subsets of languages in order to try to prove that they belong to a certain class of languages.)

An example:

> Let $\Sigma = \\{0,1\\} $ and $L = \\{ w \in \Sigma^\* \mid \text{w contains less 1's than 0's} \\}$
>
> Is $L$ regular, context free, or neither?

My intuition says that it is not regular, since finite state machines *can't count*. I think it is context free.

The strategy I'm thinking of is to show that this language is context free:

> $ L\_2 = \\{ 0^n1^m \mid n \gt m\\}$

This language is clearly a proper subset of $L$. But, like we've seen, that may not be a very useful fact if we want to prove things about the proper superset (to my understanding). It *seems* that $L\_2$ is *easier* to generate than $L$: it seems easier to count how many consecutive 0's there are rather than counting the number of 0's in a string. (Especially if you consider using a PDA to count it, since then it just boils down to pushing consecutive 0's and then popping when you start seeing 1's, accepting the language if there are 0's left on the stack when you have consumed the word.) Consequently, if this intuition of *hardness* is correct, then $L$ is at least not regular. But then another problem reveals itself; maybe $L$ is not context free? So then you have at least shown it to not be regular, but you still have to show that it is context free or not.

This is not the only problem for which I want to use this strategy. For example:

> $L\_p = \\{ w \in \Sigma^\* \mid \text{the number of 0's in w is prime}\\}$

Here I think it might be more convenient to use something like the Pumping Lemma on this language:

> $L\_{p2} = \\{ 0^n \mid \text{n is prime}\\}$

Is this kind of strategy valid?

# Answer
> 6 votes
Yes. The formal way to name this trick is the use of *closure properties*. In your specific case the families (regular, context-free) are closed inder intersection with a regular language: if $K$ is regular (context-free) then so is $K\cap R$, where $R$ is regular.

In your examples $L\_2 = L \cap 0^\*1^\*$ and $L\_{p2} = L\_p \cap 0^\*$.

So, if $L\_{p2}$ isn't context-free then neither is $L\_p$. Also if $L\_2$ isn't regular then neither is $L$.

Regarding the first part of you question this will not help: $L\_2$ may be context-free while $L$ isn't. (Not is this example, where they both are context-free: use pushing and popping but in a more general way, think how to represent negative numbers.) On the other hand, when you are not able to solve the general case, it might be helpful to develop intuition on the special cases.

---
Tags: formal-languages, proof-techniques
---