# Question
Title: is there a (FLAC like) loseless compression coding format for EEG data?
EEG and Audio data are very similar, both

1. are numerical samples in continuous sequence
    * have a sample rate
2. need and can have multiple channels
    * channels for multi-channel audio
    * channels for each electrode
3. have predictable characteristics that are exploitable for compression.

FLAC is specifically designed for efficient packing of audio data, unlike general-purpose lossless algorithms such as DEFLATE, which is used in ZIP and gzip. While ZIP may reduce the size of a CD-quality audio file by 10–20%, FLAC is able to reduce the size of audio data by 40–50% by taking advantage of the characteristics of audio.

is there a standard loseless compression coding format for EEG data, that takes advantage of the characteristics of EEG, like FLAC takes advantage of the characteristics of audio?

# Answer
For single channel with raw signal, the best option is Elias gamma, for single channel frequency signal, the best option is to use Range encoder. For multiple channels, this is still viable option to compress each channel and then compress them together interleaving signal (one sample from all electrodes, then another sample from all electrodes).

If you have multiple channels, there are inter-channel correlations, which should be used for compresion, standard method is to use DPCM or use DCT-IV for decorrelation (this is the very same transform like in JPEG) and then use arithmetic codding of any kind. For online setting - compress signal as it goes - this is very good idea.

Another standart approach is Karhunen-Loeve transform. Do not use autoregressive methods, use Elias gamma in the pipeline instead.
Another approach is to use DCT transform to remove redundancy of interchannels (decorrelation) and compress in minimal frequency form.

If you need to store volumes of EEG data, my advice is to clear it from noises and store bands you are interested in, otherwise you store mainly hard to compress noise.
> 2 votes

# Answer
You can use the same principles as FLAC, adapted to the specific data: You write code which given previous samples predicts the next sample as good as possible. Then you just compress enough samples to get the predictor running, followed by the difference between the actual signal and the encrypted signal.

You could of course just use FLAC, adapted to the difference in frequency, and see what happens. For example if you have a file with 360 11-bit samples per second, you can just pretend it is 44100 samples per second in the range -1024 to +1023 with the sample shortened by a factor 44100/360 or 122.5 / 1 and put it through FLAC. (Encoding as mp3 or aac would be useless, because they produce sounds that are very similar to the ear but can be structurally quite different).
> 0 votes

---
Tags: data-compression
---


title: Modeling equality in an ILP

text:
# Question
Title: Modeling equality in an ILP
Lets say we have integer variables $a \in\mathbb{Z}^n$ and $M \in\\{0,1\\}^{n\times L}$. I am promised $a\_i \leq L$, for some fixed constant $L$. I want to model the constraint $$M\_{i,j} \iff (a\_i=j)$$ in an integer linear program. What is the most efficient way to do this in an ILP? In particular, can I do this without Big-M constraints and without breaking down each integer into its binary representation?

Currently I can see two ways to model this:

## Option 1

We can apply the method described in the answer here to the constraint $M\_{i,j} \iff (a\_i-j=0)$. This requires $1$ extra binary variable as well as $4$ potentially large "Big M" constraints per $M\_{i,j}$, thus resulting in $nL$ new binary variables and $4nL$ new big M constraints.

## Option 2

We can break down $a\_i$ into its bits using $\log L$ extra binary variables. We can also compute the corresponding binary bit breakdowns for each $0\leq j \leq L$. Let $bit^{(a)}\_{i,k}$ be the $k$th bit of $a\_i$ and let $bit\_{j,k}^\*$ be the $k$th bit of the integer $j$, so that $$a\_i = \sum\_{k=0}^{\log L}2^kbit^{(a)}\_{i,k}.$$

We now have the following logic: $$M\_{i,j} \iff (\forall k . 0\leq k\leq \log L \implies bit^{(a)}\_{i,k} \odot bit\_{j,k}^\*)$$

Therefore

$$M\_{i,j} = \bigwedge\_{k=0}^{\log L} bit^{(a)}\_{i,k} \odot bit\_{j,k}^\*.$$

We can use this post to NXOR the pairs of variables, storing their results as another variable $z=\\{0,1\\}^{\log L}$. We can AND these together using the constraints $$M\_{i,j} \ge \sum z\_i$$ $$M\_{i,j} \leq z\_i \\;\\;\\; \forall i$$

This creates $\log L$ new variables and 1 constraint for representing the binary breakdown of $a\_i$. We then have $\log L$ XNOR variables, each which can be represented with 4 constraints. We can finally represent $M\_{i,j}$ with $\log L + 1$ more constraints. Therefore, we have a total of $5\log L$ constraints and $2\log L$ new variables per $M\_{i,j}$, giving us a total of $5nL\log L$ new binary constraints and $2nL\log L$ new binary variables.

Is there some third option that is better than either of these two options?

# Answer
I have several options for you. Here is the simplest:

# 1.1 Direct Option

Use an inequality to enforce that one out of $M\_{i,1},\dots,M\_{i,L}$ are true:

$$M\_{i,1} + \dots + M\_{i,L} = 1.$$

Use a second inequality to link that to $a\_i$:

$$a\_i = M\_{i,1} + 2 M\_{i,2} + 3 M\_{i,3} + \dots + L M\_{i,L}.$$

# 2 Indirect Options

Alternatively, we could try to follow more closely to the approach you outlined, but using ideas from one-out-of-n constraints for SAT solvers. In particular, the entries $M\_{i,1},\dots,M\_{i,L}$ are a one-hot encoding of a one-out-of-L constraint, and you want them to be consistent with an encoding directly as an integer. There are standard techniques for enforcing one-out-of-n constraints for SAT, and you could using them with ILP as well.

## 2.1 Improved Binary Encoding

We can use the idea in https://cs.stackexchange.com/a/51512/755 to improve your option 2. Let $a\_{i,k}$ denote the $k$th bit of $a$. We add the constraint

$$M\_{i,j} \implies a\_{i,k} \text{ if } bit^\*\_{j,k}=1,$$

otherwise add the constraint

$$M\_{i,j} \implies \neg a\_{i,k} \text{ if } bit^\*\_{j,k}=0.$$

Next, we add the constraint

$$M\_{i,1} + \dots + M\_{i,L} \ge 1.$$

This requires only $n+nL\log L$ constraints and $n\log L$ new variables, instead of $5nL \log L$ constraints and $2nL \log L$ new variables.

## Commander Encoding

You could use a a recursive commander encoding to enforce that exactly one out of $M\_{i,1},\dots,M\_{i,L}$ are true. Note that the constraint for "at most one variable in a group can be true" requires $O(m^2)$ clauses in SAT but can be represented in a single inequality in ILP, so the number of constraints needed will be smaller than for SAT. Then, you could use any of the above techniques to link the $M$'s to the $a'$.

That said, I don't expect these indirect options to be worth implementation; my expectation is that the direct option will be more natural, and it is what I would try first.
> 1 votes

---
Tags: logic, boolean-algebra, integer-programming
---


# Question
Title: Loop Invariant Code Motion - am I missing something?
I've been implementing LICM for a project, and came upon a strange observation.

Let's say we have a loop

```
int i = 10;
while (i > 0) {
    a = 2;
    i--;
}

```

One can easily see that `a = 2` is invariant. What we do next is check (for each invariant candidate) if the containing basic block dominates all uses of the said variable and all exits of the loop.

The former is clearly true, as `a` is only used once. The latter is what I don't seem to get. The CFG of the example above is

##

By looking at the graph we can clearly see that the cycle body (which is just a single basic block in this case) **does not dominate all exits!**

After thinking about this for some time, I got to the following conclusion:

---

*In a general case, we can not know for sure if the body of a loop is going to be executed at least once. This implies that one can not simply move invariant instructions out of the loop, as they will then be executed dependless of the actual value of the loop termination condition.*

---

I have not seen this adressed in any of the material covering LICM, as well as in the wikipedia article. In fact, their example, in which they transform

```
for (int i = 0; i < n; ++i) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

```

into

```
x = y + z;
t1 = x * x;
for (int i = 0; i < n; ++i) {
    a[i] = 6 * i + t1;
}

```

seems incorrect, as the loop condition generally could have been `false` on the first iteration, and so `x = y + z` should not have been executed at all.

## My proposed solution

All code deemed invariant should be put in an `if (expr)`, where `expr` is the loop condition. For my original example, that would give us

```
int i = 10;
if (i > 0) {
   a = 2;
}
while (i > 0) {
    i--;
}

```

# Answer
> 1 votes
You can also replace with

```
if (loop_condition) {
    loop_invariant_code
    do {
        loop_body
    } while (loop_condition)
}

```

With all he precautions of course. That makes the loop a bit simpler, and saves one test of the condition. And because you have no extra evaluations of loop\_condition, this should be correct even if loop\_condition has side effects.

And in the first example starting with i = 10 you should be able to optimise the first loop condition away.

But absolutely, you cannot just move code with side effects out of a loop, and you should be careful moving code without side effects, in case the loop is not executed and the moved code just wastes time. This more critical in languages that do overflow checks, so adding a+b can actually have a side effect on overflow.

Note: The wikipedia article also mentions strength reduction (for example, instead of calculating i\*6, set tmp = 0 before the loop starts, and increase tmp by six at each iteration). Setting tmp = 0 would also only be executed if the loop condition is tested once.

---
Tags: optimization, loop-invariants
---


# Question
Title: Dynamic programming - maximize sum of functions subject to constraints
Let $\\{f\_i\\}\_{i=1}^{k}:\[0,k\]\to\mathbb{Z}$.

**The problem: Maximize the sum $\sum\_{i=1}^{k}f\_i(x\_i)$ subject to the the constraint $\sum\_{i=1}^{k}x\_i\le k$**

I think we suppose to come up with a polynomial time solution, but i got stuck on identifying the sub-problems and using them.

One direction that i had was creating a list for each function, where both the arguments and the function values are in decreasing order: in each iteration, find the argmax of the function, delete bigger arguments that yield smaller function values, and proceed with the smaller arguments that remain (($O(k^3)$ for all functions).

Then use those lists to iterativly construct the optimal solution under the constraint for 1, 2, .. and finally for all $k$ functions, Got stuck about here. Not sure if it's a good direction at all...

Would appreciate any assistance.

# Answer
> 3 votes
Let us read the objective again, "maximize the sum $\sum\_{i=1}^{k}f\_i(x\_i)$ where $\sum\_{i=1}^{k}x\_i\le k$."

The subproblems or the table entries are $DP\[a\]\[b\]$ for all $0\le a\le k$ and $0\le b\le k$, where $DP\[a\]\[b\]$ is the maximum value of $\sum\_{i=1}^{a}f\_i(x\_i)$ where $\sum\_{i=1}^{a}x\_i=b$. The wanted maximum sum is the maximum of $DP\[k\]\[0\],DP\[k\]\[1\], \cdots, DP\[k\]\[k\]$.

The base cases is $DP\[1\]\[b\]=f\_1(b)$ for all $b$.

How to reduce the computation of $DP\[a\]\[b\]$ to smaller subproblems? The following equality is the critical observation, which is the reason why we have the first dimension "\[a\]" in the formulation of the subproblems. The other dimension "\[b\]" comes from the constraint $\sum\_{i=1}^{a}x\_i=b$.

$$\sum\_{i=1}^{a}f\_i(x\_i) = \sum\_{i=1}^{a-1}f\_i(x\_i) + f\_a(x\_{a}),$$ i.e., $DP\[a\]\[b\]$ is the maximum of the following numbers, $$\begin{aligned} &DP\[a-1\]\[b\] + f\_a(0),\\ &DP\[a-1\]\[b-1\] + f\_a(1),\\ &\cdots,\\ &DP\[a-1\]\[0\] + f\_a(b).\\ \end{aligned}$$

---

**Exercise 1.** Using dynamic programming to maximize the sum $\sum\_{i=1}^{k}f\_i(x\_i)$ subject to the the constraint $\sum\_{i=1}^{k}x\_i\le n$, where $n$ is a given integer.

**Exercise 2.** Using dynamic programming to maximize the sum $\sum\_{i=1}^{k}f\_i(x\_i)$ subject to the the constraint $\sum\_{i=1}^{k}x\_i= n$, where $n$ is a given integer.

**Exercise 3.** Using dynamic programming to maximize the sum $\sum\_{i=1}^{k}f\_i(x\_i)$ subject to the the constraint that for all $j$, $|x\_{j+1}-x\_{j}|\le n$, where $n$ is a given integer.

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: Help with question from Sipser chapter 1
Is this language regular?

$0^k10^k \ with \ k\geq1$

It needs to count the starting and ending zeros which is impossible with finite states.

Update: This is the whole problem from the book:

Let $\sum = \\{0,1\\}$. Let $A =\\{0^ku0^k \ | \ k \ge 1 \ and \ u \in \sum^\*$}. Show that $A$ is regular.

My reasoning is that $u$ can be $\\{0,00,000,...,01,011,...,1,11,111,11111...etc\\}$

So, the language $0^k10^k \ with \ k\geq1$ should be regular.

I don´t want a formal proof of the problem, but to check if my reasoning is correct. Thanks.

# Answer
> 1 votes
I think I finally understood the concept.

This:

$A =\\{0^ku0^k \ | \ k \ge 1 \ and \ u \in \sum^\*$}.

Means that A has strings that starts and ends with the same number of zeros.

For example, the string:

$0000000100$

Is recognized by A because:

$00|000001|00$

In the middle we can put any number of zeros and shrink the zeros at the edges.

$0^k10^k$ is another language that contains strings with equal number of zeros at the beginning and end separated by a 1. In this case, string from this language are accepted by the the first one but that doesn't means that the second language could be regular.

---
Tags: finite-automata
---


title: What does $\tilde{O}_P(N^\alpha)$ mean?

text:
# Question
Title: What does $\tilde{O}_P(N^\alpha)$ mean?
What does $\tilde{O}\_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.

---

What does big O subscript P mean in a probability context?

# Answer
> 4 votes
Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5).

> A probabilistic version of $\mathcal{O}$ that is frequently used is the following:
>
> $X\_n = O\_\text{P}(\alpha\_n)$ if for every $\epsilon \> 0$ there exists constants $C\_{\epsilon}$ and $n\_{\epsilon}$ such that $\mathbb{P}(|X\_n| \leq C\_{\epsilon}\alpha\_n) \> 1 − \epsilon$ for every $n \geq n\_{\epsilon}$. In other words, $X\_n/\alpha\_n$ is bounded, up to an exceptional event of arbitrarily small (but fixed) positive probability. This is also known as $X\_n/\alpha\_n$ being bounded in probability.

So combining this and D.W.'s answer we get:

> $X\_n \in \tilde{O}\_{\text{P}}(\alpha\_n)$ means for every $\epsilon \> 0$ there exists constants $C\_\epsilon$ and $n\_{\epsilon}$ such that $\mathbb{P}(|X\_n| \leq C\_{\epsilon}\alpha\_n n^{\gamma}) \> 1 - \epsilon$ for every $n \geq n\_{\epsilon}$ and for all $\gamma \> 0$.

An looser terms $X\_n \in \tilde{O}\_{\text{P}}(\alpha\_n)$ means $X\_n$ is bounded by $\alpha\_n$ within a polynomial factor with high probability.

# Answer
> 2 votes
It depends on context; often, saying $f(n) \in \tilde{O}(g(n))$ means $f(n) \in O(g(n) n^{\epsilon})$ for all $\epsilon\>0$. For example, $n^2 \log n \in \tilde{O}(n^2)$.

---
Tags: algorithms, complexity-theory, error-estimation
---


# Question
Title: Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a’s and an odd number of b’s
Does the question mean draw a Turing machine that takes input with any number of a's and any number of b's (eg. aaabbb, ab, abababab, etc.). The turing machine should only then accept or reject the input and should not be stuck in loop?

Example of a drawing to answer the question:

# Answer
A *decider* is a TM that halts (i.e either accepts or rejects) on any input.

The TM that is requested should accept any input that has an odd number of $a$s and an odd number of $b$s, and should reject all other input.

The TM you have depicted does not meet the requirements (HINT: consider the string $aa$).
> 0 votes

# Answer
Yes. "Words over the alphabet $\Sigma=\\{a,b\\}$" means that the input can be any string containing $a$s and $b$s in any order, and "decide" means that the machine must halt (accept or reject) on every input, and not get into an infinite loop.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }
$L = \\{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \\}$

I have trouble about this PDA. Anybody can help me about draw this PDA?

# Answer
> 0 votes
The PDA should start by counting the numbers of $0$s (by pushing some symbol onto the stack for each $0$ encountered) ensuring that there is at least one $0$. Then, nondeterministically choose to match each $0$ with two $1$s (by popping one symbol off the stack for every two $1$s encountered) or, ignore any $1$s encountered and match each $0$ with a $2$ (by popping one symbol from the stack for each $2$ encountered).

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


# Question
Title: Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:

* A = $O(nlogn)$
* B = $O(n\sqrt{n})$
* C = $\Theta(n)$

In my opinion, it is not possible to define the best solution, since we don't know how `C`grows. I'd like to confirm if that's correct.

# Answer
Well, we *know* how the algorithm `C` running time grows - it's linear, and it's two-side (lower *and* upper) bound.

However there is still not enough information to choose the best (meaning: fastest *in practice*) algorithm here, because:

* We know only upper bounds for algorithms `A` and `B` \- they might be more efficient than `C` actually, we just don't know that yet.
* We don't know constants, hidden in the $\Theta$ bounds - they might make the algorithm `C` less practical than `A` or `B` for limited problem size.

Using the given information we can say only that *for some sufficiently large problem size* the algorithm `C` *might* win over algorithms `A` and `B`.
> 1 votes

---
Tags: complexity-theory, time-complexity, asymptotics, big-o-notation
---


# Question
Title: Pseudo-Proof of Constrained Sudoku is co-np
## The definition of CO-NP

> A decision problem **X** is a member of **co-NP** if and only if its complement **X** is in the complexity class **NP**. In other words, **co-NP** is the class of problems for which there is a polynomial-time algorithm that can verify "no" instances - wikipedia

## Sparse-Language

> *Where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime}*
>
> *For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language.*
>
> *My algorithm follows a 3x3 shift language allowing valid Sudoku Grids. Valid grids up to 50x50 and seemingly 100x100 so far have been generated.*
>
> Wikipedia, Cyclic language, Sparse Language

*The language used by this algorithm is a 3x3 circular shift. A cyclic code of permutes allowing valid grid.*

## Constrained Sudoku Pseudo Proof

## What I'm trying to do/Decision Problem

I'm trying to compare two grids. One non-constrained and the other constrained. Both grids are technically valid but within their own "class"

*Determine if a valid Sudoku grid is of the conventional class or the constrained class following the shift(L) circular language.*

As mentioned in the co-NP definition a decision problem "X" is a member of co-np if and only if its complement X is in the complexity class "NP." As said before, co-np is the class of problems for which a poly verifier can say no instances. The algorithm verifies no instances for grids. If it does not follow the circular language. It says, "not a constrained puzzle." Therefore, Constrained Sudoku is co-np.

Assuming, that the cyclic language is maintained indefinitely.

> Cyclic Permutation
>
> *let n = input*
>
> *let k = shift(L)*
>
> **Pn = (n-k)!**
>
> **(n-3)! == lim\_(n-\>∞) 3 = 3**
>
> In reduced form
>
> **(n - 3)! = n-\>∞-k**

## Pseudo-Code

```
if indexes/elements match in grid and follows  shift(L) language:

                                   print "yes"
else:

                                   print "no"

```

*Overall, is this sufficient proof that Constrained Sudoku is co-np?*

Constrained Sudoku Algorithm

# Answer
> 5 votes
No, it's not a persuasive proof.

Before you can have a valid proof, you must first precisely state whatever it is you are trying to prove. You haven't done that.

A language (a decision problem) is in co-NP if it satisfies certain requirements. You have not defined a language; you have not defined a decision problem. You use the phrase "Constrained Sudoku" but you have not given a precise definition of what formal language that is intended to refer to.

What you list as a "definition" of co-NP is actually an English-language summary of the definition; it's not a substitute for knowing the precise mathematical definition.

The reasoning in your "proof" is faulty. You write:

> I use an algorithm that in essence says "no" when \[...\]. Therefore, Constrained Sudoku is co-np.

That doesn't follow. Just because you have an algorithm that sometimes says no, doesn't mean that the corresponding problem is in co-NP. There are additional requirements, which you haven't checked.

I'd like to give some general advice. Before trying to tackle this problem, I suggest you spend a bunch of time studying the fundamentals. Set aside Sudoku and your ideas for a few weeks, and find an online course where you can learn complexity theory. That will give you a mathematical framework that, once you've learned it, you can come back and apply to Sudoku. Until you've done that, it is pointless to continue trying to frame questions like this.

---
Tags: algorithms, sudoku
---


# Question
Title: Weighting function for Non Uniform Learning
Consider a hypothesis class $H = \cup\_{n=1}^{\infty} H\_n$, where for every $n\in N$, $H\_n$ is finite. Find a weighting function $w : H -\>\[0, 1\]$ such that $\sum\_{h \in H} w(h) ≤ 1$ and so that for all $h \in H$, $w(h)$ is determined by $n(h) = min\\{n :h \in H\_n\\} $ and by $|H\_n(h)|$.
Since every $H\_n$ is finite, it is agnostic PAC learnable. And hence their union $H$ is non-uniform learnable. However I am unable to proceed from here.

# Answer
> 0 votes
For every $n\in \mathbb{N}$, and $h\in H\_n$, we can use $w(h)$ = $\frac{2^{−n}}{|H\_n|} $.

---
Tags: machine-learning, learning-theory
---


# Question
Title: Circular Doubly Linked List find length with single pointer
I have pointer to circular doubly linked list with random values of 0 or 1.
Example: `[{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]`
I have a single pointer to the first item of the list. I need to find the length of the list **without to create any additional pointers**.
In addition, I can change the values of each node between 0 to 1 or 1 to 0.

I thought about `Josephus Circle` algorithm - with no success.

My main problem is that I don't even know what end of a circle/circular list is.
If you think about that, you will understand it is not an easy question.

# Answer
I think the following algorithm would do it:

1. Start by setting the value in the first node to $1$.
2. Follow `next` pointers until you encounter a node with value $1$, while keeping a counter $c$ of how many nodes you have encountered.
3. Set the value of the node to $0$ and follow `prev` pointers for $c$ steps
    * If the value of the node (which should be the first node) is now $0$, the list has $c-1$ elements,
    * otherwise, follow `next` pointers for $c$ steps and continue with step 2.
> 1 votes

# Answer
One of your comments suggests that you are interested in an ‘efficient’ solution -
assuming a non-empty list correctly doubly linked:

0. let $toSet = 1$ and set current item to $0$

1. $toSet$ times, follow the $next$ link and set to $1$
2. $toSet - 1$ times, follow the $prev$ link
3. up to $toSet$ times,
    * follow the $prev$ link,
    * if item is $1$, the number of $prev$s followed since last change of direction is the number of items,
    else set to $1$
4. double $toSet$
5. $toSet$ times, follow the $prev$ link and set to $0$
6. $toSet - 1$ times, follow the $next$ link
7. up to $toSet$ times,
    * follow the $next$ link,
    * if item is $0$, the number of $next$s followed since last change of direction is the number of items,
    else set to $0$
8. double $toSet$ and repeat from 1

The number of items set and potentially inspected doubles with each "half-iteration".
The number of items checked is exactly the number $n$ of items in the list.
The number of items set varies from $3n-1$ for $n = 2^i$ to $2n$ for $n = 2^{i + 1} - 1$.

ToDo: find
a simple pattern of length growth between ("half-")iterations that works for every list length, too, *and*
a list length where *#sets + #follows + #compares* is smaller than for doubling as above
> 0 votes

---
Tags: algorithms, complexity-theory, data-structures
---


# Question
Title: Give a computation of the expression to normal form (Lambda calculus)
Past exam question:

What my understanding of B-reduction is : Find all occurrences of the parameter in the output, and replace them with the input and that is what it reduces to

```
(λ param . output)input => output [param := input] => result

```

Example:

```
(λx.xy)z

= (xy)[x:=z]

= (zy)

= zy

```

But I do not know how to use B-reduction on the expression above. What is the input, output and the parameter.

# Answer
Usually, a series of applications $f\\,x\_1\\,x\_2 \dots$ means $\big(\big((f\\,x\_1)\\,x\_2\big)\\,\ldots\big)$. We say that *application is left associative*.

According to this convention, there is an extra set of parentheses that is implied in the expression you write. Here I've made it explicit: $$\big((\lambda f.\lambda g.\lambda x. f \\,(g\\,x))\\,(\lambda u.u)\big)\\,(\lambda v.v)$$

The expression $(\lambda f.\lambda g.\lambda x. f \\,(g\\,x))$ is a function and it is applied on input $(\lambda u.u)$. Reducing this will result to a function of the form $(\lambda g. \lambda x. \langle\text{body}\rangle)$, which in turn gets applied to $(\lambda v.v)$.
> 3 votes

---
Tags: computability, lambda-calculus
---


# Question
Title: How can I understand a hint for finding the lowest height of the last bulb in a Garland?
**Disclaimer** This is not from an ongoing contest, this is from my course on edx of ITMO. Also this is a paid courses so the direct link to the problem is not useful unless you also register this course.

**Problem description** A garland consists of light bulbs hanging from the same wire. One endpoint of this wire is fixed at a height of $A$ millimeters ($h\_1 = A$. Thanks to gravity, the garland bends down: the height of every light bulb which is not at the endpoint is one millimeter smaller than the average height of its neighbors: ($\displaystyle h\_i=\frac{h\_{i-1}+h\_{i+1}}2-1$ for $1 \< i \< n$).

Determine the smallest height of the second endpoint $B$ ($B= h\_n$), given that at most one light bulb is allowed to touch the ground, and for all other light bulbs the inequality ($h\_i$ \> 0) should be true.

Hint: to solve this problem, you can use binary search.

Input
The first line of the input file contains two numbers $n$ and $A. 3 \le n \le 1000$, $n$ is an integer, $10 \le A \le 10000$, $A$ is a floating-point number which has at most three digits after the decimal point.

Output
Print a single number $B$ , which is the minimal height of the second endpoint. Your answer is considered to be correct if it differs from the right one by at most $10^{-6}$.

Examples

$\displaystyle\begin{array}{|l|l|} \hline \text{input.txt} & \text{ output.txt} \\\hline 8\ \\,15 & 9.75 \\\hline 692\ \\,532.81 & 446113.34434782615 \\\hline \end{array}$

---

There are problems that you either get it or don't, this is the "don't get it" for me. I cannot correlate the hint to the solution. I mean what we are supposed to search, although I can understand the problem but it's like the hint is the ambiguity for me. Without the hint, I don't know how to proceed, either.

# Answer
### Short answer

Let $d=h\_1-h\_2$. Do a binary search for the largest value of $d$ in interval $\[0,A\]$ so that none of $n$ bulbs in the garland will be lower than the ground. The wanted minimum value of the second endpoint $B$ corresponds to the case when $d$ is that largest value.

### Explanation

The question is how to understand the hint "you can use binary search".

Before understanding the hint, we are supposed to have understood what is binary search. Binary search is a search algorithm that finds the position of a target value within a sorted array or an interval.

So, what could be that target value we are supposed to search? Within which sorted array or which interval?

* The most obvious target value to search is $m$, the minimal value of $B$. We could search $m$ within the interval $\[0, \text{FM}\]$, where $\text{FM}$ is the maximum value of a floating-point number.
* Another obvious target to search is about that lowest bulb. In case there are two lowest bulbs, the lowest bulb will mean the one to the left. The further to the right the lowest bulb is, the lower value $B$ is. We could search $\ell$, the rightmost possible position of the lowest bulb within the interval $\[0,n\]$.
* Whenever we started to compute, we find we have to understand clearly the given equality, $\displaystyle h\_i=\frac{h\_{i-1}+h\_{i+1}}2-1.$ If $h\_1=A$ and $h\_2$ are known, the height of every bulb is fixed, since $$h\_{3}=2\times h\_{2}-h\_{1}+2$$ $$h\_{4}=2\times h\_{3}-h\_{2}+2$$ $$\cdots$$

The only requirement is that no bulb can be lower than the ground. Note that

$$\displaystyle h\_{i+1}-h\_i=h\_{i}-h\_{i-1}+2.$$

As we visit the bulb from left to right, the bulb is dropping less and less between each pair of successive bulbs initially. Once the bulb have reached the lowest level, it will climb more and more between each pair of success bulbs. The larger the first drop $h\_1-h\_2$ is, the more likely one of the $n$ bulbs will hit the ground and the lower the last $B$ will be. Aha, we can also search the largest value of $h\_1-h\_2$ within interval $\[0, A\]$.

### How to binary search a real number?

How can we search for the largest value of $d$, which is a real number in an interval?

Since there are infinitely many real number in an interval, checking equality is not likely to work as the stopping condition. That is why we are given the requirement for the "the minimal height of the second endpoint" that it differs from the right one by at most $10^{−6}$". The pseudocode looks like the following.

```
'''A=h_1, n are given.'''

'''10^(-7) instead of 10^(-6) to guard against rounding errors in computation of floating-point numbers'''
precision = 10^(-7)

function get_largest_first_drop_by_binary_search():
    L = 0
    R = A
    B_L = last_height(L)
    B_R = last_height(R)
    while ( B_L - B_R > precision):
        m = (L + R) / 2.0
        if hit_ground(m):
           R = m
           B_R = last_height(R)
        else:
           L = m
           B_L = last_height(L)
    return B_L

function last_height(d):
    ''' Given first drop h_2 - h_1 = d, return h_n, the height of last bulb'''
    return A + ((-d)+(-d+2(n-2)))(n-1) / 2

function hit_ground(d):
    ''' Given first drop h_2 - h_1 = d, return true iff the garland will hit the ground '''
    k = floor(d/2) + 2
    if k >= n return last_height(d) < 0
    if k < n return A + ((-d)+(-d+2(k-2)))(k-1) / 2 < 0
    return false

```

### Implementation

Here is an implementation in Java. Click the run button to see the result.

### Exercise

Show that the minimum value of the second endpoint $B$ is 0 if and only if $A \ge (n-1)(n-2)$.
> 2 votes

---
Tags: algorithms, binary-search
---


# Question
Title: What is the complexity of this prime trial division algorithms?
I have two algorithms. What are their time complexities? The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$. The second algorithm generates a list of prime from $2,3...,\sqrt{n}$ and divides the input, $Num$ by these primes.

Algorithm 1 needs $\sqrt{Num}/2$ modulo divisions in the worst case, and Algorithm 2 needs just $\sqrt{Num}/\log{n}$ modulo divisions. Algorithm 1:

```
        bool IsPrime(BigInteger Num)
        {
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else if (Num % 2 == 0) return false;
            else for (BigInteger u = 3; u * u <= Num; u += 2)
                    if (Num % u == 0) return false;
            return true;
        }

```

Algorithm 2:

```
        bool IsPrimeBetter(BigInteger Num)
        {
            ulong arrayLe = (ulong)Isqrt((long)Num);//Sqrt of Num
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else foreach (var prime in new Atkin(arrayLe))//Atkin sieve which generate list of primes from 2 to √Num
                    if (Num % prime == 0) return false;
            return true;
        }

```

I don't really know how to check complexity of them.

# Answer
The first one is easy: Figure out how often you will iterate through the loop in the worst case.

The second one is harder: Again, you need to figure out how often you will iterate through the loop. However, you also need to figure out how long it takes to calculate the list of primes, and how long it takes to enumerate all those primes.

In practice, you would likely check many numbers for primality, so you wouldn't create a complete new sieve every time, but keep the previous sieve, and extend it when checking a larger prime number.
> 1 votes

---
Tags: complexity-theory, algorithm-analysis, time-complexity, primes
---


# Question
Title: CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }
$L =\\{a^nw \mid w \in \\{b,c\\}^\*$, $n=$ #$\_b$ \+ #$\_c$$\\}$

$\bullet $ #$\_b$ denotes the number of $b$'s in $w$

$\bullet $ #$\_c$ denotes the number of $c$'s in $w$

I have some trouble designing a CFG for the language above. How can I do this?

# Answer
> 1 votes
I believe the following CFG meets the requirements

$$ S \to aSB \mid \varepsilon\\ B \to b \mid c $$

# Answer
> 1 votes
I believe, the answer of @Acid is correct.
Also, It is sometimes hard to come up with the productions rules directly by looking at the language.
An easier (a bit longer) approach can be, making a Push Down Automata (PDA) accepting the given language and converting the transitions of PDA into production rules.
For this language, it can be observed that, we can just push some stack symbol let's say '#' into the stack on seeing 'a' as the input symbol and pop from the stack on seeing 'b' or 'c'. Also make sure that, 'a' never comes after we see at least one 'b' or 'c'. Once the PDA is done, this is a very informative video on converting to PDA to CFG.
Let me know in the comments, if you need any clarification in the conversion.

---
Tags: formal-languages, context-free
---


title: How to construct CFG for language

text:
# Question
Title: How to construct CFG for language
We have alphabet $\Sigma = \\{ { a, b} \\} $.

How to construct CFG for language $\Sigma^{\ast} - \\{a^{n}b^{n} | n \ge 0 \\}$.

I suggest that is very easy, but I can't invent. I know PDA for this language if it can help.

# Answer
> 6 votes
Split into parts that you can handle. All strings not of the form $a^\*b^\*$. All strings of the form $a^ib^j$ with $i\< j$. Then all strings ....

# Answer
> 0 votes
Yes, PDA for the language can certainly help. The transitions of the PDA can be transformed to production rules. This is an excellent video on PDA to CFG conversion.
Let me know if you need any clarification in conversion.

---
Tags: context-free
---


title: League and Divisions problem (np-hard)

text:
# Question
Title: League and Divisions problem (np-hard)
There is a *League*. And there are *Divisions*, that are the disjoint subsets of this *League*. There are **n** teams (unique locations are given, let's assume it's **x** and **y** for simplicity reasons). Every team must belong to exactly one *Division*. There are **min** and **max** \- minimal and maximal amount of teams per division. Every team travels once to every other team inside one division. The target is to divide the league into divisions in a way, that the total traveling distance for the whole league is minimized.

Input:
**n** \- amount of teams
**min** \- minimum teams per division
**max** \- maximum teams per division
**teams** \- array of teams (**name**,**x**,**y**)

Input example:
**n** = 10
**min** = 2
**max** = 3
**teams** = \[{a,1,1},{b,2,1},{c,5,3},{d,9,8},{e,6,8},{f,5,1},{g,1,7},{h,6,6}{i,7,2},{j,2,7}\]

Output:
**League**
Output example:
**League** = \[\[a,b,c\],\[d,e\],\[f,g,h\],\[i,j\]\]
One sub array stands for one division. It means that the teams a,b and c belong to one division and each of them will visit every other team from this division.
This is not the optimal solution

This is what an output of a real-world case could look like
I am struggling with selecting an algorithm for this issue. It is not a traveling salesman since we are not interested in simply visiting all of the locations. Neither the clustering approach is applicable since we need to keep the **min** and **max** in mind and it's not what clustering does. What kind of algorithms can be used to tackle down this problem?

# Answer
Balanced k-means clustering would probably work reasonably well here. Unfortunately the true cost structure can't be modelled with this (or any clustering algorithm that I know of); you would need to instead use some increasing function of the distance from the cluster centroid (this could be just the distance itself, or e.g. a small positive power). Balanced k-means will then try to cluster the teams into divisions in such a way that the sum of these per-team costs is minimised, while enforcing a hard upper bound (your **max**) on the number of teams in a division. The chosen number k of divisions, as well as these upper bounds, implies a lower bound on the division size, though this won't necessarily agree with your desired **min**. Hopefully, playing with the parameters a bit could get you close.

The idea is basically the same as regular k-means clustering, except that in the assignment phase, instead of assigning each point (team) to its nearest cluster (division), you solve an instance of the Assignment Problem in which each team is represented as a worker and each division is represented as **max** job slots: this enforces that each division receives at most **max** teams. The problem can be solved with e.g. the Hungarian algorithm.

There's a paper here, but it seems to be behind a paywall unfortunately: https://link.springer.com/chapter/10.1007/978-3-662-44415-3\_4
> 1 votes

# Answer
One approach would be to use a local search optimization method, such as hill climbing or simulated annealing.

The configuration describes the assignment of teams to divisions; and you can define a set of operations that can be applied to a configuration to change it to another one (e.g., pick two teams in different divisions and swap which division they are assigned to; pick a team in a division with at least min+1 teams, and move it to a division that has at most max-1 teams). Then, you can apply one of those algorithms to try to find an optimal assignment.

The problem is NP-hard (I suspect), so I don't expect any algorithm to be always efficient and always find the optimal solution, but this might give a "good-enough" solution.

To get better results, you might repeat it multiple times with different starting configurations. Also, the choice of the initial configuration might be important to its success. You might try using a clustering algorithm to generate a starting configuration (e.g., assign cluster centroids using k-means clustering, with that idea that each centroid reflects a single division, and then iterate over the centroids in a round-robin fashion and for each centroid, find the unassigned team that's closest to it and assign it to that division, until all teams are assigned).
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, optimization, traveling-salesman
---


# Question
Title: Is spectral radius of a graph related to its radius?
I am searching for algorithms to estimate the radius of a graph, and I found out that there are papers about the spectral radius of a graph. As far as I know, the radius of a graph is $\min\_{v \in V} ecc(v)$ where $ecc(v)$ is the depth of a tree rooted at $v$, and the spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Are these two concepts related in some way?

# Answer
No, the two notions are unrelated. To see this, we construct a pair of graphs with the same spectrum, but different radius. Graphs that have the same spectrum are called *co-spectral*. There exist non-isomorphic graphs that have the same spectrum.

This page shows two co-spectral graphs with different radius: the 4-cycle and point has infinite radius, as it is disconnected, but the co-spectral 4-star has radius 1.

The other way around, two graphs of the same radius with a different spectrum, isn't hard to see either. Simply take two graphs with a different number of nodes and the same radius, their spectra must differ as their adjacency matrices have different size.

The word radius is quite general, so it is no surprise to see it in two unrelated terms.
> 1 votes

---
Tags: graphs
---


# Question
Title: Convert this language to Context Free Grammar
I'm having trouble understanding how to convert this language to context free grammar.

$\\{a^ib^jc^k\mid i \> k, 0\le j \lt3, k \ge 0\\}$

Part im getting stuck on is how to deal with a and c, whenever a c is added, you must also add an a, but with them at opposite ends of the string how do you properly build grammar for it? Since the below is not possible:

\begin{align} C &\rightarrow aC \\ C &\rightarrow c \end{align}

I've read the below post many times and tried to apply it but still not able to get it.

How to prove that a language is context-free?

Someone able to show me how this can be done?

# Answer
If you need to prove the language is context-free, showing a PDA that accepts $L$ is enough.

Sometimes, formulating the rules that generate exactly the language $L$ is not so trivial; in such cases you can start by a constructing the PDA that accepts $L$, then convert it to a CFG.

The transformation PDA $\rightarrow$ CFG can be found:

Lecture notes

Answer on this site
> 1 votes

# Answer
> Whenever a $c$ is added, you must also add an $a$, but with them at opposite ends of the string how do you properly build grammar for it?

The production rule you are looking for looks like the following,

$$X\to aXc.$$

The full context-free grammar for the given language can be

$$S\to aS \mid aSc \mid a \mid ab \mid abb \mid abbb. $$
> 0 votes

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


# Question
Title: is a while loop always an indefinite loop?
Building on this example and others found elsewhere we have two types of loops, definite and indefinite:

definite being a loop that has its number of iterations known before it is executed. E.g. a for loop:

```
for x in range(1,10):

```

and indefinite loops which don't have the number of iterations known before it is executed. E.g. this while loop:

```
while answer <> "Yes":
    answer = input("are you an idiot?")

```

I'm checking some teaching materials that have an example of a while loop that looks definite to me as by looking at the code you know exactly when it is going to end:

```
number = 1
while  number <= 10:
    print(number)
    number = number +1

```

Is this example a definite loop even though we have to do a little work to work out the for loop equivalent?

# Answer
Yes, this is definite loop, as long as you (or your compiler for that matter) can infer number of passes.
In some languages (like C), 'for' is a *transformation* that expands during compilation to 'while' construction like you have shown. Compiler would infer number of steps during optimisation phase, when you have provided constant expression loops of any kind, but will not infer that from variable expressions.
> 1 votes

---
Tags: loops
---


title: Linked List with Merge Sort

text:
# Question
Title: Linked List with Merge Sort
Is Merge Sort the best sorting technique to sort a linked list? Also, which sorting technique is worst for a linked list?

---

Merge sort uses a divide and conquer method. What makes merge sort efficient for sorting a linked list?

# Answer
It is really inefficient to access a certain index in a linked list, which is what many sorting algorithms rely on. MergeSort, however, divides and merges lists, which LLs do efficiently. You can find some code and an explanation here.
> 2 votes

---
Tags: linked-lists
---


# Question
Title: Recursive definition for the length of a string?
I found a couple of answers online but I don't quite understand why the answer is right:

1. The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the string is 1 + length of the tail
2.

# Answer
Strings are concatenations of characters. Hence, any non-empty string $w$ has a first character $x$ and can be written as $w = x w'$, where $w'$ is the tail string. It follows from the definition of a string's length that $|w| = |x w'| = |x| + |w'| = 1 + |w'|$.
> 1 votes

---
Tags: recursion, discrete-mathematics, induction
---


# Question
Title: Describe in words how a NTM can simulate a DTM
I have this assignment

1. Describe in words how a DTM can simulate a NTM
2. Describe in wordshow a NTM can simulate a DTM

---

I'm working on this request and I'm crushing with the comparison.

1-I understand that every NTM can be represented by a DTM with a tree structure, that represents every step of the different possibilities of a NTM. Every step should simulate with n tapes the configuration states of the NTM with the DTM etc.

2-For this I'm a little lost, I think you can't have a DTM simulated by an NTM, the multiplicity of states allowed in NTM with guesses makes difficult to create a deterministic process o linear, ¿I'm going in the right path?.

# Answer
NDTM may use multiple transitions which are **allowed**, but these are **not required**. Think of it in another way, DTM is already NDTM that doesn't use possibility of multiple paths, so it is not much of simulation.
> 0 votes

# Answer
A nondeterministic Turing machine has zero or more possible transitions in every configuration; a deterministic one has exactly one. One is "zero or more".
> 0 votes

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


# Question
Title: Efficient search for solving a Jigsaw Puzzle?
I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice.

Let's assume the puzzle pieces are encoded as 4-vectors of integers representing the four sides. A negative integer indicates an indentation that must be matched with corresponding positive integer representing an extrusion. Zero represents a smooth edge (i.e., a border piece.) Rotations then correspond to cyclic shift (assuming the indentations/extrusions are rotationally symmetric.)

My heuristic for an efficient solution is to try to tile the puzzle in an inward spiral starting from the borders. What is the best strategy for building a chain of fitting pieces that avoids exhaustively trying all combinations/rotations?

I found some related SE questions that are relevant:

1. https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
2. https://stackoverflow.com/questions/15121903/algorithm-for-solving-tiling-jigsaw-puzzle
3. Partially filled jigsaw puzzle with six types of tiles

# Answer
> 0 votes
Seems like your heuristic needs to incorporate the distribution of the edge types to be optimal. Here's an idea:

Form a matrix the size of the puzzle's dimensions. Each cell indicates the proportion of remaining pieces that can be fit there on the next iteration without conflicting. At the beginning, the corners of the matrix will be $4$ (only four corner pieces), edges $2(w+h-4)$, and interior $wh-2(w+h-4)$. You can indicate filled cells with a large value, like infinity. Select the set of cells with minimum values as candidates for the next piece. Of these cells, select the piece that decreases the adjacent, unassigned cells by the most amount (use "min" of adjacent cells for the score).

This will ensure you explore the paths that have highest probability of conflicting first. If the first piece you place is incorrect, you want to find if it is incorrect as soon as possible. Likewise, you want to select the first piece to be the one with the least number of choices.

When the min value of the matrix is zero, you know there was an incorrect piece lain somewhere. In that case backtrack, decrease the proportion for the backtracked cell (since now we have eliminated one choice), and begin the iteration again. The backtracked cell will have the minimum value still, of course; so you will simply go on to trying the next piece in the candidate list.

Tentatively, I'd say on average the algorithm would propagate out from the four corners in a spiraling fashion, until two of the corner blocks connect. Then I suspect it would favor building off the connecting block. It will factor in the candidate probabilities, so for specific puzzles the paths it takes will vary.

*(You'll need a specialized data structure to store the best candidates list. Could experiment with a blacklist instead. Or could try simply keeping a counter for how many conflicting pieces you tried for a cell, and then recreate the sorted list each time you need to backtrack)*

---
Tags: search-problem, board-games
---


# Question
Title: What will be a faster algorithm that finds the maximum number of party people?
You want to organize a party and invite as many of your **N** friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be familiar with at least three other guests.

**Question:** what is the fastest algorithm that receives a list of couples of people who know each other and determines the maximum number of people for a party? Estimate the time for which the algorithm works. Argue your assessment.

**My idea**: create a matrix of size N by N, and fill it with links from the condition. After that, you need to remove from it all the connections of people who have less than three friends, it takes $N^2$ operations. Then we get new number of ${N\_{1}} \leq N $. After which I experience difficulties. Obviously, if one goes through the $ 2 ^ {N\_{1}} $ cases from the remaining friends, then one can get the maximum.

# Answer
> 2 votes
I will provide a solution for your problem with $O(N^2)$ computational complexity and $O(N^2)$ space complexity. Firstly we will introduce some helpfull notation. Let's name $A$ the set of your $N$ friends. Let's also define a boolean function $P(x, S)$ with two parameters, $x$ which is one of your friends and a set of your friends $S \subseteq A: x \in S$. $P(x, S)$ will be true iff $x$ knows at least three people in $S$ and he/she also doesn't know at least three people in $S$. Finally, we define that the boolean function $V(S)$ where $S \subseteq A$ will be true iff $x \in S \Rightarrow P(x, S)$. In other words, $V(S)$ shows if a set of people, $S$, can be the guests of your party. The answer to your problem is the value of the following expression: $$\max\_{S \subseteq A \\ V(S) = true} |S|$$ Now we will make a usefull observation: If a person $x$ doesn't have at least three known and three unknown people in a set of some of your friends, then he will not have at least three known and three unknown people in any subset of that set. This could be written as $$\forall S \subseteq A, T \subseteq S, x \in T: \neg P(x, S) \Rightarrow \neg P(x, T)$$ This means that removing guests can't make the party proper for someone if it's not already, or equivalently that the only way to make the party proper for someone (if it is not already) is by inviting more guests (and that will not always work).

Now we can construct a solution for your problem. We will initially assume that all of your friends are invited. If the required condition follows for all of them then we are done. Otherwise the party is not proper for some of your friends and as we can not add more guests to make it proper we must remove them from the party. We select one of them randomly and we remove him/her. This may make the party improper for even more guests, so we will have to remove them too. We keep removing guests one by one until the party is proper for every remaining guest. The number of the remaining guests is the answer to your problem.

This algorithm works fine. An efficient way to implement it is to have an $N \times N$ adjacency matrix in which we store binary information about "who knows who" (anti-reflexive, symmetric relationship) and $N$ pairs of integers that denote how many known and unknown people of every guest are currently at the party. These structures are initialized when you read the input. We can also have a set structure (e.g. a queue) where we insert a guest's id when we find out that the party is improper for him/her and a boolean array of size $N$ that stores who is currently invited. We pop elements from the set in order to remove the guests. When we remove a guest we update the pair of ints of every other guest according to if they know each other or not. When after an update the party is improper for a guest we insert him/her to the set in order to remove him/her later and we mark his/her position in the boolean arra to know that this guest will not be invited. When the set is empty there are no more guests to be removed so we can count how many guests are still invited to your party using the boolean array. The number of the counted invited guests is the answer.

Reading the input and initialization of the data structures has $O(N^2)$ computational complexity. We will remove at most $N$ guests and for each removal we check/update $O(N)$ values. So the total computational complexity of our algorithm is $O(N^2)$. The space complexity is also $O(N^2)$ as a result of the adjacency matrix.

Below I provide a C++ code that solves your problem using the described algorithm.

```
#include <iostream>
#include <queue>
using namespace std;

#define MAXN 105  // Maximum number of friends possible

bool adj[MAXN][MAXN];  // Adjacency matrix
// adj[x][y] = true iff x and y know each other

bool INV[MAXN];  // INV[x] = true iff x is invited to the party

int K[MAXN], U[MAXN];
// Counters for known and unknown invited guests for each guest

queue<int> Q;
// Queue with the ids of the guests that should be removed

int main()
{
    // Reding input and initializations...
    int N;  // Number of your friends
    // Assume ids in range 0 to N-1 inclusive
    cin >> N;
    int M;  // Number of connections
    cin >> M;

    // Before the connections are known to us we assume that everyone knows noone
    for (int i = 0; i < N; i++) U[i] = N - 1;

    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = true;  // x and y know each other
        // Update number of known/unknown guests for x and y
        K[x]++;
        K[y]++;
        U[x]--;
        U[y]--;
    }

    // Initially everyone is assumed to be invited
    for (int i = 0; i < N; i++) INV[i] = true;

    // Find guests that should be removed (phase 1)...
    for (int i = 0; i < N; i++)
    {
        if (K[i] < 3 || U[i] < 3)
        {
            // The party is improper for current guest
            // Save his id in the queue to remove him/her later
            Q.push(i);
            INV[i] = false;  // The guest should not be invited
        }
    }

    // Remove guests until the party is ok for everyone
    while (!Q.empty())
    {
        int rem_guest = Q.front();  // Id of a guest that we should remove
        Q.pop();
        for (int i = 0; i < N; i++) if (INV[i])
        {
            // The number of known or unknown guests for current guest is decreased
            if (adj[rem_guest][i]) K[i]--;
            else U[i]--;
            if (K[i] < 3 || U[i] < 3)
            {
                // The party is improper for current guest
                // Save his id in the queue to remove him/her later
                Q.push(i);
                INV[i] = false;  // The guest should not be invited
            }
        }
    }

    int ans = 0;  // The result variable
    // Count guests that will be invited
    for (int i = 0; i < N; i++) if (INV[i]) ans++;

    // Display answer
    cout << ans << '\n';

    return(0);
}

```

Edit:

It is also possible to construct a solution with $O(N + M)$ computational and space complexity, where $M$ is the number of connections between your friends. The main idea remains the same, you initially assume that everyone is going to be a guest and then you start to remove guests until the party is proper for everyone. What we will change is the information we keep. Let's observe why the complexity of the previous solution was $O(N^2)$.

The first reason was that we used an adjacency matrix. By replacing this structure with adjacency lists we drop the space complexity of the whole algorithm and the computational complexity of the initialization to $O(N + M)$. Note that our algorithm has nothing to lose from such a conversion. Even with no further changes we can use the adjacency lists as we used the adjacency matrix before. That's because the only use of it was to classify all of our friends to known and unknown people of a guest when this guest was removed. This can also be done if we create a boolean array of size $N$ which we initialize to false and we make true the values of it that appear in the adjacency list of the guest being removed. After that this array is equal to the row of the removed guest in the adjacency matrix that now doesn't exist (we will not do something like that, it is only used to show that in our case adjacency matrix is not needed). So there is no reason not to replace the adjacency matrix.

The second reason why the time complexity of our algorithm was $O(N^2)$ is that we updated the number of known and unknown guests of each guest every time a guest was removed, which required $O(n)$ updates. An additional observation we can make is that the number of the unknown guests of a guest can be inferred by the number of his/her known guests if we also know which is the current number of total guests, by executing a simple subtraction. Also note that, excluding the first identification of which guests should be removed (which was done after reading the input and making the initializations), after every guest removal there is a specific number of known or unknown guest of every guest that will have to be removed cause of the described removal. Specifically, if after a guest removal $L$ more guests are still invited, it is enough to check which guests have $2$ or $L - 3$ known still invited guests. These guests should be removed because they don't have enough known (in the first case) or unknown (in the second case) invited guests. In order to take advantage of these observations we can create a size $N$ array of lists where at $i$-th position we will have a list (double linked) with the ids of the not yet to be removed guests with $i$ known guests. This allows us to see which guests have exactly $3$ or $L - 3$ known guests in the party at every moment. By adding a size $N$ array of list iterators (one for every guest with the iterator showing his/her id position in the appropriate list of the previous array) we can achive $O(1)$ list change for every guest.

So the changes to the previous algorithm are the following: Use adjacency lists instead of matrix, the array of lists and the array of iterators as described above. Every time you remove a guest move all his/her known people from their current list to the previous one and then add all guests who are in list $2$ or $L - 3$ in the "to-be-removed" set and delete them from the respective list (so that you don't see them again there). You will make $O(M)$ replacements and $O(N)$ deletions in $O(1)$ each. The total computational and space complexity of the algorithm is $O(N + M)$ which is better than $O(N^2)$ for sparse graphs (where $M = o(N^2)$).

Bellow I provide C++ code for this algorithm too:

```
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

#define MAXN 105  // Maximum number of friends possible

vector<int> E[MAXN];  // Adjacency lists
// y is in E[x] vector iff x knows y

list<int> H[MAXN];  // The array of lists
// x is in H[i] iff x is currently invited and knows exactly i currently invited people

list<int>::iterator IT[MAXN];
// the iterator array, this gives you the position of each guest on the proper list

int K[MAXN];  // array that stores how many current guests does someone know

bool INV[MAXN];  // INV[x] = true iff x is invited to the party

queue<int> Q;
// Queue with the ids of the guests that should be removed

int main()
{
    // Reding input and initializations...
    int N;  // Number of your friends
    // Assume ids in range 0 to N-1 inclusive
    cin >> N;
    int M;  // Number of connections
    cin >> M;

    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        // x and y know each other
        E[x].push_back(y);
        E[y].push_back(x);
        // Increase the number of guests that x and y know by one
        K[x]++;
        K[y]++;
    }

    // Initially everyone is assumed to be invited
    for (int i = 0; i < N; i++) INV[i] = true;

    for (int i = 0; i < N; i++)
    {
        int k = K[i];  // i-th friend knows k people
        H[k].push_front(i);  // save i-th person's id in the appropriate list
        IT[i] = H[k].begin();  // save an iterator of current person's address in H[k]
    }

    int L = N;  // Initially all N guests remain in the party

    // Find guests that should be removed (phase 1)...
    for (int i = 0; i < N; i++) if (K[i] < 3 || K[i] >= N - 3)
    {
        // person with id i should be removed from the guests
        Q.push(i);
        INV[i] = false;
    }
    // Clear respective lists
    for (int i = 0; i < 3; i++) H[i].clear();
    for (int i = max(3, L - 3); i < N; i++) H[i].clear();

    // Remove guests until the party is ok for everyone
    while (!Q.empty())
    {
        int rem_guest = Q.front();  // Id of a guest that we should remove
        Q.pop();
        L--;  // Decrease the number of remaining guests by one
        for (int i = 0; i < E[rem_guest].size(); i++) if (INV[E[rem_guest][i]])
        {
            int id = E[rem_guest][i];  // id of a current guest that rem_guest knows
            // The number of known guests for current guest is decreased
            K[id]--;
            // change the list of the current guest
            H[K[id] + 1].erase(IT[id]);
            H[K[id]].push_front(id);
            IT[id] = H[K[id]].begin();
        }
        // Every guest with 2 or L-3 known guests should be removed later
        for (list<int>::iterator it = H[2].begin(); it != H[2].end(); it++)
        {
            // The party is improper for current guest
            // Save his id in the queue to remove him/her later
            Q.push(*it);
            INV[*it] = false;  // The guest should not be invited
        }
        H[2].clear();  // remove everyone from 2nd list
        if (L - 3 >= 0)
        {
            for (list<int>::iterator it = H[L - 3].begin(); it != H[L - 3].end(); it++)
            {
                // The party is improper for current guest
                // Save his id in the queue to remove him/her later
                Q.push(*it);
                INV[*it] = false;  // The guest should not be invited
            }
            H[L - 3].clear();  // remove everyone from 2nd list
        }
    }

    // L people remain invited
    // Display answer
    cout << L << '\n';

    return(0);
}

```

---
Tags: algorithms, graphs
---


# Question
Title: The barbers paradox first order logic formalization
I tried to look on the site and while I found some similar questions, I did not find the first order logic formalization of the following sentence (the basic barber's paradox), so I wanted to ask if I got the right first order logic formalization of it, and I am sure others will benefit from this thread as well.

Sentence: there exists a barber who shaves all the people that don't shave themselves.

My attempt: this complicated sentence can be made simpler by inferring that "for all of those who does not shave themselves, are shaved by the barber"

And now it seems to be easier to substitute with variables so:

$$\exists x(\lnot S(x,x) \rightarrow S(b,x))$$

where $S(x,x)$ is shaving(verb), $x$ are the persons (who don't shave themselves), and $b$ is a shortcut for barber, so if a person does not shave himself, it can be inferred that he is shaved by the barber.

# Answer
There are two issues about your formula:
First, you use an existential quantifier for the people where there should be a univeral one, since the statement is "*all* people". What your formula expresses is "There is an $x$ such that if $x$ does't shave themself, the barber does." Instead, what you want to say is that "*For all* $x$ it holds that if $x$ doesn't shave themself, the barber does." In general, an existentially quantified implicational formula is often a sign that something is wrong.
Second, instead of using a constant name $b$ for the barber, it would be better to directly translate the "There is" as an existential quantifier, and you could also specify that this someone is a barber.

Whith this, the sentence becomes

> There is a thing $y$ which is a barber and such that for all people $x$ who don't shave themselves, $y$ shaves $x$.

which translates as

$$\exists y (B(y) \land \forall x (\neg S(x,x) \to S(y,x)))$$
> 3 votes

# Answer
You're not being asked to do any inference; just to express something.

> there exists a barber who shaves all the people that don't shave themselves

translates directly as

$$\exists b\\, \forall x\\,\big(\neg S(x,x) \rightarrow S(b,x)\big)\\,.$$

(There exists a barber such that everyone who doesn't shave themself is shaved by the barber.)

Your version says that there exists a person who, if they don't shave themself, is shaved by the barber. That's not equivalent. For example, it's true in any world where at least one person *does* shave themself: just let $x$ be that person, so $\neg S(x,x)$ is false, so $\neg S(x,x)\rightarrow\text{anything}$ is true.
> 3 votes

---
Tags: logic, artificial-intelligence, first-order-logic
---


title: Pumping lemma occurrence of c > d

text:
# Question
Title: Pumping lemma occurrence of c > d
I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.

The alphabet is:

$$ \Sigma = \\{c, d\\} $$

The language is:

$$ A = \\{z \in \Sigma^\* \mid c(z) \> d(z)\\} , \text{where $c(w)$ and $d(w)$ means occurrences of $c$ or $d\in z$ }$$

I tried to define a string like so:

Pumping length = P

$$ s = c^{(P+1)}d^P $$

Here is how I tried to solve it:

If we select P = 5. Then s = ccccccddddd and split it in 3 parts. Where x = ccccccd, y = ddd and z = d. (Is that even allowed though as |xy| \<= P, but now |xy|=10 and 10\>5). If I then do y^2. Then I get s = ccccccdddddddd, so now d\>c which proves the string is not in the language. Does this then prove that the language is not regular?

# Answer
You need to show that with that arbitrary pumping length $P$, for **any** partition $c^{(P+1)}d^P = xyz$ such that $|y|\>0$ and $|xy|\leq P$, there is some $i$ such that $xy^iz \not\in A$.

Since for any partition we require that $|xy|\leq P$, then $x$ and $y$ necessarily consist only of $c$'s. Also, you know that $|y| \>0$ (it's also a requirement). Can you find an $i\in\mathbb{N}$ such that the amount of $c$'s in $xy^iz$ is less than or equal to the amount of $d$'s?
> 2 votes

# Answer
You need to pick a string that's in the language (i.e., has fewer $d$s than $c$s) but, when pumped, creates strings that are not in the language (more $d$s than $c$s). Think about how you can achieve that.
> 1 votes

---
Tags: computability, finite-automata, pumping-lemma
---


# Question
Title: Language to Generate Powers of 2 Using a Language Containing Decimal Numbers
For this question, I have the alphabet $\Sigma=\\{0,1,2,3,4,5,6,7,8,9\\}$. I also have the language $L$ over $\Sigma$ described as the language such that the strings $w$ contained in $L$ are powers of 2 and $w$ is treated as a decimal number. I then need to:

1. Design a grammar to generate $L$
2. Classify the grammar (Regular, Context-free, etc.)
3. Show that $L$ is not regular
4. Determine if $L$ is a context-free language (answering only yes or no)

The original question is in the image below, for reference.  I'm not entirely sure how to start on this question in particular. Most of the examples I had in my automata class consisted of much smaller alphabets and more precise languages. Any help with an explanation would be much appreciated.

Thank you in advance!

# Answer
### L is not context-free

**Periodicity for context-free languages of bounded growth**: Let $w\_n$ be the number of words of length $n$ in a given regular language. If the sequence $w\_1, w\_2, \cdots$ is bounded (bounded growth), then it is eventually periodic.

Proof: This follows from the fact that every context-free language of bounded growth is a union of paired loops, which is the theorem 2.1 in the paper On a conjecture about slender context-free languages by Lucian Ilie, 1994.

---

Let $w\_n$ be the number of words of length $n$ in $L$. $w\_n=\\#\\{k\in\Bbb N\mid n-1\le k\log\_{10}2 \lt n\\}$. Since $\log\_{10}2$ is irrational, the sequence $w\_1, w\_2, \cdots$ cannot be eventually periodic. So $L$ is not context-free. Hence, it is not regular, either.

As rici pointed out, it is not difficult to prove that $L$ is not context free by applying the pumping lemma to any word in $L$ that is long enough. The above more conceptual proof is presented in the hope that it might raise more interest and more questions.

## $L$ is context-sensitive

According to rici's comment, we can write a context-sensitive grammar which multiplies a decimal number by two. Use marker tokens which move right to left over the number; you'll need two of them because of the possibility of carry. As with many other cases of context-sensitive grammars, the actual construction might be apt to get lengthy and tricky, sometimes even debatable.

Another conceptual way to see $L$ is context-sensitive is using linear bounded automaton (LBA) that accepts a context-sensitive language. It is easy to see that we can divide by 2 repeatedly using a linear bounded automaton. More specifically, we can design a LBA such that given an input of $S m E$, where $m$ is a sequence of decimal digits and where $S$ and $E$ are start marker and end marker respectively, it will output $S1\square\square\cdots\square E$, where $\square$ stands for the special blank symbol if and only if $m$ is the decimal representation of some power of 2.

### An exercise

Let language $L\_U$ over $\Sigma=\\{0,1,2,3,4,5,6,7,8,9\\}$ be the language of words which are positive integers whose prime factors belong to a finite set $U$ of prime numbers when they are treated as decimal numbers. Show that $L\_U$ is context-sensitive but not context-free.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: What uses have been proposed for overlaid skewed associativity?
In "Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB" (2004; PDF), André Seznec proposed using overlaid ways with different indexing functions with guaranteed avoidance of bank conflicts. This mechanism allows TLB look-ups for multiple page sizes to be done in parallel without the overheads of CAM-based TLBs or the capacity mis-match issues of a separate TLB for each size. (TANSTAAFL: This comes at the cost of reduced associativity for each page size and does not work well with a wide range of page sizes where less significant bits can not be used by all page sizes to determine the bank.)

I have termed multiple indexing functions sharing a single memory array "overlaying", though there might be a better name.

Mohsen Sharifi and Behrouz Zolfaghari proposed using multiple indexing functions with a single bank to reduce conflict misses ("YAARC: yet another approach to further reducing the rate of conflict misses", 2007, PDF)

"Skewed Compressed Caches" (Somayeh Sardashti et al., 2014; PDF) exploits unified storage to avoid conflict misses when a superblock of memory has variable compressibility.

(The merged-associative TLB proposed in Arkaprava Basu's PhD dissertation "Revisiting Virtual Memory" (2013; PDF 6.5MB) allows the OS to specify a page size by virtual address ranges that exclusively use that page size so that all banks of the TLB can be indexed in parallel. This does not overlay the banks, though it could be trivially extended to do so; similarly page-size prediction could be used (as probably presented in "Prediction-based superpage-friendly TLB designs", Misel-Myrto Papadopoulou et al., 2015, showing the similarity to hash-rehash).)

Despite the fact that Seznec proposed the idea over a decade ago, I have not found other explorations of its utility. Are there any other proposed uses for this mechanism of overlaying ways?

# Answer
> 1 votes
The following possible uses come to mind, though I am not aware of any academic exploration of these ideas.

### Way Dueling

One possible use is to extend the range of set-dueling. Presented in Moinuddin K. Qureshi et al.'s "Adaptive Insertion Policies for High Performance Caching" (2007), the "Set Dueling mechanism dedicates a few sets of the cache to each of the two competing policies and uses the policy that performs better on the dedicated sets for the remaining follower sets." By linking policies with ways in an overlaid skewed associative cache the number of entries monitored can be extended without sacrificing capacity available to a given policy (though the associativity linked to a policy would be lower).

The number of policy-bound entries in a way could also be adjusted dynamically to trade off training sensitivity with associativity of the preferred policy. It is not clear if competition for the same entries would also have benefits; the degree of sharing of monitored entries could also be adjusted dynamically.

### Indirect Jump Target Predictor

In predicting indirect jump targets, some jumps are best predicted simply using the jump instruction address, some jumps are better predicted with history information included in the indexing. This is very similar to André Seznec's original TLB proposal in allowing capacity sharing with different indexing methods while not requiring reprobing (though reprobing could supplement the number of indexing methods, possibly filtered with information from the first probing). More than one non-null sets of history information could be used, and direct jump targets could be included along with single-target indirect jumps.

More specific predictions might be favored, making the instruction-address-based indexed prediction a default prediction.

### Virtual Non-Temporal Cache

With overlaid skewed associativity, it could be practical to associate one or more ways with non-temporal access and use indexing functions for such ways which induce conflicts. For example, by simply dropping bits 6..11 of the block number (indexing by bits 0..5,12..N), a 64-block region would conflict with itself 64-times in a stream. (By XORing specific middle and least significant bits, streams with power-of-two block-strides could be allocated densely while still providing self-conflict across groups of blocks.)

Such would have the advantage over a dedicated non-temporal cache of allowing the capacity to be used more flexibly and the advantage of potentially lower semi-reserved capacity compared to LRU placement of non-temporal data in a traditionally indexed cache (where effectively an entire way worth of data would be allocated to a stream of non-temporal data).

Since different ways (and different portions thereof) could have different degrees of inducing conflicts and less conflicting ways could be selectively used, the amount of capacity allowed to a stream could be somewhat flexible and conflicts between streams might be more easily managed.

While conflict-inducing indexing could be used with isolated ways, overlaying would allow capacity to be used more flexibly and allows conflict *between ways* to push out data that will not be re-referenced.

### Variably aligned Blocks

By associating different ways with different alignments of cache blocks, larger blocks can be more practical when there is significant spatial locality but the chunk of data that is accessed together does not start at a highly aligned address. Such could facilitate the use of larger blocks with less unused capacity. Larger blocks can reduce tag overhead and increase the accuracy of way prediction (or the utility of way memoization).

Such might be especially useful for instruction caches (benefitting more from spatial locality and being more friendly to way prediction/memoization), especially branch target instruction caches. Certain trace-oriented pre-decode optimizations might be made more practical by reducing the number of entry points within a cache block. A smaller (faster, more energy-efficient) portion of an instruction cache could be preferentially used for branch targets, avoiding redirection delay like a BTIC but allowing the capacity to be used for non-branch target blocks.

(For data caches, unaligned storage might be useful for something like a signature cache, reducing the disadvantage of non-CAM tags.???)

Similarly, a branch target instruction cache placed after the instruction cache could exploit variable alignment of function entry points without the tag overhead of using multiple smaller blocks.

### Stride-based Data Mapping

Similar to using ways to map to different alignments, it would also be possible to have different ways use different subblock strides. For example, a way could map data *within a block* such that alternating words are excluded, not only increasing utilized capacity when stride-of-two accesses are used but also potentially facilitating fixed-stride SIMD loads and stores.

It might even be practical to support configurable power-of-two strides as long as the stride does not change often.

(A data trace cache might benefit from both supporting different alignments and different chunk compositions (e.g., 32-bit address offset/compressed address vs. 64-bit address, address only vs. address plus N bytes of data). This ties in with intra-block NUMA.)

### Binding storage-type to way groups

In a unified cache, one group of ways could be dedicated to instructions and another to data. Such grouping of ways would facilitate lower associativity in at least initial look-up.

This could also be applied to metadata interpretation, different ways storing different types of metadata. For example, some ways could use ECC (requiring read-modify-write on sub-word stores) and some use parity (for lower-overhead sub-word stores, but lower reliability); such could interact with storage reliability where, e.g., ECC-using blocks in high reliability SRAM might allow greater voltage reduction and parity-protected ways might only allocate clean blocks to less reliable SRAM arrays.

### Way-based block size

While conventional non-overlaid caches could associate a tag with a pair of storage blocks, using additional ways dedicated to larger blocks would tend to require fewer tag checks. Skewed indexing, especially when overlaid, would reduce conflict increase from clumping of cached data have more spatial locality. In any case, extra tags could be used for dataless inclusion or other metadata, though the increased flexibility of allocation with overlaying would tend to increase opportunities for such alternative uses.

### Variable Characteristics of Storage

By overlaying ways, a portion of each way can be mapped to a section of cache which provides faster (or more energy-efficient) access or different amounts of metadata (different types of metadata was mentioned earlier).

By increasing the independence of cache properties and data address via overlaid skewed associaitity, more direct indexing could be used while still supporting differences in characteristics of specific storage locations.

While not as flexible in allocation as a traditional Non-Uniform Cache Architecture (which uses a layer of indirection), such might make NUCA techniques more applicable to L1 caches. (The problem of scheduling dependent operations given variable L1 cache latency would still need to be addressed. In addition, the aliasing issues of L1 skewed associativity would have to be handled.)

(The way indication itself can provide some metadata when ways are reserved for or biased toward specific uses or policies.)

It might also be practical to have portions of the cache (whether specific ways or sections of various ways) use subblock NUCA where a portion of blocks have faster access (e.g., to accelerate pointer-chasing code). While always using fast subblock allocation (with different subblocks being selected by way and/or address) could be implemented in a somewhat straightforward way, variable allocation of fast storage (e.g., where 64-byte blocks might be mapped to four fast 16-byte storage units, one fast storage unit and three slow ones, or four slow storage units) would seem to be difficult.

Such separation could be accomplished in non-overlaid cache by the same association of way/address with cache characteristic, but flexibility of allocation would be lower.

### Further Disconnecting Associativity and Capacity

With overlaying, conflict increasing squeezing of portions of ways can be mapped to different storage sections in different ways and accesses from different ways can compete for a given entry.

Partial overlaying provides another dimension of design flexibility. For example, a two-way associative cache might map one way such that half maps to an isolated section and half to an overlaid section and map the other way with its own isolated section (and the common shared section). This kind of partial overlapping might be useful for a Knapsack-like cache ("Knapsack: A Zero-Cycle Memory Hierarchy Component", Todd M. Austin et al., 1993) where a part of the storage could be dedicated to a restricted caching while another part can be used for other accesses as well (e.g., a two-way associative section could be used traditionally while also allowing the Knapsack region to be larger and somewhat sparse in the higher addresses; the amount of contention and the replacement preferences could be somewhat flexibly designed \[some similarity might be noted to Brannon Batson and T. N. Vijaykumar's "Reactive-Associative Caches"\]).

Isolated ways can provide separation of associativity and capacity by having some ways be smaller than others. However, overlaying provides slightly more flexibility in allocation of capacity. With isolated ways, a given block will always be in a higher conflict section (though this can be compensated by increasing the associativity of the smaller section).

### Potentially Greater Virtual Machine Isolation

By overlaying and using different indexing functions for different virtual machines, cache capacity might be more readily provided to virtual machines with less side channel information being communicated.

Traditional skewed associativity with per-VM indexing adjustment would provide most of this benefit, but overlaying provides a little more flexibility in placement and in what mappings can conflict for different pairs of virtual machines.

### Multithreading Conflict Containment

Partial overlaying could be used to isolate a portion of the data associated with a thread while still providing substantial capacity sharing. Such would provide more flexible allocation than assigning a traditional way or ways to a thread-specific storage area.

Partial overlaying would facilitate having higher associativity in a subset of cache, which could be advantageous in storage shared by more threads or used for allocations more likely to induce conflict misses or for which conflict misses are more expensive.

In a clustered design, overlaying could be useful for biasing placement to reduce inter-cluster communication when threads are biased or exclusively allocated to particular clusters.

#### Way Prediction Implications

While skewed associativity may increase the accuracy of partial-tag-based and recency-based way prediction (because spatially local blocks are likely to be mapped to different indexes for different address regions), overlaying may provide a slight further benefit.

(Likewise, biasing allocation to improve way prediction should increase the miss rate less with skewed associativity and especially overlaid skewed associativity than with simple modulo indexing.)

#### Defect and Block-locking Tolerance

While not a mechanism, it might be worth noting that using overlaying would reduce the impact of excluding certain blocks from allocation choices. While traditional skewed associativity increases conflict resistance in such cases, overlaying would provide a further benefit.

Similarly, locking a chunk of cache could provide the implementation simplicity of traditional way locking with less reduction in effective associativity. (As a side note, mapping a chunk of cache to a specific address to form a scratchpad memory would free the associated tag memory for other uses. For example, half normal size blocks could be supported for part of the remaining cache; overlaid skewed associativity might facilitate flexible allocation of small blocks.)

### Reduced indirection overhead for NUCA

Using overlaying would allow different addresses to map to the same block, potentially avoiding the traditional indirection of traditional NUCA while still allowing substantial flexibility in allocation of cache entries into faster storage. Lack of indirection would facilitate placing tags closer to data clusters, at least for the faster storage area (it may be desirable to co-locate all tags to provide faster miss determination, though a cache shared by multiple cores or even just multiple access paths (e.g., instruction vs. data) might have distinct fast storage with associated tags). Even if indirection is used, overlaying would reduce the costs of less general indirection, reducing metadata storage overhead and potentially access latency.

A fixed but different slice for each way would have similar benefits in terms of allowing different addresses to be placed in fast storage with quick lookup, but overlaying increases allocation flexibility.

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


# Question
Title: On a semiconductor chip, what state (on/off or read/write) corresponds to conducting or insulating behavior?
My textbook has a brief explanation of how semiconductors are used in modern computer chips because they can be made to conduct (by applying enough voltage to excite electrons across the band gap) or to insulate (by dropping the voltage to a lower level or shutting it off entirely) and this conditional, binary state can be used as an 'on/off' logic gate.

In modern computer systems, which state is "on" and which is "off"? In other words, is it the case that when we increase the voltage to cause conductance in the semiconductor that we have a "1" value and that when we drop the voltage down, we have a "0" value, or is it the other way around?

Or is it more appropriate to say "read" vs "write"?

Does the on/off or read/write state vary from one manufacturer to another? Or from one type of memory to another? I.e. does DDR SDRAM use conducting as "on" and insulating as "off" while other forms do it the other way around?

P.S. If comp sci isn't the right SE, please could you advise a better SE for this question?

# Answer
> 1 votes
In order to understand how physical background of the computers works, you should consider higher-level abstractions of the semiconductors. Otherwise, you will get stuck in a mess of semiconductors. Without basic knowledge of transistors and how these transistors form a logic gate, it will not be easy to comprehend the memory structures and read/write cycles.

To visualize, in CMOS technology, there are two complementary logic structures where one of them is connected to the ground and the other one is connnected to the high voltage source. In rest, these structures are "on" and "off" complementarily. When your output changes, on-off states of them are inverted, thus there are both 'on' and 'off' logic in every case. The scheme is completely different in another technology, let's say PTL.

In the memory case, 'HIGH' and 'LOW' voltages represent immediate memory state rather than individual 'conducting' and 'insulating' states of transistors. If a transistor between low voltage source and your memory output is 'conducting' while a transistor between high voltage source and your memory node is 'insulating', then you have a 'logic 0'. Still, all of them are technology dependent.

# Answer
> 0 votes
In general it is conventional to use high voltage for true/one and low voltage for false/zero. In fact, a notation with the signal name overscored ($\overline{SIGNAL}$) is used to indicate active-low (alternatively SIGNAL#).

This convention is somewhat arbitrary, like programming languages associating true/false with 1/0. In addition, information can be encoded in less conventional ways (e.g., Gray code, memory scrambling, error correcting codes) and more than two voltage levels can be used.

---
Tags: computer-architecture
---