# Question
Title: Generating constraints to solve dependently-typed metavariables?
In dependent-types, *Miller pattern unification* is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit arguments.

There are many papers which describe, given a unification problem in the pattern fragment, how to find a solution if one exists. Examples include are (Gundry-McBride), (Abel-Pientka), and the original Miller paper.

What I'm wondering is, given a dependently typed program containing metavariables (or implicit arguments), how does one go about generating the problems that are passed to the unification solver?

# Answer
> 7 votes
There's a nice idiom, which is explained more in chapter 22 of Types and Programming Languages (it's used for polymorphism rather than dependent types, but the idea is the same). The idiom is as follows:

> A type **checking** system can be turned into a **type inference** system by making the rules **linear** and adding **constraints**.

I'll use the application rule as an example. The **checking** rule in dependent types is this:

$$\frac{\Gamma \vdash t:\Pi x:A.B\quad \Gamma\vdash u:A}{\Gamma\vdash t\ u: B\[u/x\]} $$

**Linearizing** this rule requires re-naming the 2 occurrences of $A$, such that we obtain:

$$\frac{\Gamma \vdash t:\Pi x:A\_1.B\quad \Gamma\vdash u:A\_2}{\Gamma\vdash t\ u: B\[u/x\]} $$

But this isn't correct anymore! We need to add the **constraint** $A\_1\simeq A\_2$:

$$\frac{\Gamma \vdash t:\Pi x:A\_1.B\quad \Gamma\vdash u:A\_2}{\Gamma\vdash t\ u: B\[u/x\]}\quad A\_1\simeq A\_2 $$

Note that $\simeq$ denotes equivalence modulo your conversion relation ($\beta\eta$, typically), just like for the conversion rule, but it is now a **unification constraint**, since you may have meta-variables in your terms.

In the course of type checking, you'll accumulate constraints like these, to potentially solve them all at once at the end (or earlier for efficiency reasons).

Now things can get trickier, because the type of $t$ itself could be a metavariable in context! A more generally applicable rule would therefore be

$$\frac{\Gamma \vdash t:C\quad \Gamma\vdash u:A\_2}{\Gamma\vdash t\ u: B\[u/x\]}\ C\simeq \Pi x:A\_1.B,\ A\_1\simeq A\_2 $$

Or alternatively, keeping the previous rule and adding the rule

$$\frac{}{\Gamma\_1, x:C, \Gamma\_2 \vdash x: A} C\simeq A $$

at variable lookup time.

Another useful remark is that in the **checking** system, the conversion rule only needs to be applied right before applications, and possibly once at the very end of the derivation. Since this rules correspond to a unification constraint in the **inference** system, this tells you where to place the constraints.

# Answer
> 4 votes
If you model the lambda terms via deBruijn indexes and the meta variables via Prolog variables, you could build a Prolog constraint solver. Here is an example that works already quite well, the basic constraints that were used are as follows:

% shift(+Indexed, +Nat, +Nat, -Indexed)
% subst(+Indexed, +Nat, +Indexed, -Indexed)
% reduce(+Indexed, +Indexed, -Indexed)
https://gist.github.com/jburse/0ccd12698bfa24ce5c36#file-implicit2-p

The whole machinery also assumes that we strive for normal forms, in that we beta reduce in a certain order. There is an interaction between the normalizer and how new constraints above are generated. Since reducing a redex might require reevaluation of the normalization.

The constraint solver already implements a couple of cross constraint simplifications, without these simplifications and only constraint delay, the constraint solver would be too dumb and not practically usuable. We are still planning to add one or two more simplifications. A trove for simplifications is the following paper:

Residual Theory in λ-calculus
A Formal Development, Gerard Huet, 1998
http://pauillac.inria.fr/~huet/PUBLIC/residuals.pdf

In the paper one finds also the original inductive definitions of the constraints that we were using. See the following sections:
2.2 Lifting
2.3 Substitution
3.1 One-step β-reduction

**Warning:** The deBruijn terms help us in equality of normal terms, we do not need any step for alfa conversion. But we use a non-leveled dependent type, so for example there is no distinction between types and kinds under the hood. This makes the whole venture especially simple, on the other hand this is non-standard.

Bye

---
Tags: reference-request, lambda-calculus, type-theory, dependent-types, unification
---


# Question
Title: Select a subset of the columns in $3\times n$ matrix, is it NP-hard?
I want to know if this problem is NP-hard?

*The problem:* Given a non-negative integer-valued matrix of size $3\times n$ of the form

$$ \begin{bmatrix} a\_1 & \ldots & a\_n\\ b\_1 & \ldots & b\_n\\ a\_1b\_1 & \ldots & a\_nb\_n\\ \end{bmatrix}, $$

where $a\_i,b\_i$ are non-negative integers. Given four non-negative integer numbers $b\<n$, $c\_1$, $c\_2$ and $c\_3$.

*The goal*: Find a subset of the columns of cardinality at most $b$ such that (i) the sum of the first row over the subset of the columns is greater than $c\_1$, (ii) the sum of the second row over the subset of the columns is greater than $c\_2$ and (iii) the sum of the third row over the subset of the columns is less than $c\_3$. Return no if no such subset exists. That is to say, is there exists a set $S$ of cardinality at most $b\<n$ such that:

$$ \sum\_{i\in S}a\_i\geq c\_1,\\ \sum\_{i\in S}b\_i\geq c\_2,\\ \sum\_{i\in S}a\_ib\_i\leq c\_3, $$

How to show that this problem is NP-hard?

---

Attempt:

Here is a "similar" NP-hard problem that I asked. This problem has as instance $(n,b,c,\mathbf{A})$ where $\mathbf{A}$ is given by $$ \begin{bmatrix} x\_1 & \ldots & x\_n\\ y\_1 & \ldots & y\_n\\ \end{bmatrix}, $$ I tried to reduce the previous problem to the new one as follows: choose $c\_1=c\_2=c$ and choose $c\_3$ very big and create the matrix as follows:

$$ \begin{bmatrix} x\_1 & \ldots & x\_n\\ y\_1 & \ldots & y\_n\\ x\_1y\_1 & \ldots & x\_ny\_n\\ \end{bmatrix}, $$

# Answer
Your problem is NP-complete, indeed. You can, e.g., reduce PARTITION to your problem. If you want to know if there is a subset of the set $\\{d\_1,\ldots,d\_k\\}$ that sums up to exactly $D := \frac{1}{2} \sum\_{i=1}^k d\_i$, you can use your problem by setting $b\_i := 1$ and $a\_i := d\_i$ for all $i$ and by setting $c\_1 := D$, $c\_2 = 0$, and $c\_3 := D$ as well as $b := n-1$.
> 4 votes

---
Tags: reductions, np-hard
---


title: basic doubt on policy iteration

text:
# Question
Title: basic doubt on policy iteration
consider the policy iteration algorithm for a finite state MDP. Suppose the initial policy is a stochastic policy. Now, can the optimal policy be deterministic after improvements ? Or, can we say that always the optimal policy will be a stochastic one ? Confused about this. Any ideas will be helpful. The reason I am asking this question is that in the absence of model i.e. when we need to need to use Monte Carlo methods then each of the improved policies must be a stochastic one to make sure action-value function estimates are near equal to the mean.

# Answer
> 1 votes
A stochastic policy can perfectly represent a deterministic policy by assigning probability 1 to a unique action.

Depending on how you are adjusting the policy it might take time to converge into a deterministic one, however it can get there in the limit.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: What edge-set is required to make a non-cyclic directed disconnected graph initial?
Is there an algorithm to find the minimum set of edges required from a new node in order to make a disconnected directed graph initial?

Example -

input:

```
a -> b;
b -> c;
b -> d;
e -> f;
f -> g;

```

output:

```
n -> a;
n -> e;

```

Result:

Thanks!

# Answer
> 0 votes
Assuming that "initial" means connected and having a single source, you can do no better than adding an edge to each source.

---
Tags: graphs
---


title: Rank of random binary matrix subset

text:
# Question
Title: Rank of random binary matrix subset
I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's equivalent to some spanning tree-like problem. The problem is as follows.

We have some binary matrix $M \in \mathbb{F}\_2^{n\times k}$ with rank $n$. Let $S\_i$ be the matrix constructed by sampling the rows of M $i$ times without replacement. I would like to find

* the expected rank of $S\_i$
* a vector $x \in \mathbb{F}\_2^k$ such that appending $x$ to $M$ prior
to sampling will maximize the expected rank of $S\_i$.

Any ideas on sources that cover similar problems would also be appreciated.

# Answer
> 3 votes
The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $S\_i$.

Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though.

---
Tags: linear-algebra
---


title: Pseudo-random sequence prediction

text:
# Question
Title: Pseudo-random sequence prediction
> Disclaimer: I am a biologist, so sorry for (perhaps) basic question phrased in such crude terms.
>
> I am not sure if I should ask this question here or on DS/SC, but CS is the largest of three, so here goes. (After I posted, it occurred to me that Cross-Validated might be the better place for it, but alas).

Imagine there is an agent, who makes binary decisions. And an environment, which, for each of the agent's decisions ("trials"), either rewards the agent or not. The criteria for rewarding the agent's decisions are not simple. In general criteria are random, but they have limitation, for example, environment never rewards more than 3 times for the same decision and never alternates rewarded decision more than 4 times in a row.

Sequence of criteria might look something like this then

```
0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 ...

```

but never

```
0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 ...

```

because reward criterion cannot repeat more than 3 times.

In these conditions it is quite easy to formulate the strategy ideal observer should undertake to maximize the reward. Something along the lines of

1. decide randomly
2. if you detect that criteria repeated 3 times -- decide opposite than last criterion
3. if you detect that criteria alternated 4 times, decide according to the last criterion

Now, the difficult part. Now the criterion on each trial depends not only on the history of previous criteria, but also on the history of agent's decisions, e.g. if agent alternates on more than 8 out of the last 10 trials, reward same decision as agent made last time (as if to discourage the agent from alternating) and if agent repeated same decision on more than 8 of the the last 10 trials, i.e. he is biased, make criterion opposite of the bias. The priority of history of criteria over history of decisions is specified in advance, so there is never ambiguity.

The sequences of decisions (d) and criteria (c) might now look like this

```
d: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 ...
c: 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 ...
                       ↑ here criteria counteract bias in decisions

```

I do not see any simple way of inventing maximizing strategy for the agent. But I am sure there must be one, and some kind of clever machine learning algorithm should be able to identify it.

My question is not so much about how to solve this problem (although I would be happy if you suggest a solution), but more how these types of problems are called? Where can I read about it? Is there an abstract solution or only simulation can help? In general, how can I, as a biologist, approach this type of problem?

# Answer
You can approach this problem using Reinforcement Learning.

A classic book for this is Sutton and Barto:

The draft of the second edition is available for free: https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

In order to make your problem Markovian, define each state as a vector of the last ten decisions. You actions will be 1 or 0.
> 1 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: Algorithm: Finding shortest path through a dungeon in a game
## Background

I was playing the PC-Game "Darkest Dungeon" recently. In the game, you have to explore dungeons, which consist of connected rooms as shown in the picture below.

Here are the rules:

* You start in fixed room (Entrance). You cannot choose where to start.
* The goal is to **visit every room at least once**
* The distance between adjacent rooms is the same for all rooms.
* You can visit rooms and walk paths as often as you'd like

## Question

What is the shortest path from the entrance that visits every room at least once?

Subquestions:

* What algorithm(s) could be used to solve this problem?
* Are there implementations that are free (and fairly simple) to use for someone like me?

## What I tried

I have found other questions such as this or this without finding an answer. I am familiar with the (basic) TSP and are able to code and solve simple TSPs. Hamiltonian paths didn't solve my problem, because it doesn't allow for multiple visits. The Chinese postman problem does also not apply here in its basic form because I don't have to visit every edge.

## Update

As I have stated in the comments, I'm not a computer scientist and am not interested in proving a mathematical statements (maybe I'll post this question on stackoverflow at a later stage). Also, I'm not a programmer and the chances that I'm able to code a solution myself are pretty slim. But I suspect I'm not the first one dealing with a problem of that nature.

According to @Shreesh and @Dib, the following procedure could be applied:

1. Create a pairwise distance matrix with all rooms thus adding edges between all rooms.
2. Solve TSP using a standard solver (e.g. concorde)
3. Starting from the Entrance, visit all rooms according to the solution. For non-adjacent rooms, substitute the shortest distance between those rooms.

Will this procedure provide the answer to the problem?

# Answer
> 4 votes
Travelling Salesman Problem, even if you allow repeating nodes is NP-hard. See Computational Complexity of TSP.

Umans and Lenhart show hardness results for Hamiltonian Graphs in Solid Grid Graphs, 1997.

TSP for Euclideal Case (or graphs with triangle inequality) also imply NP-hardness of TSP with node repetition. TSP even for manhattan distance $L\_1$ (or $L\_\infty$) metric is NP-complete. See the original Papadimitriou's paper on the topic.

You may be able to prove NP-hardness of TSP for your case by adding arcs to nodes that have corresponding distance as length of shortest path between nodes which will simulate repetitions of the nodes. TSP for your special case looks like an NP-complete problem.

So either write a sufficiently good (heuristic wise) exponential branch and bound algorithm to compute a shortest tour (which may not be all that inefficient, if your graph is small) , or forget about optimization and calculate a good enough approximation.

# Answer
> 3 votes
You can treat this like a modified path coverage planning problem that you can solve in a few simple steps:

1) Construct an unweighted undirected graph from the grid- rooms, path junctions are nodes, and edges the paths between those nodes.

2) Find the minimum spanning tree from your start point using depth first search.

3) "Subdivide" the underlying grid so that your minimum spanning tree creates two "lanes".

4) From your starting point walk clockwise in the right-hand lane from node-to-node until you return to the starting point in the complementary lane.

This will give you a minimal tour of the rooms, in time proportional to the number of tiles in the dungeon, and is essentially the Spiral Spanning Tree Coverage path planning algorithm applied to a reduced setting. (Cf. "Spiral-stc: an on-line coverage algorithm of grid environments by a mobile robot")

# Answer
> 1 votes
In addition to the above answer, I would point out some TSP solvers already available.

1. Concorde TSP Solver
2. TSP solver provided by Stony Brooks University
3. TSP solver using Google Direction API
4. And Many more.

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


# Question
Title: How do cycles of non-consuming transitions in NFAs influence their halting properties?
I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which consume a symbol of the language or a *lambda* transition which does not consume a symbol from the string.

One thing that was mentioned is that languages defined by NFAs are regular, and thus can be parsed in constant time (since strings are finite). We then went through the basic pathfinding sort of algorithm where we try paths until we find one that consumes the entire string and if one path completely consumes the string and ends in an accept state - hurray.

Now, if there is a non-consuming transition from one state to itself, or another non-consuming loop in the NFA, that algorithm wouldn't halt.

Are those sorts of loops explicitly forbidden? Is halting not a required property of NFAs? Where is the disconnect in my understanding?

# Answer
> 2 votes
No, the $\lambda$-loops you talk about are not forbidden. But they do mean one has to be careful.

The actual way to determine if an NFA accepts its input is as follows. Note that this takes linear time in the length of the input, not constant time as you say in the question. First, for each state $q$ of the automaton, use a graph reachability algorithm to compute the set of states $\Lambda(q)$ that can be reached from $q$ using only $\lambda$-transitions. For a fixed automaton, with a fixed number of states and fixed transition function, this can be done in constant time. Note that $q\in\Lambda(q)$ for every $q$, since you can reach $q$ from itself by doing some number of $\lambda$-transitions: specifically, that number is zero. This means that $\lambda$-transitions from a state to itself are completely harmless.

To determine whether the automaton accepts its input, we just keep track of the set of states that the automaton "might" be in after reading each successive character of the input. Initially, it could be in any state in $\Lambda(q\_0)$. If, after reading some characters, it could be in any state in $S\subseteq Q$ then, when it reads character $a$, it could be in any state in $\Lambda\Big(\bigcup\_{s\in Q}\delta(s,a)\Big)$. It accepts if, at the end of the computation, the set of states it might be in includes at least one accepting state. Note that, at any time, the set of states the automaton could be in is bounded by the fixed constant $|Q|$ so all the manipulations needed on the set of possible states can be done in constant time per character the machine reads, independent of the length of the input.

# Answer
> 0 votes
1. The complexity for parsing a string is at least the length of the string( hence not constant).
2. The loops are not forbidden and halting is a required property. See this for the details of the definition of $NFA$.
3. It is possible to show that, any $NFA$ having $\lambda$-transitions can be converted to a $DFA$ (which by definition has no $\lambda$-transition) accepting the exact language as the $NFA$. Since $DFA$ always halts and the conversion of NFA to DFA can be done, it is safe to say that $NFA$ always halts.

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


title: Big-O Justification Question

text:
# Question
Title: Big-O Justification Question
I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n\_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so long as it is a real number and less than the right side? For instance, is the following valid: $$n^2/4 + 1/2 \leq c\cdot n^2\\,,$$

when $c= 1$ and $n=1$: $$3/4 \leq 1\\,.$$

# Answer
> "The Big-O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions."-Wikipedia

If you see the formal definition, then the only restriction is that the domain of functions must be $\mathbb{R}$. Hence, by definition the range of the functions can at least be any vector space. In the most common use in CS, the range of the functions is also taken to be $\mathbb{R}^+$.

To answer your question, by definition, the left side can be any real positive value.
> 1 votes

# Answer
No such restriction is required. To satisfy Big-O notation you have to find out a constant c \> 0 and $n\_0$ such that $f(n) \le c g(n)$ for all $n \ge n\_0$. The only assumption is $f$ and $g$ are functions such that $f, \ g : N \rightarrow R^+$.
> 1 votes

---
Tags: asymptotics, proof-techniques, landau-notation
---


title: Matrix of Matrices in Python

text:
# Question
Title: Matrix of Matrices in Python
I want to create a matrix where each entry itself is a random matrix. What would be a good way to represent this?

It is not necessary but some hints on how to implement your proposed solution in Python would be useful.

# Answer
> 1 votes
What you are looking for is just a higher dimensional array.

Let's say you want a 5x5 array where each element is a 2x2 array with random number. You can easily represent that as a 5x5x2x2 array.

If you are happy about using numpy

```
A = numpy.random.rand(5,5,2,2)

```

Will create a 5x5x2x2 array.

You can use the first two indexes to access your 2D random arrays.

```
print A[1,1]

```

Results in:

```
[[ 0.68527006  0.37304491]
 [ 0.23281899  0.46951261]]

```

---
Tags: programming-languages, matrices
---


# Question
Title: Use max operation in a constraint in Linear Programming
I have liner programme with set of $x\_{3n}$ variables where $x\_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve.

Using these variables, I want to form following constraint :

$max(x\_1 , x\_2.., x\_n) + max(x\_{n+1} , x\_{n+2}.. , x\_{2n}) + max(x\_{2n+1} , x\_{2n+2}..., x\_{3n}) \>= q$

Constraint is : Sum of *max variable* in set of variables should be greater than *q*.

How can I write constraint using $max$ operation in LP Solve?

# Answer
> 3 votes
Introduce variables $m\_1,m\_2,m\_3$ to represent the three maxes.

Add the linear inequality $m\_1 + m\_2 + m\_3 \ge q$.

Then, add the following extra inequalities for $m\_1$:

* $0 \le m\_1 \le 1$
* $m\_1 \le x\_1 + x\_2 + \dots + x\_n$
* $x\_1 \le m\_1$, $x\_2 \le m\_1$, $\dots$, $x\_n \le m\_1$

and similarly for $m\_2$ and $m\_3$.

---
Tags: linear-programming, integer-programming
---


title: Information about ε-greedy algorithms

text:
# Question
Title: Information about ε-greedy algorithms
I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms and a little explanations about it?

# Answer
ε-greedy is just a way to promote exploration in Reinforcement Learning. I would not classify SARSA or Q-Learning as ε-greedy algorithms.

The latter are very common reinforcement learning algorithms and you can definitely can find lots of material about them.

I would suggest to have a look at this classic book (the draft for the second edition is available for free)

https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Another shorter and excellent resource is (have a look at chapter 21):

*Russell SJ, Norvig P, Davis E. Artificial intelligence: a modern approach. Upper Saddle River, NJ: Prentice Hall; 2010.*

EDIT:

The paper you posted is using SARSA(λ), it is not the same as SARSA. You will need to go through a few Sutton chapters for that to make sense. You won't find it in Russell.

The link to SARSA(λ) in Sutton (1998) HTML version is here: webdocs.cs.ualberta.ca/~sutton/book/ebook/node77.html

However, I think you will need to read at least chapter 6 before jumping into eligibility traces
> 4 votes

---
Tags: algorithms, reference-request, artificial-intelligence, greedy-algorithms
---


# Question
Title: Validate that a threaded binary tree works as intended
I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended.

Would it be safe to assume that the following procedure would have tested all corner cases at least once?

I have an array of integer S = {1, 2, …, n-1, n} for n = 1’000’000. I then randomize the order of S to obtain S’ and S\*. S’ is then used to insert its elements sequentially, into the tree. After all elements are inserted, I create an in order list of the tree, say A, and confirm that A = S. This concludes the insert test.

For deletion, I pass elements of S\* sequentially as argument to be removed from the tree, testing that each call was successful. After all elements was removed I confirm that the tree is empty.

# Answer
Shortly - no, it is not safe.
Huge random test does not guarantee success (but of course, when there is a bug, it finds it in the most cases).
To test threaded tree with deletion and insertion you need to have saturated all nodes (with thread links), make them change thread, the same for deletion.
To make sure it works all corner cases must be covered both for insertion and deletion. With huge input there is huge probability it works, but this is not conclusive. Also making more passes (more test) it increases probability of success, but nothing more.

To test it manually - case by case - you do not need very big tree (I did tests on double threaded AVL, tree height was maximally 5).
> 1 votes

---
Tags: data-structures, binary-trees, search-trees, correctness-proof, software-testing
---


# Question
Title: A condition ensuring that a bipartite graph have a perfect matching
There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From this, how can I prove there is matching which covers all of $A$?

# Answer
Hint: Use Hall's criterion.

In more detail, suppose that Hall's criterion didn't hold. Choose a set $X$ of minimal size satisfying $|N(X)| \< |X|$. Show that $X$ is not empty, and let $Y = X \setminus \\{x\\}$ for some arbitrary $x \in X$. Show that $Y$ has a perfect matching with $N(Y)$, and prove that $N(N(Y))=Y$ by counting the edges connecting $Y$ and $N(Y)$ in two ways. Show that $\emptyset \neq N(x) \subseteq N(Y)$, and reach a contradiction.
> 1 votes

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


title: What are predicates of a sentence?

text:
# Question
Title: What are predicates of a sentence?
I am reading *Handbook of Satisfiability* in which they say:

> An algebraic structure, or simply structure, consists of a non-empty set of objects existing in the world $w$, called the domain and denoted below by $D$, and a function, called an interpretation and denoted below by $R$, that assigns to each constant an entity in $D$, to each predicate a relation among entities in $D$, and to each functor a function among entities in $D$.
>
> A sentence $p$ is said to be true in $w$ if the entities chosen as the interpretations of the sentence’s terms and functors stand to the relations chosen as the interpretation of the sentence’s predicates.

In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?

I am not a native English speaker, maybe this is why I can not understand this claim.

# Answer
> 5 votes
Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} \[\\!\[ {\sf cat} \]\\!\]^c = 5 \\ \[\\!\[ {\sf tuna} \]\\!\]^c = 4 \\ \[\\!\[ {\sf squirrel} \]\\!\]^c = 2 \\ \ldots \\ \[\\!\[ {\sf head} \]\\!\]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ \[\\!\[ {\sf eats} \]\\!\]^p = \\{ \langle x , y \rangle \ |\ x \< y \\} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $\[\\!\[-\]\\!\]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $\[\\!\[-\]\\!\]^f$. Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $\[\\!\[-\]\\!\]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ \[\\!\[ {\sf eats} \]\\!\]^p (\[\\!\[ {\sf cat} \]\\!\]^c, \[\\!\[ {\sf head} \]\\!\]^f(\[\\!\[ {\sf tuna} \]\\!\]^c)) $$ which is $$ \< (5, g(4)) $$ i.e. $$ 5 \< \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be *satisfiable*: there is some structure which makes it true.

---
Tags: terminology, logic
---


# Question
Title: What the length of instructions on these processors will be?
Let's say we have two computers with identical ISA, but different size of word in main memory. One is 32 bit and the other 64 bits. So will it be identical length of instruction, different, depends on memory or depends on cache memory and why ?

# Answer
If the ISA is the same, the registers and instructions have the same size.

A CPU can have 32, 64 or wider busses for caches, external memory.

It has no relation with the size of instructions.

It has no relation with the size of integer registers.

You can see variants or extension of the same ISA with 64 bits support : MIPS III, SparcV8 vs SparcV9, x86 vs AMD64, ARMv7 vs ARMv8, Power32 vs PowerPC64, etc... The new instructions are either handled as a different mode, or using different opcodes.

The "size of word" is a term for compilers and programmers (int, long int, long long int...), not for hardware.

Of course, it makes little sense to tie a 64bits bus to a 8bits CPU, or the inverse.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Master Theorem Case 3 Regularity Condition
In case 3 of the master theorem, we have to show that

$$ af(n/b) \leq cf(n). $$

I don't understand how I can setup this formula. As an example, we have

$$ T(n)=3T(n/4) + n \lg n.$$

In this case $a=3$ and $b=4$. This gives us $O(n^{0.793})$ which is smaller than $f(n) = n \lg n$ which means case 3.

Now, the solution is:

$$af(n/b)= 3(n/4) \lg(n/4) \leq (3/4)n\lg n.$$

I'm not sure how we got the above? $af(n/b)$ in my book is $3(n/4)$ so where does $\lg(n/4)$ come from? Also, since $f(n)$ is $n \lg n$, shouldn't the evaluation be:

$$3(n/4) \leq n \lg n ?$$

# Answer
> 1 votes
If $f(n) = n\lg n$ then $f(n/b) = (n/b)\lg(n/b)$, and so $af(n/b) = a(n/b)\lg(n/b)$.

---
Tags: algorithms, master-theorem
---


# Question
Title: what are read/write operations involved in main memory, cache and processor?
please bear with me, I always get confused with the terminologies used in my computer architecture class.

What are **read** and **write** operations exactly? What are their relationship with processor, main memory, and cache?

I always thought that **load/store** are interchangeable with **read/write**...

What about the **modify** operation?

# Answer
> 1 votes
**Read** is the same as **load**, and **write** is the same as **store**. **Modify** is a combination of both.

---
Tags: computer-architecture
---


# Question
Title: If I write code in machine language, then I have access to the CPU in both modes (user and kernel), since the OS is bypassed, correct?
Codes written in machine language can have access to both CPU modes (Kernel and user), since the OS is bypassed, correct?

# Answer
No. The Operating System is going to use context switching and virtual memory to hide the fact that there are multiple processes running on the computer. Native code does not mean you have full control to the CPU registers, global physical memory. Your program, if not privileged, is still running in user mode. You need to use syscalls to do lower level tasks. The operating system provided a virtual and abstract environment for the program to make them convince themselves they are running on a dedicated machine.
> 7 votes

---
Tags: os-kernel, cpu
---


# Question
Title: Compactly representing integers when allowed a multiplicative error
Consider the problem of representing in memory numbers in the range $\\{1,\ldots,n\\}$.

Obviously, exact representation of such number requires $\lceil\log\_2(n)\rceil$ bits.

In contrast, assume we are allowed to have compressed representations such that when reading the number we get a 2-approximation for the original number. Now we can encode each number using $O(\log\log n)$ bits. For example, given an integer $x\in\\{1,\ldots,n\\}$, we can store $z = \text{Round}(\log\_2 x)$. When asked to reconstruct an approximation for $x$, we compute $\widetilde{x} = 2^z$. Obviously, $z$ is in the range $\\{0,1,\ldots,\log\_2 n\\}$ and only requires $O(\log\log n)$ bits to represent.

> **In general, given a parameter $\epsilon\>0$, what is the minimal number of bits required for saving an approximate representation of an integer in the above set, so that we can reconstruct its value up to a multiplicative error of $(1+\epsilon)$?**

The above example shows that for $\epsilon=1$, approximately $\log\log n$ bits are enough. This probably holds asymptotically for every *constant* $\epsilon$. But how does epsilon affect the memory (e.g., does it require $\Theta(\frac{1}{\epsilon^2}\log\log n)$ bits?).

# Answer
Storing $x$ to within a $1+\epsilon$ approximation can be done with $\lg \lg n - \lg(\epsilon) + O(1)$ bits.

Given an integer $x$, you can store $z = \text{Round}(\log\_{1+\epsilon} x)$. $z$ is in the range $\\{0,1,\dots,\log\_{1+\epsilon} n\\}$, so requires about $b = \lg \log\_{1+\epsilon} n$ bits. Doing a bit of math, we find

$$b = \lg \frac{\lg n}{\lg(1+\epsilon)} = \lg \lg n - \lg \lg (1+\epsilon).$$

Now $\lg(1+\epsilon) = \log(1+\epsilon)/\log(2) \approx \epsilon/\log(2)$, by a Taylor series approximation. Plugging in, we get

$$b = \lg \lg n - \lg(\epsilon) + \lg(\log(2)),$$

which yields the claimed answer.
> 3 votes

---
Tags: integers, coding-theory, encoding-scheme
---


# Question
Title: Calculating attributes' values in the semantic analysis stage
I'm reading through the book : "Compiler Construction: Principles and Practice". In chapter 6 : semantic analysis, an example about attribute grammars is given. The example is of a simple integer arithmetic expressions (I posted a picture because different fonts means different things as you may know):

where the bold Courier font is a token and the Times New Roman is grammar.

Now this parse tree represents the expression: (34-3)\*42 which is 1302. I know that every attribute rule corresponds with a grammar rule, and we're actually starting with the rule exp-\>term because it is what it fits the given expression, but I just don't understand how did the compiler know the value in the first place? When was the value computed? How does the compiler start implementing the semantic analysis? did it start from the bottom where the **number** token is? I hope I made it clear.

# Answer
> 3 votes
The computer is using the rules in the left-hand column of your table. This amounts to a bottom up approach: to compute the value of a node you first compute (recursively) the values of all its children, and then you use the given rule to compute the value of the node itself.

---
Tags: compilers, static-analysis, attribute-grammars
---


title: Number of addresses in a memory region

text:
# Question
Title: Number of addresses in a memory region
So I am looking at some Operating Systems exercises and we have

> A swapping system eliminates holes by compaction. Assuming a random distribution of many holes and many data segments and a time to read or write a 32-bit memory word of 10 nsec, about how long does it take to compact 128 MB? For simplicity, assume that word 0 is part of a hole and that the highest word in memory contains valid data.
>
> The solution is : `128 x 2^20 / 4 = 2^25` memory address
>
> ```
>       compaction time = (read + write) * # of memory access
>                       = 2 x 10 x 10 ^ -9 x 2^25
>                       = 671 ms
>
> ```

Problem is I dont understand the `128 x 2^20 / 4 = 2^25 memory address` part ? How did we get 2^20 in this case? I gues the 4 is 4 bytes =32 bits so I kinda understand that.

Now in `2 x 10 x 10 ^ -9 x 2^25` what is 2 here?

# Answer
> 3 votes
A megabyte is $2^{20}$ bytes.

The factor of $2$ is because we need to count both reads and writes.

---
Tags: memory-management, virtual-memory
---


# Question
Title: Attribute grammars: How are attributes implemented?
I've read about attribute grammars, but I haven't found out, how are the attributes often implemented?

To me they scream objects (of classes), but they could be also variables.

But are there any general rules as to how the attributes should be implemented in a practical implementation? Or is it free form?

# Answer
Attribute grammars are a *conceptual* tool. You are mixing this up with *implementation* details.

There are many parser generators around (check for example the Wikipedia pages on compiler compilers and comparison of parser generators). They all implement some flavor of attribute grammar, in actual use you aren't interested in a parse tree or a derivation. The most used ones are (direct descendants of) old designs, which predate the current object oriented craze, and write parsers implemented in languages like C, with no objects.
> 3 votes

# Answer
I do not know any specific implementations, but here are two ideas a annotate nodes w.r.t an attribute grammars:

1. A recursive algorithm can evaluate top-down and bottom-up rules in two passes over the tree.

You may want to implement it using the visitor pattern
2. Use the iterator pattern.

Note that the order of iteration is crucial -- decide between pre-, in- and post-order. In order to do emulate the recursive approach you need (at least) pre- and post-order, one after the other.
> 1 votes

---
Tags: compilers, attribute-grammars
---


title: Storage cost of a suffix array

text:
# Question
Title: Storage cost of a suffix array
MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?

# Answer
You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.
> 3 votes

# Answer
You store only the position of suffixes in the index, not the suffixes themselves. So the storage complexity is O(n) for the index. You then have to keep the original string along with the suffixes array. The original string storage complexity is O(n) also by definition.
The whole storage complexity remains O(n).
> 1 votes

---
Tags: data-structures, strings, substrings, suffix-array
---


# Question
Title: Complexity of an algorithm with multiple inputs
I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$.

But what about when the complexity depends on several inputs? For example if an algorithm has complexity $O(n^2k)$, is it 'cubic', or maybe 'quadratic in $n$ and linear in $k$'?

I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

# Answer
\[If I have time, I'll answer the rest of the question later.\]

> I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

It's vague, unfortunately, and you should avoid writing anything like this, ever. It means at the very least, that the complexity depends somehow on $k^3$ and $n^3$ but I'm sure you'd already figured that out. Beyond that, it's impossible to say much. It's unclear whether it's some function of $k^3+n^3$ or some function of $k^3n^3$ or something else. It's also unclear whether they're talking about an upper bound or a lower bound: if I told you that a recipe needs a kilo of potatoes, you'd assume that was an upper bound, but if I told you that a restaurant needs kilos of potatoes, you'd assume a lower bound.
> 3 votes

---
Tags: algorithm-analysis, landau-notation
---


# Question
Title: what is difference between multilayer perceptron and multilayer neural network?
When do we say that a artificial neural network is a *multilayer Perceptron*?

And when do we say that a artificial neural network is a *multilayer*?

Is the term *perceptron* related to learning rule to update the weights?

Or It is related to neuron units?

# Answer
A perceptron is always **feedforward**, that is, all the arrows are going in the direction of the output. Neural networks in general might have loops, and if so, are often called *recurrent networks*. A recurrent network is much harder to train than a feedforward network.

In addition, it is assumed that in a perceptron, all the arrows are going from layer $i$ to layer $i+1$, and it is also usual (to start with having) that all the arcs from layer $i$ to $i+1$ are present.

Finally, having *multiple layers* means more than two layers, that is, you have *hidden* layers. A perceptron is a network with two layers, one input and one output. A multilayered network means that you have at least one hidden layer (we call all the layers between the input and output layers hidden).
> 23 votes

# Answer
> When do we say that a artificial neural network is a multilayer Perceptron?

Artificial neural network, which has input layer, output layer, and two or more trainable weight layers (constisting of Perceptrons) is called multilayer perceptron or MLP.

> And when do we say that a artificial neural network is a multilayer?

You can say it is a multilayer network, if it has two or more trainable layers.

> Is the term perceptron related to learning rule to update the weights?

No. There are many different learning rules, that can be applied to change weights in order to teach perceptron. Term perceptron does not entail any specific learning rule by itself.

> Or It is related to neuron units?

Not sure what you mean by this.

You can read more in this free book http://www.dkriesel.com/\_media/science/neuronalenetze-en-zeta2-2col-dkrieselcom.pdf
> 3 votes

# Answer
From Wikipedia:

> In the context of neural networks, a perceptron is an artificial neuron using the Heaviside step function as the activation function.

So the perceptron is a special type of a unit or a neuron. Hence multilayer perceptron is a subset of multilayer neural networks.
> 1 votes

---
Tags: neural-networks, perceptron
---


# Question
Title: What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$
Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n\_j = T\[j\]$ be the size of the chain for entry $j$. In this case the definition of the load factor should be:

$$ \mathbb{E}\[n\_j\] = \mathbb{E}\[T\[j\]\] = \alpha = \frac{n}{m}$$

I was wondering, why is the above statement correct under the Simple Uniform Hashing (i.e. the probability that any given element is equally likely to hash into any of the $m$ slots or in equations $Pr\[h(k\_i) = h(k\_j)\] = \frac{1}{m}$)? In particular, I find it difficult to understand what exactly distribution (or what random variables to define) in order to compute the expectation. What distribution is the expectation taken over with respect to?

CLRS talks about this on page 259 but they never quite explain in detail why it is $\frac{n}{m}$ or ignore (leave out) the probabilistic analysis.

---

After some thinking I realized that $n\_j$ is a random variable and it depends on how the hash function $h$ distributes keys (and I guess also in the keys one might get). So a realization of $n\_j$ will be in the set $\\{ 0, ..., m-1 \\}$, since the table can only have a $0$ elements up to $m$ elements. Hence to calculate the expected length of $n\_j$ we compute:

$$\mathbb{E}\[n\_j\] = \sum^{m-1}\_{x=0} x \Pr\[n\_j = x\]$$

but my question is, how does one determine the distribution for $x$?

# Answer
The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest way to calculate it, and it's true even if the SUHA doesn't hold.

But since you asked, let's look at the distribution of the chain lengths.

Suppose you're putting $n$ pigeons into $m$ pigeonholes at random. Examine one pigeon hole (say, pigeonhole number 1). The number of pigeons that are assigned to this pigeonhole follows a binomial distribution; the probability that there are $k$ pigeons in that particular pigeonhole is ${n \choose k} p^k (1-p)^{n-k}$ where $p = \frac{1}{m}$.

So the expected number of pigeons in that pigeonhole is:

$$\sum\_{k=0}^{n} k {n \choose k} p^k (1-p)^{n-k}$$ $$= \sum\_{k=0}^{n} np {{n-1} \choose {k-1}} p^{k-1} (1-p)^{n-k}$$ $$= np \sum\_{k=0}^{n-1} {{n-1} \choose {k}} p^k (1-p)^{n-1-k}$$ $$= np \left(p + (1-p)\right)^{n-1}$$ $$= \frac{n}{m}$$

By the way, if we want to reason about the number of chains of length $k$ in a hash table, for large enough $m$, it's well-approximated by a Poisson distribution.

The expected proportion of hash slots with chain length $k$ is:

$$\hbox{Pr}(\lambda,k) \approx \frac{e^{-\lambda} \lambda^k}{k!}$$

where $\lambda$ is the load factor. Note that $\lambda$ is also the mean of a Poisson distribution, so once again, the expected value of the chain length is the load factor.

You can learn a lot from this. For example:

* If the load factor is 1, the expected proportion of hash chains of length 0 and the expected proportion of hash chains of length 1 are both $\frac{1}{e}$.
* If you have a hash table with $m$ slots, there is a 50% chance of a collision after you insert $\sqrt{m}$ items. (Exercise: prove this!)
> 3 votes

# Answer
This has nothing to do with any property of the hash function. Rather, $$\mathbb{E}\[n\_j\] = \frac{1}{m} \sum\_{j=1}^m n\_j = \frac{1}{m} \cdot n = \frac{n}{m}.$$ (This is under the assumption that by $\mathbb{E}\[n\_j\]$ you mean the expectation of $n\_j$ over uniformly chosen $j$.)
> 2 votes

# Answer
We want to calculate the expected length of a chain using SUHA (evenly distributed keys). Denote the length of a specific slot $j$ to be $N\_j$. The length of this chain depends on how many of the $n$ keys that we hash, are successful to go to that slot. So lets count how many times a element goes to that slot with an indicator variable:

$$ X\_i= \begin{cases} 1, \text{if ith key goes to slot } j\\ 0, \text{otherwise} \end{cases} $$

Therefore we can express the length of a chain with respect to this indicator variable as follows:

$$N\_j = \sum^n\_{i=1} X\_i$$

now we can just ask what is the expected value of the variable above:

$$ \mathbb{E} \[ N\_j \] = \mathbb{E} \[ \sum^n\_{i=1} X\_i \]$$

by linearity of expectation we have and that the expectation of an indicator r.v. is its probability we have:

$$ \sum^n\_{i=1} \mathbb{E} \[ X\_i \] = \sum^n\_{i=1} Pr\[ X\_i = 1 \]$$

and using the SUHA i.e. $Pr\[h(k\_i) = j\] = \frac{1}{m} $ for all slots $j \in \\{0,...,m-1 \\} $ we get:

$$ \sum^n\_{i=1} Pr\[ X\_i = 1 \] = \sum^n\_{i=1} \frac{1}{m} = \frac{n}{m} $$

as required. This analysis holds for any slot $j$, so they all have the same expected length.
> 2 votes

---
Tags: algorithm-analysis, probability-theory, hash, hash-tables, hashing
---


# Question
Title: Proof that {(M,w) | M accepts a prefix of w} is RE
Can someone help me go over that the following language can be recognized by a Turing Machine?

$$L = \\{\langle M,w\rangle \mid M \text{ accepts a prefix of } w\\}$$

We can construct a universal Turing Machine $U$ that recognizes $L$. $U$ can be constructed as follows:

$U$: On input $\langle M,w\rangle$

1. Simulate $M$ on $w$.
2. If M accepts, $U$ accepts. Otherwise, $U$ rejects.

This seems a bit too simple so I wanted to ask how I can go about the construction of $U$.

# Answer
As pointed out by David Richerby, you need to generate all the prefixes first.

Correct solution would be:

```
U: "On input <M,w>"

1. Generate all prefixes of w non-deterministically
   (by blanking the input word after the prefix)
2. Simulate M on w (non-deterministically again).
3. If M accepts, U accepts.
   Otherwise, if M rejects then U rejects.
   And if M loops then U also loops.

```

And as to your question, "How you will go about constructing $U$?", it is just a modified Universal Turing Machine.
> 1 votes

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Minimax algorithm when all the options are the same
**tl;dr** What does the Minimax algorithm do when all its options are the same?

Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize)  (Source: Myself)

Imagine this is the tree for a game (tic-tac-toe, maybe?). What should the computer do? Pick one at random? Pick the one which on average has the best score (the second one)?

**Background**

I'm making a program to play Quoridor, and I figure that the Minimax algorithm is the best choice (with some pruning of the really bad ones; otherwise, it would be way too big). The problem is, every choice you can make (the beginning ones in particular) have a chance to loose, and every loss has the same value (-1). So how can I pick the best moves, if all the options are the same?

# Answer
Shaull's answer is absolutely correct, and by referring Zermelo's theorem it is pointing in the right direction.

However, beyond the observations done on the rationality of your opponent, the point here is that Minimax is pretty good for *strategical games* where a single mistake could lead to a disaster, e.g., chess ---where just overlooking a single move can lead to checkmate. On the other hand, if no such strategical flaws are likely (e.g., Omweso and I think Quoridor also to some extent) then Monte-Carlo sampling is a much better option.

For a thorough study on the topic, see:

Raghuram Ramanujan and Bart Selman. Trade-Offs in Sampling-Based Adversarial Planning. Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling. Freiburg, Germany, 2011.

(which was actually awarded a *honorable mention for best student paper*). In this case, the purpose of such algorithm is to follow good lines of action instead of preventing a loss. Monte-Carlo sampling is also the best option to use in case your branching factor is too large (so that minimax and any of its variants such as alpha-beta become infeasible), e.g., Go.

Be aware however, that one of the options used much often in Monte-Carlo sampling, UCT, does not seem to be so good in the end. For a good discussion on the topic, see:

Carmel Domshlak, Zohar Feldman. To UCT, or not to UCT?. Proceedings of the Sixth Annual Symposium on Combinatorial Search. Leavenworth, Washington, USA, 2013.

Hope this helps,
> 5 votes

# Answer
By Zermelo's theorem, which can itself be thought of as a version of minimax, each such game has a winning strategy for one of the players (or a strategy to force a draw).

Thus, if your algorithm encounters a node with all its children having the same value, then conceptually it doesn't matter which option you take, you are guaranteed to get the value of that node.

Having said that, the minimax algorithm computes an optimal strategy against an optimal, rational, opponent. If your opponent is assumed to be "human" (i.e. might be irrational, misinformed, computationally bounded, or plain stupid), then you can perhaps do better than just running minimax. Then, you should consider incorporating heuristics, randomness, etc.
> 4 votes

---
Tags: algorithms, search-algorithms, trees
---


# Question
Title: Difference between "sort" and "universe"
A very basic question. As title, what is the difference between "sort" and "universe" in type theory? Are they interchangable? Or are there only finite number of sorts, but infinite universes?

# Answer
Sort is (typically, though see Pure Type Systems) a meta-level concept and universes are an internalization of a particular case of a sort. The second chapter of Bart Jacobs' thesis covers a fairly general case of how sorts interact with a language. I'll be roughly following that.

I'll use the terminology $T$ is a **type** of sort $s$ if $T : s$ and $e$ is a **term** of type $T$ if $e : T$, so terms are always "grandchildren" of some sort, and types are always "children". $s$ is a **sort** if we can introduce variables of a type of sort $s$ into the context, i.e. $$\frac{\Gamma\vdash A : s}{\Gamma, x:A\vdash x:A}$$

If there were no dependencies between sorts, we could almost say a sort was an index into a collection of contexts, which leads to the notion of dependencies between sorts. We say $s\_2$ **depends on** $s\_1$ when types of sort $s\_2$ can contain terms of sort $s\_1$, i.e. if $$\frac{}{\Gamma\vdash A:s\_1\qquad \Gamma,x:A\vdash B:s\_2}$$ then it can be the case that $x$ occurs free in $B$. Without the dependency it would necessarily be the case that $x$ was *not* free in $B$.

That's all that is required to be a sort. Many additional features can be specified such as the existence of function types of sort $s$ built out of other types of sort $s$. One feature we can add (called axioms in Jacobs' thesis), is the fact that one sort is a type of another sort, i.e. $s\_1 : s\_2$. This internalizes the types of sort $s\_1$ as terms of sort $s\_2$. If we want to *embed* $s\_1$ into $s\_2$ so that *terms* of $s\_1$ are terms of $s\_2$, we can add what Jacobs calls an $(s\_1,s\_2)$-inclusion.

A universe is then a sort that is closed under all the operations in the language. A hierarchy of universes means that we further internalize the types of every universe and have an embedding of each universe into (at least) the next higher universe. Closure typically includes the following rule arising from dependent products: $$\frac{\Gamma\vdash A:\mathbb{U}\_n\qquad\Gamma,x:A\vdash B:\mathbb{U}\_n}{\Gamma\vdash(\Pi x\\!:\\!A.B) : \mathbb{U}\_n}$$ For this to be interesting, $x$ has to occur free in $B$ meaning $\mathbb{U}\_n$ depends on $\mathbb{U}\_n$. Cycles of dependencies between sorts are characteristic of dependently typed languages.

So a (hierarchy of) universe(s) is a (hierarchy of) sort(s) with a variety of additional features many of which imply additional dependencies. For contrast, we can consider sorts (potentially in addition to a hierarchy of universes) that aren't universes (or at least aren't *the* universe, i.e. we could have multiple universe hierarchies). One example is separating compile-time calculation from run-time calculation as in Higher-order ML. In this we'd have a sort that represents compile-time terms in addition to a sort for run-time terms and a dependency allowing run-time terms to depend on compile-time terms. Another example is Cloud Haskell's `Static` type constructor. We can view it as part of a $(\square,\*)$-inclusion where sort $\square$ classifies "static" terms which are terms which only depend on terms bound at the top level.
> 7 votes

---
Tags: terminology, type-theory, dependent-types
---


# Question
Title: The language of Logical Theory as Metalanguage
I am reading the Handbook of Satisfiability, and in Chapter 1 (History of Satisfiability), I found the following statement:

> Moreover, *necessary* and *possible* are predicates of the metalanguage (the language of logical theory) because they are used to describe sentences in the “object” language (the language that refers to entities in the world that is the object of investigation in logical theory).

I have two questions:

1. Could you help me please, to know what is "The language of logical theory" I have writen "'Language of Logical Theory'" in google and only found this in the same book.
2. Can I use necessary and possible as predicates? Could you give some example, please?

# Answer
> 3 votes
The concept of metalanguage is central to logic. Here is an example. The following statement is in the language of propositional logic:

> $$ a \lor b $$

The following is in the metalanguage:

> The formula $a \lor b$ is satisfiable.

In formal logic, we have some formalism for logical statements. This formalism specifies the syntax and semantics of logical statements. For example, in propositional logic we specify a set of logical connectives and how they are used to form logical statements (the syntax), and how a truth assignment to the variables yields a truth assignment of statements (the semantics). This constitutes the "object language". The metalanguage is just the usual English prose that we use, which might refer to the object language, as above.

In simple situations, we distinguish between the two by using logical symbolism for the object language, and natural language (like English) for the metalanguage. However, there are exceptions, the most interesting of which is the use of the metalanguage as a "shortcut" for a statement in the object language. For example, consider the following statement in the language of rings:

> $\exists b . ab=1$

This states that $a$ is invertible. We could also write it in this way:

> "$a$ is invertible"

What this means is that "$a$ is invertible" stands for some statement in the object language which states that $a$ is invertible. How is this different from stating in prose that $a$ is invertible? Well, suppose that we have some encoding function $\varphi$ which encodes formulas to integers. Then it is meaningful to consider $\varphi(\exists b.ab=1)$ or $\varphi(\text{"$a$ is invertible"})$ (the two might even be equal if you choose $\exists b.ab=1$ as the denotation of "$a$ is invertible"), but not $\varphi(\text{$a$ is invertible})$, the latter being as meaningless as $\varphi(\text{blue})$.

For further illustration of this difference, I recommend reading on Gödel's second incompleteness theorem.

---

*Necessary* and *possible* are logical concepts (concepts of the metalanguage) which can be thought of as properties of logical statements: a logical statement is *necessary* if it is always true (i.e., if it is a tautology), and it is *possible* if it could be true (i.e., if it is satisfiable). As such, you can think of them as predicates on the domain of logical statements. In the philosophical discipline of logic they have greater applicability, beyond propositional and predicate logic.

As an example, $a \lor \lnot a$ is possible and necessary, $a \lor b$ is possible but not necessary, and $a \land \lnot a$ is neither possible nor necessary. Every necessary statement is a fortiori possible.

---
Tags: terminology, logic
---


# Question
Title: What does it mean when each individual array is sorted in different array but bear no relationship to each other
There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure.

> Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = lg(n + 1)$, and let the binary representation of $n$ be $\langle n\_{k‒1}, n\_{k‒2}, \ldots , n\_0 \rangle$. We have $k$ sorted arrays $A\_0, A\_1, \ldots , A\_{k‒1}$, where for $i = 0, 1, \ldots , k − 1$, the length of array $A\_i$ is $2i$ . Each array is either full or empty, depending on whether $n\_i = 1$ or $n\_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $n$. **Although each individual array is sorted, elements in different arrays bear no particular relationship to each other**
>
> (Excerpt From: Thomas H. Cormen et al., “Introduction to Algorithms: Third Edition.”)

What does this mean when we have a data structure with several sorted arrays that bear no such relationship? Does it mean that they all must be sorted relative to themselves, but not to the rest? If that's the case, when you try to perform an **insert** or **delete**, conceptually, how would you know which array to insert it to or to delete from, and how would it be reshaped?

# Answer
What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A\_0,\ldots,A\_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements in different arrays.

The text probably goes on to describe how to perform the **search**, **insert** and **delete** operations. The **search** operation is simple: you just search the individual arrays. To **insert** an element, there are two cases: if $n$ is even, we just add a new array $A\_0$ with the new element. Otherwise, choose the smallest $i$ such that $n\_i = 0$ (possibly $i=k$). We add the new element to $A\_0$, and then merge $A\_0,\ldots,A\_{i-1}$ to $A\_i$ (in this order: merge $A\_0$ and $A\_1$ to $B\_1$; merge $B\_1$ and $A\_2$ to $B\_2$; and so on). Element deletion is more complicated; the data structure is only supposed to support **search** and **insert**.

The key idea is that when inserting an element, it is we (the designers of the data structure) who choose where to put it.

The text probably goes on to analyze the amortized cost of these operations. I'll leave these details to the text. (Unless it's an exercise, in which case *you* should work them out!)
> 2 votes

---
Tags: amortized-analysis
---


# Question
Title: Design patterns for simple text based scripting language?
In my current application I am trying to determine the best way to implement a simple scripting language. This language would allow a user to create a script that controls a machine with various inputs and outputs. I have defined most of the commands and created a nice editor for the language though I am stuck now trying to figure out how to verify, parse, and "compile" it.

I currently treat the commands as `const String` and plan to parse the input script text with regex and these strings. Most of the commands have the syntax

```
COMMAND Arg1 Arg2 Arg3 etc.

```

The types and numbers of arguments are currently not defined anywhere in my code, only in my head. I need a design pattern that would allow me to take a line from the script and determine if it is valid; check the command versus some list and check its arguments against the match in that list.

*Are there any known design patterns for situations like this; scripting languages in general?*

I feel like I need a class `Command` that holds the command string and information about its arguments, also the translation from string to "action" (performing the actual real life action the command describes). Then if I am to encounter the string representing the command I can lookup the command class instance, pass in the line, and get some result if it is valid. Though I feel like I would end up (in my case) with quite a few `Command` sub classes.

*Any ideas or recommendations?*

# Answer
> 6 votes
The last time somebody asked this question, I replied: why not just use an existing language?

What you have right now is an API.

You can provide a library in which your commands are function calls, or method calls, or whatever suits you. This saves you from having to design and implement a language, and it saves your users from having to learn yet another little special-purpose language. They still need to learn your API, of course.

I'd say this is the standard design pattern for exposing APIs: as libraries for one or more existing languages.

If you really want to create a new language, you need to specify and implement its syntax and semantics.

For dealing with syntax, using a parser generator is definitely the standard approach. Any language whose programs don't just consist of simple lists of statements will have nested structures and most will allow syntactic recursion (i.e. among the various types of language constructs, some can appear within themselves arbitrarily often). For instance, you may wish to allow a command invocation as an argument to another command invocation, or you may want to have a construct to express iteration or choice that can be arbitrarily nested. In that case, you don't want to parse and process nested constructs with regular expressions, you want grammars, and parser generators are the standard way to work with grammars.

As to the surface syntax, the basic way in which the source code is chopped up into meaningful tokens of your language, I think the most important general lesson is: keep it general, easily readable and context-independent. Make the structure of your programs easy to understand for humans and computers. Examples *not* to follow are such atrocities as Makefiles or /bin/sh in which the correct application of whitespace and quotes is advanced witchcraft.

As to the semantics, one of the things to decide is what sort of programming paradigm to support. Are all commands of a program executed strictly in sequence without anything else ever interfering? Then, a standard, strictly sequential imperative programming language may be a good option. Can commands set concurrent events in motion, or can multiple programs be running at once? Then, a fundamentally concurrent language may be more appropriate.

Another thing to decide is to what extent you want your language to scale. If scripts can grow large and can be invoked by other scripts, you probably want to provide mechanisms for preventing different pieces of code from biting each other in the leg (e.g. scopes for names, local variables). But this is probably a later concern.

# Answer
> 1 votes
Another possibility, somewhere between API and new language: create a domain-specific language on top of a general-purpose language. Think regular expressions: a mini-language, with its own syntax, built for just one purpose (e.g. text processing), which is usable from within another, more flexible language. Then you get the benefits of a language with a close fit to the domain, but also get a full language that you don't have to implement yourself if things start to get complex.

Lisp, Scala, and Ruby are popular choices for DSLs. Because they're so flexible, you can build a DSL directly inside the host language; this is called an embedded DSL. Interesting examples are Clojure's `core.match` and Midje, Ruby's `rspec` unit test library, and Scala's Baysick, a DSL that strongly resembles classic BASIC created using just Scala's own facilities. The designs behind embedded DSLs differ by language; in Clojure and other Lisps, they usually use a lot of macros, while Scala gets a ton of mileage from implicits and Ruby gets a lot of use from blocks. Scala's and Ruby's flexible policies on using parentheses around function arguments are also a big help.

You can also create an external DSL by writing a simple parser and a small interpreter. You can use the parser generator libraries that others have suggested, but if the language is simple enough, you don't actually need to create an abstract syntax tree or a symbol table; you can just parse and execute commands one at a time, possibly holding on to some state as you go. If your syntax is constrained enough, you can just tokenize a line with regular expressions, then loop over the tokens. If there are no user-defined commands, you can just have a class or function for each command; you can store them in a table, and use the command name at the front of each line to look up the appropriate command and pass it arguments. The commands can validate that they received the appropriate type and number of arguments.

If you want to take the external DSL approach, you might be interested in the Interpreter Pattern as a way to organize things.

# Answer
> 1 votes
Expose your API in the form of calls from a well-known language, so you can leverage the development already done in that language, and even combine with modules for other APIs and libraries. I'd probably choose Python or Perl.

Use one of the languages designed as lightweight extension languages, thought as a way to write extensions or control of the program in which it is embedded. Alternatives are lua or tcl/tk, maybe even Scheme (as in GNU guile).

This will be much less work than doing it yourself, gives a much better product faster, gives lots of extra flexibility (you don't have to provide it!), you can use tons of already available documentation (probably the hardest part of getting this into the hand of users), and flattens the learning curve (users can reuse what they learned elsewhere/reuse elsewhere what they learned here).

---
Tags: reference-request, programming-languages, software-engineering, design-patterns
---


# Question
Title: What's the difference between clock replacement & LRU replacement?
As title. When we want to request following page numbers 2,4,4,2,5,2,1,1,3,1, is clock replacement better? What are the advantages and disadvantages of them?

Thanks~

# Answer
> 2 votes
Coincidentally, for your reference string, both LRU and CLOCK replacement strategies generate the same number of page faults, five if you count all frame loads, including the first three to initially fill the buffer. In addition, both algorithms generate page faults at the same times. Of course, this won't be the general situation. I assume you know how each works; if not let me know and I'll edit this answer.

Every operating system text I have on my shelf includes a discussion on the relative performance of various page replacement algorithms, so there's where you'll find more extensive comparisons than would fit here. Some empirical studies show that in general there's reason to assert that MIN (a.k.a OPTIMAL) generates the fewest page faults (in fact, MIN is provably optimal), followed by LRU, CLOCK, and FIFO, in that order. In terms of implementation, MIN is, of course, impossible, since it requires knowledge of the future$^\*$, LRU is somewhat difficult to do, basic CLOCK is fairly easy (and can be improved with relatively little effort), and FIFO is easiest.

---

$^\*$ If I had a time machine, I certainly wouldn't waste my time including it in the hardware to support MIN. I'd buy lottery tickets and/or play the stock market.

# Answer
> 0 votes
Please consider that operating system texts show examples with a few frames and a few dozen references, while my PC here has 8 GiB RAM, i.e., 2 million 4 KiB frames, and does millions of memory references a second. And that isn't a large machine by any stretch.

It can be proved that OPT is optimal. For performance of any other method, the *only* way to evaluate that is by using real reference strings, as real references show very different behaviours, and the behaviours are very hard to model accurately enough. The behaviour is irregular enough that exact mathematical analysis is out of the question.

---
Tags: operating-systems, memory-management, cpu-cache, virtual-memory
---


# Question
Title: Does a problem stay NP-hard when an additional constraint is added to it?
I have the following problem $(P)'$:

\begin{align\*} {\rm max}\_{x\_1,...,x\_K}\quad & \sum\_{k=1}^Kf(a\_k,x\_k) \cr & & (P)'\cr {\rm subject\ to}\quad & 0 \le x\_k \le A, k=1,\ldots,K. \end{align\*}

This problem is proven NP-hard. An instance of $(P)'$ is given by $(K,a\_i,A)$.

I have another problem $(P)$:

\begin{align\*} {\rm max}\_{y\_1,...,y\_N}\quad & \sum\_{n=1}^Nf(b\_n, y\_n) \cr & & (P)\cr {\rm subject\ to}\quad & 0 \le\sum\_{n=1}^Ky\_n \le B, \cr \quad & y\_n\geq 0, n=1,\ldots,N. \end{align\*} And an instance of $(P)$ is given by $(N,b\_i,B)$.

Can I say that problem $(P)$ is NP-hard?

# Answer
> 3 votes
For general $f$ you can't conclude that $P$ is NP-hard just from the fact that $P'$ is NP-hard. In order to do so, you would need to come up with a reduction from $P'$ to $P$. For such a reduction to work, you would need that for every value of $A$ there be a value of $B$ such that the two systems of constraints are equivalent. Unfortunately this is not the case.

---
Tags: optimization, np-hard
---


title: Optimal quantization of histogram

text:
# Question
Title: Optimal quantization of histogram
I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a histogram whose entries sum to $2^n-1$.

To maintain sanity, I require some properties of the quantization algorithm:

1. Any element with 0 occurrences must have 0 occurrences after quantization.
2. Any element with \> 0 occurrences must have \> 0 occurrences after quantization.
3. The sum of the quantized histogram must add up to $2^n-1$.

To guarantee that there is a satisfiable solution there will be no more than $2^n-1$ elements.

Given those constraints the values of the quantized histogram $Q$ must proportionally be as close as possible as the values of the original histogram $H$.

Or more formally:
$$\forall i: H\_i \> 0 \rightarrow Q\_i \> 0$$ $$\forall i: H\_i = 0 \rightarrow Q\_i = 0$$ $$\Sigma Q = 2^n-1$$ $$\min \sum\_i (H\_i/\Sigma H - Q\_i/\Sigma Q)^2$$

Is there a direct algorithm that gives an optimal result? Or perhaps a fast near-optimal approximation?

---

Without requirement #2 there is a solution by choosing $Q\_i = \lfloor H\_i/\Sigma H \cdot (2^n-1) \rfloor + a\_i$. Where $a\_i$ is initially 0 for all $i$. It's easy to see that $\Sigma Q \leq 2^n-1$, and setting $a\_i$ = 1 for the $2^n-1 - \Sigma Q$ elements that have the biggest undershoot error solves the problem optimally.

The difficulty lies in the requirement that no element with nonzero occurrences may be floored to zero occurrences in the quantized histogram. Consider \[1, 1, 1, 1000\]. Without this requirement the most accurate quantization to $n = 3$ is \[0, 0, 0, 7\]. However the requirement gives us \[1, 1, 1, 4\].

# Answer
This can be reduced to the following problem.

APPROXIMATE ROUNDING:
*Input:* real numbers $c\_1,\dots,c\_m \in \mathbb{R}$, an integer $d \in \mathbb{N}$
*Goal:* find non-negative integers $x\_1,\dots,x\_m \in \mathbb{N}$ that minimize $\sum\_i (x\_i - c\_i)^2$, subject to the requirement $\sum\_i x\_i = d$.

The reduction: define $S = \\{i : H\_i \> 0\\}$, $x\_i = Q\_i - 1$ for $i \in S$, $d=2^n-1-|S|$, and

$$c\_i = -1 + (2^n-1) H\_i / \sum\_j H\_j.$$

Now the optimal solution to APPROXIMATE ROUNDING immediately yields the optimal solution to your problem, by setting $Q\_i = x\_i + 1$ for each $i \in S$ and $Q\_i=0$ for each $i \notin S$.

---

Can we solve APPROXIMATE ROUNDING efficiently? I don't know. I conjecture there exists $t \in \mathbb{R}$ such that the optimal solution is $x\_i = \lfloor t c\_i \rceil$ for all $i$ (i.e., $x\_i$ is $tc\_i$ rounded to the nearest integer). If this is true, we can use binary search to find $t$ such that $\sum\_{i \in S} \lfloor t c\_i \rceil = d$, and thereby solve APPROXIMATE ROUNDING efficiently. However, I have no proof that this works.

Erwin Kalvelagen over on Math.SE has suggested that APPROXIMATE ROUNDING can be solved using a MIQP solver.
> 1 votes

---
Tags: optimization, integers
---


# Question
Title: Regular language? Union of the dictionary and an non-regular language
I'm attempting to figure out if a union of two languages is regular.

$$ L\_1 = \\{all\ the\ words\ in\ the\ Oxford\ dictionary\\} \\ L\_2 = \\{w : w\ has\ twice\ as\ many\ a's\ as\ b's\\} $$

$L\_2$ is well established to be a non-regular language. However, I am not sure if $L\_1$ would be considered a regular language. The language should be finite (albeit large), which suggests it is regular, but I'm not certain.

If $L\_1$ is regular, then I would consider the union $L\_1 \cup L\_2 $ would also be regular, as by the same argument, the language would be finite.

What does everyone think?

# Answer
> 2 votes
The best way to see that $L\_1 \cup L\_2$ is not regular is through closure properties of the regular languages.

**Theorem.** If $L\_1$ is finite and $L\_2$ is not regular, then $L\_1 \cup L\_2$ is not regular.

**Proof.** Since $L\_1 \setminus L\_2$ is finite, it is regular. Suppose $L = L\_1 \cup L\_2$ were regular. Then $L \setminus (L\_1 \setminus L\_2) = L\_2$ would also be regular, contrary to assumption. $\qquad\square$

# Answer
> 1 votes
$L\_1$ is indeed finite. But the union $L\_1\cup L\_2$ contains everything that is in $L\_1$ and also everything that is in $L\_2$. Thus, the union of a finite set and an infinite set is infinite.

In this case, $L\_1\cup L\_2$ is not regular: you can prove this using the pumping lemma, Myhill–Nerode or any other technique you might have been taught.

---
Tags: regular-languages
---


# Question
Title: What does "post-image analysis" mean in the context of formal program analysis?
I am reviewing an anonymous paper about a sort of static analysis of programs that uses the phrase "post-image analysis", or "post-image operation" without defining what that is. I am guessing it is a well-known concept in formal methods, even though a Google search has not revealed anything.

I am guessing it means an analysis of the trace of a segment of a program. Basically, you run it a little bit, you collect the trace (perhaps that's a synonym for "image"), and analyse. But I am just guessing.

Can anyone tell me what that is, or give me a pointer?

# Answer
> 3 votes
When working with transition systems, $\text{post}(s)$ is the set of states that are reachable in a single step from the state $s$; if $S$ is a set of states,

$$\text{post}(S) = \bigcup\_{s \in S} \text{post}(S).$$

Also, $\text{post}^\*(s)$ is the set of states that are reachable from $s$, i.e., $\text{post}^\*$ is the transitive closure of $\text{post}$.

---
Tags: formal-methods, static-analysis
---


title: Shortest Path Passing All Routes

text:
# Question
Title: Shortest Path Passing All Routes
Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass through all **roads between the cities**, not just the cities. The traditional shortest path algorithims do not work because they only calculate the shortest distance between 2 points, and don't guarantee passing through all of the roads. Here is a vague map of my problem.

For a solution to be valid, it must pass through every road in between the points labeled.

# Answer
Construct the line graph of $G$, then solve the Travelling Salesman Problem on the resulting line graph. This yields the optimal solution to your problem, assuming you want to visit every edge in your graph exactly once.

See also the route inspection problem (also known as the Chinese postman problem).
> 2 votes

# Answer
The optimal solution would be to travel every edge of the graph exactly once. If all the vertices of the graph have even degree then the Euler path is the answer.

Otherwise if you allow to traverse each road twice then you can get a 2- approximation factor algorithm.
> 1 votes

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


# Question
Title: Is it legal to draw an NFA with fewer nodes than what I normally see?
Is it Ok to express an NFA accepting 1\*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?

# Answer
It is not a convention. You must know that a regular expression denotes one regular language and this language can be generated by an infinite number of differeny automatona (in this case we are talking about NFA).

Why are you always encountering the second automaton in the books? This is probably because the second automaton is obtained from the regular expression $1^\*0$ using a well known method called Thompson's construction.

Which of the two automata is better? There isn't just one answer. The first NFA looks simpler but maybe you will have more work when you try to formally prove its correctness. In the other hand the second automaton looks more complex but it was obtained by a proven method so we are sure that it is correct.
> 2 votes

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


# Question
Title: Proof that the set of all universal CFGs is co-RE complete
Let $\Sigma^\*\text{CFL} = \\{G \mid G \text{ is a CFG; } L(G) = \Sigma\_G^\*\\}$.

Enumerate the r.e. sets by $W\_n$.

Let $\text{EMPTY}= \\{ n \mid W\_n=\emptyset\\}$.

On page 4 of these lecture notes, to show $\text{EMPTY}\leq\Sigma^\*\text{CFL}$ the author constructs a function $g\colon\mathbb{N}\to\\{0,1\\}^\*$ such that

$$n\in\text{EMPTY}\iff L(g(n))\in\Sigma\_n^\*.$$

I think we actually want $n\in\text{EMPTY}\iff L(g(n))\in\Sigma\_{g(n)}^\*$. Is this correct?

# Answer
In the proof we construct grammar $g(n)$ such that it has same alphabet as the Turing machine + symbols for states + separator "#", which is defined to be:

$\Sigma\_n = \\{0, 1, \triangleright, B, \\#, q\_0, q\_1 . . , q\_n \\}$

So essentially $\Sigma\_n = \Sigma\_{g(n)}$. $\Sigma\_n$ is a superset of $\\{0, 1, \triangleright, B\\}$.
> 1 votes

---
Tags: computability, context-free, formal-grammars, reductions
---


# Question
Title: Proving that a (tree) language is not Buchi recognizable
I'm reviewing some notes about tree automata and I'm trying to conclude a proof that the professor left incomplete. The statement is:

> Let $A = \\{a,b\\}$ and $T = \\{t \in T\_A^{\omega} \mid \text{every path in $t$ contains a finite number of $a$}\\}$. Prove that $T$ isn't Buchi recognizable.

Now we can define the following subsets of trees $t\_n \subseteq T$ where $t \in t\_n$ has one $a$ at positions: $\epsilon, 1^{m\_1}0, 1^{m\_1}01^{m\_2}0, \ldots, 1^{m\_1}01^{m\_2}0\ldots1^{m\_n}0$ with $m\_i \> 0$.

Now assume that $\mathcal{A} = (Q, A, \Delta, q\_0, F)$ is the Buchi automaton that recognizes $T$ with $|Q| = n+1$ and $q\_0$ appears only at the root of its computations. Let $t \in t\_n$ and $r$ be a successful run of $\mathcal{A}$ on $t$.

**Claim:** $\color{red}{\text{There exists $u \leq v \< w$ such that $r(u) = r(w) = s \in F$ and $t(v) = a$.}}$

Obviously if we show that the claim is true we can prove the initial statement: take the subtree $t\_v$ and obtain a $t' \in t\_{n+1}$ by replacing the subtree $t\_w$ with $t\_v$. We have that there exist a run $r'$ which is identical to $r$ up to the position for $w$ and will follow the same sequence of states at $w$ as it did at $v$, and hence is accepting. Repeat the process and you obtain a branch with infinite $a$s that is accepted by $\mathcal{A}$. (This is just the rough idea, it requires a bit of formalism, but it's not the point of the question.)

My question is: how do I prove the claim?

I can show that there exist a $t' \in t\_{2n}$ with that property (which is actually good enough for the rest of the proof), but not that given a fixed $t\_n$ the statement holds for any successful run.

My idea is simply: given that $r$ is accepting there must exist a $s \in F$ repeated infinite times in a path passing through $1^{m\_1}01^{m\_2}0\ldots1^{m\_n}0$. Then take a tree $t'' \in t\_{n+1}$ that is identical to $t\_n$ up to the position $x$ where $r(x) = s$ on that path, and add an $a$ below such position. Now this tree is still accepted by the automaton and there exist an accepting run $r'$ identical to $r$ up to the position $x$, but then $r'$ cannot reuse $s$ for accepting that same path (otherwise we have found the three states of the claim) and so it must use a different state $s'$. Repeat for all final states and you have that $t\_{2n}$ must have a run with that property.

Is there any way to apply this kind of reasoning to $t\_{n-1}$, $t\_{n-2}$ etc to obtain the result for $t\_n$? It looks like at most I may be able to prove that there exist *a* $t'' \in t\_n$ with a run with that property, while the claim is stronger. Or am I going in the wrong direction?

# Answer
The idea is to play with the $m\_i$'s, as follows.

Consider a tree $t\_1$, which has $a$ in $\epsilon$, and nowhere else. Look at the path $1^\omega$ — an accepting run on it has infinitely many accepting states. Wait until such an accepting state was reached, and only then put $a$ at $1^{m\_1}0$, where $m\_1$ is large enough.

Now look at the path $1^{m\_1}01^\omega$, again, it has an accepting state eventually, denote the length up to it by $m\_2$, put an $a$ at $1^{m\_1}01^{m\_2}0$ and look at $1^{m\_1}01^{m\_2}01^\omega$. By now you have almost what you wanted - two accepting states with an $a$ between them (informally speaking). But you are not yet guaranteed that both accepting states are equal. To enforce the latter, we repeat the process for $n$ times, thus exhausting the number of accepting states, and by the pigeonhole principle, two accepting states must be equal.
> 3 votes

---
Tags: automata, trees, buchi-automata
---


# Question
Title: Generate random weighted graphs representing a road network
in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current solution for connecting vertices (and so create an edge) looks like this:

```
def connectVertices(self, vertexA, vertexB):
    vertexA.addNeighbour(vertexB)
    vertexB.addNeighbour(vertexA)
    weight = randint(1, self.maxDistance)
    self.adjacencyMatrix[vertexA.index][vertexB.index] = weight
    self.adjacencyMatrix[vertexB.index][vertexA.index] = weight

```

I insert a random integer in the adjacency matrix. How ever this can creates graph which can not represent realistic road networks. Example:

Node A has a cost of 1 to B.

Node B has a cost of 1 to C.

Node C has a cost of 60 to A.

Since the cost when travelling over B between A and C is only 2, it does not make much sens to have a cost of 60 for the direct connection between A and C.

(I can not solve this problem by reducing the maximal cost, because I will need to generate large graphs.)

Are there algorithms that solve this problem ?

(Or :Is there maybe a python library which generates random weighted graphs which takes my problem in count ?)

# Answer
> 1 votes
One approach is to generate an arbitrary graph $G$ with arbitrary (positive) lengths on each edge. Then, compute all-pairs shortest paths, and build a new fully-connected graph $G'$ where the length of the edge $u \to v$ in $G'$ is equal to the length of the shortest path from $u$ to $v$ in $G$.

The nice thing about this is that you're guaranteed by construction that $G'$ will satisfy the triangle inequality.

If you are happy with generating fully connected graphs, you can then output $G'$ as your random graph. If you don't want the graphs to be fully connected, you could keep only some subset of the edges of $G'$ and delete the rest, then output the result.

# Answer
> 1 votes
You can also consider actually generating points in the plane $(x,y)$, and then randomly connect points with weight their distance $\sqrt{|x\_1 - x\_2| + |y\_1 - y\_2|}$. Additionally, you can try to not connect two points if your edge has to cross an already existing edge.

---
Tags: graphs, graph-traversal, weighted-graphs
---


# Question
Title: Examples of languages not decidable by a TM using certain upper bounds on space/time
I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain classes of time / space hierarchies. For example, what are some examples of a decidable language that can't be decided by a TM using space O(log n) and time less than n, on inputs of length n?

Might the Travelling Salesman Problem be an example to the above question, since I think the brute-force algorithm for TSP would take space O(n) (store the current shortest path, and compare it with each new path that's being explored)?

# Answer
Look up the time hierarchy and space hierarchy theorems. They give examples of languages which can be computed using $f(n)$ time (or space), and require more or less $f(n)$ time (or space). These languages are basically the following:

> Descriptions of Turing machines that halt after time $f(n)$ (after using space $f(n)$).

Perhaps you won't consider these languages natural. Unfortunately, the best lower bounds known for natural languages are currently only $\Omega(n)$ (for time) and probably even worse for space. However, it is conjectured that NP-hard problems require exponential time (this is known as the Exponential Time Hypothesis).
> 3 votes

---
Tags: turing-machines, time-complexity, space-complexity
---


title: Runtime for algorithm

text:
# Question
Title: Runtime for algorithm
I need to get the asymptotic runtime for an algorithm and I'm just stuck.

A python implementation:

```
def alg3(n):
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                k = k*3

```

I think it should somehow be $\Theta(n^2\log(n))$ but that isn't quadratic. Can you help?

```
import time

def alg3(n):
    count = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                count = count + 1
                k = k*3
    print(count)

n = 10
for i in range(0, 6):
    start_time = time.time()
    # run two times then calculate average time
    for i in range(0, 100):
        alg3(n)
    print("time with size %s: %s seconds" % (n, (time.time() - start_time)/100))
    n = n*2

```

If you calculate the factors given they give about 4.1.

# Answer
> 4 votes
Let $f(n) = n^2\log n$, with the $\log$ taken to base 2. Then $$ \frac{f(2n)}{f(n)} = 4 \frac{\log(2n)}{\log n} = 4 \left(1 + \frac{1}{\log n}\right). $$ That is, for large $n$ you would expect $f(2n) \approx 4f(n)$. This shows that this test isn't sensitive enough to detect logarithmic factors.

# Answer
> 3 votes
Let $f$ be the runtime of your algorithm, it's easy to find a close form $$ f(n) = n \sum\_{j=1}^n \log\_3 \left\lceil \frac{n}{j}\right\rceil $$

Then some calculations, $$ \begin{aligned} f(n) &\leq n + \frac1{\ln 3} n \sum\_{j=1}^n \ln (\frac{n}{j}) \\ &\leq n + \frac1{\ln 3} n \int\_{0}^{n} \ln (\frac{n}{x}) \mathrm{d}x \\ &= n + \frac1{\ln 3} n^2 \end{aligned} $$

Similarly, you can lower bound $f$.

$f(n) = \frac1{\ln 3} n^2 + O(n)$.

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


# Question
Title: Nth number in a infinite sequence of numbers
This was interview question.

When the input is a infinite sequence of numbers starting from 1, what is the nth digit?

e.g.) 123456789101112131415161718192021.....

here 28th digit is 1.

# Answer
Just to add a concrete implementation to what was already said:

```
(defun nth-digit (n)
  (loop :with previous := 0
     :for i :upfrom 0
     :sum (* 9 (expt 10 i) (1+ i)) :into digits
     :if (> digits n) :do
     (multiple-value-bind (whole remainder)
         (floor (- n previous) (1+ i))
       (return (aref (write-to-string (+ (expt 10 i) whole)) remainder)))
     :else :do (setf previous digits)))

```

The idea for implementation is to:

1. Sum the length of all 1-digit numbers (of which there are $9\*10^0$), then sum all 2-digit numbers (of which there are $9\*10^1$), 3-digit numbers, of which there are $9\*10^2$ and so on. This gives:

$$ N = \sum\_{i=0}^m 9\times 10^i \times (i+1) $$

2. Notice that $x = \lfloor\frac{n - N}{i+1}\rfloor$ will be a positive integer which counts the number of numbers having $m+1$ digits in them.
3. Finally, after you've already found what number contains your digit, you can find $e$ s.t. $r - e = 10^i + \frac{n - N}{i+1}$, and $e \leq i$ the $e'th$ digit of $x$ is going to be the one you are looking for.
> 3 votes

# Answer
The idea here is as follows:

* The first 9 digits are 123456789.
* The next 90 pairs of digits are (10)(11)...(99).
* The following 900 triplets of digits are (100)(101)...(999).
* And so on.

Given an index $n$, you calculate which group you are (singles, pairs, triplets, ...), then which tuple you belong to and which digit inside the tuple. For example, if $n=28$ then this is digit no. 19 in the second group, which is the first digit of the 10th tuple 19, that is, 1.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Not convincing claim for Master Theorem Case 3
In a practice exam given in class, we were asked to solve the following recurrence

$$T(n) = 2T(n/4) + \frac{n}{\log n}$$

The given solution claims that this falls in the third case of the Master Theorem and starts with the following claim:

$$f(n) = n / \log n = \Omega (n^{1/2 + \epsilon}) \ \textrm{for any} \ 0 \< \epsilon \< 1/2$$

Is there a quick way to show this holds. Seeing the $\log n$ is the reason why I am doubting this claim.

# Answer
> 2 votes
Yes, this holds since $\log n = O(n^\epsilon)$ for any $\epsilon \> 0$. You can prove this formally as follows. We will show that $\log n = o(n^{1/k})$ for all $k \> 0$, or equivalently, that $\log^k n = o(n)$ for all $k \geq 0$. The proof is by induction. The base case $k = 0$, is clear. For the induction step, L'Hôpital's rule gives $$ \lim\_{n\to\infty} \frac{\log^k n}{n} = \lim\_{n\to\infty} \frac{k\log^{k-1} n}{n} = 0. $$

---
Tags: master-theorem
---


# Question
Title: Are all partial functions partial computable?
If we have some function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ that is not total, i.e. for some values $x \in \mathbb{N}$, $f(x) = {\perp}$, is $f$ always partial computable? By partial computable I mean there exists a program that $f(a)$ is defined for $a \in \mathrm{dom}(f)$ and $f(a)$ is not defined for $a \notin \mathrm{dom}(f)$.

I expect that this isn't the case but cannot come up with a counter example.

# Answer
The fact that we can encode Turing machines as strings means that there are only countably many Turing machines, so only countably many computable or partial-computable anythings. Since there are uncountably many partial functions $\mathbb{N}\to\mathbb{N}$ (or even partial functions $\mathbb{N}\to\\{0\\})$, it follows that, in a very strong sense, "most" partial functions are not partial computable.

For a concrete example, use the fact that, if a set and its complement are both semi-decidable, they are both decidable (exercise: prove this), and the analogous result for partial functions. This means that, if you take any set $S$ that is semi-decidable but not decidable, then $\overline{S}$ is not semi-decidable. So, for example, the function $$f(x) = \begin{cases} 0 &\text{ if }x=\langle M\rangle \text{ for some TM $M$ that loops on every input}\\ {\perp} &\text{ otherwise} \end{cases}$$ is not partial computable.
> 3 votes

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


# Question
Title: Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm
I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org .

Currently, I am working on the "Search in Pacman" Project; the sources can be found online at Berkley CS188 . I have problems finding an good solution for "Finding All the Corners", so I need a good Multiple Goal Heuristic.

I allready tried the simple approach described in here. I used the minimum of all manhattan distances to all goals. This works, but is considered a rather poor heuistic, because my A-Star Algorithm expands 2606 nodes for the given maze. Using the same with euclidean distance expands even 103081 nodes. A good heuristic should expand 1600 nodes or less. A very good one 1200 nodes, an excellent one even 800 or less.

I got a hint by other students who use minimum spanning trees created with Kruskal's Algorithm. I wanted to investigate into that direction, but I am somehow confused how the Kruskal Algorithm can be used to get a Heuristic? As far as I understood, this Algorithm returns a minimum spanning tree (MST) which is a path, right? So it is a solution to the Traveling Salesman Problem (TSP); it returns a sequence of nodes. But I need a heuristic, so a cost function which can be applied to this problem and called by an Algorithm (like A\*).

Can anyone of you give me a hint on how to proceed? Every help is highly appreciated!

# Answer
> 2 votes
MST is actually a tree, not a path (generally). Therefore, it is not a solution to TSP. (Although, MST can help you to find a solution that is not more than twice as long as the optimal solution, if you solve this in a metric space on a complete graph. That's unrelated story.)

Now, I must admit that I do not see a way spanning trees can help you if the maze contains loops. And in the case that the maze does not contain loops, it is somehow weird to talk about MST, because the graph of the maze is a tree.

However, maybe you can start to think about this: in a tree, for any two nodes, there is exactly one path that connects them. That's a trivial, but quite a nice property, isn't it? Length of this unique path is an easy lower bound that is more precise than Manhattan distance.

If you build MST over a graph with loops, this would probably not make an admissible heuristic, because the path using only MST edges can be longer than some path over edges you haven't choose to the spanning tree.

"Minimality" of MST is somehow a local property -- it's not like all the shortest paths are preserved. This is why I would never think about solving your problem with MST.

# Answer
> 0 votes
This is quite an old question, but for anyone coming across it - read up on the Chebyshev Distance. It is one of the three most referenced pathfinding heuristics and will solve this problem.

---
Tags: algorithms, graphs, heuristics, search-problem
---