title: Writing a grammar for lambda calculus

text:
# Question
Title: Writing a grammar for lambda calculus
I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like:

```
expr: variable | "(" expr ")" | application | abstraction
abstraction: "λ" variable "." expr
application: expr expr

```

I'd like the grammar to unambiguously parse expressions taking advantage of the notational conventions mentioned here on Wikipedia. While I'm able to modify the grammar to follow most of them, I got stuck with implementing this one: *"The body of an abstraction extends as far right as possible"*.

For example, there are two parse trees for `λx.x λa.a` \- it can be both an application of two abstractions ( `(λx.x)(λa.a)` ) or an abstraction with an application in its body ( `λx.(x(λa.a))` ). If the abstraction was greedy as it should be, only the second one would be correct.

Is it possible to write a grammar that would force (i.e., make it the only choice) greedy interpretation of abstractions? If so, how to do it?

# Answer
> 3 votes
If your motivation is practicability, you could have a look at the grammar for `lambda` in the PL Zoo. Start reading below the comment saying "main syntax tree", and you may safely ignore the `mark_position` business which just tags the syntax tree with positions in the file. What's left is an unambiguous context-free grammar.

We can summarize the grammar as follows:

```
expr ::=
  | LAMBDA binders PERIOD expr
  | app_expr

app_expr ::=
  | simple_expr
  | app_expr simple_expr

simple_expr ::=
  | name
  | LPAREN expr RPAREN

binders ::= name+

name ::= NAME

```

Here `NAME` is a lexing token carrying a variable name and `R+` means "one or more repetitions of `R`".

Note however that while textbooks say that the body of a $\lambda$-application should extend to the right as far as possible, they do not specify how brackets are to be used in an application. In particular, most people would find $x \lambda a . a$ to be confusing, even though it obviously means $x (\lambda a . a)$.

You should also pay attention to the associativity of application, i.e., is $A B C$ equal to $(A B) C$ or $A (B C)$?

So if you want a realistic grammar you should require certain restriction in an application. To see what precisely these could be, consult the `lambda` grammar linked to above.

# Answer
> 1 votes
As @chi wrote, one good solution would be to enforce parenthesis around both applications and abstractions.

Because I want to be as close to "handwritten" lambda calculus (so I'd like to eliminate parenthesis as much as possible), I tried another approach, which eventually worked. I blocked applications from having abstractions (not parenthesised abstractions, just abstractions) on their left side, so that `λx.x M` will never parse to `(λx.x)M`. This will force the greedy parsing of abstractions - `λx.(xM)`, exactly as I want.

The grammar doing that might look like this:

```
atom: "(" expression ")" | variable
expr: atom | abstraction | application
abstraction: "λ" variable "." expr
application: atom | application (atom | abstraction)

```

---
Tags: context-free, lambda-calculus
---


# Question
Title: How can I find matchings in a Bipartite graph beginning with specific vertices?
Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph exist between corresponding donors and receivers). I want a way to find maximum number of edges through disjoint chains and I've been trying to do so through maximum wtd matching.

I know I can use ford-fulkerson to find a maximum wtd perfect matching, however, the main problem I'm facing is that the matchings can only exist for chains beginning with *specific* vertices. For example, if this is my directed acyclic graph:

Turning this into a Bipartite graph and using the maximum wtd matching way, I get the chain 0-\>1-\>3-\>5-\>6 but I also get 2-\>4. However, I can only have chains beginning with 0 so 2-\>4 should not come up.

I wanted to know if there were any ways to work around this problem? Someone suggested making this a minimum cost perfect matching problem but I'm confused how.

I realise this is a weird question but any help would be appreciated!

# Answer
To make this a minimum-cost perfect matching problem, split each node as you indicated (sending/receiving). Add a high-cost edge from each node's sending node to its own receiving node. This high-cost edge will only be used if that node does not receive a kidney. Additionally, I assume Node 0 in the above graph is supposed to be an altruistic donor or a deceased organ donor that does not need to receive a kidney. (Otherwise, your example has no cycles and no exchange can take place.) Assuming Node 0 is a 1-way donor, add low cost edges from **every** sending node to Node 0's receiving node.

Then solve the minimum-cost perfect matching problem. A perfect matching is obviously possible (every sending node can send to its own receiving node). A minimum-cost perfect matching will use as few of the high-cost edges as possible. Minimizing the number of high-cost edges (nodes that send to themselves) is the same as maximizing the number of nodes that receive a kidney.

This is also known as the assignment problem and can be solved in polynomial time. Most kidney-exchange research adds the significant complication of requiring cycles to be at most length k. That complication makes the problem NP-hard. Altruistic donors could allow for longer cycles in practice.
> 2 votes

---
Tags: algorithms, graphs, bipartite-matching
---


title: Cracking code with clues

text:
# Question
Title: Cracking code with clues
I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities.

We have a 5 character code that is consisting of digits *{0,1, ..., 7}*. We have 10 attempts and for each attempt we have the amount of correctly guessed digits on the right indexes, and the number of correctly guessed digits on an incorrect index.

What I did what to generate all 5 digit numbers consisting of digits {0,1, ..., 7}., however I failed to find any way to narrow the attempts down. Could you help me find the right algorithm? Thanks!

# Answer
Your problem is a variant of Mastermind. In particular, it is "Super Mastermind". Wikipedia contains some relevant pointers, and you can find many more by searching for Super Mastermind. For example, Temporel and Kovacs describes a heuristic algorithm that solves Super Mastermind using roughly 5–7 guesses. The same work also contains pointers to other algorithms.
> 1 votes

---
Tags: backtracking
---


# Question
Title: Algorithm for fewest moves in 1's, 10's, 100's, etc
I'm building a math application (not homework) and I want to build a component that allows players to drag-and-drop 1's, 10's, 100's, etc to complete problems and *a bonus reward* if they do it in the fewest moves possible--**How can I calculate this?** e.g.

```
50 + X = 96

```

where X is a randomly generated integer and the player *is modifying* X during play. So, the player needs to make X=46, but starts at 121. For example,

```
if X is initially 121, and player needs to get to 46

```

player thinks, "cool, i'll just subtract 75"

```
remove 7x 10's, remove 5x 1's - 12 moves

```

but it turns out, there's a faster way to do it:

```
remove 1x 100's, add 2x 10's, add 5x 1's - 8 moves

```

Is there an existing algorithm for this? It would be helpful to calculate this for anything up to 10,000 where I can calculate the minimum number of moves required.

# Answer
You can construct a graph with vertices $0,1,2,3,4,\dots,10000$, two vertices are adjacent if you can construct a number with a single operation from another one. A single operation is either adding or subtracting $1,10,100,1000,\dots$. For example,$N(46) = \\{45, 47, 36, 56, 146, 1046,\dots\\}$. Then the minimum number of operations required to construct a number $x$ is the shortest path from $x$ to 0. Since graph is undirected, you can run a single one to all algorithm (Dijkstra,BFS) and obtain all distances from 0 to any other vertex. Also the graph is pretty sparse, hence Dijsktra with heap will nail it. An implementation might no need to construct the whole graph, since neighborhoods are small and easily computable on the fly.

EDIT: if you take Dijkstra code from Geeks, you can construct graph as

```
for(int v1 = 0; v1 < V; ++v1)
   for(int v2 = v1+1; v2 < V; ++v2)
      if(v2 - v1 == 1 || v2 - v1 == 10 || v2 - v1 == 100)
         g.addEdge(v1,v2,1);
 g.shortestPath(46); // gives 8 to 121

```
> 2 votes

# Answer
Let's consider digits one by one, starting by the rightmost digit answering recursively the question:

Is it better to reach it by addition or subtraction ?

Let's take your example 121 =\> 46, starting with 1=\>6, you can either:

* use 5 "+1" steps leading to the 12 =\> 4 problem
* use 5 "-1" steps leading to the 11 =\> 4 problem.

In the same way, the 12 =\> 4 problem leads to:

* use 2 "+10" steps leading to the 1 =\> 0 problem
* use 8 "-10" steps leading to the 0 =\> 0 problem

and so on ... Until you reached the digit before the leftmost one. This will eventually adds an additional digit with something like {-1, 0, 1} =\> 0, but here just keep the way done in one step.

You build a binary tree with at most $d+1$ depth, with $d$ the number of digits of the largest of your two initial numbers. Just keep the leaf using the least steps. If you limit numbers to 10000, there are at most $2^6 = 64$ branchs to evaluate.
> 1 votes

# Answer
With integral *modifications* at least twice the next lower and at most half the next higher, this should be trivial: representing the difference necessary as a "balanced" positional number (uniform base $b$ or not, digit $d\_i \in \[\lceil-(b\_i-1)/2)\rceil .. \lceil(b\_i/2)\rceil\]$) gives the *fewest moves possible* (with an odd base, there are equivalent cases: two in balanced ternary is $1\overline1$, $1+1$ amounts to same using no more digits).

Starting with the least *modification* no less than the absolute difference $\lvert D\rvert$ always choose the amount giving the accumulated sum closest to $D$, the lower value in case of a tie (possible only with even $b\_i$).

This does not seem to warrant a name.
It may or may not be enough of a challenge for a *bonus*.
> 1 votes

# Answer
I have divided this answer into a **short answer** and a **long answer**:

# SHORT ANSWER:

THE FOLLOWING IN AN OPTIMAL STRATEGY FOR THE GAME:

1) Let `diff` be the difference between current value and target value. For example,

```
current value: 550
target value:  834
diff: 834 - 550 = 284

```

2) Look at only the ones and tens place of `diff`. If the ones and tens greater than or equal to 56, overshoot using 100s. Else, undershoot using 100s.

For our running example,

```
 `diff` is `284`
The tens and ones place only are `84`
Since `84` is greater than or equal to `56`,
your first move(s) are to add 3 X 100s to the current value.

If we wanted to ***under***shoot,
then we would only add only 2 x 100s to the current value.

```

3) Now, let `diff` be the new difference between current value and target value. For our running example,

```
current value: 850
target value:  834
diff: 16

```

4) if the ones place is greater than or equal to 5, then \***over\***shoot using tens. If the ones place is les than or equal to 4, \***under\***shoot using tens

```
diff: 16
the ones place, 6, is greater than or equal to 5
we overshoot using 10s
we use two moves to subtract 2x10.
we then add 4 pennies.

RESULT:

starting value: 550
target value:  834

add 3x100
sub 2x10
add 4x1

9 total moves

```

The number of the left represents the difference between the player's current value and the target value. The number on the right represents the minimum number of moves required to make the current value equal to the target value.

```
(0, 0)
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 6)
(6, 5)
(7, 4)
(8, 3)
(9, 2)
(10, 1)
(11, 2)
(12, 3)
(13, 4)
(14, 5)
(15, 7)
(16, 6)
(17, 5)
(18, 4)
(19, 3)
(20, 2)
(21, 3)
(22, 4)
(23, 5)
(24, 6)
(25, 8)
(26, 7)
(27, 6)
(28, 5)
(29, 4)
(30, 3)
(31, 4)
(32, 5)
(33, 6)
(34, 7)
(35, 9)
(36, 8)
(37, 7)
(38, 6)
(39, 5)
(40, 4)
(41, 5)
(42, 6)
(43, 7)
(44, 8)
(45, 10)
(46, 9)
(47, 8)
(48, 7)
(49, 6)
(50, 5)
(51, 6)
(52, 7)
(53, 8)
(54, 9)
(55, 11)
(56, 9)
(57, 8)
(58, 7)
(59, 6)
(60, 5)
(61, 6)
(62, 7)
(63, 8)
(64, 9)
(65, 10)

```

# LONG ANSWER:

Your problem is related to making change using the smallest number of coins possible.

For example, suppose that you owe a customer 72 cents. How do you make 72 cents using the smallest number of coins possible? Assuming that ($25¢, 10¢, 5¢,$ and $1¢$) are the only types of coins available to you. Notice that you first get as close as possible using the largest denomination (quarters), then get as close as possible using the second largest denomination (dimes), and so on... 2 quarters, 2 dimes and 2 pennies is optimal. That uses 6 coins in total.

---

Unlike the traditional coin-change problem, your problem allows ***negative*** value coins. That is, you allow the user to subtract 100, 10, or 1, in addition to adding 100, 10, or 1.

Your "coins" come in the following denominations sizes: ${100¢, -100¢, 10¢, -10¢, 1¢, -1¢}

---

First observation:

If you are going to add tens, then there is no point in subtracting tens also. Those would be wasted moves.

For example, instead of adding 5 tens and subtracting 3 tens, you would simply add 2 tens, and not subtract any tens.

---

A second observation is that it makes sense to work with 100s first, then 10s then 1s. you get as close as possible to the target value using "coarse" resolution, then get even closer using "fine" resolution afterwards.

---

If you add 100s, "overshoot," then subtract 10s later, what's the optimal amoutn of overshoot by? If you are currently using 100s, then you get as close to the target value that 100s will get you. After you are done adding or subtracting 100s, you always want to be less than 100 away from the target value; after you're done adding and subtracting 10s, you will always be less than 10 away from the target value, and so on...

For example, suppose the current value is 0 and the target value is 283. You either add 2\*100, and underachieve the target of 283 by 83 points,or you add 3\*100 and overshoot the target by 17 points. You have no incentive to overshoot by 117 points, or 217 points. There's no incentive to be more than 100 away from the target value after you are done adding and subtracting 100s. This is because takes fewer steps to jump 100 units using a step length of 100 units than a step length 10. You might as well make logn strides will using 100s, rather than using 10s to make up the distance later.

---

We are very close now to knowing the optimal strategy.

Let `//` denote integer division. For example `5//2` is `2` not `2.5`

Suppose that for any integer `x`, `SIGN(x)` returns the sign of x. For example, `SIGN(-342) = -1`

Suppose that the current number is `CURRENT` and the target value is `TARGET` `DIFF = TARGET - CURRENT`

So far, our strategy is as follows:

1. Add `DIFF//100` or `DIFF//100 + SIGN(DIFF)` one-hundreds to `CURRENT`
2. Re-compute `DIFF` using the new current value, `CURRENT`
3. Add `DIFF//10` or `DIFF//10 + SIGN(DIFF)` tens
4. Re-compute `DIFF` using the new current value, `CURRENT`
5. Add `DIFF` ones.

For any given target value, we have 4 strategies. One of those 4 will be the optimal one. The choices revolve around getting close by undershooting or overshooting. For example, suppose the current value is 0 and the target value is 283. You either begin by adding 3\*100, and overshoot the target value by 17 points. Or, you add 2\*100, and underachieve the target of 283 by 83 points. Those are the only 2 sensible choices for your first action. After that, you either under-shoot or over-shoot using tens. In the end, you have 4 possible stragegies:

1. (undershoot using 100s, undershoot using 10s, add pennies)
2. (undershoot using 100s, OVERshoot using 10s, subtract pennies)
3. (OVERshoot using 100s, subtract 10s, subtract pennies)
4. (OVERshoot using 100s, subtract too many 10s, add pennies)

---

As a reminder, the denominations are $\\{100, -100, 10, -10, 1, -1\\}$

### Question:

You would think that the more total cents there are, the more coins you're going to have to use. For positive integers `x < y`, is it always at least as easy to make change for x than for y? For example, is it easier to make change for 44 cents than 49 cents?

Answer:
No. The best way to make change for 44 cents is to use 4 positive dimes and 4 positive pennies, for a total of 8 coins used.

The best way to make change for 49 cents is to use 5 positive dimes and 1 negative penny, for a total of 6 coins used.

Making change for 49 cents uses fewer coins than making change for 44 cents.

---

Why ask the earlier question? It means that there exist (current value, target value) pairs such that the following strategy is ***non***-optimal:

1. add or subtract 100s until abs(current - target) is minimized
2. add or subtract 10s until abs(current - target) is minimized
3. add or subtract 1s until abs(current - target) is minimized

---

Suppose current value is 0. For target values between 0 and 99, When does "overshooting" with 10s require fewer coins than "undershooting"?

If we undershoot, what will the coin count be?
coin count will be (count of original tens) + (count of original pennies)

```
    under(44) = 4 + 4
              = 8

```

If we overshoot, what will the coin count be?

```
(original tens + 1) + (10 - original pennies)

over(44) = (4 + 1) + (10 - 4)
         = 5 + 6
         = 11

```

For what X in {0, 1, 2, 3, ..., 99} is over(x) \< under(x)?

For what X in {0, 1, 2, 3, ..., 99} is `[(x//10) + 1] + [10 - (x%10)] < (x//10) + (x%10)` ?

combine constant terms (+1) and (+10)
`(x//10) + 11 - (x%10) < (x//10) + (x%10)`

subtract (x//10) from both sides
`11 - (x%10) < + (x%10)`

`11 < 2(x%10)`

`4.5 < (x%10)`

Note that `(x%10)` is an integer. `5 <= (x%10)`

When using tens, overshooting `X` with is better than undershooting `X` if and only if `(x%10) => 5`

Below is some code written Python to help us:

```
def undershoot_dimes(total_cents):
    # make `total_cents`  non-negative by taking the absolute value
    pos_total_cents = abs(total_cents)
    if pos_total_cents == 0:
        pos_total_cents = 1
    sign = total_cents / pos_total_cents

    dimes = pos_total_cents // 10
    pennies = pos_total_cents % 10

    # `//1` converts float into integer
    return (sign*dimes//1, sign*pennies//1)

def overshoot_dimes(total_cents):
    # make `total_cents`  non-negative by taking the absolute value
    pos_total_cents = abs(total_cents)
    sign = total_cents / pos_total_cents

    dimes = 1 + (pos_total_cents // 10)
    pennies = (pos_total_cents % 10) - 10

    return (sign*dimes//1, sign*pennies//1)

def coin_breakdown_dimes(total_cents):
    """
    A `total_cents` is an integer, such
    as `42` or `83`

   This function returns (number of dimes, number of pennies)

    4 types of coin may be used: {-1, +1, -10, +10}
    Note that in addition to positive dimes and pennies,
    we allow negative dimes and negative pennies
    """
    if abs(total_cents) % 10 >= 5:
        return overshoot_dimes(total_cents)
    #end if
    return undershoot_dimes(total_cents)
# end function definition

def print_coin_breakdown_dimes(total):
    dimes, pennies = coin_breakdown_dimes(total)
    print(total, "total cents can be made using", end = " ")
    print(dimes, "dimes and", pennies, "pennies.")

for total in [19, 82, 87]:
    print_coin_breakdown_dimes(total)

# 19 total cents can be made using 2 dimes and -1 pennies.
# 82 total cents can be made using 8 dimes and 2 pennies.
# 87 total cents can be made using 9 dimes and -3 pennies.

```

## Question:

When do we want to overshoot with 100s and when to we want to undershoot with 100s?

```
overshooters = list()
for cents in range(0, 100):
    CC_undershoot = CC_dimes(cents)
    CC_overshoot = CC_dimes(100 - cents)
    if 1 + CC_overshoot < CC_undershoot:
        overshooters.append(cents)
print(overshooters)

```

If `cents` is 56 or greater, we want to overshoot using 100s.

```
def undershoot_dollars(total_cents):
    assert(total_cents >= 0)
    dollars = total_cents // 100
    leftovers = total_cents % 100
    return (dollars, leftovers)

def overshoot_dollars(total_cents):
    assert (total_cents >= 0)
    dollars = 1 + (total_cents // 100)
    leftovers = (total_cents % 100) - 100
    return (dollars, leftovers)

def coin_breakdown_dollars(total_cents):
    # INPUT:
    # an integer, such as `42` or `83`
    #
    # OUTPUT:
    # (number of dollars, number of dimes, number of pennies)
    #
    # 6 denominations of coin may be used: {-1, +1, -10, +10, -100, +100}
    # In addition to positive dimes and pennies,
    # we allow negative dimes and negative pennies
    assert (total_cents >= 0)
    if (total_cents % 100) <= 55:
        dollars, leftovers = undershoot_dollars(total_cents)
        dimes, pennies = coin_breakdown_dimes(leftovers)
    else:
        dollars, leftovers = overshoot_dollars(total_cents)
        dimes, pennies = coin_breakdown_dimes(leftovers)
    return (dollars, dimes, pennies)

def CC(total_cents):
    """
    `CC` stands for `coin count`
    This function does use 100s
    6 denominations of coin may be used: {-1, +1, -10, +10, -100, +100}
    """
    coin_spec = coin_breakdown_dollars(total_cents)
    return sum(map(abs, coin_spec))//1

def print_coin_breakdown_dimes(total):
    dol, dimes, pennies = coin_breakdown_dollars(total)
    print() # new line
    print(total, "total cents can be made using", end = " ")
    print(dol, "dollars", dimes, "dimes and", pennies, "pennies.")
    print(CC(total), "coins total.")

for total in [219, 882, 487]:
    print_coin_breakdown_dimes(total)

# 219 total cents can be made using 2 dollars 2.0 dimes and -1.0 pennies.
# 5.0 coins total.
#
# 882 total cents can be made using 9 dollars -2.0 dimes and 2.0 pennies.
# 13.0 coins total.
#
# 487 total cents can be made using 5 dollars -1.0 dimes and -3.0 pennies.
# 9.0 coins total.

```

So, your videogame has a `target_value` and a current\_value`. You want to know the minimum number of steps the player must use to reach`target\_value`from`current\_value`. The answer, using our python code, is`CC(abs(target\_value - current\_value))\`

You can pre-compute these values:

```
diff_to_min_moves = dict()
for difference in range(0, 100):
    diff_to_min_moves[difference] = int(CC(difference))

print('\n'.join(map(str, diff_to_min_moves.items())))

```
> 1 votes

---
Tags: algorithms
---


# Question
Title: Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory
I am proving a kind of structure invariance principle for magmas in Cubical Type Theory with the Agda/Cubical library. This is done by constructing a path between two simple magmas and then transporting proofs of simple properties about this path. I have already obtained most of the proof (see my code repository) but did not manage yet to complete the following lemma.

At some point in the proof I have the following given:

* A bijection between types: `f : ℕ → ℕ₀`
* The isomorphism constructed with `f`: `fIso : Iso ℕ ℕ₀`
* A function that gives the inverse isomorphism of an isomorphism: `invIso : Iso A B → Iso B A`

Now, I would like to prove that:

```
sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))

```

There are two parts to my question:

* Is this a valid theorem in HoTT? Although this statement seems valid, maybe I have produced a false statement?
* Are there built-in functions in the Agda/Cubical that may help in the proof?

# Answer
The original statement in my question `sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))` is a valid statement in Homotopy Type Theory but because (homotopy-) isomorphisms are a special case of equivalences, the statement can be generalized to

`sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))` (\*)

It is one of the properties of `ua` that are informally proven in the Univalent Foundations book in section 2.10.

## Solution

The results from  have been implemented and proven in the lemmas in the Agda Cubical library. The function `uaInvEquiv` of those lemmas in particular solves my problem (\*). For future applications it is better to use  because they are more general than my own approach below.

---

## Historical solution

Using the hint to use `EquivJ`, I gave a proof for the theorem that may not be the most efficient one but it worked (typechecked) for my specific case:

```
baseIndLemma : (A : Type ℓ-zero) → (λ i → ua (idEquiv A) (~ i)) ≡ ua (invEquiv (idEquiv A))
baseIndLemma A =
  sym ( ua (idEquiv A) ) ≡⟨ uaIdEquiv ⟩
  sym refl ≡⟨ refl ⟩
  refl ≡⟨ sym uaIdEquiv ⟩
  ua (idEquiv A) ≡⟨ cong ua (equivEq (idEquiv A) (invEquiv (idEquiv A)) refl) ⟩
  ua (invEquiv (idEquiv A)) ∎

myUaInvEquiv : sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))
myUaInvEquiv = EquivJ
  (λ _ _ e → sym (ua e) ≡ ua (invEquiv e)) (λ A → baseIndLemma A) ℕ₀ ℕ fEquiv

```
> 3 votes

---
Tags: type-theory, homotopy-type-theory, cubical-type-theory
---


# Question
Title: How does Rogozhin's (2, 18) universal turing machine work?
I am trying to understand Rogozhin's (2, 18) universal turing machine by stepping through a simple 2-tag encoding that I believe should loop forever:

```
a -> aa

```

For example, using an initial input of `aaa`:

```
aaa
  aaa
    aaa
      .... etc

```

*Apologies for the extremely specific question, but it's what I've narrowed my issue down to and I've been stuck for a while!*

Following the instructions in part 10 / pp22 and page 6 I believe this system should be encoded as:

```
c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
|P2   |P1           |P0   |Ar   |As   |At

```

Running this, however, results in termination rather than an infinite loop. Following the trace I have managed to identify something I can't explain and that seems wrong, but have not been able to figure out a resolution.

Following the first stage of modelling:

> On the first stage, the UTM searches the code P, corresponding to the code A, and then the UTM deletes the codes A, and A, (i.e. it deletes the mark between them)
>
> ...
>
> if the head of the UTM moves to the right and meets the mark c, then the first stage of modelling is over. The UTM deletes this mark and the second stage of modelling begins

Gives the following trace:

```
c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b  b⃖ >1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b >b⃖  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1 >b  b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖ >b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖  1⃖ >c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c

```

At this stage, Rogozhin claims the tape should be:

*P2P1P'0R'At*

Notice in particular *R'At*

> R’ consists of 1⃖ and 1⃗ and the head of the UTM is located on the R’ in the state Q2

But to me, **it appears that only Ar has been deleted!?**

```
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c
|P2   |P1           |P'0  |R'   |As!! |At

```

I would expect something like:

```
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1⃖  1⃗  1  c
|P2   |P1           |P'0  |R'         |At

```

I have identified the following potential errors I have made, but have double checked each and have not been able to identify any:

* Understanding of 2-tag system.
* Encoding of 2-tag system.
* Execution of rules (programming bug).
* Formatting of trace.
* Interpretation of trace.

Can anyone spot what I'm missing? Am hoping it's something obvious!

Supplementary materials

# Answer
> 3 votes
I see (at least) two errors:

The head position should be at the beginning of $S$; and there is an extra 1 at each $P\_i, i \> 1$: $P\_i = bb 1^{N\_{i\_{m\_i}}}1b....b1^{N\_{i\_2}}1b1^{N\_{i\_1}}$

```
c⃖₁ c⃖₁ b  b  1  1  b  1  b b >1  c  1  c  1  c
                 ^            ^
                !!!          !!!

```

Don't forget that the rest of the tape should be fille with $1^{\leftarrow}$ (the balnk symbol).

A few years ago I also examined its behaviour; you can find the javascript version I made here: click "Small" to load it, then fill the tape (click on the second gray row to place the head), and click "Step". You can compare it with your implementation.

---
Tags: turing-machines
---


# Question
Title: Proving Turing Completeness by creating a compiler to a Turing Complete language
Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the formal thinking behind the idea?

# Answer
> 5 votes
No. It's usually relatively easy to compile a language (Turing complete or otherwise). At a very simplistic level, a compiler flattens an abstract syntax tree into a list of instructions. This can usually be done by a simple structural induction over the syntax tree. Optimization passes often do data flow or control flow analyses that would be harder to represent as a simple structural induction.

You can make a practical demonstration by programming a compiler for the untyped lambda calculus into some simple Turing complete stack-based machine in Agda or some other non-Turing complete language.

However, just as an extreme example, the "compiler" could be the identity function. If you meant that you could write a compiler for *any* Turing complete language, then that wouldn't be possible simply because the semantics of the language may require executing arbitrary code (e.g. Common Lisp macros) to elaborate the syntax or otherwise to produce a correct compiler.

# Answer
> 0 votes
I don't think that's the case.

Looks to me that you are questioning if the Turing-completeness is *specification-wise* or *implementation-wise*. And the answer is in the *specification-wise*.

If I have a language A, I've specified its semantics - and it is not Turing complete by definition (say, CSS for example). This means that whatever compiler you write will have to follow that specification regardless of what language your compiler's backend will spit out.

---
Tags: programming-languages, turing-completeness
---


title: Kraft's inequality for Huffman coding

text:
# Question
Title: Kraft's inequality for Huffman coding
Is it true to say that Huffman codes always satisfy Kraft's inequality with strict equality?

At first, I thought the statement is wrong since for Huffman coding there is no assumptions on the probabilities. However, when I tried evaluation the Kraft inequality for several Huffman codes, I realized that it's got nothing to do with the probabilities. It's the algorithm.

I looked for a nice mathematical proof for this, but couldn't find any. Would appreciate your help.

# Answer
> 3 votes
All Huffman codes satisfy Kraft’s inequality with strict equality. We will give two proofs of this fact, one specific to Huffman codes, and the other applying to all minimum redundancy codes.

**First proof.** The first proof is inductive. Recall that Huffman’s algorithm proceeds as follows. We choose the two symbols with minimal probability, and merge them. We then run the algorithm on the new distribution. Finally, we split the merged symbol into two symbols by adding a suffix of 0 to one of them and of 1 to the other.

When there are only two symbols left, Huffman’s algorithm assigns them the codewords 0 and 1, and since $2^{-1} + 2^{-1} = 1$, we see that Kraft’s inequality is satisfied with equality.

Now suppose that there are more than two symbols. Huffman’s algorithm merges two of them, and then runs on the resulting code. The induction hypothesis shows that Kraft’s inequality is satisfied with equality on the new code. The final step is splitting one of the symbols. In this step, a codeword of length $\ell$ is replaced by two codewords of length $\ell+1$. Since $2^{-\ell} = 2 \cdot 2^{-\ell-1}$, we see that the final code also satisfies Kraft’s inequality with equality.

**Second proof.** The second proof applies to any minimum redundancy code. We start by associating with each prefix code a binary tree. This is done as follows. If the prefix code consists of just the empty word, then the binary tree is a leaf. Otherwise, we construct a binary tree for all codewords starting with 0, another one from all codewords starting with 1, and join the two at the root. If we think of the edges as labeled by 0 and 1, then we can recover the codewords by traversing the tree from root to leaves and concatenating the symbols written on the edges.

A simple induction shows that $\sum\_f 2^{-\ell(f)} \leq 1$, where $f$ goes over all leaves, and $\ell(f)$ is the depth of $f$; this is just Kraft’s inequality. The same proof also shows that equality holds iff all internal nodes have exactly two children. In this case we call the code *complete*.

If the code is incomplete, there is an internal vertex with only a single child. We can replace this vertex by its child, thus obtaining a new code in which no codeword gets longer, and some get strictly shorter. The new code has less redundancy than the original one. This shows that if we start with a minimum redundancy code, then the code must be complete, and so Kraft’s inequality holds with equality.

---
Tags: huffman-coding
---


# Question
Title: Prove NP-completeness for union of NP-complete language and language in P
Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete?

My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is NP-hard:

I can prove $(X\cup Y)\in NP$ by saying that since both are in NP, they each have polytime verifiers. Thus we can have a polytime verifier that on any input will use these verifiers and accept if any accept, reject otherwise.

I am stuck on the part of proving NP-hardness. The idea of arbitrary languages is throwing me off; I am trying to reduce a NP-complete problem (SAT for example) to $X\cup Y$ and using the fact that $X$ has some method to reduce to it already but I am lost as for what to do with $Y$. I am thinking that given an input for SAT, I need to somehow change the input so that I can relate acceptance in $X\cup Y$ to acceptance in SAT; same for rejection.

Any guidance would be appreciated; thanks!

# Answer
> 8 votes
If for any two disjoint languages $X,Y$, we have:

$\textbf{\*} \hspace{1mm} X \text{ is NP-complete} \land Y\in P \Rightarrow X\cup Y\text{ is NP complete}$

then $P\neq NP$.

Let $L$ be some NP-complete language. $L\cup\overline{L}=\Sigma^\*$ is not NP-complete, thus, using (\*) we obtain $\overline{L}\notin P$, but $L\in P\iff \overline{L}\in P$.

In fact your statement is equivalent to $P\neq NP$. You can prove the opposite direction by using the fact that if $P\neq NP$ and $L$ is NP-complete, then $\overline{L}$ is not in $P$. In that case, you can reduce $X$ to $X\cup Y$ by checking if the input is in $Y$, and output some constant word outside of $X\cup Y$ if it is. This can be done since we know now that $Y\subsetneq \overline{X}$.

# Answer
> 2 votes
Here are some thought which might be helpful.

1) *NP*-hardness

Take a language $L$ in $NP$. There is a many-one reduction $f$ from $L$ to $X$ because $X$ is *NP*-Complete. So, for yes-instance you have no problem, because for $l \in L$ you have $f(l) \in X$ so $f(l) \in X \cup Y$. For the no-instance it's not that trivial because you might have for $l \notin L$ $f(l) \in Y$. To fix this case, you use the fact that $Y \in P$ and thus it is easy to tell if $f(l) \in Y$. You can confidently reject if this is the case because $X$ and $Y$ are disjoint. In the summary, your new many-one reduction becomes $$f^\*(l) = \begin{cases}l\_0 \text{ if } f(l) \in Y \\ f(l) \text{ o.w. } \end{cases}$$ where $l\_0 \notin X \cup Y$. Verify that this will work.

2) Belonging to NP

Your idea was pretty good. It can be done several ways here, the easy one is to use the non-deterministic machine which firstly checks for belonging to $Y$, if yes - accept, if no - run the n-d machine for $X$ which exists because $X \in NP$.

Hope this helps.

# Answer
> 0 votes
$Y$ is finite, hence $Y=(X\cup Y)\setminus X$ is finite. So $Y$ is in $P$ and has a poly-time decider $D\_y$.

Let's build the polynomial function $f$ from $x$ to $X\cup Y$ on input $x$:

1. if $D\_y$ accepts $x$, return $l\_0$ (where $l\_0 \notin X\cup Y$)
2. else, return $x$

This is of course UNDER the assumption that $X\cup Y$ isn't trivial.

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


# Question
Title: Is the halting problem solvable for NPDAs?
After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my prior question:

1. arrive at the same state as you were in previously
2. with the same top symbol as you had last time
3. without consuming anything on the stack, and
4. without consuming any input.

But is my last question actually unanswerable because we cannot, in fact, determine whether a NPDA will halt? Is the halting problem even solvable for NPDAs?

# Answer
> 1 votes
There is no "minimal normal form" or the like for PDAs. If there was, a first step would be to minimize the PDA. This minimal type of machine would certainly not allow pathological examples like the one in your other post. We can, however, do something similar.

You can convert any NPDA to an equivalent context-free grammar. For these there are ways to remove useless rules and simplify them, and there are normal forms (Greibach and Chomsky). Definitely GNF allows answering the "halting problem", because a word of length n is generated in n steps. Going from GNF back to a PDA you get one with a similar property.

Maybe this method is not satisfactory for you, because you would like a more direct analysis of the given NPDA. But as you have observed, this can be very hard, because of possible very complex epsilon-loops.

To summarize: it is decidable whether for a given NPDA, there exists an equivalent one that always halts. But probably this is always true, because there is (e.g. Greibach NF for all context-free languages).

But you ask about a given PDA, not about whether a halting one exists for the same language. Thus for an answer to your question, one might have to analyze which kind of thing the mentioned grammar transformations eliminate and what that means in terms of PDAs.

Therefore, there is strong evidence that the question is decidable, but I have no definite method. In the transformations, one does not detect whether "useless" loops in the PDA/grammar would halt or not - they are simply eliminated, all of them.

---
Tags: pushdown-automata, nondeterminism, halting-problem
---


# Question
Title: Finding a cycle in a graph with the biggest value (the sum of all edges)
I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred solution is via backtracking.

My idea was to :

1. backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
2. then verify if the subgraph is connected
3. then verify if a source vertex of any edge is in the subgraph is used only once
4. and then connecting the first vertex with the last one, thus forming a cycle.
5. If the sum of all weights is \> then max, max = sum.

However, this solution doesn't work correctly on any almost any vertex. It finds a cycle, but it never finds the biggest one. Could you help me fix my algorithm? Thanks!

# Answer
You should note that this problem is NP-hard (i.e., when all edges have uniform weight, a cycle of maximum weight is a Hamiltonian cycle). So unless your inputs are small or somehow usefully structured, it's probably a better idea to go for heuristics since there is likely no polynomial-time algorithm.

To fix your exact algorithm, possibly with a few tricks to speed things up as well, you can have a look at the description of an algorithm given by Rubin \[1\].

---

\[1\] Rubin, Frank. "A search procedure for Hamilton paths and circuits." Journal of the ACM (JACM) 21.4 (1974): 576-580.
> 1 votes

---
Tags: graphs
---


# Question
Title: Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?
Wikipedia here https://en.m.wikipedia.org/wiki/Selection\_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The point which is unclear is whether K is required to be constant or at least independent of size of N.

I saw this issue being discussed on this site here : https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on But people there in the comments seem to claim that K is fixed.

The point which I don't understand is, if k is indeed needed to be fixed.. then what's the point of this algorithm of select and quicksort?

Why can't we just perform like bubble sort K times if K is fixed it wouldn't be more than K\*N which is O(n) . So what's the problem of achiving it in O(n) if k is fixed.

# Answer
> 2 votes
There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect.

Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)$ which is $O(n^2)$ unless $k$ is somehow restricted.

But the Quickselect algorithm is stochastic $O(n)$ and can be made worst-case $O(n)$ by using the median-of-medians algorithm to select the pivot. (Median-of-medians is too slow for practical use, but it proves that $O(n)$ is possible.) Quickselect does not require $k$ to be fixed.

# Answer
> 2 votes
The algorithm that uses "sort of quicksort" to find the $k$-th smallest (or largest) element is generally called quickselect.

Here is the precise meaning of "the average complexity of quickselect is $O(n)$" as commonly understood. Or one of its precise meanings.

### the precise statement

There exists a constant $c$ such that given two integer $n$ and $k$ such that $1\le k\le n$, the average number of comparisons used in the quickselect algorithm that finds the $k$-th smallest element in an array of $n$ elements is no more than $cn$.

---

$100$ should be a good value for $c$ in general I believe, although it could possibly be as small as 4. Note that the upper bound $cn$ is independent of $k$. In other words, **$k$ is not required to be fixed.**

The same statement is not true if we use bubble sort instead of quickselect. We can show that bubble sort will make $\Theta(n^2)$ comparisons on average in order to find the $n/2$-th smallest element in an array of $n$ elements.

### What is "the average number of comparisons"?

One might ask further what is meant exactly by that "average number". One way to interpret is to assume that every possible permutation of the given $n$ elements is equally likely to happen. For example, we can let the given array be a permutation of $1, 2, \cdots, n$, with each permutation equally likely to occur. For a permutation $\sigma$, let $\\#(\sigma, k)$ be the number of comparisons used by the quickselect algorithm when the given array corresponds to $\sigma$. Then $$\text{average number of comparisons}=\frac{\sum\_{\sigma\text{ is a permutation of }1,2\cdots, n} \\#(\sigma,k)}{\text{number of permutations of }1,2,\cdots, n}$$

### Many variations

There are many versions of the quickselect algorithm. There are other common ways to compute the average number of comparisons as well. Whichever version of the quickselect algorithm will be applied and however the average number of comparisons will be computed, that precise statement is valid in general.

Instead of on average case, for some versions of the quickselect algorithm, the number of comparisons in the worse case is no more than $c'n$ for some constant $c'$.

### Exercise

Read quickselect, especially its section on time complexity, which explains the reason behind the bounds for time-complexity.

---
Tags: sorting, quicksort, partitions, selection-problem
---


# Question
Title: If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?
Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?

# Answer
There exists a reduction (many-to-one polynomial time) from a problem (or language) $A$ to a problem $B$, denoted $A \leq\_{\textsf{p}}^{\textsf{m}} B$, if there exists a function $f$, computable in polynomial time in the size of the entry, so that $x\in A \Leftrightarrow f(x) \in B$.

It means that if you are able to solve any instance of the problem $B$, then for an instance $x$ of the problem $A$, you can transform it into $f(x)$, solve it like a problem of $B$, and it gives you the answer for the instance $x$.

In your case, if $A \leq\_{\textsf{p}}^{\textsf{m}} B \leq\_{\textsf{p}}^{\textsf{m}} C \leq\_{\textsf{p}}^{\textsf{m}} D$ and $C$ is $\textsf{NP}$-hard, then it implies that $D$ is $\textsf{NP}$-hard. But if $C$ is $\textsf{NP}$, it implies that $A$ and $B$ are $\textsf{NP}$ (since hardness gives a lower bound and $\textsf{NP}$ gives an upper bound).

You can find a reference in the Arora-Barak, page 59 of the pdf, or the Cormen-Leiserson-Rivest-Stein, page 992 of the pdf.
> 2 votes

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


# Question
Title: Adding an ordered into a relationship without violating the functional dependencies
Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies:

$$A \to C$$ $$A \to B,D$$

is it possible to insert a tuple with $NULL$ values, without violating the functional dependencies? I understand the definition of functional dependencies but I've never actually thought about what would happen for $NULL$ values. On the one hand, if you consider $NULL$ as a value then yes but if you say that it's the absence of value, then you can't. But in the case of the possibility of adding the tuple, mentioned above, without violating the functional dependencies, what could you do?

# Answer
First of all, the classical relational theory does not include null values, and for this reason the concept of functional dependency (and violation of FD) is not defined in presence of such values.

Note that NULL is not a constant, neither a different value each time it is used. This can be seen if you try something like:

```
SELECT NULL = NULL;

```

the result is neither `TRUE` (the two values are in effect the same value) nor `FALSE` (the two values are different), but `NULL`, which means that we have no information at all about the real values (even if they exist or not!). And this is the foundamental reason for which it has no sense to consider or not a violation of a FD in presence of a null value.

For instance, considering your question, let's think about the meaning of a functional dependency. Since from the dependencies that you have listed we can derive `A -> D`, this means that each time in a tuple there is a certain value of the attribute `A`, there should be the same value of the attribute `D`. But if we have two tuples with the same value of `A`, and one of them has a `NULL` value for `D`, while the other has a normal value, this means that we do not know if the dependency is violated or not, since we do not know nothing about the value of the attribute specified as `NULL`. It could be unknown, and be the same, or different, or it could not be present. So nothing can be said about the violation.
> 1 votes

---
Tags: data-structures, database-theory, databases
---


title: Turing machine reduction task

text:
# Question
Title: Turing machine reduction task
I am having trouble solving the following task:

> Given is the language $$D=\\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\\}$$
>
> Prove that $D$ is not decidable by reducing $$A\_{\mathrm{TM}}=\\{\langle T, w \rangle \mid \text{$T$ is a Turing machine and $T$ accepts $w$}\\}$$ to $D$.

## My solution and proof idea

(I am not sure if they are correct.) Assume that $D$ is decidable. Let $R$ be a decider for $D$ and $S$ for $A\_{\mathrm{TM}}$. We know that $A\_{\mathrm{TM}}$ is not decidable. However, if we manage to show it is decidable using $R$ as subroutine, we derive a contradiction and have therefore shown that $R$ is not decidable either.

Now I have got to a point where I do not know further because I have problems finding ways of showig the contradiction since I cannot see a connection between entering all states and accepting input $w$. If the TM enters all states, it is still unclear if the input is also accepted.

I guess I have to run R on a modification of $T$ so that I can derive a contradiction.

# Answer
> 1 votes
Given a TM $T$, consider the machine $T'$ which, on input $w$, simulates $T$ on $w$ and enters a special state $q$ if and only if has determined that $T$ accepts $w$. Note you can easily guarantee $T'$ never enters $q$ prior to $T$ accepting $w$. Moreover, you can make sure that, once $T'$ enters $q$, it starts to cycle between all its states indefinitely. (For instance, have $T'$ write a special tape symbol so it knows it is supposed to do so.)

For an arbitrary $T$, producing the description of $T'$ is computable. I'll leave it to you to fill in the gaps so this is a full-fledged reduction.

---

As a rule of thumb, these exercises can usually be solved by producing description of machines (in this case, $T'$) which encode the answer to the original problem ($A\_{\mathrm{TM}}$) *in their own behavior*. In this particular case, the idea is to establish the equivalence between $T'$ entering all its states and $T$ accepting $w$.

# Answer
> 0 votes
GENERAL HINT: we know that $A\_{TM}$ is undecidable. So we know that a TM $V$ that can decide $A\_{TM}$ does not exist by definition. Now suppose that you have a TM $V\_{2}$ that can decide the language $D$. You need to find a way (and this is the hard part of the exercise which i leave to you) for produce the machine $V$ starting with $V\_{2}$. Now if you can do it, since $V$ does not exist, you can conclude that $V\_{2}$ cant exist neither because otherwise there would be a contradiction.

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


title: Pebble game lower bound?

text:
# Question
Title: Pebble game lower bound?
This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.

Why is it not considered proof of constructive example for a function in $NP$ which requires superlinear runtime?

# Answer
> 3 votes
The time hierarchy theorem gives, for every $k$, a function in P with a runtime lower bound of $\Omega(n^k)$. Unfortunately, this is not enough to separate P from NP: to do this, we need a function in NP with a *superpolynomial* runtime lower bound.

One popular approach for tackling the P vs NP question is via circuits. The best lower bounds for explicit functions are only linear. Perhaps this is the context in which you heard of *superlinear lower bounds* as a seeming barrier.

---
Tags: complexity-theory, turing-machines, time-complexity, np, lower-bounds
---


# Question
Title: Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular
I have been looking around for a good source to answer the following question. Have read a few different sources but have not found the answer I was looking for.

The question is:

> Give an example of an infinite set of:
>
> a. Regular languages whose union is a regular language
>
> b. Regular languages whose union is a non-regular language
>
> c. Non-regular languages whose union is a regular language
>
> d. Non-regular languages whose union is a non-regular language

I've used this post to answer part b, and I understand the method behind it (at least I think I do).

What is the right way to approach this question?

Wouldn't an infinite set of anything constitute a non-regular language, by definition?

# Answer
> 1 votes
a. is pretty easy. Just consider $\\{a\\}^\ast = \bigcup\_{i \in \mathbb{N}\_0} \\{a\\}^i$. This also answers the last question in your post (i.e., regular does not mean finite).

The answer to b., as you have said, can be found in the linked question.

Finally, for c. and d. you can use subsets of $\\{ 0^n 1^n \mid n \in \mathbb{N}\_0 \\}$ and $\\{ 1^n 0^n \mid n \in \mathbb{N}\_0 \\}$, which are both non-regular languages. Hint: The exercise text does not require the languages to be disjoint.

# Answer
> 1 votes
Regarding a and b, let us make the following observation:

> Every language is a union of regular languages.

This follows from the identity $$ L = \bigcup\_{w \in L} \\{w\\}. $$

For part c, it is easy to write $\Sigma^\*$ as a union of infinitely many distinct non-regular languages. Using your favorite non-regular language $L$, $$ \Sigma^\* = \bigcup\_{w \in \Sigma^\*} (L \cup \\{w\\}). $$

For part d, again take your favorite non-regular language $L$. Then $$ L = \bigcup\_{n=0}^\infty \\{ w \in L : |w| \geq n \\}. $$ Since $L$ is infinite, infinitely many of the summands would be distinct.

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


title: Shrinking Item 0-1 Knapsack problem

text:
# Question
Title: Shrinking Item 0-1 Knapsack problem
I have encountered a variant of the knapsack problem with shrinking items.

Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, but immediately after being put into the container the item shrinks by $W(n)$. This means that for every item IN the knapsack, weight and value are the same. (It is therefore also possible to look at this as a value-irrelevant "best fill only" 0-1 knapsack.)

So, in this case, one also needs to determine the proper order of items to insert and whether a specific item is legal in the combination before being put in the container.

I have already determined that order of insertion, given a valid collection, should be based on $W(n)+V(n)$ descending—but thus far I am failing to create a set of valid collections in anything under $O(2^n)$.

Dynamic programming solutions are failing me both because of the apparent interdependence of elements which makes memoization seemingly impossible.

I realize I have not given much here, but I could really use some help. How does one go about approaching this variant?

*If curious, the actual application is that we have a large number of different electrical appliances that all cause a known power surge when turned on and afterwards draw a set amount of power. We never want to trip a breaker, so the surge needs to be taken into account when figuring out how many at most we can turn on.*

# Answer
Maybe I misunderstood you, but we can definitely find a dynamic programming solution, a very similar one to the one for knapsack itself. Let $T\[i, b\]$ denote the maximum profit that can be made for the first $1 \leq i \leq n$ items, and $b$ is the remaining weight of the knapsack. Here is the recurrence.

$$T\[i, b\] = \begin{cases} 0 & \text{if } i =0 \vee b = 0 \\ T\[i - 1, b\] & \text{if } w(i) \> b \\ \max \\{T\[i - 1, b\], T\[i-1, b-V(i)\] + V(i)\\} & \text{if } w(i) \le b \end{cases}$$

For the base case, the 0th item doesn't exist so we have no profit. Similar for having run out of space.

Next, if $w(i) := W(i) + V(i) \> b$, then we obviously cannot add item $i$ to our knapsack, and must continue on.

In the last case, we have two choices, either not include the item, or include it. For the latter, we then have $b - V(i)$ weight remaining, and $V(i)$ extra profit.

This dynamic programming algorithm has a running time of $O(nB)$, which is pseudopolynomial. Returning $T\[n, B\]$ is your maximum profit for all your items.
> 1 votes

---
Tags: algorithms, dynamic-programming, knapsack-problems
---


# Question
Title: If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?
If we store a min heap of $n$ elements, $\color{Blue}{\[1,2, \dots n\]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are from $\color{Blue}1$ to $\color{Blue}n$)

# Answer
Let $D(i)$ denote the number of descendants of the $i$th node. In a min-heap, all $D(i)$ nodes below node $i$ must have a larger value than node $i$. Hence, the $n-D(i)$ largest values $n-D(i)+1,\ldots,n$ cannot be put in node $i$. It turns out that $n-D(i)$ can be put in node $i$, and so the maximum possible value for node $i$ is $n-D(i)$. To see how this can be achieved, fill in the descendants of node $i$ by $n-D(i)+1,\ldots,n$, and fill in the remaining nodes in any way so that the min-heap property is satisfied. The integers available for the parents of node $i$ are all less than $n-D(i)$ and so the min-heap property can be satisfied. The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of these siblings, all necessarily contain values smaller than node $i$ because the values larger than $n-D(i)$ have been used up, and this is fine because we want node $i$ to have the largest possible value. There is no violation of the min-heap property, which only concerns relations between a node and its parent (and therefore all its ancestors) or its children.

To obtain the smallest possible value for node $i$, let $A(i)$ denote the number of ancestors of node $i$. This value is the number of nodes in the unique path from the root to node $i$ (including the root node but not including node $i$). These $A(i)$ nodes must have values less than node $i$, and so the smallest possible value for node is at least $A(i)+1$. Is this bound achievable? Yes, put values $1,2,\ldots,A(i)+1$ as the values on the path from the root node to node $i$ (where node $i$ takes value $A(i)+1$). Observe that the remaining nodes can be filled in with the remaining values in such a way that the min-heap property is satisfied. The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of all these siblings, as well as the descendants of node $i$, will all have a larger value than $A(i)+1$, and this doesn't violate the min-heap property.
> 1 votes

# Answer
For a vertex $x$, let $a$ denote the number of vertices above $x$ (i.e., its parent, its grandparent, and so on), and let $b$ denote the number of descendants of $x$ (excluding $x$). Identifying $x$ with the number put in $x$, we see that $x \> a$ and $x + b \leq n$. This shows that $a+1 \leq x \leq n-b$. It is very likely that both extremes are achievable, and it could be a nice exercise to confirm or refute this conjecture.
> 0 votes

---
Tags: algorithms, data-structures, heaps, heap-sort
---


# Question
Title: Algorithm for factoring elements of permutation groups?
You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). There are several algorithms for solving Rubik's cubes. Are there any algorithms for the general problem of factoring permutations?

# Answer
Let $S$ be a set of generators in $S\_n$ such that $S$ is closed under inverses, and let $h \in S\_n$. The goal is to express $h$ as a product of elements of $S$. A graph-theoretic approach to solve this problem is to construct the Cayley digraph of $S\_n$ with respect to generating set $S$, denoted $G = Cay(S\_n,S)$, which is defined to be the graph with vertex set $S\_n$ and arc set $\\{ (g,sg): g \in S\_n, s \in S\\}$. One can also construct an arc-labeled graph where arc $(g,sg)$ has label $s$.

Thus, if $b = (1,2,3,4,5)$, then there is an arc in the Cayley graph $G$ from the identity vertex $e$ to vertex $b$, from vertex $b$ to vertex $b^2$, etc. If $a,b$ are generators, then there is a directed path $e, a, ba, aba $ from the identity vertex $e$ to vertex $aba$. The goal is to find a directed path from $e$ to $h$.

This can be done by constructing the Cayley graph and running a shortest path algorithm such as BFS to find a shortest $e-h$ path. The SAGE program below finds a shortest expression for $(4,5)$ as a product of elements from generator set $\\{(1,2), (1,2,3,4,5), (1,5,4,3,2)\\}$ \- both the path and the arc labels (i.e. generator elements) are shown in the output below:

```
a = PermutationGroupElement('(1,2)')
b = PermutationGroupElement('(1,2,3,4,5)')
e = PermutationGroupElement('()')
S = [a,b, b.inverse()] #generators, closed under inverses
S5 = PermutationGroup(S)
G = S5.cayley_graph(generators=S)
V = G.vertices()
p = G.shortest_path(V[0], V[1])
genterms = [p[i+1] * p[i].inverse() for i in range(len(p)-1)]
print("vertices on shortest path: \n" + str(p))
print("generators on shortest path: \n" + str(genterms))

Output:

vertices on shortest path:
[(), (1,2,3,4,5), (1,3,5,2,4), (1,3,5)(2,4), (1,2,3,4), (4,5)]
generators on shortest path:
[(1,2,3,4,5), (1,2,3,4,5), (4,5), (1,4,5,3,2), (1,4,5,3,2)]

```
> 2 votes

# Answer
It seems that your problem could be stated in terms of finding paths in Cayley Graphs, which might interest you:

Cayley Graph - Wikipedia
> 2 votes

---
Tags: algorithms, permutations, group-theory
---


# Question
Title: Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?
Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?

Is it because the "modern OOP" that exists in programming languages like C++ and C# and Java are "better" than "real OOP", or are there other reasons?

# Answer
> 1 votes
"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them." - Alan Kay.
I would like to point that there is no single evidence of term OOP being coined by Alan Kay (if you find one, please share).

About C++ Alan gave statement: "I invented the term object-oriented, and I can tell you that C++ wasn't what I had in mind".

Other languages that may fall into "real OOP" is self programming language and probably Squeak and Objective-C.

When languages switched from messages to params passing, becoming bidirectional, it broke initial assumptions. Alan have pointed flaws in Simula design, so this one also do not count.

It is impossible to say that some languages are "better" than others, but being "real OOP" according to definition is some road taken by one influential author. Term OOP and class based programming was introduced in Simula, long before "real OOP" was supposedly coined.

All modern languages took other road and "modern OOP" is more down-to-earth, no asynchronous agents passing messages, microservices with own memory, everything being object by default.

Since there are performance hits in every step and there is no single reference gathering what it should do beside notes like actor-based programming is a way to go, because programmers should consider interactions of objects and interactions with users, we can safely assume "real OOP" by Alan Kay is only about road taken by him and not really implementable by others, so only smalltalk and squeak may be truly covered and other languages followed more pragmatic, expressive and performant way.

---
Tags: programming-languages, object-oriented
---


# Question
Title: A simple clarification on polynomial hierarchy
$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma\_2^P\cap\Pi\_2^P$ holds. So according to current knowledge is following true?

1. $P^{\Sigma\_2^P\cup\Pi\_2^P}\subseteq BPP^{NP}\subseteq(\Sigma\_2^P\cap\Pi\_2^P)^{NP}\subseteq\Sigma\_3^P\cap\Pi\_3^P$?
2. Is $P^{\Sigma\_2^P\cup\Pi\_2^P}$ the largest standard polynomial hierarchy class in $BPP^{NP}$ and is $(\Sigma\_2^P\cap\Pi\_2^P)^{NP}$ the smallest standard polynomial hierarchy class containing $BPP^{NP}$?

# Answer
The NP-machine hypothesis implies that $BPP^{NP}=P^{NP}$.

So combining with the hypothesis that $PH$ does not collapse, this will falsify the proposition that $P^{\Sigma\_2^p\cup\Pi\_2^p}\subseteq BPP^{NP}$.

Reference for NP-machine hypothesis and its aforementioned consequence: https://www.researchgate.net/publication/225526797\_Hardness\_Hypotheses\_Derandomization\_and\_Circuit\_Complexity
> 0 votes

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


# Question
Title: Is λx. a valid Lamda Calculus abstraction?
For demonstration purposes I was wondering about some very easy to grasp LC abstractions and I came to the idea of a function that simply eats its argument, and nothing more.

If you apply λx. (Yes no lambda term after the point) to an argument the abstraction reduces to nothing.

Although this isn't very useful for computation maybe, do you think the idea itself is valid or not?

---

Ok thanks everyone. Although I still like to tinker with the idea in my head, I understand it's simply not an option to use this throwaway function when dealing with LC.

Every application in LC returns an expression. There are no birds in the forest of Smullyan that can not sing.

Thanks again.

# Answer
> 3 votes
No, $\lambda x.$ is not a syntactically valid expression. By the definition of the syntax of lamda terms,

> $\lambda x.M$ is a term if $x$ is a variable and $M$ is a term.

You need a term $M$ to abstract over, and there are no empty terms. (This also means that there can be no application that reduces to "nothing". Any lambda term must consist of at least an atom (= a variable or a constant)). So $\lambda x.$ is not a term.

# Answer
> 2 votes
I am sorry but writing just λx. Is not usefull in any way. And it is not a function that eats his argument, it is a undefined function like writing $f(x)=$

# Answer
> 2 votes
Just writing $\lambda x.$ is not an LC expression. It's syntactically not correct. There are clear rules about the syntax of LC terms and in the case of a $\lambda$-expression these rules are:

If $x$ is a variable and $t$ is a LC expression, then $(\lambda x.t)$ is also an LC expression.

Note that in order to write a $\lambda$-expression, the definition **requires** both a variable **and** another LC expression.

---
Tags: lambda-calculus
---


# Question
Title: Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$
Is the complement of the following language a regular language? $$L = \\{ x \in \\{a,b,c,d\\}^\* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|\_a - |y|\_b|\leq 10 \\}$$

My first thought is that it is not a regular language because finite automata can't store the number of $a$ in $x$ and the number of $b$ in $x$, but I guess I do not understand what is the meaning of the prefix here. Could someone help me?

# Answer
First of all, a language is regular iff its complement is regular. Therefore it suffices to determine whether $L$ itself is regular.

Indeed, since $\epsilon$ is a prefix of every word, and $\epsilon$ satisfies $||\epsilon|\_a-|\epsilon|\_b| \leq 10$, we see that $L = \Sigma^\*$, and in particular $L$ is regular.

Matters become more interesting if we replace the condition $||y|\_a-|y|\_b| \leq 10$ by its complement $||y|\_a-|y|\_b| \> 10$. In this case the language $L$ is still regular, but the argument is a bit more complicated. Let us show that the following language is regular: $$ L' = \\{ x \in \\{a,b,c,d\\}^\* : \text{some prefix $y$ of $x$ satisfies $||y|\_a-|y|\_b| \> 10$}\\}. $$ (Its complement is the language of all words, all of whose prefixes satisfy $||y|\_a-|y|\_b| \leq 10$.)

We construct a DFA with 22 states $\\{q\_{-10},\ldots,q\_{+10},q\_f\\}$. The initial state is $q\_0$, and the unique final state is $q\_f$. The transition function is given by the following table: $$ \begin{array}{c|cccc} q & \delta(q,a) & \delta(q,b) & \delta(q,c) & \delta(q,d) \\\hline q\_{-10} & q\_{-9} & q\_f & q\_{-10} & q\_{-10} \\ q\_{-9} & q\_{-8} & q\_{-10} & q\_{-9} & q\_{-9} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ q\_9 & q\_{10} & q\_8 & q\_9 & q\_9 \\ q\_{10} & q\_f & q\_9 & q\_{10} & q\_{10} \\ q\_f & q\_f & q\_f & q\_f & q\_f \end{array} $$ If the current prefix satisfies $||y|\_a-|y|\_b| \> 10$, the DFA moves to state $q\_f$ and stays there. Otherwise, the DFA is in state $q\_i$, where $i = |y|\_a - |y|\_b$.
> 4 votes

---
Tags: regular-languages, context-free
---


# Question
Title: Average codeword length in a Huffman tree is $\Omega(\log n)$
> Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.

My try:

I think that the worst case is when the tree is full and all the characters are in the highest level.

Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.

Am I missing something?

# Answer
> 4 votes
This answer assumes that by *average* you mean just that – the sum of all codeword lengths divided by $n$.

Let us show that *any* prefix code satisfies your property. Consider any prefix code whose codewords have lengths $\ell\_1,\ldots,\ell\_n$. Kraft's inequality shows that $$ 2^{-\ell\_1} + \cdots + 2^{-\ell\_n} \leq 1. $$ The function $x \mapsto 2^{-x}$ is convex, hence $$ \frac{1}{n} \geq \frac{2^{-\ell\_1} + \cdots + 2^{-\ell\_n}}{n} \geq 2^{-(\ell\_1+\cdots+\ell\_n)/n}. $$ It follows that $$ \frac{\ell\_1 + \cdots + \ell\_n}{n} \geq \log\_2 n. $$ Since $x \mapsto 2^{-x}$ is strictly convex, there can be equality only if $\ell\_1 = \cdots = \ell\_n$, that is, only if all codewords are of length exactly $\log\_2 n$. That can only happen if $n$ is a power of 2. This leaves open the following question:

> What is the minimum average codeword length of a prefix code on $n$ symbols?

(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $i$th symbol is $2^{-\ell\_i}$.)

To answer this, let us note that convexity implies that if $a \< b$ then $$ 2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}. $$ (We can also see this directly: without loss of generality $a=0$, and then we need to prove $1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$, that is, $1/2 \geq 2^{-b}$, which follows from $b \geq 1$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $\ell,\ell+1$. If $n = 2^k + m$, where $0 \leq m \< 2^k$, then this solution must consist of $2^k - m$ many $k$'s and $2m$ many $k+1$'s. Hence the optimal average codeword length is $$ \frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}. $$

# Answer
> 0 votes
If by average you mean the average length of the n codewords, then if the k-th symbol has probability $2^{-k}$, the length of the code words ranges from 1 to n-1, with average about n/2.

If by average you mean the average length of a codeword in a compressed message, then if the first symbol has probability 1-eps, and the others all have probability (1 - eps) / (n - 1), then the average length of a codeword in a compressed message is just a bit more than 1.

---
Tags: algorithms, binary-trees, huffman-coding
---


# Question
Title: Number of possible heaps on $\{1,...,2^h-1\}$
> Let $C\_h$ be the number of possible heaps for the set of keys $\\{1,...,2^h-1\\}$. Determine a recurrence relation for $C\_h$ via the substitution method and prove it.
>
> **Definition**
>
> A binary tree is *ordered* if the key at every node is smaller than the keys at its children.
>
> An ordered binary tree of height $h$ is called a *heap* if the tree induced by all levels except the last is a complete binary tree and all leaves are "as much to the left as possible".

So what I've come up with is this expression:

$$C\_h=\displaystyle\prod\_{n=1}^{h} (2^{i-1})!$$

The intuition behind it is that with every increment by $1$ of $h$ the tree gains $2$ times more leaves than before and the possibilities of ordering these leaves can be determined via the factorial operation. Does that make sense?

# Answer
> 2 votes
When $n = 2^h-1$, the heap is just a complete binary tree of height $h$. Clearly $C\_0 = C\_1 = 1$. For $h \> 1$, we can decompose the heap as follows:

* The root must be 1.
* Each of the two children are heaps of size $2^{h-1}-1$ on their respective values.
* The $2^h-2$ values other than the root can be divided arbitrarily to the two children (each gets exactly $2^{h-1}-1$).

This gives us the recurrence $$ C\_h = \binom{2^h-2}{2^{h-1}-1} C\_{h-1}^2. $$ Unrolling this recurrence gives $$ C\_h = \binom{2^h-2}{2^{h-1}-1} \binom{2^{h-1}-2}{2^{h-2}-1}^2 \binom{2^{h-2}-2}{2^{h-3}-1}^4 \cdots \binom{2^1-2}{2^0-1}^{2^{h-1}}. $$ This is A056972. You can prove inductively that $$ C\_h = \frac{(2^h-1)!}{\prod\_{k=1}^h (2^k-1)^{2^{h-k}}}. $$ This formula also has a combinatorial interpretation. Start with one of the $(2^h-1)!$ possible permutations of keys. Swap the root with the minimal key (1), and then do the same recursively on both children. This gives a heap. Going in the other direction, we can start with a heap, and then go over all internal nodes in non-increasing order of depth, swapping the root with an arbitrary node in the subtree. There are $2^{h-k}$ nodes at depth $h-k$, and each of them has $2^k-1$ nodes at its subtree. This gives the denominator.

# Answer
> 3 votes
The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $\[\\!\[1, 2^h-1\]\\!\]$, then it is also a **perfect tree** of height $h$.

Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C\_{h-1}$ appears). You just have to think of how to split $2^{h}-2$ keys between left and right (the key of the root is uniquely determined, since it is a heap).

I will edit this answer if it is not clear enough.

---
Tags: combinatorics, recurrence-relation, heaps, enumeration, check-my-answer
---


# Question
Title: Find typing derivation of STLC term with reference types
The problem is to find the typing derivation of a term of the call-by-value STLC extended with reference types. The evaluation and typing rules for this language is given in Types and Programming Languages by Pierce on page 166. The term is $$ t = (\lambda a:\mathrm{Ref}\mathrm{Bool}. \mathrm{if}\\, \mathrm{true}\\,\mathrm{then}\\, !l\_1\\, !a\\, \mathrm{else}\\,0)\\,\mathrm{ref}\\,\mathrm{true} $$ where $$ \mu(l\_1)=\lambda x:\mathrm{Int}.x $$ So I need to find $\Gamma, \Sigma,$ and $T$ so that $$ \Gamma\\,|\\,\Sigma\vdash t:T $$ I know you are supposed to show your work, but my problem is that $t$ doesn't seem well-typed... What am I missing?

# Answer
The expression $t$ does not contain any free variables, so one can start typing it with an empty context: $\emptyset\\,|\\,\Sigma~\vdash~t : \mathrm{Int}$, and attempt to build the full derivation tree in a bottom-up way.

The tricky part of the typing derivation is where we try to type-check the subexpression $(!l\_1\\,!a)$. Because $(!l\_1\\,!a)$ lies in the body of a $\lambda$-expression which introduces the variable $a$ of type $\text{Ref Bool}$, at that point the context will be extended with an entry $(a : \mathrm{Ref~Bool})$, therefore $\Gamma=\emptyset,a : \mathrm{Ref~Bool}$.

$\dfrac{\dfrac{(a)}{\Gamma\\,|\\,\Sigma~\vdash~!l\_1 : \mathrm{Bool \to Int}}{\text{T-Loc}}~~~~~~~~~~~~~\dfrac{\Gamma\\,|\\,\Sigma~\vdash~a : \mathrm{Ref~Bool}}{\Gamma\\,|\\,\Sigma~\vdash~!a : \mathrm{Bool}}{\text{T-Var}}}{\Gamma\\,|\\,\Sigma~\vdash~!l\_1\\,!a : \mathrm{Int}}{\text{T-App}}$

Completing the above sub-derivation by filling in the missing premise in $(a)$, shows what $\Sigma$ we must choose so that $t$ is typable. From the $\text{T-Loc}$ rule, clearly $\Sigma$ must contain the entry $(l\_1:\mathrm{Bool \to Int})$.

This contradicts the expectation that $\Sigma(l\_1) = \mathrm{Int \to Int}$. But this expectation is there only because we know that $\mu(l\_1)$ is a term of type $\mathrm{Int \to Int}$. However, $\mu$ plays no role in the typing of an expression. It only plays a role in the evaluation process.

What is violated here is not the typing of $t$. Indeed, $t$ is straight-forwardly typable by following the typing rules and choosing appropriate $\Gamma$ and $\Sigma$. What is violated is the typing of $\mu$. Following the theory and notation of the book, the judgment $\Gamma\\,|\\,\Sigma\vdash\mu$ does not hold. Because of this, the preservation theorem does not apply and if you try to evaluate $t$, a run-time error will occur.
> 2 votes

---
Tags: lambda-calculus, type-theory, typing, types-and-programming-languages
---


# Question
Title: Suffix array and counting distinct substrings of specific length
I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.

I started with the algorithm for counting ALL distinct substrings. I solved it after this explanation: https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/ . The problem right now is that I can't figure out how to only count the substrings of my given length, and not all possibilities.

I also computed the array which tells me how many suffixes are lexicographically smaller than suffix\_array\[i\].

Any ideas what I could use to do it?

# Answer
The geeksforgeeks solution gives an efficient algorithm that accomplishes the following:

* Sorts the suffixes of the input string in lexicographic order.
* For every two adjacent suffixes in this order, finds the longest common prefix.

If you are after the number of distinct substrings of length $\ell$, you should proceed as follows:

* If the first suffix has length at least $\ell$, initialize your counter with 1, otherwise with 0.
* Now go over all the suffixes in lexicographic order. If the new suffix has length at least $\ell$ and the lcp with the preceding suffix has length smaller than $\ell$, then increment the counter.

For example, suppose that the string is `ababa`, and you're after substrings of length $\ell = 3$. The ordered suffixes are `a`, `aba`, `ababa`, `ba`, `baba`. The algorithm proceeds as follows:

* The first suffix `a` is shorter than $\ell$, so the counter starts at 0.
* The second suffix `aba` has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered `aba`.)
* The third suffix `ababa` has length at least $\ell$, but the lcp with the preceding suffix also has length at least $\ell$.
* The fourth suffix `ba` has length less than $\ell$.
* The fifth suffix `baba` has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered `bab`.)
> 0 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?
For a string $w$, $M\_w$ denotes the Turing machine whose encoding is $w$.

I want to reduce the language $L=\\{w \mid |T(M\_w)| \geq 42\\}$ to $H\_0 = \\{w \mid M\_w \text{ halts on } \epsilon\\}$, but I can't find a way to define an algorithm that halts only if $w \in L$. Either way:

* if $w \in L$ I would have to find at least 42 words that are in $T(M\_w)$, which might be undecidable for certain languages.
* if $w \notin L$ then $M\_w$ would accept only 41 or less words. Then we do know, that the language $T(M\_w)$ is regular, but still we can't test if the language is regular or not.

Simply trying random words until we have at least 42 doesn't work as for some words the TM will not halt.

Is there any idea I could try? Or in other words: how would one prove $L \leq H\_0 $?

# Answer
> 2 votes
This answer assumes that $T(w)$ is the set of inputs that the Turing machine $M\_w$ halts on.

Given a Turing machine $M$, construct a new Turing machine which runs $M$ in parallel on all inputs. Once $M$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.)

In order to run $M$ on infinitely many inputs, you do the following:

* Start with some enumeration $x\_1,x\_2,\ldots$ of all inputs.
* Run $M$ for one step on $x\_1$.
* Run $M$ for one step on $x\_1,x\_2$.
* Run $M$ for one step on $x\_1,x\_2,x\_3$.
* And so on.

This is known as *dovetailing*.

The argument above reduces $L$ to the halting problem, and so shows that $L$ is r.e. We can also reduce the halting problem to $L$, hence showing that $L$ is r.e.-complete. To do this, suppose that we are given a Turing machine $M$ as input to $H\_0$. We construct a new Turing machine which:

* On input $\epsilon$, transfers control to $M$.
* On input $0,00,\ldots,0^{41}$, halts.
* On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H\_0$.

---
Tags: formal-languages, turing-machines, reductions, proof-techniques
---


title: Maximum weight vertex-disjoint paths

text:
# Question
Title: Maximum weight vertex-disjoint paths
I have a complete (every vertex is connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large as possible.

To me this sound like a mix of the longest path problem (NP-complete) and minimum spanning tree. Finding the best solution is not required, so maybe some greedy algorithm or something would be a good fit.

Any ideas and algorithms on how to approach this problem?

# Answer
This is not NP-Complete as far as I know. Below is a way to solve it.

You can convert the problem to finding the minimal path cover of your graph by making all the weights negative. The minimal path cover is a collection of disjoint paths covering all vertices.

One way of solving this is to convert your graph into a bipartite graph by doubling the vertices and making sure every edge goes from one side to the other. You then find the maximum bipartite matching, which will give you all the edges used in the disjoint path covers, and you can then find the paths from this set.

To get the maximum bipartite matching you can convert the graph into a flow network with unit weights on edges and use Ford-Fulkerson algorithm. All edges in the max flow will be in the maximum bipartite matching. You can then stitch the edges together as there will be only one way to assemble it with minimum number of paths.
> 0 votes

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Prove that the upper bound in the Noiseless-coding theorem is strict
Given a probability distribution $p$ across an alphabet, we define redundancy as:

Expected Length of codewords - entropy of p = $\ E(S) - h(p)$

Prove that for each $\epsilon$ with $0 \le \epsilon \lt 1$ there exists a $p$ such that the optimal encoding has redundancy $ \epsilon$.

**Attempts**

I have tried constructing a probability distribution like $p\_o = \epsilon, p\_1 = 1 - \epsilon $ based on a previous answer, but I can't get it to work.

Any help would be much appreciated.

**Edit:**

The solution I think I have found is mapped below.

redundancy = $E(S) - h(p) = \sum p\_is\_i + \sum p\_ilogp\_i$. We want to show that for a given $\epsilon$, we can find a $p$ that makes redundancy = $\epsilon$. So $\sum p\_is\_i + \sum p\_ilogp\_i = \epsilon ==\> \sum p\_is\_i = -\sum p\_ilogp\_i + \epsilon$.

We know the optimal value for $s\_i$ will be less than $-logp\_i + 1$, so we can write all $s\_i$ as $s\_i = -logp\_i+\alpha\_i$.

Now, $\sum p\_is\_i = -\sum p\_ilogp\_i + \epsilon ==\> \sum p\_i(-logp\_i + \alpha\_i) = -\sum p\_ilogp\_i + \epsilon ==\> \sum p\_i\alpha\_i = \epsilon$.

Intuitively I feel that you can always find a p so that the above is true for $epsilon$, because the $\alpha$ values are governed by how far away from a power of two your $m$ is, but I am not sure how to prove this last step.

# Answer
Take the probability distribution that you consider: there are two symbols, one with probability $\delta$, the other with probability $1-\delta$.

Any minimum redundancy code for this distribution has average codeword length $1$. Therefore the redundancy is $1 - h(\delta)$. Since $h(1/2) = 1$, $\lim\_{\delta\to0} h(\delta)=0$ and $h$ is continuous, for every $0 \< \gamma \leq 1$ you can find $\delta \> 0$ such that $h(\delta) = \gamma$. Choosing $\gamma = 1 - \epsilon$, we get a distribution whose redundancy is $1-\gamma = \epsilon$.

It is natural to "outlaw" such distributions by requiring all probabilities to be smaller than some $\kappa$. For small $\kappa$, we can no longer find distributions whose redundancy is close to 1. It is natural to conjecture that as $\kappa$ goes to zero, the maximum redundancy also goes to zero. However, this is not the case: for arbitrarily small $\kappa$, there are distributions whose redundancy is roughly 0.086. See Gallager's Variations on a theme by Huffman, which establishes that the limiting value of the maximum redundancy is (roughly) 0.086.
> 1 votes

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


# Question
Title: Find the cheapest combination of raw foods that fulfill nutritional requirements
I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples allowed) with the lowest total price.

Does anyone have any advice as to how to approach this problem? Is there a certain algorithm that exists that takes in a list of possible items, and finds a permutation that minimizes one property of the item(s), in this case the price, and also makes sure that the sum of each property meets a certain range, in this case nutritional properties like carbs and protein? Any advice is greatly appreciated. Thanks!

# Answer
> 1 votes
Use integer linear programming. Suppose you have $n$ foods. Let $x\_1,\dots,x\_n$ be zero-or-one variables, with the intention that $x\_i=1$ means you include food $i$ in the combination. Then the price is a linear function of these $x$'s, so that's your objective function you are minimizing. If you want the total carbs to be within a range, you can express that as a linear inequality (e.g., $\ell \le c\_1 x\_1 + \dots + c\_n x\_n \le u$, where $\ell,u$ are the lower and upper bounds of the range and $c\_i$ is the amount of carbs in food $i$). Feed this to an off-the-shelf ILP solver, and it should give you the optimal answer.

# Answer
> 1 votes
Since you are asking in Computer Science, I very much recommend George Dantzig's "Linear Programming and Extensions". It explains linear programming in a way that a normal human being (like me) can understand. The link has links to three .pdf files of this book.

https://www.rand.org/pubs/reports/R366.html

PS. D.W.'s recommendation to look at integer linear programming (instead of just linear programming) is important if you have food items that you can only buy in discrete sizes. For example, you can have an arbitrary amount of strawberry jam, but you must have no apples, 1 apple, two apple's, three apples, you can't have 1.7206 apples.

Solving the linear programming problem and then for example rounding the number of apples to 2 won't give optimal results. But you can take your equations, then once add a condition "apples \<= 1" and then add a condition "apples \>= 2". Solve both systems, and take the one that is better. This works well enough if you have only few items that are discrete.

# Answer
> 0 votes
At the outset, I'll write this up in Java, or at least show my line of thinking from a Java standpoint.

Given that we're looking at Food items, we'll define a Food class that has:

A field/attribute for type of food (In our case, we'll take "raw" and "un-raw"). A field/attribute for the name of the food. A field/attribute for the price of the food.

Note that I am not taking into consideration the actual caloric properties or anything health-associated for now. If I can come back to this answer later, I'll see if I have anything to offer on that front.

We'll define this class and then for our algorithm we'll take in as input a List, or informally speaking, a list of Objects that are all of type Food. We'll denote this as *List A.*

To solve the problem of minimizing price, we could use some sorting algorithm (quicksort, right?) on the item prices, and once we've sorted in ascending order, iterate through this list and add to a new List, denoted as *List B*, **only** those items which have the type "raw."

Your final *List B* would have only raw foods and those raw foods in ascending order of price.

## END OF INITIAL ANSWER

Now let's take a look at this caloric/health-property part of the problem. We'll say that you have three inputs for the algorithm:

1. *A List of Food items*
2. *A price bound, expressed as a double/decimal number*
3. *A calorie bound, expressed as a whole number*

We'll see that what you're doing is minimizing on two fronts instead of one. The first front we minimize on is price. What we'll do is we'll iterate through *List A* and add to *List B* only those items that are raw.

## SORTING ON PRICE, LIST B

We'll then sort through *List B* using price, so that we have raw foods arranged in ascending order of price. We'll take the sum of all the items' prices and see where we're at. Denote this as *initialTotal.*

If we're within the price bound, then we're good, and if we aren't... then there's problems. We may have to take out certain items based on price, but the interesting thing is that we'll have to also consider caloric intake there...

Let's assume you're within the price bound, so *initialTotal* \<= *priceBound*.

## SORTING ON CALORIES, LIST B

We'll add up all the calories of all the items in *List B*, and denote this as *initialCal*.

If we're within the caloric bound, denoted as *calBound*, then *initialCal* \<= *calBound*. If both conditions relating to total price and total cal hold, then we can return *List B* as it is.

Let us suggest the calories are off. What we can do is we can sort on the calories, and reorder *List B*. We could potentially reverse-sort on *List B* so we see the most caloric-heavy foods first, and the least caloric-heavy foods last.

We may be able to isolate some subset of *List B* as having the most caloric-heavy foods, say the *k* element subset of foods within *List B*.

We need to find the combination then of foods to get rid of such that *initialCal* \<= *calBound*. Whatever remains, we can return.

I know this is a rather long answer, but hopefully in a few days I may be able to come and answer some more/significantly reformat the answer to be more helpful. My apologies for this being incomplete, as it were. I'll try to fix this soon.

Good luck with the diet!

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


# Question
Title: Does dependent type checkers need to store lambda parameter type in their core language?
"Core language" refers to the exported well-typed terms that can be evaluated (or reduced).

In the core language of MiniAgda, a dependently-typed language, the parameter type of a lambda is not stored anywhere. So does in Mini-TT and Agda.

However, Idris does store lambda parameter type in its core language.

I wonder do we need/needn't to store parameter type (or, under what condition do we need/needn't to store it)? Because according the surface syntax of all these languages, they don't have lambdas with their parameters explicitly-annotated. For Idris here's a link showing that Idris does not have lambda with type annotation.

# Answer
> 2 votes
In general, type inference for dependent types is undecidable. This means that when checking a function, we need *some* way to know what type its argument has.

In the case of Idris, they simply annotate lambdas with parameter types. This is *very* common in type theory, since it makes your type system syntax directed in a very simple way. When you do this, you can usually view the typing judgment as having the type as an output parameter (i.e. given the input term, you can determine its type).

I don't know what MiniAgda does in particular, but the other main way is to treat the type as an *input* to the checking judgment. So in this case, you don't need to store the type of the function in the AST, but when typechecking, you will use the context in some way to get the type of the function (i.e. from an annotation).

Generally this is done using bidirectional typechecking. This paper and this post both give excellent overviews of how this can be done in practice.

---
Tags: dependent-types
---


# Question
Title: Calculate Stages in Non-Pipelined Processor
I have tried to attempt a question where I have to find the number of stages for non-pipelined processor(8085) for below program :-

```
MOV #40, R00
MOV #50, R01
MOV #60, R02
SUB R02, R01
ADD R02, R01
INC R01
SUB R00, R02
HLT

```

What will be the no. of stages and there list here?

# Answer
That processor should come with a manual. If yes, you can use the information in the manual. If no, you can google for the manual, like "8085 manual". The number of cycles and states for each instruction are in chapter 3, for example CPI = 7 states. Then you add up the numbers.
> 0 votes

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


# Question
Title: Description for languages that can be solved in time(n)?
How can one describe all languages that are in $\mathrm{TIME}(n)$?

It can't be all the regular languages only, as for example $L = \\{a^n b^nw \mid w \in \Sigma^\* \land n \geq 1\\}$ is not regular but in $\mathrm{TIME}(n)$. Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

So, is there a nice description for all $L \in \mathrm{TIME}(n)$?

# Answer
> 2 votes
We're not good at characterizing languages that can be decided in deterministic polynomial time. There are multiple characterizations of $\mathrm{NP}$ (e.g., nondeterministic Turing machines, polynomial witnesses, existential second-order logic), but $\mathrm{P}$ seems to be just "stuff you can do in polynomial time on a Turing machine."

Similarly, it's unlikely that there's any alternative characterization of linear time beyond its literal definition.

> Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

No there aren't. You can decide any regular language in linear time using a DFA (trivially modify its description so it's a Turing machine).

---
Tags: formal-languages, time-complexity
---


# Question
Title: Conditions for maximum period of quadratic congruential method (PRNG)
$X\_{n} = (d^2X\_{n-1} + aX\_{n-1} + c) \operatorname{mod} m$

Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):

> 1. $c$ is relatively prime to $m$
> 2. $d$ and $a-1$ are both multiples of $p$, for all odd primes $p$ dividing $m$
> 3. $d \equiv a-1$(mod 2) when $2|m$; $d$ is even and $d \equiv a-1$(mod 4) when $4|m$
> 4. $d \not \equiv 3c$ (mod 9) when $9|m$

Knuth writes in the answer to exercise 8:

> *If $p \leqslant 3$, it's easy to establish the necessity of condition (iii) and (iiii) by **trial and error method***

I do try to find my own way to prove (the necessity of) condition (iii) and (iiii). Here's how i prove the first one:

Assume $m=p^e$. Firstly, we consider the case when $p=2,e=1$

So, the sequence $X\_n$ with ($X\_0 = 0$ and $m=2$) has the period of $2$ when:
$$X\_2 = X\_0 = 0 $$

We can prove: $X\_2=dc+a+1 \operatorname{mod}$ 2 (due to the relatively prime $c$)

Obviously, we have: $$d \equiv a-1 (\operatorname{mod} 2)\space \tag1$$

If $e \geqslant 2$ then $4|m$. The same sequence $X\_n$ with $(X\_0=0,m=4)$ must have the period of 4 which means: $X\_0\not=X\_1\not=X\_2\not=X\_3$

$X\_2 \not=X\_0$. So, $X\_2 = 2$ and $X\_3 \not=X1$. The fact then implies: $$aX\_2 \not\equiv 0 (\operatorname{mod} 4)\space\tag2$$

Due to (1), (2), $a \operatorname{mod} 4$ and $d \operatorname{mod} 4$ can only adopt odd and even values. After some trials on $X\_2 = dc + a + 1 \operatorname{mod} 4= 2$ (c is odd), we easily prove: $d \equiv a-1(\operatorname{mod} 4)$

I have also proved the condition (iiii) by my "trial and error method" but i'm not sure if they are what Knuth mentions. So my first question:
*1. What's exactly "trial and error method" applying for this situation?*

Finally, the proof of condition (ii) confuses me:

> If $d \not\equiv 0(\operatorname{mod} p)$ then $dx^2+ax+c \equiv d(x+a\_1)^2 + c\_1(\operatorname{mod} p^e)$ for some integers $a\_1$, $c\_1$ and for all integers x

$d\not\equiv 0 (\operatorname{mod} p)$ leads to d relatively prime to $p^e$. But i can't go on any further from this.

2. Why does $dx^2+ax+c\equiv d(x+a\_1)^2 + c\_1(\operatorname{mod} p^e)$ hold when $d \not\equiv 0(\operatorname{mod} p)$ ?

# Answer
> 2 votes
> What's exactly "trial and error method" applied in this situation?

$\newcommand{\mymod}{\operatorname{modulo}}$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $\mymod 2$ or $\mymod 4$ or $\mymod 9$ is very small.

What you have done seems pretty good.

---

> Why does $dx^2+ax+c\equiv d(x+a\_1)^2 + c\_1(\mymod{p^e})$ hold when $d \not\equiv 0\\,(\mymod{p})$ ?

Prime $p\not=2$ since it has been assumed $p\ge5$. Since $d \not\equiv 0\\,(\mymod p)$, $2d$ and $p^e$ are relatively prime, which implies $2d$ is invertible $\mymod p^e$. Let $(2d)d'\equiv1\\,(\mymod p^e)$ fro some $d'$. Then

$$\begin{aligned} dx^2+ax+c &\equiv dx^2+2dd'ax + c\\ &\equiv d(x+d'a)^2 -d(d'a)^2+c\ (\mymod p^e)\\ \end{aligned}$$

Letting $a\_1=d'a$ and $c\_1=-d(d'a)^2+c$, we are done.

---
Tags: algorithms, algorithm-analysis, modular-arithmetic
---


# Question
Title: In "multi hop" network, is computer => computer 0 hop or 1 hop?
Would this here, a computer sending information directly to another computer, count as 0 hops or 1 hop?

# Answer
> 1 votes
As stated on this site:

> A hop is a computer networking term that refers to the number of routers that a packet (a portion of data) passes through from its source to its destination. Sometimes a hop is counted when a packet passes through other hardware on a network, like switches, access points, and repeaters. This isn't always the case and it depends on what role those devices are playing on the network and how they're configured.

So as there are no routers showed between the two workstations, I'd say this is a point-to-point connection (layer 2 link with only two devices) with no hops in between.

---
Tags: routing
---