# Question
Title: A Question about a Question related to Graph Theory and Maximum Flow
The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob

# Answer
> -1 votes
It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow. Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird. Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow). Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.

---
Tags: graphs
---


# Question
Title: Determine if a line going through n rectangles exists
I guess this is kinda like asking if 3 (or more) rectangles are collinear.

The question is, given n rectangles on the 2D plane (given as the rectangle's top-left corner coordinates and it's width/height), does there exist a line that goes through all of them?

Notes:

* The rectangles' sides are perpendicular or parallel to the axes. So basically, none of the rectangle sides are slanted.
* Rectangles themselves can intersect
* Does not actually need to produce the line equation

I've been thinking through this for a good portion of today, and can't figure out (or find online) an answer. I keep finding edge cases and can't figure out a guaranteed method. The line of best fit for the mid-point or the corners of all n rectangles seem like a good heuristic for a line, should one exist, but I don't think it always works.

The corners of the rectangles seem like good starting points to determine the extreme slopes of a potential line, but it's still unclear to me how i'd use them to determine if a line exists for all n rectangles. I also know how I'd do this intuitively IRL, but not sure how to turn it into an algorithm.

Visual Example for 4 rectangles:

# Answer
> 2 votes
There is a line through the four rectangles if and only if you can pick one edge from each rectangle such that the line intersects each of those four edges -- or equivalently, if there is a point on each of those edges such that the resulting four points are colinear. So a plausible algorithm is to enumerate all $4^4$ ways to choose one edge from each rectangle; then check whether there exists a line that goes through those four edges.

How do we do the latter test? Let's suppose the endpoints of the first edge are the two points $P',P''$ (i.e., these are two adjacent corners of the first rectangle). Then any point $P$ on that edge can be expressed as $P = (1-\alpha) P' + \alpha P''$ for some $0 \le \alpha \le 1$. Similarly, we can express any point $Q$ on the second edge as $Q = (1-\beta) Q' + \beta Q''$ where $Q',Q''$ are the endpoints of the second edge, and similarly for the two remaining points $R,S$ on the two remaining edges.

We can express algebraically the condition that $P,Q,R$ are colinear (on the same line). Let $P\_x$ be the x-coordinate of the point $P$, and $P\_y$ be its y-coordinate. Then $P,Q,R$ are colinear iff

$$(Q\_x-P\_x)(R\_y-P\_y) = (Q\_y-P\_y)(R\_x-P\_x).$$

We can plug in $Q\_x = (1-\beta)Q'\_x + \beta Q''\_x$, and so on, to get an equation in terms of the three $\alpha,\beta,\gamma$ unknowns. Similarly, the condition that $P,Q,S$ are colinear can be expressed as an equation in terms of $\alpha,\beta,\delta$. Now there exists a linear through these four edges iff there exists a common solution to these two equations such that $0 \le \alpha,\beta,\gamma,\delta \le 1$. This reduces the problem to solving two quadratic equations over four real unknowns. Now you can apply standard methods for solving such equations to determine whether a simultaneous solution exists.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Do all the cells in a recurrent neural network share learned parameters?
Most descriptions of modern RNNs present a "folded" characterisation, that is to say, a single cell with a loop back to itself transmitting the hidden state from one step to the next. However, in implementations the RNN is computed "unfolded", so a new cell is created for every step of the sequence up to some maximum sequence length, and the state is passed from one cell to the next.

My question is: are the learned parameters shared between all the cells in the unfolded sequence? E.g. in the case of a stack of LSTMs, does each LSTM have its own set of forget, input-gate, candidate and output parameters, or does the whole stack share and update a common set?

# Answer
> 1 votes
Indeed, the copies of a cell in an unfolded version share their learning parameters.

Why is it done this way? If the sequence processed by the LSTM is always the same lenght, we could conceivably get a better result with different parameters, but there are two key caveats:

1. Shared parameters are faster to learn
2. We want to be able to process cases when the lenght of the sequence processed is not fixed!

---
Tags: machine-learning, neural-networks
---


# Question
Title: Time complexity of euler totient function
Code for finding $\phi$(n) is

```
int phi(int n)
    {
        int result = n;   // Initialize result as n

        // Consider all prime factors of n and subtract their
        // multiples from result
        for (int p=2; p*p<=n; ++p)
        {
            // Check if p is a prime factor.
            if (n % p == 0)
            {
                // If yes, then update n and result
                while (n % p == 0)
                    n /= p;
                result -= result / p;
            }
        }

        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (n > 1)
            result -= result / n;
        return result;
    }

```

I don't understand how is the overall complexity $O(\sqrt{n}) $.

From the code, I see that the outer loop runs for $O(\sqrt{n}) $ time but I am not sure of how to include the time complexity of the inner loop for finding the overall complexity.

If we have n=$128$, then outer loop runs for $O(\sqrt{n}) $ time and inner loop for $O(log\_2 n)$, so overall complexity is $O(\sqrt{n}) $ + $O(log\_2 n)$ which is $O(\sqrt{n}) $.

I don't know how to extend this for general case of $n=P1^{a1}\*P2^{a2}\*P3^{a3}\*..Pn^{an}$

# Answer
The cost inner loop if $n$ is equal to $P\_1^{a\_1}P\_2^{a\_2}\cdots P\_k^{a\_k}$, should be run in $\log\_{P\_1}n + \log\_{P\_2}n + \cdots + \log\_{P\_k}n$ totaly which is $O(k\log(n))$.Notice that, these computation is computed over the outer loop and summation of all iterations of the outer loop.

To more scrutinizing, as the maximum asymptotic number of primes less than $x$ is $\frac{x}{\log x}$, size of $k$ would be $O(\frac{\sqrt{n}}{\log\sqrt{n}})$. Hence, The complexity of the problem would be: $$O(\sqrt{n} + k\log(n))=O(\sqrt{n} + \frac{\sqrt{n}}{\log\sqrt{n}}\log(n)) = O(\sqrt{n}+\frac{\sqrt{n}}{2})=O(\sqrt{n})$$
> 2 votes

# Answer
Whenever you find a factor, n gets smaller. The amount of work needed to process one factor is trivial compared to the savings you get by dividing n by that factor.
> 0 votes

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


# Question
Title: Minimal DFA with more states than its equivalent NFA
I understand that using a bad case for subset construction as provided through an example in the book - Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $n+1$ states, and get a corresponding minimal DFA with $2^n$ states due to the power set logic.

But, my question is, is there a case where you can have an NFA (with or without epsilon moves), with $n$ states, having an equivalent minimal DFA of $p$ states, where $p \neq 2^n \ and \ p \> 2n$ ?

# Answer
> 0 votes
I happened to find an example, with lots of trial and error throughout the day, where p = 12 and n = 5. You can take a look below. Although the Minimal DFA turned out a bit messy. Will update this answer incase I find a generic idea on how to come up with such examples, or an intuition behind this idea.

# Answer
> 1 votes
Consider the language $(0+1)^\*0(0+1)^{n-1}$ over the alphabet $\\{0,1,2\\}$. It is accepted by an NFA having $n+1$ states, and its minimal DFA contains $2^n+1$ states.

# Answer
> 0 votes
Yes there is. When converting an NFA with $n$ states to a DFA you are going to have more states in the DFA then you did in the NFA but typical the DFA has less than $2^n$ states.

Consider the NFA the accepts the strings $\\{aaa,aab\\}$. If you convert that NFA to a DFA you will find that the DFA has less than 8 states.

---
Tags: automata, finite-automata, nondeterminism, simulation
---


# Question
Title: Algorithms - In which relation to the big O notation are the functions lg n and ln n?
I want to prove in which relation the two functions stand to each other with the help of a proof. But how?

# Answer
Hint: for $a,b\>0$ we have $\log\_an=(\log\_ab)(\log\_bn)$.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Understanding Applicative Evaluation Order with the Z-Combinator
I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this.

So I know Python's evaluation order is applicative. But I seem to be overlooking something in how applicative order works. To compensate for applicative evaluation order I reasoned to build a Y-combinator that does not dive off into infinite recursion it would be sufficient to write it like this:

```
Y = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x)))

```

I arrived at this conclusion by first manually deriving `Y g` like so

```
Y g =  (lambda f : (lambda x : f(x x)) (lambda x : f(x x))) g      # Definition of Y
    -> (lambda x : g(x x)) (lambda x : g(x x))                   # beta reduction
    -> g((lambda x : g(x x)) (lambda x : g(x x)))                # beta reduction
    -> g((lambda f : (lambda x : f(x x)) (lambda x : f(x x))) g) # lambda abstraction
    =  g(Y g)                                                    # put in Y

```

And then working my way backwards like this, adding in a lambda abstraction hat would delay the recursion until a value is passed in:

```
    = g(lambda z : Y g z)
    =  g(lambda z : (lambda f (lambda x : f(x x)) (lambda x : f(x x))) g z)
    -> g(lambda z : (lambda x : g(x x)) (lambda x : g(x x)) z)
    -> (lambda x : g(lambda z : x x z)) (lambda x : g(x x))
Y g =  (lambda f : (lambda x : f( lambda z : x x z)) (lambda x : f(x x))) g

```

When I manually evaluate `factorial 3` where

```
factorial_ = lambda f : lambda n : 1 if n == 0 else n * f(n-1)

factorial = Y(factorial_)

```

in applicative order I get

```
 factorial 3 =  (lambda n : 1 if n == 0 else n * (lambda z : Y factorial_ z)(n-1)) 3
            -> 3 * (lambda z : Y factorial_ z)(3-1)
            -> 3 * (Y factorial_ 2)
            =  3 * ((lambda n : 1 if n == 0 else n * (lambda z : Y factorial_ z)(n-1)) 2)
            -> 3 * 2 * ((lambda z : Y factorial_ z)(2-1))
            -> 3 * 2 * (Y factorial_ 1)
            =  3 * 2 * ((lambda n : 1 if n == 0 else n * (lambda z : Y factorial_ z)(n-1)) 1)
            -> 3 * 2 * 1 * ((lambda z : Y factorial_ z)(1-1))
            -> 3 * 2 * 1 * (Y factorial_ 0)
            =  3 * 2 * 1 * ((lambda n : 1 if n == 0 else n * (lambda z : Y factorial_ z)(n-1)) 0)
            -> 3 * 2 * 1 * 1
            -> 6

```

But when I run

```
Y = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x)))

factorial_ = lambda f : lambda n : 1 if n == 0 else n * f(n-1)

factorial = Y(factorial_)

print(factorial(3))

```

I still get the infinite recursion problem:

> Y = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x))) \[Previous line repeated 994 more times\] RecursionError: maximum recursion depth exceeded

So I must not actually have performed correct applicative order on my manual derivation, otherwise I would have gotten infinite recursion like Python gets.

What am I missing here about how applicative order works?

# EDIT:

To reiterate:

Let's say I name that version of `Y` `Z'`:

Let $Z' = \lambda f. \lambda x( f ( \lambda z. x x z)) (\lambda x. f( xx))$

Let $F' = \lambda f. \lambda n. 1 \text{ if } n = 0 \text{ else } n\*f(n-1)$ $$ \text{Let } F = Z' F' = (\lambda f . (\lambda x . f( \lambda z . x x z) (\lambda x . f(x x)) F'$$ $$\longrightarrow (\lambda x . F'(\lambda z . x x z)) (\lambda x . F'(x x))$$ $$\longrightarrow F'(\lambda z . (\lambda x . F'(x x)) (\lambda x . F'(x x)) z)$$ Lambda-Abstraction for $F'$
$$= F'(\lambda z . (\lambda f (\lambda x . f(x x)) (\lambda x . f(x x))) F' z)$$ Per definition of $Z'$ $$= F'(\lambda z . Z' F' z)$$

Now applying $F$ to some number:

$$F~ 3 = (\lambda n . 1 \text{ if } n = 0 \text{ else } n * (\lambda z . Z' F' z)(n-1)) 3$$

$$\longrightarrow 3 * (\lambda z . Z' F' z)(3-1) $$

$$\longrightarrow 3 * (Z' F' 2) $$ $$= 3 * ((\lambda n . 1 \text{ if } n = 0 \text{ else } n * (\lambda z . Z' F' z)(n-1)) 2) $$ $$\longrightarrow 3 * 2 * ((\lambda z . Z' F' z)(2-1))$$ $$\longrightarrow 3 * 2 * (Z' F' 1)$$ $$= 3 * 2 * ((\lambda n . 1 \text{ if } n = 0 \text{ else } n * (\lambda z . Z' F' z)(n-1)) 1)$$ $$\longrightarrow 3 * 2 * 1 * ((\lambda z . Z' F' z)(1-1))$$ $$\longrightarrow 3 * 2 * 1 * (Z' F' 0)$$ $$= 3 * 2 * 1 * ((\lambda n . 1 \text{ if } n = 0 \text{ else } n * (\lambda z . Z' F' z)(n-1)) 0)$$ $$\longrightarrow 3 * 2 * 1 * 1$$ $$\longrightarrow 6$$

So, why did this work? It was supposed to go into infinite recursion. What is my mistake?

# Answer
> 2 votes
Let's call your proposal `X`, instead:

```
X = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x)))

```

For convenience, we can rewrite it as

```
M = (lambda x : f(x(x)))    # depends on f
X = lambda f : (lambda x : f( lambda z: x(x) (z) )) M

```

Now, when we invoke `X(f)`, we get

```
X(f) =
(lambda x : f( lambda z: x(x) (z) )) M =
f( lambda z: M(M) (z) )

```

Assume `f` "recurses", invoking its argument with some value, e.g. `5`. Its code might look as

```
c = M(M)(5)
do something with c
return something

```

However, `M(M)` above is exactly the non terminating `Y(f)`. The additional `lambda z:` disappears after the first recursive call.

In order to prevent that, we need to add `lambda z:` inside `M` as well. Hence we get the actual `Z` combinator:

```
Z = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(lambda z: x(x) (z)))

```

---
Tags: computability, lambda-calculus, computation-models, python, evaluation-strategies
---


# Question
Title: Process address space separation in L1 cache of Intel hyperthreaded CPUs
Since a processing core with hyperthreading enabled is presented as two or more cores to the operating system, it can run completely different processes with different, isolated virtual memory spaces. There must be a mechanism that guarantees process address space isolation. How is it done in Intel hyperthreaded CPUs with regards to L1 cache? I can think of three possibilities:

1) virtual-physical address mapping is done before L1 (could add delay to L1);

2) each virtual core has its own L1 cache (costs space on the die);

3) only different threads of the same process are allowed to be hyperthreaded (must be implemented in the OS kernel)

Or is it something completely different?

# Answer
In modern Intel processors, the virtual-physical mapping is done in parallel with the lookup into the L1 cache. There is a trick that gets the effect of doing lookups on virtual addresses, without actually having to complete the virtual-physical mapping before the cache lookup (and thus avoiding the delay you are worried about). See https://stackoverflow.com/q/19039280/781723 and https://software.intel.com/en-us/articles/how-memory-is-accessedfor details of how they make this work.

There is only one L1 cache per physical core. The two virtual cores on the same physical core share the same L1 cache. See, e.g., https://stackoverflow.com/q/27797424/781723 and https://stackoverflow.com/q/32979067/781723.

Different processes can be hyperthreaded on the same physical core.

In general, you can often find answers to these questions by reading the Intel reference manuals.
> 1 votes

---
Tags: computer-architecture, cpu, virtual-memory
---


# Question
Title: Time complexity to check if there is an edge between two nodes in an adjacency list
I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M\[i\]\[j\]$). However, I didn't really get why time complexity in an adjacency list to check would be $O(|V|)$, where $V$ represents the vertices. Shouldn't it be $O(|E|)$ instead? Because in the worst case, it needs to traverse through all of the elements (edges) in a linked list of a certain vertex.

# Answer
> 6 votes
In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices.
Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{adjacent\[u\]}$.
A node can have at most $O(|V|)$ neighbors, from here the complexity follows.

# Answer
> 2 votes
Every vertex at most can have an edge with every other vertex which is $O(|V|)$ elements in the adjacency list per vertex. $|V|$ is just a tighter bound which has to be true due the first claim.

---
Tags: graphs, algorithm-analysis, data-structures, runtime-analysis, lists
---


# Question
Title: Greedy Heuristic for the Traveling Salesperson Problem
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any given point and connect it with the nearest point and then connect that to the next nearest one until all points are covered - then going back to the first point.

Where "P" is the starting and ending point.

The second approach, which gives the optimal answer, is the "closest pair of points" or "Engstes-Paar-Heuristic". I don't understand how this approach works because from the looks of it, you simply make a straight line but I don't understand this approach.

Sorry about the possible name changes, it's originally in German.

# Answer
> 3 votes
First let's name your points $P\_A$, $P\_B$, $P$, $P\_C$, and $P\_D$ (from left to right).

With the first heuristic you start at one point ($P$) and move to the closest point. From that new point, you move to the next closest point, and so on and so forth.

With the second heuristic you again start at one point ($P$) but you move to the point closest to one of the two ends of your current path. It is a simple improvement over the first heuristic.

For your example:

1. Current path: $P$. Closest point to $P$: $P\_B$.
2. Current path: $P-P\_B$. Closest point to $P$ or $P\_B$: $P\_C$.
3. Current path: $P\_B-P-P\_C$. Closest point to $P\_B$ or $P\_C$: $P\_A$.
4. Current path: $P\_A-P\_B-P-P\_C$. Closest point to $P\_A$ or $P\_C$: $P\_D$.
5. Current path: $P\_A-P\_B-P-P\_C-P\_D$. The only choice left is to connect $P\_A$ to $P\_D$.

# Answer
> 1 votes
The example shows the Travelling salesman problem for the case that all points are on a straight line. That’s rarely the case. And you cant just move the points to solve the problem, they are where they are.

The closest pair heuristics seems to be that you find the closest connection and add it, then again the closest connection that is still available and so on.

You can easily show that this is optimal if all the points are on a straight line, but usually it’s not.

---
Tags: algorithms, graphs, computational-geometry, greedy-algorithms, heuristics
---


title: Cost of break statement

text:
# Question
Title: Cost of break statement
i am trying find the Cost of an algorithm. it contains break statements. is there any cost of `break and Continue` statement in a Algorithm?

# Answer
Depends on how close you want to look.

On face value, `break`, `continue`, etc. are implemented by *unconditional jumps*, which are (under most RAM-/CPU-like models) primitive instructions of the machine. So they certainly have some constant cost; $O(1)$ is a valid bound.

That's not very interesting, though: *all* primitive instructions have constant cost. If you want to answer questions like, "can I speed up my algorithm by adding/removing `break`/`continue`?", the situation becomes more involved.

The true cost of jumps depends on many factors, e.g.

* the type of pipeline the CPU uses,
* which type of speculative execution happens (if any),

and so on. My *guess* is that an unconditional jump -- other than *conditional* jumps -- should behave well in many regards. They are most certainly cheaper than completing the loop would be.

If the true cost matters to you, I recommend you benchmark the alternatives at hand. Be aware that the effect you're trying to measure may be smaller than the noise introduced by benchmarking, and you may have to account for that.
> 3 votes

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


# Question
Title: How does the nearest insertion heuristic for TSP work?
In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson Problem".

In it we covered the "Nearest Neighbor", "Closest Pair" and "Insertion" heuristics approach to solve the TSP Problem.

The first two are quite clear - the first one connects the starting point to the nearest neighbor and then connect that to its neighbor and so on. The second one you move to the point closest to one of the two ends of your current path. But I don't understand how the third one actually works.

The example is as follows:

And continue this five more times and you get the answer below.

# Answer
> 3 votes
I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:

1. We're looking to construct a cycle $C$ containing all the nodes of our problem. We will do this by initially constructing a small cycle and slowly adding nodes to it until it contains all the nodes. We start by choosing some starting node $N$ and adding it to $C$. $C$ now contains a single node, $N$.
2. We want to add to $C$ the node which will increase its length the *least*. To do this we need to find which node to add to our cycle and then figure out where in the cycle to put it. We select this node by choosing the node (not in $C$) which is the closest to any node in $C$. We then insert this node between two nodes in $C$ such that the increase in length is minimal. More formally: Let $k$ be the node we selected. Find an edge $(i,j)$ such that $d\_{ik}+d\_{kj}-d\_{ij}$ is minimal.
3. Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.
4. If $C$ contains all the nodes, stop. Otherwise, go to 2.

---
Tags: algorithms, graphs, greedy-algorithms, heuristics
---


# Question
Title: In two sets, identify set of pairs with maximal sum of connections
Given two sets of items

$A = { a\_1, .., a\_N }, B = { b\_1, .., b\_M },$

and assuming a connection weight $w{\_i}\_j \ge 0$ between any possible pair $(a\_i, b\_j)$ that contains one item of each set, how can I identify the set of pairs $S$ that maximizes the sum of all involved weights: $\sum\_{S}w{\_i}\_j$, under the condition that any $a\_i$ and any $b\_j$ occurs maximally once in the new set?

Example: With $A = \[a\_1, a\_2\], B = \[b\_1, b\_2, b\_3\]$, and

$w$'s from $a\_1$ to $B$: $\[5, 2, 1\]$

$w$'s from $a\_2$ to $B$: $\[1, 0.2, 0.4\]$

the solution is to use the pairs: $(a\_1, b\_1), (a\_2, b\_3)$ which result in the highest possible sum $5.4$, and $b\_2$ is left over.

Also, is there a way to approximate the sum e.g. not optimizing further for those $w{\_i}\_j \< threshold$?

I'm sure this problem has a name, but I'm not able to figure it out.

# Answer
This is the assignment problem. There are standard algorithms, such as the "Hungarian algorithm".

If you want to only include edges whose weight is below some threshold, delete those edges first before running the algorithm.
> 1 votes

---
Tags: algorithms, optimization, sorting, sets
---


title: Minimum edge cover with a constraint

text:
# Question
Title: Minimum edge cover with a constraint
An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each vertex is incident to an odd number of edges. Is anything similar studied in Computer Science?

# Answer
There is at most one edge cover which touches each vertex an odd number of times. To see this, let us consider a more general problem, in which each vertex is labeled either "odd" or "even". We want to cover each vertex by an odd or even number of edges, according to its label.

If the tree contains more than one vertex, then we can always find some leaf. It it is labeled "odd", every solution must contain the unique edge containing it. We add this edge to the edge cover, remove the leaf, and modify the label at the other end of the edge accordingly. If the leaf is labeled "even", every solution must not contain the unique edge containing it, and so we simply remove the vertex. Eventually only one vertex will remain. There is a solution if and only if this vertex is labeled "even".
> 2 votes

---
Tags: graphs, trees
---


# Question
Title: Surprisingly high collision rates when hashing a short list with few buckets
I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- it's been a long time since I did this stuff). And the output from the hashing function is an int modulo 4000.

Her naive hash function gets about 1500 collisions. To get something for comparison, I found a handful of hashing functions here and here. I ended up trying almost all of them (oat, fnv, djb, another djb, sax, elf, jsw, and a crc adaptation), because every single one of them got about 1500 collisions. That sure seems like a lot. I'm starting to think maybe we're missing something fundamental. Or not. I don't know.

(I was able to reduce collisions significantly by increasing the number of output buckets to 200k, and returning `hash mod 200k` from the functions. Naturally, this isn't allowed for the assignment.)

I'm not sure what questions to ask, but the first one that comes to mind is, does 1500 collisions sound about right when using such a small number of output buckets? Or does it sound more like we're doing something totally wrong **outside** the hashing function? (Presumably not **inside** it, given that we tried so many different ones.) Or maybe I should ask, is there a way to find out whether 1500 collisions is about right?

# Answer
> 4 votes
Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions. The latter is in close agreement with what you observe, so yes, 1500 collisions looks about right to me.

# Counting collisions pairwise

I think the most natural way to count collisions is "pairwise". For instance, if A, B, and C all hash into the same bucket, let's count that as 3 collisions. If A, B, C, and D hash to the same bucket, let's count that as 6 collisions (not 4, but 6: the 6 collisions are AB, AC, AD, BC, BD, and CD). And so on. In general if there are $k$ items in a bucket, that causes ${k \choose 2}$ collisions, with this method of counting collisions.

Then, you can use linearity of expectation to estimate the number of collisions, assuming the hash function is good. Let $X\_{i,j}$ be an indicator random variable that is $1$ if objects $i,j$ hash to the same bucket, or $0$ otherwise. Let $Y=\sum\_{i\<j} X\_{i,j}$ be the sum of these random variables. Then $Y$ counts the number of collisions.

Can we estimate a typical value for $Y$? Well, we can compute the expected value of $Y$ in a straightforward way:

$$\mathbb{E}\[Y\] = \sum\_{i\<j} \mathbb{E}\[X\_{i,j}\] = \sum\_{i\<j} {1 \over 4000} = {4000 \choose 2} {1 \over 4000} = {3999 \over 2} \approx 2000,$$

using the fact that $\mathbb{E}\[X\_{i,j}\] = \Pr\[X\_{i,j}=1\] = {1 \over 4000}$ since there is a 1 in 4000 chance that object $j$ hashes to the same bucket as object $i$ (assuming a good hash function). Typically, the observed value of $Y$ will be near its expected value. So, that'd predict that you see about 1500 collisions. That's a consequence of the number of buckets and the number of items hashed.

In general, if you hash $n$ items into $m$ buckets using a good hash function, you should expect to see about ${n^2 \over 2m}$ collisions, on average, using this method for counting collisions.

# Counting collisions by bucket size

On reading your comment, it sounds like you are counting collisions differently. If there are $k \ge 1$ items in a bucket, it sounds like you are counting that as $k-1$ collisions. How does that affect things? Well, it makes the calculation more complicated. I'll share a much terser analysis for this case, without showing all the details.

Let $N\_i$ denote the number of items in bucket $i$. If the hash function is good, the number of items in a bucket should follow approximately the Poisson distribution with parameter $\lambda = n/m$. In your case, we have $\lambda=1$. The total number of collisions (the way you are counting it) is

$$N = \sum\_i \max(N\_i-1,0).$$

Now,

$$\begin{align\*} \mathbb{E}\[\max(N\_i-1,0)\] &= 1 \cdot {\lambda^2 e^{-\lambda} \over 2!} + 2 \cdot {\lambda^3 e^{-\lambda} \over 3!} + 3 \cdot {\lambda^4 e^{-\lambda} \over 4!} + \cdots\\ &= \lambda e^{-\lambda} + \lambda^2 - \lambda. \end{align\*}$$

(Don't ask me how I summed the series; black magic.) It follows that

$$\mathbb{E}\[N\] = \sum\_i \mathbb{E}\[\max(N\_i-1,0)\] = (\lambda e^{-\lambda} + \lambda^2 - \lambda) n.$$

In your case $\lambda=1$ and $n=4000$, so we predict $1/e \times 4000 \approx 1472$ collisions. That has very close agreement with what you are observing empirically, so practice and theory seem to be in close agreement.

---
Tags: hash
---


# Question
Title: How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points?
Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x\_0,y\_0,z\_0)$ be the origin/point of reference.

We consider a convex polytope $P$ *good* / *interior* if:

1. $P$ is wholly contained within the interior of the convex hull of $S$: $P \subsetneq \text{convexhull}(S)$.
2. $O$ is contained within the interior of $P$, namely: $O \in P$.
3. none of the points in $S$ are in $P$ namely $S \cap P = \emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e. $\sup \text{Vol}(P)$ where $P$ ranges over good polytopes.

---

Here is a 2D modest illustration (the green polytope might not be really the optimal):

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $\alpha$-shapes or $\beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is "pumping down" the convex hull of Delaunay Triangulation:

> DT $\leftarrow$ delaunayTriangulation($S \cup O$)
>
> CH $\leftarrow$ convexHull(DT)
>
> while Not empty(DT) and $O \notin CH$:
>
> $\quad$ i. previousDT $\leftarrow$ DT
>
> $\quad$ ii. update DT $\leftarrow$ DT $\setminus$ CH
>
> return previousDT

---

**EDIT**: I think what I am looking for in a one-liner of math symbols is:

$$\text{argmax}\_{P} \text\\{\text{Vol}(P) \\, | \\, O \in P \setminus \partial P \\, ; \\, S\cap P = \emptyset \\, ; \\, P \subsetneq \text{convexhull}(S) \\} $$

Where $\partial P$ is the boundary of a polytope $P$.

# Answer
> 0 votes
What I ended up doing is the following:

Given a set of points in $S \subset \mathbf{R}^3$, and a single point as origin, $\mathbf O \in \mathbf{R}^3$ preform the following:

1. Init empty set $S'$.
2. $r = \max\\{ ||\mathbf x - \mathbf O ||^2\_2 \\, , \\,\\, \mathbf x \in S\\}$
3. Create a mapping $F(x): S\to S'$ where $\mathbf x \in S \to \frac{r^2}{||\mathbf x - \mathbf O\\|^2} (\mathbf x- \mathbf O)$
4. $CH\_{S'} \leftarrow $ the points in $S'$ which form convex hull of $S'$ (the sphere inverted set $S$)
5. Init the interior points set, $IP$ $\leftarrow$ $F^{-1}(s'\in CH\_{S'})$ to find the points in $S$ whose sphere inversion points were in $CH\_{S'}$.
6. Use Delaunay triangulation to find the volume of the the convex hull of $IP$

---

Matlab code:

```
%% Init
N=20;

S1 = cell(1, N);
for k = 1:N, S1{k} = 30*rand(1, 3); end
S2 = cell(1, N);
for k = 1:N, S2{k} = 30*rand(1, 3); end

M1 = cat(3, S1{:});
M2 = cat(3, S2{:});
M  = permute(cat(1, M1, M2), [1, 3, 2]);

O=[0.5,0.5,0.5];

NearestIntersectionPoints = cell(1,N);
for k = 1:N
    tmp1 = M(1,k,:); tmp2 = M(2,k,:);
    v1=tmp1(1,:); v2=tmp2(1,:);
    [d, intersection] = point_to_line(O, v1, v2);
    NearestIntersectionPoints{k} = intersection;
end

MHull = cat(3,NearestIntersectionPoints{:});
X=MHull(:,1,:); Y=MHull(:,2,:); Z=MHull(:,3,:);
R=[ X(:) Y(:) Z(:)];

X=[X(:)]; Y=[Y(:)]; Z=[Z(:)];
DT = delaunayTriangulation(X,Y,Z);

rSquared = (X-O(1)).^2 + (X-O(2)).^2 + (Z-O(3)).^2;

q = rSquared/max(rSquared);
xx=X./q; yy=Y./q; zz=Z./q;

figure
plot3(X,Y,Z, '.', 'MarkerSize',15);
hold on
[k,v] = convhull(X,Y,Z);
v
trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)

figure
[k,v] = convhull(xx,yy,zz);

trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)
hold on
plot3(X,Y,Z, '.', 'MarkerSize',15)
uniqueK = unique(k)
DTinterior = delaunayTriangulation(X(uniqueK),Y(uniqueK),Z(uniqueK));
DTexterior = delaunayTriangulation(X,Y,Z);

[kin, vin] = DTinterior.convexHull;
[kext, vext] = DTexterior.convexHull;

function [d,intersection] = point_to_line(pt, v1, v2)
      a = v1 - v2;
      b = pt - v2;
      d = norm(cross(a,b)) / norm(a);
      theta = asin(norm(cross(a,b))/(norm(a)*norm(b)));
      intersection = v2 + a * cos(theta);
end

```

---

---

Demo in 2D:

```
close all
N=20;
R=[1, 5];
center=[0, 0];
x=zeros(length(R),N);
y=zeros(length(R),N);
theta=linspace(0,2*pi,N+1);
theta=theta(1:end-1);

for i=1:length(R)
    x(i,:)=R(i)*(randn+1)*cos(theta+rand) + center(1);
    y(i,:)=R(i)*(randn+1)*sin(theta+rand) + center(2);
end

% Concat all the arrays into one set
x=[x(1,:) x(2,:)]; y=[y(1,:) y(2,:)];
rSquared=x.^2 + y.^2;
q = rSquared/max(rSquared)^2;
xx=x./q; yy=y./q;

k = convhull(xx,yy);
plot(x(k),y(k),'r-',x,y,'b*')

```

---

---

---
Tags: algorithms, optimization, linear-programming, convex-hull
---


# Question
Title: is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?
L is the language of all turing machines that its computing time on all inputs is O(n^2). my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search.... However, is the language in CO-RE ?

# Answer
> 5 votes
This problem is not in RE nor in coRE.

First, your *intuition* that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof! However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.

Let's start by proving that the language is not in coRE, by a reduction from $HALT\_{TM}=\\{\langle M,w \rangle: M$ halts on $w\\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.

Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT\_{\overline{TM}}=\\{\langle M,w \rangle: M$ does not halt on $w\\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.

The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.

---
Tags: turing-machines, computability
---


# Question
Title: deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition
Thanks a lot for your help.

I want to understand what really causes what I suppose to be a deadlock:

I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t really matter for my problem)

I have a container (list) of Couples, where a Couple simply is: 2 Words and 1 couple-Key.

I have a function that is suppose to do some calculation on the list of Couples, it might modify the letters and the key during the calculation , but when the calculation is finish we can stock the result and reset it to the initial values.

Considering a code that uses a parallel for loop to get the results of all my couples. This uses a lock on the first word and then a lock on the second word before calling the getResult() function, why could a deadlock happen ?

My first idea was that if we have :

Couple 1 : A B

Couple 2 : B C

Couple 3 : C D

Couple 4 : D A

Couple 5 : A E.

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

My intuition is that, someway deadlock might occur if a cycle pattern appears in my list of Couples. On the other hand, I am unable to build an example that explains a deadlock appearance without considering one of these event:

* simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment (quite unprobable to me).
* a thread takes the priority to a former one (example:well I can't find any, finally I thinks it s equivalent to simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment. It's just that, considering a big cycle, the probability that it happends is as high as the proportion of time required for a calculation over the number of threads.

Am i right with my analysis ?

If the cause of the eventual deadlock is not due to the "simultaneously " event, I'd be glad to know what causes it, or happy if more precision to deadlock probability appearances depending on number of threads or length of cycles etc... are discussed .

Actually, I kind of have 10^5 Couples 10^4 Words.

Thanks,

Guillaume

# Answer
> 1 votes
> If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

Couple 1 tries to start and is waiting on A, couple 4 tries to start but is also waiting on A.

After couple 5 finishes one of the waiting couples will be able to lock A. If it is couple 1 then it will need to lock B before it can continue, however that is held by couple 2 and that is waiting on couple 2 which is waiting on couple 3 etc. until couple 4 which is now waiting on couple 1. There is no way to make progress $\implies$ deadlock.

It's important to keep in mind that between locking one word and locking the next a process can be interrupted or another can simple be faster and lock the second word.

You can avoid the lock by always locking the words in alphabetical order, that way couple 4 will lock A before it will try to lock D and couple 3 is then able to make forward progress and a deadlock is impossible.

---
Tags: graphs, parallel-computing, deadlocks
---


# Question
Title: How to prove these two distributions are statistically/computationally indistinguishable
First we generate a key, $$k \leftarrow \\{\\, 0,1 \\,\\}^{n}$$ And we construct two PPT algorithms $A$ and $B$ as follow:

$$A\_{k}\left( \cdot \right) \colon y\_{A} \leftarrow k, \text{ return } y\_{A}$$ and $$B\_{k}\left( \cdot \right): y\_{B} \leftarrow \\{\\, 0,1 \\,\\}^{n}, \text{ return } y\_{B}$$

For **fixed** $k$, let $D\_{A}$ be the distribution of $A$, and $D\_{B}$ be the distribution of $B$. I want to know whether $D\_{A}$ and $D\_{B}$ are statistically indistinguishable or computationally indistinguishable.

In my opinion, $D\_{A}$ is a one-point distribution and $D\_{B}$ is a uniform distribution. Thus they are not statistically indistinguishable.

Let $$A^{\prime}\left( \cdot \right) \colon k \leftarrow \\{\\, 0,1 \\,\\}^{n}, y\_{A^{\prime}} \leftarrow A\_{k}\left( \cdot \right), \text{ return } y\_{A^{\prime}}$$ and $$B^{\prime}\left( \cdot \right) \colon k \leftarrow \\{\\, 0,1 \\,\\}^{n}, y\_{B^{\prime}}, \leftarrow B\_{k}\left( \cdot \right), \text{ return } y\_{B^{\prime}}$$ then $D\_{A^{\prime}}$ and $D\_{B^{\prime}}$ are statistically indistinguishable, thus they are also computationally indistinguishable.

Is my method correct? It looks strange and it seems that $k$ is not fixed when I show that they are computationally indistinguishable. Is there a better method from a clear view about the computationally indistinguishable and statistically indistinguishable?

Thanks for @D.W.♦'s answer, if $k$ is fixed, then $k$ is not a random variable anymore. Thus, there are 4 kinds of distributions.

Type (1)

> For $k \leftarrow \\{\\, 0,1 \\,\\}^{n}$, $A\_{k}$ and $B\_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left\[ k \leftarrow \\{\\, 0,1 \\,\\}^{n}; \mathcal{A} \left(k, A\_{k} \left( \cdot \right) \right) = 1 \right\] - \Pr \left\[ k \leftarrow \\{\\, 0,1 \\,\\}^{n}; \mathcal{A} \left(k, B\_{k} \left( \cdot \right) \right) = 1 \right\] \right\vert \< \varepsilon(n) $$

Type (2)

> For $k \leftarrow \\{\\, 0,1 \\,\\}^{n}$, $A\_{k}$ and $B\_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left\[ k \leftarrow \\{\\, 0,1 \\,\\}^{n}; \mathcal{A} \left( A\_{k} \left( \cdot \right) \right) = 1 \right\] - \Pr \left\[ k \leftarrow \\{\\, 0,1 \\,\\}^{n}; \mathcal{A} \left( B\_{k} \left( \cdot \right) \right) = 1 \right\] \right\vert \< \varepsilon (n) $$

Type (3)

> For $k \in \\{\\, 0,1 \\,\\}^{n}$, $A\_{k}$ and $B\_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left\[ \mathcal{A} \left(k, A\_{k} \left( \cdot \right) \right) = 1 \right\] - \Pr \left\[ \mathcal{A} \left(k, B\_{k} \left( \cdot \right) \right) = 1 \right\] \right\vert \< \varepsilon(n) $$

Type (4)

> For $k \in \\{\\, 0,1 \\,\\}^{n}$, $A\_{k}$ and $B\_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left\[ \mathcal{A} \left( A\_{k} \left( \cdot \right) \right) = 1 \right\] - \Pr \left\[ \mathcal{A} \left( B\_{k} \left( \cdot \right) \right) = 1 \right\] \right\vert \< \varepsilon (n) $$

To make it clear, I just want to know (4) holds true or not. And my original method confuses the definition between (2) and (4).

I think it may be helpful after we analyse the relation among these 4 types.

Obviously, "(1) holds true" $\Leftrightarrow$ "(3) holds true", since for all the PPT $\mathcal{A}$, $$\Pr \left\[ \mathcal{A} \left(k, A\_{k} \left( \cdot \right) \right) = 1 \right\] = \Pr \left\[ k \leftarrow \\{\\, 0,1 \\,\\}^{n}; \mathcal{A} \left(k, A\_{k} \left( \cdot \right) \right) = 1 \right\]$$

And "(1) holds true" $\Rightarrow$ "(2) holds true" is also easy to prove.

However I still cannot find a clear proof about the relation between (3) and (4).

# Answer
> 1 votes
I think your problem is in trying to insist that $k$ is fixed. That's getting you tied up in knots.

The statement "for fixed $k$, define $D\_A$ to be the distribution..." makes no sense to me, because as you have previously defined $k$, $k$ *isn't* fixed -- $k$ is defined to be a random variable (that is uniformly distributed on $\\{0,1\\}^n$). So, it looks to me like you are contradicting yourself.

Instead, let me suggest a better way to think about indistinguishability. Think about indistinguishability as a *random experiment*. There is a formal definition of indistinguishability. In that definition, we define an experiment. The experiment works by running some algorithms that we have fully specified, and then observing the result. As part of this you will need to fully specify the probability space and the event you care about. For instance, if $F,G$ are two algorithms that depend only on a key $k$, then we might define them to be computationally indistinguishable if there does not exist a polynomial-time algorithm $A$ such that

$$|\Pr\[k \leftarrow \\{0,1\\}^n ; A(F(k)) = 1\] - \Pr\[k \leftarrow \\{0,1\\}^n ; A(G(k)) = 1\]|$$

is non-negligible. That's a standard definition of computational indistinguishability. Notice that the event $k \leftarrow \\{0,1\\}^n ; A(F(k)) = 1$ (and corresponding probability space) is fully defined, by defining some algorithms and then asking about the probability that it outputs 1. Everything can be expressed as a statement about some random variable, where the random variable is defined by executing a well-specified algorithm (i.e., in pseudocode). There is no step halfway along that says "fix $k$" (it's not even clear to me what that would mean).

The idea here is that we want to make a statement about the probability of some event. That event is defined in terms of running a randomized algorithm and checking its output. This is a well-defined and precise way to define an event in some probability space. Once you start trying to add "fix $k$" in the middle of that, we lose that property and it's not clear what you mean.

So, stick with the standard definitions, and try to apply them as is. Don't try to create your own definition. Or, if you insist on it, first translate your idea to a statement about a probability of some event where the event is defined in terms of a well-specified randomized algorithm. You should be able to write pseudocode for each step of your algorithm, without needing English (like "fix $k$"). If you try to do that for your idea, probably you'll find that at one step along the way your pseudocode assigns to $k$ (say, by picking a random value from $\\{0,1\\}^n$), and then $k$ is whatever it is (if it is picked randomly, then it's not fixed; it's a random variable).

For example, here is one fact that is true. If we define $X$ by $k \leftarrow \\{0,1\\}^n; X \leftarrow k$ and $Y$ by $k \leftarrow \\{0,1\\}^n; Y \leftarrow \\{0,1\\}^n$, then $X,Y$ are computationally indistinguishable and statistically indistinguishable (just apply the definition and see what you get). Same if you define algorithms $A,B$ as in your question and define $X$ by $k \leftarrow \\{0,1\\}^n; X \leftarrow A\_k()$ and $Y$ by $k \leftarrow \\{0,1\\}^n; X \leftarrow B\_k()$.

However, if you give the adversary knowledge of $k$, they are no longer distinguishable. Thus, for instance,

$$|\Pr\[k \leftarrow \\{0,1\\}^n ; \mathcal{A}(A\_k()) = 1\] - \Pr\[k \leftarrow \\{0,1\\}^n ; \mathcal{A}(B\_k()) = 1\]|$$

is negligible for all adversaries $\mathcal{A}$, but

$$|\Pr\[k \leftarrow \\{0,1\\}^n ; \mathcal{A}(k,A\_k()) = 1\] - \Pr\[k \leftarrow \\{0,1\\}^n ; \mathcal{A}(k,B\_k()) = 1\]|$$

is not.

As an aside, often we use $A$ to represent the adversary/attacker, so using $A$ to represent some other algorithm can potentialy get a little confusing.

---
Tags: computability
---


# Question
Title: How to read off the set represented by a van-Emde-Boas tree?
I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the *proto-vEB* with related picture. I'm struggling to understand the actual data structure. I have no clue how the "min" and "max" members are actually used, I'm not talking about the procedures but just how the following picture is supposed to be interpreted. Can anyone help me with this?

# Answer
> 4 votes
If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons.

In 20.3.1, they write:

> min stores the minimum element in the vEB tree, and max stores the maximum element in the vEB tree. Furthermore, the element stored in min does not appear in any of the \[subtrees\].

What might confuse you is that the actual elements to not appear. As explained earlier in the chapter, the elements are encoded by *position*: the domain of the tree is $\[0..15\]$, and the subset is essentially encoded by a bit vector stored in the leaves of the tree. Figure 20.4 is annotated helpfully in this regard; note that the minimums are moved up to the `min` fields here, though.

In the full VEB tree, the encoding itself is a little tricky. Here goes:

Here is how you read the tree (ignore the dark summary nodes for this purpose):

* `u` denotes the size of the domain of a node.
* The root has domain `[0..u-1]`.
* The domain of a node `cluser[i]` is the the `i`-th chunk of size `cluser[i].u` in the domain of its parent.
* If they are not `nil`, `min` and `max` are indices into the domain of the node.
* If `min` and `max` are `nil`, the node represents no elements.

*Examples:*

* `root.cluster[1].min` is `0`; it represents element `0 + 1*4 * 0 = 3`.
* `root.cluster[0].cluster[1].min/max` are `nil`; therefore `0 + 0*4 + 1*2 + 0/1 = 2/3` are both not in the node.
*But* `2` is in the set anyway, since it's represented by `root.min`!
* `root.cluster[3].min` is `2`; therefore, `0 + 3*4 + 2 = 14` is in the set.
* `root.cluster[3].cluster[1].min/max` are `1`; therefore `0 + 3*4 + 1*2 + 1 = 15` is in the set.

---
Tags: data-structures, trees, sets, integers, van-emde-boas-trees
---


# Question
Title: Rigorous reason against the seemingly wrong way of substitution
Let us consider the lambda calculus expression .

$ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$

Now $\lambda x.x$ is seen as an argument . How to decide which bound variable should the value of the argument go to ?

The books I am going through suggest that in this kind of case when there is one argument available the first bound variable should take that arguments value .

To the best of knowledge I don't remember reading anything rigorous till what Ii have covered of these books that would provide rigorous reasoning as to why the first argument should go to the first bind variable .

I understand it makes sense and a meaningful expression when seen as a function demanding two arguments but being provided one as it makes a function again demanding one more argument . This thing is provided in every introduction to functional programming but still somehow I wonder if we can rigorously show that the first bound variable should be taking the value of the first argument .

I have read about beta reduction and I tried applying that to the above expression :

so $ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$ can be seen as $ (\lambda func.(\lambda arg$ $( func$ $ arg))$ $\lambda x.x)$ and will be in a form $ (\lambda x$$.M) N$ form so here I can justify the first argument being used for $func$.

But can I not see it as follow : $ (\lambda func.((\lambda arg$ $( func$ $ arg))$ $\lambda x.x))$ thereby making it in a form :

$ \lambda func.($ $( \lambda x .M)N$) thereby allowing the second bound variable to take the value of the argument ?

So how to provide a rigorous reason for the first bind variable taking the first argument ?

# Answer
You're not going to find a rigorous reason, because there is no semantic reason. The reason is *purely* syntactic.

The key is to remember that lambda calculus expression are, in fact, trees. A node is either a variable, with no children, an application with two children, or a lambda, with two children, one of which is the variable it binds.

Trees are hard to write, so we have a syntax for writing expression trees in a linear way. If we wrap every expression in parentheses, there's an unambiguous mapping between linear expressions and trees. But any time that parentheses are missing, we need precedence rules to disambiguate.

The choice of precedence rules is arbitrary, and is purely catered towards human understanding.

Once you're working with trees, or at least fully parenthesized expressions, then it should be more clear why the argument is given as the outermost bound variable: application is a binary operation between siblings in the trees. Other than the substitution operation, we don't want to have to look up or down the tree when applying a reduction.

If you want a syntax where you don't always apply arguments this way, you may be interested in the spine calculus, which is a syntax that nicely captures the idea of applying multiple arguments to a single core, called the *head*.
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Turing Machine that halts iff the tape contains at least two '1's
> Contruct a Turing Machine that halts if and only if the tape it is on contains at least two '1's.

My attempt:

The gist of this turing machine is that it has to check all of the cells, and since it is infinite in both directions, one way of indexing it is a follows

Thus it has occurred to me to write a pseudocode for the TM's behaviour like this:

```
n:= 0           //number of '1's encountered
i:= 0           //index
while(true)
{
  if(n==2)
    halt
  for k=0 upto i
  {
    check()
    if(i even)
      move left
    if(i odd)
      move right
  }
  i++
}

```

Where check is the function defined as follows:

```
check()
{
if(current cell contains 1)
  n++
}

```

But this seems really hard to implement as a turing machine, especially since there are two variables involved. My guess is that I am overthinking and there is a much cleaner, nicer and elegant solution.

So my question is: What would be a better solution?

# Answer
I managed to solve it in the end. If anyone is interested, I left a diagram of the TM here
> 0 votes

---
Tags: turing-machines
---


title: Concatenation of two regular languages

text:
# Question
Title: Concatenation of two regular languages
In a question, it is given that L is a finite language over the unary alphabet and L+ is not regular. We know that L+ = LL\* Since L is finite, it must be regular because all finite languages are regular. If L is regular L\* is also regular. Then how can be L+ not regular? It is the concatenation of two regular languages. Where am I wrong?

# Answer
> it is given that L is a finite language over the unary alphabet and L+ is not regular.

That's impossible. Since $L$ is finite, it is regular. Since $L$ is regular, $L^+ = L L^\*$ is regular. See, e.g., https://en.wikipedia.org/wiki/Regular\_language#Closure\_properties.

You're not wrong; you are right.
> 3 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Find the longest contigous subsequence where each pair's difference is at most p
> Given input sequence $x\_1,...,x\_n$, find the longest contigous subsequence $x\_i,... x\_l$ where each pair $(x\_j,x\_k)$ satisfies that $|x\_j - x\_k| \le p$.

I have come up with simple $\mathcal{O}(n^2)$ solution.

I'm sure there is a better way so I'm looking for $\mathcal{O}(n)$ or at least $\mathcal{O(n \log n)}$ solution. Thanks for any help!

# Answer
> 1 votes
You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x\_i,\ldots,x\_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x\_i,\ldots,x\_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity $$\min(x\_i,\ldots,x\_{i+2^{\ell+1}-1}) = \min\bigl(\min(x\_i,\ldots,x\_{i+2^\ell-1}),\min(x\_{i+2^\ell},\ldots,x\_{i+2^\ell+2^{\ell}-1})\bigr). $$ Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log\_2 (j-i+1) \rceil$ in constant time. Then $$ \min(x\_i,\ldots,x\_j) = \min\bigl(\min(x\_i,\ldots,x\_{i+2^\ell-1}), \min(x\_{j-2^\ell+1},\ldots,x\_j)\bigr). $$

For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x\_\ell,\ldots,x\_i) \geq x\_i-p$ and the minimal $r \geq i$ such that $\min(x\_i,\ldots,x\_r) \geq x\_i-p$. Thus $x\_\ell,\ldots,x\_r$ is the largest interval satisfying your constraint in which $x\_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.

---
Tags: algorithms, subsequences
---


# Question
Title: Cartesian product of regular expressions?
My textbook has a problem to find the regular expression that describes the set of all strings of `0`'s and `1`'s whose number of `0`'s is divisible by `5` and whose number of `1`'s is even.

I can write a regular expression for each condition

a. $0^\*(10^\*1)^\*$

b. $1^\*(01^\*01^\*01^\*01^\*01^\*)^\*$

I am having trouble understanding how to combine these two regular expressions. If they were DFAs, I could combine them by taking their cartesian product. Is is possible to take the cartesian product of two regular expressions (without translating each to a DFA first)?

# Answer
Gelade and Neven prove the following theorem in their paper Succinctness of the Complement and Intersection of Regular Expressions:

> For every $n$ there exist two regular expressions $r\_1,r\_2$ of size $O(n^2)$ such that the smallest regular expression representing $L\[r\_1\] \cap L\[r\_2\]$ has size $\Omega(2^n)$.

This suggests that there is no analog of the product construction for regular expressions.
> 4 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?
Let $A$ denote a set that contains a relatively large number of different strings. Let $S\_i$ denote these strings.

Let $B$ denote a set of sets such that each subset contains a (relatively small, usually not greater than 100) number of different strings. Let $B\_i$ denote these subsets.

The problem is the following: is it possible to have an efficient way to obtain a set $C$ that contains a **minimal** number of different subsets of $B$, but for each $n$, a subset of $B$ that contains a string $S\_n$ will be present as a subset of $C$?

Example:

```
A = ["a", "b", "cd", "e", "eeff", "x", "y", "xyz"];
B = [
["aa", "dce", "n", "e", "f", "y"],
["aa", "b", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["i", "cd", "le8", "a", "t", "eeff", "f"],
["aaa0", "x", "b", "a", "t1", "s"],
["xyz", "a", "n"],
["b", "xyz", "n"],
["eeff", "xyz", "dce", "aa"],
],

```

We can find multiple possibilities here, e.g. a set with five subsets:

```
C = [
["aa", "dce", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["aaa0", "x", "b", "a", "t1", "s"],
["eeff", "xyz", "dce", "aa"],
]

```

(note that for each $x$ such that $0 \le x \le 7$, there is an element of $C$ that contains $A\_x$), but the possible solution allows to have only four elements in $C$:

```
C =
["aa", "b", "n", "e", "f", "y"],
["aaa0", "x", "b", "a", "t1", "s"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["eeff", "xyz", "dce", "aa"]
]

```

Is it possible to have a relatively efficient method of solving such a problem? I only see a factorial-level complexity (testing each possible combination), which quickly becomes physically impossible to implement. But if $A$ contains millions of elements, and $B$ contains billions of elements, we need another solution...

# Answer
> 3 votes
If you delete all subsets in $B$ that contain no string from $A$, then this is exactly the (Minimum) Set Cover problem, which is NP-hard, meaning that almost certainly no efficient (that is, polynomial-time) algorithm exists.

Testing each possible combination can be done in $O(m2^n)$ time if there are $n$ sets in $B$ and $m$ elements in $A$, which is better than factorial time. (We don't care about the *order* of the subsets we select.)

---
Tags: algorithms, optimization, time-complexity, sets
---


# Question
Title: Placing small circles randomly inside a larger circle, where no two small circles intersect
Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else.

So i am trying to work out a way to write an algorithm to place a series of small circles of a set radius (all the small circles have the same radius), inside a larger circle.

The small circles cannot overlap each other or overlap the main circle's perimeter, and they are placed randomly inside the main circle.

I am wanting it to then populate as many circles as it can until it is not possible to place any more circles without overlapping another.

This obviously means that each run through depending on the random placements will potentially give different amounts of maximum number of circles inside the big circle - thats fine, and thats some what the point.

Does any one have any advice how i might approach the logic for this?

# Answer
> 1 votes
Suppose the small circles have radius $r$, and the large circle has radius $R$. If there are less than, say, 100 small circles, then the following simple algorithm should be fast enough:

1. Generate a larger number, say 1000, of points at random locations inside a circle of radius $R-r$ (this smaller radius guarantees that a small circle centered at each point will fit within the radius-$R$ circle).
2. Calculate all roughly 500000 pairwise distances between points.
3. Sort these distances in increasing order.
4. Loop through the distances. For each distance $\< 2r$, randomly pick either point and delete it. (Such a distance implies that there could not be a radius-$r$ circle at *both* points without overlap.) If the distance refers to a point that has already been deleted, ignore it.
5. All points that remain are at least $2r$ apart from each other, so you can put a radius-$r$ circle at each.

If this is too slow, you could use a grid to speed things up: Make the step size of the grid $2r$, and only bother comparing point pairs that are in the same grid cell or adjacent grid cells. (Every pair of points $x \in X, y \in Y$ for 2 non-adjacent grid cells $X$ and $Y$ is at least $2r$ apart, so we don't need to bother testing them.)

NOTE: This could leave holes where a small circle could fit. My intuition is that having enough initial potential centre points will make this unlikely. You could use a smaller grid, of step size $r$, to find some (not necessarily all) of these holes: A grid cell that does not overlap any circle is definitely a "hole" (a circle can be added there).

In case you're wondering, the problem you "really" want to solve is to find an independent set of vertices in a graph in which you have a vertex for each circle and an edge between 2 points whenever they are at distance $\< 2r$. The general form of this problem is NP-hard, though I suspect there is enough additional structure here that a faster solution (maybe poly-time, maybe not) is possible.

---
Tags: algorithms, computational-geometry, discrete-mathematics, randomness
---


title: No of Actions in if statement

text:
# Question
Title: No of Actions in if statement
i am new to analysis of algorithm . i am having an if condition.

```
If (I !=j AND A[i]==A[j])

```

i am counting the operations as

```
i) accessing element from Array A[]
ii)compairing i!=j

iii) compairing a[i]==a[j]

```

according to me this statement is performing 3 Actions. is it so ? if not than please clarify... thanks

# Answer
> 3 votes
Counting "actions" in this way is completely arbitrary. In order to accurately count basic actions, you need to first come up with a list of basic actions, and then to compile your statement to a list of basic actions. This is exactly what compilers do – they compile your problem to assembly language or, in some cases, to bytecode.

Since you are not specifying your assembly language, it is truly impossible to say anything. It could be that there is one instruction that is equivalent to your `if`, or it could be that your assembly language is very weak, and your `if` requires 100 instructions. Even if you did specify your assembly language, it is still not clear how to compile the statement to assembly, since in general there is no canonical way to do so.

The way out is to realize that (under certain conditions) whatever assembly language is used, the statement would compile to a constant number of instructions, whose exact number depends on the assembly language. Therefore we can say that the number of instructions is $O(1)$, where the hidden constant depends on the assembly language and the compiler. In contrast, a loop summing an array would execute $\Theta(n)$ instructions. The difference between $O(1)$ and $\Theta(n)$ exists irrespective of the assembly language and compiler used.

---
Tags: algorithms
---


# Question
Title: L = {<M> | M is a TM and halts on every input after 5 steps exactly } - is L decidable?
in order for M to belong to L, it must halts on all inputs after 5 steps exactly. is the problem not decidable ? how can it be proved ? I could not succeed in doing a reduction from Htm as the attempt to count M(w) steps failed.

update: apparently the language is in R. can anyone provide a proof?

# Answer
It is NOT NECESSARY to read the whole input for a Turing Machine to halt.

Imagine a Turing Machine M that receives any input such that it reads anything and moves right exactly 5 times. On fifth step it reaches the accept state and halts.

M belongs to L.

Contrary to what I was thinking before, L is indeed decidable.

Consider all Σ $^5$ configurations of the first 5 cells of the tape. For each of these configurations execute 5 steps. If TM is nondeterministic execute 5 steps for all possible paths. If TM does not halt for some configuration (or execution when TM is nondeterministic) reject. Otherwise, accept.

As Σ $^5$ is finite, L is decidable.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: Are programming languages ultimately procedural?
I'm studying a declarative programming language (Prolog) and in thinking about how certain things are programmed at a low level, a question came to me:

are programming languages ultimately procedural ?

# Answer
> 4 votes
I imagine that by "procedural" you mean languages whose statements refer to changes of state in one ore more objects, but these references are implicit, not explicit (they follow a fixed pattern, for instance, the state change made by the execution of a statement is delivered to the next, resembling a *procedure*).

You may be referring to the fact that our computers, at a low level of abstraction, are usually state machines - so to speak - so all programming languages would have to be procedural languages disguised as something else.

This has happened for technical and economical reasons, it's not a theoretical imperative. It doesn't have to be that way. Inside your head there is a computational device that isn't like that, and we've been experimenting with all kinds of different models for low level implementation of general-purpose computers for decades. It is not unlikely that, at some point, one of these alternative models becomes commercially viable.

# Answer
> 4 votes
1. Existing hardware is "procedural". Therefore, whatever machines do, it is always "procedural" at the very low level. However, there is nothing mathematically fundamental about procedural computing. There are many forms of computing (procedural, functional, logic programming) and they can all simulate each other.
2. Furthermore, a programming language may have a definition of how it executes that does not "translate" or "compile" to anything. If such a language is functional, then we have a functional programming language that is *not* "ultimately procedural" because its execution rules are explained without refrence to anything procedural (Note: the execution rules themselves are given as an inductively generated relation, so they are a mathematical object and it makes no sense to ask "are the rules procedural?" It makes sense to ask how the rules should be implemented on existing hardware, `goto 1`.)

# Answer
> -3 votes
No. not every programming language is procedural at the end. as procedural languages follow the pattern as the statements are typed whereas Non procedural languages keeps jumping to different statements and methods... take a look here too

---
Tags: programming-languages
---


# Question
Title: What are some examples of types that can't be derived set theoretically?
I'm hoping for examples that aren't too abstract or useless in day-to-day programming, though not with a lot of hope, since in Bartosz Milewski's book, it is stated that generally speaking, the category **Set** is good enough, but mentions polymorphic functions and there not being a set that includes all sets as being one possible example.

For polymorphic functions, I'm not really sure how this comes up. For example, with `id[A](x: A): x -> x`, where `A` is a type parameter, I do not see why we could not just say: `A` is a member of the type universe corresponding to our programming language, which would just be the set of all types supported by our language. Perhaps if our programming language supports a type universe hierarchy, then this argument could be made, but I do not know if any languages do support it in any meaningful way (perhaps theorem proving languages like CoQ?)

## Notes on answers

**Recursively defined types**

For `type t = bool + (t -> t)`, since we assume `t` corresponds to a set `T`, `t->t` would be size `T^T` (ref). In Scala it looks like this:

```
sealed trait T
final case class Foo(value: Boolean) extends T
final case class Bar(value: T => T) extends T

```

# Answer
There are several type-theoretic constructions that cannot be easily handled with set theory. Note that when we say "set theory" we mean that we intend to interpret types as sets and type-theoretic functions as set-theoretic functions. In particular, the set-theoretic interpretation of types requires that a function type `A → B` must be interpreted as the set of *all* set-theoretic functions from `A` to `B`.

If our type theory has general recursion then it cannot be interpreted set-theoretically. General recursion allows us to define, for any type `A`, the fixed-point operator `fix : (A → A) → A`

```
fix f = f (fix f)

```

but the only sets which have such a fixed-point operator are the singletons. For example, if we take `A` to have two elements, then it will have a function without fixed point (the one that swaps the elements).

Another reason that set theory may not be sufficient is polymorphism, as you indicated. Here the reasons are perhaps a bit technical and it is best to read the famous paper Polymorphism is not set-theoretic by John Reynolds. Beware: reasoning about how one might get away with a polymorphic identity function is *not* proof that set theory models polymorphism. In any case, your suggestion to use universes is not going to work for System F. You can have an identity function that works for *one* universe, but to make it work for *all* universes you will have to make it *universe-polymorphic*, and so you're back to square one.

A third reason that a type theory may not be set-theoretic is that it allows constructions of types that do not exist in set theory. For example, in many programming languages we can define recursive types (Haskell and ML are like this) such as

```
type t = bool + (t -> t)

```

The set-theoretic counterpart of this is a set `T` such that $$T \cong 2 + T^T$$ but such a set $T$ does not exist, because the cardinality of $2 + T^T$ is strcictly larger than the cardinality of $T$.

A fourth reason that a type theory may not be set-theoretic is that it may contain constructs that prevent this. For example, we could have a type theory with a `timeout` construct which works as follows: `timeout k x e` computes `e` for at most `k` steps (where "step" need to be suitably defined). If `e` finishes with result `y` within `k` steps then the overall result is `y`, otherwise the overall result is the "fallback" value `x`. From a programming point of view, this is a reasonable construct that can actually be implemented. However, as soon as we have `timeout` we can write down functions that do not exist in set theory. One such function is the modulus of continuity which witnesses the fact that "all functions are continuous". In set theory there are many discontinuous functions.

Lastly, if we take "spartan" type theory without any special features (no general recursion, no polymorphism, no recursive types, etc.) then it *is* set theoretic. You need to extend type theory in some fashion to break the set-theoretic interpretation.
> 11 votes

---
Tags: type-theory, category-theory
---


# Question
Title: What is the difference between exactness and optimality of an algorithm?
I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve this problem, or there is no optimal solution for that. The following paper mentioned this fact in its introduction: "An exact algorithm for graph partitioning"

However, they provided an exact solution for GP using branch-and-bound algorithm. Isn't it a paradox?, I mean I assume that if a problem is NP-Complete, there is also no exact solution for that, right?

# Answer
> 3 votes
Every NP-complete problem can be solved in exponential time. Assuming that P differs from NP, it cannot be solved in polynomial time. It follows that the branch-and-bound algorithm probably doesn't run in polynomial time (in the worst case).

To give a concrete example, consider the problem of MAX-CLIQUE: given a graph, the task is to find a clique of maximum size. The decision version of this problem (given a graph and a number $k$, decide whether the maximum clique has size at least $k$) is NP-complete. This means that (unless P equals NP), no polynomial time algorithm can solve MAX-CLIQUE exactly on all inputs. However, there is a simple exponential time algorithm that does solve MAX-CLIQUE exactly: it just tries all potential cliques and checks which of them are present in the graph.

Finally, you mention that if a problem is NP-complete then the reason might be that there is no optimal solution. This is just wrong, and I suggest ignoring the source which led you to believe this statement.

---
Tags: algorithms
---


title: Structural induction proof

text:
# Question
Title: Structural induction proof
I need to prove the following:

```
reverse(append(zs, z)) = Cons(z, reverse(zs))

```

Where:

```
sealed abstract class IntList
case object Nil extends IntList
case class Cons(x: Int, xs: IntList) extends IntList

def append(xs: IntList, x: Int): IntList = xs match {
    case Nil => Cons(x, Nil)
    case Cons(y, ys) => Cons(y, append(ys, x))
}

def reverse(xs: IntList): IntList = xs match {
    case Nil => Nil
    case Cons(x, ys) => append(reverse(ys), x)
}

```

I've already made the induction basis:

Assume $zs=Nil$. \begin{align\*} reverse(append(zs, z)) &=reverse(append(Nil,z)) \\ &=reverse(Cons(z,Nil)) \\ &=append(reverse(Cons(Nil),z)) \\ &=Cons(z,reverse(Nil)) \end{align\*}

How do I make the induction step?

# Answer
Here is the complete proof:

reverse(append(Cons(w,ws),z)) = reverse(Cons(w,append(ws,z))) = append(reverse(append(ws,z)),w) = append(Cons(z,reverse(ws)),w) = Cons(z,append(reverse(ws),w)) = Cons(z,reverse(Cons(w,ws)))

At one point we used the inductive hypothesis.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$
I have a sum:
$$S = \sum\_{i=1}^n{\lfloor a/i \rfloor i^2},$$
where $a$ is a constant. Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in logarithmic or better time, something manageable when $a$ is big, `n = a/2`? I tried lots with pen and paper, but I cannot see how to do this faster than $O(a)$ time.

# Answer
The idea is to split the sum into two parts: For individual values of i for $i \<= a^{1/2}$, then for individual values of floor (a/i). For example find the smallest and largest values i where floor (a/i) = 1 or 1 \<= a/i \< 2. The values i^2 can be summed with a simple formula.

Here's how we can do this efficiently:

We have $a/i ≥ k$ iff $i ≤ a/k$ or $i ≤ \lfloor a/k \rfloor$. Define $g(k) = \lfloor a/k \rfloor$, then $a/i ≥ k$ iff $i ≤ g(k)$.

We have $\lfloor a/i \rfloor = k$ iff $a/i ≥ k$ but not $a/i ≥ k + 1$, that is $i ≤ g(k)$ but not $i ≤ g(k+1)$, or $g(k+1) \< i ≤ g(k)$.

Define $f(n) = (n \cdot (n+1) \cdot (2n+1))/6$, then the sum of squares from $1^2$ to $n^2$ is $f(n)$. The sum of the squares $i^2$ for $g(k+1) \< i ≤ g(k)$ is $f(g(k)-f(g(k+1))$.

So the sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor = k$ is $k \cdot (f(g(k)-f(g(k+1)))$. We pick some m close to $a^{1/2}$. The sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor ≤ m$ equals $k \cdot (f(g(k)-f(g(k+1)))$, summed for 1 ≤ k ≤ m. This covers all $i \> g(m+1)$.

To this sum we add $\lfloor a/i \rfloor \cdot i^2 = g(i) \cdot i2$ for 1 ≤ i ≤ g(m+1).
> 4 votes

---
Tags: algorithms, number-theory, iteration
---


# Question
Title: Do all Regular Expressions describe Regular Languages?
I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent regular language? Or is the set of regular languages a subset of regular expressions?

If this is not the case, is there a good example of a regular expression that does not have an equivalent regular language?

# Answer
It's a standard part of any automata theory course that regular expressions, deterministic finite automata and nondeterministic automata all define the same class of languages. Any individual exposition will take one of those three things as defining the class of regular languages.

So, yes, all regular expressions define regular languages, and every regular language is the set of strings that match some regular expression.

At least, the above is true for regular expressions as used in computer science. Perhaps the confusion in the question arises from the fact that many computer systems such as text editors, programming languages/libraries and command shells have pattern-matching features that they call "regular expressions" but which are more powerful than CS regular expressions. @reinierpost provides the example that `egrep '^(.*)\1` matches the non-regular language $\\{ww\mid w\in\Sigma^\*\\}$.
> 6 votes

---
Tags: regular-languages, automata, regular-expressions
---


title: Counting restricted partitions

text:
# Question
Title: Counting restricted partitions
Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x\_1 + \dots + x\_S, ~~~~ 0 \leq x\_i \leq \frac{N}{2} $$

Two partitions are considered distinct if any of the summands has distinct values in them. For example, if $N = 4$ and $S = 3$ then there are 6 possible partitions: $$(1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2, 0), (2, 0, 2), (0, 2, 2)$$

I've derived a dynamic programming solution. Let $d\_{ns}$ be the number of above defined partitions of number $n$ with $s$ summands (each not greater than $\frac{N}{2}$). Then $$ d\_{0s} = 1, ~~~ s \geq 0 $$ $$ d\_{n0} = 0, ~~~ n \> 0 $$ $$ d\_{ns} = \sum\_{k = 0}^{\max \left(n, \frac{N}{2} \right)}d\_{n-k,s-1}, ~~~ sn \> 0 $$

It works fine but i consider this approach to be too slow from algorithmic point of view. It requires roughly $O(N^2 S)$ operations.

So here's my question. Can this computation be done faster? Perhaps via some other recurrence or some smarter way to fill the dynamic programming table for recurrence described above.

# Answer
> 2 votes
First, let us note that the number of ways to write $N$ as a sum of $S$ non-negative integers is exactly $\binom{N+S-1}{N}$. Indeed, the partition $N=x\_1+\cdots+x\_S$ corresponds to the string $\ast^{x\_1}|\ast^{x\_2}|\cdots|\ast^{x\_S}$ (where $\ast^x$ means $x$ many stars), which contains $N$ stars and $S-1$ bars, and conversely any such string corresponds to a partition.

In your case you have the additional constraint that all $x\_i$s are at most $N/2$. Note that at most one $x\_i$ can be more than $N/2$. If $x\_i \> N/2$, then the number of ways to fill the rest of the $x\_j$s is exactly $\binom{N-x\_i+S-2}{S-1}$. Therefore the number of ways to write $N$ as a sum of $S$ non-negative integers which are at most $N/2$ is $$ \binom{N+S-1}{S-1} - S\sum\_{x=\left\lceil \frac{N+1}{2} \right\rceil}^N \binom{N-x+S-2}{S-2} = \binom{N+S-1}{S-1} - S\sum\_{y=0}^{\left\lfloor \frac{N-1}{2} \right\rfloor} \binom{y+S-2}{S-2} = \binom{N+S-1}{S-1} - S \binom{\left\lfloor \frac{N-1}{2} \right\rfloor+S-1}{S-1}. $$ You can calculate this closed form using $O(S)$ arithmetic operations.

---
Tags: combinatorics, dynamic-programming, efficiency
---


# Question
Title: Data-structure for dynamic disjoint-sets
I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).

This is just a simple (javascript) array of gaming cards (think "magic the gathering"), that could be in different zones (deck, hand, grave, play), and they could be owned by different players at different stages of their lifecycle. Also, there is a type (spell, minion, weapon, enchantment) which is unchangeable, but still very important discriminator.

In order to process game, I need to often query my store to get "all spells in hand which cost less than current mana of current player", or "all enemy minions which had not attacked this turn".

Right now I simply use `Array.filter` and just filter the all universe with small predicate functions, but I have a feeling this could be made more efficient, if I can at least cut the size of whole collection in the beginning of query processing.

To speed up queries like `where type = N`, I considered using a pre-made number of Sets (e.g.: "cardsByType = MINIONS | SPELLS | WEAPONS" or cardsByZone = HAND | DECK | GRAVE). Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with object update.

Unfortunately in practice, I need the collection to be ordered, as insertions and removals need to happen in certain positions. This means that Sets only help me with queries like `count where type=n`. Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with each object's (card) update.

Also, maintaining the consistency between object itself, and two collection (old and new) is very error prone.

Am I missing some known obvious data-structure that could be helpful with such task ? OR no general-purpose data-structure like that exists ?

# Answer
For Magic the Gathering, the number of cards is so small that the simplest data structure is probably the best. Just have a list of all cards (each card records its name, location, properties, etc.). Then to answer a query, scan through all cards and see which ones match the query. Since you'll probably have very few cards in the data structure at a time (like, at most a few hundred), all operations should be very fast.

There are more sophisticated schemes, but they probably aren't worth the implementation effort. You could think of this as a table in a relational database (one row per card, one column per attribute), and build an index for each column. In other words, you have an ordered list of cards. You also have a hashmap that maps from location to a list of all cards in that location. These lists are stored as balanced search trees, with links between them (i.e., given a card in one tree, you can follow pointers to find where that card is stored in each of the other trees). This will let you do queries quickly. Also to update the data structure, you can remove a card by finding it, then removing it from all of the linked trees; and you can insert a card similarly. But in your case it won't be worth the effort.
> 1 votes

---
Tags: data-structures, sets, database-theory, searching
---


title: Definition of SAT Problem

text:
# Question
Title: Definition of SAT Problem
What is the goal of the SAT Problem?

* Check if it is possible to have output '1'?
* Above + find the right combination of inputs for that?

Witch one?

Cheers

# Answer
In computational complexity, we usually think of SAT as a decision problem: given a CNF, decide whether there is a truth assignment that satisfies it. There is also a search version of SAT: given a CNF, either find a satisfying assignment, or state that the formula is unsatisfiable. SAT solvers consider a third version: given a CNF, either find a satisfying assignment, or a *proof* that the formula is unsatisfiable.

There are several relations between the various versions. First, if you solve the decision version, you can also solve the search version. The idea is to find the lexicographically smallest satisfying assignment. Assuming that the variables are $x\_1,\ldots,x\_n$, we first substitute $x\_1=0$ and check whether the resulting formula is still satisfiable. If so, we continue on to $x\_2$. Otherwise, we substitute $x\_1 = 1$ (the formula must remain satisfiable) and continue on to $x\_2$. After $n-1$ more such steps we uncover a satisfying assignment.

Another relation is that if you can solve the search version that you can also solve the SAT solver version. The idea is that if the algorithm for the search version states that the CNF is unsatisfiable, then the transcript of the algorithm serves as proof that the CNF is indeed unsatisfiable. So these two versions are essentially equivalent.
> 2 votes

# Answer
Depends if you need to know the value attributions or not.

Deciding the output is always the goal of SAT problem. Deciding the values that lead to the output is something extra.

Notice that if you can decide if the output is 1 then you can decide the input that generates the solution.
> 0 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Bits of memory address used for page number?
A $64$-bit computer has a virtual mem space of $2^{64}$ bytes and the computer also uses memory paging with size of $2^7$ $(128)$ bytes.

Work out the bits of the memory address which are used for the page number?

No. of bits of the memory address which are used for the offset?

Can someone explain how I would go about doing this ?

# Answer
Your virtual address is of size $64$ bits. This means your system can address $2^{64}$ bytes. Each virtual address your system generates points to a byte of memory.

Your system has a page size of $2^7$ bytes. Operating systems like to group bunches of memory bytes together into what is called a page. Think about each page as a block of memory that contains many bytes.

We have a virtual space of $2^{64}$ bytes that we need to page. How many blocks of memory (of size $2^7$ bytes) can we fit in this address space (of size $2^{64}$ bytes) ? $2^{64}$ / $2^7$ = $2^{57}$ blocks (or pages).

We need $2^{57}$ pages. Therefore, there would be $57$ bits required to address each page that we have.

Now, remember each page has $2^7$ bytes. If your OS were looking for a specific byte, the first $57$ bits in the address would have the page number it wants. Then, the last $7$ bits would address a byte on that page. The number of bits used to address a byte in a page is called the offset.

So, $7$ bits for the offset, $57$ bits for the page number. Together, they equal a $64$ bit virtual address.
> 1 votes

---
Tags: operating-systems
---


title: What is the origin of dot notation?

text:
# Question
Title: What is the origin of dot notation?
In object-oriented programming, dot notation is used when accessing the properties or methods of a class:

```
Dog dog
print dog.name
>> "Fido"
dog.walk()
>> Walking the dog now...

```

What is the origin of that syntax and why the `.` to notate it? It must date to some early object-oriented language, but I couldn't find mention of it anywhere.

# Answer
> 10 votes
In \[1\] (authored by one of the co-creators of Simula), there is a suggestion that Simula 67 may have been the first to use this dot notation. Given that Simula is widely credited for being the first OO language, it may be tricky to find an earlier example specifically in an OO context.

EDIT: On DiscreteLizard's suggestion in comments, I took a peek at the use of this dot notation for specifying fields in a record. As it turns out, according to this specification of the PL/I language for the IBM System/360 from July 1965, the dot notation was indeed used to identify fields within structures:

> A qualified name takes the form:
>
> identifier {. identifier} ...
>
> Examples: 1. A program may contain the structures:
>
> DECLARE 1 CARDIN, 2 PARTNO, 3 DESCRIPTION, 2 PRICE;
>
> DECLARE 1 CARDOUT, 2 PARTNO, 2 DESCRIPTION, 2 PRICE;
>
> Elements are then referred to as:
>
> CARDIN.PARTNO
>
> CARDOUT.PARTNO
>
> CARDIN.PRICE

1. Dahl, Ole-Johan. "The Birth of Object Orientation: the Simula Languages." From Object-Orientation to Formal Methods. Springer, Berlin, Heidelberg, 2004. 15-25.

---
Tags: programming-languages, history, object-oriented
---


# Question
Title: Blockchain cipher suitable for preschoolers
Is there a cipher that well suited for preschool-aged children to work out on pencil and paper, to learn concepts of block chains?

It must have the following requirements:

1. Able to be easily verified
a. For example, Joe submitted red, but Suzy submitted blue. Everyone knows Suzy is right...somehow. (Color-specific results are not required but used to illustrate that the cipher need not be number-based, although that is fine too)
2. Able to be easily ciphered with pencil and paper, or drawings, or in a child's head
3. Able to use a previous result (minus the genesis of course), to create a 'blockchain' of sorts

The cipher may be low-complexity. It does not matter if it is easily broken.

Most ciphers are geared towards being easy to verify, but difficult to decipher. This situation is a bit different in that it does not have to be difficult to decipher. Out of the box ideas are quite welcome.

# Answer
> 3 votes
I'd suggest you don't try to create or use a cipher. Rather, I think maybe a more interesting way to view blockchain systems is as a log that is created through a distributed lottery.

So, in lesson one, you could describe how to keep track of something (account balances? something more relevant?) via a sequence of log entries written on the board. This would be a centralized scheme.

In lesson two, you can make it distributed. In each stage, have a lottery where you randomly pick one of the students to win the lottery. The winner of the lottery gets to write down the next log entry on the board. Everyone else watching can see whether that student did it correctly and fairly. If not, the next winner ignores the bogus stuff written on the board.

No cryptography is needed. You just need a way to randomly pick one student in the room, in a fair way. This could be done with numbered balls in a box, or any number of other ways.

# Answer
> 0 votes
Would a clock face fit the bill? The position of the hands on the clock is a "block", and you generate a new block in the chain by adding (optionally subtracting) some amount of time to it.

E.g.:

`e(x, prev) = (x + prev) % 12:00`

1. Suzy starts things with her "6": `e(6, 0:00) = 6:00`
2. Joe correctly submits "3": `e(3, 6:00) = 9:00`
3. Suzy correctly submits "5": `e(5, 9:00) = 2:00`
4. Everyone can tell that Joe isn't right when he says he submitted "1" and got 5:00 instead of 3:00

It's quite easy to reverse this "cipher", but is very simple and visual. You can also readily check if Suzy or Joe correctly submitted the right thing.

---
Tags: cryptography
---