title: Minimizing the SUM algorithm

text:
# Question
Title: Minimizing the SUM algorithm
We are given $2n$ positive integers $a\_1,a\_2\ldots,a\_n$ and and $$b\_1,b\_2,\ldots,b\_n$$ as input.

The question is to find a permutation $O$ on $\\{1,2,\ldots,n\\}$ that minimizes $$\sum\_{i=1}^n \left(a\_{O(i)} \cdot \sum\_{j=1}^i b\_{O(j)}\right).$$

For example, take $n = 3$, $a\_1 = 10, a\_2 = 1, a\_3 = 100, b\_1 = 10, b\_2 = 100$, and $b\_3 = 1$. If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum\_{i=1}^n \left(a\_{O(i)} \cdot \sum\_{j=1}^i b\_{O(j)}\right) = 1311.$$

The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum\_{i=1}^n \left(a\_{O(i)} \cdot \sum\_{j=1}^i b\_{O(j)}\right) = 321.$$

Trying all possibility is exponential. How can I find an optimal permutation $O$?

# Answer
Did you check what's the class of your problem? I'd try a reduction to a scheduling problem.

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.
> -1 votes

---
Tags: algorithms, permutations
---


# Question
Title: Constraint Satisfaction: maximizing total value with no overlaps
Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value.

Out of all the bars available, we want to choose the set which maximizes the total value but with no overlap between the start points and end points of the bars. In the example above, the selected bars would be the following (in red):

What would be the best way to approach this problem computationally, for `n` number of bars being potentially large (several thousands) and `[x,y]` the possible bar positions being large as well?

I thought of a probabilistic approach, but are there deterministic approaches as well?

# Answer
You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs.

One such algorithm is based on dynamic programming, you can see e.g., \[1\] for details and discussion.

---

\[1\] Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs." Information Processing Letters 43.5 (1992): 229-235.
> 7 votes

---
Tags: constraint-satisfaction, constraint-programming
---


title: Randomly choose a line - algorithm

text:
# Question
Title: Randomly choose a line - algorithm
We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked?

And how do we randomly pick such n lines so that they all have the same probability?

We don't know the number of lines beforehand.

Any hint on where to start solving this, which algorithm to use, or at least an idea where to start would be appreciated.

# Answer
> 2 votes
Your problem is known as reservoir sampling. The algorithm maintains a currently picked line, whose initial value is the very first line. For $k \> 1$, you replace the currently picked line by the $k$th line with probability $1/k$. If there are $n$ lines in total, the probability that the $k$th line is chosen is $$ \frac{1}{k} \cdot \left(1-\frac{1}{k+1}\right) \left(1-\frac{1}{k+2}\right) \cdots \left(1-\frac{1}{n}\right) = \\ \frac{1}{k} \cdot \frac{k}{k+1} \frac{k+1}{k+2} \cdots \frac{n-1}{n} = \frac{1}{n}. $$

---
Tags: algorithms, randomness, sampling
---


# Question
Title: Finding one of 2/3 of all array elements in constant expected time
How do I go about designing a constant time algorithm which satisfies the following I/O requirements:

> *Input*: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the symbol $Y$
>
> *Output*: a number $i$, such that $A\[i\]=X$

It is clear that the naive linear scan approach is $O(n)$. Is there any good algorithm, potentially randomized, that has a constant number of expected operations $O(1)$?

# Answer
Use *rejection sampling*:

```
do {
   i = uniform_random(0..3*n-1)
} while A[i] != X
return i

```

Whenever this terminates, it clearly outputs a correct $i$.

If the probability of $A\[i\] = X$ is $p \in (0,1\]$, then the expected number of iterations is $\frac{1}{p}$ (geometric distribution). Filling in the details is an instructive exercise.
> 0 votes

# Answer
One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A\[i\] = X$ would be:

$$\begin{align} P(\text{at least }1\\; X) &= 1 - P(\text{all are } Y)\\ & = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\\\[0.5em\] & \geq 1 - 3^{-k} \end{align}$$ This inequality holds as $n$ approaches $\infty$ for some constant $k$ because: $$\lim\_{n\to\infty} \frac{n/3 - k}{n - k} = \frac{1}{3}$$ Even for some small $k$ like 10, the probability of finding an index $i$ such that $A\[i\] = X$ is: $$\begin{align} P(\text{at least }1\\; X) &\geq 1 - 3^{-10}\\ & \geq 0.99998 \end{align}$$
> 3 votes

# Answer
Consider $ALG$:

> Pick an index $i$ at *uniformly random*.
>
> **If** $A\[i\]=X$ **then** return $i$ **else** return $FAIL$

We see that $Pr\[SUCCESS\] = \frac{2}{3}$ i.e., $Pr\[FAIL\] = \frac{1}{3}$ in a single run.

Suppose we want to boost the success of finding at least one $i$ so that $A\[i\]=X$ to a probability of $\geq 1-\delta$

We can do so by repeating $ALG$ ***independently*** upto a sufficient number of times. This repeated algorithm fails only if all the runs return $FAIL$ otherwise we return the first run that produces an $i$ and break there.

Suppose we conduct $k$ runs, the event that this repeated version of $ALG$, namely $ALG\_k$, fails is if **each** of the runs return $FAIL$. Thus,

$Pr\[ALG\_k\ fails\] = \frac{1}{3} \cdot \frac{1}{3} \cdots\frac{1}{3} = \frac{1}{3^k}$ i.e., $Pr\[ALG\_k\ Succeeds\] = 1 - \frac{1}{3^k} \geq 1 - \delta$

where the last inequality comes from our requirement on the probability of success and thus leads to the following bound on k:

$\frac{1}{3^k} \leq \delta \implies k \geq \lceil log\_3(\frac{1}{\delta})\rceil$

For instance, if we want the Algorithm to find an $i$ (i.e., succeed) with probability at least $0.99999$, then our $\delta = 10^{-5}$ giving a lower bound of $\lceil log\_3(10^5) \rceil = 11$. In other words, $11$ independent runs of $ALG$ ensures success with at least probability of $0.99999$

## Here's the pseudocode:

(Note: $\delta$ is a parameter that is fixed and independent of $n$)

$FINDINDEX(A,\delta):\\ k \leftarrow \lceil log\_3(\frac{1}{\delta})\rceil \\ N \leftarrow A.length \\ \textbf{for}\ j=1\ \textbf{to}\ k\ \textbf{do}\\ \ \ \ \ i \leftarrow RANDOM(N) \\ \ \ \ \ \textbf{if}\ A\[i\]=X\ \textbf{then}\\ \ \ \ \ \ \ \ \ \textbf{return}\ i\\ \textbf{return}\ NULL $

In the above, $RANDOM(N)$ is assumed to be a function that returns an integer picked uniformly at random from $1$ to $N$
> 1 votes

---
Tags: algorithms, randomized-algorithms, searching, algorithm-design
---


# Question
Title: Uniformly randomly generating an "unlockable" graph
I'm working with something that can modeled as the following type of (multi-)graph $G = (V,E)$, which I've been calling an "unlockable" graph. (There may be existing terminology for this.)

Let $G$ be a graph with the following additional structure. There is a set $K$ of *keys*, and edges may be "unlocked" or they may be "locked" by decorating them with the name of some $k \in K$. Multiple edges can be locked by the same $k$. Each vertex in the graph $v\_i$ has a (possibly empty) ordered list $L\_i$ of *locations*, which may be empty or contain a key. One of the vertices of the graph is marked as the *start vertex*.

The graph can be *completely unlocked* if every vertex can be visited from the start vertex. A locked edge can only be traversed if a vertex containing the key for that edge is first visited. Traversals are allowed to repeat edges and vertices.

Such a graph is valid if a) all keys are placed in exactly one location and b) the graph can be completely unlocked.

I'd like to uniformly randomly select a valid key placement on a fixed underlying graph. (That is, a map from $K$ into the locations $L = \cup\_i L\_i$ of the graph.)

---

The analogy (and essentially the context) is as follows: The graph represents a dungeon composed of rooms, and the edges are doors, which can be locked or unlocked by various keys. These keys are scattered around the dungeon in treasure chests. An adventurer enters the dungeon and explores it, and wins if they can enter every single room (to loot it, I suppose). How can the keys be distributed so that the adventurer always wins, and cannot have an unfair advantage by assuming that one valid configuration is more likely than others?

---

Here's a naive algorithm that produces a random valid key placement:

```
current_keys = {}
placed_keys = {}
current_rooms = {}
while not all rooms are in current_rooms:
    current_rooms = largest connected component of start_room via unlocked doors
    for key not in current_keys and key not in placed_keys:
        if key has door connected to room in current_rooms:
            add key to current_keys
    randomly select new_key in current_keys
    place new_key in random unused location in room in current_rooms
    remove new_key from current_keys
    add new_key to placed_keys
    unlock all doors that can be opened using new_key

```

However, this algorithm does not randomly select a valid key placement *uniformly*.

For instance, imagine a dungeon consisting of three rooms: a start room and two side rooms connected to it. The door to one side room needs key $a$ and the door to the other needs key $b$. Each side room has one chest, and the starting room has two. I'll draw this dungeon as `[_|__|_]`, with the start room in the middle, the $a$ side room on the left, and the $b$ side room on the right.

There are six distinct valid configurations:

`[_|ab|_], [_|ba|_], [b|a_|_], [b|_a|_], [_|b_|a], [_|_b|a]`

However, the naive algorithm over-weights the first two choices, selecting them 1/4 of the time each and the remaining choices only 1/8 of the time. This is because earlier areas are unlocked for longer, so they have a higher chance to have a key placed in them.

Also notice that `[_|ab|_]` and `[_|ba|_]` are distinct configurations, since the elements of $L\_i$ are distinguishable from each other. It is not the same as specifying that $v\_i$ can hold at most $|L\_i|$ keys.

I thought about something like a dynamic programming-type algorithm, but the issue is that a valid configuration can be produced from an invalid configuration. For example, if we always placed $a$ before $b$ in the above example, then the configurations `[_|b_|a]` and `[_|_b|a]` could never be reached because `[_|__|a]` is not a valid partial configuration.

---

It's pretty clear that there are roughly at most $|L|^{|K|}$-many key placements, although for a generic graph, a good portion of these will not be valid.

In my particular problem, I have about 40 rooms with about 100 treasure chests spread around among them and about 20 keys. Enumerating all possible valid locations and then uniformly choosing a random one seems like it would be quite slow, especially if I want to use this for a larger scenario, where I have about 50 rooms with 1000 chests and 40 keys.

This question is pretty specific and I couldn't find any information about this type of graph, but I also don't really know what to search for it as.

I did find some information about generating such graphs where you can also choose which doors are unlocked with which keys -- in the context of surprise, surprise, dungeon generation for a game -- but here that information is fixed in advance and only the keys can be freely placed.

(I'm also interested in a harder problem where some of the doors are one-way (so the graph is a digraph) and we don't want the adventurer to ever get stuck in a room with no way out, but I suspect the above problem is hard enough to start.)

# Answer
The following decision variant of your problem is NP-hard in general:

> Given a graph,determine whether the graph has any valid placement of keys to make it unlockable.

In particular, there's a straightforward reduction from 3SAT, shown below in the appendix.

As a consequence, in the general case your problem is NP-hard too: take the graph, try to sample a valid placement of keys, and if the procedure returns a valid placement, then you know the graph is unlockable; if it gives up, the graph is not unlockable. However, this might not be terribly relevant in practice.

It does suggest a possible approach to your problem. We could construct a formula $\psi$ where every satisfying assignment corresponds to a valid placement of keys that makes the graph unlockable, and then ask to randomly sample from the satisfying assignments of $\psi$. It should be straightforward to construct such a formula; then see Using SMT solvers to generate random solutions to given predicate for one method for doing the latter. This approach will be exponential-time in the worst case, but it's possible that if your problem has enough structure, maybe it will be effective in practice.

---

# Appendix: The reduction

Suppose we have a 3CNF formula $\phi$ with $n$ variables $x\_1,\dots,x\_n$ and $m$ clauses. We'll have $2n$ keys (one for each $x\_i$ and one for its negation, $\neg x\_i$). The graph is a sequence of $n$ diamonds, one for each variable, followed by a sequence of $m$ vertices, one for each clause, like this:

I haven't shown the edge decorations or locations yet. Let's start with the $i$th diamond (corresponding to the $i$th variable, $x\_i$):

The edge $A\_i \to B\_i$ is decorated with the key $x\_i$, and the edge $A\_i \to C\_i$ is decorated with the key $\neg x\_i$. There is one location associated with $A\_i$; $B\_i$ and $C\_i$ have no locations. Notice how this forces any valid placement to put either $x\_i$ or $\neg x\_i$ into the location at $A\_i$, and in particular, we can either place the key $x\_i$ somewhere or place the key $\neg x\_i$ somewhere.

Next, let's look at one of the pieces of the right half of the graph, corresponding to the $j$th clause.:

I've shown the decorations we'd get if the clause is $(x\_3 \lor \neg x\_5 \lor \neg x\_7)$.

Finally, we add $n$ more isolated vertices $D\_1,\dots,D\_n$ (not shown above), each with a single location. The idea is that the keys that aren't placed into $A\_1,\dots,A\_n$ will be placed in $D\_1,\dots,D\_n$, so each key can be placed in exactly one location.

Note that $V\_m$ will be reachable if and only if there exists an assignment that satisfies the formula $x\_i$.
> 1 votes

# Answer
One approach is to use rejection sampling. In other words:

1. Randomly sample a placement of keys in locations (without regard to whether that placement allows the graph to be completely unlocked).
2. Test whether the resulting graph can be completely unlocked. If not, repeat (go back to step 1, and keep repeating until you find one that can be unlocked).

This does have a uniform random distribution on the set of valid graphs. The running time depends on what fraction of random placements allow the graph to be completely unlocked; I don't know what that fraction is.

There may be better algorithms.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is there an example of an AVL tree that is taller than a binary heap?
I am curious because I took a quiz and answered false to the question:

"The height of an AVL tree may be greater than the height of a binary heap with the same elements."

I have been trying to think of an example, but I just cannot figure it out. Does anyone know when this is the case?

# Answer
> 1 votes
Consider the following AVL-tree with 7-nodes. It has 4 levels. The form of a binary heap is determined by the number of its nodes. With seven nodes it would be the perfectly balanced binary tree with 3 levels.

An AVL-tree is height balanced, in the sense that the height of two sibling subtrees never differs by more than one. Leaves however may exist on several levels. Binary heaps are much more rigidly structured. Leaves exist only on two levels, and nodes are added level by level, from left to right.

The example tree is of a special type: it has the minimal number of nodes to get a tree of this height.

OK for an exercise, but it is quite uncommon to compare AVL-trees and binary heaps. The value of the nodes are ordered in completely different ways. Also binary heaps are in fact implemented as arrays, not as pointer structures.

---
Tags: binary-trees, heaps, binary-search-trees
---


# Question
Title: Finding the nth to last node in a linked list
I have a linked list with n elements and my goal is to find the 'nth to last element' in the list. I would like to present my approach. Please provide your opinions on whether it is optimal or how may I improve it.
Sample linked list "4-\>5-\>6-\>8-\>2-\>9-\>1"
Suppose the question indicates find 3th to last element in the list.
a)In a single pass, get the length of the linked list
b) Determine which node needs to be traversed upto (len(list)-nth element from last-1)
c) Make (len(list)-nth element from last-1) moves from head to get the element
Run time should be O(n)
Thank you

# Answer
tevemadar's solution is the standard double-runner/pointer method. I'll offer up a little different solution because I think it's interesting. It is a similar approach that utilizes sufficiently less "reads" if $n \gg k$.

We will do this by keeping track of a well positioned "checkpoint". Checkpoint `c1` will always be $k$ nodes behind checkpoint `c2`. Checkpoint `c2` will always be $\< k$ nodes behind our runner `a`. If we ever iterate `a` less than $k$ nodes past `c2` before hitting the end, we can restart at our checkpoint `c1`.

```
func(list L, int k):
  let n = 0
  let a = c1 = c2 = L.head

  do k times: a = a.next
  let c2 = a

  i = k
  while i == k:
    i = 0
    do k times or until a = null:
      i = i + 1
      a = a.next
    if i == k:
      c1 = c2
      c2 = a
    else: break
  a = c1
  do i times: a = a.next
  return a

```

You read the head node once, then $n$ nodes with your `a` iterator, then at most $k-1$ more times after going back to your check point. So this is $n + k$ reads total if you only consider `node.next` to be reads. Compared to the ordinary double runner method which would be $2n - k$ reads. Asymptotically there is no difference though. You can do the other operations you describe pretty trivially with some extra variables and pointer manipulation.
> 1 votes

# Answer
The length of list is not needed in my opinion, I would traverse the list using two iterators, k nodes apart:

```
1) run iterator 'a' to kth element
2) start iterator 'b' from head
3) proceed iterator 'a' to the end of list, stepping 'b' each time when you step 'a'
end) 'a' arrives to last element, 'b' arrives to 'kth to last' at the same time.

```

Of course you can also count indices in the process, for getting the length of list.
> 0 votes

# Answer
I think the best option is (in C):

```
void printFromElementIndex(int elementIdx, struct list* p){
    int idx = 0;
    while(p->next != NULL){
        // if the n(th) element is reached we print
        if(idx >= elementIdx)
            printf ("%d ->", p->k);

        // we go to the next element on the list
        idx++;
        p = p->next;
    }
}

```
> 0 votes

---
Tags: algorithms, data-structures, linked-lists
---


title: Develop a winning strategy for a game

text:
# Question
Title: Develop a winning strategy for a game
Okay so I've been going crazy about this problem I was given. It is as follows:

Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed remove 1, 5 or 6 matches. If it is your turn and you are unable to make a move then the game is over and you have lost.

The idea is to develop a strategy where you can always win. Note that you can always decides who goes first.

Not sure if I'm even on the right track but currently I can guarantee that if it is my go and then I remove 1, 5 or 6 matches, leaving my opponent with 22 matches I will win. But unsure how to guarantee that this situation will arise.

Any help would be appreciated even if it's just a reassurance that it is possible because I've spent hours within the last 2 days and still can't come up with a winning strategy that works all the time.

# Answer
> 1 votes
The nature of a position in this game depends only on $n \bmod{11}$. If $n \equiv 0,2,4 \pmod{11}$ then $n$ is a losing position, otherwise it is a winning position. You can prove this by induction by showing that (1) every move from a losing position leads to a winning position, (2) at every winning position one can move to a losing position. This can be checked by exhaustive case analysis:

* $0 \bmod{11}$: moves lead to $5,6,10 \bmod{11}$, all winning positions.
* $1 \bmod{11}$: removing 1 match leads to $0 \bmod{11}$, a losing position.
* $2 \bmod{11}$: moves lead to $1,7,8 \bmod{11}$, all winning positions.
* $3 \bmod{11}$: removing 1 match leads to $2 \bmod{11}$, a losing position.
* $4 \bmod{11}$: moves lead to $3,9,10 \bmod{11}$, all winning positions.
* $5 \bmod{11}$: removing 1 match leads to $4 \bmod{11}$, a losing position.
* $6 \bmod{11}$: removing 6 matches leads to $0 \bmod{11}$, a losing position.
* $7 \bmod{11}$: removing 5 match leads to $2 \bmod{11}$, a losing position.
* $8 \bmod{11}$: removing 6 match leads to $2 \bmod{11}$, a losing position.
* $9 \bmod{11}$: removing 5 match leads to $4 \bmod{11}$, a losing position.
* $10 \bmod{11}$: removing 6 match leads to $4 \bmod{11}$, a losing position.

For completeness, the $g$ values are $0,1,0,1,0,1,2,3,2,3,2$ (and then they repeat).

Your strategy is as follows: if $n$ is a winning position you start, otherwise you go second. Then you follow the strategy outlined above, which is guaranteed to win.

This strategy can be computed mechanically using the Sprague–Grundy function $g$.

---
Tags: graphs, game-theory, modelling, algorithm-design
---


title: Worst Case Scenario in MaxHeapify

text:
# Question
Title: Worst Case Scenario in MaxHeapify
First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most give a mathematical answer, but can't give a real example.

In CLRS 3ed pg 155 we have "The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the $\Theta(1)$ time to fix up the relationships among the elements $A\[i\]$, $A\[LEFT(i)\]$ , and $A\[RIGHT(i)\]$, plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i (assuming that the recursive call occurs). The children’s subtrees each have size at most $2n/3$ - $\textbf{the worst case occurs when the bottom level of the tree is exactly half full}$ — and therefore we can describe the running time of MAX-HEAPIFY by the recurrence $T(n) \leq T(2n/3) + \Theta(1)$.

I understand why the maximum nodes a subtree can have is around $2n/3$. I have two questions:

1) We're dealing with a heap - a "binary tree that is completely filled on all levels except possibly the lowest, which is filled from the left up to a point" (CLRS pg 151). For a given n, there's only one legal tree structure - we can't "make" its bottom level exactly half full. So what does it mean to say the worst run-time for n is when the bottom level is exactly full? If you mean that the worst-case happens when n is such that the bottom-level is half-filled, then it's worse in comparison to what? trees of other sizes? obviously different sizes have different run-times!

2) I understand why when there's a height difference it'll take another MaxHeapify call, but why does the bottom level have to be full? Can you give me an example of two trees of height larger than 1, where in one its bottom level is half-full, and in the other it's almost half-full (missing just one leaf from being half-full) and there's a worse run-time in the first one?

# Answer
> 2 votes
1) This is the worst case in regards to all the possible recurrences and their respective sub-problem sizes.

Let's take some small sample $n$'s for a tree of height $3$. This is to show how the varying worst-case sub-tree size ranges from 1/2 to 2/3.

$$ \begin{align} n &\quad \text{bottom half-full?} & \text{size of worst case sub-tree} \\ 8 &\quad no & 4/8 \\ 9 &\quad no & 5/9 \\ 10 &\quad no & 6/10 \\ 11 &\quad yes & 7/11 \\ 12 &\quad no & 7/12 \\ 13 &\quad no & 7/13 \\ 14 &\quad no & 7/14 \\ 15 &\quad no & 7/15 \\ \end{align} $$

We deal in worst case scenarios when defining running times. This is why we must look for the worst case sub-problem (sub-tree) to define the recurrence relation. Clearly with varying $n$ values, the recurrence would vary, so we must take the worst of them. This is clearly the result of the deepest level being half-full, resulting in the upper bound recurrence:

$$T(n) \leq T\left(\frac{2n}{3}\right) + \Theta(1)$$

Alternatively if we were looking for a lower bound, we should look for the best case of all those worst case sub problems. We could then achieve:

$$T(n) \geq T\left(\frac{n}{2}\right) + \Theta(1)$$

2) The heap with the bottom level half full will always have the worse running time no matter how trivial the difference is. Minor differences like the one you described are not important. We're not comparing for one instance, time complexity is used to compare on a larger scale. On a large scale you can see the size of the sub problem ranges from n/2 to 2n/3.

# Answer
> 0 votes
For a given algorithm, the running time can depend on the particular data configuration.

A worst-case scenario is one that corresponds to the maximum number of operations from all possible datasets. So the comparison is between executions from different datasets.

---
Tags: data-structures, runtime-analysis, heaps
---


# Question
Title: Regular expression for even/odd string on alphabet
Given the alphabet $\\{ a,b \\}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the letters can be paired, so there are four possibilities: $aa,ab,ba,bb$, the regular expression(for even lenght strings) so is:

$(aa+ab+ba+bb)^\* $

But can I write this in this other (more compact) way?

*(Using, e.g., the notation of Hopcroft-Motwani-Ullman)* given a language $L$,

we write $L^i:=\\{ w\_1w\_2...w\_i \ \ \ s.t. w\_1,w\_2,...,w\_i \in L \\}$

Then given that $(a+b)$ is (as a regular expression) the notation for the strings formed by one symbol, $a$ or $b$, then $(a+b)^2$ as in the notation above is

$\\{w\_1w\_2 \ \ \ s.t. w\_1,w\_2 \in (a+b)\\}=\\{aa,ab,ba,bb\\}$

So i can rewrite the notation for the regular expression for even lenght words as:

$((a+b)^2)^\*$

But this holds in general, so if I want the strings of lenght a multiple on $n \in \mathbb{N}$, I can consider:

$((a+b)^n)^\*$

As the regular expression.

I feel like this is somehow cheating and that this argument is not valid, but to me it seems correct: because it is true that exponentiation is not an operation in the language of regular expressions, but it is also true that in reality here exponentiation is only the concatenation $n-$times of the regular expression $(a+b)$, so $(a+b)^2=(a+b)(a+b)$, $(a+b)^3=(a+b)(a+b)(a+b)$, which is always a valid operation for regular expressions.

> **So my question is**: *Is the first way in which I have expressed the regular expressions for even-lenght words the most concise way to write it? And if the second way in which I have expressed it is correct, can this be generalised for $n$ generic (as I proposed)?*

# Answer
> 2 votes
How about an expression for even strings $((a+b)\cdot(a+b))^\*$ and deriving the one for odd strings from it: $((a+b)\cdot(a+b))^\*\cdot(a+b)$?

# Answer
> 1 votes
Here is an even shorter regular expression for the set of even length strings: $$ E $$ where I define $E = ((0+1)(0+1))^\*$.

The morale is that in order to talk about the shortest regular expression, you have to fix the syntax of regular expressions in advance. If you allow powering in your syntax, then $((0+1)^2)^\*$ could be shorter than $((0+1)(0+1))^\*$ (whether it is or not depends on how you measure length). If you don't allow powering in your syntax, then $((0+1)^2)^\*$ isn't a valid regular expression.

One standard definition of regular expressions over an alphabet $\Sigma$ goes as follows:

* $\epsilon$ and $\emptyset$ are regular expressions.
* For each $\sigma \in \Sigma$, $\sigma$ is a regular expression.
* If $r$ is a regular expression then so is $(r)^\*$.
* If $r\_1,r\_2$ are regular expressions then so are $(r\_1+r\_2)$ and $(r\_1r\_2)$.

This defines a language over $\Sigma \cup \\{\epsilon,\emptyset,(,),^\*,+\\}$.

Under this definition, $ab$ is not a regular expression over $\Sigma = \\{a,b\\}$, since the parentheses are missing. However, in practice we do interpret $ab$ as a regular expression, because we are using a more complicated syntax in which parenthesis are optional and different operators have precedence. Yet in the back of our minds, we interpret $ab$ as the regular expression $(ab)$. Formally, every "relaxed" regular expression has a standard form which does correspond to the specification above, and we often identify the two.

Other syntactic sugar such as powering is treated similarly as a shortcut which helps humans write the regular expression, but is absent when discussing the regular expression formally, for example when measuring its length.

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


# Question
Title: Words equal to the concatenation of their odd and even position - characters
Let $\Sigma = \\{0, 1\\}$ and $$L = \\{ w \in \Sigma^\* | w = \mathrm{odd}(w) · \mathrm{even}(w) \\},$$ where $\mathrm{odd}(w) = w\_1, w\_3, w\_5 \ldots{}$ and $\mathrm{even}(w) = w\_2, w\_4, w\_6, \ldots{}$ are the words constructed from the characters in all the odd and even positions of the string. I.e. $w = 0110110110 \in L$, because $\mathrm{odd}(w) = 01101, \mathrm{even}(w) = 10110$ and $w = 01101 \cdot{} 10110 = \mathrm{odd}(w) \cdot{} \mathrm{even}(w)$.

> Is $L$ regular?

I've tried using the Pumping Lemma for strings of the sort $0^{2n+1}1$ but I can't fix the value of $v^i$ from $w = uvx$ to have an either even or odd length.

I also tried to construct the DFA but it seems to need an infinite number of states to "track" which characters of $w$ get mapped to $\mathrm{odd}(w) \cdot \mathrm{even}(w)$, so my best bet is it's irregular, which means I need to find a way to prove it with the Pumping-Lemma.

Any ideas how I can find a suitable string for the Pumping Lemma?

# Answer
> 1 votes
It would be more convenient to index word positions starting with zero. Let us take a look at $L \cap \Sigma^{2^n}$. Any word $w \in L \cap \Sigma^{2^n}$ satisfies $$ w = w\_0 w\_2 \ldots w\_{2^n-2} w\_1 w\_3 \ldots w\_{2^n-1}. $$ You can check that for $0 \leq m \< 2^{n-1}$ and $b \in \\{0,1\\}$, this is equivalent to $$ w\_{2^{n-1}b + m} = w\_{2m+b}. $$ In other words, if we think of the index as an $n$-bit string, then this is the same as $w\_i = w\_{\mathrm{rot}(i)}$, where $\mathrm{rot}(i)$ is obtained by rotating $i$ to the left.

A *necklace* is an equivalence class of words under rotation. What we have shown above is that $w \in L \cap \Sigma^{2^n}$ iff $w\_i$, interpreted as a function $\\{0,1\\}^n \to \Sigma$, is constant on necklaces. Denoting the number of necklaces of length $n$ by $N\_2(n)$, we deduce that $$ |L \cap \Sigma^{2^n}| = 2^{N\_2(n)}. $$ The explicit formula for $N\_2(n)$ shows that $N\_2(n) \sim 2^n/n$.

---

It is known that if $L$ is a regular language then there exists a modulus $m \geq 1$ such that for every $0 \leq i \< m$ there exist constants $C,d,\lambda \geq 0$ such that for $N \equiv i \pmod{m}$, $$ |L \cap \Sigma^N| \sim C N^d \lambda^N. $$ We can calculate $\lambda$ as $\lim\_{N\to\infty} |L \cap \Sigma^N|^{1/N}$ (the limit taken over $N \equiv i \pmod{m}$).

Now suppose that our $L$ were regular. Choose $i$ so that infinitely many values $2^n$ satisfy $2^n \equiv i \pmod{m}$. We have $$ |L \cap \Sigma^{2^n}|^{1/2^n} = 2^{N\_2(n)/2^n} = 2^{O(1/n)} \longrightarrow 1, $$ and so $\lambda = 1$. However, that implies that $|L \cap \Sigma^{2^n}|$ should have polynomial growth (in $2^n$), whereas it clearly has superpolynomial growth.

---
Tags: regular-languages, finite-automata, pumping-lemma
---


title: The 'directionality' of reductions?

text:
# Question
Title: The 'directionality' of reductions?
I've been finding myself a bit confused with the *direction* of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($HALT\_{TM}$)is undecidable. I know we can assume that it is decidable and then try to build a decider for the acceptance problem, which is impossible. But though we are using the Acceptance Problem ($A\_{TM}$) to help solve the decidability of the Halting Problem, we have reduced the Acceptance Problem to the Halting Problem, not the other way around, right?

I sometimes get a little bit confused when I encounter questions that ask me to deploy a reduction; I will be asked to reduce language $x$ to $y$, but what that means is that $y$ is a simpler instance of a problem of $x$, right (or at least should be)? I'm assuming it's impossible to reduce a simpler version of a problem to a more complex version of a problem, am I right in believing that?

# Answer
Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing $A$ to $B$ or $B$ to $A$?" moment.

Reducing $A$ to $B$ produces a statement of the form "If I could solve $B$, then I'd also know how to solve $A$". "Solve" in this sense could mean "compute using any Turing machine", or "compute in polynomial time" or whatever other notion of solution your context requires.

This may seem counterintuitive, since "$A$ reduces to $B$" implies that solving $B$ is at least as hard as solving $A$, so you haven't reduced the difficulty. However, you can think of it as reducing the number of problems you need to solve. Imagine that, at the start of the day, your goals were to find an algorithm for $A$ and an algorithm for $B$. Well, now that you've found a reduction from $A$ to $B$, you've reduced your goals to just finding an algorithm for $B$.
> 19 votes

# Answer
No. When $A$ reduces to $B$, it intuitively means that $A$ is simpler than $B$, not the other way around.

More practically: assume you want to check $x \in A$. Instead of doing that in some way, you transform $x$ according to some (reduction) function $y=f(x)$. You now have to check $y \in B$.

You haven't yet solved the initial problem $x \in A$, since now you are left with another problem to solve: $y \in B$. This means that you have *reduced* the initial problem to another one.

It might seem counter-intuitive at first that we reduce easy things to more complex ones. Indeed, pragmatically, why should one wanting to solve an easy task *reducing* themselves to an harder task? Wouldn't we like to reduce our task to an even easier task, instead?

However, the truth is: if we could solve a hard task $A$ reducing it to an easy task $B$, this means that $A$ was not really harder than $B$. Indeed, if solving $A$ can be achieved by applying the reduction function, and then solving the "easier" $B$, it means that $A$ was easier than $B$ in the first place.
> 5 votes

# Answer
A reduction from $A$ to $B$ is something that does part of the work needed to do $A$ and what remains to do is $B$. For example, "getting food" can be reduced to "cooking" by "getting ingredients". This means that "cooking" is *harder* than "getting food": Anyone that can "cook" can "get food" (assuming that the reduction "getting ingredients" always works, for example in the presence of a place giving ingredients for free).

Drawing things tend to make them easier to understand:

You want to build the blue box (which represents an algorithm that takes an input $x$ and decides if $x\in A$). The reduction is then the red box, and once you have it, the only thing that remains to do in order to build the blue box is building the green box. So if you have a red box (that reduces $A$ to $B$), building the green box (that decides $B$) is at least as hard as building the blue one (that decides $A$): If you have a green box it is very easy to build a blue one, while if you build a blue box you may not be able to build a green box.

Note that the reasons for the two conditions defining a reduction appear on this drawing: the fact that $f$ is computable means that you can build the red box, while the fact that $f(x)\in B\iff x \in A$ means that you can connect the two rightmost wires.
> 5 votes

---
Tags: computability, turing-machines, reductions, halting-problem
---


# Question
Title: Pushdown automaton for language with "or"
> Find a pushdown automaton accepting the language $$L=\\{A^i B^j C^k \mid 2k \le i \le 3k \text{ or } j \neq i+k \\}.$$

I can't construct the automaton because I can only imagine it with multiple stacks or with set-theoretic intersections.

# Answer
Presumably you are able to construct PDAs for the following languages: $$ \\{ A^i B^j C^k : 2k \leq i \leq 3k \\}, \\ \\{ A^i B^j C^k : j \< i+k \\}, \\ \\{ A^i B^j C^k : j \> i+k \\}. \\ $$ Now you can use non-determinism to construct a PDA which non-deterministically chooses which of the three PDAs to apply.
> 3 votes

---
Tags: pushdown-automata
---


# Question
Title: Is there any polynomial time algorithm for a restricted EXP-time problem?
Let we fix $\<T\>$ and $w$, where $\<T\>$ is its binary representation of a Turing machine and $w$ is input.

We want to check if $T$ doesn't halt over $w$ before $2^{|w|}$ steps. A trivial solution is to use a universal Turing machine which simulates $T$ on $w$ and counts its steps, but this method uses exponential time.

I wish to know do we have any polynomial time algorithm to check this for the fixed Turing machine and input?

If we had a high-level program or pseudo code, then we had the possibility to analyze it and figure out the time complexity without simulation. But by Rice theorem, we know that it is not possible to understand the behaviour of a Turing machine using its binary representation string. So it seems impossible to have a Turing machine which runs in polynomial time and understand that $T$ doesn't halt less than $2^{|w|}$ steps even for a fixed $T$ and $w$. I don't know how to prove it.

Edit (In order to be more clear about inputs and outputs):

There are two possible ways to think of it:

* We want a Turing machine $M$ that runs in polynomial time over its empty tape and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise.
* We want a Turing machine $M$ that runs in polynomial time over input $\<T\>w$ and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise. It's not important for us that what is $M$ output for other inputs.

I believe there is no such $M$ since it is not possible to understand what is a Turing machine doing without simulation of its steps. If such $M$ exists, then it is understanding somehow how $T$ acts on $w$ without simulation of $T$ on $w$. Of course for special cases like pseudo-code, we can estimate the running time. But the $T$ which we fix is not always a pseudo-code.

Edit 2: In order to fix the point Ariel mentioned in his answer,

We want a Turing machine $M$ with the second formulation that works correctly as we stated (it understand T takes exponential time running its input) for two inputs $\<T\>w\_1$ and $\<T\>w\_2$.

# Answer
> 0 votes
Your first formulation isn't very useful, as either the machine which simply writes $0$ on its tape (without putting in any effort) or the one which writes $1$, satisfy your condition. Fixing both $T,w$ means you have only one question at hand, and not a computational task we can reason about in terms of the amount of resources require to handle it. In that case, a simple yes or no consists as a valid answer, and we can output it in constant time.

In your second formulation, you're asking whether the language

$L=\\{(\langle M \rangle,w)| \text{$M$ halts on $w$ within $2^{|w|} steps$}\\}$

is decidable in polynomial time? The answer is no, since $L$ is hard (under polynomial time reductions) for the class $\mathsf{DTIME\left(2^n\right)}$. This means that if $L\in P$ then $\mathsf{P=DTIME\left(2^n\right)}$, contradicting the time hierarchy theorem.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: $\sqrt{n} = \Omega(3^{\log{}n})$ is not true? Why?
Had this question on an algorithm exam. Can any one explain why $\sqrt{n} = \Omega(3^{\log n})$ is false?

# Answer
We'll start with some arithmetic, and assume the base of the logarithm to be $x$. First, remember the log law: $$ \log\_{a}(b) = \frac{\log\_{c}(b)}{\log\_{c}(a)} $$ So $$ \begin{array}{rl} 3^{\log\_{x}(n)} &= 3^{\frac{\log\_{3}(n)}{\log\_{3}(x)}}\\ &=(3^{\log\_{3}(n)})^{1/\log\_{3}(x)} &=n^{1/\log\_{3}(x)} \end{array} $$ Whether $n^{\frac{1}{2}}$ is in big-omega of this then depends on what $x$ is.

If we make the right and proper computer science assumption that the base 2 logarithm is the only logarithm (that was a joke of course), then $1/\log\_{3}(x)=1/\log\_{3}(2)\approx 1.6$, which is certainly bigger than $1/2$.

You'd need $x\geq 9$ for the statement to be true.
> 5 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: What algorithm paradigm is a recursive solver of Sudoku?
I am interested in knowing what algorithmic paradigm are the usual recursive sudoku solvers. Can I consider it a local search? or are they Dynamic programming, greedy, divide and conquer, backtracking?

# Answer
> 5 votes
Let us go over your paradigms one by one:

* Local search: In this paradigm, we start with some solution and try to improve it by local changes. Local search can be applied to Sudoku in at least two ways:

1. Start with a non-legal solution (either not satisfying the Sudoku constraints or not conforming to the filled cells), and try to make local changes (say, one cell at a time) that make it more legal.
    2. Same as before, only we also allow partially filled boards. In this case we might as well start with the board as given, and at each step pick a cell and fill in some legal value. When we get stuck, we can choose a cell and erase it, and so on. This is a stochastic form of local search which in some sense goes against the essence of classical local search, which is completely deterministic and strives to reach an arbitrary locally optimal solution.
* Dynamic programming: In this paradigm, we reduce our instance to smaller instances in such a way that the "repertory" of smaller instances is small, and each could be reached in many different ways.

One way you could try to implement this paradigm to Sudoku is as follows. Pick an empty cell and fill it in all possible legal ways. For each such filling, check whether it leads to a solution. Each filling is a smaller problem since it has fewer empty cells. However, the number of possible smaller instances is huge, and each is reached in a unique way, so while this is the same as your recursive solution, it's not really in the spirit of dynamic programming.
* Greedy: In this paradigm, you repeatedly make choices that you cannot later change. In the case of Sudoku, this corresponds to identifying unfilled cells which have only one legal filling. This is the approach used by most humans to solve Sudoku, though some puzzles require rather elaborate case analysis to find such safe fillings.
* Divide and conquer: In this paradigm you divide your instance into independent instances which you solve separately, and then use their solutions to solve the original instance. One way this could be applied to Sudoku is by finding all possible solutions of 3×3 squares, and then try to combine them together. This is not only a terrible algorithm, but also the recursion is very shallow, whereas in divide and conquer we are aiming at deeper levels of recursion.
* Backtracking: The standard recursive approach for Sudoku (pick a cell, enumerate all values, and recurse) is a great example of backtracking, which is the paradigm that best describes this algorithm.

# Answer
> 0 votes
You can ask the following 4 x 81 questions:

```
Where in column c does the number x go
Where in row r does the number x go
Where in 3x3 block b does the number x go
Which number goes into cell l

```

Obviously you leave out those questions that are already forced by the filled out cells. Now if any of the remaining questions has 0 possible answers, then the Sudoku cannot be solved. If any of the questions has exactly one answer, then fill a cell according to that answer. If each question has two or more answers, then you use backtracking with all possible answers of one of the questions that had the smallest number of answers.

---
Tags: programming-paradigms, sudoku
---


# Question
Title: What is the complexity of determining Satisfiability of a CNF containing both Horn and Dual Horn clauses?
If a CNF contains both horn and dual horn clauses and does not contain clauses of other types, then can its Satisfiability always be determined in polynomial time?

If the answer to the above problem is yes, then suppose we only add XOR clauses in addition to horn and dual horn clauses, can the Satisfiability of this type of CNF be determined in polynomial time?

# Answer
3-CNF formulas contain a mixture of only Horn and dual-Horn clauses. 3-SAT, the Boolean satisfiability problem over 3-CNF formulas, is known to be NP-complete. So it is unlikely that the satisfiability of such formulas can be decided in polynomial time.
> 2 votes

---
Tags: complexity-theory, time-complexity, satisfiability, sat-solvers
---


# Question
Title: How do processors fetch instructions that are longer than the word length?
From what I have read, instructions under x86 can be as long as 15 bytes. Since x86 is a 32-bit architecture (64-bit for x86-64 obviously) how does it handle these long instructions? How are they stored in memory, and how are they fetched?

# Answer
> 4 votes
In general there is not relation between the processor register size (32-bit for x86, 64-bit for x86\_64) and the instruction size. Instructions are fetched by a dedicated hardware unit and the current instruction is stored the instruction register, but this register does not need to (and usually does not) have the same size as the data registers. On x86, this register must be able to hold 15 bytes. Instructions are fetched like everything else by issuing read commands to the memory. In general to speed up things, the CPU has an instruction cache so it will not just fetch one instruction at a time but rather an entire cache line at once.

# Answer
> 3 votes
Amaury Pouly's answer covers most of it: modern instruction fetch units work on cache lines, not words. A cache line might be 64 or 128 bytes.

However, that isn't the whole story. You still need to deal with the fact that the instruction fetch operation is uneven (in the sense that some cache lines may have a lot of instructions and some may have few), and that instructions may cross a cache line boundary.

Modern L1 instruction cache doesn't necessarily need to store only instructions. It's common practice to make the L1 instruction cache line slightly wider and store additional information which is computed when the cache line is inserted in the cache. This is called predecoding. A simple example might be to add a bit to each byte which marks where each instruction starts.

Because there are a lot fewer cache line loads than there are instructions executed, this can save time during instruction fetch.

As for cache line boundaries (or, indeed, implementing predecode), one way to model decoding an instruction stream is as a finite state machine of some kind. Modelling the problem this way lets you handle cache line boundaries in a straightforward manner: all you need to "know" between cache line fetches is what state you were in. The implementation may be more complex than this (e.g. to allow for more hardware parallelism), but this can all be handled from the finite state model.

---
Tags: computer-architecture, cpu
---


# Question
Title: Traveling Salesman -- number of qubits required?
I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In there, they give an example of how you could use quantum computers to solve the Traveling Salesman problem, for 4 cities. I may have missed the explanation somewhere in the notebook, but they use 9 qubits to address the problem -- can someone explain why 9? It is a hardcoded value in the actual code, which indicates to me that you could use different numbers...so what would be the tradeoffs with using more or fewer qubits, and how would that scale with the number of cities?

I understand that I can run the notebook and change the value to see how the results change, but I'd like to get a better theoretical grasp of why.

Thanks!

# Answer
The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a Hamiltonian, and so solved by a quantum computer. The number of qubits needed is the dimension of the Hamiltonian, which is also the number of bits in the encoding.

In TSP, the optimization is over permutations. The notebook suggests encoding a permutation by encoding its permutation matrix, which is an $n\times n$ binary matrix. Since the rows and columns sum to 1, we can deduce the final row and column from the rest of the entry, and so need to keep only $(n-1)^2$ variables. In your example, $n = 4$ and so $(n-1)^2 = 9$.
> 3 votes

---
Tags: algorithms, complexity-theory, quantum-computing, traveling-salesman
---


# Question
Title: Size of the language accepted by a Turing Machine
I want to figure out if the following language is Turing decidable, Turing acceptable but not turing decidable, or neither. The language is

```
{ρ(M) : |L(M)| ≤ 10}

```

My question for this problem is what does |L(M)| ≤ 10 mean? At first, I thought it meant that the language will only accept strings that are less than or equal to 10 in length, but I am not sure

# Answer
> ... what does $|L(M)| \leq 10$ mean?

This means that the size of the language accepted by the TM $M$ is less than or equal to $10$. In other words, TM $M$ accepts no more than $10$ strings (inputs), while the length of any accepted input may be greater than $10$.
> 2 votes

# Answer
if the problem is knowing if a TM accepts (or recognices) less than 10 words, then it can be acceptable or decidible, coz to recognize only 10 or less words you need to test the entire language associated to the original alphabet and determinate the "non-recognotion" of almost all words...

so neither

respecting the question of the matter of the size of the accepted words in relation to the fact of being decidible or not... usually is easier to recognice have more than N words than less than N... because "more than" means you only need to find the first N words and finish. On the other side, "less than" means you need to check all words to be sure that there are only N words and no more(wich means infinite cases to check)
> -2 votes

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


# Question
Title: Continuing the example of why it's hard to compute with univalence?
In "Towards a cubical type theory without an interval" Altenkirch and Kaposi motivate why it is hard to compute with univalence. They say:

> For example, we can define the equivalence `(not ,...)` between `Bool` and `Bool` and thus `univ (not ,...) : Bool =_U Bool`, and then using it, define a boolean `b`:
>
> ```
> coe : (A =_U B) → A → B
> coe (refl A) a :≡ a
>
> b : Bool
> b :≡ coe (univ (not, ...)) true
>
> ```
>
> We know that `b` should be false as we coerce along `not`, but `coe` was only defined for the case `refl` so the term `b` does not compute further. One may think that it would be enought to add the equation `coe (univ (f,...)) ≡ f` but this is not sufficient as shown by the following example. Here we use the `ap` (apply path) function for a `P : U → U` :
>
> ```
> ap_P : A =_U B → P A =_U P B
> ap_P (refl A) ≡ refl (P A)
>
> x : P Bool =_U P Bool
> x :≡ ap_P (univ (not, ...))
>
> ```
>
> To reduce this term we need to know how to transport an equivalence along an arbitrary type.

What I don't understand is the last sentence. Is the "arbitrary type" the result of applying `P` to `Bool`? I feel that for any given `P : U → U` we can write a corresponding `ap_P`. For example:

```
Maybe : U → U
Maybe A = () + A

Show : U → U
Show A = A → String

Endo : U → U
Endo A = A → A

ap_Maybe (univ (f, g, ...)) = univ (either id f, either id g, ...)
ap_Show (univ (f, g, ...)) = univ (\show -> show . g, \show -> show . f, ...)
ap_Endo (univ (f, g, ...)) = univ (\endo -> f . endo . g, \endo -> g . endo . f, ...)

```

Is this intuition already off? What would be a concrete `P` where this fails? Or is the problem that while we know how to transport an equivalence along *any* function `P : U → U` we don't know how to do it for *all* such functions?

# Answer
You are correct, in the sense that the elusive computational nature of Univalence is not so elusive for "ordinary" type constructors.

In fact, you might want to glance at Tabareau, Tanter and Sozeau's paper Equivalences for Free!, which outlines what you have just written, along with many more types of, well, types.

Trouble starts (as usual!) with dependent types, particularly when equivalent types start appearing in indices. Take the following type:

```
IndexedList (A : Type) : List A -> Type :=
   | INil : IndexedList A []
   | ICons : forall (a : A) (l : List A) (il : IndexedList A l), IndexedList A (a::l)

```

It's an interesting exercise to write down `ap_IndexedList` in this case, it's not trivial! But once this is done you then have to take into account types that depend on types that depend on $A$, etc. This is where things get pretty hairy.

Homotopy type theorists want to be able to describe this theory in full generality, since only this will capture the "ideal" of a constructive model of homotopy types.

But as Tabareau *& al* mention, this is not really all that useful for programing applications, where "single index nesting" is really all that is necessary (for the most part, obviously then proving things about dependent types might require more). So as far as *computer scientists* are concerned, we're pretty much ready for univalence!
> 5 votes

---
Tags: homotopy-type-theory
---


# Question
Title: Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?
We are assigning the colours white/black to the vertices of a DAG, under the condition that if $V$ is black and there is a path $V \to W$ for some vertex $W$, then $W$ is black.

Examples:

* In the case of a linear chain of $N$ nodes, the answer is $N+1$ - either all the nodes are white, or one of the N nodes is black meaning all subsequent nodes in the chain are black.
* In the case of $N$ nodes and zero edges, the answer is $2^N$.

A trivial solution is to generate all valid of the graph colourings, and then count the number of them. This can be done recursively in exponential time.

I'm looking for an efficient solution to the above problem. There is a seemingly O(n) dynamic programming algorithm that solves this for trees; I wasn't able to generalise it for the arbitrary DAG case.

# Answer
Your problem is #P-complete. The set of solutions can be identified with the set of antichains with the poset corresponding to the DAG (the correspondence identifies a coloring with the black vertices that have no black parents), counting the number of which has been shown to be #P-complete by Provan and Ball in The complexity of counting cuts and of computing the probability that a graph is connected.
> 6 votes

---
Tags: algorithms, graphs, combinatorics
---


# Question
Title: Finite state automaton's reaction to simultaneous events
What does happen if two events simultaneously occur at a particular state of a finite state automaton (FSA)?

For example, assume that an FSA's event table at its state $s$ is as follows:

$\delta(s,e\_1)=s\_1$ and $\delta(s,e\_2)=s\_2$. What will be the system's next state if both $e\_1$ and $e\_2$ occur exactly at the same time?

# Answer
Finite-state automata take a sequence of events as input. There is a single event in the input sequence at any given position. What if there are two different values at position 3 in the sequence $ababcaccab$? There aren't, that's just how the mathematical object is constructed.

The input to a FSA is not necessarily a sequence of events that happen one after the other. For example, when an FSA is used for string parsing, there's no concept of time. But let's assume that you're using an FSA as part of a model of something that reacts to events over time. Note that this is no longer just about automata theory, but also about what you're modeling. What if you want to express that two events are simultaneous? Then you'll need to use a more sophisticated mathematical tool.

The core of the mathematical tool can still be a finite state automata, but instead of taking a sequence of events as input, you'd take a sequence of *sets of events*. The thing is, in practice, this is rarely useful, because in practice, things do not happen simultaneously. At most, they happen simultaneously up to measurement error. Given that measurement error is, by definition, variable, the same physical process may or may not be observed as simultaneous if you try it again several times. Therefore it is not useful to consider simultaneity in the model: it brings extra complexity to the math without providing any extra insights regarding the physical process.

Simultaneity is a useful concept regarding events that have a duration: event A may end after event B starts, in which case events A and B overlap. But if you're interested in that, then you can't model A and B as single events, you need to distinguish separate events “A starts, B starts, A ends, B ends”. These start/end events happen sequentially.

There is one world where things do happen sequentially, which is the world of discrete time. Discrete time is used to model digital circuits (because it corresponds to how they work). Two events may happen during the same clock cycle; that's the definition of simultaneous here. A digital circuit is modeled as a finite state automaton in a straightforward way, but then each element in the input sequence is not an individual event such as “input 42 switches from 0 to 1”, but a collective event made of the state of all the states of all the inputs.
> 3 votes

# Answer
As far as I know a finite automaton (FA) may read only one input at a time, either $e\_1$ or $e\_2$ and hence the FA is in either $s\_1$ or $s\_2$.
> 2 votes

# Answer
Concurrency is not part of the finite automaton model (just check the definition), nor in any finite-state system I'm aware of. When implementing one, you would serialize incoming events.

You *could* define a new model that, in each state, accepts a set of input symbols/events. What happens is up to you, or part of the transition function. You'll see that your model does not become any more powerful (it's just a larger alphabet) so the theory behind this is probably not very interesting.
> 1 votes

---
Tags: automata, finite-automata, concurrency
---


# Question
Title: Is there a limit on transition function compositions in NFAs?
I want to prove regularity of a language that contains a known regular language $L$ using an NFA.

Say the transition function of the automation that accepts $L$ is $f$.

In my new transition function, is there a limitation on composition of $f$? For example, can I make the following transition in the new function?

$$f'(q\_i ,\sigma)=f(f(f(q\_i, \sigma))))$$

If not, why?

# Answer
You can define the transition function of an automaton to be whatever you want, as long as it's a function of the appropriate type, i.e., $Q\times\Sigma\to Q$ fora DFA and $Q\times\Sigma\to 2^Q$ for an NFA.

However, the composition you've attempted doesn't actually make sense. Since $f$ is the transition function of an NFA, it has type $Q\times\Sigma\to 2^Q$. As such, you can't write $f(f(q\_i,\sigma))$, since the argument of the outer application of $f$ is some subset of $Q$, whereas there are supposed to be two arguments: an *element* of $Q$ and a symbol from the alphabet. So, for a double-composition, you probably need to write something like $$\bigcup\\{f(q,\sigma)\mid q\in f(q\_i,\sigma)\\}\\,.$$ You can try to work out the triple-composition yourself.

But are you sure you want to do that? You're defining an automaton that says "Every time I read the character $\sigma$, I will do whatever the original automaton would have done if it read three $\sigma$s." As I said, you can make your automaton do whatever you want, but I'd be interested to know the context that makes this a sensible thing to do.
> 4 votes

# Answer
The transition function of a DFA is $Q \times \Sigma \rightarrow Q$. aka a function that takes a State and a symbol and outputs another state.

As long as that is valid it doesn't matter how it is built.

For example the DFA built from an NFA. There each state of the DFA is a subset of the states of the NFA and the transition function returns the union of the output of the NFA's transition function applied to each state in the input subset.
> 3 votes

---
Tags: regular-languages, automata, finite-automata, computation-models
---


# Question
Title: consistent heuristic - does it always exist?
I am studying for an artificial inteligence class, and i have to classify the following sentence

"For any search space, there is always an admissable and consistent A\* heuristic".

Well, i know that there is always an admissable heuristic, for example zero, since its an underestimation of the real cost (althoug this would lead to uniform cost instead of a\*).

What I would like to know is if there is always a consistent heuristic, and why.

Thanks for your help

# Answer
> 2 votes
The zero heuristic is trivially admissible, as you've noted. It's also trivially consistent as long as all step-costs are non-negative: if $h(x)=0$ for all $x$ and $c(x,y)\geq 0$ for all $x$ and $y$, then $$ h(x)\leq c(x,y) + h(y) $$ for all $x$, $y$.

---
Tags: search-algorithms, heuristics
---


# Question
Title: Randomized vs deterministic approach for multiset equality
Let $S\_1$ and $S\_2$ are two multi sets. We want to find, Is $S\_1 =S\_2$?

**Algo 1:**

Sort $S\_1$ and $S\_2$ and then check $S\_1 = S\_2$

**Running time :** $O(n \log {n})$, where $n$ is the size of the multi sets.

**Algo 2:**

Contruct two polynomials using $S\_1$ and $S\_2$ (example if $S\_1 = \\{1,1,2\\}$ then polynomial will be $(x-1)(x-1)(x-2)$)

Let us say we have now two polynomials $p(x)$ and $q(x)$, do $p(x)-q(x)$, now using polynomial identity testing check whether $p(x)-q(x) =0 $ or not. If it is zero then $S\_1$ equals to $S\_2$.

Question : Which algorithm is better Algo 1 or Algo 2?

# Answer
To understand the complexity of the randomized algorithm, you must delve into the implementation details.

Suppose $S\_1,S\_2$ consist of $m$ elements, each bounded by $n$ in absolute value, i.e. the input size is $O(m\log n)$. Let $P\_S=\prod\limits\_{w\in s}\left(x-w\right)$ be the polynomial corresponding to the set $S$. $P\_{s\_1},P\_{S\_2}$ are degree $m$ polynomials. Thus, in order to succeed with constant probability in testing whether $q(x)=P\_{S\_1}(x)-P\_{S\_2}(x)$ is the zero polynomial, you need to evaluate it at numbers in the range $\[0,cm\]$, for some constant $c$.

Suppose you choose $y$ uniformly at random from this range, then in order to avoid blowup in the intermediate values while computing $q(y)$, you need to compute the values modulo some $k$ (the standard trick in PIT).

Note that the blowup here is not exponential, unlike in PIT where the polynomials are given as algebraic circuits, so you can in fact directly compute $q(y)$. However, this will lead to handling $\Omega(m)$ bit numbers, which will result in quadratic running time, so you can still compute $q(y) \bmod k$ for a random $k$ chosen appropriately to save some time.

If $k$ is chosen at random from some range $\[1,R\]$, then a "good" event is that $k$ does not divide $q(y)$, in that case $q(y)\neq 0$ iff $q(y) \bmod k \neq 0$. To lower bound this probability, note that $k$ is prime with probability $\approx \frac{1}{\log R}$ (here you need some finite version of the prime number theorem), and that $q(y)\le (cm+n)^m$, hence it has at most $m \log (cm+n)$ different prime factors.

$ \begin{align\*} & \Pr\limits\left\[\text{$k$ is prime $\land$ $k$ is not a product of $q(y)$}\right\]= \Pr\left\[\text{$k$ is prime}\right\]\cdot\\ & \Pr\limits\big\[\text{$k$ is a product of $q(y)$} \big| \text{$k$ is prime}\big\]\approx \frac{1}{\log R}\left(1-\frac{\log (cm+n)^m}{R/\log R}\right) \end{align\*} $

Choosing $R=(m+n)^2$ suffices to make the above probability high enough, and yields constant success probability after $\approx\log R$ evaluations. Each evaluation requires $O(m)$ additions/multiplications of numbers with $\log R$ bits, thus the overall running time is $O(m\log ^2 R\log\log R)$, which is worse than sorting. Perhaps sharper bounds on the success probability will allow you to get rid of one of the logarithmic factors, but taking numeric operations into account will eventually show that you cant beat naive sorting. However, the randomized approach is not without merits, as it allows you to determine multiset equality between two parties with logarithmic communication (you only need to send $y,k$ and the evaluations of $P\_{S\_1},P\_{S\_2}$ on $y$ modulo $k$).
> 1 votes

---
Tags: algorithms, randomized-algorithms, polynomials
---


title: How to define function type in AGDA

text:
# Question
Title: How to define function type in AGDA
The "function" type $\rightarrow$ is predefined in Agda. But how would one define it if it was not predefined? Specifically I am talking about $\rightarrow$ in:

```
data Nat : Set where
     zero : Nat
     Suc : Nat -> Nat

```

# Answer
It is not possible: `->` is built into the underlying logic of Agda (and most dependently typed languages).

In particular, `->` is *not* a type constructor, because it has binding properties. Because you can define things like `(n : Nat) -> Vec A n`, the compiler needs to add `n` to the variables in scope in the right hand side of the arrow, so this can't be done.

There are ways to cheat with bindings. For example, you can define $\exists x : T \ldotp S\[x\]$ as `ex T (\x -> S)`, i.e. using a lambda to represent the binding. But, that lambda is typed using `->`. Having dependent functions built in is the starter that bootstraps the rest of the type system. It's the only way the language can express quantification, so it ends up being critical.
> 2 votes

---
Tags: type-theory, automated-theorem-proving
---


# Question
Title: Proving that it is undecidable if a Turing machine accepts a language that is its own reverse
I have a Turing machine M. How can I prove that $L(M) = (L(M))^R$ is decidable by constructing a Turing machine that can do this? I know how to figure out if two DFA's accept the same language (using the symmetric difference) however I don't believe it works for Turing machines. Now I am able to design a Turing machine where, for a string w, I can determine whether or not the reverse of w is also accepted by the language. The problem is that I'm having trouble determining if the set of all strings is the same as the set of all reverse strings. If I design another TM then I feel like it's just going to infinitely loop. So how can I prove that this is decidable?

# Answer
The decision problem

> Given Turing machine $M$, is $L(M) = (L(M))^R$?

is *undecidable*. This is a simple consequence of Rice's theorem.

The property (i.e. class of Turing-recognizable languages)

$$\mathcal{S}\_{\mathrm{rev}} = \\{ L \mid L \\; \text{recognizable and } L = L^R \\}$$

is non-trivial, since $\emptyset \in \mathcal{S}\_{\mathrm{rev}}$ and $\\{ ab \\} \notin \mathcal{S}\_{\mathrm{rev}}$.
> 4 votes

---
Tags: computability, turing-machines, decision-problem
---


# Question
Title: Paper-based algorithm to find longest formula which is common to at least two formulas
Given a list of logical formulas:

* f1: A&B
* f2: A&D&C
* f3: B&D&E
* f4: A&B&C
* f5:
* fn: ...

In this case I want A&B as the longest formula which is common to at least two formulas. Is there a simple algorithm to find the longest formula that could be performed on paper?

# Answer
For each pair of formulas $f\_i,f\_j$ from your list, find the longest formula common to both $f\_i,f\_j$. If things are as in your example, this is as simple as a set intersection. That gives you $n(n-1)/2$ candidates. Take the candidate that is the longest.
> 0 votes

---
Tags: algorithms, optimization
---


title: Knapsack Problem with Vector Values

text:
# Question
Title: Knapsack Problem with Vector Values
I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being summed are vectors (and them sum is the Euclidean norm of the sum of the vectors). Formally, given a set of $m$ vectors $v \in \Re^{n}$, a set of non-negative weights $\alpha \in \Re\_{0+}$, and a non-negative maximum Euclidean norm $W \in \Re\_{0+}$,

$$Maximize: ||\sum\_{i=1}^{m} v\_{i}x\_{i}||\_{2}$$ $$S.T.:\sum\_{i=1}^{m}\alpha\_{i}x\_{i}\leq W, x \in \\{0, 1\\}$$

What, if anything is known about the complexity of this problem? It seems like it should be NP-Hard at minimum (as a generalization of the 0-1 Knapsack Problem), but it is unclear to me whether the decision problem variant is NP-Complete.

# Answer
Yes, the decision problem is NP-complete. If $n=1$ it is exactly the knapsack problem, which is already known to be NP-complete.

Possibly related Given a set of 2D vectors, find the furthest reachable point.
> 1 votes

---
Tags: complexity-theory, knapsack-problems
---


# Question
Title: Does the write through cache copies the whole block or just the byte which is updated?
Just a basic question to ask

**Does the write through cache copies the whole block or just the byte which is updated?**

I went through the following question

*Array A contains 256 elements of 4 bytes each. Its first element is stored at physical address 4096. Array B contains 512 elements of 4 bytes each. Its first element is stored at physical address 8192. Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct mapped, 2K-byte cache with an 8 byte block size. The following loop is the executed*

```
for(i=0; i<256; i++)
A[i] = A[i] + B[2*i];

```

*How many bytes will be written to memory if the cache has a write-through policy?*

I calculated it as follows:

The cache can store the whole array with 2 elements per block (block size = 8bytes, element size = 4bytes). For every write, the whole block will be copied. For $0^{th}$ element, the block containing $0^{th}$ and $1^{st}$ element would be written. The same would be done for $1^{st}$ element as well.

So, for every iteration the 2 elements would be written. This makes the number of bytes as $256\*2\* (4bytes / element) = 2048bytes$.

But in the solution, they have just calculated the number of loop iterations ($256$) multiplied by the element size ($4byte$) which makes the answer $1024bytes$. If this is true, then the cache would update only the updated byte (not the whole block).

Which is correct?

# Answer
> 1 votes
The caching strategies could be very "domain specific" like efficient data caching for numerical data structure, graph data structures and algorithms, bio-informatics data structure, etc.. This is a nice Ph.D thesis about it: "Cache-efficient Algorithms and Data Structures: Theory and Experimental Evaluation"

For your specific program I think it will cache whole block of memory not only the specific data in array. It uses a general cache strategy. See Cache algorithms on Wikipedia.

# Answer
> 2 votes
I would say that write-through cache always knows which addressable units need to be written, so there is absolutely no reason why it should write the rest of the block. Therefore it does not.

I am intentionally saying "addressable units", because (though I am not sure) it would generally be aligned units of the same width as the bus, i.e. usually 4-byte. But that has no effect here when the elements are 4-byte.

In contrast write-*back* cache is likely to only keep per-block modified status. However a write-back cache would be delaying the writes and since the consecutive passes through the loop end up overwriting whole blocks, it would *still* write just 1024 bytes.

# Answer
> 0 votes
The answer really depends on the implementation.

A cache and memory subsystem *can* be designed to support writes on a byte granularity, but doesn't have to be.

For example, if the memory interface is 8B wide and can support only 1 write at a time (and the cache line size is 8B), there's no point in only writing 1 byte in a write-through scenario (I guess there's slight power savings, but it'd probably be overshadowed by the complexity of tracking byte-enables).

Most caches deal with entire blocks of data (whatever the cache line size is). But then, most caches are not write-through. However, they often support byte-selected writes for non-cacheable/non-temporal data as that data isn't cached.

# Answer
> -1 votes
A cache works by transferring a block at a time from/to RAM, so it copies a full block.

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: MESI Protocol Invalid cache line is attempted to be stored?
I am implementing a sample MESI simulator having two levels of cache (write back). I have added MESI status bits to both levels of cache. As it is a write back cache, the cache line is updated to L2 only when it is flushed. My doubts are

1. what should be the behavior when a cache line with INVALID state is flushed from L1 cache. Will it just ignore the transaction? It seems that is the only possibility..but it doesn't seem right.
2. Consider processor1(P1) modifying a cacheline shared by processor2(P2). Then that cache line in P2 will get status INVALID. If P2 has to update the same cache line in future and sees the state is INVALID, it should read the updated value from??what if it is still in modified state in P1(not yet written back to L2/Main memory)?
3. Consider a similar situation that P1 has a cache line in MODIFIED state, P2 has the same line in INVALID state. When P3 tries to retrieve the same line, it broadcasts a request to all L1 caches. According to the theory,if P3 cant get the cache line from any other L1 caches, it sends request to L2/main memory. In this case where will P3 get the requested cache line from? From P1 or from the L2/main memory? Or will P1 update to the main memory first and then send the cache line to P3?
4. I am using LRU for flushing the cache(write back). When flushing a cache if it is INVALID what should be the behavior? It just ignores the line?

# Answer
> 3 votes
INVALID means "not in the cache," so there is nothing to flush. When you mark a cache block as INVALID it means that the data *and the tag* are not relevant.

Similarly, for your second question. The line is not in P2's cache, so it should treat the line the same way it treats any other cache miss: (if it's a snoopy coherence mechanism then it should broadcast a message to all the other caches. If it's a directory based coherence mechanism then it should send a request to the directory.)

# Answer
> 0 votes
1. A cacheline that is invalid will not be affected by a flush.
2. The sequence goes:
    * Line A is in state S (shared) in P1 and P2
    * P1 sets its state to E (exclusive) and sends out a StUp (store upgrade) to some central directory (CD)
    * CD sends a SnpI (snoop invalidate) to all other agents (in this case, P2) telling them to set their copy of Line A to I (invalid).
    * P2 sends an Ack (acknowledge) to the CD. After receiving all Acks from all agents, the CD sends an AckE (acknowledge you are exclusive) to P1.
    * P1 is free to commit any write it does to Line A. But it doesn't (Line A remains E).
    * P2 now wants to write Line A, it sees that Line A is I in its own cache. So P2 sends a RdE (read exclusive) to the CD.
    * CD gets the RdE and looks up its directory and sees that P1 has Line A in state E. CD sends a SnpI (snoop invalidate) to P1.
    * P1 receives the SnpI -- but it hasn't written any data to Line A -- so it sends a AckI (acknowledge I've invalidated and I have no data to give you) to CD.
    * CD sees the AckI from P1 and knows there is no data from P1. It reads Line A from memory and sends a FillE (fill data with exclusive permission) to P2.
    * P2 gets the FillE and has the latest updated data. It can then write to Line A.
3. Similar to #2, the sequence goes:
    * Line A is in state S (shared) in P1 and P2
    * P1 sets its state to E (exclusive) and sends out a StUp (store upgrade) to some central directory (CD)
    * CD sends a snoop to all other agents (in this case, P2) telling them to set their copy of Line A to I (invalid).
    * P2 sends an ack (acknowledge) to the CD. After receiving all acks from every agent, the CD sends an AckE (acknowledge you are exclusive) to P1.
    * P1 is free to commit any write it does to Line A. It sets its local copy state to M (modified) and writes some data to it.
    * P2 now wants to write Line A, it sees that Line A is I in its own cache. So P2 sends a RdE (read exclusive) to the CD.
    * CD gets the RdE and looks up its directory and sees that P1 has Line A in state E. CD sends a SnpI (snoop invalidate) to P1.
    * P1 receives the SnpI and sees that Line A is M in its own cache. It sends a Wb (writeback) to CD.
    * CD sees the Wb from P1, which has data. It writes the data from P1 to both memory (optional) and sends a FillE to P2.
    * P2 gets the FillE and has the latest updated data. It can then write to Line A.
        4. In this case:
    * P1 does not have Line A. It wants to read/write Line A. It will look up the LRU to find space. It sees that it has space that is invalid, so it sets that entry in its cache to Line A and sets the cache state to either S (for a read) or E (for a write). It does not need to flush anything as the replaced cache entry was invalid.
    * P1 sends a RdS (read shared) or RdE (read exclusive) to the CD to make sure everyone else knows it has the data for Line A.
    * The CD replies with a FillS (fill data with shared permission) or FillE (fill data with exclusive permission).
    * P1 uses data in Line A for a Load. Or it is free to commit data to Line A for a Store.

---
Tags: cpu-cache, protocols
---


# Question
Title: Miss penalty for Write request in a Write-Back style system
If the processor is trying to write a word to a certain memory location, and the system uses a write-back style architecture, what happens in case of a *miss*? I'm assuming that the system would first load the cache line, update the specific word, and keep the cache line in the cache until it has to be replaced. Then it would commence the write-back operation upon removal.

So, the penalty for a missed write-back is actually a cache line read, correct?

# Answer
Depends on what you mean by "penalty". In theory (and in practice in high performance processors), a store does not need to stall subsequent instructions, so there's essentially no penalty at all from a store *miss*.

If you're talking about issue-to-commit time (i.e. when the store can be considered permanent) then the latency would indeed be when the cache line read occurs.

NOTE:

Most if not all architectures (ARM for example) allow non-temporal store hints. In practice most processors treat these as non-cacheable stores. So they go directly to memory without the need to grab the data into cache.

Some microarchitectures detect store streams to a temporal block. They support a type of RdNoData command that simply grabs store permissions without transferring data.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Is it possible to reconstruct graph if we have given matrix of shortest pairs
I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally:

Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such that from this graph we only have given matrix $g$ of size $N \cdot N$ elements, such that $g(i, j)$ gives the shortest path between nodes $i$ and $j$, note that it doesn't mean that nodes $i$ and $j$ are directly connected with edge.

**What I think**

We can say that node $x$ belongs on the path from node $a$ to node $b$ if and only if: $g(a,b) = g(a, x) + g(x, b)$.

If we fix nodes $a$ and $b$ in $O(N \cdot N)$ and we iterate over all other nodes, we will get total complexity of $O(N^3)$.

Is it possible to reduce this complexity to $O(N^2)$.

Thanks in advance.

# Answer
> 6 votes
I would suggest the following approach.

Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$.

Maintain a partition $P$ of nodes $V = \\{1,2,\dotsc,N\\}$.

Maintain a tree $T$.

We will maintain the invariant that $T$ contains some edges of the tree that we are trying to reconstruct, each part $X \in P$ is some subtree that we have not reconstructed yet. Eventually, $T$ will be the tree and $P$ will consist of singleton sets.

Initially, $P = \\{V\\}$ and $T = \emptyset$.

Apply the following operation repeatedly until $H$ is empty:

* In $H$, find and remove a triple $(i,j,w)$ that minimises $w$.
* See if $i$ and $j$ are in the same part of $P$. If not, discard this triple and try again.
* Now we have a pair $(i,j)$ and a part $X \in P$ such that $i\in X$, $j \in X$. We now know that $\\{i,j\\}$ has to be an edge in the subtree induced by $X$.
* Add $\\{i,j\\}$ to $T$.
* For all nodes $v \in X$, see if $v$ is closer to $i$ or $j$. Based on this information, refine the partition $P$ by replacing $X$ with $X\_i$ and $X\_j$, where $X\_i \subseteq X$ contains the nodes that are closer to $i$, and $X\_j$ similarly.

If I am not mistaken, the time complexity is roughly as follows, assuming appropriate data structures:

* We extract $O(N^2)$ triples.
* Only $O(N)$ triples will result in something added to $T$. These are the triples that require nontrivial work.
* For nontrivial triples, the operation that dominates is splitting. There we will need to check in the worst case $O(N)$ nodes.
* So overall the running time is something like $O(N^2) + O(N) O(N) = O(N^2)$.
* On top of this we pay whatever time we used to construct $H$. A simple solution is to just sort the triples $(i,j,w)$ by $w$. The cost depends on what kind of $w$ values you might have, but it isn't much worse than $O(N^2)$.

# Answer
> 1 votes
Reconstructing an *unrooted undirected weighted tree* from its distance matrix is an important problem in bio-informatics, where it is used in the context of creating phylogenetic trees.

A commonly used tool is the algorithm of neigbour joining, a clustering method. It performs very simple computations in the matrix, basically repeatedly recalculating weighted distances. Its complexity is $\mathcal O(n^3)$.

A tree defines a metric which is "additive" and satisfies the so-called "four point condition". Neighbour joining is quite robust in the sense that is also constructs acceptable trees if the metric is not exactly additive. In the case of bio-informatics exact information is not always available.

# Answer
> 1 votes
Since you already have a matrix of shortest distances between all nodes in the graph, you can treat each of these pair values as an edge in a separate graph. Now, if you compute the minimum spanning tree of this graph, you get an undirected acyclic graph (forest), which will span across all $N$ nodes, preserving the shortest distances from the original matrix. You could use Kruskal's algorithm for this, which isn't that hard to implement, and it will run in $O(E$ log $N)$, where $E$ is the number of edges, and $N$ the number of vertices.

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


# Question
Title: What kinds of programming pitfalls modern languages are able to find?
I often see claims that modern functional strictly-typed languages are 'safer' than others. These statement mostly linked with type systems and their ability to explicitly express the following pitfalls:

* Alternatives in function result. Maybe and Either datatypes vs. exceptions and null-pointers in C++-like languages.
* Access to mutable state (possibly inconsistent behavior over time). State datatype in Haskell vs. variables in C++-like languages.
* Performing IO. IO datatype in Haskell vs. just doing things in C++-like languages.

Haskell allows to express constraints required for safe handling of these situations. And compiler is able to warn programmer when he doesn't follow them.

Although pitfalls above are definitely the most common ones I can think of much more, for example:

* Unexpected resource consumption. Memory, CPU, disk, bandwidth.
* Inconsistent access to shared resources. Like read and write interference, broken lock ordering.
* System-level failure. Like crashing process or pulled plugs.
* Unexpected execution time for IO, timing violation.

Is there languages, libraries or at least models which allow to express constraints from the second set and yield a warning when they are not met?

# Answer
Substructural types ( http://en.wikipedia.org/wiki/Substructural\_type\_system ) can be used to provide some version of each of those. As a summary, while normal types control how something may be used, substructural types further control when or how often it may be used.

* Affine types can be used to construct languages capable of expressing all, and only, polynomial-time functions. http://www.cs.cmu.edu/~fp/courses/15816-s12/misc/aehlig02tocl.pdf
* Linear types can enforce that memory is accessible when variables go out of scope, enabling a kind of "static garbage collection." Similarly, ordered types can be used to require that variables are used in a LIFO order, allowing them to be stack-allocated. Regions ( http://en.wikipedia.org/wiki/Region-based\_memory\_management ) are also useful here. The first chapter of Advanced Topics in Types and Programming Languages provides a nice introduction to using linear and ordered types for this purpose.
* Affine types also enable typestate-oriented programming ( http://www.cs.cmu.edu/~aldrich/papers/onward2009-state.pdf ). Typestate is used to enforce certain orderings in APIs (e.g.: can't read from a closed file), but can also be used to enforce safety properties. Requiring a block that handles some error can be encoded as requiring a function that transitions some object from an error state to a recovery state.
> 7 votes

# Answer
As something on the more extreme end, there is $\lambda\_{\text{zap}}$, a typed lambda calculus designed to handle transient hardware faults e.g. cosmic rays. It is described in Static Typing for a Faulty Lambda Calculus by Walker et al.

As for things like "pulling out the plug", this is typically handled by transactions. Since programming language data structures and computations are not usually intended to be durable, this is rarely built into a language and instead it's handled by database systems. There is work on static analysis on detecting when coordination is necessary such as the Dedalus/Bloom work, and when transactions can be weakened or eliminated such as the coordination avoidance work by Peter Bailis. Related is the techniques Rust uses to avoid concurrency issues utilizing its substructural type system.
> 4 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: Are neural networks inherently imperfect because they mimic an imperfect machine (human)?
Neural networks are the base for all(most?) of the machine learning / deep learning algorithms/programs.

Humans don't have fixed algorithms to decide or do something. Initially, we don't know how a snake is supposed to look. **We learn** that **from experience**. But our learning is never perfect. Once in a while, we mistake a black wire lying on the floor for a snake. Or **we mistake the snake for a wire**.

Given that **neural networks are using the same technique as humans, are they inherently imperfect?** Surely, we can make the self-driving network much better than best human, but that is because it got much more experience(24x7) than the human. **But can we guarantee it's perfectness?**(**mathematically, or at least by testing**, enough to make people trust in the programs)

---

I have this question because of the moral implications ML programs bring. I guess this will cause a lot of problem in adopting these technologies, especially when human life is at stake(eg. surgeon, self-driving cars, self-flying jets) as humans would rather rely on an imperfect human than a lesser imperfect AI.

# Answer
It's better to think of neural networks as inspired by human biology, not that they're using exactly the same mechanism.

The notion of "inherently imperfect" isn't well-defined, so the question isn't meaningful. And, no, neural networks aren't always imperfect. For instance, suppose the learning task was "label everything 0". If you give a neural network a training set with one million examples, all of which have the label 0, then the neural network might well learn to output label 0 on all possible inputs.

As far as moral implications, it's not clear that it matters much *why* neural networks are imperfect; what's important is that they are often imperfect. But moral implications are probably more a matter of the study of ethics and philosophy than the science of computing, so I'll leave that there.

Finally, I encourage you to avoid binary thinking. Don't divide the world into "perfect" vs "imperfect". An engineer would say that in practice nothing is perfect; it's all about degrees of imperfection. One system might be good enough, or better than the reasonably available alternatives, even if it's not 100% perfect.
> 1 votes

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Is implication(function) more fundamental than lets say conjunction(product) in type theory?
According to the answer at (How to define function type in AGDA) the function type is kind of a fundamental thing in Agda and needed for bootstrapping, hence end user can not define it like what they do for conjunction(product) type and has to be predefined at the language level. Does this mean that implication(function) type is more fundamental than types like product(conjunction) since function is used in defining those types?

# Answer
> 5 votes
For Agda, I think, as stated in the other question, that the fact that function types (or rather Π-types) are built-in while pairs (or even Σ-types) aren't so much is a reasonable argument that they are more fundamental *in Agda*. That said, even there it's not completely clear cut. For example, Σ-types/pairs are introduced in Agda via inductive data type declarations which are largely unrelated to Π-types. On the other hand, you could Church-encode pairs in terms of Π-types but to actually push this all the way through you'd need universes (which Agda does have) so it's not Π-types alone that do it.

I find comparing "how fundamental" things are very ambiguous and usually not useful. Something being "more fundamental" means it's "closer" to some foundations (fundament). In the context of a specific foundational system, e.g. Agda, that can be reasonably clear, but in general things that are fundamental in one foundation may be derived in another. More generically, "fundamental" has connotations that can easily pull in opposite directions. On the one hand, if I can derive $X$ from $Y$ but not vice versa, it would seem $Y$ is "more fundamental" in some sense. On the other hand, "fundamental" has connotations of simplicity, minimality, and a kind of unavoidability. If given all of $X$, $Y$, and $Z$ I can derive $W$, but given just $W$ I could derive each of $X$, $Y$, and $Z$, is $W$ more fundamental or less fundamental than $X$? Maybe $W$ is just a complex composite of $X$, $Y$, and $Z$. *Because* $X$ is derivable from $W$, that means $X$ is a more omnipresent concept; $X$ can exist even if $W$ does not but not vice versa.

At any rate, let's move to some more technical goodness that talks about how pairs and functions relate without trying to rank them. Unsurprisingly, category theory provides a good vantage point for gaining insight on these types of questions, though it is important to compare what the category theory suggests to what the type theorists actually do because these don't always line up. It can be quite interesting on both sides to see what is needed to make them line up.

Arguably the simplest example is cartesian closed categories. A cartesian category is one that has finite products, this means (the existence of terminal objects and) $\text{Hom}(A,B)\times\text{Hom}(A,C)\cong\text{Hom}(A,B\times C)$ (natural in $A$, $B$, and $C$). This is a characterization of binary products. A cartesian closed category additionally has $\text{Hom}(A\times B,C)\cong\text{Hom}(A,C^B)$ characterizing exponents in terms of products. This is to say a (parameterized) adjunction $-\times B\dashv (-)^B$. Hagino's Categorical Programming Language (CPL) described in his thesis allows declaring the function type constructor just this way (see sections 3.3.2 and 3.3.3). The type theoretic view of this is the simply typed lambda calculus (STLC) *with products*. But the STLC is usually *not* presented with products, or at the very least they are optional. So how are function types described in STLC without products? Usually by the following two rules (or some variation on them):$$\cfrac{\Gamma, x\\!:\\!A\vdash M:B}{\Gamma\vdash(\lambda x\\!:\\!A.M) : A\to B}\to\\!\\!I\qquad\cfrac{\Gamma\vdash M : A\to B\qquad \Gamma\vdash N:A}{\Gamma\vdash (M\\,N) : B}\to\\!\\!E$$ This characterizes function types without any reference to product types. This is typical in modern type theory; type constructions are characterized without referencing other type constructions so that you can build type theories a la carte. In tihs sense, product types and function types are somewhat orthogonal.

Why does the categorical approach need products? Roughly speaking, an arrow $t\in\text{Hom}(A,B)$ corresponds to a term $x\\!:\\!A\vdash t:B$. So the issue is simply that we need some way of talking about arrows with more than one input. Products are one way, but an alternative, more direct approach would be to use (cartesian) multicategories. However, a more common approach is to split the adjunction characterizing function types in terms of product types into two adjunctions. Instead of having $-\times B\dashv (-)^B$ as described earlier, we can split this into $\Sigma\_B\dashv p^\*\dashv \Pi\_B$ where $p : \[\Gamma,B\]\to \[\Gamma\]$ and $p^\* : \mathcal{E}\_\Gamma\to\mathcal{E}\_{\Gamma,B}$. Here $\mathcal{E}\_\Gamma$ can be thought of as a category of terms in context $\Gamma$. The machinery to do this is indexed or mostly equivalently fibered categories. $p^\*$ is called a weakening functor and it corresponds to adding an unused variable (of type $B$) to the context. Now we can consider indexed-/fibered-categories where only one or the other (or neither or both) of those adjunctions hold. A simpler but less general approach to this is to use polycategories as Hasegawa does in Decomposing typed lambda calculus into a couple of categorical programming languages. A polycategory, $\mathcal{C}\[x:B\]$, is a category, $\mathcal{C}$, that has a terminal object and to which an arrow $x : 1 \to B$ is freely added. We of course have an inclusion of $\mathcal{C}$ into $\mathcal{C}\[x:B\]$, and this inclusion takes the place of $p^\*$. When this perspective is related back to type theory, we end up splitting the lambda calculus into the kappa calculus and the zeta calculus. The kappa calculus captures a first-order notion of multi-parameter functions. The zeta calculus captures the higher-order aspect of the lambda calculus, but the result is quite strange and awkward. Either way, these approaches place product types and function types on somewhat even ground.

---
Tags: type-theory, dependent-types, curry-howard
---