title: Expressing that a functor is natural

text:
# Question
Title: Expressing that a functor is natural
The Haskell `List: Type -> Type` constructor implements the `Functor` typeclass with function `fmap f = map f`. This functor that applies the morphism `f` to each element of a list works, but there are other equally valid functors, for example `fmap f = map f . rev` which first reverses the list before mapping over it. Is there a concept in category theory that expresses the fact that the first choice of functor is in some sense "more natural" for this type constructor?

# Answer
> 3 votes
Being a functor requires two properties:

1. `fmap id = id`
2. `fmap (f . g) = fmap f . fmap g`

The definition `fmap` fails the first condition:

```
fmap id = map id . reverse = reverse != id

```

So that's not a functor at all!

And it even fails the second condition:

```
fmap (f . g) = map (f . g) . reverse
             = map f . map g . reverse
             = map f . fmap g
             = reverse . map f . reverse . fmap g
             = reverse . fmap f . fmap g
             != fmap f . fmap g

```

Which is quite clear if you think about it:

* `fmap (f . g)` reverses the list once and then maps its elements via `f . g`
* `fmap f . fmap g` reverse the list, maps via `g`, *then reverses the list again* and then maps via `f`!

---
Tags: category-theory
---


# Question
Title: What are thin-core and fat-core processors
I am reading a paper called *Back to Thin-Core Massively Parallel Processors* by Ami Marowka (*Computer*, 44(12):49–54, 2011; IEEE Xplore).

However I have a question about the title of the article: what does "thin core" (and for that matter, "fat core") mean?

Thank you!

# Answer
*Thin-core* is a simple processing unit, slower with less registers, for example GPU core or small, low-energy core.
*Fat-core* is full-fledged CPU core. The mobile version of CPU is still *fat-core*

From article:

> The IBM Blue Gene/P supercomputer (1 Pflop) is an example of a contemporary large-scale system design (294,912 processors) based on a many-thin (850 MHz, 1 Gbyte) processing-core approach.
> 1 votes

---
Tags: terminology, computer-architecture, parallel-computing
---


title: Bit Blasting Algorithm

text:
# Question
Title: Bit Blasting Algorithm
I found a pseudo algorithm which describes bit blasting: click (page 156,157). I am trying to implement it in C, but I don't understand it yet completely. Let's make an example:

Assume our bit-vectors have only a length of 2 bits (for simplicity) and they are unsigned and out bit-vector formula looks as follows: $\phi = x \\,\\,\\,\wedge\\,\\,\\, y\mid 2 = z \\,\\,\\,\wedge\\,\\,\\, 1 \< 3$.

Let's describe Boolean variables with $b\_0, b\_1,...$ ($x,y$ and $z$ are bit vectors).

The set of atoms would be $At(\phi) = \\{ x,\\,\\,\\, y\mid2=z,\\,\\,\\, 1\<3 \\}$ and therefore the initially $\beta = e(\phi) = b\_0 \\,\\,\\,\wedge\\,\\,\\, b\_1 \\,\\,\\,\wedge\\,\\,\\, b\_2$.

The set of terms would be $T(\phi) = \\{ x,\\,\\,\\, y, \\,\\,\\, 2,\\,\\,\\, z,\\,\\,\ 1,\\,\\,\\,3 \\}$.

# Algorithm

Line 2: $\beta$ is already set.

Line 3-5: We set the $t \in T(\phi)$ to Boolean variables, hence $x \rightarrow b\_3, b\_4\\,$ \- (because we said our bit-vectors only have a length of 2 bits), the same with $y$ and $z$, but what happens with constants? I would guess: $2 \rightarrow 1,0$ or more precise $2 \rightarrow b\_7=1, \\, b\_8=0$.

So after line 5, our $T(\phi) = \\{ b\_3, b\_4,..., b\_{14}\\}$.

Then I stuck, how does it go on? And how would the equisatisfiable Boolean formula $\beta$ look like after the algorithm? Other references to other algorithms would be also nice.

# Answer
> 4 votes
I assume the formula is

$$(x \ne 0) \land (y|2 = z) \land (1\<3).$$

We can handle each clause of the conjunction separately. If $x=(b\_3,b\_4)$, then $x \ne 0$ translates to

$$b\_3 \lor b\_4.$$

If $y=(b\_5,b\_6)$ and $z=(b\_7,b\_8)$, then $y|2$ translates to $(b\_5|1,b\_6)$, which simplifies to $(1,b\_6)$ (if you are doing simplification). Now $(1,b\_6) = (b\_7,b\_8)$ translates to

$$(b\_7=1) \land (b\_6 = b\_8),$$

which in CNF form is

$$b\_7 \land (b\_6 \lor \neg b\_8) \land (\neg b\_6 \lor b\_8).$$

Finally, $1\<3$ translates to True, if you are doing simplification. So, the final result is the conjunction of those:

$$(b\_3 \lor b\_4) \land (b\_7) \land (b\_6 \lor \neg b\_8) \land (\neg b\_6 \lor b\_8).$$

---
Tags: satisfiability, sat-solvers, smt-solvers, bit-blasting
---


# Question
Title: DFA for the set of strings of 0’s and 1’s such that there are two 0’s separated by a number of positions that is a multiple of 4
I've being trying to understand this statement for quite a long time especially the "number of positions" part, but i can't seem to interpret it correctly.What i understand is that the statement means that there should be two 0's seperated by a number of symbols that are multiples of 4 i-e (0 , 4 , 8 , 16...), according to my understanding the string "01110", should not be in the language as the 0's are seperated by three 1's which is clearly not a multiple of 4, but the solution to the problem i've seen here:

https://www.google.com.pk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjxtfzov9jWAhXGJ8AKHfP6D6gQFggmMAA&url=http%3A%2F%2Fwww.ics.uci.edu%2F~goodrich%2Fteach%2Fcs162%2Fhw%2FHW1Sols.pdf&usg=AOvVaw2XrD6v28VSz30I7l5jvdLd

Suggests that "01110" is in the language.

Can someone please help me with understanding what the question statement means?

# Answer
Your interpretation is correct. It looks to me like the "solution" is wrong (and the solution isn't strictly a DFA).

Assuming you don't mind an NFA (getting a DFA is a bit fiddly, but obviously doable), you can fix the solution by removing the $(q\_{4},0) \rightarrow q\_{5}$ transition, and adding $(q\_{5}, 0) \rightarrow q\_{5}$ and $(q\_{5}, 1) \rightarrow q\_{5}$ transitions.

After some fiddling, it seems like a minimal DFA for this has 23 states... not so much fun.
> 2 votes

---
Tags: formal-languages, finite-automata
---


# Question
Title: In the context of parametrized complexity
For instance, Subset Sum is classified :

```
    W[1]-hard, in W[P] (parameter:k, subset cardinality)

```

by the Compendium of Parameterized Problems, how the parameter could impact the membership of the problem on a specific class?

Looks like Parametrized Complexity is trying to provide a better problem classification for NP-hard problems.

# Answer
Firstly, there is an important part of the quoted statement you are missing - the parameterization. It can only be classified with respect to some parameterization. For example, **Dominating Set** is $\mathrm{W}\[2\]$-complete when parameterized by $k$, the size of the dominating set, but it is in $\mathrm{FPT}$ when parameterized by the treewidth of the input graph.

So a different parameter choice gives you different parameterizations, and hence (possibly) different complexity. Another way to think of it is that the parameterizations tell you which part of the input is the bit that makes the problem hard - so Dominating Set is hard when the graph has very large treewidth, but the size of the solution doesn't really play into it (i.e. when we "control" it by making it the parameter, the problem doesn't get easier, in contrast to say, Vertex Cover).

This approach allows problems to be examined from many angles via different parameterizations, to get a better quantified understanding of the sources of complexity for that problem.

The classical approach is more-or-less like taking a trivial parameterization for every problem (e.g. we just set the parameter to 1, regardless of the input) - this statement is a bit wonky, but a not-to-bad approximation to develop some intuition from.

To address your final statement, yes, that is one of the inspirations for the development of Parameterized Complexity - the observation that some $\mathrm{NP}$-complete problems had really good algorithms, but others were apparently completely intractable in practice. The theory was at least partially developed to provide a formalised way of approaching this weakness in classical complexity (the inability to certain classes of problems).
> 3 votes

---
Tags: complexity-theory, parameterized-complexity
---


title: Google DeepDream Elaborated

text:
# Question
Title: Google DeepDream Elaborated
I've seen a few questions on this site about Deep Dream, however none of them seem to actually speak as to what DeepDream is doing, specifically. As far as I've gathered, they seem to have changed the objective function, and also changed backpropagation so that instead of updating weights they update the input image.

I'm wondering if anyone knows exactly what Google did. They mention in one of their articles imposing Bayesian priors when they carry out their optimization, and with this I can imagine that getting the neural net to spit out an image for each label is not that difficult - we can simply set the label, and then optimize the input vector accordingly.

However, the interesting part of deep dream is that it does this per layer, and in this regard I'm not quite sure how it emphasizes the details in a per layer way.

Certainly, feeding in an image will give you values at each neuron, but then how can we use that information to exaggerate details in the original image? I've struggled to find any detailed write-ups about this.

References: Here vzn answered a similar question: https://cs.stackexchange.com/a/44857/49671

From that link, there is an implementation of Deepdream, here: http://auduno.com/post/125362849838/visualizing-googlenet-classes

Except it doesn't offer exaggeration of features as discussed here:http://googleresearch.blogspot.com/2015/06/inceptionism-going-deeper-into-neural.html

Where they both show the visualization of particular classes, and particular layers, and say:

> Instead of exactly prescribing which feature we want the network to amplify, we can also let the network make that decision. In this case we simply feed the network an arbitrary image or photo and let the network analyze the picture. We then pick a layer and ask the network to enhance whatever it detected.

# Answer
The idea of DeepDream is this: pick some layer from the network (usually a convolutional layer), pass the starting image through the network to extract features at the chosen layer, set the gradient at that layer equal to the activations themselves, and then backpropagate to the image.

Why does it make sense? Intuitively, it amplifies the features that are maximally activated in the network. By backpropagating this gradient, we'll make an image update that will boost any of the existing activations. If there's a cat-like detector in the layer and the image contains some patch that looks a bit like a cat, DeepDream boosts this activation by updating this patch to be even more cat-like. As a result, DeepDream is trying to find cats and dogs everywhere in the image (ImageNet dataset has lots of dogs, so the network has many dog-related neurons).

If you look at the code, the key part is `objective_L2` function that makes this: $dx = x$ and then backpropagates.
> 7 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, image-processing, computer-vision
---


# Question
Title: Single pair shortest path algorithm with time a constraint
I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional constraint "the total time should not exceed T time units", then the problem becomes much harder.

More formally:

The input consists of a set of n cities and m roads between pairs of cities. There can be multiple roads between a pair of cities $(i, j)$. For each road, you are given its departure city $x\_i$, its destination city $y\_i$, its duration $d$, and its cost $c$. The objective is to find the cheapest path between a pair of cities $(a, b)$ such that the cost is minimized while keeping the duration less than the maximum duration $T$.

I tried thinking on the lines of Dijkstra's and modifying the graph so that it is in some way possible to run a shortest path algorithm on it, but there seems to be no trivial way of doing this. Simple solutions like (follow a greedy strategy until you exceed the time limit, and then move on to the next element in the priority queue) don't seem to work because the use of a priority queue in the Dijkstra's algorithm and DEQUEUING the minimum element from the priority queue behave like destructive operations. There is a need to backtrack (of sorts) but the shortest path algorithms visit each node in the graph only once.

I've tried thinking about other simpler approaches using the Bellman-Ford algorithm, but the time complexity of the algorithm I turned out writing depended on $T$ (which is not very desirable).

I spent almost 2 days on this and every solution I try either seems to not work, or runs in exponential time. Is this problem NP hard or are there polynomial time solutions possible?

P.S. I am not looking for a practical implementation of this problem, just an algorithm that can solve this problem in polynomial time. Although any thoughts about how to efficiently implement this would be more than welcome :)

# Answer
Your problem is NP-hard: The partition problem reduces to it as follows:

Let $ S = \\{s\_0, ... , s\_{n-1} \\} $ be a multiset of non-negative integers.

Construct cities $ \\{ c\_0, ... , c\_n \\} $, with each city $ c\_i $ having 2 roads to $ c\_{i+1} $, one with duration $ 0 $ and cost $ s\_i $, the other with duration $ s\_i $ and cost $ 0 $.

Then find the minimum-distance path from $ c\_0 $ to $ c\_n $ with total duration at most $ \frac 1 2 \sum S $. This path has equal cost and duration iff $ S $ can be partitioned into subsets of equal sum.
> 3 votes

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


# Question
Title: Finding longest prefix of a given string in set of strings that satisfies some property
I have a set of strings, lets call them *RULES*. I have a function *F* which given 2 strings deterministically returns boolean value. Given one string, lets call it *QUERY*, what is the fastest way to find longest prefix (lets call it *P*) of *QUERY* which is a member of *RULES* for which *F(P,QUERY)* returns true?

That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type *T* is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type *T*.

An example:

Types are {A,B,C}.

Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1

View is defined by those rules: {/; C=\>true, A=\>true}, {/A1/B1; C=\>true}, {/A1; C=\>false}, {/A2; B=\>true, C=\>true}

Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1

Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.

# Answer
I'll answer your generic question. Store the RULES in a trie. Then, you can generate each prefix of the QUERY, traversing the trie as you go. This will let you enumerate all prefixes P of QUERY that are a member of RULES. For each such prefix P, you can then evaluate F(P,QUERY). The running time is $O(n)$ where $n$ is the length of QUERY, plus the time to do at most $n$ invocations of F. If you want, you can check the longest prefixes of QUERY first, in order of decreasing length, so that once you find a single prefix P where F(P,QUERY) returns true, you can stop immediately.

I don't believe it is possible to do better, without knowing something about F. Obviously, any algorithm must take at least $\Omega(n)$ time (since you must read each character of QUERY), and must invoke F potentially on each prefix that is a member of RULES.
> 1 votes

---
Tags: algorithms, optimization, strings, searching
---


title: Can CNN be used for numeric data

text:
# Question
Title: Can CNN be used for numeric data
I have a numpy array of shape N\_Samples x 360, as an example, consider the following:

```
 [ 89 94 56 - - - 55] <-360 length vector
 [ 56 98 55 - - - 98]
 |                  |
 |                  |
 [ 67 55 99 - - - 77] Total N such vectors

```

There is one label 0 or 1 corresponding to each of the 360- length vector I am asked to train this using CNN but everywhere I am observing that CNN is used for image classification. I am confused about the following:

1. Is CNN appropriate for such data?
2. If yes, then how concepts like max pooling and strides are applicable?
3. Should we use Conv1D instead of Conv2D?

I will also appreciate if some helpful papers or blogs are provided with respect to this context on how to adjust shapes of input and weight.

**Edit:** The 360-length vector is showing ECG signal values of one heartbeat. Keeping R-peak in the middle, I have 180 signal values after and 180 before the R-Peak to have 360 long chunks represent heartbeats (Sampling Rate: 360). I am using it to classify each heartbeat as arrhythmic or non-arrhythmic.

# Answer
> 3 votes
Yes, you can use a CNN. CNN's are not limited to just images. Use a 1D convolution, not a 2D convolution; you have 1D data, so a 1D convolution is more appropriate. A CNN is a reasonable thing to try, but the only way to find out if it actually works or not is to try it on some real data and evaluate its effectiveness.

You can also try simpler methods, like a fully connected network, or even logistic regression.

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


# Question
Title: String edit distance between strings x, y, with restrictions on 'intermediary' strings
This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient.

### Problem

Given a starting string $x$, a target string $y$, and a set of valid strings $V$, find the minimum edit distance between $x$ and $z$ where edits can only be character exchanges and each intermediary string $z\_i$ must be in $V$.

Further constraints on problem * **All** strings are length 8
* The complete character set for strings is $\\{A, T, G, C\\}$
* The starting string $x$ does **not** need to be in $V$, but $y$ is

### My Straightforward an slow-ish solution

When I see an edit-distance problem I immediately think of Dynamic Programming, but tradition Dynamic Programming approaches don't care about the intermediary stages of the string when transitioning between $x$ and $y$, so I wasn't 100% confident in this approach.

Noticing that given a small enough set $V$ I could quite quickly find all strings in it that were $1$ edit distance from my current string, I went we the following approach.

1. Start at string $x$ with target $y$ and set $V$ and current distance $0$
    * If $x == y$ the return current distance
2. Mark $x$ as 'seen' by removing it from $V$
3. Find all strings in $V$ that are 1 edit-distance from current string
4. recur on all candidate strings, keeping the same target, the updated $V$, and an incremented current distance

This approach isn't too terrible, and with some memoization thrown in it gets even more acceptable, but I get the strong feeling there is a much faster approach to solving the problem with out 'searching' through the set $V$.

# Answer
> 2 votes
I think your approach has merit, but you want to limit the amount of searches on $V$.

Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ with all nodes at Hamming distance one, respectively.

Now the problem is just finding a shortest path from $x$ to $y$.

---
Tags: dynamic-programming, edit-distance
---


title: DFA or NFA Construction

text:
# Question
Title: DFA or NFA Construction
I have to draw a DFA or NFA for a language that has two symbols lets say {0,1}. The condition is "such that exactly one of the two symbols 0 or 1 appears at least three times." I understood this as if 0 appears three times or more than 1 can be there for 0,1 or 2 times and if 1 appears for 3 times or more DFA fails and goes to dead state. The same will happen for the case if 1 appears 3 times or more and if 0 can be there for 0,1 or 2 times and if 0 appears for 3 times or more DFA fails and goes to dead state. I have been trying to create a DFA for this but failing everytime on condition like "01010". I am not sure if it is possible to create a DFA or NFA for this. I guess this is solvable by PDA only. Need help in making sure that I am thinking in right direction.

# Answer
> 2 votes
You only have a limited number of states to worry about:

Let note them $Q\_{i,j}$ where $i \in \\{0,1,2,3,4\\}$ is the number of `0` and $j \in \\{0,1,2,3,4\\}$ is the number of `1`; each up to a max of 4 $\implies$ only 25 states.

Then the transition is
$\delta(Q\_{i,j}, 0) = Q\_{i+1,j}$ if $i\<4$
$\delta(Q\_{4,j}, 0) = Q\_{4,j}$
$\delta(Q\_{i,j}, 1) =Q\_{i,j+1}$ if $j\<4$
$\delta(Q\_{i,4}, 1) =Q\_{i,4}$

Then the starting state is $Q\_{0,0}$ and the accepting states are all $Q\_{i,j}$ with $i=0 \oplus j = 1$ (where $\oplus$ is the xor operator).

---
Tags: formal-languages, finite-automata
---


# Question
Title: Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ Regular?
## Question

> Is $L=\left \\{ wxw \\,\\,|\\,\\,w,x \\,\in \left ( a+b \right )^{+}\right \\}$ regular?

## My Understanding/Doubt

We can say that Language

> $L\_{2}=\left \\{ wxw \\,\\,|\\,\\,w,x \\,\in \left ( a+b \right )^{\*}\right \\}$ is regular

By making $x=(a+b)^{\*}$ and $w=\epsilon$

Based on above Understanding , i can say that $L$ is regular?

---

My regular expression will be-: $L=a(a+b)^{+}a+b(a+b)^{+}b+a(a+b)^{+}b+b(a+b)^{+}a$ Am i right?

# Answer
When is a string of the form $a^\*ba^\*b$ in the language $L$, i.e., of the form $wxw$, for nonempty $w,x$?

Or, to be more explicit, what is the language $L \cap a^\*ba^\*b$?
> 2 votes

# Answer
*The answer previously provided here is wrong. Counter example is $ab a ab$, see comment section below*

> Your conclusions are correct, but your regular expression also accepts the strings $aab$ or $abb$, which are not in $L$.
>
> $a(a + b)^+a + b(a + b)^+b$ accepts a string $s$ if and only if $s \in L$, so $L$ is regular.
> 0 votes

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


# Question
Title: Assembly language translation to machine code (process in "RAM")
How does a assembler (at very basic level) work in translation of Assembly language to machine code ? Just want to know that what is happening in RAM ?

\[What my understanding is that when when I type MOV A, B : in RAM :'M' \>\> some bytes (ASCII CODE) in memory (RAM)in form of 0v and 5v (voltage may be different but you know what I mean) 'O' will be saved with same method & so V , A , "," , B .Now the programming software also have the part in RAM which we call "library" saved in 0s & 1s in the form of 0v /5v.So my question is that does "translation" mean that typed the 0s,1s of MOV A,B will be compared to saved 0s and 1s (library's)by logic ckt & then depending on the matching or mismatching of those 0s,1s will result in another 0s,1s (opcodes bits/bytes ,will be stored & later executed in RAM)?Am I right or is this a wrong way of thinking? \]

# Answer
> 2 votes
In modern computers, *assemblers* do not deal directly with in-RAM machine code anymore. Their job is to translate the textual representation of the assembly language to opcode combinations, in a form that is not completely finished because exact addresses are not decided yet.

Both the tetx and its translation are stored in disk files, they only reside in RAM while translation takes place.

A next step is performed by another utility, the *linker*, which performs address assignments and creates another file, called the executable, and will also reside on disk.

When you want execution to take place, a third program called the *loader* will read the opcodes from disk and write them in RAM memory where it belongs. Then the loader will tell the operating system that a new task is ready for execution and eventually control will be passed to the program you have written and which is now loaded in RAM.

(This explanation is really simplified as there are many intervening steps and other goodies to consider.)

---
Tags: programming-languages, binary
---


# Question
Title: What is more effective, a do while or a while?
I mean, with the same code, if I modify a do while into a while in this way:

do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change in the code?

B = condition

S; = instructions

# Answer
*While* and *do while* differ only in the first execution when condition is false. If you ignore this difference it boils down to the place of condition check, in *while* the condition is checked and if it is true the statements are executed. In the *do while* the condition check is executed after the block execution.

The code is exactly the same, with one line reordered.

If you want to do micro-optimisations please check whether these are worthy of your time. Compiler does really great job nowadays, unless it doesn't then change the compiler.

So under the hood they are equivalent.
> 2 votes

---
Tags: efficiency, loops
---


# Question
Title: What does the $^*$ operator do in the theory of parsing?
I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^\*$). The book defines it recursively as follows:

\begin{align\*} 1)\ L^0&=\\{e\\}\\ 2)\ L^n&=LL^{n-1}\quad \text{for } n\ge1\\ 3)\ L^\*&=\bigcup\_{n\ge0}{L^n} \end{align\*}

What sort of set does this operation define? It seemed to me that it defines something like "the set of all possible concatenations of strings of language $L$". There wasn't an actual example in the chapter, I can't figure it out.

# Answer
> 1 votes
It does exactly what you describe: $L^\*$ contains all possible *finite* concatenations of words in L, including the empty word. This operator is known as the Kleene star, it is fundamental in the theory of regular languages and more generally of grammars.

# Answer
> 0 votes
Yes, you're right. As an example, suppose your alphabet was $\sum = \\{a,b\\}$ and and you wanted to represent the set of all strings over $\sum$ where every $a$ is immediately followed by a $b$. Then $\\{ab , b\\}^\*$ would give you such a set of strings since it contains exactly all the possible finite concatenations of $ab$ and $b$. If you're familiar with regex expressions, then it is very similiar to the $\*$ operator used in that context.

---
Tags: regular-languages, compilers, parsers
---


# Question
Title: Proving by induction that a function gets called n-1 times
This is the pseudo-code from the problem:

```
procedure Foo(A,f,L)

   Precondition: A[f..L] is an array of integers, f,L, are
                 two naturals >=1 with f<=L.

   if (f=L) then
     return A[f]
   else
     m <-- [(f+L)/2]
     return min(Foo(A,f,m), Foo(A, m+1,L))
   endif

```

The Question:

Using induction, argue that Foo invokes `min` at most $n-1$ times.

I am a little lost on how to continue my proof for part (iii). I have the claim written out as well as the base case. Which I believe it to be $n\geq2$. But how do I do it for $k + 1$ terms? Since this is a proof by induction.

Thanks

# Answer
> 1 votes
Here, I'm going to let $n = L-f$ and let $M(f,L)$ be the number of times min is invoked when calling $Foo(A,f,l)$. Notice when $n=0$, then $L=f$ and clearly Foo invokes the function min $0$ times so the condition is satisfied.

Now suppose that the assertion is satisfied for $n \leq k$. We want to show it holds true for $n=k+1$, i.e., suppose that $L-f = k+1$. Since $Foo(A,f,L)$ has to invoke min once and then invoke it as many times as its invoked in the recursive calls, we get that,

$$M(f,L) = 1 + M(f,m)+M(m+1,L).$$

Now notice that for $M(f,m)$ and $M(m+1,L)$, the quantity $m-f$ and $L-(m+1)$ are both less than $L-f = k+1$ (since $m$ is essentially the midpoint of $L$ and $f$). So by the inductive hypothesis $Foo(A,f,m)$ invokes min at most $m-f-1$ times and $Foo(A,m+1,L)$ invokes min at most $L-(m+1)-1$ times. Plugging these into our equation yields, we get,

$$M(f,L) = 1 + M(f,m)+M(m+1,L) \leq 1 + (m-f-1) + (L-(m+1)-1) = L-f-1 = n-1,$$

as desired.

---
Tags: algorithms, correctness-proof
---


# Question
Title: How is the data stored in AVL tree in a memory?
I have been struggling to visualize how is the AVL tree is stored in memory? Does it store data in array or list, If so how is it connected with its child and parents.

# Answer
If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.

In most cases, however, the individual nodes of the tree are stored in one sequential chunk of memory that's allocated by whatever method your system/language provides (most common being `malloc` and/or `new`), each containing the key and the two pointers to child nodes, either of which can be a special value `NULL`, if a child is not present.

The individual nodes are usually scattered around the memory, with no clear relation between how/where they are located. We leave this for the memory allocator of the environment to handle. When we allocate a new node, we place its address (a pointer to it) in an existing node (or, as a special case, in the root pointer), so we can navigate to it.

Think of this as a linked list, where each item can have not only one, but two successors.
> 2 votes

---
Tags: data-structures, search-trees, balanced-search-trees, storage
---


# Question
Title: How to calculate the total error from an arbitrary hidden layer in a neural network back propogation?
I'm following the tutorial over at https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/ and so far everything makes sense to me. I am now trying to reason about how these formulas extend to any number of hidden layers. Specifically, how to proceed when you have the partial derivative of total error with respect to a weight. In the above post, $\frac{\partial Etotal}{\partial w1}$ is just the sum of the partials for $Eo1$ and $Eo2$ with respect to $w1$. Let's say that there is an extra layer between the $h$ nodes and the $o$ nodes, with nodes $j1$ and $j2$. Is $\frac{\partial Etotal}{\partial w1} = \frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}$ or is it more complicated? Something like: $\frac{\partial Etotal}{\partial w1} = \frac{\partial Eo1}{\partial w1} + \frac{\partial Eo2}{\partial w1} = (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}) + (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1})$

# Answer
> 1 votes
The short answer is yes, $\frac{\partial E\_{total}}{\partial w\_1} = \frac{\partial E\_{j\_1}}{\partial w\_1} + \frac{\partial E\_{j\_2}}{\partial w\_1}$.

The long answer. The key formula is the chain rule, as D.W. mentioned:

$\frac{\partial E\_{total}}{\partial w\_1} = \frac{\partial E\_{total}}{\partial out\_{h\_1}} \cdot \frac{\partial out\_{h\_1}}{\partial net\_{h\_1}} \cdot \frac{\partial net\_{h\_1}}{\partial w\_1}$

What's good about it is that all three components on the left are *local information*. No matter what the next or previous layers are,

$\frac{\partial out\_{h\_1}}{\partial net\_{h\_1}} = out\_{h\_1} (1 - out\_{h\_1})$

$\frac{\partial net\_{h\_1}}{\partial w\_1} = i\_1$

Hence, the calculation is the current node depends only on forward messages from direct neighbors to the left and backward messages from direct neighbors to the right:

$out\_{h\_1}$ and $i\_1$ are known from the forward pass, and $\frac{\partial E\_{total}}{\partial out\_{h\_1}}$ is the total backward message.

In the architecture from the post, the node $h\_1$ has two direct neighbors to the right: $o\_1$ and $o\_2$, and that explains the sum $\frac{\partial E\_{total}}{\partial out\_{h\_1}} = \frac{\partial E\_{o\_1}}{\partial out\_{h\_1}} + \frac{\partial E\_{o\_2}}{\partial out\_{h\_1}}$. In your example, the neighbors are $j\_1$ and $j\_2$, so it will be the sum $\frac{\partial E\_{total}}{\partial out\_{h\_1}} = \frac{\partial E\_{j\_1}}{\partial out\_{h\_1}} + \frac{\partial E\_{j\_2}}{\partial out\_{h\_1}}$. If $h\_1$ has even more connections, all of them will pass the backward message and they will be added up.

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


# Question
Title: Minimum number of moves in this Graph Coloring "Game"
You're given a graph $G = (V, E)$ and a set of colors $C = \\{c\_1, \cdots, c\_v\\}$, and the task is as follows:

* Color the vertices using the colors in $C$.
* Remove any edges that have differing colors for its endpoints (of course, if a vertex eventually has all edges removed, it can be deleted - but it is not necessary).
* Repeat the above two steps until there are no edges left in the graph.

Suppose that $k = |V|$ is the number of vertices, $m = |E|$ is the number of edges, and $v = |C|$ is the number of colors. I am interested in the quantity $p(k, m, v)$, which is the *smallest* number of iterations of the above algorithm given $k, m, v$. Of course, we need $v \ge 2$ (couldn't remove any edges otherwise), and $p(k, m, v) \le m$ because we can color one edge at a time. We can also denote this quantity by $p(G, v)$.

Based on a combinatorial object that is equivalent with respect to this procedure (perfect hash families), when we have the complete graph $K\_k$, one can prove that $p(K\_k, v) = \lceil \log\_v(k) \rceil$. So of course $p(k, m, v) \le \lceil \log\_v(k) \rceil$ if $G$ is a simple graph.

But the more interesting case is when we have $G$ be a hypergraph. Here, we remove hyperedges that are *rainbow* (i.e., every vertex in the hyperedge is a distinct color). Based on PHFs, there are lower and upper bounds for $p(G, v)$ when $G$ is the complete $t$-uniform hypergraph. In general, $p(G, v) \in \Theta(\log k)$ for these graphs, but the hidden constant heavily depends on $v, t$.

Are there references that have looked at a similar problem for hypergraphs?

# Answer
The value of $p(G,v)$ is at most $r$ if you can label the vertices of $G$ with colors from $\[v\]^r$ in such a way that the colors assigned to every pair of adjacent vertices differ on at least one coordinate. Equivalently, $p(G,v) \leq r$ if you can label the vertices of $G$ with colors from $\[v\]^r$ in such a way that every pair of adjacent vertices gets a different color. Stated differently, $p(G,v) \leq r$ iff $\chi(G) \leq v^r$, where $\chi(G)$ is the chromatic number of $G$. This implies the formula $$ p(G,v) = \lceil \log\_v \chi(G) \rceil. $$ A similar relation should hold for the case of hypergraphs if you use the correct definition of chromatic number.
> 2 votes

---
Tags: graphs
---


title: Quick sort analysis confusion

text:
# Question
Title: Quick sort analysis confusion
Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input?

Let say A1 = \[1,2,3,4,5\] , A2 = \[5,2,3,4,1\] A3 = \[5,4,3,2,1\] , Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

but for B1 = \[1,2,3,4,5\] B2 = \[11,12,13,14,15\] will have different runtime i.e. depends on the digits in the input?

# Answer
> 1 votes
> Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

Statements like this do not make any sense. For any given input, *any* algorithm has running time O(1).

Note that Landau notation (here) inherently contains a "for size to infinity" clause. Therefore, it makes only sense for infinite input sets.

Then, yes, the result depends a lot on the input sequences you consider. If you average over *all* inputs, you get $\Theta(n \log n)$. If you average over all *worst-case* inputs, you get $\Theta(n^2)$.

# Answer
> 0 votes
The runtime of the randomized quick sort algorithm does depend on the sequence of the input (if you mean the order of the elements in the array).

Since this algorithm chooses a **random** element as the pivot, the running time for the arrays $A\_1$, $A\_2$, and $A\_3$ may be same or different each time you run this algorithm. But in general, expected (average) running time of the randomized quick sort algorithm is $O(n\log n)$ and its worst-case running time is $O(n^2)$. The purpose of randomization (shuffling for example) is to make the worst-case unlikely.

---
Tags: algorithm-analysis, runtime-analysis, randomized-algorithms, quicksort
---


# Question
Title: Determining Language from Context Free Grammar
I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar:

$S \to 0B \mid 1A$

$A \to 0 \mid 0S \mid 1AA$

$B \to 1 \mid 1S \mid 0BB$

What this says to me is that the first symbol can be either a 0 or 1, and the next could be 0 or 1 or 1 or 0, and you continue down the parse tree from there. How does one determine what the language of the grammar is? I having trouble putting the patterns of symbols into a language definition.

# Answer
Structural induction would prove the following:

* All words generated from $S$ have the same number of 0s and 1s.
* All words generated from $A$ have an excess of one 0.
* All words generated from $B$ have an excess of one 1.

Presumably the reverse is also true, but I'll leave such pondering for you.
> 1 votes

---
Tags: formal-languages, formal-grammars
---


title: Is genetic programming relevant today?

text:
# Question
Title: Is genetic programming relevant today?
My main concern is whether the genetic programming is an active field of research, with some promising applications in practice. It seems like in field of machine learning, the neural networks are the main buzzword, with mentions in mainstream news today, but I have never heard of similar genetic programming "success story".

# Answer
The research is well in progress, though not so much talked about in comparison to machine learning, deep learning in particular.

* Genetic algorithms are applied in particular research areas (examples: "Genetic Programming for Estimation of Heat Flux between the Atmosphere and Sea Ice in Polar Regions" (link), "Genetic Programming with Alternative Search Drivers for Detection of Retinal Blood Vessels" (link), "Optimal placement of water-lubricated rubber bearings for vibration reduction of flexible multistage rotor systems" (link)).
* If you are interested in a research of genetic algorithms themselves, see the papers by Claire Le Goues.
* There is an annual conference dedicated to evolutionary computation.
* Programming frameworks are far from dead as well.

> Is genetic programming relevant today?

Not so long ago, in early 2000-s, people asked the same question about neural networks. Hugo Larochelle mentions how the neural networks papers have been reviewed back then. And we know how it turned out. So don't be so quick in your conclusions, it all can change one day.
> 5 votes

---
Tags: machine-learning, evolutionary-computing
---


# Question
Title: Showing the following sequents are not valid
$\lnot \forall x P(x) \models \forall x \lnot P(x)$
$P(x) : x$ is divisible by 2 or $P(x) : x$ is a dog. or $P(x) can be anything.

I want to show the following sequents are not valid ..Isn't the following sequents equal or the first sequent the whole negation of the statement and the second sequent is the negation of the $P(x)$ .. Can anybody explain this with examples?

# Answer
First, $\phi \models \psi $ means that $\psi$ is a *consequence* of $\phi$. In other words, if $M$ is a structure and if $M \models \phi$ ($M$ models $\phi$) then $M \models \psi$ ($M$ also models $\psi$).

Now, regarding your statement $$\lnot \forall x P(x) \models \forall x \lnot P(x)$$ clearly $\forall x \lnot P(x)$ is not a consequence of $\lnot \forall x P(x)$. To show it consider the set of natural numbers as a structure $M$ and $P(x)$ as the predicate "$x$ *is divisible by* $2$". Then $$\lnot \forall x P(x)$$ means "*Not for all* $x$, $x$ *is divisible by* $2$ which is a true sentence (since in fact odd numbers are not divisible by 2), while $$ \forall x \lnot P(x)$$ means "*For all* $x$, $x$ *is not divisible by* $2$" which is not a true sentence (since in fact even numbers are divisible by $2$).

So, the structure $M$ (the set of natural numbers) is an example showing that $M \models \lnot \forall x P(x)$, but $M \nvDash \forall x \lnot P(x)$ and your statement $$\lnot \forall x P(x) \models \forall x \lnot P(x)$$ is not true.
> 1 votes

---
Tags: first-order-logic, logical-validity
---


# Question
Title: Some questions about the depth hierarchy of threshold circuits
Let me split my query into a few parts which possibly have overlapping answers,

1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT\_3}$) are in $NP/poly$? (I saw this claimed in the conclusion of this recent paper https://arxiv.org/abs/1705.02397 without any proof or reference.)
2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?
3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?
4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT\_3} \subseteq NP/poly$ when we know that $\hat{LT\_3} \subseteq P/poly$? What am I missing?

# Answer
First, let me correct you definition of $\widehat{LT}\\!\\!\_3$: it is the class of depth-3 *polynomial size* threshold circuits with polynomially bounded weights.

Polynomial size threshold circuits can be converted to polynomial size Boolean circuits. To show this, it suffices to show that any single threshold gate can be computed by a polynomial size Boolean circuit. The proof goes along the following lines:

* Every threshold gate is equivalent to a threshold gates whose weights have bit-length $O(m\log m)$, where $m$ is the number of inputs. This can be shown using linear programming (see below).
* Adding $m$ numbers of bit-length $O(m\log m)$ can be accomplished using a Boolean circuit of size polynomial in $m$.

In our case $m$ is at most the number of gates in the original threshold circuit, which is polynomial (in $n$, the number of input bits). Therefore the Boolean circuit equivalent to any single threshold gate has polynomial size.

The foregoing shows that $\widehat{LT}\\!\\!\_3 \subseteq \mathrm{P/poly}$. While it is also true that $\widehat{LT}\\!\\!\_3 \subseteq \mathrm{NP/poly}$, it seems like a typo in the paper.

Finally, let us indicate how to show that every threshold gate on $m$ inputs is equivalent to one in which the weights have bit-length $O(m\log m)$. Consider the following linear program. The variables are $c\_1,\ldots,c\_m,\theta$. For each $x\_1,\ldots,x\_m \in \\{0,1\\}^m$, if the threshold gate outputs 1 on this input, we add the constraint $$ \sum\_{i=1}^m c\_i x\_i \geq \theta + 1, $$ and if it outputs 0 then we add the constraint $$ \sum\_{i=1}^m c\_i x\_i \leq \theta - 1. $$ It is not too hard to check that this LP is feasible, essentially using the parameters of the threshold gate (possibly scaled). On the other hand, LP theory tells us that there exists a basic feasible solution, which is obtained by choosing $m+1$ linearly independent inequalities and treating them as equations. Cramer's rule, which expresses the solution as a ratio of determinants, completes the proof (exercise).
> 1 votes

---
Tags: complexity-theory, complexity-classes, circuits
---


title: Finding Models for a sequent

text:
# Question
Title: Finding Models for a sequent
I am trying to generate models for the following sequent.

$$\exists x \exists y \forall z (z = x \lor z = y)$$

What I have come up with is this.

$$A= \\{0,1\\}$$

So in this model, for all the values of $z$ there exists $x$ such that $z = x$ or there exists $y$ such that $z = y$. Is this model correct? What other models are there that satisfy this?

# Answer
> 1 votes
You should be careful with order of quantifiers. You are given a predicate $$\exists x \exists y \forall z (z = x ∨ z = y)$$ which is read as $$\text{ there is } x \text { such that there is } y \text { for all } z \dots $$ while you read it as $$ \text { for all the values of } z \text{ there exists } x \dots$$ which would correspond to $$\forall z \exists x \dots$$ When you change the order of quantifiers the meaning (and hence the truth value) of the sentence changes. For example consider the set of natural numbers excluding 0. Then $$\forall x \exists y (x \text { divides } y)$$ is a true sentence since for any $x$ take $y=x$. But the sentence $$\exists x \forall y (x \text { divides } y)$$ is false since $x$ does not divide $x+1$.

Now as for your question, yes $A=\\{0, 1\\}$ models this sentence. In fact you could also take a set consisting of a single element, for instance $\\{0\\}$ or $\\{1\\}$ (there is no condition such as $x\neq y$).

---
Tags: first-order-logic, model-checking
---


# Question
Title: Why do the definitions of non-deterministic Turing machines look strange?
I read some definitions of the NDTM in several books. Something makes me confused.

Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply.

So, if $x \in L(M)$, then $M$ can always guess a branch which leads to $q\_{accept}$. And if $x \not\in L(M)$, then $M$ just chooses an arbitrary branch until it enters $q\_{reject}$. It seems that $M$ knows the result after reading $x$ because the rule which tells $M$ how to guess depends on whether $x$ is in $L(M)$.

It looks so strange!

Another definitions say that $M$ executes all branches in parallel.

That looks better. And it shows that if $x \in L(M)$, then $M$ halts when it enters $q\_{accept}$ at the first time. However, the running time of NDTM is defined as the maximum number of steps that $M$ uses on any branch of its computation on any input. I am not sure if the definitions of the running time of NDTM are equivalent.

# Answer
> 5 votes
Do not think of a non-deterministic machine as a mechanism that actually operates in some fashion. Instead, think of it as a way of making a tree of possibilities: whenever the machine "guesses" or "chooses" a transition, think of that as a node which branches into several further computation trees, one for each transition.

The tree will have many possible paths of execution. We can ask questions like:

1. Is there at least one path that leads to acceptin the input?
2. Do all paths lead to accepting the input?
3. Do more than half the paths lead to accepting the input?

And so on. The usual notion of a non-deterministic machine uses the first point above, i.e., we usually study whether there is *any* choice of transitions that leads to accepting the input. This is different from trying to devise an actual machine that will make such choices. We just want to know whether the choices *exist*.

Once you get used to the trees, you can start thinking of such a tree as describing a machine which actually runs. Of course, you need to explain to yourself how the machine chooses a particular path in the tree. You can think of it "guessing the future" or "being lucky" or "running all possibilities in parallel universes and then picking the one that works". It doesn't really matter what story you make up, so long as it fits your intuition and the definition. We're not actually going to build a non-determinstic machine (except if someone can master parallel universes or make a machine that can predict the future).

# Answer
> 4 votes
Basically, a NDTM on input $x$ may have more than one computation branches. If at least one of these branches accepts the input then we say the NDTM accepts the input $x$, otherwise it rejects.

You can consider a NDTM as a finite number computation branches such that branch on input$x$ may halt with accept or reject, or run forever. If at least one branch halts with accept then the NDTM accepts that input no matter other branches halts or run forever. If no branch accepts (halts with in ACCEPT state) then we say the NDTM does not accept the input. And if every branch halts and rejects then we say that NDTM rejects the input.

Do not try look for a real life model of a NDTM. It is just a conceptual computation model which allows to define a complexity class known as $\mathrm{\mathbf{NP}}$ class.

This post has more.

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Optimal solution algorithm for K-center problems
I'm wondering if there is an algorithm that calculates the optimal solution of a typical k-center problem (more than one dimension). I've tried, but without success, to find this algorithm. Does such an algorithm exist?

# Answer
An optimal solution for the k-center problem can be found by an exhaustive search over the solution space, and by picking the best solution. The problem is NP-Hard for more than 2 dimensions, and moreover any $\delta$-approximation for $\delta \< 2$ is NP-hard.
> 3 votes

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


# Question
Title: Writing the coherence conditions for a monad in a functional laguage
i recently asked a related question about the relationship between monads in category theory and Haskell. The answerer showed me the following classes and instances:

```
class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f m = m >>== (ret . f)
  eta     = ret
  mu m    = m >>== id

instance MyMonad t => KleisliTriple t where
   ret      = eta
   m >>== f = mu (fun f m)

```

And told me I should show that the rules for each class are equivalent. I've finally gotten around to this exercise but I've already run into some confusion.

I know that the "laws" for a Kleisli Triple are as follows:

```
return x >>= f  = f x
m >>= return    = m
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

```

And I know that the coherence conditions for a monad can be written $$\mu \circ \eta T = \mu \circ T \eta = id\_C$$ $$\mu \circ \mu T = \mu \circ T \mu$$ Where $T$ is the endofunctor, `fun` in the Haskell class.

I know $(\eta T)\_x = \eta\_{T\\, x}$ and $(T\eta)\_x=T(\eta\_x)$, so I think the rules for `MyMonad` could be written as follows:

```
mu . eta . (fun f) = f
mu . (fun eta) = id
mu . mu . (fun id) = mu . (fun mu)

```

Writing any of these expressions as a function with the desired type signatures loads in GHCI, but I don't think I'm right.

It's mainly associativity that I'm not confident about. Unwrapping associativity for the Kleisli triple yields

```
mu (fun g (mu (fun f m))) = mu (fun (\x -> mu (fun g (f x))) m)

```

Which seems over-complicated, but unlike my attempt to express the category-theoretic constraints, this equation universally quantifies over the functions

```
f :: a -> m b
g :: b -> m c`

```

How close am I to coming to the correct conclusion? Hints would be appreciated.

# Answer
> 6 votes
First off, you've confused $\nu$ and $\eta$ in your class. I'm going to go with $\eta$.

The coherency law:

$$\mu \circ T \eta = \mu \circ \eta T = 1\_T$$

translates to:

```
mu . fun eta = mu . eta = id

```

And the other coherency law:

$$\mu \circ T\mu = \mu \circ \mu T$$

translates to:

```
mu . fmap mu = mu . mu

```

Intuitively, the reason why the $T$ "disappears" when translating $\mu T$ to `mu` is the same reason why it "disappears" when translating $1\_T$ into `id`: in Haskell, types are passed implicitly. If you translate this into System $F\_\omega$ (or GHC Core!) the types are passed explicitly and the correspondence is more obvious. I'm going to leave you that one as an exercise.

One more thing. Don't forget the other conditions on `mu` and `eta`: they have to be natural transformations! The coherency conditions in category theory are:

$$\forall f : X \rightarrow Y, \eta\_Y \circ f = T(f) \circ \eta\_X$$ $$\forall f : X \rightarrow Y, \nu\_Y \circ T^2(f) = T(f) \circ \nu\_X$$

In Haskell:

```
∀ f, eta . f = fun f . eta
∀ f, nu . fun (fun f) = fun f . nu

```

In category theory, you might need to prove these, but in Haskell you don't because they are the free theorems for those functions. This is a very nice property of Haskell: Ignoring bottom values and general recursion, any function with the type of a natural transformation must be a natural transformation.

(This is also a good piece of intuition as to what is so "natural" about natural transformations. It means that the "forall" in a polymorphic type is a real "forall"; it's true for *any* type with no exceptions.)

---
Tags: functional-programming, category-theory
---


# Question
Title: Viable use of genetic algorithms to train neural nets in a poker bot?
I am designing a bot to play Texas Hold'Em Poker on tables of up to ten players, and the design includes a few feed forward neural networks (FFNN). These neural nets each have 8 to 12 inputs, 2 to 6 outputs, and 1 or 2 hidden layers, so there are a few hundred weights that I have to optimize. My main issue with training through back propagation is getting enough training data. I play poker in my spare time, but not enough to gather data on my own. I have looked into purchasing a few million hands off of a poker site, but I don't think my wallet will be very happy with me if I do... So, I have decided on approaching this by designing a genetic algorithm. I have seen examples of FFNNs being trained to play games like Super Mario and Tetris using genetic algorithms, but never for a game like poker, so I want to know if this is a viable approach to training my bot.

First, let me give a little background information (this may be confusing if you are unfamiliar with poker). I have a system in place that allows the bot to put its opponents on a specific range of hands so that it can make intelligent decisions accordingly, but it relies entirely on accurate output from three different neural networks:

NN\_1) This determines how likely it is that an opponent is a) playing the actual value of his hand, b) bluffing, or c) playing a hand with the potential to become stronger later on.

NN\_2) This assumes the opponent is playing the actual value of his hand and outputs the likely strength. It represents option (a) from the first neural net.

NN\_3) This does the same thing as NN\_2 but instead assumes the opponent is bluffing, representing option (b).

Then I have an algorithm for option (c) that does not use a FFNN. The outputs for (a), (b), and (c) are then combined based on the output from NN\_1 to update my opponent's range.
Whenever the bot is faced with a decision (i.e. should it fold, call, or raise?), it calculates which is most profitable based on its opponents' hand ranges and how they are likely to respond to different bet sizes. This is where the fourth and final neural net comes in. It takes inputs based on properties unique to each player and the state of the table, and it outputs the likelihood of the opponent folding, calling, or raising.
The bot will also have a value for aggression (how likely it is to raise instead of call) and its opening range (which hands to play pre-flop). These four neural networks and two values will define each generation of bots in my genetic algorithm.

Here is my plan for training:
I will be simulating multiple large tournaments with 10n initial bots each with random values for everything. For the first few dozen tournaments, they will all be placed on tables of 10. They will play until either one bot is left or they play, say, 1,000 hands. If they reach that hand limit, the remaining bots will instantly go all-in every hand until one is left. After each table has completed, the most accurate FFNNs will be placed in the winning bot that will move on to the next round (even if the bot containing the best FFNN was not the winner). The winning bot will retain its aggression and opening range values. The tournament ends when only 100 bots remain, and random variations on those bots will generate the players for the next tournament. I'm assuming the first few tournaments will be complete chaos, so I don't want to narrow down my options too much early on.

If by some miracle, the bots actually develop a profitable, or at least somewhat coherent, strategy (I will check for this periodically), I will begin decreasing the amount of variation between bots. Anyone who plays poker could tell you that there are different types of players each with different strategies. I want to make sure that I am allowing enough room for different strategies to develop throughout this process. Then I may develop some sort of "super bot" that can switch between those different strategies if one is failing.

So, are there any glaring issue with this approach? If so, how would you recommend fixing them? Do you have any advice for speeding up this process or increasing my chances of success? I just want to make sure I'm not about to waste hundreds of hours on something doomed to fail. Also, if this site is not the correct place to be asking this question, please refer me to another website before flagging this. I would really appreciate it. Thanks all!

# Answer
> 1 votes
If you don't have enough training data, I expect that using genetic algorithms to select the neural network weights isn't going to work any better than backpropagation. If you don't have enough training data, it probably doesn't matter how you train the network.

If you do have enough training data, I would expect backpropagation to work better. There's an art to training neural networks, and there is a lot written on how to apply backpropagation and gradient descent to train neural networks effectively. If you wanted to try using genetic programming to find the weights, you'd be on your own and wouldn't be able to be guided by existing practice and lessons learned in the community.

That said, with only a few hundred weights, I would predict that your neural network won't play very good poker in any case, no matter how much training data you have.

You could also look at reinforcement learning, and methods to have the network learn by playing against itself.

---
Tags: artificial-intelligence, neural-networks, simulation, genetic-algorithms
---


title: What is the Big O for n^2 + n * T(n-1)

text:
# Question
Title: What is the Big O for n^2 + n * T(n-1)
I am working on the following algorithm time equation:

```
T(n) = n^2 + n * T(n-1)

```

What would be its Big O?

# Answer
By expanding,

$$T(n) = n^2+n\cdot T(n-1)$$ $$ = n^2+n\[(n-1)^2+(n-1) \cdot T(n-2)\]$$ $$= n^2+n(n-1)^2 + n(n-1)T(n-2)$$ $$= n^2+n(n-1)^2 + n(n-1)\[(n-2)^2+(n-2) \cdot T(n-3)\]$$ $$= n^2+n(n-1)^2 + n(n-1)(n-2)^2+n(n-1)(n-2) \cdot T(n-3)$$ $$ = n \cdot \frac{n!}{(n-1)!} + (n-1) \cdot \frac{n!}{(n-2)!} + (n-2) \cdot \frac{n!}{(n-3)!} + T(n-3) \cdot \frac{n!}{(n-3)!}$$ $$=T(n-3) \cdot \frac{n!}{(n-3)!} + \sum\_{i=1}^3 (n-i+1) \frac{n!}{(n-i)!}$$ $$\dots$$ $$=T(n-k) \cdot \frac{n!}{(n-k)!} + \sum\_{i=1}^k (n-i+1) \frac{n!}{(n-i)!}$$

If you assume that $T(0) = 0$, then when $k = n$, we have $n-k = 0$ and hence,

$$T(0) \cdot \frac{n!}{(n-n)!} + \sum\_{i=1}^n (n-i+1) \frac{n!}{(n-i)!}$$ $$ = \sum\_{i=1}^n (n-i+1) \frac{n!}{(n-i)!}$$ $$ n! \cdot \sum\_{i=1}^n \frac{(n-i+1)}{(n-i)!}$$ $$ \leq n! \cdot \sum\_{i=1}^n n \quad \text{(for sufficiently large n)}$$ $$ = n! \cdot n^2 \in \mathcal{O}(n! \cdot n^2),$$

as desired.

EDIT: There's a lot of steps here, so let me know if there's a particular step that isn't clear and I can try to elaborate.
> 2 votes

# Answer
The upper bound can be expressed as O(n^2 * n!)
> -1 votes

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


# Question
Title: Is there a difference between type safety and type soundness?
I've been trying to tease apart the definitions of type safety and type soundness and I'm having a heck of a time of it. I asked a professor recently and after a bit of thought he said that there really wasn't any difference. However after reading this it seems like:

* **Type Safety** is a property of the language that says that the application of functions (and operators) to data is *meaningful* (i.e. 1 / "Hello" is nonsense and is disallowed)
* **Type Soundness** is a property of a type checking system that guarantees that its static type predictions are accurate at run time.

This is clearly just a single persons notes and I'm wondering if there is some standard within the PL community. I've done some searching and I haven't found a satisfying answer.

# Answer
> 19 votes
Type safety and type soundness are synonyms in most theoretical work. Type soundness is often formulated with respect to an operational semantics as (type) preservation and progress. Preservation states that if an expression has some type, then after a step of evaluation (via the operational semantics), the resulting expression can be given the same type. Progress states that if an expression is not a value, i.e. it is not fully evaluated, and it is well-typed, then it can be further evaluated.

"Type safety" and "soundness", but particularly "type safety", are also widely used by the (non-theoretical) programming community often in vague, ambiguous, or outright incorrect ways. For example, an API that uses enumeration types instead of allowing arbitrary strings when only a subset are meaningful, say, might be referred to as being "more type safe", but this statement doesn't make sense using the theoretical definition of "type safe" which is a binary property of the language as a whole.

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


# Question
Title: Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma
**Question:**

L is a language defined as $\ L = \\{1^l | l\in primes\\}$ (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory of closure or the pumping lemma to prove this.

**My try:**

So far I have tried to take a word $\ w | w=1^p$ ($\ p$ being the pumping value), but in this case I don't know how to prove that every decomposition of the form $\ w=xy^i z$ is invalid. When $\ |y|=p$ (and therefore $\ x=z= \epsilon $) the lemma is clearly untrue, because when $\ i = 2$, $\ |w'| = 2p$ which is not prime. But in the case that $\ y\<p$, and $\ x \neq \epsilon$ and/or $\ z \neq \epsilon$, I don't see a way to prove that $\ w' = x y² z$ is not prime.

# Answer
> 6 votes
Your attempt doesn't work, since you need the word you pick to belong to the language. Therefore I suggest picking $w = 1^p$, where $p$ is a *prime* which is larger than the pumping constant. The pumping lemma shows that there is a decomposition $w=xyz$, where $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$. Let $x=1^r$, $y=1^s$, and $z=1^t$, so that $r+s+t=p$. Then $xy^iz = 1^r 1^{si} 1^t = 1^{r+si+t} = 1^{p+(i-1)s}$. Thus, $p+(i-1)s$ has to be prime for all $i \geq 0$. However, when $i = p+1$, we get $p+(i-1)s = p+ps = p(1+s)$, which isn't prime.

---
Tags: formal-languages, regular-languages, logic, proof-techniques, pumping-lemma
---


# Question
Title: Does the subset sum problem remain $NP$ complete when we increase word size and restrict number of words?
Is the problem

> 'Given $m=\big\lceil{n^b}\big\rceil$ with $b\in(0,1)$ integers $a\_1,\cdots,a\_m$ each with $\lceil\log\_2 |a\_i|\rceil=\big\lceil n^a\big\rceil$ with $a\in\[1,\infty)$ is there a subset that sums to zero?'

$NP$ complete?

The reason I ask is this problem can be solved in $2^{O(n^b)}=2^{o(n)}$ time.

# Answer
Your problem is not really well-defined, since it's not clear what is the parameter $n$. That said, under any reasonable interpretation, your problem is still NP-complete, as can be shown by padding. Given an instance of subset sum, we can create an instance of your restricted subset sum by adding a lot of zeroes to the set.

Subset sum is solvable in polynomial time if the weights are polynomially bounded. More generally, if there are $m$ integers and each one is bounded in magnitude by $B$, then subset sum can be solved in $O(mB)$. In your case the weights are not polynomially bounded.
> 1 votes

---
Tags: np-complete, subset-sum
---


# Question
Title: Minimum number of edges to add such that there are no bridges on a tree
Any edge of a tree is a bridge. What is the minimum number of edges that I will need to add so that there are no more bridges in a tree? I have seen the solution from the internet the answer is $\frac{|V|}{2}$, where $|V|$ is the number of vertices in the tree. How can I prove it?

# Answer
> 3 votes
Let me describe the following algorithm. The basic idea is to add edges such that for any pair of vertices $v\_i$ and $v\_j$ there is at least two different simple paths between $v\_i$ and $v\_j$.

1. Initially all edges are unmarked
2. Select a simple path $v\_i\dots v\_j$ containing at least **two unmarked edges** such as $(v\_i,v\_j) \notin E$ (vertices $v\_i$ and $v\_j$ are not connected). If there is no path containing two unmarked edges, then select a path containing one unmarked edge (this means we are done)
3. Connect $v\_i$ and $v\_j$ (thereby creating a cycle).
4. Mark all edges of the (newly created) cycle $v\_i\dots v\_j$
5. If there is unmarked edge then go to step 2
6. Halt

**Claim 1:** The algorithm adds at most $\frac{|V|}{2}$ edges.
**Proof:** At step 2 we select a path whose length is at least $2$ (i.e. has at least two edges) containing at least two unmarked edges. Such path exists as long as we have two unmarked edges since there is always a simple path between any two vertices $v\_i$ and $v\_j$ in a connected tree. So, at each step 2 we decrease the number of unmarked edges by $2$. Since the tree initially has $|V|-1$ unmarked edges, the algorithm adds at most $\big\lceil{\frac{|V|-1}{2}}\big\rceil$ edges. But $\big\lceil{\frac{|V|-1}{2}}\big\rceil \leq \big\lfloor\frac{|V|}{2}\big\rfloor \leq \frac{|V|}{2}$.

**Claim 2:** The resulting graph created by the algorithm has no bridges.
**Proof:** Consider a partition $(V',V- V')$. Let $v\_i \in V'$ and $v\_j \in V-V'$ such that $(v\_i, v\_j)$ is an edge of the initial tree. Such edge obviously exists since the tree is connected. At some point the algorithm selects a path containing the edge $(v\_i, v\_j)$ and creates a simple cycle which includes the edge $(v\_i, v\_j)$. So, there are two different paths between vertices $v\_i$ and $v\_j$, and hence there are at least two paths (or edges) connecting the partitions $V'$ and $V-V'$.

---

This algorithm does not compute the optimal number of edges for all possible input instances. For example for a tree which is a path it is enough to add a single edge connecting two end points to transform the tree into a bridgeless graph. My goal is to establish the least upper bound for the number of edges required to add to a tree to transform it into a bridgless graph. For example a star-like tree with even number of vertices is a worst case in which case we need exactly $\frac{|V|}{2}$ edges.

---
Tags: graphs, trees
---


title: Need help for maximizing solution

text:
# Question
Title: Need help for maximizing solution
Suppose there exists a list of unsorted int numbers \[91,89,90,90,90,89,91\].
I need to maximize the profit by selecting an element, in as many steps as needed, which satisfies the condition that, when element(i) is chosen, the profit would be value of element(i) multiplied by its frequency/occurrence in list, an extra condition is that element(i), element(i)-1 and element(i)+1 should be removed as well.
So for the given array \[91,89,90,90,90,89,91\], if I choose 90 and remove it, my profit will be 90\*3=270 and my array reduces to \[\], because I remove (90-1) and (90+1) in the same step.
However, if I had chosen, 89 then profit would be 89\*2 and upon removing 89 and 89+1(There is no element corresponding to (89-1)), I am left with \[91,91\]. In the next step, I remove 91, this results in a total profit of 89\*2+91\*2. The profit is greater than the one obtained after selecting 90.
Another example is list \[3,4,2\], suppose I select 3, this means profit is 3\*1 and I remove 3, 2 and 4 which results in empty list and profit is 3. Now, I choose 2, this results in removal of 2 and 3, profit will be 2\*1. List will be \[4\]. Next step profit will be 4\*1, so total profit will be 2+4=6.
I tried to select max element in array and remove it, but it will not work for list \[1,1,1,1,1,1,1,1,1,2\]. Here, 1 needs to be selected, instead of 2. Because selecting 2, would result in a profit of 1 versus selecting 1 which would give 1\*9.
What approach would be ideal to solve this? Please provide your opinions. Thank you

# Answer
> 2 votes
This is a special case of maximum weighted independent set on an interval graph. Another way to phrase your problem is as follows: choose a subset of your neighbors of maximal sum in which no two elements have difference exactly 1.

One simple way to solve your problem is using dynamic programming. First sort the list, and remove duplicates (but remember how many of each number appear in the original list). Now use dynamic programming to calculate the optimal solution for every prefix of the sorted list.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Is $2^n$ steps enough to tell if DTM will run forever?
In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time.

My question is: how is it that $2^{|f(x)|}$ steps is enough to tell if machine $M$ will run forever or not?

# Answer
> 2 votes
More precisely, if a deterministic Turing machine has an alphabet $\Sigma$, and a set of states $|Q|$ and consumes at most $f(|x|)$ space then the maximum number of configurations the machine can have is $$|Q|\times f(|x|) \times|\Sigma|^{f(|x|)}$$ This is because the maximum length of the tape portion (cells in fact used by the machine) is $f(|x|)$, the head of Turing machine at any time can be located on one of the $f(|x|)$ cells, the machine may be in $|Q|$ different states, and this portion of the tape can be filled in $|\Sigma|^{f(|x|)}$ different ways (using alphabet symbols).

If $q=|Q|$ and $|\Sigma| = 2$ (binary alphabet) then we have $$qf(|x|)2^{f(|x|)}$$ different configurations.

Each step of a Turing machine may change machine's state, tape content, or the position of the head. So after $qf(|x|)2^{f(|x|)}$ steps if the machine hasn't yet halted it must repeat the configuration: $\langle$ state, tape content, head position $\rangle$ meaning the machine will loop forever. So I would say it needs $O(f(|x|)2^{f(|x|)})$ steps rather than $O(2^{f(|x|)})$.

# Answer
> 1 votes
Your goal here is to show that $L$ (as defined in your wiki link) is decidable using $O(f(x))$ space.

If we were talking about the time hierarchy theorem (with an analogous $L$ having a time requirement rather than a space one), then it is clear how to decide $L$, simply simulate the given machine $M$ on its encoding for $f\big(|\langle M\rangle|\big)$ steps and see whether it rejects in this time. Now however, you want to do the same thing, but you cant use an argument like "simulate $M$ with $f\big(|\langle M\rangle|\big)$ space and see if it rejects", when do you stop?

The key point here is that a Turing machine with a binary alphabet who uses $O(f(n))$ space, either halts on a length $n$ input in $O\big(2^{f(n)}\big)$ time or doesn't halt at all. The reason being that the number of possible configurations of a Turing machine limited to $O(f(n))$ cells is $O\big(2^{f(n)}\big)$, assuming we are dealing with a binary alphabet (an exact upper bound depends on the number of states). Thus, if your machine doesn't halt in $O\big(2^{f(n)}\big)$ time on a length $n$ input, you can conclude that it has either gone into an infinite loop (a configuration was repeated), or will eventually use more than $O(f(n))$ space. When actually writing up the machine deciding $L$, you should obviously use exact bounds to avoid the asymptotic notation used here, but for the sake of explanation it doesn't really matter.

---
Tags: complexity-theory, proof-techniques, space-complexity
---


# Question
Title: Problem about getting a value of the hashed password
Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing.

admin 827ccb0eea8a

user c3981fa8d26e

operator 5f4dcc3b5aa7

guest 084e0343a048

The password of admin is 12345. What value of the hashed password will be added to the database after the creation of the username operator with the password qwerty123?

How can I solve this problem? Any tips?

# Answer
The problem asks to be creative about breaking hash attempt, well it is a big stretch even for simplistic example, but let's try.

1. You are given a password `12345` from user `admin` with `827ccb0eea8a` hash, that is first 6-bytes of the hash.
2. A standard hashing function has been used - it means MD5. Why?
    1. The construction of the task asks for preimage attack, it must be homemade breakable and possibly already hashed and shown online, otherwise it would not be possible to *crack* without substantial resources.
    2. It cannot be salted, because the salt was not given in the task, but using salt is a wise thing to do - it prevents the rainbow tables attacks and in the case like here, you have a collection of hashes would be harder to recover in batches.
    3. The MD5 is built-in into PHP and easily accessible in the most programming languages (MD5 implementations)
3. Try them until the match is found and then take the steps to hash your password.

Make the test of standard functions (like MD5, SHA256) of any combination of `admin` and `12345`, it may be concatenated or xored, in fact it is not. First try out of lazy guess,
`MD5(12345) =`$\color{maroon}{\text{827ccb0eea8a}}\color{gray}{\text{706c4c34a16891f84e7b}}$
It tells that no salt or username was used, just plain password hashed with deprecated function. The other hashes are irrelevant at this point, but seeing the pattern, find simple MD5 of potential passwords until the first 6 bytes are like in the list.

After the scheme is known, the task is to produce the output from `qwerty123`, so `MD5(qwerty123) =`$\color{maroon}{\text{3fc0a7acf087}}\color{gray}{\text{f549ac2b266baf94b8b1}}$
> 1 votes

---
Tags: cryptography, hash
---


# Question
Title: Linear programming restricted to rational coefficients
I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function and conditions to be rational numbers. I guess that this restriction is because of time analysis consideration in terms of input length. Am I correct? Are there other reasons?

**EDIT:** And do we know that if there is a solution to the LP, then there is a rational solution to it?

**EDIT 2:** If the answer to the previous question is yes, is there a guarantee for the length of resulting rational numbers to be polynomially bounded as a function of input size?

# Answer
In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the coefficients, noting that arbitrary real coefficients cannot be encoded in a finite manner. The simplest and most canonical possibility is to ask for all coefficients to be *integers* or, equivalently, *rational*. In practice this encoding is usually good enough, so there is no reason to look any further. In principle, however, it is perfectly possible to consider more complicated coefficients. Indeed, any field which supports efficient linear algebra would do.

A feasible linear program always has a *basic feasible solution*, which is obtained by taking $n$ linearly independent inequalities (where $n$ is the number of variables), and replacing them with equations. The solution of this linear system will always be rational, and furthermore will be polynomially bounded.

Later on you might learn about semidefinite programs (SDPs). In the case of SDPs, we are no longer guaranteed that there exist an optimal solution over the rationals, but there is always an algebraic solution with bounded algebraic degree over the rationals. This fine point has recently been a cause for worry, see Ryan O'Donnell's SOS is not obviously automatizable, even approximately.
> 4 votes

---
Tags: polynomial-time, linear-programming
---


title: T(n) = 2T (sqrt(n))+ log n Recurrence

text:
# Question
Title: T(n) = 2T (sqrt(n))+ log n Recurrence
I am aware that the question is asked before but i there is still a confusing part for me.

In book the solution is like that:

1. $T(n) = 2T(\sqrt{n}) + \log(n)$
2. $m = \log n$ yields
3. $T(2^m) = 2T(2^{m/2}) + m$
4. Then $S(m) = T(2^m)$ produces the recurrence:
5. $S(m) = 2S(m/2) + m$
6. So $T(n) = T(2^m) = S(m) = O(m\log m) = O(\log n (\log {\log n}))$

But i can't understand in part $5$, how $2T(2^{m/2})$ is converted to $2S(2m/2)$ ? If $S(m)$ is $T(2^m)$, then $S(m/2)$ must be $T(2^{m-1})$? Can you verify me that why the book's solution is correct, and i am wrong?

# Answer
> 4 votes
We define $S(m)$ to be $T(2^m)$, *for every possible value of $m$*. Changing the name of the variable, $S(M) = T(2^M)$ for every value of $M$. Substituting $M := m/2$, we get $S(m/2) = T(2^{m/2})$.

As an example, suppose that $T$ is the identity function: $T(n) = n$. We define $S(m) = T(2^m) = 2^m$. Then $S(m/2) = 2^{m/2}$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Higher order rewriting theory and critical pairs with the beta rule
In a higher-order pattern rewrite system, one specifies rewrites on beta normal forms of terms. Is it possible to have a rewrite like:

$\gamma := \lambda x . F(m) \to F(\lambda x . m)$

for some function symbol $F$ and $m$ in $\beta$-normal form? If so, then there is a "critical pair" between $\gamma$ and $\beta$

$F(m) \[t/x\] \leftarrow (\lambda x . F(m)) t \rightarrow (F(\lambda x .m )) t $

On the other hand, is there any reason to require $\gamma$ go the other direction?:

$F(\lambda x . m) \to \lambda x . F(m)$

This would avoid critical pairs with $\beta$, but may in practice be less natural.

If the former is possible, can one still conclude confluence if all critical pairs are development closed?

# Answer
> 3 votes
The theory of higher-order critical pairs can indeed handle this example, as outlined in the following article:

Higher-Order Rewrite Systems and their Confluence, Richard Mayr & Tobias Nipkow

There are several different notions of higher-order rewrite systems, and several of them are able to handle your example, including those of the paper.

The critical pair lemma is still true: if every critical pair is development closed, **and the system is terminating**, then one can conclude that it is confluent. The second condition is necessary though, in particular, $\beta$-reduction on untyped terms can muck things up.

This means that completion is still a meaningful operation in this setting.

At any rate, your second rule seems a bit more natural in a termination context, where $F$ is "pushed towards the leaves", but obviously it depends on the meaning of the symbol.

---
Tags: lambda-calculus, term-rewriting, higher-order-logic
---


title: Working of NPDA

text:
# Question
Title: Working of NPDA
I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example of regular language a\*. Here if we use stack then we can't decide when to pop the symbols from stack. If we pop all the symbols(prefix belonging to language) then stack will become empty and we can't process the input further(left over input). So we can't accept a\* using dpda by stack.

I read another statement that NPDA using stack can accept all languages which NPDA using final state will accept. Here we can have many copies of machine running simultaneously and we can non deterministically check if the input is accepted or not. But what if prefix like aa of input aaaaa is accepted by one of the machine ? Will all the machines stop and say yes (that is we can't proceed with the input further) or will some of the machines still continue with the remaining input even if one of them halts?

# Answer
A nondeterministic PDA for any triple $\langle q,a,A\rangle$ may have more than one moves/transitions and so the NPDA may have different computation paths/branches depending on what choice the NPDA makes (see this definition for details). So, for any input $x$ if **at least one** of these sequence of choices leads to an accepting configuration then we say the NDPA accepts $x$. In this case whether or not other possible computation branches lead to an accepting configuration does not matter. At least one accepting path is enough to accept the input $x$.

Now, regarding the question in your comment:

> Now what if that one branch is the one which accepts the prefix of the language ? What happens to other branches?

You presumably mean "the prefix of a string", in particular, say $x=aaaaa$ and its prefix $y=aa$. For a NPDA $x$ and $y$ are two different inputs, the NPDA may accept or reject both strings or accept only one of them. This absolutely has nothing to do with the prefix property of a language.

---

Example: a PDA accepting the set of odd length $a$s and and empty string. The basic idea is to keep track of how many $a$s are read, even or odd number of $a$s, using the stack symbols.

$\delta(q,a, Z\_0) = (q,Z\_{odd})$
$\delta(q,a, Z\_{odd}) = (q,Z\_{even})$
$\delta(q,a, Z\_{even}) = (q,Z\_{odd})$
$\delta(q,\epsilon, Z\_{odd}) = (q\_1,\epsilon)$
$\delta(q\_1,\epsilon, Z\_0) = (q\_1,\epsilon)$
$\delta(q\_1,\epsilon, Z\_{even}) = (q\_1,\epsilon)$
$\delta(q\_1,\epsilon, Z\_{odd}) = (q\_1,\epsilon)$

This PDA is not deterministic due to the following two transitions:

$\delta(q,a, Z\_{odd}) = (q,Z\_{even})$
$\delta(q,\epsilon, Z\_{odd}) = (q\_1,\epsilon)$

In other words it has two choices when it is in the state $q$ and the topmost stack symbol is $Z\_{odd}$.

Now suppose this PDA reads $aaaaa$. After reading the third $a$ it may enter the state $\delta(q,\epsilon, Z\_{odd}) = (q\_1,\epsilon)$ which will empty the stack but the rest of the input are not read, and so this branch does not accept the input. However, the PDA has another choice, namely $\delta(q,a, Z\_{odd}) = (q,Z\_{even})$ which leads to accepting the $aaaaa$.
> 3 votes

---
Tags: automata, computation-models, pushdown-automata, nondeterminism
---


# Question
Title: What kind of optimization problem this belongs to?
Supervised learning is: given $X$ and $Y$, we want to find a good predictive function $f$ such that $f(X)$ is "close" to $Y$. Examples include XGBoost (ensemble of decision trees), neural networks, $\ell\_1$-regularized linear fit, etc.

In the problem I am encountering I have $X$. Each row of $X$ describes each day's scenario, for example, the financial market descriptors of that day. I don't have $Y$. $Y$ is the decision for each day, for example, whether I should buy/hold SP500. For each $Y$, I will have some scoring, say `score(Y)` system to describe whether my decision is good over a long period of time. Now, I want to find simple, robust $f$ such that $f(X)$ gets the low score. Of course, for arbitrarily complex $f(X)$, the score `score(f(X))` can be very low but the higher complexity generally means worse model for the problem I am tackling on. So there should be some regularization parameter that I could tune to control the complexity of $f$. The $f$ can be anything, like supervised learning. It could be ensemble of decision trees (XGBoost, random forest, etc...), linear (L1-regularized fitting etc.). I am currently essentially hard coding my problem into a optimization problem to solve on. But I think there should be a field out there tackling such problems.

If so, what is this type of problems generally called. And what's the state of the art packages currently in python. Thank you.

# Answer
> 1 votes
Yes, many standard methods can handle this. Your `score` is called a *loss function*. In particular, let $\ell(x\_i,y\_i)$ denote the penalty (score) if on input $x\_i$, your decision rule outputs $y\_i$. If $x\_1,\dots,x\_n$ is a training set, we define the total loss over the training set (the empirical risk) of a decision rule $f$ to be

$$L(f) = \sum\_{i=1}^n \ell(x\_i,f(x\_i)).$$

Now your goal is to find $f$ that minimizes the total loss $L(f)$. Many machine learning algorithms can be used in this manner, with an arbitrary loss function. Typically, we require that the loss function be differentiable, and then we use gradient descent to find $f$ that minimizes $L(f)$. For instance, if you are using neural networks, then you use gradient descent to find weights for the neural network that minimize $L(f)$. Often you add a regularization term to the loss function, too, to prevent overfitting.

---
Tags: optimization
---


title: Is plain multiplication a P problem?

text:
# Question
Title: Is plain multiplication a P problem?
I am a CS novice who just recently encountered the P vs NP problem. And I was wondering whether plain multiplication is a P problem. If it is, does that mean there is a polynomial relationship between the increasing complexity and the time required to solve? I.e. Is there a polynomial relationship between the time required to solve x\*1, x\*2, x\*3, x\*4, etc?

I tried to get some "experimental results" by writing simple a Java program that multiplies BigIntegers and counts time of execution. Curiously, I noticed that the execution time only increased in a polynomial manner (e.g. 2ms -\> 4ms -\> 6ms, etc) when the "complexity" grew in a exponential manner (e.g. x\*2 -\> x\*20 -\> x\*200, etc), meaning that time and execution of multiplication is a logarithmic relationship instead? Why is this?

Thanks in advance.

# Answer
Yes, and with many different algorithms.

See https://en.wikipedia.org/wiki/Computational\_complexity\_of\_mathematical\_operations

One important thing to notice is that the size of the input is the number of digits in the numbers, rather than the magnitude of the numbers (e.g. the "size" of the number 657 is 3, rather than 657, because it has 3 digits).
> 2 votes

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


title: Relational algebra and indexes

text:
# Question
Title: Relational algebra and indexes
How might indexes be represented in the context of relational algebra?

How would an optimizer transform a query to use indexes?

# Answer
> 4 votes
Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes **what** you must do, but not **how** you must do it.

It is comparable to the multiplication and other operations of the elementary arithmetic. There is a definition of what *multiplying* is but not of the way how you have to do it. There are several algorithms to multiply two numbers but the results are all equal. For further information see Wikipedia (What does it mean to multiply two natural numbers?).

Relating to your question that means that the result of an operation is the same with or without indices. The only difference is the increasing performance if you use indices.

# Answer
> -1 votes
@Elastic Lamb's answer is so terribly wrong in so many ways, I have to respond.

Relational Algebra is a practical/executable implementation of a system of logic, expressively equivalent to First Order Predicate Logic. In FOPL, you can state truths about the subject matter -- that's the **what**. RA corresponds to FOPL and -- *exactly* -- formulates the **how**. That's exactly the purpose for RA established by Codd's Theorem at the dawn of Relational Theory 1972

As well as truths like 'Employee E123 works in Department D456 ...' -- that is represented by a tuple in the Employee relation; or 'Employees in Departments D450 to D459' -- a query; you can state truths like 'Employee number uniquely identifies an Employee'; 'for all Employees, the Department each works in must be uniquely identified by a Department number which has a name'.

Those what we might call 'structural' truths are typically expressed in the database schema; and you can see those example truths express keys (uniqueness contraints/Functional Dependencies) and foreign keys (Inclusion Dependencies). Constraints/Dependencies are merely queries that return a Boolean result, and must always return True for the database content to be valid according to the business rules expressed in the schema.

So a practical implementation of RA would build indexes for rapidly validating updates, and give faster response to queries (which typically JOIN across FKs).

Most SQL engines under the hood convert your query to an algebraic form much more like RA. Then they can transform the RA expression using well-known equivalences; and how to transform will depend on what indexes are available, together with statistics about the content of relations and the clustering of keys around indexes. You can see that in practice by getting the query engine to explain its query plan. RA is crucial to the **how**, because SQL is not an algebra, not structured, barely a language.

---
Tags: relational-algebra
---


# Question
Title: Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof
Im having a lot of trouble proving that for the Regular expression $R\_{1} = \left( a^{\*} b^{\*} \right)^{\*}$ and $R\_{2} = \left( a+b \right)^{\*}$ that $L \left( R\_{1} \right) = L \left( R\_{2} \right)$. I was wondering if anyone could help me with this? thanks

# Answer
Proving equivalence of regular expressions can be tedious, so let me recommend two different strategies.

1. Convert both expressions into regular grammars using the algorithm from the equivalence proof. Then prove them equivalent.
2. Even more mechanical: convert both expressions into finite automata (using the algorithm from the equivalence proof). Showing equivalence is now moslty an algorithmic task the solution for which you should have seen in class.

> Determinise, minimize, show that they are isomorphic.
> 3 votes

# Answer
First prove that every word in R1 is also in R2; then prove that every word in R2 is also in R1. Spend some time on each and see what progress you can make.
> 2 votes

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


# Question
Title: How to properly describe this behavior (in terms of time complexity)
After completing the time analysis for an algorithm I have been working on, I need some help to write its time complexity properly, let me describe how it works...

The algorithm has two inputs $x$ and $y$.

When $x \< 15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

However when $ x \>= 15$, the steps to solve begin ramping down (from the $2^y$) at a rate of $-1\\%$ as $x$ increases, up to $x \< 50$ (don't know how to express this part)

And then, when $x\>=50$ it flats out, and keep the same cost, that is $O(2^y\*35\\%)$, and doesn't matter what is the value of $x$ (as long as it is greater than $50$)

How to write a time complexity that has 3 delimited phases depending on the inputs?

# Answer
> 5 votes
You're interested in asymptotic behavior as $x$ increases without bound.

$O(.35 \times 2^y)$ is still $O(2^y)$.

# Answer
> 2 votes
> When $x\<15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

It's also O(1).

Go back to the definition of $O$: small $x$ don't matter. In your case, pick $x\_0 \geq 50$ and ignore the other cases.

That said, your question reads as if you looked at plots, not done a proper analysis. Be aware that plots (or other means of looking at finite samples) *never* prove any asymptotic property. You may want to peruse our reference questions.

---
Tags: asymptotics
---


# Question
Title: Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?
For example, which part will detect these errors, Parser or Semantic Routine?

**1) int Array\[10.5\] ( wrong size )**

**2) int x="some string"**

**3) A\[10.5\] + 3 (not in declaration, but in the middle of the code)**

The book that I'm reading says the first one will be detected by parser but the third one will be detected by Semantic routine! I don't get it? why not both of them by parser? if the parser can detect first one, then it should be able to detect the third one

*ALSO*, i thought that lexical analyzers usually turn every number into a same token? for example:

a = 3.5 + 5 --\> id = num + num

so how can parser or semantic analyzer differentiate between a real number and a integer number?

Lets assume our compiler is a modern day compiler for C for example.

# Answer
It's impossible to say in general; it depends on the compiler resp. the exact definition of the syntax.

If your language contains special syntax for array declarations, the parser will note that it doesn't find an integer literal between the brackets.

For array accesses, the language probably allows arbitrary arithmetic expressions (including function calls) between the brackets. So the parser will create an expression tree, and only the type checker will determine that the expression is not of type integer.
> 3 votes

---
Tags: programming-languages, compilers, parsers
---


# Question
Title: How to simulate a k tape non deterministic turing machine with 2 tapes?
The only thing I found online about this is the following blog: http://blog.computationalcomplexity.org/2005/03/tape-reduction.html

where they write:

> Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

How exactly do you guess the transition function? And if you guess it, then why do you need to verify it? Isn't the guess in non deterministic turing machines always correct?

# Answer
> 1 votes
I think the idea is that we can run with just the first tape of the original machine while pretend other $k-1$ tapes exist. We pretend knowing states of other tapes by guessing every possible ones.

After the first tape executed, for those machines stopped in accept state, run with the second tape to see whether the guesses with respect to that tape were correct. Reject all wrong guesses. Repeat until all $k$ tapes are executed.

> Isn't the guess in non deterministic turing machines always correct?

For NDTMs, "correct guess" is that guess which will lead the machine into accept state. We need to reject all incorrect guesses by verifying them to make only the correct guesses (for our problem) correct (for NDTM).

---
Tags: turing-machines
---


# Question
Title: Find the $k$-th lexicographically smallest hamiltonian circuit
Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order.

For example, if we have complete graph with $4$ nodes, and $12$ edges. The smallest hamiltonian circuit is $1 - 2 - 3 - 4$, the second one is $1 - 2 - 4 - 3$. Since finding hamiltonian circuit is NP Hard, what is the best complexity we can get this algorithm at?

Hamiltonian circuit is path that visits each node exactly once.

For the purpose of the problem, the circuit should begin in node $1$

**What I think**

If we have adjacent list of nodes connected to node $1$, sorted, then the permutations numbered from $\[1, x\]$ will pass in the first node, the on the second node the permutations numbered $\[x, y\]$ will pass the second node, etc..

Now our task is actually to find the $x, y...$ And we can solve for the second node (that we called from node $1$) for each of nodes adjacent to it, but this leads us to time complexity of $O(N!)$. Can we do it faster?

# Answer
Counting the number of Hamiltonian circuits in a graph is $\mathsf{\\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph.

As an aside, let me mention that listing things in lexicographical order might be harder than listing them in any order. A case in point is the complexity of finding a \[maximal independent set\], which is an independent set which cannot be enlarged (but not necessarily one which has maximum size). A maximal independent set can easily be found by going over the vertices in some arbitrary order, putting the problem in the complexity class $\mathsf{P}$. This algorithm can be improved, and in fact a maximal independent set can be found in $\mathsf{NC^2}$. In contrast, finding the lexicographically first maximal independent set (that is, deciding whether a given vertex belongs to this set) is $\mathsf{P}$-complete.
> 1 votes

---
Tags: np-hard, hamiltonian-path, memoization, hamiltonian-circuit
---