# Question
Title: Integer solution that approximates a desired stock split
I am building software for an investment manager. The investment manager invests money on behalf of his clients.

The investment manager has a model portfolio, of say 20 stocks, each with certain weightage.

Eg: His model portfolio can look like this:

{GOOG: .03, AAPL: 0.4, MSFT: 0.25, TESLA: 0.5, IBM: 0.1, .....} Now lets say the investment manager has one client, who holds all of the stocks, the total of which is worth, say USD50,000, but with slightly different weightage:

{GOOG: .0295, AAPL: 0.415, MSFT: 0.232, TESLA: 0.1, IBM: 0.2, .....} Now the client wants to invest a lumpsum, lets say USD10,000.

Now, the investment manager wants to split this USD10,000 across 20 stocks, so that he gets closest to the model portfolio. i.e. I want the resultant USD60,000 to be split in a way that is closest to the ratios maintained in the model portfolio.

A limitation here is that, I can buy or sell a minimum of 1 stock; I cannot deal in fractions of stocks.

Is there a name for this kind of problem? I am pretty sure this has been solved by someone, so do not want to reinvent the wheel.

I do not know what I should google for, or where to start from.

I want the chosen allocation to have the least deviation from the model portfolio, measured by $L\_2$ distance (sum of squared differences). Also, the investor keeps investing periodically, so there is a chance his portfolio might deviate further and further, so the idea is to keep these "tracking errors" to a minimum, so that it the investor's portfolio is as close to the model portfolio as possible.

# Answer
> 3 votes
Let $d\_i$ be the desired dollar amount that you'd ideally like to have invested in the $i$th stock (i.e., $d\_1,\dots,d\_n$ represent the ideal/model portfolio, without taking the requirement to avoid fractional shares). Let $p\_i$ denote the price of a single share of the $i$th stock.

Then you want to find a solution to the following optimization problem

$$\begin{align\*} \text{minimize } &(p\_1 x\_1 - d\_1)^2 + \dots + (p\_{20} x\_{20} - d\_{20})^2\\ \text{subject to } &p\_1 x\_1 + \dots + p\_{20} x\_{20} = 10,000\\ &x\_1 \ge 0, \dots, x\_{20} \ge 0 \end{align\*}$$

where you require that the variables $x\_1,\dots,x\_{20}$ be integers. Here the $p\_i$'s and $d\_i$'s are given (they are known constants), and you've solving for the $x\_i$'s.

This is an instance of quadratic integer programming: i.e., integer programming with linear constraints and a quadratic objective function. That in turn is a special case of mixed-integer quadratic programming (MIQP). In general MIQP allows the problem to contain some integer variables and some continuous variables; your particular instance has only integer variables, so it's a special case of MIQP. You can find off-the-shelf MIQP solvers out there. I would recommend that you try applying one to your problem. Given the problem size you describe, I would expect them to be effective and efficient at your problem.

If you wanted to measure the deviation from the ideal model by the $L\_1$ distance (sum of absolute values of differences) instead of the $L\_2$ distance (sum of squared differences), that could be expressed as an instance of integer linear programming (ILP), for which solvers are even more effective.

---
Tags: algorithms
---


# Question
Title: Number of nodes of height $h$ in a heap or almost complete binary tree
I came up with the following statement:

> If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full.

That is to say, $X-1$ must full and the last node of height $h$ may or may not be full.

Intuitively it seems right, but I can't seem to prove it. Could someone help me prove it. If the statement is false, please let me know why.

# Answer
Except for the next to last level all nodes are full, nothing to show. On the last level there are only leaves.

Only on the next to last level there can be non-full nodes, i.e. nodes with only one child. And there can be leaves. So your reformulation should be "**X-1 nodes must be full or leaves.**"

Now it depends on the definition if the statement is true. If the last level must be filled from left to right, for example (this is the case if you implement the tree as an array), the next to last level looks like:

`full full ... full (one possibly non-full) leaf leaf ...leaf`

If another element is added, it must be a child of the non-full node and thus will make it full. If one element is removed, the non-full node will become a leaf.

As I said, the exact details depend on the exact definition of almost full binary tree. If the last level can be filled in an arbitrary manner, then the statement does not hold.
> 1 votes

---
Tags: graphs, trees, binary-trees, heaps
---


# Question
Title: Can a type system serve as a proof assistant for foreign functions?
Given that:

1. A language with very expressive type systems (e.g. Idris) can also have escape mechanisms like foreign function interfaces/unsafePerformIO.
2. There are proof assistants that can be used to prove some properties of a program written in a language that doesn't have a type system capable of expressing those properties.
3. The Curry–Howard correspondence shows that a successfully type-checked implementation of a function with a given type is proof of what is expressed by that type.

Can one express non-trivial proofs of some property of foreign language code in the type system of the native language?

For example, pretend I have a C function called stable\_qsort that sorts numbers in a terribly clever and efficient way while maintaining the order of already equal elements, and an Idris program that calls stable\_qsort via its FFI, but I don't trust this relatively obscure C function. Could I prove that the function doesn't reorder equal elements, for all inputs, in my Idris code instead of using a separate proof assistant?

# Answer
> 10 votes
Long story short: no you can't. A foreign function is like a black box and the type you ascribe to it is a promise you make: in the Curry-Howard correspondence that would correspond to adding an axiom to your theory.

That being said, there are ways. In Coq for instance, there are various formalisations of the C standard (e.g. Robbert Krebbers' work). Because you have an explicit representation of C programs and their semantics, you can write your code directly in the proof assistant and it is then possible to prove some of its properties.

---
Tags: type-theory, proof-assistants, curry-howard
---


# Question
Title: Puzzle/game of NP class for a high school student
Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better.

I want to demonstrate to a high school student the difference between P and NP class of problems using an example. Also, if there's some simple algorithm to show that it can be decided in polynomial time by a non-deterministic machine that would be a great bonus.

# Answer
> 2 votes
There is a list of a bunch of games that are NP-hard here: https://www.ics.uci.edu/~eppstein/cgt/hard.html You might also enjoy this list of Nintendo games that are NP-hard: https://jeremykun.com/2012/03/22/nintendo-np-hard/.

Some well-known games that can be proven to be NP-hard (in some form or other) include Tetris, Minesweeper, Checkers, Chess, Dots and boxes.

I think Dots and Boxes might be a particularly surprising and accessible one -- it's rather mind-blowing that such a simple-seeming game hides such complexity.

Caveat: do understand that in many of these cases, we're actually considering a variant of the game. Many games are finite, so there are only finitely many positions, and thus can't literally be NP-complete -- so instead we consider variants. For instance, instead of chess on a 8x8 board we consider a variant with a $n \times n$ board, or something like that. The general point still applies but there are technical details that you should make sure you understand before using this in a classroom.

# Answer
> 2 votes
One example that's familiar to many people is dishwasher loading. You have a set of items (3-dimensional objects) you want to fit in a dishwasher. Many people have experienced that greedy methods and heuristics don't work: you load up the dishwasher using some sensible method and things don't fit. But then if you start from scratch and load things slightly differently, there's plenty of room.

The dishwasher example is nice because it's relatively familiar, and gives some intuition about why NP hardness problems are really hard: fitting things nicely locally doesn't necessarily give a good global solution. It's also truly an NP-hard problem, even in very simple cases (like all your dishes are cubes).

It's obvious that an NP machine can solve dishwasher loading in polynomial time (as it can try all ways of loading the dishwasher non-deterministically). On the other hand, most natural NP-hard problems can be solved using something like this so I'm not sure if that's the structure you want.

A second example that's likely even more familiar is three-dimensional pathfinding. Many people have experienced the struggle of (say) trying to move a couch into a new apartment. Shortest path in three dimensions in general is NP-hard (see New Results on Shortest Paths in Three Dimensions by Mitchell and Sharir for example). Some disadvantages of this problem are that the technical aspect is more difficult, and that everyday cases are often easy. (Aside from moving couches into small apartments I solve 3-dimensional shortest path every day without much issue.)

---
Tags: complexity-theory, time-complexity, nondeterminism, education
---


# Question
Title: If a grammar is SLR(1) then are the LALR and SLR tables the same?
I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all that has to be in LALR.

# Answer
The tables aren't the same. The effect is not visible on correct inputs but on erroneous one. The SLR tables may indicate that a reduce operation is in order and then detect that the input is erroneous after the reduction when the LALR one will directly indicates that the input is erroneous without doing any reduction. That may have an influence on automatic error message generation and error recovery which are using the state of the push-down automaton to do their work.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Divide and Conquer majority element algorithm
The algorithm should return the majority element if it exists (majority meaning that there are $\> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

```
def findMajority(arr):
    if len(arr) == 1:
        return [arr[0], 1]
    else:
        leftHalf = findMajority(arr[:len(arr)/2])
        rightHalf = findMajority(arr[len(arr)/2:])

        if leftHalf[0] is None and rightHalf[0] is not None: #Left half is indeterminate
            return [rightHalf[0], rightHalf[1]]

        if leftHalf[0] is not None and rightHalf[0] is None: #Right half is indeterminate
            return [leftHalf[0], leftHalf[1]]

        if leftHalf[0] is None and rightHalf[0] is None: #Both halves are indeterminate
            return [None, 0]

        if leftHalf[0] == rightHalf[0]: #Majority in both halves is the same
            return [leftHalf[0], leftHalf[1] + rightHalf[1]]

        elif leftHalf[1] < rightHalf[1]: #Right majority has more occurrences
            return [rightHalf[0], rightHalf[1]]

        elif leftHalf[1] > rightHalf[1]: #Left majority has more occurrences
            return [leftHalf[0], leftHalf[1]]

        else: #There is no winner between the two halves and they have equal occurrences
            return [None, 0]

```

EDIT: It returns the wrong answer for \[2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0\] . So it doesn't work.

# Answer
> 2 votes
It's not correct. On input `[a a b c]`, the left side yields `[a, 2]`, the right side yields `[nil, 1]`. They would be merged into `[a, 2]`.

I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.

---
Tags: algorithms, arrays, correctness-proof, divide-and-conquer
---


# Question
Title: NP-Completeness of modified decision problems
Suppose we have a **NP**-Complete decision problem like independent set or finding matching in graph theory and we change the greatness or smallness of the condition of that problem i.e. change the direction of the inequality in the problem's definition ($ \ge$ or $\le $). For example in independent set problem when the condition is $|V'| \ge k$ and I change it into $|V'|\le k $. Are problems modified in this way still **NP**-complete?

# Answer
It depends on the problem. For, say, clique or independent set, the problems become trivial if you change the direction of the inequality: $\emptyset$ is always a clique/independent set of size $\leq k$.

On the other hand, the travelling salesman problem remains **NP**-complete if you ask for a tour of length at least $d$ instead of at most $d$. To see this, suppose that you want a tour of graph $G$ of length at most $d$. Let $m$ be the length of the longest edge in $G$, and let $G'$ be the graph that's identical to $G$ except that, if an edge has length $\ell$ in $G$, then it has length $m-\ell$ in $G'$. Now, any tour of length $t$ in $G$ corresponds to a tour of length $nm-t$ in $G'$ (where $n$ is the number of vertices), so $G$ has a tour of length at most $d$ if, and only if, $G'$ has a tour of length at least $nm-d$.
> 3 votes

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


# Question
Title: Primitive Recursive Function for Division and Hailstone function
Are division and Hailstone primitive recursion function?

$$\text{Div}(x,y) = \begin{cases} x/y, & \text{if $y$ divides $x$ } \\ 0, & \text{otherwise} \end{cases}$$

$$\text{Hailstone}(n) =\begin{cases} 3n + 1, & \text{if $n$ is odd } \\ n/2, & \text{if $n$ is even} \end{cases}$$

I tried to solve division in this way $$\text{Div}(0,y) = 0 $$ $$\text{Div}(x+y,y) = \text{Div}(x,y) + 1$$

I do not know how to proceed from here. Can anyone help me?

# Answer
> -2 votes
For your division example, what would the case be if y was equal to zero?

The function is undefined if y = 0. Thus, it is not a total function. Thus, division is not primitively recursive, as all primitively recursive functions are total functions.

---
Tags: computability, primitive-recursion
---


# Question
Title: Calculate the amount of formal languages
Statement:

> There are 256 formal languages $L$ with $L \subseteq \\{w \in \\{a,b\\}^\* \ \vert \ \ \vert w \vert = 3 \\}$

Answer:

> True.

My question is why there are 256 formal languages. If I calculate the possible combinations with length 3 I get 6 combinations:

$M =\\{aaa, aab, abb, bbb, bba, baa\\}$

Calculalting the power set results in: $2^M = 2^6 = 64$

Where did I go wrong the get $64$ as result?

# Answer
> 2 votes
That would be eight combinations, as $2^3=8$. You missed $aba$, and another one.

---
Tags: formal-languages
---


# Question
Title: How do I normalize a push down automaton?
Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q\_1$ to $q\_1$, because I know a transition must either push OR pop from the stack. Does this mean that there must be two separate transitions to push the * and then pop the \*? Or is it normalized as is? Is it okay to have multiple transitions from a single state to another, some of which pop, and some of which push?

# Answer
What do you call a normalized PDA? There are many ways to specify that. Also, a PDA is defined by its transition fonction. The diagram is just a convenient graphical way to do that, as long as it is precise and easily read.

For the example you give, a transition is not represented by a directed edge, but by a directed edge together with a label. If you have an edge with two labels, as in your loop on $q\_1$, that represents two transitions. Trying to do it with two separate loop edges would only make your diagram less readable.

Now, it is possible that your instructor has defined "normalized diagrams" in some way, and you should try to follow his wishes. But I do not remember of any such normalization of PDA diagrams with real technical importance.

Yes it is OK to have multiple transitions from one state to another. You could avoid it by introducing new intermediate states, but that would serve absolutely no purpose other than making your life miserable.
> 2 votes

---
Tags: pushdown-automata, notation, normal-forms
---


# Question
Title: Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL
I am trying to prove that the language $L=${$0^n 1^m |m ≤n^2$} is not a context free language. To do so I selected a string $w=0^p 1^{p^2}$. However, I am new to the CFL pumping lemma, and I am not sure if my proof is correct. Specifically, does the value of $i$ need to be the same for all divisions?

My first division is: v and y both contain 0’s.

$u=0^h$

$v=0^j$

$x=0^k$

$y=0^q$

$z=0^{-h-j-k-q} 1^{p^2}$

When $i=0$, I get $uv^0 xy^0 z=0^h 0^0j 0^k 0^0q 0^{p-h-j-k-q} 1^{p^2}=0^{p-j-q} 1^{p^2}$. This means $w$ contains less than p 0’s, but p2 1’s. This means for any valid value of p, there are more than p2 0’s. So this is not in the language.

The second division is either v or y contain both 0’s and 1’s. When $i=2$ I have $v=0^j 1^k$ or $y=0^j 1^k$, when $i=2$, so 0’s and 1’s out of order as the sequence $0^j 1^k$ will be repeated.

Finally the case that both v and y contain 1’s.

$u=0^p$

$v=1^j$

$x=1^k$

$y=1^q$

$z=1^{p^2-j-k-q}$

When $i=3$, the string becomes $uv^3 xy^3 z=0^p 1^3j 1^k 1^3q 1^{p^2-j-k-q}=0^p 1^{p^2+2j+2q}$. This means s contains more than $p^2$ 1’s, but only p 0’s, so the string is not in the language.

# Answer
> 2 votes
What you have done up to now is correct. The idea is that you should prove that the 'pumping' fails for all possible partitions of $w$. You have considered just two families of partitions, namely, the one for which $vxy\in0^+$ and the one for which $vxy\in1^+$.

You are missing the cases in which the sliding window (ie. $vxy$) crosses the boundary between $0$ and $1$.

Hence, next step is to consider the following cases (here $|w|$ is the length of $w$):

1) $vxy=0^{|vx|}0^h1^k$ where $h,k\geq 1$ and $h+k+|vx|\leq p$

2) $vxy=0^{|vx|}1^{|y|}$ where $|y|\>0$ and $|vxy|\leq p$

3) $vxy=0^{|v|}0^h1^k1^{|y|}$ where $h+k=|x|\>0$ and $|vxy|\leq p$

4) $vxy=0^{|v|}1^{|xy|}$ where $|v|\>0$, $|xy|\>0$ and $|vxy|\leq p$

All of the above cases can be easily solved with the technique you used with the former ones.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Interpolation on marching cubes algorithm
I'm currently learning how isosurfaces are extrated from volumetric data. I already understood the original marching cubes algorithm which is based on 3D-voxel data which stores only values of either 1 or 0. For learning purposes I implemented the easier version of it for 2D-volumetric data called marching squares algorithm. Results are shown below:

After all I read that the marching cubes algorithm can benefit of float values in the voxels instead of the binary values in terms of *interpolating the vertices*. However I do not understand how this should work simply because I'm missing the rules of which values should only be assumed for the voxels and also how the interpolation based on them would be done.

Could someone give me a fundamental view of how interpolation with the marching cubes algorithm is asumed to work? An example with 2D would be fine but showing how it works in 3D would be even nicer.

PS: For references, I read such stuff here.

# Answer
> 3 votes
*I worked it out on my own. I'm trying to write it down correctly so it's readable for newcomers.*

# Introduction

First of all, interpolation itself requires that there are float values and not binary values. This gives the ability to create different edge-crossing-vertices. How it's going I'm explaining now.

The interpolation which is needed here is linear interpolation. For understanding purposes I'll explain it here too.

# General Interpolation

After all, what is *interpolation*? Well good question. Interpolation is described as name for algorithms which smooth a given input of data e.g. points (with n-dimensions). Simpler there are points searched between the points for a given *interpolation value*. First it's required to give the points a base so that's clear where points are searched for in between. After that a specific algorithm for the interpolation has to be chosen. There are different kinds of interpolation algorithm out there each for a specific application. Best known is linear interpolation which results for a value one point on a line which crosses two input points.

The formula for linear interpolation (2D here) is as following (simply maths): $$ y = y\_{0} + (value - x\_{0} ) * \frac{y\_{1} - y\_{0} }{x\_{1} - x\_{0}} $$ with $$ value \in \mathbb{R} \wedge 0 \<= value \<= 1 $$

After all with this formula it's possible to apply interpolation on the vertices of the marching cubes algorithm which requires following rules.

1. The voxels must have a floating value instead of a binary value.
2. The value of the voxels must be only between zero and one
3. There must be a boundary value be declared which describes whether a voxel is supposed to be *in surface*.

Looking back to the blog the boundary value is called the *iso surface value*. This value describes as explained whether a voxel is being asumed to be *in* the surface so for acquiring the edge crossing. This is important to know because without it you wouldn't find out where even a edge-crossing computation is needed.

The interpolation is done on each coordinate of the two voxels position where and crossing-edge vertex is. The implementation is quite easy and looks like this (extracted from here):

```
/*
   Linearly interpolate the position where an isosurface cuts
   an edge between two vertices, each with their own scalar value
*/
XYZ VertexInterp(isolevel,p1,p2,valp1,valp2)
double isolevel;
XYZ p1,p2;
double valp1,valp2;
{
   double mu;
   XYZ p;

   if (ABS(isolevel-valp1) < 0.00001)
      return(p1);
   if (ABS(isolevel-valp2) < 0.00001)
      return(p2);
   if (ABS(valp1-valp2) < 0.00001)
      return(p1);
   mu = (isolevel - valp1) / (valp2 - valp1);
   p.x = p1.x + mu * (p2.x - p1.x);
   p.y = p1.y + mu * (p2.y - p1.y);
   p.z = p1.z + mu * (p2.z - p1.z);

   return(p);
}

```

# Conclusion

The interpolation of the edge-crossing vertices is a nice feature for smoothing the presentation of voxels.However the interpolation relies on that there are already floating values which means that it cannot smooth your existing binary data. For such cases different algorithms and approaches are needed.

---
Tags: algorithms
---


# Question
Title: Finite substitution and regular closure properties
I'm not sure if I get the following definition right:

1.Def: A map $\varphi: \Sigma^{\*} \rightarrow 2^{\Delta^{\*}}$ is called Substitution iff:

1. $\forall u,v \in \Sigma^{\*}: \varphi(uv)=\varphi(u) \varphi(v)$
2. $\varphi(\epsilon)=\\{\epsilon\\}$

My assumption: every string in $\Sigma^{\*}$ with the size $\>0$ maps to a Language from $\Delta^{\*}$.

such as:

$\Sigma := \\{a, b\\}$, $\Delta:=\\{0,1\\}$

$\varphi(a) = \\{01^{i}0 |i \in \mathbb N \\}$, $\varphi(b) = \\{w\in \Delta^{\*} ||w|\_{0} \neq |w|\_{1}\\}$

$\varphi(ab) = \varphi(a)\varphi(b)=\\{01^{i}0w |i \in \mathbb N \land w \in \Delta^{\*} |w|\_{0} \neq |w|\_{1}\\}$

example strings: 001, 000, 0101, 01011, 010100, ...

My first question: Is this assumption and example right?

2.Def: $\varphi$ is finitie iff $\varphi(a)$ $\forall a \in \Sigma$ is a finite subset of $\Delta^{\*}$

My assumption: $\Delta^{\*}$ is every possible string over the alphabet $\Delta$ and an finite subset would be a limited set $X \subseteq \Delta^{\*}$ $|X| \< \infty$

I would now implie that my first example is not a finite substitution, because a and b are not mapping to finite sets.

an example could be:

$\varphi(a) = \\{10^{i}1 | i \in \\{1,...,100\\}\\}$, $\varphi(b) = \\{\epsilon\\}$

$\varphi(bba) = \varphi(b)\varphi(b)\varphi(a) = \\{\epsilon\\}\\{\epsilon\\}\\{10^{i}1 | i \in \\{1,...,100\\}\\}=\\{10^{i}1 | i \in \\{1,...,100\\}\\}$

now I can implie that the class $REG$ is closed under finite substitution, because a concatenation of finite sets is finite and every finite set is regular.

My second question: Is this my assumption about finite substitution and the closure propierty right?

# Answer
You seem to have understood the operation of substitution. That maps any string into a language by concatenating the images of the letters.

Your argument that regular languages are closed under finite substitution does not work. Even if the substitution maps avery word into a finite language, the substitution of a regular language usually is infinite as the initial ragular language is infinite.

A possible approach is to use regular expressions.
> 1 votes

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


# Question
Title: I would like to know if there is a closed form expression from taking the reciprocal of a polynomial
I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading.

My idea is to multiply the numerator polynomial by the reciprocal of the denominator polynomial using Furer's algorithm to multiply dense polyomials with integer coefficients in a parallel fashion targeting multi-core processor architectures.

The URL , https://math.stackexchange.com/questions/469415/general-formula-for-polynomial-division , states that the algebra for deriving a general Formula for Polynomial Division is too tedious and complicated when the author substitutes 1/x for x in the numerator and denominator polymonials and then multiply the numerator and denominator by 1/x^(m+v) and factor the denominator by x^v.

# Answer
> 0 votes
The following URL, https://mathoverflow.net/questions/53384/power-series-of-the-reciprocal-does-a-recursive-formula-exist-for-the-coeffic, gives a closed-form expression with taylor series coefficients for the reciprocal of a polynomial with real coeficients. When I multiply the reciprocal taylor series coefficients by the numerator polynomial, I obtain the target quotient polynomial .

---
Tags: algorithms, polynomials
---


# Question
Title: Proving at least $n-1$ comparisons are needed to test if an array is sorted
so I need to prove the following:

Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.

The problem comes with the following hint:

Assume an algorithm exists that always correctly tests if the array is sorted using at most $n-2$ comparisons and show there must exist an input where this algorithm fails.

Base on the hint, I tried proving this via contradiction and here is my attempt:

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons. Then, let A be an array of 2 random numbers $a$ and $b$. Given that we don't know the value of $a$ with relation to $b$ or vice versa, in order to find this relation, an thus find out if the array with n-distinct elements is sorted in increasing order, 1 comparison operation, namely between $a$ and $b$, is needed, but then $n-2 = 1-2 \neq 1$. Therefore we have arrived at a contradiction.

While this attempt is most likely wrong, I am somewhat familiar with proofs by contradiction, but I don't see how deriving a contradiction from my initial assumption (the one from the hint) helps prove that $n-1$ comparisons are necessary.

# Answer
> 3 votes
You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a\_i$ with $a\_{i+1}$ for $i=0,1, \ldots, n−2$.

If it is not the case, you can carefully choose the values such that $a\_{i+1} \< a\_{i}$, *without* violating any other comparison results.

You are encouraged to fill the details.

# Answer
> 0 votes
For any $n \geq 1$, $n-1$ comparisons are sometimes necessary to test whether an array with n distinct elements is sorted in increasing order. An adversary argument will be used to prove this.

Suppose we have an array $A$ consisting of elements $a\_i, a\_{i+1}...a\_n$ with $a\_i = i$ for $i=1$ to $n$.

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons, and returns true if the algorithm is sorted in increasing order and false if it is not. Now suppose that the algorithm is run on array A. Then since $n-2$ comparisons are performed and the array contains $n-1$ pairs of consecutive elements, there must be a pair of consecutive elements which has not been compared to one another. Note that since $a\_i = i$ for every element of the array, the array is indeed sorted in increasing order and the algorithm will return true.

Following, suppose we find element $a\_i$ which was not compared to its successor by the algorithm and change its value to $i+2$ (previously $i$), and run the algorithm on array A. Then A is not sorted in increasing order anymore,since $a\_i = i+2 \> a\_{i+1} = i + 1$. but, since $a\_i$ is never compared to $a\_{i+1}$ the algorithm will still return true, which is incorrect.

---
Tags: proof-techniques, arrays, comparison
---


title: Solving the 10 players duel game

text:
# Question
Title: Solving the 10 players duel game
Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game.

**Rules of the game:** Players from #1 to #10 take turns to fire at each other. After round one, survivors repeat the circle (still in the order of #1 to #10). The game lasts many rounds until only one player survives. Players are rational and each calculates to maximize his survival probability.

**Question:** What is each player's optimal choice of target in his turn, when all 10 players are alive? And what are their respective survival probabilities? (**Technically, I'm looking for a pure strategy subgame perfect Nash equilibrium**, where the players follow deterministic strategies. Barring the very unlikely circumstance of ties, in which firing at one or the other player yields the same survival probability for the shooter, such an equilibrium is unique.)

---

My problem is I don't know how to write a tractable program to solve it. Let's consider 4 players with probabilities $(p\_1,p\_2,p\_3,p\_4)$. In this case, my reasoning is that the problem is solved by the following equations:

$s\_{i1}^4 = p\_1\*$(i's survival probability after 1 hits his target) $＋ (1-p\_1) * s\_{i2}^4$

$s\_{i2}^4 = p\_2\*$(i's survival probability after 2 hits his target) $＋ (1-p\_2) * s\_{i3}^4$

$s\_{i3}^4 = p\_3\*$(i's survival probability after 3 hits his target) $＋ (1-p\_3) * s\_{i4}^4$

$s\_{i4}^4 = p\_4\*$(i's survival probability after 4 hits his target) $＋ (1-p\_4) * s\_{i1}^4$

for $i=1,2,3,4$, where $s\_{ij}^4$ denotes i's survival probability when it's j's turn to fire, with 4 player alive. Notice that after a play hits his target, there's only 3 players left. So if we already know the 3 players case, the above equations can be solved. But I have no idea how to define a suitable structure and sub-programs to implement these thought... or maybe this is not the best way to look at the problem?

# Answer
> 4 votes
Robert Israel's answer on Math Overflow provides the key insight:

* If $S$ is the set of players remaining alive and it is player $j$'s turn, player $j$ should shoot at the player $k$ such that, if $k$ dies, the remaining set gives $j$ the best survival chances.

This enables us to build a dynamic programming algorithm, as Robert Israel states. I'll explain in a bit more detail how that works.

Represent a configuration of the game by $(S,j)$, where $S$ is the set of players remaining alive and $j$ is the player whose turn it is to shoot next. Define $f\_i(S,j)$ to be $i$'s probability of survival, under the equilibrium strategy for all (under optimal play), in configuration $(S,j)$. Then the insight above means that in configuration $(S,j)$, player $j$ should shoot at the player $k$ such that $f\_j(S\setminus\\{k\\},j+1)$ is as large as possible.

(As a conventional notation, when I write $(S,j+1)$, you should interpret $j+1$ as the next person to shoot after $j$, given that players $S$ are alive.)

Based on this, we can write recursive equations for $f$:

$$f\_i(S,j) = p\_j \cdot f\_i(S \setminus \\{g(S,j)\\}, j+1) + (1-p\_j) \cdot f\_i(S,j+1)$$

where

$$g(S,j) = \arg \max\_k p\_j(S \setminus \\{k\\}, j+1).$$

We'll start by calculating the values of $f\_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=1$. Then, we'll calculate the values of $f\_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=2$. Then, we'll calculate the values of $f\_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=3$.

At the $k$th stage, to calculate the $f$-values, we solve a system of linear equations in $k^2 \times {n \choose k}$ unknowns. (The unknowns are the terms $f\_i(S,j)$ where $|S|=k$ and $i,j \in S$. Note that at this point $f\_i(S \setminus \\{\text{anything}\\},j$ is known, since the first argument to $f$ will be a set of size $k-1$, which we've already calculated in the previous stage.) In your problem, $n=10$, so the $k$th stage involves solving a system of linear equations in $k^2 \times {10 \choose k}$ unknowns. This has a maximum at $k=6$, where we have 7560 unknowns. The system of linear equations can be solved using Gaussian elimination, which takes cubic time. In particular, Gaussian elimination on a $7560 \times 7560$ matrix is entirely feasible on a computer (probably it will take at most seconds).

Therefore, this should provide an efficient algorithm to compute the survival probabilities and strategy you are looking for.

---
Tags: algorithms, dynamic-programming, game-theory
---


# Question
Title: how the instructions are stored in relocatable format on disk
I understand how the instructions are kept in relocatable format in RAM. It is done so by keeping a base register and a limit register. Physical address = base register value + logical address. And logical address = the logical distance from the starting location of process's address space, just like an array.

But what I don't understand how are they kept in relocatable format on the disk, is there some base value there too. Plus how are they linked to a computer program say C Program or Java program using dynamic loading of shared libraries.

Please help me understand !!

Thanks.

# Answer
A compiled entity (say, a library) has a sequence of instructions. Each instruction has a particular location in sequence. This location is a value which can be considered simply as an offset from a base address. Loader loads the library at a particular address in the virtual address space of process and this address becomes the base address for the library and subsequently each instruction's location added to this base address becomes the actual address of the instruction in virtual address space of process.
> 2 votes

# Answer
## Instructions

To answer your question it's worth diving briefly into the instruction set of the architecture. Most instruction sets will contain 2 classes of jump instructions; the indirect jump and the direct jump. This includes call instructions and branch instructions as they generally all feature some kind of jump. The direct type will jump to a set location, i.e. `instruction pointer = value`. Indirect jumps will perform the operation `instruction pointer = instruction pointer + value`.

## The compiler

Since you want to be able to write in a higher level language you will likely be using a compiler, this saves you having to work out all these offsets. An option in the compiler is to have it assemble programs using indirect jumps exclusively. This mode is likely default because, as you're aware, there is an operating system to contend with and so you never know where your program is actually located. By avoiding direct jumps completely you no longer need to know where you are, just how far away you are.

## Why have direct jumps in the first place?

They're faster, there's one less operation involved and often more. An indirect jump will need to look at the instruction pointer and add a number to it. Direct jumps then find themselves used in time critical situations as you'd often find in embedded applications such as microcontrollers or very low level OS and BIOS work.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Complexity calculation of a recursive function with additional O(n) complexity
There is a method that I want to calculate its complexity in asymptotic notation. It calls additional methods(equals and substring) which complexity is $O(n)$. If it was $O(1)$, I could figure out complexity of the calling method. I have tried some operations; however, I'm stuck on calculation with the additional part. Can you solve its complexity with steps?

```
public static int func(String x)
   if(x == null || x.equals(""))
      return 0;
   else
      return 1 + func(x.substring(1));

```

# Answer
> 1 votes
This all comes down to the time it takes to compute `x.substring(1)` and `x.equals("")`.

If these methods were implemented in the obvious way (`x.substring(1)` builds up a new string by copying characters; `x.equals("")` compares character-by-character until the first match), then `x.substring(1)` would take $O(n)$ time and `x.equals("")` would take $O(1)$ time (because it only looks at the first character of `x`; if that is non-empty, it returns `false`).

So let's calculate the running time under the assumption that these methods are implemented in the obvious, naive way. `x.substring(1)` returns a string of length $n-1$. Therefore, you recursively invoke `func()` on a string of length $n-1$. Let $T(n)$ denote the running time of `func(x)` when passed a string `x` of length $n$. We obtain the recurrence relation

$$T(n) = T(n-1) + O(n).$$

(In other words, the recurrence you had is correct.) This recurrence solves to

$$T(n) = O(n^2);$$

see https://cs.stackexchange.com/a/2803/755 for details how. So, if those were the right assumptions about the running time of `substring()` and `equals()`, the running time of your method would be $O(n^2)$.

However, it turns out that some versions of Java implement `substring()` in a particularly clever way, with the result that `x.substring(1)` takes only $O(1)$ time, not $O(n)$ time. In particular, `x.substring(1)` doesn't make any copies of the string. Instead, it creates a new string object (call it `y`) which has a pointer to `x` and effectively says "hey, this string skips the first character of `x` and starts at index 1".

Consequently, when you take into account this more sophisticated understanding of how `substring()` works in some versions of Java, the recurrence becomes

$$T(n) = T(n-1) + O(1).$$

That solves to $T(n) = O(n)$. So, the total running time of your code is actually only $O(n)$, in those versions of Java, due to the clever way that Java implements the `substring()` method.

See https://stackoverflow.com/q/4679746/781723 to learn more about the running time of `substring()` and which of these analyses applies to you.

# Answer
> 1 votes
The question is absolutely not answerable without knowing what aFunctionWhichComplexityisO(n) returns.

Assuming that the function takes x as an argument, it might for example check if x contains the decimal representation of an integer y, and returns a string with the decimal representation of y-1 if y \> 0, and null if y ≤ 0 or x does not contain the decimal representation of an integer.

In that case if x contains n characters, the time is $O (n·10^n)$.

Or the function always returns null, then the time is $O (n)$.

# Answer
> 1 votes
Assuming that you have the right recurrence:

$T(n)=T(n-1)+2+(n-1)$

then you have

\begin{align\*} T(n)&=T(n-1)+2+(n-1)\\ T(n-1)&=T(n-2)+2+(n-2)\\ \vdots&=\vdots\\ T(n-k)&=T(n-k)+2+(n-k)\\ \vdots&=\vdots\\ T(1)&=T(0)+2+(1)\\ \end{align\*}

Summing-up you obtain:

$T(n)=T(0)+2n+\sum\_{i=1}^{n-1}i=2n+\frac{n(n-1)}{2}=\frac{n(n+3)}{2}$

(recall that $T(0)=0$)

Hope this is what you expected.

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Express a "complex" IF-Statement to Linear Programming
In our current project we need to model the following if-statement in linear programming:

```
If T1 < b < T2 then z = s else z = 0

```

where T1 and T2 are two integer values (e.g. T1 = 10 and T2 = 100) and s is also an integer value (e.g. 5).

We already know how to model a simpler if-statement with for example A \> 0 but we can not figure out how to model an if-statement with a condition t1 \< b \< t2.

Can someone help us?

---

Here is a little more detailed explanation of the problem:

In our problem we have several different ranges, each range with a lower and an upper bound, and for each of these steps we have to multiply another value to a variable (lets call this variable *k* and the result of this multiplication *z*). For example we have the following range and if-statements:

```
Ranges:
0   - 10 : 0
11  - 100: 9
101 - 200: 8.5
201 - 300: 8

IF-Statements
if 0   < b < 10  then z = k * 0
if 11  < b < 100 then z = k * 9
if 101 < b < 200 then z = k * 8.5
if 201 < b < 300 then z = k * 8

```

The lower and the upper bounds as well as the multiplication values are constants and known upfront. The rest (i.e. b, z, k) are integer variables for which we don't know the exact upper bound (lower bound is 0), but we know that they will not get too big. So, we are able to define M values for the M technique.

We already figured out how to do an if-statement like the following (T1 and T2 are the thresholds of the ranges from above, e.g. T1=0 & T2=10):

```
if T1 < b then z = k * something

```

and

```
if b < T2 then z = k * something

```

For this we transform T1 \< b to 0 \< b - T1 and b \< T2 to 0 \< T2 - b and then we use the way described here.

But we are stuck at how we can do the:

```
0 < b - T1 && b < T2 to 0 < T2 - b

```

The whole problem is a mixed integer linear programming problem, because we have also boolean decision variables and integer values like for example b.

# Answer
> 2 votes
You can solve this by introducing some temporary variables ($t,u,v$) and applying the big-M method.

For each expression `L <= b <= U`, we'll introduce 0-or-1 variables $t,u,v$, with the intent that $u=1$ if and only if $L \le b$ holds, $v=1$ if and only if $b \le U$ holds, and $t=1$ if and only if $L \le b \le U$ holds. We'll enforce this with the inequalities

$$L \le b + M(1-u), L \> b - Mu, b \le U + M(1-v), b \> U - Mv, 0 \le u+v - 2t \le 1,$$

where $M$ is a sufficiently large constant (you can take it to be at least the largest possible value of $b$, and at least $L$ and at least $U$). How does this work? The first two inequalities define $u$ so that $u=1 \Leftrightarrow (L \le b)$ using the technique from Boolean variable true iff equation is satisfied in ILP. The next two inequalities define $v$, similarly. The last inequality ensures that $t$ is the logical-AND of $u$ and $v$, using the technique from https://cs.stackexchange.com/a/43884/755.

Now, we'll enforce the constraint `if t=1 then z = k*c` for some constant `c`. We can enforce this using the inequalities

$$ck - M(1-t) \le z \le ck + M(1-t)$$

where $M$ is a sufficiently large constant (in particular, it needs to be at least $c$ times the largest possible value of $k$, and at least the largest possible value of $z$). Why does this do what we want? The argument is similar. If $t=1$, then the inequality is equivalent to $ck \le z \le ck$, which implies $ck=z$; if $t=0$, the inequality is equivalent to $ck-M \le z \le ck+M$, which imposes no restrictions on $z$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for more techniques for handling other sorts of inequalities.

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


title: Big theta of $ \lceil{log(n+1)}\rceil $

text:
# Question
Title: Big theta of $ \lceil{log(n+1)}\rceil $
I am trying to calculate the big theta of $ \lceil{log(n+1)}\rceil $.

I derived the following inequality:

$ log(n+1) \le \lceil{log(n+1)}\rceil \le log(n+1) + 1 $

Based on the definition of big theta, a function $ f(n) \in \Theta({g(n))} $ iff $ \exists \ c\_1,\ c\_2 \> 0 $ and a constant $k $ such that $ \forall n \ge k $, $ c\_1\cdot g(n)\le f(n) \le c\_2 \cdot g(n)$

This means that we must define the inequality in terms of multiplicative constants. However, I have no idea how to formulate such an equation. Could someone please advise me?

# Answer
There is no such thing as "the big-theta of a function", just as there is no such thing as "the number that's approximately equal to $\pi$." There are infinitely many functions $f$ such that $\log(n+1)=\Theta(f)$.
> 3 votes

# Answer
> $ log(n+1) \le \lceil{log(n+1)}\rceil \le log(n+1) + 1 $
>
> Based on the definition of big theta, a function $ f(n) \in \Theta({g(n))} \>$ iff $ \exists \ c\_1,\ c\_2 \> 0 $ and a constant $k $ such that $ \forall \>n \ge k $, $ c\_1\cdot g(n)\le f(n) \le c\_2 \cdot g(n)$
>
> This means that we must define the inequality in terms of multiplicative \>constants.

Remark that

$ log\_b n\<log\_b(n+1) \le \lceil{log\_b(n+1)}\rceil \le log\_b(n+1) + 1\< 3\log\_b n$

for $n\>1$.
> 0 votes

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


title: Sort array with minimum swaps

text:
# Question
Title: Sort array with minimum swaps
Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized.

I was thinking of first determining whether it is increasing type or decreasing type i.e. the type in which least swaps would be required and then sort my array in increasing or decreasing order accordingly. I don't know how to implement in determining the type. Can someone help me in finding heuristic or algorithm to do so ?

Also if the array is 2-Dimensional, would the idea still work or will I use less swaps if I change elements between rows instead of within the row itself. And if it has to be inter-row, how would I go about for that such that all rows are sorted (a row can be either increasing or decreasing) ?

# Answer
> 2 votes
Let $A$ be the array; by hypothesis there exists a unique permutation $\pi : A \rightarrow A$ such that $\pi(A)$ is sorted. The minimum number of swaps required to sort $A$ is the minimum $h$ such that there exists a decomposition of $\pi$ in $h$ transpositions.

Certainly $\pi$ can be broken down in at most $n-k$ transpositions where $k$ is the number of cycles in the unique cycle decomposition of $\pi$: it is sufficient to observe that a cycle $(c\_1, c\_2, \dots, c\_l)$ can be rewritten as $(c\_1, c\_l)(c\_1, c\_{l-1})\dots(c\_1, c\_2)$.

It can also be shown that $n-k$ is the minimum, the proof isn't straightforward but it's a known result that you can easily find in literature should you be interested.

As for your multi-dimensional case, the same idea should work, but you should be more specific about what you mean for a multi-dimensional array to be sorted.

---
Tags: algorithms, sorting, heuristics, permutations
---


# Question
Title: How to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and set operations?
I have to create new language with languages $L\_a = \\{a\\}, L\_b = \\{b\\}$ and with set operations which contains only words

1. with even length
2. with odd length and first letter not equal to last letter

So my solution for part 1 is this. Am I rigth?

> $L\_n = \\{aa, bb, ab, ba\\}\* = (L\_a.L\_a \cup L\_b.L\_b \cup L\_a.L\_b \cup L\_b.L\_a)\*$

Regarding to part 2, I dont have any simple solution. In this language must be words like these: $abb,bba,baaaa, ababb$ etc. So before first and last word must be only word with odd length. But I dont know how to write it.

# Answer
Part 1. is ok. The idea behind is that you have to take the letters 2 by 2 and then make the star closure. Call $L\_e$ the language of even words you just defined.

Part 2. Assume for a moment to have defined $L\_o$ the language of words of even length from $L\_a$ and $L\_b$. Then to have even length and different initial and final letter you can just define

$L=L\_a\cdot L\_o\cdot L\_b\cup L\_b\cdot L\_o\cdot L\_a$

Remark that words in $L$ have length at least 3 since $a$ starts and finish with the same letter...

To define $L\_o$ the idea is that an even word is just to exploit $L\_e$:

$L\_o=L\_a\cdot L\_e\cup L\_b\cdot L\_e$.
> 3 votes

---
Tags: formal-languages
---


title: Maximize product of sum of two subset

text:
# Question
Title: Maximize product of sum of two subset
Given two sets $A = \\{a\_1, a\_2, \dots, a\_n\\}$ and $B = \\{b\_1, b\_2, \dots, b\_n\\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\\{1, 2, \dots, n\\}$ to maximize $$ \left(\sum\_{i \in S} a\_i\right)\left(\sum\_{i \notin S} b\_i\right) $$

A naive solution is to iterate over the powerset of $\\{1, 2, \dots ,n\\}$ and find the maximum value, which is $O(n2^n)$. How to use dynamic programming to solve this?

Any comments would be appreciated.

# Answer
> 1 votes
If you could solve this problem, then you would be able to solve the NP-complete PARTITION problem. The partition problem asks whether a given set of positive integers $X$ can be partitioned into two equal parts. Given a set $X$ whose sum is $M$, choose an arbitrary ordering of its elements $X = \\{x\_1,\ldots,x\_n\\}$, and let $A=B=X$. Your problem asks to maximize $$ f(S) = \left(\sum\_{i \in S} x\_i \right) \left(M - \sum\_{i \in S} x\_i\right). $$ As a quadratic in $\sigma = \sum\_{i \in S} x\_i$, $f(S)$ is maximized at $\sigma = M/2$, at which we have $f = (M/2)^2$. This is achievable for some set $S$ iff $X$ can be partitioned into two equal halves.

---
Tags: optimization, dynamic-programming, sets
---


# Question
Title: Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets
The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k\<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling\_numbers\_of\_the\_second\_kind)

Is there an algorithm to generate all the possible combinations?

# Answer
Concretely, let us count the number of ways to partition $\[n\]$ into $k$ non-empty ordered subsets, which are themselves ordered by increasing order of the first element. For example, a valid partition of 10 into 5 sets is $$ \\{1,4,5\\},\\{2,3,6\\},\\{7\\},\\{8,10\\},\\{9\\}. $$ Note that $1\<2\<7\<8\<9$.

The base cases $k=0,k=1,k=n$ are easy, so suppose $2 \leq k \< n$. A partition of $\[n\]$ into $k$ ordered subsets can be obtained in two ways:

1. Taking a partition of $\[n-1\]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.
2. Taking a partition of $\[n-1\]$ into $k$ ordered subsets, and adding $n$ to the 1st subset, the 2nd subset, ..., the $k$th subset.

By recursively generating all partitions of $\[n-1\]$ into $k-1$ or $k$ ordered subsets, you can thus generate all partitions of $\[n\]$ into $k$ ordered subsets.

As D.W. mentions, this is just the recurrence for the Stirling numbers.
> 2 votes

---
Tags: algorithms, combinatorics, discrete-mathematics, partitions
---


# Question
Title: Decide given complexity of given function
I'm trying to determine correct notation for the given functions which are $f(n) = n$ and $g(n) = (log(n))^{100}$. Moreover, I don't understand while calculating its complexity using limit because calculator shows that it goes infinity, so f(n) is growing faster than g(n). But, I found vice versa. Could you explain me where I'm doing wrong?

# Answer
This answer assumes that $\log$ is to the base 2.

Consider $n = 2^{1000}$. Then $$ f(n) = 2^{1000}, \quad g(n) = (\log\_2 2^{1000})^{100} = (1000)^{100} \< (1024)^{100} = (2^{10})^{100} = 2^{1000}. $$ If you increase $n$ even more, you will see an even more dramatic difference between $f(n)$ and $g(n)$. You just have to consider large enough $n$, perhaps too large for your calculator.

What this example shows that even though $f(n)$ grows faster than $g(n)$, for values of $n$ encountered in practice the situation is very different, with $g(n)$ being much larger than $f(n)$. This shows the limits of asymptotic analysis – it is a natural and useful mathematical notion, but it isn't always a good model for reality.
> 1 votes

---
Tags: asymptotics
---


title: Closure under the Star Operation

text:
# Question
Title: Closure under the Star Operation
I'm doing my homework, but there's one task that I didn't get the idea.

Task:

Recall the alternative definition for the star of a language A that we gave just before Theorem 2.3.1. In Theorems 2.3.1 and 2.6.2 (which is about closure under union operation), we have shown that the class of regular languages is closed under the union and concatenation operations. Since $A^\* = \cup\_{=0}^\infty ^$, why doesn’t this imply that the class of regular languages is closed under the star operation?

# Answer
One must be careful about what the closure properties actually state.

If $A,B$ are regular languages, then $AB$ and $A \cup B$ are regular languages as well.

By induction, one can obtain that the concatenation / union of **finitely** many regular languages $A\_1,\ldots,A\_n$ is regular.

This however does not extend to infinite unions!

To understand why the extension would be wrong, consider a simpler case, first. Take the class of finite languages: sets containing finitely many words. Clearly this class is closed under union: if $A,B$ are finite languages, then $A\cup B$ is a finite language. However, taking the union of the infinitely many finite languages $\\{1\\},\\{11\\},\\{111\\},\ldots$ one gets an infinite language $\\{1,11,111,\ldots\\}$.

In the realm of regular languages, we met the same problem. Take any non-regular language $L$: it has to be infinite, since otherwise it would be regular. We can write $L=\\{w\_1,w\_2,\ldots\\}$ for some $w\_1,w\_2,\ldots$. But we also have $L=\\{w\_1\\}\cup\\{w\_2\\}\cup\ldots = \bigcup\_{i\geq 1}\\{w\_i\\}$, which is an infinite union of singleton-languages, which are regular. So, any non regular $L$ can be written as an infinite union of regular languages.

We conclude that the union of infinitely many regular languages is not necessarily a regular language.
> 3 votes

# Answer
$A^\* = \cup\_{=0}^\infty ^$ is just the definition of $star$-closure and this do not imply at all that if you take a regular language $L$ then $L^\*$ is regular. For that you need to prove the theorem you mention.
> 0 votes

---
Tags: regular-languages, finite-automata, regular-expressions, closure-properties
---


# Question
Title: What's the difference between dynamic and static pipelines?
I was trying to understand what a reservation table is in the context of pipelining, when I found this reference here, where the author mentions that there are *static* and *dynamic* pipelines. According to him/her,

> There are two types of pipelines: static and dynamic. A static pipeline can perform only one function at a time, whereas a dynamic pipeline can perform more than one function at a time. A pipeline reservation table shows when stages of a pipeline are in use for a particular function.

This definition sounds confusing to me: is "function" a synonym for "operation" in this case? So, a static pipeline can only process a batch of instructions that use the same operator? Like if the pipeline had to be "rewired" every time a new operator is issued? It makes no sense to me.

In order to get lost a bit more, I resorted to Wikipedia which states that

> A linear pipeline processor is a series of processing stages and memory access. A non linear pipelining (also called dynamic pipeline) can be configured to perform various functions at different times. In a dynamic pipeline there is also feed forward or feedback connection. Non-linear pipeline also allows very long instruction words.

So, static pipelines are *linear*, dynamic ones are *non-linear* and functions are indeed a synonym for operations in this context? And, finally, are static pipelines really reconfigured every time a new *function* is processed?

# Answer
The reference I've mentioned is actually self-contained; i.e, the answer I was looking for was there all the time. But considering that others could have the same doubt, I will reproduce an snippet from that reference and answer my own question:

> Pipelines are usually divided into two classes: instruction pipelines and arithmetic pipelines. A pipeline in each of these classes can be designed in two ways: static or dynamic. A static pipeline can perform only one operation (such as addition or multiplication) at a time. The operation of a static pipeline can only be changed after the pipeline has been drained. (A pipeline is said to be drained when the last input data leave the pipeline.) For example, consider a static pipeline that is able to perform addition and multiplication. Each time that the pipeline switches from a multiplication operation to an addition operation, it must be drained and set for the new operation. The performance of static pipelines is severely degraded when the operations change often, since this requires the pipeline to be drained and refilled each time. A dynamic pipeline can perform more than one operation at a time.

So, yes, a "function" is a synonym for "operation" in this context, but nothing is said about *linear* and *non-linear* pipelines. I hope some fellow can confirm if those terms exist indeed with the same meaning used in the Wikipedia.
> 1 votes

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


# Question
Title: Is there any efficient way of calculating the n-th fibonacci number modulo another number?
With efficient I mean of a big O of polynomial time in the number of digits each number has.

# Answer
Here are two suggestions:

**The linear algebra approach.** It is known that $$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F\_{n+1} & F\_n \\ F\_n &F\_{n-1} \end{bmatrix}. $$ You can compute the matrix power using repeated squaring, doing all the calculations modulo your modulus.

**Closed form.** If your modulus is odd and 5 is a quadratic residue (i.e., 5 has a modular square root) then you can use the explicit formula $$ F\_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}. $$ You can then use Carmichael's function to reduce $n$, and then repeated squaring. Care must be taken when the modulus isn't a prime power.

It is possible that a similar approach works more generally.
> 2 votes

---
Tags: number-theory
---


title: co-NP but not NP problems

text:
# Question
Title: co-NP but not NP problems
What are the problems that are in **co-NP** but not in **NP**?

i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.

# Answer
> 3 votes
**co-NP** is the set of complements of problems that are in **NP**. So **co-NP** contains problems such as non-3-colourability, Boolean unsatisfiability and so on. Most complexity theorists believe that **NP$\\,\neq\\,$co-NP** and one consequence of this is that the complement of any **NP**-complete problem would be in **co-NP** but not in **NP**.

Wikipedia has more information on **co-NP**.

# Answer
> 3 votes
Your question assumes $NP \neq coNP$, which is currently unknown (but generally assumed to be true). If $NP = coNP$, there is no problem satisfying your requirements.

If $NP \neq coNP$, the complement of any NP-complete problem works. You can find a list on Wikipedia.

---
Tags: p-vs-np, co-np
---


# Question
Title: Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting
Let me define the problems first

Polynomial Identity Testing $(\mathsf{PIT\text{}})$

**Given** : A polynomial $p$ over some field $\mathbb{F}$.

**Decide** : Are all coefficients of the monomials of $p$ are equal to zero ?

Polynomial Identity Testing $(\mathsf{PIT1\text{}})$

Polynomial identity testing defined in **non commutative** setting i.e. $x.y \neq y.x $

**Given** : A polynomial $p$ over some field $\mathbb{F}$.

**Decide** : Are all coefficients of the monomials of $p$ are equal to zero?

Evaluates to Zero Everywhere $(\mathsf{EZE\text{}})$

**Given** : A polynomial $p$ over some field $\mathbb{F}$.

**Decide** : Is it true that for every choice of numbers $a \in \mathbb{F}$, the value of $p(a)$ is the number $0$.

**My question** : Are $\mathsf{PIT\text{}}$ and $\mathsf{PIT1\text{}}$ equivalent?

**Reference** : http://www.cs.ubc.ca/~nickhar/W12/Lecture9Notes.pdf

# Answer
> 1 votes
PIT and PIT1 are not equivalent. For example, $xy-yx$ is the zero polynomial in the commutative setting but not in the non-commutative setting. You can get a non-commutative analog of EZE by considering large enough *matrices*, where large enough depends on the formal degree of the polynomial involved.

Suppose that $P$ is a multivariate polynomial in $x\_1,\ldots,x\_n$ which is not identically zero. We want to find a point where it is non-zero. The proof is by induction on $n$. If $n=0$ then $P$ is some non-zero constant, and there is nothing to prove. If $n\>0$, write $$ P = \sum\_{i=0}^d Q\_i x\_n^i, $$ where the $Q\_i$ are polynomials in $x\_1,\ldots,x\_{n-1}$, and $Q\_d$ is not identically zero. The induction hypothesis shows that $Q\_d(\alpha\_1,\ldots,\alpha\_{n-1}) \neq 0$ for some real $\alpha\_1,\ldots,\alpha\_{n-1}$. Making this substitution, we obtain a univariate polynomial $P'$ in $x\_n$ which is not identically zero. If $|\alpha\_n|$ is large enough, simple estimates show that $P'(\alpha\_n) \neq 0$, and so $P(\alpha\_1,\ldots,\alpha\_n) \neq 0$.

Here are the simple estimates: if $P' = \sum\_{i=0}^d c\_i x^i$ and $|\alpha| \geq 1$ then $$ |P'(\alpha)| \geq |c\_d| |\alpha|^d - \sum\_{i=0}^{d-1} |c\_i| |\alpha|^i \geq |\alpha|^{d-1} |c\_d| \left(|\alpha| - \frac{\sum\_{i=0}^{d-1} |c\_i|}{|c\_d|}\right). $$ This is non-zero if $|\alpha| \> 1+\sum\_{i=0}^{d-1} |c\_i|/|c\_d|$.

---
Tags: complexity-theory, randomized-algorithms, circuits
---


# Question
Title: Optimization problem where penalty is sensitive to permutation
Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I want to minimize my penalty ***P***. There is no limit to the amount of values I use (I could do 4x5, 20x1 and any other possibility).

The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.

In this example, let's assume the penalties are as follows:

* 1 * ***k*** for 0 \<= ***S*** \< 2
* 2 * ***k*** for 2 \<= ***S*** \< 6
* 3 * ***k*** for 6 \<= ***S*** \< 11
* 4 * ***k*** for 11 \<= ***S*** \< 20

where ***k*** is the current value being added to my intermediate sum ***S***.

So if I consider e.g. \[1,2,3,4,5,5\] (in that particular order), my total penalty would be ***P***=1\*1+1\*2+2\*3+3\*4+3\*5+4\*5=56.

However, the penalty changes if I permute my array to e.g. \[1,5,4,5,2,3\] (***P***=53) or \[2,4,5,1,3,5\] (***P***=61).

In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.

However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.

I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at ***S***=11, it no longer matters in what way I add the final 9).

My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations **a priori** (first generating *all* permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additional improvements that could be made here.

# Answer
I will outline two different solution methods. Either one will work -- pick whichever one you find easiest to understand and implement.

## Dynamic programming

This can be solved using dynamic programming. We'll fill in a one-dimensional table, so that $T\[s\]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$. Once we've filled in all of the entries, $T\[20\]$ will tell you the lowest penalty achievable for any combination that sums to 20.

So how do we fill in the table entries? We can fill them in recursively:

$$T\[s\] = \min(T\[s-1\]+p(s-1,1), T\[s-2\]+p(s-2,2), \dots, T\[s-5\]+p(s-5,5))$$

where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$. In the question, you tell us that $p(s,k) = k$ for $0 \le s \< 2$, $p(s,k) = 2k$ for $2 \le s \< 6$, etc.

Also, we have the base cases $T\[0\] = 0$. As a convention, we'll agree that $T\[-1\]=T\[-2\]=T\[-3\]=T\[-4\]=\infty$. Then you can fill in $T\[1\],T\[2\],\dots,T\[20\]$ in that order, using the recursive formula above.

This will give you the penalty of the best way to achieve the sum $20$. If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification. Basically, each time you fill in a $T\[i\]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.

## Graph search

Construct a weighted directed graph, with vertices 0, 1, 2, .., 20. Each vertex corresponds to a possible intermediate sum. From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add. The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.

Now find the shortest path from vertex 0 to vertex 20 in this graph. That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path. The shortest path will correspond to the combination with lowest penalty. You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.
> 2 votes

# Answer
Another way to view the problem using Dynamic Programming might be the following. We can first define the discrete recurrence relation of your sequence to be the following:

\begin{align} s\_{n+1} &= s\_{n} + u\_{n} \end{align}

where $s\_{n}$ is the sum up to, but not including, the $n^{th}$ term of the sequence, and $u\_{n}$ is the $n^{th}$ sequence term you will choose based on your set of possible sequence term values. Note all the possible values for the variables are as followed (based on your example):

\begin{align} u\_{n} &\in \mathcal{U} = \lbrace 1,2,3,4,5\rbrace \\;\\; \forall n\\ s\_{n} &\in \mathcal{S}\_{n} =\lbrace k \in \mathbb{N}: (n-1) \leq k \leq 5(n-1) \rbrace \end{align}

The above expression shows the set of possible values for $s\_1$ is only $\lbrace 0 \rbrace$, but grows larger each step in the sequence. The possible values for $s\_{n}$ can be reduced by tailoring the sets for a sum equal to $20$, but you can figure that out on your own. The next step is to define some cost function we wish to minimize with respect to $\lbrace u\_{n} \rbrace\_{n=1}^{M}$, perhaps:

\begin{align} V &= \gamma (s\_{M+1}-20)^2 + \sum\_{n=1}^{M} P\_{n}(s\_{n},u\_{n}) \end{align}

where $M$ is the size of the sequence, $s\_{M+1}$ is the final sum across all values chosen in the sequence, $\gamma$ is some constant, and $P\_{n}(\cdot,\cdot)$ is some penalty at the $n^{th}$ sequence as a function of the current sum ($s\_{n}$) and $n^{th}$ chosen sequence term value ($u\_{n}$). We can break this into pieces and recursively solve the optimization by doing the following:

\begin{align} V^{\*}\_{M+1}(s) &= \gamma (s - 20)^2 \\; \forall s \in \mathcal{S}\_{M+1} \\ V^{\*}\_{n}(s) &= \min\_{u \in \mathcal{U}} P\_{n}(s,u) + V^{\*}\_{n+1}(s+u) \\;\\;\forall s \in \mathcal{S}\_n\\ u^{\*}\_{n}(s) &= \arg \min\_{u \in \mathcal{U}} P\_{n}(s,u) + V^{\*}\_{n+1}(s+u) \\;\\; \forall s \in \mathcal{S}\_n \end{align}

Since this problem is discrete, you can obtain $V^{\*}\_{n}(s),u^{\*}\_{n}(s)$ by just looping through all $u \in \mathcal{U}$ for some $s \in \mathcal{S}\_{n}$ and store the best cost and choice values as $V^{\*}\_{n}(s),u^{\*}\_{n}(s)$ in lookup-tables/arrays. Once you have computed those optimal values, you can start at $s\_1 = 0$ and generate an optimal sequence using the discrete recurrence relation and $u^{\*}\_{n}(s)$.

**Edit 3/5/2017**

I implemented a code for the vanilla approach I describe above that you can check out here. Using this code, you can specify the sequence size you're interested in, the range of values that make up $\mathcal{U}$, the function $P\_{n}(s\_n,u\_n)$, and the final cost term (which I define as $\gamma (s - 20)^2$ ). The algorithm technically obtains an optimal policy (that need not be unique) and then uses it to generate the optimal sequence.

Using the example provided by the OP, the code finds a sequence of $( 1, 4, 5, 5, 1, 4 )$ as optimal with a penalty of $P = 50$. If I then increase the sequence size to have 10 elements, the optimal sequence $( 1, 3, 1, 5, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 51$. If I increase the sequence size to have 15 elements, the optimal sequence $( 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 56$.

The Dynamic Programming formulation makes these results quite efficient to obtain, though things could be slimmed down further with some clever modifications.
> 1 votes

# Answer
With the help of D.W.'s answer I managed to tackle the problem quite easily.

See below code for my implementation of the example problem in MATLAB using dynamic programming. If there's any way to further optimize this, I'd love to hear it!

**edit:** also added the graph search approach. That one was ridiculously simple to implement..!

## Caller script (Dynamic programming)

```
% Set target value
V = 20;

% Define globals for lookup-table LUT and allowed values pVals
global pVals LUT
pVals   = randperm(5);  % use values 1 to 5 in random order
LUT     = cell(2,V);    % row 1: minimum penalty | row 2: used values

% Perform the calculation
[minPenal, usedVals] = T(V);

% Verify correctness of answer
currPenal = 0;
currSum   = 0;
for ii=1:length(usedVals)
    currPenal = currPenal + p(currSum, usedVals(ii));
    currSum   = currSum + usedVals(ii);
end

if isequal(minPenal, currPenal) && (currSum==V)
    fprintf('\rPossible solution (P = %d):\n%s\n', minPenal, num2str(usedVals))
else
    fprintf('\rSomehow the recursion failed to obtain a solution... :(\n')
end

```

## The recursive function (Dynamic programming)

```
function [minPenalUpToVal, bestSeq] = T(targetVal)

global pVals LUT

if ~isempty(LUT{1,targetVal})
    % No need to redo the calculation if it has been done already
    minPenalUpToVal = LUT{1,targetVal};
    bestSeq         = LUT{2,targetVal};

else
    % Initialize arrays
    currPenal   = zeros(1,length(pVals));
    currSeq     = cell(1,length(pVals));

    % Loop over all possibile "previous states" that could result in V
    for pv = 1:length(currPenal)

        % Fetch the increment that may have made the current target possible
        incr = pVals(pv);

        if (targetVal-incr < 0) % Invalid, we rule this out by setting the penalty to inf
            currPenal(pv)  = inf;

        elseif (targetVal-incr == 0) % We know the penalty is zero at zero, so we don't need a minimum penalty
            currPenal(pv)  = 0 + p(targetVal-incr,incr);

        else % Recursive approach to get the minimum penalty up to V along with a possible solution to get there
            [penalUpToVal, currSeq{pv}] = T(targetVal-incr);
            currPenal(pv)               = penalUpToVal + p(targetVal-incr,incr);
        end
    end

    % We are only interested in the lowest penalty to get to V
    [minPenalUpToVal, idx]  = min( currPenal );
    bestSeq                 = [currSeq{idx} pVals(idx)];

    % Store these above quantities in our lookup-table
    LUT{1,targetVal} = minPenalUpToVal;
    LUT{2,targetVal} = bestSeq;

end

end

```

## Caller script (Graph search)

```
% Set target value
V       = 20;
pVals   = randperm(5);  % use values 1 to 5 in random order

% Preallocate matrix
A = zeros(V+1,V+1);
for ii=1:V+1 % Loop over nodes
    for jj=pVals % Generate the edges
        if (ii+jj <= V+1) % Avoid exceeding our target
            A(ii, ii+jj) = p(ii-1, jj);
        end
    end
end

% Solve the problem with MATLAB built-in functions.
G       = digraph(A);
[sP,dP] = shortestpath(G, 1, V+1);
fprintf('\rPossible solution (P = %d):\n%s\n', dP, num2str(diff(sP)));

```

## Penalty function

```
function p_out = p(s, k)

if (s < 2)
    p_out = 1*k;

elseif (s < 6)
    p_out = 2*k;

elseif (s < 11)
    p_out = 3*k;

elseif (s < 20)
    p_out = 4*k;

end

end

```
> 1 votes

# Answer
I'd change it from "penalties" to rewards. Pretend you have n slots that you need to fill with coins, and you have piles with different amounts of coins available. You can take a pile of k coins, find k consecutive empty slots, and fill these slots with coins.

Now the rewards: In your example, if you take a pile of k points and start dropping them at position 0 ≤ S \< 2, and S + k \> 2, then you get S + k - 2 rewards. If you start dropping them at position 2 ≤ S \< 6, and S + k \> 6, then you get S + k - 2 rewards and so on.

We can simplify this: If you drop m coins at position S, and S is the highest position 0 ≤ S \< 2 where coins are dropped, then you get S + k - 2 rewards. In your example you can get 3 rewards (the fourth reward is always zero), so you maximise the sum of those three rewards.
> 0 votes

---
Tags: algorithms, optimization, permutations
---


title: CFL and inverse homomorphism

text:
# Question
Title: CFL and inverse homomorphism
I found a proof that shows CFL is closed under inverse homomorphism.

First of all the Definition of an homomorphism and its inverse:

$h: \Sigma^{\*} \rightarrow \Delta^{\*} \ \ \ h(L) = \\{h(w) |w \in L\\}$

$h^{-1}: \Delta^{\*} \rightarrow \Sigma^{\*} \ \ \ h^{-1}(L) = \\{w | h(w) \in L\\}$

The proof I found works as follows:

Let $L = L(A)$ for some PDA $A$. Construct PDA $A’$ to accept $h^{-1}(L)$. $A’$ simulates $A$, but keeps, as one component of a two-component state a buffer that holds the result of applying $h$ to one input symbol.

I really can't get my head around that intuition. My approach was to create an example:

Let $L=\\{a^{n}b^{n} | n \in \mathbb N\\}$ and $h: \\{a,b\\}^{\*} \rightarrow \\{0,1\\}^{\*} | \ \ h(a) = 01, h(b) = 1$

$\Rightarrow h(L)= \\{(01)^{n}1^{n} | n \in \mathbb N\\}$

I would then create an PDA $A$ that accepts my $h(L)$ and PDA $A'$ (because I already know how my inverse image looks like) that accepts $L$.

And that is the point I got stuck. I know that I need a different PDA for $A'$ with some sort of buffer but I don't know how to realise that.

My Question: Can someone explain the proof a little bit more detailed. And what it means that $A'$ simulates $A$?

# Answer
> 1 votes
Suppose that $A=(Q,\Delta, \Gamma, \delta, q\_0, \gamma\_0, F)$.

Define $\operatorname{Prefs}(u)$ to be the set $\\{v|\exists w, u = vw\\}$ of prefixes of $u$.

Define $A':=(Q',\Sigma, \Gamma, \delta', q\_0', \gamma\_0, F')$ by:

* $\displaystyle Q':= \left(Q\times \left(\bigcup\_{a\in \Sigma}\operatorname{Prefs}(h(a))\right)\right) \sqcup \left(Q\times \Sigma \right)$. A state $(q,u)$ with $u\in\operatorname{Prefs}(h(a))$ will mean "I'm in state $q$ in $A$, I've read $u$ and am waiting for the rest of $h(a)$ and then I'll go to $(q,a)$" while a state $(q,a)$ means "I've read $h(a)$ and will now simulate a transition reading $a$ in state $q$ in $A$ to arrive to some state $(q',\varepsilon)$".
* Transitions are (where if a transition doesn't mention the stack, it means it doesn't change it):

+ $(q,u)\overset{b}{\to}(q,ub)$ whenever the destination state exists (i.e. if you can read the letter while remaining a prefix of some $h(a)$, you can just keep reading)
    + $(q,h(a))\overset{\varepsilon}{\to}(q,a)$ (i.e. at any point, if the word I've read is the image of a letter by $h$, I can replace it by its preimage)
    + $(q,a)\overset{\varepsilon,...}{\to}(q',\varepsilon)$ whenever $q\overset{a,...}{\to}q'$ in $A$ (where both $...$ are the same thing) (i.e. if I just read the image of $a$, simulate reading $a$ in $A$)
* $q\_0':=(q\_0,\varepsilon)$
* $F':=F\times \\{\varepsilon\\}$

Then (I think that) $L(A')=h^{-1}(L(A))$.

What you call "buffer" would be the right component of the states used to remember the prefix of $h(a)$ you've read.

---
Tags: context-free, proof-techniques, pushdown-automata
---


# Question
Title: Minimize longest continuous streak of $1$s after flipping $m$ $-1$s to $1$s
Given an array a of length n of $-1$s and $1$s, and another input $m$, I was supposed to minimize the longest continuous streak of $1$s or $-1$s after flipping $m$ $-1$s to $1$s or vice versa.

I know how to maximize it but can't figure out how to minimize it. I maximize the number of $1's$ by sliding window method. Take a window ($wleft$ , $wright$).It covers given array from index $wleft$ to $wright$. I represent $-1$ with $0$ for ease.Suppose number of zeros in window in $wzeros$.

Algorithm :

```
while wright < length of array {

     wzeros <= m: increment wright

     wzeros>m: increment wleft

  // Update the max window size during this whole process.

        int temp = wright-wleft;
        if(temp > mx_length){
          mx_length = temp;
          solution_window = wleft;
        }
    }

```

This code maximizes the number of consecutive $1$s whereas I want to minimize the number of consecutive $1$s and $-1($or $0)$s. How do I modify the algorithm/code to achieve so ?

# Answer
> 1 votes
You can use dynamic programming. It is very likely that much faster algorithms exist.

Given a string $w$ of length $n$, for $0 \leq i,j \leq n$ and $0 \leq k \leq m$ you compute the minimal maximum 1-run in $w\_1,\ldots,w\_i$ given that $k$ many -1s were changed to 1s, and given that $w\_1,\ldots,w\_i$ ends in a 1-run of length $j$.

This gives an $O(n^2m) = O(n^3)$ algorithm.

---
Tags: number-theory, searching
---


# Question
Title: What are the gates used to implement Shor's algorithm?
I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?

# Answer
There are several correct answers to this question because there are several candidate sets available for use as a universal set of quantum operators and because there isn't an agreed upon best implementation for the primitives needed by Shor's algorithm. Different circuits will trade-off circuit-depth for ancillary qubits and vice versa. Ultimately, the exact implementation is likely to depend on the architecture of the quantum computer.

What that in mind, you can probably find a version of the details you're looking for in Fast Modular Exponentiation Architecture for Shor's Factoring Algorithm by Pavlidis and Gizopoulos. The exact circuit layout is lengthy and complex and probably too much for an answer here. The paper has lots of diagrams though and a quick scan should should provide you with a rough feel for the circuit construction. Unsurprisingly, the circuit makes heavy use of Hadamard gates and controlled phase-shift operators both to implement the inverse QFT and the modular exponentiation circuit.
> 2 votes

# Answer
According to quantumplayground.net shor's algorithm uses some swaps, hadamards, measuerments, and Inverse Quantum Fourier Transform gates.
check it out yourself: Shor's Algorithm
> -2 votes

---
Tags: algorithms, quantum-computing, circuits
---


# Question
Title: Shortest past including an edge from a given set
I am working on the following problem.

There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find the minimum number of broken roads taken. If no good road is taken, display −1.

I am trying to use Dijkstra shortest path algorithm for this. I have assigned weight 0 to the good roads and 1 to broken roads. Then I find the shortest path taken. According to me, this shortest path should be equal to the minimum number of broken roads taken. For considering the case where all the roads are broken, I check if the total weight of path is equal to the number of roads taken, then display −1. But I understand, this algorithm will not work always.

What would be the right approach for this problem?

# Answer
Create two copies of your graph. The first copy represents not having taken a good road, and the second copy represents having taken a good road. You transfer between the copies by taking a good road. The weighting scheme you describe will result in minimizing the number of broken roads. Details left to you.
> 1 votes

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


title: I need help with virtual memory problem

text:
# Question
Title: I need help with virtual memory problem
• Given the above virtual to physical address mapping,

1 What is the page size?

2 How many virtual pages can we have in maximum?

3 How many physical pages can we have in maximum?

Approach:

1 For the page size I would say I don't know because we have no information that gives us a clue about page size.

2 I think that we can have as many as the number of physical frames in memory

3 As many as we want, but since we have to constrain the number pages to the number of bits in the address then I would say 2^15 pages.

Can you give me some insight to get to the right idea to solve this problem?

# Answer
A quick search reveals that

* POFS is page offset.
* VPN is virtual page number.
* PFN is page frame number.

Since the page offset is 13 bits long, assuming that the page is byte-addressed, the conclusion is that page size is $2^{13}$ bytes.

I trust that you can solve the other parts in a similar way, especially having been taught these concepts in class.
> 2 votes

# Answer
The first part of the question has been been correctly addressed . For the second part imagine if the number of virtual pages were to be equal to the number of physical pages there would be no benefit of the virtual memory. The number of virtual pages is $2^{20}$. That is the remaining bits of the virtual address.

Usually in the implementation of the OS it is the PAGE SIZE and the FRAME SIZE which matches.hence the number of page offset bits in virtual and physical address is same. Number of physical frames can be found by the remaining bits of the physical address.
> 0 votes

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


# Question
Title: Finding the Shortest Path that connects k nodes in a graph
I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass through all the $k$ nodes, but can contain other nodes from the graph and can visit those $k$ nodes in any order. In addition, any node can be traversed more than once. Also, the path has to start and end with two distinct nodes from the given set of $k$ nodes. For example, if $k=2$, we have two nodes, $u\_1$ and $u\_2$, and are looking for the shortest path from $u\_1$ to $u\_2$. We can use UCS or $A^\*$ to solve this. If $k=3$, there will be three nodes: $u\_1$, $u\_2$, and $u\_3$. The path can start in $u\_1$, pass through $u\_2$, and finish in $u\_3$, or start in $u\_2$, pass through $u\_1$, and end in $u\_3$, etc. $k$ can take any value from $2$ to $n$, $n$ being the total number of nodes in the graph.

To me, this somewhat looks like a problem of finding the minimal tree whose leaves are those $k$ nodes. A path passing through the leaves could then be obtained by traversing the tree in an appropriate order.

# Answer
> 2 votes
The state of a traversal at any point will be (a) the node you're currently at, and (b) the subset of the $k$ selected nodes you've already passed through. Thus, you can solve this problem by constructing a new graph $G'$ that is $2^k$ times as large as the original graph $G$, and then finding the shortest path in $G'$.

In particular, each vertex of $G'$ has the form $(v,S)$ where $v \in V$ and $S$ is a subset of the $k$ selected nodes; for each edge $v \to w$ in the original graph, $G$' has the edge $(v,S) \to (w,S)$ (if $w$ is not one of the selected $k$) or $(v,S) \to (w,S\cup \\{w\\})$ (if $w$ is one of the selected $k$).

Unfortunately the running time of this algorithm is exponential in $k$. I don't expect there to be a polynomial-time solution; David Richerby explains why not.

# Answer
> 1 votes
A tree which includes all the vertices in your set of "interesting" vertices is a Steiner tree. Finding minimum-weight Steiner trees is **NP**-hard.

Note that any tree necessarily has at least two leaves, and every leaf is necessarily an "interesting vertex", since any leaf that isn't interesting doesn't help to connect the interesting vertices, so can be deleted to make a lower-weight tree that still connects the things that need to be connected. This means that you can definitely find a traversal of the tree that starts and ends at leaves and visits every vertex. However, there may be "interesting" vertices in the interior of the tree. For example, if the original graph is a tree and every vertex is interesting, the minimum-weight Steiner tree is, of course, the whole graph.

However, the minimum-weight walk that visits every interesting vertex is not necessarily a traversal of a Steiner tree. Suppose, for example, that you have vertices 1-4 and edges 12, 13, 14 of weight 1 and 23 of weight 1.5. The minimum-weight walk is 4123, with weight 3.5, but the minimum Steiner tree is the weight-1 edges and any traversal of that (e.g., 41213) has weight 4.

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


title: 2-SAT implication Understanding

text:
# Question
Title: 2-SAT implication Understanding
Having a simple 2-SAT problem where the equation is simply: $a \lor b$

We have two implications:

$\lnot a \Rightarrow b$
$\lnot b \Rightarrow a$

Thus, in the graph we build we add edges similar to the arrows above.

What exactly do the arrows symbolise in this instance? I've read that they means if $a$ is true, $b$ must be true as well. The same for false. Why can we model this equation in such a way?

# Answer
> 5 votes
You are asking why we can model the equation $a \lor b$ as two directed edges in a graph. The answer is that mathematics is a free country, and we are allowed to do whatever we want. The only restriction we have to obey is that whenever we claim a result, it must be accompanied by a valid proof.

This representation is used in an algorithm that decides whether a 2SAT instance is satisfiable. As you mention, an edge from a literal $\ell\_1$ to a literal $\ell\_2$ means that if $\ell\_1$ is true, then $\ell\_2$ has to be true. Indeed, if $a \lor b$ holds then if $\lnot a$ is true, $b$ must be true, and vice verse, if $\lnot b$ is true, $a$ must be true.

If there is a path from some literal to its negation – from $x$ to $\lnot x$ or from $\lnot x$ to $x$, for some variable $x$ – then clearly the formula is not satisfiable, since $x$ cannot be both true and false. A more delicate argument shows that if no such paths exist, then the formula is satisfiable. This is proved by showing how to find a satisfying assignment for the formula (it's a nice exercise).

# Answer
> 2 votes
The arrows symbolize material implication, which is the operator with the truth table

$$\begin{matrix} A & B & A\Rightarrow B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}$$

---
Tags: 2-sat
---


# Question
Title: The content of an implication from the snm-Theorem
I have a question on the statement of the s-m-n Theorem and the implication $$ \varphi\_{f(x,y)} = \lambda z \varphi\_x(\varphi\_y(z)) $$ for some recursive function $f(x,y)$ cited in the above link. In what sense does this follows from the s-m-n theorem and in what sense does it gives anything new?

To be more specific. As I see it to apply the s-n-m-theorem the function on the right side must be partial recursive or computable, but $\varphi\_x(\varphi\_y(z))$ is just the composition of computable functions (by the universal turing machine theorem $(y,z) \mapsto \varphi\_y(z)$ and so on are computable). But knowing this already says that it has some Gödel coding, and the fact that this is effective (and total) is given by the typical proofs that the composition of computable functions is computable (i.e. by giving an algorithm to construct a suitable Turing machine). So the statement that there exists some recursive $f(x,y)$ gives nothing new to what I know from the basic proof that the composition of computable functions is computable?

So have I missed anything? Or in what sense does this follow from the snm-theorem? And does it states anything nontrivial?

# Answer
> 1 votes
Your assumptions on composition are quite strong. The idea, here, is that you are only assuming that the class of (partial) computable functions is closed with respect to composition (so you only know that you must have some program computing it) and then use smn to prove that you can uniformely and effectively compute an index for such a program from the indexes of the programs you are composing (x and y in your example).

Instead of spending time to show that you can effectively construct a turing machine computing the composition of two other turing machines (that is not so trivial) it is better to spend some time to prove smn, that gives you a much more general technique:

1. it proves that any partial instantiation of a computable function is still computable
2. it tells you that you may compute the index of the partial instatiation in a uniform and effective way in terms of the index of the source program and the parameters of the given instantiation (hence, providing a form of parameter abstraction, quite similar to lambda abstraction).

Coming back to your examples, the "source" function is

$$g(x,y,z) = \varphi\_x(\varphi\_y(z))$$

and you are computing the partial instantiation of $g$ with respect to x and y. The point is that $g$ can be any computable function, and you are free to choose your parameteres in any way you like. A real jolly.

I strongly suggest you to have a look at the following answer on mathoverflow, that gives a very, very nice explanation of smn.

---
Tags: formal-languages, computability, turing-machines
---


# Question
Title: Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?
I would like to know why the following statement

> The running time of algorithm $A$ is at least $O(n^2)$

which means the best-case running time of $A$ is $O(n^2)$ is meaningless (CLRS page 53).

But the following is not

> The worst-case running time of algorithm $A$ is $\Omega(n^2)$

(used in CLRS page 160).

# Answer
First of all, both sentences are a slight abuse of notation. $\mathcal{O}(n^2)$ and $\Theta(n^2)$ are sets; strictly speaking you can't compare a running time with a set. Saying "$f$ is $\mathcal{O}(g(n))$" is actually a shorthand for "$f$ belongs to the set $\mathcal{O}(g(n))$"; with that in mind, we can rephrase the statements you quote as follows:

> The running time of $A$ is at least $f(n)$ for some $f \in \mathcal{O}(n^2)$.

and:

> The worst-case running time of $A$ is at least $f(n)$ for some $f \in \Omega(n^2)$.

Put in this form, the first statement is well-defined, but it's not really insightful. In fact, it is always true. Let $g$ be the constant function $0$. Certainly $g$ is a member of $\mathcal{O}(n^2)$, and whatever the running time of $A$ is on input of size $n$, it is at least $g(n)$.

Intuitively speaking, big-oh is an upper bound: if I tell you: "I have at least $100 or less", I didn't really give you any information at all.

On the other hand, the second statement guarantees that the worst-case running time of $A$ cannot be too low: it must grow at least quadratically.
> 9 votes

# Answer
Saying that

> The running time of the algorithm is at least $O(n^2)$

is pointless since it does not describe what could be neither the average case nor the worst one. Hence you would classify in the same complexity class algorithms which have very different worst case behaviors say polynomial wrt. exponential. In the second statement saying

> The worst-case running time is $\Omega(n^2)$

is precise since it allows to put in the same class only algorithms that are really uniform with respect to their computational complexity.
> 1 votes

# Answer
The short intuitive answer is that the big-O notation is used to express *upper bounds* on (e.g) runtime. Saying that the runtime is 'at least (some upper bound)' is peculiar and confusing - you are saying an upper bound is really a lower bound.
> 1 votes

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


# Question
Title: Stroke Width Transform: Gradient Direction and Rays
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

Now, up to this point I got lost on the second paragraph of section 3.1 of the paper, which is getting a gradient direction and finding the other point for the ray: " *...then dp must be roughly perpendicular to the orientation of the stroke...* " and " *... dp(dq = -dp±π/6) ...* ". Does this mean I'll have to take a wild guess as to where the direction of dq is? or have I misinterpreted it?

# Answer
> 2 votes
You basically have to sample points from p in the direction of *p*'s gradient *dp*.
You get the *dp* from the x and y gradient maps. And sample from where? from the edge map and the gradient maps. First check if it is a edge from the edge map. If it is not then take another step in the dp direction. If it is an edge then compute the gradient direction from the x and y gradient map. If that gradient points back to *p* with about *π/6* of tolerance then that is the *q* you are looking for.

Be careful with back over while vs white over black. The gradients will point in opposites directions when you invert the image. That is why you have to run the algorithm twice since SWT does not know which case are we dealing with. One with the original gradient directions and another flipping the gradients in the opposite direction.

---
Tags: algorithms, image-processing, research
---


# Question
Title: Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?
I need to prove or disprove if these two languages are same. So I assume that these lanaguages are same because I think that every word from $\\{a,b\\}^\*$ could be concatenated from two words $x$ and $y$ where $|x|\_a = |y|\_b$. So $x$ and $y$ must belong to $\\{a,b\\}^\*$, too. Then I can write and prove this:

$\\{a,b\\}^\* \subseteq \\{xy \in \\{a,b\\}^\* \mid |x|\_a = |y|\_b \\} \wedge \\{xy \in \\{a,b\\}^\* \mid |x|\_a = |y|\_b \\} \subseteq \\{a,b\\}^\*$

So I assume that $z \in \\{a,b\\}^\*$. Then $z = z\_1z\_2...z\_i$ where $z\_1,z\_2,...,z\_i \in \\{a,b\\}$

Here I stucked and I don't know (1) how to continue, (2) if the way of proving i choose is correct or not.

# Answer
> 3 votes
You can prove this by induction on the length of the string.

The base case of $|z| = 0$ is obvious, we have to take $x=y=\varepsilon$.

The inductive assumption then is that $L =\\{xy \in \\{a,b\\}^{\ast}\mid |x|\_{a} = |y|\_{b}\\}$ contains all strings1 of length at most $n$.

Now we want to show that it contains all strings of length $n+1$.

Let $z \in \\{a,b\\}^{n+1}$ and let $z^{-1}$ be $z$ with the final symbol removed. By the inductive assumption $z^{-1} \in L$. The final symbol $z\_{n+1}$ in $z$ must be either an $a$ or a $b$.

1. If $z\_{n+1}$ is an $a$, then we can construct an appropriate $x\_{z}$ and $y\_{z}$ by taking $x\_{z} = x\_{z^{-1}}$ and $y\_{z} = y\_{z^{-1}}a$. Then $|x\_{z}|\_{a} = |x\_{z^{-1}}|\_{a} = |y\_{z^{-1}}|\_{b} = |y\_{z}|\_{b}$, and therefore $z\in L$.
2. If $z\_{n+1}$ is a $b$ we have a slightly more complicated situation, but it's not too difficult. The first symbol of $y\_{z^{-1}}$ must also be either an $a$ or a $b$, or $y = \varepsilon$.

* If the first symbol is an $a$, then we use the same $x$-$y$ partition as for $z^{-1}$, but we move the first symbol of $y$ to the end of $x$, and add the new $b$ to the end of $y$, then $|x\_{z}|\_{a} = |x\_{z^{-1}}|\_{a} + 1$ and $|y\_{z}|\_{b} = |y\_{z^{-1}}|\_{b} + 1$.
    * If the first symbol is a $b$, we do the same as in the $a$ case, but as we're adding a $b$ to $x$ and taking one $b$ away from $y$ but adding another at the end, the number of $a$s and $b$s in $x$ and $y$ don't change.
    * If $y\_{z^{-1}} = \varepsilon$, then we simply choose $x = z$ and $y = \varepsilon$ and again $|x\_{z}|\_{a} = |x\_{z^{-1}}|\_{a} = |y\_{z^{-1}}|\_{b} = |y\_{z}|\_{b}$ (in fact, they all equal $0$, so $z = b^{n+1}$).

Therefore in all cases $z \in L$, and we are done.

**Footnotes**

1. ...over alphabet $\Sigma = \\{a,b\\}$.

# Answer
> 4 votes
We want to show that every string $z\in \\{a,b\\}^\*$ is of the form $xy$ with $|x|\_a=|y|\_b$, as follows.

Make a graph of the value $|x|\_a - |y|\_b$ for every composition $x,y$ of $z = xy$, letting $x$ run over the prefixes of $z$. The value starts at $-|z|\_b$ for $x=\varepsilon$ and ends in $|z|\_a$ for $x=z$. Carefully argue it will be zero somewhere on the way.

---
Tags: formal-languages
---