title: Can there be a perfect chess algorithm?

text:
# Question
Title: Can there be a perfect chess algorithm?
Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game. An algorithm that has all the possible paths that opponent can take at any given moment depending on the players moves. Can there ever be a perfect chess algorithm that will never lose? Or maybe an algorithm that will always win? I mean in theory someone who can predict all the possible moves must be able to find a way to defeat each and every one of them or simply choose a different path if a certain one will effeminately lead him to defeat.....

edit-- What my question really is. Let's say we have the computing power for a perfect algorithm that can play optimally. What happens when the opponent plays with the same optimal algorithm? That also will apply in all 2 player games with finite number (very large or not) of moves. Can there ever be an optimal algorithm that always wins?

Personal definition: An optimal algorithm is a perfect algorithm that always wins... (not one that never loses, but one that always wins

# Answer
> 14 votes
Your question is akin to the old chestnut: "What happens when an irresistible force meets an immovable object?" The problem is in the question itself: the two entities as described cannot exist in the same logically consistent universe. Your optimal algorithm, an algorithm that always wins, cannot be played by both sides in a game where one side must win and the other must by definition lose. Thus your optimal algorithm as defined cannot exist.

# Answer
> 23 votes
First of all, I believe that chess algorithms look more than 2 plies down, although they don't consider all different possibilities; pruning the search tree is very important to avoid the combinatorial explosion in the number of possible moves.

For a game like chess, there are three possibilities as to the identity of the winner: either player 1 has a winning strategy, or player 2 has a winning strategy, or both players draw under optimal play. It is not known which is the case for the game of chess. However, since chess is a finite game, there is a computer algorithm, consisting of a very large table, which plays chess optimally.

Of course, such an algorithm wouldn't be practical. But for some simpler games, the "value" of the game (which player wins, if any) has been determined, and an optimal algorithm has been devised. Such a game is known as a solved game.

The mathematical subject that deals with (what are known as) combinatorial games is combinatorial game theory. Mathematicians have developed a recursive method to determine the value of a game given the graph of the game, which includes all the allowed positions and moves. You should be able to find a description of this algorithm in the Wikipedia entry or any lecture notes on the subject.

# Answer
> 8 votes
First of all, good chess algorithms look further than 1 or 2 levels. Rather than using naive tree search, they perform alpha-beta pruning to narrow down the number of options to consider. Note that for openings and end games, a large database of moves is used as it has better performance than tree search, which is used in the middle of the game.

To the question: what you are asking I believe is "Is chess solvable?". Hypothetically, it is, although opinions vary on whether this result will be achievable any time soon. Checkers was solved in 2007 for example, but has much fewer positions (around the square root of the number in chess). See the Wikipedia article for more information.

Incidentally, current best chess AIs nearly always defeat or draw with world champions; so while not currently perfect, the algorithms are pretty good at least!

# Answer
> 6 votes
In principle, chess is solvable like any other game. As the other answers have pointed out, however, this is not expected to happen anytime soon.

*Edit: it has been pointed out in the comments that \[1\] is a hoax so skip the rest of this answer.*

That said, there has been some recent developments in this direction. \[1\] claims to have shown that the chess opening called **King's Gambit is solved**: there's only one move that draws for White, while all other opening moves lead to a win for Black. Note that \[1\] didn't explore the game tree in full depth, but only claims these results to hold with high probability.

\[1\] http://chessbase.com/newsdetail.asp?newsid=8047

# Answer
> -1 votes
Whether it is possible to always win a game of chess or not depends on the rules of the game. However, there is an technic/algorithm named Minimax (for details, view https://en.wikipedia.org/wiki/Minimax). The algorithm consists in trying to predict which player has the upper hand in different scenarios with a recursive function. Here is an clear explanation of how this works with a simpler game: Tic-tac-toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13.

# Answer
> -3 votes
will add another answer that emphasizes the massive state space, not really conceptualized in the question or pointed out in other answers. must disagree with your premise:

> Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game.

see info on shannons 1950 paper, "Programming a Computer for Playing Chess" which introduced the field of computer based chess playing/algorithms and which its analysis is basically unchanged & still sound (even by the subsequent computer revolution and Moores law). it estimates the number of moves. its absolutely astronomical. in the range of "never within conceivable hardware even with revolutionary unforeseen advances".

its a documented psychological fact \[3\], probably one of the many psychological biases \[2\], that humans have trouble understanding numbers of this magnitude. see also *counterfactual thinking*.\[4\] while supercomputers compute massive problems, its uncontroversially not within the range of any supercomputer that is currently built or could ever *be* built. (and many chess aficionados would argue this "combinatorial explosion" in move/position possibilities is an intrinsic aspect of the games "flavor" that seems to be *intentionally designed* into the millenia-old game).

therefore chess is fundamentally different than some games which have smaller "solvable" state spaces \[of which there is some study in computer science & game theory etc\] and in some key ways cannot be evaluated within that framework.

> Allis also estimated the game-tree complexity to be at least $10^{123}$, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between $4×10^{79}$ and $10^{81}$.

now, that said, it is conceivable (but unlikely) that there may be theoretical insights into the game that could be used to prune the search space substantially. that has happened since 1950 but not really in any fundamentally breakthrough ways.

see also

\[1\] what is the computational complexity of solving chess, tcs.se

\[2\] human biases in judgement and decision making

\[3\] Psychology students publish research on conceptualizing numbers

\[4\] counterfactual thinking

---
Tags: algorithms, turing-machines
---


# Question
Title: Efficiently generating a prime polynomial of a given degree
I'm playing around with finite field arithmetic and implementing it in a little library. I'd like to be able to handle arbitrary finite fields given their size and characteristic. I don't want to write down a prime polynomial for every given possible finite field though. How can I generate a prime polynomial of a given degree for use in multiplication? To be clear I don't care which polynomial I get, and I don't want all of them. I just want any old one of a given degree. If this is an open research question what if we only try to solve it for $GF(2^n)$?

# Answer
> 2 votes
It suffices to construct an irreducible polynomial of degree $n$ over $GF(2)$ (as this immediately induces an explicit construction for $GF(2^n)$). So, how do you generate an irreducible polynomial?

One approach is to repeatedly choose a random polynomial of degree $n$, then test whether it is irreducible. You can test for irreducibility by factoring the polynomial over $GF(2)$. There are standard algorithms for polynomial factorization; they run in polynomial time. Moreover, about a $1/n$ fraction of all polynomials are irreducible (see here). It follows that on average about $n$ iterations will suffice, and since each iteration can be done in polynomial time, the whole thing runs in (randomized) polynomial time.

# Answer
> 2 votes
In a related question on MathOverflow, Igor Rivin provides a link to a 2009 pre-print of a paper of Couveignes and Lercier, Fast construction of irreducible polynomials over finite fields, which uses elliptic curves to provide a probabilistic quasi-linear algorithm. The paper was published in Israel Journal of Mathematics (2013) vol. 194, pp 77–105, DOI https://doi.org/10.1007/s11856-012-0070-8

---
Tags: algorithms
---


# Question
Title: Dynamic Programming on bracketed sequences
I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest *fully bracketed expression* (FBE), $y$ that contains a given string $x = x\_1x\_2...x\_n$. An FBE is defined as a string over the characters (,),\[, and \] that is either

1. the empty string
2. the string $\[T\]$ or $(T)$, where $T$ is a fully bracketed expression, or
3. the string $TU$, where $T$ and $U$ are fully bracketed expressions.

So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x\_i...x\_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x\_i...x\_j$ that $x\_i$ is either "mathced" to an appropriate character $x\_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.

I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!

# Answer
> 1 votes
Let $S(i,j)$ be the set of the shortest FBEs containing $x\_i\ldots x\_j$. We focus on non-trivial cases ($j-i\ge 2$).

If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k\<j$ such that $x\_i,\ldots, x\_k$ belong to $A$ and $x\_{k+1},\ldots,x\_j$ belongs to $B$. Easy to see $T(i,j)=\min\_k\\{T(i,k)+T(k+1,j)\\}$.

Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form `[`$A$`]`. Note $x\_{i+1},\ldots,x\_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x\_i\neq$ `[` or $x\_j\neq$ `]` (say $x\_i\neq$ `[` WLOG), then $A$`[]` (with the form $AB$) is also an FBE containing $x\_i\ldots x\_j$, which contradicts to the assumption. **Hence $x\_i$ and $x\_j$ must match.**

Combining the two paragraphs above, we have proved

* if $x\_i$ and $x\_j$ do not match,

$$T(i,j)= \min\_k\\{T(i,k)+T(k+1,j)\\},$$

* if $x\_i$ and $x\_j$ match,

$$T(i,j)\ge \min\left\\{\min\_k\\{T(i,k)+T(k+1,j)\\}, T(i+1,j-1)+2\right\\}.$$

Note concentrating a shortest FBE containing $x\_i\ldots x\_k$ and a shortest FBE containing $x\_{k+1}\ldots x\_j$ constitutes an FBE containing $x\_i\ldots x\_j$, so $T(i,j)\le \min\_k\\{T(i,k)+T(k+1,j)\\}$. In addition, if $x\_i$ and $x\_j$ match, say $x\_i=$ `[` and $x\_j=$ `]`, and let $s$ be a shortest FBE containing $x\_{i+1}\ldots x\_{j-1}$, then `[`$s$`]` is an FBE containing $x\_i\ldots x\_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x\_i$ and $x\_j$ match,

$$T(i,j)\le \min\left\\{\min\_k\\{T(i,k)+T(k+1,j)\\}, T(i+1,j-1)+2\right\\}.$$

So the recursion turns out to be

* if $x\_i$ and $x\_j$ do not match,

$$T(i,j)= \min\_k\\{T(i,k)+T(k+1,j)\\},$$

* if $x\_i$ and $x\_j$ match,

$$T(i,j)= \min\left\\{\min\_k\\{T(i,k)+T(k+1,j)\\}, T(i+1,j-1)+2\right\\}.$$

---
Tags: algorithms, dynamic-programming
---


# Question
Title: What does Sigma notation mean, in the context of computability of functions?
I was reading a paper on the computability of AIXI \[1\] and came across the notion of $\Sigma^0\_n$-computability for real-valued functions in section 2.3.

I'd like to read about this in more detail. Unfortunately I couldn't find this definition anywhere else in the literature. I already checked the references given at the end of the paper.

Could somebody point me to some book/article I can take a look at?

---

1. On the Computability of AIXI by J. Leike and M. Hutter (2015)

# Answer
> 1 votes
The key term for finding references is "arithmetical hierarchy of real numbers". In particular, the original article by Zheng and Weihrauch (correctly) defines those notions.

# Answer
> 2 votes
Section 2.1 of that paper defines such computability for sets of natural numbers, and Section 2.3 of that paper then extends the notion to real-valued functions.

---
Tags: computability, reference-request, computable-analysis
---


# Question
Title: Notation for expressing function call count during a program run
Which notation can be used for expressing how many times that function or subroutine called during a run of a program?

Example program pseudocode:

$ a \gets 0 \\ \textbf{While } a \neq 5 \textbf{ do} \\ \quad \textit{function1()} \\ \quad a \gets a + 1 \\ \textbf{end} $

$g: functions \rightarrow \mathbb{N}$ and for this example it is: $g(function1()) = 5$

I want to use it for expressing empirical observations depending on function call count.

```
Most of the time less than |iterSearch(searchState)|/3 child node searched during experiments.

```

What are the possible notations for function $g$ ?

# Answer
> 1 votes
Based on your desired usage and the fact that there likely isn't a widely-known notation for this, I think that, whatever notation your use, you should formally simply consider it a *name*. As you want to use the actual value, a variable (or function if you wish to distinguish among parameters for the call) would suffice.

What I mean by considering the notation a *name* is that you give your notation no syntactic status: it is simply a naming convention for some function or variable. This requires that you must define the name for each different method call number you wish to describe. I advise you to do this, as number of function calls is something that is context-dependent (calls by whom? calls made when?), so defining this for every function call separately gives a natural place to specify this.

---

So, for your particular example, a name like $\\#\mathrm{function1}(\bullet)$ could work.

Then, we can write something like

> Let $\\#\mathrm{itersearch}(a)$ be the number of calls to the function $\mathrm{itersearch}()$ in the execution of algorithm A with parameter $a$.
>
> (...)
>
> Most of the time less than $\\#\mathrm{iterSearch}(searchState)/3$ child nodes were searched during experiments.

---
Tags: notation
---


# Question
Title: TSP when cost depends only on location in sequence
I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of finding the minimal cost tour still NP-complete?

# Answer
Your problem is the same as minimum-weight perfect matching in a bipartite graph. If there are $n$ cities, consider the bipartite graph in which one side consists of vertices $p\_1,\ldots,p\_n$, the other side consists of vertices $c\_1,\ldots,c\_n$, and the weight of the edge $(p\_i,x\_j)$ is the cost of city $j$ at position $i$.

A minimum-weight perfect matching in a bipartite graph can be found efficiently (this is known as the assignment problem). In particular, the problem is not NP-hard unless P=NP.
> 1 votes

---
Tags: optimization, np-complete, traveling-salesman
---


# Question
Title: Is there an algorithm to compute the shortest Hamiltonian path in an directed graph from one point to another in polynomial time?
I am wondering whether the Shortest Hamiltonian Path (SHP) problem is NP-Complete, because I couldn't find a way of solving it in a polynominal time. if it is NP\_Complete, it will be so kind of you to give me the proof or the relevent papers,thanks a lot

the problem explanation: Given a directed,weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u. by the way,the graph must exit a hamiltonian path from v to u.

# Answer
> 2 votes
Here's a small hint.

Let $G$ be a directed graph with unit weights, and $u$ and $v$ be two vertices. Suppose that I could solve SHP in polynomial time, say, $O(n^c)$.

Now, say that I would like to solve Hamiltonian Path on a directed graph. Let me spend $O(n^2)$ time to "guess" your vertices $u$ and $v$, and for each of them run your algorithm for SHP. Then, I would in $O(n^{c+2})$ time have either found a Hamiltonian path in $G$, or conclude that $G$ is not Hamiltonian.

That would mean that P = NP.

Now, this doesn't prove that your problem in NP-complete. For that, you need to come up with a reduction. But it does tell you that you should probably not spend too much time looking for a polynomial time algorithm.

---
Tags: graphs
---


# Question
Title: Is halting problem computable for particular inputs/assumptions
From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a paradox when giving P as an input to the same P, having: P(P), trying to decide if P halts or not using P itself.

So my question is: is halting problem computable by program P for all other programs used as input but P itself? In other words: is halting problem not computable only in this special case or the proof is more general and I'm missing something?

# Answer
> 11 votes
If $f$ is any computable function, then $g$, defined as

$$ g(n) = \begin{cases} f(n) & \mbox{if } n \neq k \\ v & \mbox{otherwise} \end{cases} $$

is also computable, for any choice of $k,v$.

Basically, if you have a program $P'$ which computes $g(n)$ for all $n$'s except for $n=k$, you can "fix" that case (e.g. using an `if then else`) and obtain another program $P$ which computes $g(n)$ for all $n$.

Hence, if you could compute the halting function "except for one case", you could also compute the halting function (with no exceptions). From that, you can obtain a contradiction as usual.

Conclusion: no, you can't decide the halting problem "except one case" (nor "except finitely many cases").

# Answer
> 22 votes
> is halting problem computable by program P for all other programs used as input but P itself?

No. Consider the infinite sequence of programs $P\_1, P\_2, \dots$, where $P\_i$ is "Move the head $i$ squares to the right, then $i$ squares to the left, then do exactly what $P$ would do." Every one of these programs produces exactly the same output as $P$ for every input (including looping forever if $P$ loops forever), but they're all different programs.

And you can't get around this by only requiring $P$ to work on programs that aren't functionally equivalent to itself, since that property is also undecidable. Perhaps the problem would be decidable when restricted to those instances (though I suspect it wouldn't) but the set of instances is undecidable, so you couldn't actually perform the restriction.

# Answer
> 6 votes
There are algorithms to show that certain classes of programs do or don't halt. For example,

* It is possible to determine algorithmically whether a program that models a finite-state machine halts.
* It is possible to determine arithmetically whether a linear-bounded turing machine halts
* If you know what complexity class a program is in, then you know that the program halts for finite inputs.

While there's no algorithm to determine if an arbitrary program halts, a majority of code was designed either to halt (like most subroutines) or not halt (like an infinite loop to handle events), and it's possible to algorithmically to determine which is which. In other words, you *can* have an algorithm that answers either "halts", "doesn't halt", or "I dunno", and such an algorithm can be designed to cover enough programs that it would be useful.

# Answer
> 4 votes
Proofs by contradiction don't have to be *exhaustive*, a single counter-example is enough. The proof of the halting problem being undecidable provides you with one example of P for which the halting property cannot be decided. This proof doesn't state that P is the only such program, in fact, there may exist independent proofs constructing completely different classes of P.

# Answer
> 3 votes
The proof is indeed more general: the halting problem is a special case of Rice's theorem, which states

> If $\Phi$ is a property of programs that is independent of representation, then it is either always true, always false, or undecidable.

where "independent of representation" means that if $A$ and $B$ are programs that have the same behaviour for all inputs, then $\Phi(A)$ holds iff $\Phi(B)$ holds.

This means in particular that for every input $x$, the set of programs that halt on $x$ is undecidable; you cannot get decidability by reducing the input space.

You *can* get some results by restricting the space of programs you want to work with, though these restrictions have to be fairly drastic. For example, if you are guaranteed that the program you are given either halts within 100 steps or runs forever, deciding whether it halts becomes easy.

A more complicated case is when you know that the program is at most 100 characters long. Since there are only finitely many programs of that length, there exists some number of steps $N$ that is an upper bound on how long such a program can run if it terminates. However, the function that maps a program length $k$ to a maximum number of steps $BB(k)$ is not computable.

# Answer
> 0 votes
Let R be any recursively enumerable but nonrecursive set. There are infinitely many such sets. Let T be a Turing machine that halts on input k if and only if k is in R. Such a T exists for any recursively enumerable set. It is impossible to write a program which can solve the halting problem for this T. This is because any algorithm to determine if T halts would yield an algorithm for determining membership in R, which is impossible if R is nonrecursive. Since there are infinitely many such R, each of which give different Turing machines, there are infinitely many Turing machines that any attempted halting program P would fail on.

---
Tags: halting-problem
---


# Question
Title: Write algorithm for biased toss of a coin
Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

I am not able to proceed with the problem. What should be my approach ?

# Answer
You should just use a random number generator which is generally located in Math libraries. (Pseudo) Random number generators generally use linear congruences like $X\_{i+1} = (a X\_i + c) ~ {\rm mod} ~ m, ~~~ i = 0, 1, 2, ... $

```
function()

   var rand := generateRandomNumber [1, 100]
   if rand<=67 then
      print "heads"
   else
      print "tails"
   endif

end function

```

generateRandomNumber function will return a pseudorandom number between 1 and 100. So if we say your random variable is $X \\\$
$ Then,\\; P(X\leq67)\\; will\\; be \\; \frac{67}{100}\\;and \\; P(X\>67)\\; will\\; be \\; \frac{33} {100} $
> 0 votes

# Answer
Let $\xi$ be a random variable uniformly distribuited in $\[0,1\]$ and $t$ a real value in $(0,1)$, consider the function

$$ Y(\xi;t) = \begin{cases} 1 & \xi \< t \\ 0 & \text{otherwise} \end{cases} $$

Which is a discrete random variable therefore

$$ p\_Y(y) = (1-t) \delta(y) + t \delta(y - 1) $$

This means that if pick a random number in $\[0,1\]$ and you later compute $Y$, this $Y$ will correspond to a randomly picked value in $\left\\{0,1\right\\}$, but biased accordingly to $t$. If you use @kngtu pseudocode, it's equivalent to define the distribution above where $t = 0.67$.
> 1 votes

# Answer
If you can generate a random number between 0 and 1, then do

Edit: round random to 2 decimal places

if (random \< 0.34) return "tails"; else return "heads";

That way (assuming the random number generator is actually random) you have a 33% change of tails and 67% chance of heads.
> -1 votes

---
Tags: algorithms
---


title: ALOHA - Throughput and probabilities

text:
# Question
Title: ALOHA - Throughput and probabilities
I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25.

1) What is the throughput and what is the probability that a user will successfully transmit a frame after three unsuccessful attempts? I have managed to calculate the throughput as 0.00627. But the major problem is the probability to succeed after 3 attempts. Should I use these two formulas?

$$ n\_a = \sum\_{n=0}^\infty n(1-p\_a)^n p\_a $$

$$ n\_a = \frac{1-p\_a}{p\_a} $$

2) What is the average number of unsuccessful attempts before a user can transmit a frame in the above problem?

Can somebody assist me?

Best regards

# Answer
> 0 votes
I assumed that you have calculated the probability of successful transmit (which is about 1e-4 or something)

$$ P\[trials = 3\] = P\[Fail\] ^3 * P\[Succ\] $$ $$ Average = E\[X\] = 1/P\[Succ\] $$

Please revise or study (if you haven't) the geometric distribution

---
Tags: probability-theory
---


# Question
Title: Dynamic Programming vs Greedy - coin change problem
This is a fairly common problem:

Given coins of integer denominations $v\_1 \< v\_2\< ... \< v\_n$, make change for an amount A using as few coins as possible.

Given an input of powers of $p$,

$V = \[1, 3, 9, 27\]$

How would a dynamic programming vs greedy approach differ in this algorithm? I don't have a good general idea of how these approaches would differ.

# Answer
> 4 votes
A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + one of the precomputed values. Here is a link talking about dynamic: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change

Greedy choice however uses the fact that, for many currencies, we simply can take the maximum value that still gives us less than then our amount and ignore all other possibilities. However, greedy doesn't work for all currencies.

For example: V = {1, 3, 4} and making change for 6: Greedy gives 4 + 1 + 1 = 3 Dynamic gives 3 + 3 = 2

Therefore, greedy algorithms are a subset of dynamic programming. Technically greedy algorithms require optimal substructure AND the greedy choice while dynamic programming only requires optimal substructure.

# Answer
> 0 votes
If $A$ is your amount you're looking for $k\_1,\ldots,k\_n$ you want to minimize

$$ f(k\_1,\dots,k\_n) = k\_1 + \ldots +k\_n $$ subjected to $$ A = k\_1 v\_1 + \ldots k\_n v\_n $$

As dynamic programming I would procede as follow... say you want to add $v\_i$ to the change, then as next step you will try to minimize the amount the change for the amount $A - v\_i$, assuming $A \geq v\_i$ of course. So basically for each coin you add the coin to the feasible solution, and recurse for the problem $A - v\_i$, once the recursion is over you pick the smallest set of coins. For the greedy solution you iterate from the largest value, keep adding this value to the solution, and then iterate for the next lower coin etc.

I think though you can work out this by simply using divisions. Basically $k\_n = \frac{A}{v\_n}, k\_{n-1} = \frac{A - k\_nv\_n}{v\_{n-1}}, \ldots k\_{n-i} = \frac{A - k\_n v\_n - \ldots k\_{n - i + 1} v\_{n-i+1}}{v\_{n-1}}$ etc... which essentially I think is the solution for the greedy strategy.

---
Tags: algorithms, optimization, dynamic-programming, greedy-algorithms
---


title: Notation for field access in Algorithm

text:
# Question
Title: Notation for field access in Algorithm
While writing array index in an algorithm $a\[i\]\gets v$ is conventionally used. Is the notation $a\_{i}\gets v$ also used ?

If the algorithm uses `struct` or equivalent, some notation is required for property access. In some occasions $p(s)$ is used where $p$ is the property. Using $s \rightarrow p$ messes up with the assignment arrow. Using $s\_{p}$ looks like $p$ is an index and $p\in \mathbb{Z}^{+}$. Should $s\["p"\]$ be used ? What is the convention to denote property access in algorithm ?

Is there any reference where I can check different notations of these two scenarios ?

# Answer
Not everyone follows the same conventions, but I'll describe the ones I see most commonly. Your experience may vary.

* If $a$ is an array, $a\[i\]$ is typically used, but not $a\_i$.
* If $(a\_1,\dots,a\_n)$ is a sequence, $a\_i$ is typically used, but not $a\[i\]$. Usually sequences are not updateable.
* If $a$ is a string, you might see either $a\[i\]$ or $a\_i$; both are common, in my experience.
* I have most commonly seen $s.p$ used for property access. Sometimes I have seen people use $p(s)$ used.

Different sources may follow different conventions. There is no one right answer. A good approach is to find a textbook that you like (e.g., CLRS), and then follow the same conventions they use. Odds are that they have put some thought into choosing consistent and understandable conventions, so they probably have chosen something reasonable.
> 3 votes

---
Tags: algorithms, notation, pseudocode
---


# Question
Title: How can I partition a graph such that as few edges as possible cross partition boundaries?
The following problem appeared while trying to distribute a program over a cluster of computers:

Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ partitions $V\_i$ of about equal size such that the number of edges crossing partition boundaries is minimised.

You can imagine $V$ as being chunks of a data set with $E$ indicating which chunks are related to what other chunks. When the computer operates on a chunk $v\in V\_i$, it needs to access chunks from all $w\sim\_E v$ and the performance is better if as many $w$ as possible are in the same partition $V\_i$. The chunks are all of equal size and it is important that each partition $V\_i$ contains about the same amount of them.

How can I a) model and b) approximate a good solution for this problem?

# Answer
> 4 votes
Your problem is known as graph partition. Apart from $n$, the problem has a parameter $\epsilon \geq 0$, and it is required that each part have size at most $(1+\epsilon)|V|/n$. The Wikipedia article mentions several relevant algorithms. The case $n = 2$ is known as *minimum bisection* when the parts are required to be exactly equal, and this is a well-known special case.

# Answer
> 1 votes
It should be noted that even the simplest case (minimum bisection) problem is NP-Hard. Look at the following articles:

"REDUCIBILITY AMONG COMBINATORIAL PROBLEMS" by Richard M. Karp

"Some Simplified NP-Complete Graph Problems" by M. R. Garey and D. S. Johnson

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)
I'm looking for a reference to an algorithm that does the following. Given `n`, and a range `[min, max]`, generate a random ascending stream of `n` integers `i_1, i_2 .. i_n` such that `min <= i_1 < i_2 < ... < i_n <= max`. And this should be done in constant space.

(So I'm looking for a more efficient alternative to the following simple approach: First generate `n` random numbers in the desired range, then sort them, and then go over the sorted list in order. This needs `O(n)` space.)

I could swear I saw a paper describing an algorithm that does exactly this. But I can't find that paper again, no matter what I search for. Am I misremembering? Can you help me?

# Answer
> 2 votes
It can be done in $O(1)$ space and $O(n^2)$ time. Let $X\_1,\dots,X\_n$ denote the numbers in the stream, in sorted order. You can calculate

$$\Pr\[X\_i = x\_i | X\_1=x\_1,\dots,X\_{i-1}=x\_{i-1}\]$$

and then use that to generate the numbers $X\_1,\dots,X\_n$ one by one.

Here is the derivation. We have

$$\begin{align\*} \Pr\[X\_1=x\_1,\dots,X\_{i-1}=x\_{i-1}\] &= {{\text{max}-x\_{i-1} \choose n-i+1} \over {\text{max}-\text{min}+1 \choose n}}\\ \Pr\[X\_1=x\_1,\dots,X\_{i-1}=x\_i\] &= {{\text{max}-x\_i \choose n-i} \over {\text{max}-\text{min}+1 \choose n}} \end{align\*}$$

so it follows that

$$\Pr\[X\_i = x\_i | X\_1=x\_1,\dots,X\_{i-1}=x\_{i-1}\] = {{\text{max}-x\_i \choose n-i} \over {\text{max}-x\_{i-1} \choose n-i+1}}= \Pr\[X\_i = x\_i | X\_{i-1}=x\_{i-1}\].$$

Here the domain of possible values for $X\_i$ is $x\_{i-1}+1,\dots,\text{max}$; the probability is zero for other values of $X\_i$ outside that domain.

Notice that this probability depends only on $x\_{i-1},x\_i$, so you only need a constant amount of space: you don't need to remember the entire past history.

Thus, the algorithm becomes:

1. Pick $x\_1$ from the distribution $\Pr\[X\_1=x\_1\] = {{\text{max}-x\_1 \choose n-1} \over {\text{max}-\text{min}+1 \choose n}}$.
2. For each $i=2,3,\dots,n$, pick $x\_i$ from the distribution for $\Pr\[X\_i = x\_i | X\_{i-1}=x\_{i-1}\]$ given above.

This algorithm requires only $O(1)$ space. The running time might be $O(n^2)$ (since it might take $O(n)$ time to draw from a distribution with $n$ possible values). Perhaps further analysis could reduce the running time by finding a more efficient way to draw from these distributions. For instance, if you could find a way to compute the cdf (cumulative distribution function) for these distributions and evaluate it at an arbitrary $x\_i$ in $O(1)$ time, then you could reduce the total running time to $O(n \log n)$ by using binary search at each step to draw from the distribution. I don't see how to do that myself, but perhaps someone else will.

This might get a lot easier if you are willing to draw streams of non-decreasing integers rather than a stream of increasing integers (i.e., allow an integer to be repeated), since the formulas for probability for drawing with replacement tend to be a lot simpler than those for drawing without replacement.

# Answer
> 1 votes
Original asker here. For anyone else looking at this: the paper I was looking for is **Generating Sorted Lists of Random Numbers** by Jon Louis Bentley and James B. Saxe. The algorithm in the paper does what I asked.

---
Tags: algorithms, reference-request, sorting, random-number-generator
---


# Question
Title: Sort sequence from topological sort if another value is being important
We have sequence that we got from topological sort, but because the graph may not be connected in all cases, we should sort this sequence with another factor.

We should output permutation of numbers from $1$ to $n$ such that we also have graph $G$ that is without cycle and might be not connected and array $A$ of integers that is keeping another information for each nod. Now for each pair $(i,j)$ node $j$ should be after node $i$ if they are connected, meaning node $j$ is under node $i$, on other hand if not $j$ is not under $i$, they are not connected, they should be compared with the another array A and sorted with that array.

So, if node $j$ is not reachable from node $i$, node $j$ should be after $i$ if $A\_j$ is greater than $A\_i$

For example, let our graph have 3 nodes and 1 edge: $(1, 2)$. If $B$ after the topological sort is $\\{ 3, 1, 2\\}$ and another sequence $A\_1 = 5, A\_2=8, A\_3=1 $. We should sort the sequence $B=\\{1, 2, 3\\}$. We cannot put $2$ before $1$ because we will break the topological sort rule give above.

I was thinking about using normal sorts, but they are not giving correct results.

# Answer
> 0 votes
Your requirements may not be simultaneously satisfiable. Consider the graph with three nodes $1,2,3$, and a single edge $1 \to 2$. Suppose the array $A$ is $\[15,5,10\]$. Then node 1 is not reachable from node 3 and $A\_1 \> A\_3$, so your requirement says node 1 should be after node 3. Also node 3 is not reachable from node 2 and $A\_3 \> A\_2$, so your requirement says that node 3 should be after node 2. Finally based on the graph, we require node 1 to be before node 2. These three requirements are not simultaneously satisfiable.

In general, if you have a problem you don't know how to approach, I suggest you start by working through a bunch of small examples by hand, to get a feeling for what's going on. That will help you discover examples like this.

---
Tags: sorting, topology
---


# Question
Title: Can the regular image of a context-free language be undecidable?
I just need to know the truth or falsity of a simple statement.

Let $L\_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special metacharacter “|”. Suppose that every string in $L\_1$ contains exactly one metacharacter. Let the *left half* and *right half* of a string in $L\_1$ denote the part of the string before the “|” and the part after, respectively. Let $L\_2$ be the language over $\Sigma$ containing all the right halves of the strings in $L\_1$.

Then is membership in $L\_2$ decidable? What about if $L\_1$ is restricted to be nice in some way? I'm fairly sure there are counterexamples in any case, but I can't find them.

# Answer
If $L\_1$ is context-free, then so is $L\_2$. You can show this easily using closure properties of context-free languages. Let $\Sigma' = \\{ \sigma' : \sigma \in \Sigma \\}$; we assume that $\Sigma$ and $\Sigma'$ are disjoint. Define a homomorphism $h\colon \Sigma \cup \Sigma' \cup \\{|\\} \to \Sigma^\* \cup \\{|\\}$ by $h(\sigma) = h(\sigma') = \sigma$ and $h(|) = |$, and a homomorphism $k\colon \Sigma \cup \Sigma' \cup \\{|\\} \to \Sigma^\*$ by $k(\sigma) = \sigma$ and $k(\sigma') = k(|) = \epsilon$. Then $$ L\_2 = k(h^{-1}(L\_1) \cap \Sigma^{\prime\ast} | \Sigma^\*). $$ The family of context-free languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages, hence $L\_2$ is context-free as well.
> 6 votes

# Answer
This is a form of **left quotient** of a context-free language by a regular language:

$L\_2 = R\backslash L\_1 = \\{ x\in \Sigma^\* : yx\in L\_1 \text{ for some } y\in R \\}$, where in your case $R= \Sigma^\* \mid$.

Context-free languages are closed under quotient by regular languages. Usually one considers right quotient, where the regular language is chopped off from the right. The argument however is symmetric (context-free and regular languages are both closed under mirror image).

See
> 6 votes

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


# Question
Title: Find longest subsequence in array with given condition
I am given an array $A$ having $n$ elements and an integer $k$.

I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition:

for all $i \< j$: $|A\[i\] - A\[j\]| \leq k$.

Example: $n= 4$, $k = 5$, $A = \[1, 2, 50, 6\]$

Answer: the longest valid subsequence, $\[1, 2, 6\]$, has length $3$.
Note that the first element is always to be included in the sequence.

I think this can be solved with Dynamic Programming. But I can't form a recursive equation for Dynamic Programming.

# Answer
> 4 votes
In the following answer, I show how to solve in $O(n\log n)$ the following similar question:

> Given an array $A$ and a number $k$, find the longest *contiguous* subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Using this, it is easy to solve in $O(n \log n)$ the following question, closer to yours:

> Given an array $A$ and a number $k$, find the longest subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Indeed, sort $A$ and then find the longest contiguous subsequence satisfying the condition.

Finally, to solve your actual question, filter $A$ by removing all elements at distance more than $k$ from the first element. The longest subsequence is now guaranteed to contain the first element (since it can always be added), so we can run the preceding algorithm to solve your question in $O(n\log n)$.

# Answer
> 2 votes
The solution by Daniel Saad is on the right track, but unfortunately isn't complete. It's not difficult to come up with an example when the greedy algorithm fails and hence the item should be better excluded even if it satisfies the condition when it's processed:

Let $A=(1, 0, 2, 2)$ and $k=1$. The answer is $(1, 2, 2)$ and one would make a mistake by including $0$ into a subsequence, because it will shut the door for both $2$s. Obviously, the skip sequence can be arbitrarily long, e.g. $A=(1, 0, ..., 0, 2, 2, ..., 2)$.

Moreover, an algorithm that tries to complete *any* previous subsequence is also wrong, because the principle of optimality isn't satisfied. Consider this example:

Let $A=(0, 1, -1, 0, 2, 2, 2, 2)$ and $k=2$. The optimal sequence up to $A\[4\]$ is $(0, 1, -1, 0)$ (contains all items). But the answer up to $A\[5\]$ is *not* completing the best sequences up to $A\[4\]$ or up to $A\[2\]$! The best subsequence actually includes $A\[4\]=0$ and excludes $A\[3\]=-1$.

---

The algorithm I came up fills the table $T\[i, p, q\]$, which designates the best subsequence that ends with item $i$, the minimum of which is $A\[p\]$ and the maximum is $A\[q\]$ ($p \leq i$ and $q \leq i$). This means that on each step $i$, the list of candidates is going to hold up to $i^2$ values, for each $(A\[p\], A\[q\])$ pair from $A\[1..i\]$. The total time is $O(n^4)$!

The base equation is trivial. The transition on step $i+1$ computes the list of candidates by completing *all candidates* from the previous steps $T\[j\]$, $j \leq i$. The total number of candidates is $O(n^3)$. I leave you the task of writing formal recursive equations as an exercise.

---
Tags: algorithms, dynamic-programming, subsequences
---


# Question
Title: How to efficiently sort and filter a large iterator
Given an huge iterator (millions of random elements) and asked to obtain the top 10 elements in descending/ascending order. What is an efficient way or algorithm to do this?

**NOTE**: The iterator size is to huge and cannot be all loaded into memory and in-place sorting done. (I need a different approach)

I have a simple implementation in Python (sorting an iterators containing hash maps), but it's not efficient

```
def sort(iterator, sort_key, count):
    result = []
    for idx, row in enumerate(iterator):
        if idx < count:
            result.append(row)
        elif idx == count:
            result.sort(key=lambda x: x[sort_key])
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]
        else:
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]

    return result

```

# Answer
You can use a max-heap or min-heap. If you want to find the top $k$ elements, use a min-heap. Start by inserting the first $k$ elements. For every subsequent element, compare it to the root of the min-heap. If the new element is smaller, continue to the next element. Otherwise, remove the root and insert instead the new element, operations which can be done in $O(\log k)$. In total, this is an $O(n\log k)$ algorithm.
> 3 votes

---
Tags: algorithms, sorting
---


title: Activity Selection and Matroid Theory

text:
# Question
Title: Activity Selection and Matroid Theory
Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

1. Maximum sum of m integers among n integer.
2. Minimum spanning tree.

However, The classical greedy algorithm **Activity Selection** seems to fail having both ***independence and base exchange*** property.

Let, `E = {1-3, 2-4, 3-5, 4-6, 5-7}`

Now, Take two independent set, `I = {2-4, 4-6}` and `J = {1-3, 3-5, 5-7}`

There is no activity in `J` which can extend `I`. Which fails the ***independence exchange*** property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?

# Answer
> 1 votes
Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom:

> If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$.

Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}\_+$ (here $\mathbb{R}\_+$ consists of all positive reals):

1. Set $S \gets \emptyset$.
2. While there exists an element $x \notin S$ such that $S \cup \\{x\\} \in \mathcal{F}$:

* Let $x$ be an element of maximum weight among $\\{ x : x \notin S \text{ and } S \cup \\{x\\} \in \mathcal{F} \\}$.
    * Set $S \gets S \cup \\{x\\}$.
3. Return $S$.

We say that the algorithm is *valid* for $w$ if it returns a set $S$ maximizing $\sum\_{x \in S} w(x)$ among all $S \in \mathcal{F}$.

> **Theorem.** The algorithm is valid for all $w\colon U \to \mathbb{R}^+$ iff $\mathcal{F}$ is a matroid.

You can find the proof of this theorem in lecture notes and in textbooks.

The algorithm given above is a specific greedy algorithm. This specific greedy algorithm is optimal if and only if the set system is a matroid. However, the (informal) notion of greedy algorithms encompasses more than just this specific algorithm. The theorem above doesn't apply to these algorithms.

In the two good examples you consider, the corresponding greedy algorithms (or at least one of their variants) are instances of the algorithm above. The same isn't true for the algorithm for your bad example.

For a formalized notion of "greedy-like" algorithms, consult (Incremental) priority algorithms by Borodin, Nielsen, and Rackoff. You can see that is is much more general than the simple algorithm stated above.

Another relevant notion is that of greedoid, for which a theorem similar to the one stated above does hold (see Wikipedia for details).

---
Tags: greedy-algorithms, matroids
---


# Question
Title: Graph Algorithm (Modification on Dijkstra?) : Tech Interview
*Problem:* Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S \in V$. Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK). If no path exists, output -INF or +INF. Polynomial time algorithms only (in $V$, $E$, and $C$).

*My attempt:* If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.

I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.

# Answer
> 4 votes
The Hamitonian path problem is reducible to your problem. Given a directed graph $G(V,E)$, set $C=|V|$ (number of nodes), $A = V$, and weight of each edge is equal to $1$. Thus, this instance of the problem requires to find a shortest path containing all vertices. Since it asks to find the shortest path, cycles are not allowed, and since it asks to include all vertices, the path visits all vertices once. This is a Hamiltonian path. So, your problem is NP-complete meaning it is unlikely to find a polynomial time algorithm. In this case you should try approximation algorithms or Linear/Integer programming algorithms.

**Note (on @user53923's comment)**: There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.

# Answer
> 2 votes
The problem can be solved in polynomial time if we interpret this condition:

> Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK)

... in the following way: find the shortest path containing at least $C$ **occurrences** of vertices from $A$. That would include, for instance, the path $(S, a\_1, a\_2, a\_1)$ for $C=3$ and $a\_i \in A$. You can't reduce *this* problem to Hamiltonian path problem, so it doesn't contradict the answer by @fade2black. Probably your interview assumed this interpretation.

### Algorithm

Before doing anything, let's assume we've found the distances between any two vertices $u, v \in V$, let's call it $d\[u, v\]$ (Floyd–Warshall algorithm is polynomial).

Suppose $C = 1$. Since the weights are positive, the shortest path must end with a vertex from $A$ (by going further we'll only make the path longer). Hence, we are interested in $\min\_{a \in A} d\[s, a\]$. Let's view it as a base and call it

$$D\_1(a) = d\[s, a\],$$

the solution for all ending vertices for $C = 1$.

Next, we can compute $D\_{n+1}$ from $D\_{n}$. Like before, the shortest path that contains $n+1$ vertices from $A$ must end with some $a \in A$. In addition, for the previous vertex on that path $a'$ the following holds:

* the path from $S$ to $a'$ is optimal (containing $n$ vertices from $A$);
* the path from $a'$ to $a$ is optimal.

Hence,

$$D\_{n+1}(a) = \min\_{a' \in A} (D\_n(a') + d\[a', a\])$$

Note: we never check how many *unique* vertices from $A$ are on the path and count only the *occurrences*.

In total, the algorithm does $C$ cycles that compute $|V|$ values, each requiring finding minimum of $|V|$ values. The result is thus $O(|V|^3 + C \cdot |V|^2) = O(|V|^3).$

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


# Question
Title: What would be the appropriate learning path given these circumstances?
I've recently been trying to learn to program in python but I’ve been experiencing this overwhelming feeling of a desire to understand the underlying structure behind everything I’m doing. I want to be able to understand how computers work from the ground up, how hardware and software relate to one another and develop an intuition for their potential. I'd also like to know how all these languages that build on top of each other all rely on the same fundamentals and what those fundamentals are. Only then do I think I’ll feel comfortable and satisfied learning and working on a more superficial abstraction which I consider python to be.

Can any of you recommend a path I should take in order to satisfy this need? Whether that be a particular order of learning certain topics or more specifically any book, video, course that you might consider appropriate given my situation.

Thank you,

Mango164

# Answer
> 1 votes
A project I would recommend is the NandToTetris Project. It takes you from understanding the basic logic gates through VonNeumann architecture to how Operating Systems work.

---
Tags: computer-architecture
---


# Question
Title: Algorithm for determining if there is exactly one Eulerian path
Given a directed graph such that at least an Eulerian path exists, how to determine efficiently if there is exactly one Eulerian path?

Of course if there is an Eulerian circuit then there is more than one Eulerian path, so we will assume that no Eulerian circuit exists. In other words, just to fix some notation, we assume that for all nodes $\text{indegree}=\text{outdegree}$ except for two nodes $r$ (starting point) and $s$ (ending point) for which the following holds: $$\text{outdegree}(r) = \text{indegree}(r)+1$$ and $$\text{indegree}(s) = \text{outdegree}(s)+1.$$

An observation. If there is a node with $\text{outdegree} \geq 3$ then there are at least two distinct Eulerian paths. Is this condition only sufficient or maybe even necessary?

# Answer
> 1 votes
Do you know an algorithm for finding Eulerian paths? Fleury's algorithm begins at one of the endpoints and draws out the eulerian path one edge at a time, then imagine removing that edge from the graph. The only trick to the algorithm is that it never chooses an edge that will disconnect the graph. Only with that condition, it is guaranteed to never get stuck in tracing out an eulerian path. So, as long as that choice of edge is unique at every step, the eulerian path will be unique. If ever there are two choices that can be made which are valid (i.e. they each would not disconnect the graph) then you have multiple eulerian paths.

# Answer
> 0 votes
The condition you give is not necessary. Consider the following graph:

There are two Eulerian paths $A\rightarrow B\rightarrow C\rightarrow A\rightarrow E\rightarrow B\rightarrow D\rightarrow E$ and $A\rightarrow E\rightarrow B\rightarrow C\rightarrow A\rightarrow B\rightarrow D\rightarrow E$, but out-degree of each node is no more than $2$.

We now focus on graphs where out-degree of each node is no more than $2$.

Add an edge from $s$ to $r$ to form a new graph $G$, then there is exactly one Eulerian path if and only if there is exactly one Eulerian cycle in the new graph. According to BEST theorem, the number of Eulerian cycles equals $t\_w(G)\prod\_{v\in V}(\deg(v)-1)!=t\_w(G)$ (note out-degree of each node is no more than $2$ by assumption), where $t\_w(G)$ is the number of arborescences of $G$, and can be computed by computing a determinant according to Kirchhoff's theorem.

To summarize, let $Q$ be the Laplacian matrix of $G$, and $Q'$ be the matrix got by deleting the $i$-th column and the $i$-th row (any $i$ is OK) from $Q$. Then there is exactly one Eulerian path in the original graph if and only if $|Q'|=1$.

---
Tags: eulerian-paths
---


title: Does counting sort require mutation?

text:
# Question
Title: Does counting sort require mutation?
I'm trying to implement counting sort in Haskell for a list of type `(Int, String)`. I've been trying to do it according to Wikipedia's description.

After some attempts, I gave up, because the Wikipedia description makes heavy use of mutation in different places throughout the algorithm, which I just don't know how to translate to a declarative language.

So my question is, does counting sort require mutation or can it be implemented in a language like Haskell without fancy constructs?

# Answer
> 1 votes
First off, a persistent map from address to value can simulate RAM. There is a time overhead of $O(\log(s))$ and a space overhead of $O(s)$, where $s$ is the space used.\* So an algorithm that runs in time $t$ and space $s$ in RAM has a purely functional algorithm in time $O(t \log(s))$ and space $O(s)$. However, simulating the RAM itself, at least conceptually, creates a purely functional *computer*, not version of the particular algorithm in question, so it probably isn't what you're looking for.

Fortunately this algorithm can be tweaked slightly to be purely functional. Using a persistent sorted map from list item to count, you can traverse the list, updating the count in the map for each list item encountered in $\theta(n \log(c))$ time and $\theta(c)$ space, excluding input and output lists, where $c$ is the number of distinct values. Then, you can `concatMap` the (list item, count) pairs to count occurrences of the list item. As the map is already sorted by list item, the resulting list will be sorted.

The original algorithm runs in $\theta(n)$ time and $\theta(c)$ mutable space, excluding input and output lists, so the functional version introduces a factor of $\log(c)$ in its run time, which is the same factor introduced by simulating the RAM.

---

* Specifically, as far as time is concerned, $s$ is the *mutable* space used, as any immutable space can be provided separately in a read-only array so it doesn't impose any time penalty.

---
Tags: algorithms, sorting
---


title: ResNet output dimensions

text:
# Question
Title: ResNet output dimensions
So I am currently going over the ResNet paper and trying to understand the output dimensions of each of the layer, and it seems that I am already stuck on the first layer and its output dimension.

If I understand correctly, the size of output of a particular layer can be calculated as **(ORIGINAL\_SIZE - FILTER\_SIZE) / STRIDE + 1**

In the plain example of the ResNet, presented below on the right hand side, they claim they use 224x224 image. Therefore, when I calculate the output dimension of the 7x7 convolution with stride 2, I get

(224 - 7) / 2 + 1 = 109.5, so I round it 110.

However, in the paper they claim that their output size is 112. How would that be possible?

# Answer
I managed to find an official github repository, and they use a padding of size 3, and therefore the output 112.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Question about proving that Rado's function is non-computable
I am currently following the proof, found here, that Rado's function $$ \Sigma (n) = \max \\{ \text{# of 1's that may be written to a tape by an n-state turing machine} \\} $$ is non-computable. Within this proof, they say that there exists a Turing machine $M\_F$, which we say has $n$-states, that writes $F(x)$ 1's to the tape.

However, they then go on to imply that there exists a Turing machine with $n$ states which writes $F(F(x))$ 1's to the tape! Surely, since $F(x) \> x$ this should require more than $n$ states - since more states $\iff$ more 1's?

**EDIT:** For added clarity, I will now explain why I have interpreted this to mean that both $F(x)$ and $F(F(x))$ have $n$ states.

This proof first defines a Turning machine $M\_F$ which has $n$ states and writes $F(x)$ 1's to the tape before halting. It then goes on to describe a (trivial) $x$-state Turing machine $M$ which "on input $\Lambda$" writes $x$ 1's to the machine's tape.

The proof then goes on to claim that $$ \Sigma (x + 2n) \geq x + F(x) + F(F(x)) $$ which means that there exists a $x + 2n$ state Turing machine which prints $x + F(x) + F(F(x))$ 1's to the machines tape.

I am *assuming* that these $x + F(x) + F(F(x))$ 1's are written as follows:

1. The $x$ state Turing machine $M$ prints $x$ 1's to the tape.
2. Next, $F(x)$ 1's are written to the tape by the $n$ state Turing machine $M\_F$
3. So far, we have written $x + F(x)$ 1's and $x+n$ states have been used to do so. Comparing this to the fact that $x + F(x) + F(F(x))$ 1's may be written using $x + 2n$ states, they are implying that there must exist a Turing machine which writes $F(F(x))$ 1's using $n$ states

I am probably interpreting this incorrectly, but I don't know why?

# Answer
Thanks for the clarification! I really misinterpreted your question.

Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M\_F$ with the following behavior:

> when started with a tape with $y$ $1$'s, writes a block of $F(y)$ $1$'s to the right, separated by at least one blank

Note that I used $y$ instead of $x$. So when our TM starts with a tape like

$$\Delta\underbrace{1\ldots1}\_{\times y}\Delta$$

the resulting tape will be

$$\Delta\underbrace{1\ldots1}\_{\times y}\Delta\underbrace{1\ldots 1}\_{\times F(y)}\Delta$$

and we say that $M\_F$ uses $n$ states. **Note that $n$ is independent of $y$.** The number of states doesn't depend on the input of the TM.

Now the machine $M$ does the following:

1. Start with blank tape: $\Delta$
2. Write $x$ $1$'s on tape: $$\Delta\underbrace{1\ldots1}\_{\times x}\Delta$$
3. Now mimic $M\_F$ with these $x$ $1$'s as a start, i.e. $y=x$: $$\Delta\underbrace{1\ldots1}\_{\times x}\Delta\underbrace{1\ldots 1}\_{\times F(x)}\Delta$$
4. Now we mimic $M\_F$ *again*, but this time with the $F(x)$ $1$'s as a start, i.e. $y=F(x)$: $$\Delta\underbrace{1\ldots1}\_{\times x}\Delta\underbrace{1\ldots 1}\_{\times F(x)}\Delta\underbrace{1\ldots 1}\_{\times F(F(x))}\Delta$$

So when we mimic $M\_F$ a second time, we simply ignore the $x$ $1$'s at the leftmost of the tape and pretend they are not there. I think the text is implying that executing $M\_F$ doesn't moves it too much left and that is understandable, since this behavior can be simulated by using a one-side bounded TM which is equivalent to our usual TM. So by mimicking $M\_F$ two times, we would need about $2n$ states for that.
> 3 votes

---
Tags: turing-machines, computability, check-my-answer
---


# Question
Title: Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?
I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.

Does it make sense to discuss the complexity of computing a function that cannot be computed?

# Answer
Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about. Or, to put it the other way around, it only makes sense to talk about the computational complexity of the halting problem with respect to models of computation in which that problem is computable. For example, you could talk about the complexity of recursively enumerable problems using Turing machines with an oracle for the halting problem as your model of computation.

The proof you link to does *not* show that the halting problem is in **NP**. It shows that the halting problem is **NP**-hard, which just means that every problem in **NP** is polynomial-time reducible to the halting problem.
> 22 votes

# Answer
The halting problem is not in NP. It is, however, NP-hard, which is not the same thing.
> 12 votes

---
Tags: complexity-theory, computability, halting-problem
---


# Question
Title: Developing invariants for comparing two strings
The following algorithm is supposed to compare two strings $S\_1$ and $S\_2$ ("/\\" for empty string):

```
X = S1
Y = S2

E = true
// (1)
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2)
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 \land E = false
// (4) S1 = S2 <=> E = true
return E

```

I want to develop invariants at points (1) and (2).

The invariant at (1) I choose is $$S\_1 = S\_2 \iff X = Y \land E = true.$$

From it, I can derive an invariant at (2):

$$(S\_1 = S\_2 \iff X = Y \land E = true) \land \lnot(X \neq \Lambda \land Y \neq \Lambda \land E = true).$$

Then I tried to simplify the formula:

$$(S\_1 = S\_2 \iff X = Y \land E = true) \land (X = \Lambda \lor Y = \Lambda \lor E = false)\\ \equiv \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (X = \Lambda)\big) \lor \\ \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (Y = \Lambda)\big) \lor \\ \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (E = false)\big) \\ \equiv (S\_1 = S\_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor \\ (S\_1 = S\_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor \\ \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (E = false)\big)\\ \equiv \big(S\_1 = S\_2 \iff (X = \Lambda \land Y = \Lambda) \land (E = true)\big) \lor \\ \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (E = false)\big)$$

My problems are

* Is the derivation above correct? If so, how to further simplify this formula? In particular, how to deal with the second disjunction? Is it simply $S\_1 \neq S\_2 \land E = false$?
* How does the invariant at (3) and (4) follow from the one at (2)?
* Can we obtain an invariant at (2) in a single conjunct instead of multiple disjuncts?

# Answer
I would not simplify $(2)$ at all. Just apply the rules for `if`, `=`, and command composition. Use weakening (pre- or post- rules) when convenient to do so.

Below, I added an empty `else` branch for clarity.

```
// (2): (S1 = S2 <=> X = Y \land E = true)
//            \land \lnot(X != /\ \land Y != /\ \land E = true)
if !(X == /\ and Y == /\)
  // (3a): (2) \land (X != /\ \lor Y != /\)
  // (3b): S1 != S2 \land false = false
  E = false
  // (3): S1 != S2 \land E = false
  // (4): S1 = S2 <=> E = true
else
  // (3c): (2) \land X = /\ \land Y = /\
  // (4): S1 = S2 <=> E = true
// (4): S1 = S2 <=> E = true
return E

```

Above, we used weakening, so we are left with proving:

* $3a\implies 3b$. By contradiction, assume $\lnot 3b:\ S\_1=S\_2$ and $3a$. Since $S\_1=S\_2$, then by $2$ (part of $3a$) we have that $X=Y \land E=true$. We also know that at least one of $X,Y$ is not empty from $3a$, hence both are not empty since they are equal. This contradicts the last part of $2$, namely $\lnot(X\neq\Lambda \land Y\neq\Lambda \land E=true)$.
* $3 \implies 4$. Two truths are always equivalent.
* $3c \implies 4$. Replacing both $X,Y$ in $2$ with $\Lambda$, the first part of property $2$ immediately simplifies into $4$.

The first item can also be proved more formally, but I think you get the idea.

---

About your attempt: you used the equivalence

$$ \begin{array}{l} \big((S\_1 = S\_2 \iff X = Y \land E = true) \land (X = \Lambda)\big) \\ \equiv (S\_1 = S\_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \end{array} $$

However, this does not hold in general, e.g. for $X={\sf x}, Y={\sf y}, S\_1=\Lambda, S\_2={\sf h}, E=true$. Or, more in general, when $X$ is non empty, and $S\_1\neq S\_2$. In such case, the former is false, but the latter is true.
> 3 votes

---
Tags: logic, loop-invariants, hoare-logic
---


title: Reduction of the Y combinator

text:
# Question
Title: Reduction of the Y combinator
The Y combinator expression is as follows: $$ Y \equiv \lambda f .(\lambda x .f(xx) )) .(\lambda x .f(xx) ) $$

Now , if I am not wrong , then this expression can be reduced by seeing this as the argument: $ .(\lambda x .f(xx))$ hence would lead to the consumption of first bound variable giving: $$ (\lambda x .\lambda x .f(xx) (xx))$$

which is equivalent to $ \lambda xx .f(xx) (xx)$

which will yield $ f(xx) $.

But in my book I don't find the Y combinator being reduced to this and it made me feel that something is fishy with the reduction that I am doing .

Is there any mistake in this?

# Answer
> 6 votes
You've misread the definition of $Y$. $(\lambda x.f(xx))) (\lambda x.f(xx))$ is the body of the function. You can put an additional pair of parentheses in the definition: $$ Y = \lambda f. \color{red}{\mathbf{(}} (\lambda x.f(xx))) (\lambda x.f(xx)) \color{red}{\mathbf{)}}$$ Beware that different authors use different conventions for parentheses. But under the most common convention, $\lambda$ has lower precedence than application, so the body of a lambda goes until the next enclosing closing parenthesis. If a text uses a different convention, make sure to put parentheses accordingly.

You can reduce $Y$, but the argument $(\lambda x.f(xx)))$ is applied to $(\lambda x.f(xx))$. The $\lambda f. \ldots$ doesn't change since it isn't applied to anything. $$\begin{align} Y \\;\\; = \\; & \lambda f. (\lambda \color{magenta}{x}.f(\color{magenta}{x}\color{magenta}{x}))) \color{magenta}{(\lambda x.f(xx)))} \\ \rightarrow\_\beta \\; & \lambda f. f \left( (\lambda x.f(xx))) (\lambda x.f(xx))) \right) \\ \end{align}$$ Let $\Omega\_f = (\lambda x.f(xx)) (\lambda x.f(xx))$, so that $Y = \lambda f. \Omega\_f$. The reduction above is $\lambda f. \Omega\_f \rightarrow\_\beta \lambda f. f \Omega\_f$. That's $\Omega\_f \rightarrow\_\beta f \Omega\_f$ under the context $\lambda f. \[\]$. There's an infinite chain of reductions $$ Y = \lambda f. \Omega\_f \rightarrow\_\beta \lambda f. f \Omega\_f \rightarrow\_\beta \lambda f. f (f \Omega\_f) \rightarrow\_\beta \lambda f. f (f (f \Omega\_f)) \rightarrow\_\beta \ldots $$ This is how the recursion combinator works. But this won't do anything “useful” until $f$ is replaced by a lambda so that the $f \Omega\_f$ part can be reduced.

If you apply $Y$ to a function $g$, a redex appears at the top level. $$ \begin{align} Y g \\;\\; = \\;\\; & \left( \color{green}{\lambda f}. (\lambda x.\color{green}{f}(xx))) (\lambda x.\color{green}{f}(xx)) \right) \color{green}{g} \\ \rightarrow\_\beta \\; & (\color{darkblue}{\lambda x}. g(\color{darkblue}{x} \color{darkblue}{x})) \color{darkblue}{(\lambda x. g(x x))} \\ \rightarrow\_\beta \\; & g \left( (\lambda x. g(x x)) (\lambda x. g(x x)) \right) \\ \leftarrow\_\beta \\; & g \left( \left( \color{brown}{\lambda f}. (\lambda x. \color{brown}{f}(x x)) (\lambda x. \color{brown}{f}(x x)) \right) \color{brown}{g} \right) \\ = \\; & g (Y g) \end{align}$$

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: Given a set of n balls with different weights and a scale that compares two balls
Write an algorithm to determine if there's a set of \> n/4 balls of the same weight. The algorithm cannot exceed O(n log n) time.

One way I was thinking about this was using divide and conquer. My original algorithm was as follows:

```
findSet(S) #S is the set of n balls
    If |S| = 1, return the lone ball
    If |S| = 2 or 3, return any ball
    Divide S up into 4 subsets of equal length, run findSet on each
    If no run returns a ball, return nothing
    If a single test returns a ball, weigh the ball against all other balls
      in S. If we generate a set of balls > n/4, return the ball

    If >=2 tests return balls, let B denote the set of these balls.
    For each ball b in B, weight b against all elements in B.
      If we generate a set of balls > n/4, return the corresponding b.

```

I think the algorithm is O(n) because the recurrence would be T(n) = 4T(n/4) + n which can be reduced to O(n log4 n). However, I'm pretty sure this algorithm is incorrect. Primarily, I'm not sure if the base cases will ensure we choose a ball b that is \> n/4 in the original set.

# Answer
Assume you have a sorted array of all weights. If any such element existed then more than %25 of that array had to be occupied with that element. Then either element at %25 marker, %50 marker and %75 marker has to contain such element. So we have 3 candidates but no such sorted array. Assume N is divisible by 4 below. There might some tweaks to be done for edge cases which can be handled.

1. Do Worst-Case Linear-Time Selection to find the median of the entire array.
2. Create two arrays of size |N / 2| both. For the first one but everything smaller than the median. For the second one put everything that is larger. If either of the arrays or not full pad the array with the median element. Then find the median of both of these arrays as mentioned in step 1.
3. We have 3 candidates. For each candidate count how many of them have equal weight. If any has counter more than |N / 4| output this element.

Runtime: Each step is linear with respect to input. We iterate over the entire balls multiple times but still it is O(N).

Problem with the proposed algorithm is mainly the probable imbalance of the random partitions of the set
> 2 votes

---
Tags: algorithms
---


# Question
Title: Thompson Regular Expression Search Algorithm 3rd Stage
My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows:

1. Check that the RE is syntactically correct
2. Convert RE to reverse polish form

The paper states "the third stage is at its heart a pushdown stack." I don't get what that means.

It seamlessly walks us through pushing and popping off the stack to translate the RE $a(b|c)^\*d$ with CNODES and NNODES.

But what is this for? I know that the purpose of the algorithm is to find all substrings in a given text that match the given RE, but I don't see how the third stage achieves this.

# Answer
Let's take the example from the paper: $a(b|c)^\*d$. This is first translated into RPN: "$abc|\*.d.$". This is compiled into (essentially) an NFA by using a stack. Upon reading a symbol $\sigma$, we push to the stack an NFA for $\sigma$, which we will denote by $N(\sigma)$. Upon reading $\*$, we pop an NFA $N(r)$ for the regular expression $r$ from the stack and push $N(r^\*)$, an NFA for $r^\*$. Upon reading a binary operand $\circ$, we pop two NFAs $N(r\_1),N(r\_2)$ and push $N(r\_1 \circ r\_2)$, an NFA for $r\_1 \circ r\_2$.

Here are the different stages. At each stage, we underline the character being processed, and the resulting stack after processing it, where the top-of-stack is to the right:

1. $abc|\*.d. \qquad $ (empty)
2. $\underline{a}bc|\*.d. \qquad N(a)$
3. $a\underline{b}c|\*.d. \qquad N(a) N(b)$
4. $ab\underline{c}|\*.d. \qquad N(a) N(b) N(c)$
5. $abc\underline{|}\*.d. \qquad N(a) N(b|c)$
6. $abc|\\!\underline{\*}.d. \qquad N(a) N((b|c)^\*)$
7. $abc|\*\underline{.}d. \qquad N(a(b|c)^\*)$
8. $abc|\*.\underline{d}. \qquad N(a(b|c)^\*) N(d)$
9. $abc|\*.d\underline{.} \qquad N(a(b|c)^\*d)$

Nowadays the regular expression will be parsed into a tree, and the translation process will proceed recursively. If the tree is processed in the correct order (DFS), then this would be completely equivalent to the algorithm described by Thompson.

Either way, having constructed an NFA for the input regular expression, we run it on the input text. This is the part in which we actually search the input text.
> 1 votes

---
Tags: formal-languages, regular-expressions, search-algorithms, compilers
---


# Question
Title: Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither
where $L\_{1} \cup L\_{2} \cup L\_{3} = \sum^{\*}$ and

$L\_{1} \cap L\_{2} = \emptyset$ and $L\_{2} \cap L\_{3} = \emptyset$ and $L\_{1} \cap L\_{3} = \emptyset$

is it possible that $L\_{1}$ is decidable, $L\_{2}$ is recognizable but not decidable

and $L\_{3}$ is not recognizable?

If so please give an example, if not why?

By recognizable I mean Turing Recognizable.

To make things a little easier (I think!) I have reached a conclusion that it is very much possible, I only can't think of an example of such 3 languages.

# Answer
> 2 votes
Is is indeed possible.

Consider the halting problem set $$H = \big\\{ \big(\langle M \rangle, w\big): M \big( w \big) \space halts \big\\}$$

and its complement $$\overline{H} = \big\\{ \big(\langle M \rangle, w\big): M \big( w \big) \space doesn't \space halt \big\\}$$

We know that **H** is recognizable and not decidable. That means that **$$\overline{H}$$** is not recognizable because, otherwise, **H** would be decidable.

Now take $$L\_1 = \emptyset \space \big( decidable \big) $$ $$L\_2 = H \space \big( recognizable \space and \space not \space decidable \big) $$ $$L\_3 = \overline{H} \space \big( not \space recognizable \big)$$

We have that $$L\_1 \cup L\_2 \cup L\_3 = \Sigma^\*$$ and $$L\_1 \cap L\_2 = L\_2 \cap L\_3 = L\_1 \cap L\_3 = \emptyset$$

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


# Question
Title: How to find an arrangement of a sequence that has the lowest cost
Given is a set of $n$ items: $x\_1, x\_2\ldots, x\_n$. Additionally, we have a non-symmetrical evaluation function $f(x\_i, x\_j)$ that gives a cost value of two items. Note that $f(x\_i, x\_j)\neq f(x\_j, x\_i)$.

We want to find a list $y$ containing all items from $x$ exactly once such that the total cost of $y$, given by $F(y) = \sum\_{i=1}^{n-1} f(x\_i,x\_{i+1})$, is minimal.

How can we do this?

# Answer
> 2 votes
Unfortunately, this problem is NP-hard, which can be seen by transforming it into a question on graphs.

To see this, construct the graph $G=(V,E)$ with $V=\\{x\_1,x\_2,\ldots,x\_n\\}$, $(v,w)\in E$ for all $v,w\in V$ and a cost function $c:E\rightarrow \mathbb{R}$ given by $c((x\_i,x\_j)) : =f(x\_i,x\_j)$. Observe that any path visiting all vertices in $V$ exactly once corresponds uniquely to an arrangement of the original set.

To show NP-hardness, we must first formulate a decision problem corresponding to the optimization problem. One such formulation is:

> Given set $X$ of $n$ items and function $f:X\times X\rightarrow \mathbb{R}$ and an integer $T$, does there exist an arrangement such that the total cost of the arrangement is at most $T$?

By our discussion above, this problem is equivalent to

> Given the full graph $G=(V,E)$ (i.e. $E=V\times V$) of $n$ vertices and cost function $c:E\rightarrow \mathbb{R}$ and an integer $T$, does there exist an Hamiltonian path such that the total cost of the edges of this path is at most $T$?

This problem is very similar to the traveling salesman problem (TSP), but isn't quite the same, as that problem requires a Hamiltonian *cycle* instead of a *path*.

However, as @j\_random\_hacker mentioned, this problem is in fact equivalent to the TSP problem on a different graph, namely $G'=(V',E')$ with $V' = V\cup \\{z\\}$, $E'=V'\times V'$ and $c'$ such that $c'(x,y)=c(x,y)$ for all $x,y\in V$ and $c(z,x)=c(x,z)=0$ for all $x\in V'$.

Therefore, the arrangement problem is indeed equivalent to TSP, which is NP-hard.

---

Although NP-hardness means that there are no efficient algorithms to find an exact solution, there are still heuristics that can find decent solution in reasonable time. There are many such approaches for the TSP problem.

The fact that we know that $f$ is 'fully' non-symmetric doesn't really help, it has the same use as knowing there is no guarantee for symmetry here, which only means *some* approaches won't work.

---
Tags: algorithms, optimization
---


# Question
Title: extend ECMAScript by adding new keywords and syntax
I would like to extend ECMAScript by adding new keywords and syntax to it, for example:

|variableName| stipulates a special kind of variable which I would like to be able to include in a normal ECMAScript line of code, for example:

```
|variable1| = 1 + 1
|variable1| = |variable2|.length - 3

```

a more complex one would be:

```
@SpecialObject[propertName:propertyValue,..., propertyNameN:propertyValueN] {
    {|variable1| == true} => {
        console.log("condition 1 applies")
        |variable1| = false
    }
    .
    .
    .
    {|variable2|.length !== 0} => {
        console.log("variable 2 contains elements")
        |variable2| = Date.now()
    }
}

```

I have built an initial prototype by impementing my own lexer and parser (using Chevrotain), but it is quite limited as it only supports those specific constructs of my new syntax, **what I would like to do is to make it more powerful by being able to include ECMAScript code in my syntax, how could it be done?**

# Answer
> 2 votes
I know of two plausible approaches:

One approach is to start with a lexer and parser for ECMAScript and modify them.

Another approach is to build your own preprocessor that takes as input a program with your syntax, and transforms it to EMCAScript which can be accepted by an existing interpreter (by replacing instances of `|variable|` with something that does fall within the normal ECMAScript syntax). Since you haven't told us anything about the semantics of the `|variable|` syntax, I can't make any suggestions for a specific transformation to apply, but you might be able to work one out.

---
Tags: programming-languages, parsers, language-design
---


# Question
Title: find an element in array that appeared at least 51% times
Given an array with n rational numbers, element in is array called popular if it have appeared at least in 51% of the indices.

I have to design an algorithm that finds such element in O(n) worst case complexity time, that if there is one.

The only ideas I have is to use hash tables but the complexity time is O(n) in average and counting sort but it only works with natural numbers.

Is there anything I am missing or I can use ?

# Answer
If element appears more than 50% of time, you can use Median of medians algorithm by Blum et. al. It is not deterministic though.

Or use specialized algorithm by Boyer and Moore called "Majority vote algorithm". It works by keeping counters of seen element, incrementing on the same symbol and decrementing otherwise. If counter drops to zero, the next symbol is picked.

The trick is that number of increments (and decrements for other symbols) will leave the most frequent item at the end. The second pass is required, because algorithm always terminates with some symbol, which is either the most frequent symbol or some random one (if the most frequent item - the mode - occurs below 50%, there is no guarantee it will be returned).

Here is old-school animation of the majority vote algorithm at authors webpage.
> 5 votes

# Answer
step 1: find the median: O(n)
step 2: count number of occurrence of the median value, O(n)

If a number appears more than 50%, it must be the popular element.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Will Java's hashCode() reduce collisions regardless of table size?
for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions resulting from a poor hashing function.

Do I have to create a poor hashing function to demonstrate the effects of table sizes on collision? Right now I am using Java's native hashCode() method as the key and am passing it into a hashing function to get the index. I passed the generated hashCode into variations of hashing functions, but found no difference in # of collisions between prime/non-prime table sizes.

```
//Hashing function
    scale = rand.nextInt(prime−1) + 1;
    shift = rand.nextInt(prime);
    private int hashValue(K key) {
                return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) }

```

I also implemented quadratic probing, but my book says it should result in more collisions if the table size is non-prime.. I would really appreciate your advice.

# Answer
Java's default implementation for `hashCode()` is probably doing quite a good job. If you were designing (or implementing) a language then you'd want to design your hashing function perform well. So yes, you should be generating your own hash codes.

If hash codes are more-or-less random (as they should be) then table size does not matter at all. Table size only starts to matter when the hash function is poor.

Suppose that, by some fluke, your hash function only output even numbers. Then, if the table size also were even, you'd only ever use half of the slots in your table (the even ones) - more than doubling the collision rate.

Now suppose that, all hash codes are $1$ modulo $3$. If your table size is a multiple of three, then you'd only ever use slots that are $1$ modulo $3$, cutting the effective size of your table by third.

The reason you want to pick a prime as table size is that this avoids any issues with poor hash functions (unless your hash codes all happen to be the same modulo that prime). On the other hand, picking $223092870$ as table size is a terrible idea.
> 1 votes

---
Tags: hash
---


title: XOR of two NP-Complete languages

text:
# Question
Title: XOR of two NP-Complete languages
Given two NP-Complete languages A and B, show that the language:

$L = A\bigoplus B =\\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\\}$

is not necessarily NP-Complete.

Remember $a\bigoplus b$ when $|a|=|b|$ gives 0 when they have the same digit and 1 otherwise.

Example: 0110$\bigoplus$ 0101 = 0011

I have tried to solve this in my exam only was not so accurate..Help needed.

# Answer
$A\bigoplus B$ can be empty (and thus definitely not $NP$-complete) if we pick $A$ and $B$ carefully. For instance, if all strings in $A$ have even length and all strings in $B$ have odd length then $A\bigoplus B$ is empty.

It is fairly easy to modify any $NP$-complete language $L$ to have either only even (resp., odd) strings: let $L'$ be the language consisting of strings formed by prepending $1$ to any odd (resp., even) length string from $L$ and prepending $01$ to any even (resp., odd) length string from $L$.

Note that we can easily recover the original language $L$ from $L'$ by noting that any string that was originally of odd length starts with a $1$ (and thus we must drop the first character), and any string that was originally of even length starts with $01$ (and thus we must drop the first two characters).
> 4 votes

# Answer
First, notice that $A \oplus B = A \space \Delta \space B = \big( A \space \backslash \space B \big) \cup \big(B \space \backslash \space A \big)$.

To prove that it is not always the case that$\space A \space \oplus \space B \in NP-COMPLETE \space$ you only need to provide one example that falsifies the statement.

Take $A = B = SAT \in NP-COMPLETE$. Then $A \oplus B = \emptyset \notin NP-COMPLETE.$
> -1 votes

---
Tags: complexity-theory, time-complexity, np-complete, closure-properties
---


# Question
Title: How to check if a specific ILP problem can be solved in polynomial time or not?
How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?

# Answer
First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a *class* of problem instances. It makes no sense to speak of polynomial time for a *single* problem as any single problem can be solved in $O(1)$!

That said, there is a notable class of ILP's that is known to be polynomial time solvable. This class consists of the ILP's that can be described with a *totally unimodular matrix* (or equivalently, if the solution space is an integral polyhedron). This property guarantees that the relaxed version of the ILP has in fact the same solution as the original ILP!

However, this doesn't mean that there aren't other classes of ILP's for which there exists an algorithm that can solve them in polynomial time (In fact, as it is *possible* that P=NP, it is possible that the class of all ILP's is solveable in polynomial time!)

So, in general, a complete answer to your question is beyond the current state of science, but there are special cases where can say that it is poly-time solvable. However, we cannot say for sure that there even exist classes that are not.
> 7 votes

# Answer
There are instances of size n that can be solved in time $t ≤ 2n+2$, $t ≤ (2n+2)^2$, $t ≤ (2n+2)^3$, $t ≤ (2n+2)^4$ etc. *Every* instance can be solved in $t ≤ (2n+2)^k$ if we pick k large enough for that instance.

Let $I\_k$ be the class of all instances that can be solved in $t ≤ (2n+2)^k$, where n is the instance size. Then each class $I\_k$ can be solved in polynomial time. And since the union of all classes $I\_k$ covers all instances, each instance can be solved "in polynomial time".

That's true for any problem that can be solved. It just means that asking if one particular instance can be solved "in polynomial time" doesn't make much sense.

Now you can of course take any k-th degree polynomial $P\_k (n)$, an algorithm to solve ILP, and for every instance I check if the algorithm solves I in $P\_k(n)$ where n is the size of I by just running the algorithm until either a solution is found or $P\_k(n)$ has been spent. Again, not very valuable.
> 0 votes

---
Tags: discrete-mathematics, linear-programming, integer-programming
---


title: Updation in log n

text:
# Question
Title: Updation in log n
I am working on a problem where I need to binary search on a given array and there can be updates for a given index. As the updates can occur frequently, I need to do it as efficiently as possible. Could you please suggest an appropriate data structure which would update the element in O(log n) and allow me to perform binary search on the array as well? The constant time update (updating by index) won't work as after each update, I have to sort the elements again in order to be able to perform binary search on it later, which would take the complexity to O(nlogn) for each update.

# Answer
If you use any balanced binary search tree data structure, each read and update can be done in $O(\log n)$ time. Binary search can also be done in $O(\log n)$ time -- it is just a read (search) operation in the tree.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Classical set theory and the existence of at least one set
As a student of mathematics I used to accept the argument that the existence of the empty set followed from the axiom schema of comprehension, so long as we could prove the existence of at least one set: if `a` is any set, then we can derive the existence of `{x:a | bot }`. I would then argue using the axiom of infinity that the existence of at least one set was established.

Having drifted towards logic and computer science it now seems to me that the existence of at least one set can be derived simply from the deductive system being used, without additional set theoretic axiom.

This is slightly disappointing to me, as I would have liked the existence of at least one set to be a consequence of set theoretic axioms, not a logical consequence of a deductive system. Of course, there are many reasonable deductive system of first order logic we could consider, and it may be that I am looking at the wrong one, which motivates my question.

**I am hoping that someone will confirm that the existence of at least one set is indeed a logical consequence (not a set theoretic consequence)**, or explain the flaws in the forthcoming reasoning, or point to a deductive system where the statement does not hold.

In order to spell out the deductive system I have in mind, let us consider the language where primitive propositions are of the form `x in y` (where `x` and `y`lie in a suitably large set of variables) and `bot`, and we have an implication `->` as well as quantification `Ax` for every variable `x`. This language can be represented by the Haskell type:

```
data Expr v  = In v v
             | Bot
             | Imply (Expr v) (Expr v)
             | Forall v (Expr v)

```

or for those who prefer coq:

```
Inductive Expr (v:Type) : Type :=
| In    : v -> v -> Expr v
| Bot   : Expr v
| Imply : Expr v -> Expr v -> Expr v
| Forall: v -> Expr v -> Expr v
.

```

There is nothing else in the language (no constant, no equality). Although ordinary mathematics usually involves a far richer language, the hope is that everything can be desugared in terms of this core language.

Now the deductive system I have in mind is a Hilbert style system with 5 axiom schema and 2 rules of inference (modus ponens and generalization).

```
(i)     p -> (q -> p)
(ii)    [p -> (q -> r)] -> [(p -> q) -> (p -> r)]
(iii)   [(p -> bot) -> bot] -> p                   (classical mathematics)
(iv)    [Ax.(p -> q)] -> (p -> Ax.q)   (x not free in p)
(v)     Ax.p -> p[y/x]                 (y free for x in p)

```

Given our rules of inference, we can formally represent our proofs as derivation trees, or specifically as the Haskell inductive data type:

```
data Proof v  = Axiom (Expr v)
              | Hypothesis (Expr v)
              | ModusPonens (Proof v) (Proof v)
              | Generalize v (Proof v)

```

and we crucially have a map `eval :: Proof v -> Expr v` which acts as a sort of type checker, returning the proposition (the type) actually being proved by the proof (the expression). Now of course, not every proof is valid (for example the proof `Axiom p` is not a valid axiom invocation unless `p` is indeed an axiom) in which case the `eval` function can simply return `bot -> bot` which is a convenient way to state that an invalid proof does not prove anything. When implementing the function `eval` (which amounts to spelling out our deductive system), we shall need `isAxiom :: Expr v -> Bool` as well as `Hyp :: Proof v -> [Expr v]` (which returns the list of hypothesis involved in a proof). The function `Hyp` is useful to decide whether the proof `Generalize x P` is valid, by checking that `x` is not free in any of the propositions of `Hyp P`. A proof `P = ModusPonens P1 P2` is not valid unless `eval P2` is of the form `eval P1 -> p` in which case `eval P = p`.

Having described our proofs, we can define the sequent `G |- p` as equivalent to the existence of a proof `P` such that `eval P = p` and `Hyp P <= G` (where the `<=` is set inclusion and lists are viewed as sets)

Ok so at this stage we have a reasonable outline of a reasonable deductive system for first order logic and set theory. Now, if `p` is a proposition without any free variable then `Ax.p` and `p` are provably equivalent for any variable `x` (`Ax.p -> p` is an axiom, while `p -> Ax.p` is not hard to prove), and if we consider the existence statement `Ex.(bot -> bot)` as syntactic sugar for `~Ax.~(bot->bot)` where `~p` is syntactic sugar for `p -> bot`, then the existence of at least one set is equivalent to `[Ax.((bot -> bot) -> bot)] -> bot` which is equivalent to `((bot -> bot) -> bot)-> bot` which is itself provable. **So the existence of at least one set is a logical consequence, not a set theoretic one.**

Going back to the comprehension axiom schema, we have:

```
Aa.Eb.Ax[x in b <-> bot]     (*)

```

where it is understood that `p <-> q` is syntactic sugar for `(p -> q) /\ (q -> p)` while `p /\ q` is syntactic sugar for `~ (~p \/ ~q)` and `p \/ q` is syntactic sugar for `~p -> q`. Since `Eb.Ax[x in b <-> bot]` has no free variable, it is equivalent to (\*) and so we have the theorem: `Eb.Ax[~ x in b]`, **i.e. we are able to prove the existence of the empty set solely from the comprehension axiom schema and nothing else (beyond logic).**

# Answer
It seems that you haven't drifted enough to computer science yet: you're still using untyped quantifiers. The crux of your argument is

> `Ax.p -> p` is an axiom

Indeed, that's axiom `(v)` with a `p` such that `x` is not free in `p`. You can define any axiom you like, but what does this axiom mean? In the case where `x` is not free in `p`, combined with the axioms of classical logic, *it means that there is at least one set*. As chi notes, you can instantiate `(v)` with `p = bot`, which gives `(Ax.bot) -> bot`. By the classical definition of the existential quantifier, this is equivalent to `~(Ax.bot) = Ex.~bot = Ex.True`.

If you take the view of a typical mathematical logician, then this axiom is perfectly fine — because mathematical logicians are not interested in empty models!

But if you take the point of view of constructive logic, your axiom is wrong. Not wrong in the sense that it makes the theory inconsistent — after all, it's valid in set theory and set theory isn't inconsistent that we know of — but wrong in the sense that it does not correspond to the proof calculation rule.

Let's write `(v)` in Coq syntax:

```
          A : T
-------------------------
(forall x:T. P) -> P[A/x]

```

Note the premise `A : T`. This is the axiom for forall elimination, and it requires a value of the type that's quantified over. You can only find such a value in an empty environment if the type is non-empty. In other words, this axiom will only let you prove that there exists a set if the domain of sets is not empty.
> 3 votes

---
Tags: logic, first-order-logic
---