# Question
Title: Connection between vertex cover and P=NP
I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.

In an undirected graph $G(V,E)$, vertex cover is a set of edges U so that every Edge in E has at least one end at U.

Defining the following function: $f(G,v)$ equals to the minimal vertex cover that v belongs to.

Why if it is possible to calculate in a polynomial time the function $g(G,v)$ and it is guaranteed that $f(G,v) -5 \leq g(G,v) \leq f(G,v) +5$ then P=NP?

(Meaning if we can estimate f in a constant boundary of +5 in a polynomial time, then P=NP?)

What i think:since vertex cover is an NP-COMPLETE language, and so is the minimal vertex cover, if it is bounded by +-5, a linear bound. then if known that $g(G,v)$ can be calculated in polynomial time and we can also show that it's boundaries are $f(G,v) - 5$ and $f(G,v)+5$, then P = NP.

So regarding minimal vertex cover, the problem is $min(f(x)| x \in vertexcover(G))$. so an algorithm for minvertexcover is: initialize {cover\<-0, Edges\<-0}; until there are no more edges $e \in E$ in G: 1)add u,v to cover; 2)add $e\_i$ to Edges; 3)remove u,v from G and adjacent edges.

Now, since $|Edges = 2 * cover|$, then for a possible solution, meaning vertex cover that covers all the edges, that possible solution will be more than Edges, so that possible solution will be bigger than 2 * Edges.

Since that possible solution $\geq 2 * Edges$, it means that the possible solution is $\geq f(G,v) + 5$, so it is bounded. now if we can calculate $g(G,v)$ in a polynomial time, it means we can calculate the possible solution in at least 2 * polynomial time, which is still polynomial. so it means that if $g(G,v)$ can be calculated in polynomial time, and the given +-5 boundary exists, then P=NP.

How to prove it correctly and efficiently? spent long days on it and would appreciate seeing how to do it correctly

# Answer
> 2 votes
I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time. We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, we can scale the graph such that $(f(G,v) + 5) / f(G, v)) \leq 1.36$, which results in $f(G, v) \geq 14$.

Furthermore, vertex cover is fixed parameter tractable in the solution size. In other words, we can compute whether $G$ admits a vertex cover of a fixed size in polynomial time. Hence, we apply the fixed parameter tractable algorithm up to $k = 13$. If no solution has been found, use $g$. We now have a polynomial time algorithm that can solve any set cover instance within a factor below 1.36 times the optimal solution, which is a contradiction unless P = NP.

Corollary: it is impossible to have a computable algorithm that outputs a vertex cover of size at most $OPT + c$, where $c \geq 0$ is a constant, in polynomial time, unless P = NP.

---
Tags: complexity-theory, turing-machines, computability, np-hard, vertex-cover
---


# Question
Title: There exists an algorithm to find grammar of complement of a function?
I'm wondering if there exists an algorithm to solve the following problem:

> Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar $S'$ such as $L(S) = L(S')^c $.

I note that the complement of a context-free language is also a context-free language, so the questions is well stated.

# Answer
> 6 votes
Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm.

Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^\*$. If you could compute the complement, then you could decide the latter using the algorithm for the former.

In contrast, deterministic context-free languages *are* closed under complement, and the proof of that fact likely identifies an algorithm that will work when you have a deterministic context-free language. Another way to handle it: convert to a deterministic pushdown automaton, then it is clear how to complement it.

# Answer
> 1 votes
Since you didn't explicitly specify that $S'$ should be a *context-free* grammar, I'll take the opportunity to mention Boolean grammars, which are a fairly modest extension of CFGs that allow conjunction and negation in rules, in addition to the implicit disjunction of CFGs. The productions have the form

> $$A \to \alpha\_1 \And \ldots \And \alpha\_m \And \lnot\beta\_1 \And \ldots \And \lnot\beta\_n$$ where $A$ is a nonterminal, $m+n \ge 1$ and $\alpha\_1$, ..., $\alpha\_m$, $\beta\_1, \ldots, \beta\_n$ are strings formed of symbols in $\Sigma$ and $N$. Informally, such a rule asserts that every string $w$ over $\Sigma$ that satisfies each of the syntactical conditions represented by $\alpha\_1$, ..., $\alpha\_m$ and none of the syntactical conditions represented by $\beta\_1$, ..., $\beta\_n$ therefore satisfies the condition defined by $A$.

Then if $G$ is a Boolean grammar (in particular, it could be a CFG) with start symbol $S$, add a new start symbol $S'$ and add the rule $S' \rightarrow \lnot S$ to obtain a grammar for $L(G)^c$.

Boolean grammars are a "modest" extension in that the deterministic time complexity of parsing is the same as for CFGs and they can be defined by language equations, but on the other hand they recognize a much larger class of languages. For example, even conjunctive grammars do not satisfy Parikh's theorem (i.e., the conjunctive grammars over an unary alphabet recognize non-regular languages). It is an open problem whether conjunctive grammars are closed under complementation.

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


# Question
Title: A linear time algorithm to find the array of indices of bigger numbers
Suppose you have an array `nums` of integers, unsorted, containing the values from 1 to n. You have a second array, call it `firstBigger`, initially empty, which you want to populate with integers such that `firstBigger[i]` contains j if j is the least index such that i \< j and `nums[j] > nums[i]`. A brute force search of `nums` runs in $O(n^2)$ time. I need to find a linear time search.

For example, if
`nums = [4,6,3,2,1,7, 5]` and we use 1-indexing, then
`firstBigger = [2,6,6,6,6,None,None]`.

---

I have considered first computing the array of differences in linear time. Certainly anywhere in the array of differences with a positive value, this indicates a place in `firstBigger` where it should store $i+1$. But I'm not seeing how to fill any other coordinates efficiently.

I might have gotten close when I started thinking of analyzing the array end-to-start. The last $n$th coordinate of `firstBigger` is going to be None, the $n-1$th has to be directly compared to the $n$th. As we proceed backward, if the number at $i$ is smaller than at $i+$1 we make this assignment. Otherwise we look up the first number bigger than the one at $i+1$. If that's still too small, again look up the first number bigger than that.

On average this does better than the naive algorithm, but in the worst case it's still $n^2$. I can't see any room to optimize this.

# Answer
Let $A$ be an array with indizes $1$ to $n$. We first build the array $B$ where $B\[i\] = j$ indicates that index $j$ has the highest value $A\[j\]$ in the first $i$ entries of $A$. Then we build a list $L$ which has the numbers from $B$ in the same order but without duplicates in it. Then we define the function $f$ as $f(i) = L\[i+1\]$ or none if $L\[i+1\]$ does not exist. The final result is applying $f$ to $B$.

Let's look again at your example $A = \[4,6,2,3,1,7,5\]$. Then $B = \[1,2,2,2,2,6,6\]$ and $L = \[1,2,6\]$. Hence the function $f$ is $1 \mapsto 2, 2 \mapsto 6, 6\mapsto \textrm{none}$. Applying $f$ to $B$ gives us $\[2,6,6,6,6,\textrm{none},\textrm{none}\]$.

Computing $B$ and $L$ runs clearly in linear time (for $L$ we only need to append values to a list at its end). Applying $f$ takes linear time too, if done correctly: Either you have an look up table as array of length $n$ (or hash map if you're ok with expected worst-case analysis). Or you use the monotonicity of $B$ and use the list $L$ which you traverse in lock-step when traversing $B$. This approach has the benefit that it uses less space in some instances and cache efficiency may be better since the relevant information is stored next to each other in consecutive order (worst case is still $n$).
> 1 votes

---
Tags: algorithms
---


title: What are HP and MP in this context?

text:
# Question
Title: What are HP and MP in this context?
From Kozen's Automata and Computability, 3ed, lecture 32 p. 328:

What are HP and MP in this context? I tried looking around and this text says:

How did the halting problem and membership problem become regular expression? I am so loss here.

# Answer
> 2 votes
Both HP and MP are *decision problems*, namely sets of *instances* that you can think of as descriptive strings. For example,

HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ eventually halts when started on input $x$,

and, similarly

MP is a collection of pairs $M, x$ as above and an instance of MP is in the set MP if the machine described by $M$ eventually halts in an accept state when started on input $x$.

---

In simple terms, HP is about programs and inputs and answers "Does this program halt on this input?" and MP answers "Does this program accept this input?"

The octothorpe (the # symbol) is just a separator so we know where $M$ ends and $x$ starts.

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


# Question
Title: Count number of pairs of elements whose product is a perfect square
Given two arrays whose elements lie between $\[1,10^5\]$ and the size of arrays is $\[1,10^5\]$, how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:

> Array 1: {1, 2, 4, 5}
>
> Array 2: {4, 8, 16, 125}
>
> Output : 6

The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $10^5$, an $n^2$ algorithm would be inefficient.

# Answer
There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a\_x,b\_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum\_x a\_x b\_x$.

There are many optimizations possible for this general scheme, which in practice can speed it up significantly. I'll let you work them out.
> 3 votes

# Answer
The numbers involved are small, which makes this quite trivial. The numbers are ≤ $10^5$. We have $10^5 \< 47^3$, and there are 14 primes \< 47.

So for each of the numbers x, y in X, Y, we calculate a 14 bit integer with bit #i set if x, y is divisible by an odd power of the i-th prime, and we also calculate x', y' which are x, y divided by the fourteen primes \< 47. The product of x, y is a square if and only if x, y produced the same bit vector, and x'y' is a square.

We split X, Y with x, y replaced by x', y' into up to 16,384 arrays where all the elements have the same bit vector. Let X', Y' be two such subarrays where all original numbers had the same bit vector, and all the numbers have been divided by the primes \< 47.

We first handle squares: If x', y' are both squares then the product is a square. If only one of them is a square then the product is not a square. Let X' contain n squares and Y' contain m squares, then we have nm square products, and remove the squares from X', Y'.

Now the elements of X' are all less than $10^5$, all have no prime factors \< 47, and none are squares. The smallest number with three prime factors ≥ 47 is $47^3 \< 10^5$, therefore each x', y' is either prime or the product of two primes. The product of two such numbers is a square if and only if they are the same, that is x' = y'. We therefore easily find the squares after sorting each array. We need to be a bit careful because each array can contain the same number twice.

All in all, this takes O (n log n) steps, where n is the size of the larger array. If the numbers were less than $10^{15}$ then we'd want to divide them by all primes \< 100,000 which would still be O (n log n) but with a much larger constant.
> 0 votes

---
Tags: algorithms, dynamic-programming, combinatorics, linear-algebra
---


# Question
Title: CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$
Given the language:

> $$ L=\\{ \omega \in \\{ a,b,c,d \\}^\* : |\omega|\_a = |\omega|\_b \\} $$

I propose the following grammar: $$ \begin{align\*} S &\to \varepsilon \mid aSbS \mid bSaS \\ S &\to cS \mid dS \mid Sc \mid Sd \end{align\*} $$

I want to know if this is correct or if there exists a smarter grammar (a shorter grammar).

# Answer
> 2 votes
I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules

$$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$

Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions.

1. Does $S$ only generate strings within $L$?
2. Can every string in $L$ be generated by $S$?

If the answer to these questions is both yes, then a string is in $L$ if and only if it is generated by $S$, which means that $S$ is a correct grammar for the language.

The answer to 1. is clearly yes because every string generated by $S$ must have the same number of $a$'s as it does $b$'s because in every rule where an $a$ is present a $b$ is also present, and vise versa.

The answer to number 2 is a bit trickier. We will use induction on $|\omega|\_a = |\omega|\_b$ to show that any string in $L$ can be generated by $S$

(Base case $n=0$) If $|\omega|\_a = |\omega|\_b = 0$, then $\omega$ consists of a sequence of $c$'s and $d$'s, and can be generated by scanning over it using the rules

$$S \rightarrow cS \hspace{10px} | \hspace{10px} dS$$

until we terminate with $S \rightarrow \epsilon$.

($n$ implies $n+1$) Assume by induction that for all $\omega \in L$ with $|\omega|\_a = |\omega|\_b \leq n$ that $\omega$ can be generated by $S$. Now let $\omega' \in L$ be such that $|\omega'|\_a = |\omega'|\_b = n+1$.

At some point in $\omega'$ there must be at least one time that an $a$ comes before a $b$ (with only $c$'s and $d$'s between them) or a $b$ comes before an $a$ (with only $c$'s and $d$'s between them). Without loss of generality, we can assume there is an $a$ that comes before a $b$.

Now, we can decompose $\omega' = XaYbZ$ where $|X|\_a + |Z|\_a = |XZ|\_a = n$ (and the same for $b$) and $Y \in \\{c,d\\}^\*$ . This holds because we are taking one $a$ and one $b$ from $\omega'$ which had $n+1$ of each which leaves $n$ in the rest of the string, and we know that there is a pair of $a$ and $b$ with just $c$ and $d$ between.

Now we can get a little clever and observe that the string $XcZ \in L$ and $|XcZ|\_a = |XcZ|\_b = n$ and therefore, by the inductive hypothesis, $XcZ$ can be generated by $S$.

Now here's the tricky part. Consider the process that generated $XcZ$. At some point in the generation, we must have used the rule $S \rightarrow cS$ to generate the $c$ between $X$ and $Z$. If we instead chose to use

$$S \rightarrow aS^\*bS$$

as the expansion where $S^\*$ generates $Y$ as in the case where $n = 0$, and did everything else exactly the same, then what happens is we replace the $c$ in $XcZ$ with $aYb$, and get the string $XaYbZ$. This demonstrates that $\omega'$ can be generated by $L$ because we have just found a process by which it can be generated by $S$.

Therefore by induction on $|\omega|\_a = |\omega|\_b$ every string in $L$ can be generated by $S$.

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


title: Analysis of dependent double for

text:
# Question
Title: Analysis of dependent double for
Here is the algorithm:

```
int sum = 0
for (int i = 2N; i > 0; i = i / 4) {
  for (int j = 0; j < i; j+=2) {
    sum++
  }
}

```

I figured this would be linearithmic, but it's just linear. I would appreciate seeing a formalized summation and not a qualitative explanation. I have tried doing this but I fail to get linear runtime.

# Answer
The number of iterations is: $$T = \frac{2N}{2} + \frac{2N}{2 * 4} + \cdots + 1$$

The number of elements in the above formula is $\log\_4(2N)$. After simplification, we will have:

$$T = N(1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log\_4(N)}}) = \Theta(N)$$

As $1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log\_4(N)}} \< 2$ is a geometric series with step of $\frac{1}{4}$ in asymptotic sense.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Which inductive schemes can encode the following Agda definition?
Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to encode the following Agda definition

```
  data A : Set where
    a : Maybe (List A) → A

```

I can think of some tricks to reformulate `List` in this definition so that induction-recursion becomes applicable, but are there any schemes that would allow me to first say what a list is and then refer to this information to say what `A` is the way it's done in Agda?

**Edit**: As follows from András Kovács's answer, this *particular* definition can be reformulated as an inductive family. Here is how to do it:

```
data Three : Set where one two three : Three

data AG : Three → Set where
  a'       : AG three → AG one
  nil'     : AG two
  cons'    : AG one → AG two → AG two
  nothing' : AG three
  just'    : AG two → AG three

A = AG one
ListA = AG two
MaybeListA = AG three

a : MaybeListA → A
a = a'

nil : ListA
nil = nil'

cons : A → ListA → ListA
cons = cons'

nothing : MaybeListA
nothing = nothing'

just : ListA → MaybeListA
just = just'

```

# Answer
> 4 votes
No scheme that I know of directly encodes that type. Sometimes it's called a "nested" inductive definition. The complication here is that `Maybe` and `List` are type constructors which are external to the signature, and we have to formalize strict positivity for external type operators in general, if we want to allow such definitions.

In other words, the consistency of `A` depends on the definition on `Maybe` and `List`. Some external type operators are not positive, as in:

```
data Neg (A : Set) : Set where
  neg : (A -> Bool) -> Neg A

data B : Set where
  b : Neg B -> B

```

Agda does look into all the external definitions and tries to determine the variance of type parameters. While I don't know a reference for a direct formal specification of this, an easy way to reformulate nested definitions as non-nested is to include the external type operators into a mutual inductive signature. For example:

```
data A : Set
data ListA : Set
data MaybeListA : Set

data A where
  a : MaybeListA -> A

data ListA where
  nil : ListA
  cons : A -> ListA -> ListA

data MaybeListA where
  nothing : MaybeListA
  just : ListA -> MaybeListA

```

This is an ordinary mutual inductive type, which is covered (modulo cosmetic details) by Dybjer's inductive families.

---
Tags: induction, agda
---


# Question
Title: Why do we use big O rather than $\Omega$ when discussing best case runtime?
When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ of an algorithm, we also attempt to bound $T(n)$ above and use $O$ notation.

Why don't we instead attempt to bound the best case runtime from below? Wouldn't it make more sense to put an upper bound on the worst case runtime and a lower bound on the best case runtime, as this will then give us upper and lower bounds on all cases?

I understand that both $O$ and $\Omega$ notations can be useful for discussing best/worst/average case runtime., and that we can put upper and lower bounds on the worst or best case runtimes, respectively. My question is about the convention in the field to list an upper bound rather than a lower bound for the best case runtime (for example, see here and here).

# Answer
> 7 votes
The symbols $O$, $\Omega$ and $\Theta$ mean *at most*, *at least* and *exactly*, respectively. What these bounds are *about*, is an entirely separate issue. They can be about best-case or worst-case performance, but you can use these symbols throughout mathematics. To describe a function, one of the things you can do is to give $O$ and $\Omega$ upper and lower bounds, independent of whether your function is related to computer science.

For example, to describe an complicated algorithm (or language) for which you don't have precise bounds yet, but for which you do have rough preliminary bounds, you can say: the best-case of this algorithm runs in $\Omega(n^2)$ and $O(n^3)$ (meaning no better than $n^2$ but no worse than $n^3$) and the worst-case runs in $\Omega(2^{\sqrt{n}})$ and $O(2^{n^{2}})$. This means: I don't know what the worst-case running time is exactly, but my analysis thus far puts it between $2^{\sqrt{n}}$ and $2^{n^{2}}$. Later, it may turn out that the worst-case running time was in fact $\Theta(2^{n})$, and then your $O(2^{n^{2}})$ upper bound, while correct, was not strict.

# Answer
> 5 votes
$O$ upper bounds how quickly a function grows, while $\Omega$ lower bounds how quickly a function grows. This a completely separate issue from whether one's considering worst/average/best case runtime analysis, although this distinction causes confusion. Usually we care most about upper bounding the runtime of an algorithm, which is why you'll likely see $O$ bounds most often regardless of which notion of runtime is being considered.

# Answer
> 0 votes
It is usually easier to get some sort of upper bound (i.e., $O(g(n))$); lower bounds (like $\Omega(g(n))$) don't say much, you want to have an idea of "how long could it take", an answer like "it definitely takes more than" isn't very useful. Useful (but often hard to get) is $\Theta(g(n))$ (upper *and* lower bound). Besides, some functions just can't be reduced to a simple $\Theta(g(n))$. Consider for example:

$\begin{equation\*} f(n) = \begin{cases} n^3 & \text{if \\(n\\) is odd} \\ n & \text{if \\(n\\) is even} \end{cases} \end{equation\*}$

We have $f(n) = \Omega(n)$ and $f(n) = O(n^3)$, and there is no $\alpha$ so that $f(n) = \Theta(n^\alpha)$. We implicitly require our $g(n)$ monotonic increasing, and that won't work here for $\Theta$.

Note that Sedgewick advocates using $\sim$ when possible:

$\begin{equation\*} f(n) \sim g(n) \text{ if and only if } \lim\_{n \to \infty} \frac{g(n)}{f(n)} = 1 \end{equation\*}$

This gives maximal information. But is harder.

# Answer
> -1 votes
Big O is used mostly because we want to make sure that the best case time complexity $T(n)$ will never exceed the upper bound time complexity $Cg(n)$. It would be meaningless to talk about big $\Omega$ notation because what we want is a upper bound on $T(n)$.

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


title: Average Case Complexity Rivisted

text:
# Question
Title: Average Case Complexity Rivisted
I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem:

> Suppose we have a 5 elements array to be sorted using Insertion sort. Time complexity will depend upon the particular arrangements of elements in the array. Usually, when algorithm's time complexity depends upon the particular ordering of elements or different instances of same problem size n, then different cases (i.e. best, average and worst) occurs. In the above example there are 5!=120 possible instances of problem size 5. For a instance, when elements are already sorted, algorithms takes lowest time, and that will be best case. For another instance, when elements are reverse sorted, it takes longest time, and that will be worst case. there are still 118 instances left. For average case time complexity, we should take average of running times for all possible input instances (including 118 left and 2 others). That means we should take average of all 120 running time for different 120 instances.

Why probability distribution plays a role while computing average case time complexity? Why don't we just take a simple average of running times for all possible input instances of same problem size?

# Answer
If the distribution on input instances is uniform, then the two are equivalent. Talking about a distribution has two potential advantages: (1) it allows us to analyze the algorithm using the tools of probability theory, which can sometimes be useful, (2) it allows us to meaningfully talk about average-case running time for a non-uniform distribution on inputs.
> 1 votes

# Answer
Getting detailed data for *one* instance is hard, getting them for *each* possible instance of size $n$ is worse, and then you have to average... assuming you do know the distribution of the input data in sufficient detail.

Take the well-plodded case of sorting. How would you characterize the distribution of the $n!$ possible permutations of $n$ elements (assuming they are all different!) real people throw at your program? It is said \[citation needed\] that "somewhat sorted" data are quite common. Presumably meaning starting with a large collection of sorted data and "append a bunch of unsorted data at the end", maybe "change a random selection of data in some way", or perhaps "add a (smallish) random value to each element", or a lot of other reasonable models depending on the case. A dictionary presumably works in the first way, a list of prices the second or third. OK, selected one, what exactly are the parameters of your distribution? It'll depend on the application. So you have your distribution, just setting up the equations to compute the average for size $n$ is a daunting task, let alone solve them.

For a glimpse of the difficulties involved, the (very simple!) Shell sort routine has defied exact analysis except for limited cases, precisely because it scrambles data so that the second, third and following passes get "somewhat sorted" data to work on.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, average-case
---


# Question
Title: Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition
Given a set of positive integers :

$ \\ D = \\{ D\_1, D\_2, ..., D\_n\\}$

and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find a set of non-negative integers:

$C = \\{ C\_1, C\_2,..., C\_n\\}$

such that

$S \> P $

where
$S = \displaystyle \sum\_{i = 1}^nC\_iD\_i$
and for all $i$ where $C\_i \> 0 $,

$\ S - D\_i \< P$

There can be multiple solutions, any solution can suffice.

For example, if

$D = \\{2, 6, 9 \\}$
$P = 18$

$ C $ can be:

$C = \\{0, 2, 1 \\}$

since $ S = 0\*2 + 2\*6 + 1\*9 = 21 \> 18 $
and $ 21 - 6 = 15 \< 18 $ and $ 21 - 9 = 12 \< 18 $

What can be some approaches to tackle this? For starters, is there a way to ensure that there even exists a solution? There can be examples where there is no solution.

# Answer
> 1 votes
If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$. Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D\_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order. In that case you have just:

$\begin{equation\*} P = c \cdot \prod\_{1 \le k \le n} D\_k \end{equation\*}$

For the Frobenius problem sums like $S$ with non-negative $C\_i$ can represent all numbers greater than a function $g(D)$, and it can be shown that $g(D) \< D\_n^2$ (computing the exact value of $g(D)$ is NP-complete). So, if $P \> D\_n^2$ (the other $D\_k$ would have to be small indeed for this to be false), any number $S \ge P$ can be represented, and also any number $S - D\_i$, pick say $S = P + 1$ to satisfy your condition.

To get a set of $C\_i$, you can now use the greedy algorithm: Take $C\_n = \lfloor S / D\_n \rfloor$ (as large as possible), $S \leftarrow S - C\_n D\_n$, and repeat for the next largest.

---
Tags: algorithms, algorithm-analysis, sets, number-theory, linear-algebra
---


# Question
Title: Being stuck and frustrated with my masters project
I'm doing a masters in CS that requires me to implement from scratch most of the neural network models and because python libraries aren't applicable to what i want.

The problem is that i don't feel capable of implementing those from scratch. Even the MLP seems very difficult, i always try but get stuck and restart. Meantime, i feel that my supervisor think it's a natural thing and i shouldn't have problems implementing those algorithms.

I know that when we are talking about research, it shouldn't be easy - because anyone else would do it if so - but i'd be glad to receive some advices about this process i am going through: **Am I not prepared enough for this or is it an overambitious idea to implement all these networks from scratch? Should i continue this? I've already thought about giving up.**

Ps: any good materials (books, videos, etc) focusing in implementation of neural networks are welcome.

# Answer
I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project.

So forget your computer for now. Bring a bunch of white papers and a pen. Describe the steps of the algorithm precisely. Design the program, decide the data structures and how they will communicate. Decide where data should be kept and how it should be commuted. When you have the details drawn on papers, coding is just a matter of writing it down and doing some optimization.

Another good advise is to start by writing the simplest version you can imagine. Implement only what you need to have, in the simplest way you can think of. No optimization, no copy/reference calls thinking just get it to run correctly at first. Once you are at that point you have something to deliver, start making it better. Check where you are doing stuff naively where you can do it better. Find all copies where you could have just done it on the original structure. Because if you kept optimizing and adding features while implementing you will never finish. There will always be something to add.
> 5 votes

# Answer
(Not enough reputation to comment, so writing here.)

1. Unless your algorithms are secret, please post your algorithms here. Maybe someone (not me though) can find a library for you. Maybe someone can tell how long does it take to implement it.
2. Use Git and GitHub. You can rollback bad code with this.
3. Always write tests. This helps against regressions as you update/optimize your algorithm. Moreover, code without testing are almost certainly broken.
> 2 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, neural-networks, mathematical-programming
---


# Question
Title: Why N-Queens Problem is not used as experiment in CSP thesis?
I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems.

If so,when I do master thesis in CSP,it is reasonable to experiment algorithms with N-Queens.

How can N-Queens problem be changed CSP parameters like Tightness,Constraint Density to experiment?

I wonder why many researchers test their CSP algorithms with Zebra problem, sudoku ,random CSP but why not N-Queens problem? Is N-Queens problem with CSP does not give better results?

# Answer
> 1 votes
n-queens problem can be solved quite efficiently with a very simple algorithm (finding *all* solutions takes ages, because the number grows exponentially).

Getting anywhere near that efficiency with a general method is impossible.

---
Tags: algorithm-analysis, constraint-satisfaction, constraint-programming, backtracking
---


# Question
Title: Name for sorting algorithm "while not sorted, swap the FIRST unordered pair"
A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass.

For a toy problem, we have a variant that just performs the first available swap in each iteration and repeats until sorted. It does not continue from the position of the last swap.

Is there a standard name for this sort? It seems so trivial that it must have a name, but we were surprised not to find it on any obvious lists. It's just like, a raw comparison sort.

## Bubble

```
4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
3, 2, 1, 4 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

```

## Variant

```
4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
2, 3, 4, 1 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

```

**Don't worry, this is not meant to be a good sorting algorithm, just for a fun thing.**

# Answer
> 2 votes
In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list is sorted. (Note the two items in the leftmost inversion must be adjacent).

There is no standard or popular name for this variant of bubble sort, or so I believe.

I would call it **left-bubble sort**, a name that captures its conceptual intention. We could also have **right-bubble sort**, which swaps the items in the rightmost inversion repeatedly until sorted. We could also have **random-bubble sort**, which swaps two randomly-selected adjacent items that are in the wrong order repeatedly until sorted. If we do not even require the two items to be adjacent, we can have **random-swap sort**. Depending on how the inversion is selected randomly, "random-swap sort" can become bogo-sortopt, bozo-sortopt, and bozo-sort+opt that appear in this article.

The above description of left-bubble sort does not specify how to find the leftmost inversion in each iteration. A naive implementation may always comparing the first two items, then the next two items and so on until it finds the first inversion or stops. We can observe that the initial part of the list during the left-bubble sort is sorted. Since there cannot be any inversion in the initial part of the list, we can optimize the implementation by just comparing the item that was just moved to the left with the item right before it without comparing the initial adjacent items.

Whether we use the naive implementation or the optimized implementation above, left-bubble sort behaves exactly the same as the simplest insertion sort, in terms of the states the given list goes through until sorted. The simplest insert sort here corresponds to the first pseudocode at this Wikipedia page, which is implemented in *Programming Pearls* (2000) by Jon Bentley.

Here is an illustration of the states produced by left-bubble sort.

```
4, 3, 2, 1    <- 4 is considered inserted into the expected place.
3, 4, 2, 1    <- 3 is inserted into the expected place
3, 2, 4, 1
2, 3, 4, 1    <- 2 is inserted into the expected place
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4    <- 1 is inserted into the expected place

```

In particular, left-bubble sort builds the final sorted array (or list) one item at a time, which is the defining characteristic of "insertion sort" according to that Wikipedia page. We can thus treat (the optimized version of) left-bubble sort as another name for the simplest insertion sort.

---
Tags: terminology, sorting
---


# Question
Title: How to create a LR(k) grammar for an arbitrary k
Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?

# Answer
Here's one pattern for an LR(k) grammar which is not LR(k-1). I didn't fill in the definition of $A$; there's nothing particularly special about it. It might have an empty right-hand side, or it might match any LR(k) subgrammar. $a^k$ represents $k$ instances of $a$.

$$ \begin{align}S&\to B a^{k-1} b\\ S&\to C a^{k-1} c\\ B&\to A\\ C&\to A\\ A&\to \text{see above} \end{align} $$

Clearly, it is not possible to determine whether $A$ should be reduced to $B$ or to $C$ without knowing what the $k$ following token is. So the grammar is not LR(i) for any $i \lt k$. The reduction can be determined using $k$ lookahead tokens, so the grammar is LR(k) provided that $A$ is.
> 1 votes

---
Tags: context-free, parsers, lr-k
---


# Question
Title: Implementing Dynamic Programming Solutions
I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion. My confusion comes from implementation. Here is a specific question. Every question I look at builds its grid differently, for example, 0,1 knapsack you go back down the row and up one. For coin changing its just back down the row. For Fibonacci and stair steps its the sum of the last two. If I am tasked with a Dynamic Programming problem is there any kind of base approach I can take to building out my grid?

# Answer
> 1 votes
One easy way to do dynamic programming is memoization -- just do the regular recursion, but store any results computed and reuse them if the same (sub)problem shows up. Recursion is at the very hearth of dynamic programming, what is usually programmed is a careful unrolling of the recursion.

---
Tags: dynamic-programming
---


# Question
Title: Solve recurrence with Master Theorem - Polynomially Smaller/Larger
The problem is to solve the recurrence using Master Theorem :

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

**My attempt:** $$ a=2, b=2, f(n)= \log\_2 {n}, g(n)=n^{\log\_b{a}}=n $$ I am torn between case 1 & the Master Theorem not applying. I notice that $\log\_2{n}$ cannot be written as a polynomial, but the ratio of $f/g = \log\_2{n}/n$, which has an $n$ term in it. And $f$ clearly is less than $g$. So, does case 1 apply or not? I have found very mixed results online, and, ultimately, I am unclear of if in this case it is considered polynomially smaller and what that constitutes in general. (see definition on this from book below)

The version of the Master Theorem we use is as follows:

Our book also notes that in the first case not only must $f$ be smaller than $n^{\log\_b{a}}$, it must *polynomially smaller*, that is, $f$ must be asymptotically smaller than $n^{\log\_b{a}}$ by a factor of $n^\varepsilon$ for some constant $\varepsilon\>0$. Similarly, in the third case, not only must $f$ be larger than $n^{\log\_b{a}}$, it must *polynomially larger*.

# Answer
Apply the definition. Does there exists $\epsilon\>0$ such that $f(n) = O(n^{1-\epsilon})$? If yes, then case 1 applies (just see the text that you included in the question). If no, then case 1 does not apply.

For instance, ask yourself: if $\epsilon=0.1$, does $f(n)=O(n^{1-\epsilon})$? i.e., does $\log n=O(n^9)$? You should be able to take it from here.
> 1 votes

---
Tags: time-complexity, asymptotics, master-theorem
---


# Question
Title: Is there a name for the class of algorithms that are the most efficient for a particular task?
This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.

We would therefore have to be able to show that any other algorithm is at best of the same order of complexity as the algorithm in question.

I'm asking because I'm working on a paper that makes use of this concept, and I was surprised when I realized that I'm not aware of any name for this concept, though I'll concede I'm risking embarrassment if there is such a name that I'm simply unaware of.

# Answer
You can say that an algorithm is asymptotically optimal in such a case.

In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.
> 34 votes

# Answer
I've seen this concept explained as Solomonoff induction, a formalization of Occam's razor.

Given some set of Turing machines that fit the data, the one with the lowest complexity is likely to be the one that truly models it.
> 2 votes

---
Tags: algorithms, time-complexity, terminology
---


title: Triple nested loop complexity

text:
# Question
Title: Triple nested loop complexity
I'm trying to determine the complexity of the following structure:

for (i = 1; i \< n; i++)

for (j = 1; j \< o; j++)

for (k = 1; k \< p; k++)

```
print "Hello world!"

```

Normally, for a triple loop like this, I believe the complexity is O(n^3), but the undefined variables "o" and "p" are throwing a wrench in the works. I've done some hunting around, and the best I can surmise is that it might be O(n * o * p), depending on what values are assigned to n, o and p. Thanks for taking a look!

# Answer
> 1 votes
$O(nop)$ is indeed exactly the best upper bound one can conclude for this program without additional information. The bound $O(n^3)$ cannot be shown unless you know $o$ and $p$ are themselves $O(n)$. On the other hand, if you knew $o$ and $p$ were actually constants, then you could prove a bound of $O(n)$ for the entire program.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Finding the count of 0's bounded by all 1's
Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( **This is not any online platform question** ) (**This problem statement I faced during an interview**).

**Sub-matrix or matrix which is forming the square or rectangular boundary should only contain 1 in it and 0's should inside that boundary.**

**Please refer examples for better understanding**

Example:

Input : Row : 3 , Col : 3

1 1 1

1 0 1

1 1 1

Output : 1

Explanation : In above case only 3\*3 matrix which have all 1's at there boundary and 1 zero enclosed within that.

Input : Row: 2 Col: 2

1 1

1 1

Output : 0

Input : Row: 4 Col: 4

1 0 1 0

1 1 1 0

1 0 1 1

1 1 1 1

Output : 1

Explanation : 0 based indexing i.e. sub-matrix (1,0) to (3 , 2 ) only sub-matrix which have 0 enclosed by all 1's. That's why output is 1.

Input : Row : 4 Col : 5

1 1 1 0 1

1 0 1 1 1

1 1 1 0 1

0 0 1 1 1

Output : 2

Explanation : Here sub-matrix ( 0 based indexing )

1. (0,0) to (2,2) has one(1) 0 enclosed.
2. (1,2) to (3,4) has one(1) 0 enclosed in it Therefore total count become 2.

Input : Row : 4 Col : 4

1 1 1 1

1 0 0 1

1 0 0 1

1 1 1 1

Output : 4

Explanation : Here matrix (0,0) to (3,3) contains **four** 0's enclosed within the 1's boundary. Therefore count is 4.

I have tried to solve this question but not able to think about the optimized solution.

My Algorithm ( Brute Force Algorithm ):

1. Generating the all the Sub-Matrix of a given matrix
2. Checking whether given sub-matrix satisfies my given condition or not.
3. Increment the counter repeat 1 to 3.

Could anyone please help me out to think about more optimized approach to solve the above question ?

# Answer
Form a grid graph, with one vertex per cell. Add an edge between each pair of adjacent cells that contain a 0. Add one more start vertex, with an edge from it to every cell on the perimeter that contains a 0. Find all cells reachable from the start vertex (using DFS or BFS), and remove them. Then, count the number of remaining cells containing a 0.
> 0 votes

---
Tags: algorithms, data-structures, optimization, mathematical-analysis, matrix
---


# Question
Title: How are "Problem Complexity" and "Solution Complexity" different?
I am in an algorithms course, and my professor keeps specifying "we are talking about *Problem* complexity here, not *Solution* complexity". I would like to gain an intuitive understanding of the difference between these two. Do you all have an example(s) that can help me to understand?

# Answer
Problem complexity is the best we can achieve for a given problem (sometimes under given restrictions). We usually talk about problem complexity when dealing with lower-bounds and it means there is probably no algorithm with lower time/place complexity than the proved ones.

Algorithm complexity is on the other hand the resources needed for a specific algorithm to run. When some algorithm solves a given problem in time $t$, we know that this problem has at most time complexity $t$ and hence, the complexity of an algorithm is an upper-bound for the complexity of the problem it solves.
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Grammar for the following language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$$ N^{+}$ $\land$ m + k $\geq$ n}
I'm trying to create a grammar (having the highest type) for the language:

L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$ $N^{+}$ $\land$ m +k $\geq$ n}

I'm not finding any good approach for it. Hints or ideas?

Thanks!

# Answer
Try to think of the CFG for $a^kb^k$, and for $b^mc^m$, and then make a grammar for the language $$ L' = \\{ a^kb^nc^m : m,n,k \in N^+ \wedge m+k=n\\}. $$ After that, think of how you can change it to be a grammar for $L$.
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: Does left factoring CFG make it unambiguous?
I came across following problem:

> If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE?

I have many thoughts about this. But I feel they are somewhat contradicting and hence form a bigger doubt. May be I lack some understanding.

**Thought 1**

Ambiguity has nothing to do with determinism (even if grammar does not have productions with same prefix of their right side, they still can have a string with two parse trees). So CFG is still ambiguous after left refactoring. Hence, the sentence should be false.

**Thought 2**

Left factoring is used to eliminate common prefixes of right hand side of productions in the grammar. Doesnt that make grammar deterministic? Deterministic grammar derive deterministic context free languages. So isnt turning grammar deterministic makes it unambiguous? If yes, given statement should be true.

**Thought 3**

I have completely ignored left recursion in thought 1 and 2. Is it ok?

**Doubt:** I feel thought 1 and thought 2 are contradicting. And I am not able to figure it out which one is correct. Which of the above thoughts are incorrect and why? Am I missing any more subtleties?

# Answer
> 2 votes
The answer is *no*. Some context-free languages are inherently ambiguous: *every* context-free grammar defining a language of this kind will be ambiguous. An example is

$$\\{a^ib^jc^k \mid i = j \text{ or } j = k\\}$$

# Answer
> 0 votes
Left factoring does not significantly change the derivations produced by a grammar. It introduces new non-terminals, which adds steps to the derivations, but the original derivation is still present.

So if the grammar were ambiguous before, it is still ambiguous afterwards. Recall that an ambiguous grammar has more than one leftmost derivation for the sane sentence; after left-factoring, this will still be the case.)

Left-factoring is necessary to produce a top-down parser, but that is because top-down parsing requires a stronger condition than non-determinism. (Informally, a top-down parser must decide which alternative to pursue before it starts to explore that alternative, while a deterministic parser only requires that the decision can be made within a bounded time after the alternative is complete.)

---
Tags: formal-languages, automata, context-free, formal-grammars, pushdown-automata
---


# Question
Title: Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$
The language is defined as $$L = \\{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do first. I have made an automaton that keeps track of $\mod 5$, what next?

# Answer
Use nondeterminism to guess the remainder of $nm \div 5$ and then check that this is also the remainder of $q \div 5$.
> 0 votes

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


# Question
Title: Calculate boolean matrix multiplication (BMM) using transitive closure
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \\{ V, E \\}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two matrices $X$ and $Y$?

I know that in order to calculate the transitive closure of a matrix $I$ need to compute $I^{(V-1)}$. But what else?

# Answer
Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \\{u\_1, \dots u\_n\\}$ and similarly $V := \\{v\_1, \dots v\_n\\}$ and $W := \\{w\_1, \dots w\_n\\}$. Define $E$ as follows: For $i, j \in \[n\]$, we add $(u\_i, v\_j)$ to $E$ for $u\_i \in U$ and $v\_j \in V$, if and only if $X\_{ij} = 1$. Similarly we add $(v\_i, w\_j)$ to $E$ for $v\_i \in V$ and $w\_j \in W$ if and only if $Y\_{ij} = 1$.

Let $G^T := (S, E')$ be the transitive closure of $G$. This means $(x, y) \in E'$ if and only if there is a path from $x$ to $y$ in $G$.

**Claim.** Let $Z := X \cdot Y$ be the matrix resulting from the multiplication. We claim that $Z\_{ij} = 1$ if and only if $(u\_i, w\_j) \in E'$.

Proof. $Z\_{ij} = 1$ if and only if $\bigvee\limits\_{k=1}^nX\_{ik}\land Y\_{kj}$ if and only if there is a $k\in \[n\]$ such that $X\_{ik} = 1$ and $Y\_{kj} = 1$ which is the case if and only if there is a $k\in \[n\]$ such that $(u\_i, v\_k) \in E$ and $(v\_k, w\_j) \in E$ which is the case if and only if$^{(\*)}$ there is a path in $G$ from $u\_i$ to $w\_j$ and hence $(u\_i, w\_j) \in E'$.

Try to prove $(\*)$ as an exercise. Hint: for the harder direction use the fact that the graph is directed.
> 1 votes

---
Tags: algorithms, graphs, matrix, adjacency-matrix, matrix-multiplication
---


# Question
Title: How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.

Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s odd 1’s, even 0’s odd 1’s, odd 1’s, even 0’s – and combine them ...

But I can't understand how it works

Who can help?

# Answer
Let us define 4 non-terminals $X\_{00}, X\_{01}, X\_{10}, X\_{11}$ and the start variable $S$. The rules are as follow: \begin{align} S &\rightarrow X\_{00},\\ X\_{01}&\rightarrow \epsilon,\\ X\_{00}&\rightarrow 0X\_{10},\\ X\_{00}&\rightarrow 1X\_{10},\\ X\_{01}&\rightarrow 0X\_{11},\\ X\_{01}&\rightarrow 1X\_{00},\\ X\_{10}&\rightarrow 0X\_{00},\\ X\_{10}&\rightarrow 1X\_{11},\\ X\_{11}&\rightarrow 0X\_{01},\\ X\_{11}&\rightarrow 1X\_{10},\\ \end{align} where the first index tells the parity of the number of zeros and the second one the parity of the count of ones.

Try to prove the correctness as an exercise.
> 2 votes

---
Tags: complexity-theory, formal-languages, context-free, formal-grammars
---


# Question
Title: Why do we not use CFGs to describe the structure of lexical tokens?
This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff.

Here is my current answer:

*CFGs describe how non-terminal symbols are converted into terminal symbols via a parser. However, a scanner defines what those terminal symbols convert to in terms of lexical tokens. CFGs are grammatical descriptions of a language instead of simply defining what tokens should be scanned from an input string.*

**What is the correct way to answer this?**

# Answer
> 4 votes
You don't use CFGs because typically lexical analysis can be performed using regular automata, and these are faster than context-free parsers. It's a question of efficiency.

# Answer
> 0 votes
Regular expressions are recognized by finite state machines, while context free grammar recognized by push-down automata. Push-down automata is not efficient as FSM in terms of time, hence it's all about efficiency.

# Answer
> 0 votes
Several angles here.

* The distinction between "token" and "syntax" is somewhat arbitrary. Both can (and have been) described by CFGs.
* One reason for the split is that we read e.g. a C program in terms of tokens (variable names, operators, reserved words, comments), not in term of characters. So it makes sense for the compiler writer to do what comes naturally.
* A significant time of any compiler is reading and grouping characters into tokens, it makes sense to make this as fast as possible. The technology to handle regular expression matching is mature. Much character detail can just be discarded without much analysis (spaces, comments).
* "Most" languages have the same (general) idea what the basic building blocks (names, operators, even comments) look like. It makes sense to package that and free the compiler writer of a task that way (less code, less bugs...). Several parsing tools offer this prepackaged.
* Parsing is complex, it's speed depends on number of symbols handled. Grouping into tokens gives less stuff to parse, thus betrer performance.

---
Tags: context-free, formal-grammars, regular-expressions, lexical-analysis
---


# Question
Title: Best and Worst options in Gale Shapley algorithm for an agent
Please consider the figure below. I have to find the best and worst options for W. From the preference list of W, the best option for W is D but there is no matching of W with D in all the 6 options. Thus option 1 is the best option in the context of W because A is the second preferred element of W.

Now C is the worse preferred option of W. Thus option 5 & 6 are the worse options of W. X (worst : 4, Best:2) Y (Worst : 6, Best:2) Z (Worst: 6, Best: 1,2 &3)

Somebody please guide me.

Zulfi.

# Answer
Gale-Shapley can run two (symmetric) ways: Men propose to women (men get their most desirable mate in any stable matching) or the other way around.
> 0 votes

---
Tags: matching
---


# Question
Title: How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation?
Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?

# Answer
A famous example: a PCRE that finds primes. I couldn’t find Abigail’s original, but there have been many iterations on this.

In JavaScript, for example, you can pass a function to the matcher to do arbitrary computation with the results.
> 2 votes

# Answer
Here is a specific example, POSIX EREs (Extended Regular Expressions).

POSIX EREs have, on top of the computer science definition, back-references for the first 9 capturing groups. This gives some extended properties, like being able to match the $a^nba^nba^n$ via the regex `\(a*\)b\1b\1`, which cannot be matched by any context-free grammars.

However, POSIX EREs cannot match $a^nb^n$ despite this language being context-free.

Thus to answer your question, "or is there an intermediate (between finite automata and CFGs) set of languages that it covers?", POSIX EREs do match an intermediate, but it is not strictly between finite automata and CFGs, as mentioned with the example languages given above. In fact, you can have an infinite hierarchy of such regular expressions based on POSIX EREs, each having increased maximum number of capturing groups that can be back-referenced.
> 2 votes

# Answer
In programing languages, or their libraries, functions for handling regular expressions are not interested in languages, they are interested in detecting things. For example, take the text of an e-mail and detect a phone number inside it.

There is no reason to restrict regular expressions to those in computer science. For example, $a^n b^n$ is not a regular language, but quite easy to detect. (Yes, there's an infinite number of states. A 64 bit counter can practically represent an infinite number of states - enough to recognise any string that fits on one million large hard drives). Or take the situation where you want two substrings to be the same. Not regular, but easy enough to program.

So "regexes" in programming languages will recognise strings where the rules can be described easily, and that can be recognised with reasonable programming effort, without any regard for computer science.

(As an example, a recent question asked: Given a regular language L, is the language { w: ww element of L } a regular language? Turns out, no. But it is easily recognised. Give me a string w, I write down ww and check if it is in L. )
> 1 votes

# Answer
In POSIX ERE (extended regular expressions) you can write `^([a-z]*)\1$` (here `(...)` captures a match, which is repeated by `\1` later, `^` matches the beginning of a line, `$` it's end), which represents the language $\\{\omega \omega \colon \omega \in \Sigma^\*\\}$ (the alphabet being lowercase letters), which isn't even context free.
> 0 votes

---
Tags: computability, regular-expressions
---


# Question
Title: Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?
The following process seems to be a recurring one:

1. **Initial design**. Commercial organisations invent and implement a design that seems at the time to work.
2. **Problem discovered, new design suggested**. Due to new developments, or just because the designers missed something, a problem with the design is discovered. Academics find a solution to the problem, and a new design is proposed.
3. **Old, sub-optimal design persists due to existing production**. However, the original sub-optimal design is maintained, because a large amount of devices with the old design are already deployed, and for various reasons (network effects, the need for compatibility between devices, etc), this means producers don't want to switch. **Or alternatively**, new production switches, but we still have to deal with the old design because of the large already produced devices.

I am looking for historical examples of such a process in the context of the **IT security of CPU/instruction-set-architecture**:

**What designs of instruction sets/CPU's are we stuck with that are bad from a security perspective, but that are maintained because the cost of switching is high?** (I can imagine that this is also intertwined with OS design and internet protocols).

# Answer
> 1 votes
There were some boo-boos with WiFi, thus the various generations of security protocols. Fortunately, most of the heavy lifting is done in firmware that is uploaded to the card/computer.

Initial (analog) cell phone technologies were trivial to intercept, newer (digital) ones much harder, but there were (are?) still gaps. Needless to say, switching required redoing much infrastructure and everybody getting new phones.

For some entertaining war stories, check out Ross Anderson's "Security engineering" (available as PDFs for each chapter on his homepage). Nicely written, a real classic.

---
Tags: security, lists
---


# Question
Title: How big is the capacity of a standard memory cell that the pointer is linking to?
Often programming language lectures and references have an illustration of computer memory as an array composed of individual cells. Each cell has an address, which is effectively the pointer and can be used to access it. I learned that 32 bit systems will have 4 byte pointers and then got curious what the (standard) capacity of those cells (they are pointing to) was. The most discrete unit of memory is a Memory Cell, but with 1 bit capacity, this does not really fit the bill.

# Answer
That depends on the underlying architecture. Most machines today use byte addresses, but machines that addressed words (i.e. 16, 18, 32, even 36 bits) were reasonably common. If I recall correctly, most RISC machines were unable to address anything but words (but gave addresses in bytes). At least, such an address caused the CPU to fetch both words and snip out and assemble the piece wanted.

What your favorite language does above the machine's intrincacies, ask them. Often they will refuse to handle pointers that aren't aligned at some "machine natural boundary", like the size of a C `double`, 8 bytes. Even on machines that have no penalty attached to non-aligned address acces.
> 2 votes

---
Tags: memory-allocation
---


title: Two versions of Subset Sum Problem

text:
# Question
Title: Two versions of Subset Sum Problem
I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

> Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w\_i$, find the subset $S$ of the items that maximizes $\sum\_{i \in S} w\_i$ while keeping this sum at most $W$. Or the decision version: Is there a subset obeying the at-most-$W$ rule with weight at least some number $k$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

> Given a set of $n$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $k$)?

E.g., my textbook (Kleinberg and Tardos) as well as this have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

1. Do quick reductions exists between the two?
2. Why are these given the same name in the first place?

# Answer
Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.

In the other direction, the idea is to add to the collection a small set of items satisfying the following two properties:

* The total weight of the new items is $W-k$.
* Every weight between $0$ and $W-k$ can be represented as a sum of a subset of the new items.

Having added this collection, we ask whether there is a subset summing to exactly $W$. It is not hard to check that there is a subset of the original collection whose sum is between $k$ and $W-k$ if there is a subset of the enlarged collection summing to $W$ exactly.

How do we add these items? The simplest case is when $W - k = 2^t$, in which case we can simply add $1,2,4,\ldots,2^{t-1}$. More generally, suppose $2^t \leq W-k \< 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.
> 3 votes

---
Tags: complexity-theory, np-complete, reductions, subset-sum
---


# Question
Title: Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope?
I understand that in programming languages in general, function routines have what I can generally name a parameter set (or "list"), usually symbolized with parenthesis and if it is not empty, it is also utilized in function calls.

In JavaScript:

```
function myFunction (passed_parameter_1, passed_parameter_2) {
    // Some code...
}

myFunction(corresponding_passed_argument_1, corresponding_passed_argument_2);

```

## My problem

I never learned in programming courses:

* What is the name of that feature
* why, in programming languages in general, a user *must* have this feature, even if the parameter set in `routine` and the corresponding argument set in `call`, are both empty.
* Why not let a user define a group of parameters (or not) per need, only inside a routine's scope instead

## Interim note

* One could claim it is needed for a compiler to know what is a function but a `keyword` such as `function` reinforce the opinion that it isn't.
* One can claim it is needed for separation of `internal implementation` and `external interface` but such separation could be done as two different sub-scopes of the main scope (`{}`), for example:

> ```
> function myFunction {
>     par myPar1
>     par myPar2
>
>     // some code
>
> }
>
> myFunction {1,2}
>
> ```

## My question

Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope?

# Answer
In my opinion, your question is formed on the basis of working with a small number of programming languages and extrapolating conclusions that may not be valid.

Here are some assumptions I have recognised that may not be valid which I will later explore in greater detail:

* All function calls must use parenthesis.
* All programming languages use these syntactic notations to mean the same thing
* There is some common underlying nature that requires things to be like this

I further understand you hinted that you have no significant background in Computer Science theory, but some of the background material to why functions are usually written like this, is about the theoretical evolutionary route that most current languages came from;
So, lets review some of that, as it may help readers (such as students of Computer Science and programming per se) understand your question and our answers more fully.

Consider an early computer language, such as Fortran, which was devised in 1954. It had functions and used parentheses. Actually, at that time the character set available on computer was so limited that it had no other bracketing symbols, and only had upper case letters. It did not have access to `[]{}<>` symbols. Originally all comparisons were made to zero so that comparison operators were not needed, but when they were later introduced they had to be written as .GT. and .LT. due to the lack of characters. The result of this was we could write:

```
       FUNCTION B
       B=1.0
       RETURN

       FUNCTION C(D)
       C = D
       RETURN

       DIMENSION A(10)
       A(1) = C(1) + B
       STOP
       END

```

You can see that we have used parentheses for `A(1)` (which is an array) and `C(1)` which is a function call, but not for `+ B` which is also a function call. We have used parentheses for `A(10)` which is an array declaration and also for `C(D)` which is a function declaration with a formal parameter. Thee design on the language is such that the compiler can work out what is intended and instruct the computer in its machine code to take appropriate actions. However, sometimes this is not convenient for the compiler writer as that may require multiple passes (or readings) of the program to determine what use of parenthesis was intended before determining the semantics of that fragment of code.

Algol 60 also has a similar situation, shown in this example:

> **integer** **function** one;
> **begin**
> one := 1
> **end**;
>
> **integer** **function** two (**integer** p);
> **begin**
> two := p
> **end**;
>
> **begin**
> **integer** **array** a \[ 1: 10 \];
> a\[one\] := two(1)
> **end**

In the above example `one` is a function that uses no parentheses in its declaration or invocation, whereas `two` is a function that used parentheses to indicate the formal parameter list (**integer** p) and also the actual argument `(1)`. this time they are not confused with arrays at all, because the array exclusively used `[]` in both its declaration and application. So thus invalidating your assumption on what `()` might mean.

We also get some symbol overloading in more modern advanced languages. Take Algol 68 for example. It also uses parentheses for arrays and functions (but also almost everything else), but also like Algol 60 that proceeded it, it uses square brackets `[]`:

> ( \[\] **int** a := (1,2,3);
> print((a\[1\])) )

Here '\[\]' are used to indicate the array declaration, whereas `(1,2,3)` indicates the array constant used to initialise it. The print statement is even more complex. The inner parentheses `(a[1])` indicate an array constant containing one element and the outer `print()` indicates a function call, and the `[1]` indicates an array selection operation. The all-encompassing `()` are used for the program *begin* and *end*.

One more historical language is important here, which is LISP. Using LISP we can explore functions as first class objects, lambda functions and other aspects of functions and the notation associated with them. In LISP we can store a function in a named variable like this:

```
(setq double (function (lambda (x) (+ x x)) ))

```

Notice that everything is using parentheses; that is the nature of LISP. LISP is constructed entirely of lists denoted by the tuples in parentheses like this:

```
(x x x x)

```

Those lists can be either or both data and functions, it makes no difference. Now that the name `double` contains a function we can do various things with it.

We can **invoke** the function like this:

```
(funcall double 11)

```

This leads into coverage of the notation used in command command languages such as Windows/DOS command prompt and unix shells. In them each line is essentially a function call:

```
cd path/file

```

Function calls can be nested by using *backtick notation*:

```
cd `which file`

```

Here no parentheses have been used at all, yet it is a notation familiar to many experienced computer users.

I have not really covered other uses of functions and their notations, such as functions as first class objects, passing functions as arguments, partial parameterisation, lazy evaluation and many many more concepts that could shine a light onto why function notation is as it is. We have to have a notation to ultimately say: This name is a function and I want it to be invoked at this point.

Some of what we are exploring here is the separation between programming language syntax and its semantics. How much of the symbols indicate structure and how much communicate meaning (semantics), and how can this be determined by automated means. An introduction (to a deeper) theoretical topic can be started by looking at Chomsky Language Hierarchy. Algol 60's nice separation of `[]` from `()` meant that a *Context Free Grammar* could be used to describe the syntax of the language. Algol 68, in contrast, by the use of symbol overloading (and for other reasons) mean that a more complex *Context Sensitive Grammar* (known as W-grammars) needed to be used.

The more complex the grammar needed to express the language the more complex the compiler implementation. Language designers wanted both a powerful and expressive language, but also one that could be implemented without undue complexity in the compiler. This often resulted in some stereotyping of language features in ways that were know to be implemented more easily.

In the evolution of languages they developed into different families as they grew from one to another. To prevent the overloading of `()` meaning *begin* and *end* the use of the symbols `{}` became common place, and the use of `[]` for array was considered sensible. However many languages use `()` to indicate both formal parameters and actual arguments, but this is by no means a universal characteristic, and there are exceptions to everything.

When we think that many languages seem to use the `name()` notation for function invocation, what we are really seeing is that many languages in common use today inherit a set of notations from the **C** family of languages through the Algol route. That is all we are seeing is the genealogy of language in the notations.

I hope by a brief tour on the history of the use of parenthesis in the evolution of computer languages and its relation to computer science theory you have gained an insight into what you are trying to understand.

---

And if it matters: yes I have worked on Fortran, Algol 60, Algol 68 and other esoteric language compilers
> 19 votes

# Answer
This notation is seen as useful to differentiate variables from function calls (both for humans *and* compiler parsers):

```
a = 12;
int b = a;

```

versus

```
int a() { return 12; }
int b = a();

```

Furthermore, when `a` is a function, `a` without parentheses can represent the function pointer itself (in Python for instance, or in C if preceded by `&`)

Note that it is not universally true: some languages like Ada don't require (and will reject) parentheses when the function takes no arguments, making it undifferentiable from a variable out of context. And function pointers use a different notation.
> 12 votes

# Answer
The problem a compiler must solve is the use-mention distinction. Are we *using* the subroutine or function (i.e., calling it), or just *mentioning* it (i.e., just needing its identification -- I refrain from talking about 'pointers' since the same problem exists in languages without the concept of pointers).

Even if you have a language that demands declaration before use, and/or has a multipass compiler, so that you know FOO is the name of a subroutine rather than the name of a variable, there is still the problem of knowing what you're supposed to do when the name FOO is encountered without parentheses.

In the simplest case: is `X := FOO;` a call of FOO or not? The answer generally depends on the effective type of X, though note that X itself may have the same problem of resolution. There are at least the following possibilities:

* X is an integer variable, FOO is a function returning an integer value -\> it's a call to FOO.
* X is a reference to a function returning an integer value, FOO is a function returning an integer value -\> it's not a call to FOO, the result is that X now refers to the function named FOO.
* X is a function returning a reference to an integer variable, and FOO is a function returning an integer value -\> both X and FOO are called.
* X is a function returning a reference to a function returning an integer, FOO is a function returning an integer -\> X is called, FOO is not called; whatever reference X returned now refers to the function FOO.

Many early languages did not require parentheses on a call to a subroutine or function that required no arguments. They handled use/mention distinction by other means. The simpler the language, the simpler those 'other means' could be -- might be as simple as an explicit CALL statement for a subroutine.

A particularly interesting example was the language Algol 68, which had fairly involved rules about when a 'procedure value' could be 'deprocedured' (i.e., called to yield a value). The deproceduring coercion applies only to procedures without parameters.

The modern taste, however, is to avoid that particular complexity by making it explicit when a call is required - by having parentheses to indicate a call even though the parameter-list is empty. You might consider the change to be from implicit semantics to explicit semantics; Algol 68's system of implicit type conversions ('coercions' in the jargon) were sometimes thought to be overly complex.

---

With respect to this part: I am just baffled to understand what you mean:

> I don't understand what is the name of this feature and why not let a user define arrays (or not) per need, only inside a routine's scope instead.

The name of the feature would be 'function or subroutine arguments' if anyone bothered to name it.

Suppose we write a function to compute square roots: we define it by something like (pseudocode follows): `function sqrt(real arg) : real { ... }`, to be read 'the function sqrt takes a real argument, represented by the formal name *arg*, and returns a real value'.

Now to call that, we write something like `y := sqrt(42.0)`. The caller is telling the function what value to use for its argument *arg*. That should be clear, right? Neither 'arg' not '42.0' constitutes an array; they are the formal arguments and actual arguments, respectively, of the sqrt function. And they're certainly not 'defaults'.

How could 'arg' be defined 'in a routine's scope' in any more concise manner? 3 facts about it are needed: its formal name, its data type, and the important one, that it is the name of a formal argument for which the caller must supply an actual argument.

A similar function with no formal argument could be declared without parentheses in the syntax I chose: `function FOO : real { ... }` but that's a consequence of the syntax I made up. However, we'd still be left with the need to determine the meaning of the appearance of the name FOO elsewhere: is `X := FOO` a call or not?
> 9 votes

# Answer
There are at least 3 things a function declaration needs to tell the compiler.

* It's a function declaration.
* The name (if any) of the function being declared.
* The names of the arguments (if any).

You can devise any syntax you like that will convey those things. However, there's a certain preference for syntax that either resembles mathematical use, or resembles previous programming language use. These days, in 'mainstream' languages, that usually leads to parentheses, because in such cases there's no particular benefit in doing otherwise.

To make a case for not using parentheses, I think you'd have to argue that your alternative is consistent with the rest of the language syntax, and/or there are advantages of expression that you get by not following the *de facto* standard.

In your specific example (function … par) you have added two new keywords to the language, which is probably two reserved words: proliferation of reserved words is generally avoided if it can be. Further, IMO it's made the language harder to read since now the related concepts of 'declaration' and 'call' now have entirely different syntax. Those two costs appears to have no corresponding benefits.

To sum up: there is no 'must' about it; a language definer is free to define his language however he chooses. However, there are forces which operate: overall linguistic consistency, and the desire to not make familiar mechanisms look arbitrarily different.
> 4 votes

# Answer
On top of what everyone else has said, there is a very good reason why some programming languages did it this way.

"Tuple" call notation in programming languages goes at least back to Fortran. I couldn't find an earlier example, although MATH-MATIC used parentheses and commas for subscripts. It makes sense, because this is familiar from mathematical notation: $f(x,y)$.

Wirth-family languages adopted the notation. But even more than this, Wirth-family languages have an interesting property which makes them very easy to parse.

(Disclaimer: I *believe* this is true of ALGOL, but I'm not 100% certain. It's certainly true of Pascal and its derivatives.)

The property is: No two identifiers appear without a keyword or operator between them. A grammar with this property is known as an "operator grammar".

So, for example, in Pascal you would say:

```
var variable1, variable2: my_type;

```

Where in C you would say:

```
my_type variable1, variable2;

```

In C, the identifiers `my_type` and `variable1` have no keyword or operator between them. Just whitespace. To implement this syntax, C uses "lexical feedback": as soon as a user-defined type has been declared, the lexical analyser must be informed so it can be interpreted as a type name and not a variable name. This is why, in C, a type must be declared before it is used. Without this, C's syntax is not $LR(1)$.

(Technical point: C actually has four distinct identifier namespaces: types, variables, struct members, and goto labels. But this isn't relevant for our discussion.)

So one reason why some languages use tuple notation for calls is to keep the operator grammar property.

There are other alternatives. One, for example, is to keep type names and variable names lexically distinct. Some older languages (e.g. Perl) use sigils. In Haskell, variables begin with lower-case letters and type names begin with upper-case letters.
> 4 votes

# Answer
An exception was Pascal, where using the name of a function with no arguments called it, and assigning to the name of a function assigned to it. It was considered a good idea back then. I always thought it made code less readable.

Today, look at a language like Swift where a function is a first class object. Which can be stored into a variable, passed as a parameter etc. The function name on its own is a function, not a function call. And () is the function call operator.

*Must* function names be followed by empty parentheses if there are no argument? Of course not, there is no *must*. But over the last fifty years, more and more programming languages have found that using parentheses consistently makes life easier.
> 3 votes

# Answer
Well, in the case of Algol family, the answer is **yes, most of them has similar syntax**. and IMO, Algol family could be treated as representative of general programming languages since there are many of well-known field-tested languages like JS, Pascal, Ruby, Java and C-family language.

FYI(I guess you might want to know how this kind of syntax has invented, too), I left my note on this syntax what I've used to answer similar question.

---

1. In perspective of linguistics, the answer is "Well, no one wouldn't find out why if creator never say the reason."(Just think about arbitrariness)
2. If we trace the origin of this syntax, we would reach to Algol 58, which also introduced function(and procedure) in the world. And if we go through CACM's Algol 58 report, we can find the reason why they used those kind of syntax.

> 1. The new language should be as close as possible to standard mathematical notation and be readable with little further explanation" - Page 9
>
> "4. Function Declarations A function declaration declares a given expression to be a function of certain of its variables. Thereby, the declaration gives (for certain simple functions) the computing rule for assigning values to the function (cf. functions) whenever this function appears in an expression. " Page 18
> 2 votes

# Answer
> Why, in programming languages *in general*, must function declarations be followed by a parameter set ...

There are many programming languages and all of them work differently; nothing is "in general".

"`mex` functions" in Matlab for example do not have a possibility to define the number (or data types) of the required parameters; the function itself must check if the number of parameters is correct.

> ... external to the sub-routine scope?
>
> why ... even if the parameter set ... are both empty.

Many modern programming languages are influenced by "C", which is influenced by "BCPL". For this reason the syntax of such languages uses many elements that are found in "C" or in "BCPL".

"C" requires declaring the function arguments after the function name and therefore the other programming languages also require that. "C" requires declaring local variables "in the sub-routine scope" and therefore the other programming languages also require that.

"Pascal" would be an example of a programming language that is not influenced by "C".

The following "Java" functions:

```
int myFunction()
{
    typedef int aType;
    aType a = anotherFunction();
    return a + 5;
}

int secondFunction(int a)
{
    return aThirdFunction(a+1);
}

```

... would look the following way in Pascal:

```
function myFunction: integer;
  type
    aType = integer;
  var
    a: aType;
  begin
    a := anotherFunction;
    myFunction := a + 5;
  end;

function secondFunction(a: integer): integer;
  begin
    secondFunction := aThirdFunction(a+1);
  end;

```

You can see that in "Pascal" the declaration of local variables and local data types is not "inside the scope of a function" (how you call mixing code and variable declarations). Declaring variables and types "inside the scope of a function" seems to be an invention of "C" and therefore you will find this feature in programming languages that have been influenced by "C" but not in most other programming languages.

To me it is obvious that a programming language not allowing a variable declaration "inside the scope of a function" will also not allow a parameter declaration there.

You can also see that neither a function call nor a function declaration of a function that does not take parameters uses empty brackets in "Pascal".

I'm not absolutely sure but I have already seen programming languages (in the industrial environment) where the parameter declaration does not follow the function name directly - just like shown here:

```
function myFunction
  local_data_types
    myType = integer
  memory_information
    in_far_ram
  calling_information
    from_near_flash
  parameters
    myParam1 = integer
    myParam2 = integer
  code
    return myParam1 + myParam2
  end

```

However, the designers of such a programming language would take care that all the parameters must be declared at the same position (here: after the `parameters` keyword):

It shall be possible for a programmer to look at the function and to see the list of required parameters at once; a programmer who wants to call the function should not need to search the entire code for the parameters required.

In your original question you also asked why such syntax elements ...

> ... *endured* in many programming languages?

The reason for this is simple:

In many projects you have to work with different programming languages. Imagine some device (like a "smart" coffeemaker) with an Ethernet plug that can be controlled via a web interface and via a PC program.

For programming the device you will need "C", for the web interface you'll need "JavaScript" and for the PC program you might need "C#".

Because you have to work with three programming languages in your project, you want the three programming languages to be as similar as possible because you don't want to learn three completely different languages.

For this reason a programming language which is completely different to other "widely used" programming languages would not be used by anybody. This seems to be the main reason why "Pascal" (which was quite popular in the 1990s) is only rarely used today.
> 2 votes

# Answer
This is (more or less) a legacy from C. In C (and most languages inheriting from it) you can *declare* a function (announce to the compiler what the function is all about), like:

```
int some_function(int, double, bool);

```

This announces that somewhere the function `some_func` will be defined (perhaps later in this file, perhaps in another file), and that `some_func` takes an `int`, a `double` and a `bool` as arguments, and returns an `int`. After that, you can call e.g. `a = some_func(3, 17.3, true)`, and the compiler can check everything is OK with the call.

Somewhere else you *define* your function:

```
int some_func(int i, double d, bool b)
{
    if(b)
        return i * d;
    else
        return d - i;
}

```

The `{ ... }` is the body of the function, the code executed if it is called.

It is allowed to have functions that take no arguments, and it is also allowed to have functions that do nothing. Both uses do make sense: A function that just retrieves some information from it's environment doesn't require arguments; functions that do nothing can be used as placeholders while you flesh out the program, or be alternatives to be called when nothing is to be done. So it is legal to *declare*:

```
int f();

```

Modern --since ANSI-- C usage explicitly states there are no arguments, nowadays the above says `f` is a function without detailing arguments:

```
int f(void);

```

then you can *define*:

```
int f()
{
}

```

or:

```
int f(void)
{
}

```

In the particular case of C (and close family) languages, you can declare:

```
int i, a[5], *p, f();

```

saying that `i` is an integer, `a` is an array (of 5 integers), `p` is a pointer to an integer, `f` is a function returning an integer. In the case of `f`, no further details are given. The various decorations specify what kind of object is being declared. Other languages use different syntax, in Pascal(-family) languages you'd say something like:

```
 var i: integer, array[0..4] of integer,
     p: ^integer;
 function f; forward;

```

where again `f` is just being declared (thus the `forward`) as a function with no arguments, it must be defined somewhere later, somewhat like:

```
function f;
  begin
    return 42
  end;

```

In Scheme (and other Lisp-familly languages) you define a variable as:

```
(define a)

```

if you want to give it a value, you'd say:

```
(define b 42)

```

while a function is just a variable that happens to have a function as value:

```
(define f
   (lambda (x y)
      (+ x y)))

```

which you then call like `(f 3 4)` (yes, parenthesis outside).

More in general, programming languages are rarely clean, completely rational constructions. Older languages (that have seen much use, and thus evolution) have changed and normally include obsolete constructions for the sake of backwards compatibility (asking everybody to rewrite tons of existing, working code just for the sake of a language change would create riots), some die-hard traditionalists will insist in using them even if better alternatives are available. New languages inherit from older ones, often including endearing quirks and inconsistencies.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: IS there a consensus on the definition of a computer program in CS literature and if so, what is it?
The following is what I came up with from my synthetic prior research but I might be wrong.

I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:

* **Internal implementation:** Everything from start to end, including possible functions and possible sub functions
* **External interface:** A parameter set with which arguments might correspond in `execution` or `call` → if any

Internal implementation includes:

* **Data structures:** *Primitive data types* and possibly also functions or modules (depends what term one prefers)
* **algorithms:** outside or inside a function/algorithm → if any
* **Database interfaces** → if any

I understand that external interface (very often represented by parenthesis) can be part of internal implementation (which, in programming languages, is very often represented by brackets) and that yes or no depends from `language architecture`.

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

# Answer
Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it might be a sequence of binary instructions. For someone working on operating systems, it might be any file with the executable bit set.

Perhaps it could be said that a unifying theme is any form of information that can used to control the operation of a process, or an abstract or real machine, to produce information in the same or different form.

For some, I’m sure this will be too broad, for others, too narrow.
> 3 votes

# Answer
This is not IMO a 'computer science' matter. A 'program' is necessarily expressed in a particular programming language, whether that's a programming language with an implementation on a computer, or a 'mere' logical formalism.

The particular language will tell you what a program is. Which means that it's a grubby implementation issue, not a pristine question of science. (I'm a rude mechanical so I'm ok with that).

For example, for Algol 60

```
<program> ::= <block> | <compound statement>

```

and therefore (if you chase the definitions down) the minimal Algol 60 program is just a pair of statement brackets:

**begin** **end**

Contrariwise, in Algol 68 as far as I recall a particular-program needs to be a block, so a declaration is needed:

**begin** **int** k **end**

Your implementer may add additional requirements.
> 1 votes

---
Tags: terminology, reductions
---


# Question
Title: Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing
I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, but I'm not sure how to write it formally.

Here is what I have:

Let $x\_1$ and $x\_2$ be two letters in the encoding where $x\_1$ is before $x\_2$.

It is given that $\text{freq}(x\_1) \< \text{freq}(x\_2)$.

Suppose the contradiction, $\text{code\_length}(x\_1) \< \text{code\_length}(x\_2)$.

The cost would be $$B(A) = \text{freq}(x\_1)\times\text{code\_length}(x\_1) + \text{freq}(x\_2)\times\text{code\_length}(x\_2)+r$$ where $r$ is the remaining cost of the other letters in the code.

If we were to swap the code lengths of $x\_1$ and $x\_2$, the cost would become $$B(A) = \text{freq}(x\_1)\times\text{code\_length}(x\_2) + \text{freq}(x\_2)\times\text{code\_length}(x\_1)+r$$

The cost would decrease, meaning the code where they are not swapped is not an optimal encoding.

The problem is I'm not sure how to prove that the cost would decrease. Is that provable? Also, is there a better approach?

# Answer
I have come up with a solution.

To show that the old $B(A)$ is larger than the new $B(A)$, it is necessary to show that

$$\text{f}(x\_1)\times\text{c\_len}(x\_1) + \text{f}(x\_2)\times\text{c\_len}(x\_2) \> \text{f}(x\_1)\times\text{c\_len}(x\_2) + \text{f}(x\_2)\times\text{c\_len}(x\_1)$$

($\text{f}(x)$ = frequency of $x$, $\text{c\_len}(x)$ = length of $x$'s encoding.)

By moving terms over and using distributive law:

$$\text{f}(x\_1)(\text{c\_len}(x\_1) - \text{c\_len}(x\_2)) \> \text{f}(x\_2)(\text{c\_len}(x\_1) - \text{c\_len}(x\_2))$$

Since $\text{c\_len}(x\_1) \< \text{c\_len}(x\_2)$, $$\text{c\_len}(x\_1) - \text{c\_len}(x\_2) \< 0$$

Therefore dividing both sides by $\text{c\_len}(x\_1) - \text{c\_len}(x\_2)$ leaves:

$$\text{f}(x\_1) \< \text{f}(x\_2)$$

Which is true as it is a premise.

Correct me if I have made a mistake.
> 2 votes

---
Tags: data-structures, proof-techniques, encoding-scheme, huffman-coding
---


# Question
Title: Linear algorithm to measure how sorted an array is
I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I've heard, quicksort is preferred most of the times, yet still it has $O(n^2)$ complexity in case the array is sorted already.

My question is if there is a way to *measure* in linear time how sorted the array is, and then decide which algorithm is better to use. By measure I mean an algorithm that outputs 1 if the array is sorted already, values closed to 1 if just a few values are unordered, 0 if the input is sorted from the highest to the lowest value. Depending on this output, we could decide if it's a good idea to use quicksort, or we should use some other sorting algorithm.

# Answer
Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A good way to avoid this problem is to shuffle the whole input randomly before we start sorting.

Now to gain more information about how "sorted" the array is, we have to define this quantity formally. We need a formal mathematical definition of "sortedness" before we can design an algorithm to measure it. Here are two different quantities that show in some way the "sortedness" of the array. Let us call the input array $A := a\_1, \dots a\_n$ where $n$ is the length of the array.

The first of which is the number of "inversions". So what are inversions? - you might ask. Inversions are pairs $(i, j)$ such that $i \< j$ and $a\_i \> a\_j$. Of course in a sorted array we have no inversions. Counting inversions can be done in running time $O(n\log n)$ using different methods among which are divide and conquer and using balanced search trees. However since counting inversions is not faster than sorting, I would not recommend it to find how sorted an array is as a pre-sorting routine.

Another measure is the minimum number of elements to be removed to turn the array sorted. This problem is equivalent to finding the longest increasing subsequence and it has an $O(n \log n)$ algorithm using dynamic programming. However, there is an simple linear time two approximation algorithm for this problem. Intuitively, the algorithm removes pairs of adjacent inversions until the array contains no more inversions. In pseudo-code the algorithm goes as follows:

```
- Let L be an empty linked list
- For each a := a[1] .. a[n] do
 - Append a to L.
- Set i := 1
- While a[i] is not the last element in L
 - while  a[i] no the first element in L
     and a[i] < a[i-1] do
  - remove a[i] and a[i-1] from L
  - Set i to the next element.
 - Set i to the next element.

```

Each time we remove two elements from $L$, they form an inversion an at least one of them should be removed. Hence we remove at most twice as many as the total number of elements that must be removed. Note that the running time can be bounded in $O(n)$ since the outer while iterate over all elements once and each call of the inner loop removes two elements and hence it can not be called more than $O(n)$ times in total.

One way to use this measure to sort arrays more efficiently is to use the previous algorithm to find all such pairs. Let $L\_1$ be the list above after removing the elements from it and $L\_2$ the list of all removed elements. Now since we know that $L\_1$ is sorted, all we need to do is to sort $L\_2$ in $O(h\log h)$ assuming $h$ is the number of elements has to be removed to turn the array sorted. Using some kind of sliding window (the conquer part of merge sort), we can build a sorted version of $A$ combining $A\_1$ and the sorted version of $A\_2$ in linear time. In total we get an adaptive sorting algorithm running in $O(n + h \log h)$.
> 6 votes

# Answer
So you learnt that Quicksort takes quadratic time for an already sorted array.

Exercise 1: implement Quicksort so it takes O(n log n) for a already sorted array.

Exercise 2: implement Quicksort so it takes linear time in this case.
> 0 votes

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