title: Does the OS come in the hard drive?

text:
# Question
Title: Does the OS come in the hard drive?
This might be a a simple and for some a silly question as well.

If I buy two hard drives and have windows in one and Ubuntu in the other, can I work with both two systems(one at a time).

Example, I wanna edit a photo and I quickly need to go to Adobe Photoshop, so I plug in the Windows harddrive and start editing, then I remember I need to code something real quick so I remove the windows hardrive and plug in the Ubuntu hardrive and start working.

Does it work this way? Is it impractical? Enlighten me.

I could use a VirtualBox, but I want to know if the above is possible.

# Answer
Yes, you could do that but it is rather awkward. Instead, you can use a boot loader which can load an operating system pass on the execution to it. Many issues and caveats on multi-booting exist.

In addition, you can use virtualization (for example, Docker is popular) to run say a Linux machine on your host Windows machine.
> 1 votes

# Answer
Nowadays people don't want their stolen computers to be used by a thief, and they don't want a thief to boot from an external hard drive and somehow manage to access their secrets on an internal drive.

So it is quite possible that an alternative boot drive has to be created on the original machine.
> 0 votes

---
Tags: memory-hardware, os-kernel
---


# Question
Title: Race condition, my doubt on Peterson's algorithm vs. C
I have seen this C code showing an implentation of Peterson's Critical Section algorithm. It is obviously skeletal and hardwired for two threads but the logic is supposed to be correct in detail.

Despite reading and talking I remain with a grain of doubt about the following line (and the similar line for Thread B):

> \`while (turn == 1 && flag1) skip;

When it is compiled, the while clause will generate multiple instructions which it seems to me can lead to a race condition in a pre-emptive scheduling model.

While I trust the proofs etc. I have not seen a good way to refute my concern.

(I know this is an oldie but goodie so feel free to respond with a link.)

# Answer
> When it is compiled, the while clause will generate multiple instructions which it seems to me can lead to a race condition in a pre-emptive scheduling model.

This is the technical beauty of Peterson's algorithm. Even though there could be many possible execution paths for this short and simple-looking code, it guarantees mutual exclusion, progress and bounded waiting. (Bounded waiting is not guaranteed for more than two participating threads, though).

On first sight, it looks there is a race condition on which thread will set the value of "turn", especially in a pre-emptive scheduling model. However, a close analysis will show neither does this race condition corrupt the mutual exclusion nor does it prevent progress. Here is the basic analysis on mutual exclusion by Wikipedia, adapted for the variable names here.

> `Thread A` and `Thread B` can never be in their critical sections at the same time. If `Thread A` is in its critical section, then `flag0` is `TRUE`. In addition,
>
> * either `flag1` is `FALSE`, meaning that `Thread B` has left its critical section,
> * or `turn` is `0`, meaning that `Thread B` is just now trying to enter its critical section, but graciously waiting,
> * or `Thread B` is right before the line `turn = 0`, trying to enter its critical section, after setting `flag1` to `TRUE` but before setting `turn` to `0` and busy waiting.
>
> So if both threads are in their critical sections, then we conclude that the state must satisfy `flag0` and `flag1` and `turn = 0` and `turn = 1`. No state can satisfy both `turn = 0` and `turn = 1`, so there can be no state where both threads are in their critical sections.

Note that the analysis above is programming-language independent. It does not matter you use C, Java, Python, assembly, etc.

Note that the analysis above only assumes that the code/instruction in each thread is executed/implemented serially. Whether there is a race condition to set `turn` or whether the scheduling model is pre-emptive does not matter.

As you could have insisted, it is not convincing enough with the explanation above, nor with many similar high-level arguments in textbooks. Currency is too subtle, delicate and illusive for involving propositions to be proved easily, usually.

People have spent great efforts proving propositions involving concurrency (in a pre-emptive scheduling model). For example, Uri Abraham's paper The assertional versus Tarskian methods presents two formal proofs on the correctness of the Peterson's algorithm, together with an enlightening and convincing clarification on what is a formal proof. You will be convinced beyond any doubt if you have finished reading it or just half of it. (I do not remember whether I have finished reading that paper, though.)
> 2 votes

# Answer
For starters, one could model this in one's favourite model-checking language such as Promela and explore the model with spin.

With the basic atomic awaits, the code could look like this

```
#include "critical3.h"

bool wantp = false, wantq = false, last = 1

active proctype p()
{
  do
    :: non_critical_section('p');
wap:   wantp = true;
       last = 1;
       (!wantq || last == 0);
csp:   critical_section('p');
       wantp = false
  od
}

active proctype q()
{
  do
    :: non_critical_section('q');
waq:   wantq = true;
       last = 0;
       (!wantp || last == 1);
csq:   critical_section('q');
       wantq = false
  od
}

ltl mutex { !<>(p@csp && q@csq) }
ltl dlf   { [](p@wap && q@waq -> <>(p@csp || q@csq)) }
ltl aud   { [](p@wap && ([](!q@waq)) -> <>p@csp) }
ltl ee    { [](p@wap -> <>p@csp) }

```

where the included `critical3.h` is

```
/*
  Definitions for 2 process critical sections; derived from Ben-Ari's.
*/

inline critical_section(proc) {
     printf("MSC: %c in CS\n", proc);
}

inline non_critical_section(proc) {
  printf("MSC: %c in non-CS\n", proc);
  do                            /* non-deterministically choose how
                                   long to stay, even forever */
    :: true ->
         skip
    :: true ->
         break
  od
}

```

Here's a version with explicit non-atomic awaits.

```
#include "critical3.h"

bool wantp = false, wantq = false, last = 1

active proctype p()
{
  do
    :: non_critical_section('p');
wap:   wantp = true;
       last = 1;
tp:    if
         :: !wantq -> goto csp
         :: else
       fi
       if
         :: last == 0 -> goto csp
         :: else -> goto tp
       fi
csp:   critical_section('p');
       wantp = false
  od
}

active proctype q()
{
  do
    :: non_critical_section('q');
waq:   wantq = true;
       last = 0;
tq:    if
         :: !wantp -> goto csq
         :: else -> skip
       fi
       if
         :: last == 1 -> goto csq
         :: else -> goto tq
       fi
csq:   critical_section('q');
       wantq = false
  od
}

ltl mutex { !<>(p@csp && q@csq) }
ltl dlf   { [](p@wap && q@waq -> <>(p@csp || q@csq)) }
ltl aud   { [](p@wap && ([](!q@waq)) -> <>p@csp) }
ltl ee    { [](p@wap -> <>p@csp) }

```

Exploring these models with spin reveals that both have the 4 claimed properties of a mutual exclusion algorithm, *mutual exclusion* (formalised as LTL property `mutex`), \_deadlock-freedom (`dlf`), *absence of unnecessary delay* (`aud`), and *eventual entry* (`ee`). The last 3 require weak fairness, otherwise the execution could end with the other process doing infinitely many steps in its non-critical section.

Crucially, this model is faithful only for sequentially consistent hardware. Modern multi-core CPUs do *not* satisfy that assumption. One could use fence instructions to salvage correctness Peterson on architectures with weaker memory models (such as ARM's PSO and Intel's TSO).
> 2 votes

---
Tags: algorithms, operating-systems, threads, critical-section
---


# Question
Title: Constructing a deterministic finite automaton from a particular regular expression
This is the given question-

**Construct a DFA over the alphabet {0,1} such that it accepts all strings containing even number of 0's ***OR*** the number of 1's divisible by 3.**

The very first problem I've encountered was the 'or' mentioned in the question. Does this mean i just '+' the RegEx for -'accepts all strings containing even number of 0's' and the RegEx for- 'the number of 1's divisible by 3'?

Anyways, this was the approach that I'd tried. I ended up with this RegEx- `(1*01*01*)*1* | ((0*10*10*10*)*0*)*`

The first part is to check for an even number of 0s and the latter part is to ensure that the number of 1s is divisible by 3. Firstly I'm not sure if this RegEx is right. Let's assume it is-

Now when i try to construct the epsilon-NFA, the conversion took an insane amount of pages and finally when i put it into the converter to convert it into a DFA, it says 'encountered infinite transition loop'.

I dont recall problems of this level being discussed in the class and I'd appreciate any help I can get

Thank you

# Answer
> 1 votes
It is a detour to construct the automaton by first determining a regular expression. The description of the languages gives enough information to obtain possible states for the automaton.

To check whether the number of $0$'s is even we count modulo two. To check divisibility by three of the number of $1$'s we need three states. As we have to keep track of these at the same time we have $2\times 3$ states.

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


# Question
Title: Is there a typo in this excerpt from the book?
Michael Sipser's Introduction to Theory of Computation:

Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a state of M.

It also says that E(R) is 'the collection of states that can be reached from members of R by going only along ε arrows, including the members of R themselves' which means that both R and E(R) are sets of states of N.

But then it says that 'q', an element of E(R) can contain, can be reached from 'R'. The problem is that 'q' is an element of E(R) which is a set of states of N while R is a state of M. How can you reach a state of N from one of M?

# Answer
> 1 votes
To clarify, I think they meant that $$E(R)=\\{q|\exists s\in R, q\text{ can be reached from $s$ by $0$ or more $\epsilon$ transitions}\\}$$

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


# Question
Title: How would this grammar be converted to a non-left recursive rule?
With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing.

How would this grammar be converted to be non-left recursive?

```
S-> Aa | b, A -> Ac | Sd | epsilon

```

I have gotten this far but I am not sure if it is correct.

```
S-> bS'
S'-> epsilon | AaS'
A-> SdA'
A'-> cA'

```

I wasn't sure if the 'S' rule had to be changed since it did not have an 'S'(itself) in it. From reading online, it looked like each rule should be checked before starting to change it but I'm a bit stuck right now. Does anyone know if this is the right approach or have any suggestions?

# Answer
> 1 votes
The given grammar has a direct and an indirect recursion. There is no rule to solve this or such which mentions whether any production is to be changed or not. However one way to keep things clear would be to consider one rule at a time for removing left recursion, which in your case would be as follows $$S\rightarrow Aa\mid b$$$$A\rightarrow Ac\mid Sd\mid \epsilon$$

Removing left recursion from productions of $A$ $$A\rightarrow Sd{A}'\mid {A}'$$$${A}'\rightarrow c{A}'\mid \epsilon$$

substituting these productions in the productions of $S$ and removing left recursion$$S\rightarrow {A}'a{S}'\mid b{S}'$$$${S}'\rightarrow d{A}'a{S}'\mid \epsilon$$

This is just one way. Likewise you could remove the indirect recursion first and work it out.

---
Tags: formal-grammars, left-recursion
---


# Question
Title: Can a program that terminates have a running time of infinity? (Or not have an upper bound)
Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?

A (non-)example which shows what I mean: If let's say that my algorithm is one that takes an input number, generates a random number, adds them both and puts the program to sleep for that number of seconds. Would the running time here be unbounded (even though the algorithm would terminate)? I can see how in this example, it might not be, because we can represent the running time in terms of both the input size and the randomly generated number.

But could there be some other (possibly non-deterministic) algorithm with such traits? That does something random to the input, terminates and does not have an upper bound for worst-case running time?

Thank you!

# Answer
Since you allow inputs, you can imagine a program that inputs a natural number $n$ and then performs $n$ steps. No further randomness is required.

More interesting is the case without inputs. If you want an input-less, terminating program with unbounded executions then you require a source of (countably) infinite randomness. Without that source, the program's executions form a finitely branching tree. By König's lemma that tree cannot have infinitely many nodes without also having an infinite path. The latter would be a non-terminating execution.
> 2 votes

# Answer
Sure. Consider the following algorithm: flip a fair coin; if it is heads, terminate; if it is tails, go back to the beginning and repeat. There is no upper limit to the amount of time this algorithm could take.
> 0 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, randomized-algorithms, infinity
---


# Question
Title: Is order important in Structural Equivalence?
From 6.3.2 of Aho *et al.*

> When type expressions are represented by graphs, two types are structurally equivalent if and only if one of the following conditions is true:
>
> * They are the same basic type.
> * They are formed by applying the same constructor to structurally equivalent types.
> * One is a type name that denotes the other.
>
> If type names are treated as standing for themselves, then the first two conditions in the above definition lead to name equivalence of type expressions.

1. What do they mean by *formed by applying the same constructor*?
2. If we consider the following in C

```
typedef struct a{
    int x;
    float y;
} a;

typedef struct b{
    float y;
    int x;
} b;

```

By the book's definition, would `a` and `b` be structurally equivalent?

# Answer
> 2 votes
A type constructor is a way to build a type from other types (possibly zero other types), in the same way that a value constructor is a way to build a value from (possibly 0) other values. Constructors are usually identified by a name. The details can vary between programming languages; in my examples I'll use a syntax similar to ML (but with type constructors prefixed, not postfixed) and Haskell.

For example, `int` is a type expression, whose values are integers (within a range that depends on the implementation). `list(int)` is a type expression, whose values are lists of integers. `list` is a type constructor that takes one argument (the type of the list elements). `int` is a type constructor that takes zero arguments. `int * float` is a type expression, whose values are pairs consisting of one integer and one floating-point value. `*` is a type constructor that takes two arguments (the type of the first value and the type of the second value). `int -> float` is a type expression, whose values are functions from integers to floats. `->` is a type constructor that takes two arguments (the domain and the range of the function).

Two type expressions are structurally equivalent if they are essentially the same type, but using different names. For example, after a definition

```
type int_list = list(int)

```

the types `int_list * float` and `list(int) * float` are structurally equivalent, since `int_list` is s.e. to `list(int)` (rule 3), `float` is s.e. to `float` (rule 1), and applying the type constructor `*` to s.e. types yields s.e. types (rule 2).

In simple cases, two type expressions are structurally equivalent if you get the exact same expression after expanding all type abbreviations in both. However, this necessarily doesn't work with recursive type definitions, where expanding all abbreviations might not terminate.

You can't reorder the arguments of a type constructor. That results in a different type. `int * float` and `float * int` are not structurally equivalent. Intuitively, their values have different shapes. If you had a computer where `int` and `float` values are stored in different kinds of memory cells, the two types would need to be stored differently. This is more obvious if you consider the function type constructor: `int -> float` and `float -> int` are completely unrelated types.

Intuitively, if two types $T\_1$ and $T\_2$ are structurally equivalent, then they have the same memory layout. You can write a value of type $T\_1$ in memory, and read it back as type $T\_2$. (An implementation doesn't have to follow this property, but if it doesn't, that would likely mean that the formalization of the type system is missing some information about the language.) Note that the converse is not true: it's common to have different types with the same layout in memory. For example, in C, `struct {int a;}` and `struct {int b;}` have the same layout in memory (and you can cast pointers between the two), but they aren't compatible types (you can't assign from one directly to the other). Furthermore, many languages treat some structurally equivalent types as distinct: that's the whole point of having abstract types.

A pair of types like `(int * float, float * int)` or the two structures in your question are not structurally equivalent. They aren't compatible and they don't have the same layout in memory. They do have an interesting property that you can build a pair of bijections between the two types that obeys the structure of the data. I don't know if there's an established name for this kind of equivalence; it's a kind of structural or algebraic isomorphism.

---
Tags: compilers, types
---


# Question
Title: Why is there no polynomial time verifier for N Queens
The N-Queens in question is referring to the one where it is interested in finding all solutions for some natural number n. I just read about the idea of a verifier being an algorithm that verifies whether it accepts an input and a "certificate".

So say for example that I want to check some configuration of n queens in an n x n chessboard. Can I not loop over each queen and check if every cell that it can reach has another queen in it? And if I finish every queen and find no collision, determine that it is a valid configuration?

What am I missing that makes the verification of this problem non polynomial time?

# Answer
You're not missing anything. Verifying that a candidate solution is valid (i.e., that no queen attacks any other) can be done in polynomial time.

Finding a solution might take more than polynomial time (I don't know). Also, checking whether $n$ is the smallest possible value such that you can place $n$ queens in a valid way also might take more than polynomial time (I don't know).
> 2 votes

# Answer
Problem: Given an integer n \>= 1, is there a way to put n queens on an n by n chessboard so that none attacks another one?

The algorithm “return “yes” if and only if n != 2 and n != 3” may be correct and runs in O(1). Assume this is not true or not provable.

I’m unsure if an actual solution can be found in polynomial time in n or not, but that is just my opinion. If you put queens on the first rows, it’s quite possible easy to put queens on the first 950 of 1000 rows, and not very hard to fill the remaining rows.

It can’t be done in polynomial time in the size of n. That would be a polynomial in log(n) and you can’t even copy a solution in that time.
> -1 votes

---
Tags: algorithms, np-hard
---


# Question
Title: What is a good load factor for seperate chaining (closed addressing)?
For open addressing, I know that once you have around 70% table being filled you should resize because more than that you get collision.

But for closed addressing, I read that load factor should not exceed 1 **(m/n where m = number of items in the buckets and n = size of the table)** otherwise trigger rehashing to grow the hashtable, which I find to have two problems:

1. We could have 6 items in one bucket and the size of the table is 6 so we have load factor of 1 which supposed to be a good but in reality we have a terrible hashtable.
2. if we spread the items ot the table we are only allowed to have one items per a chain (or bucket) for example if we have 7 items, and the size of the hashtable is 6, we can't have a bucket that holds 2 items or we trigger a rehashing.

if you have more items than the size of the hashtable it results a trigger, unless I am miss calculating something (which highly possible).

so how load factor works in seperate chaining ? what is the magical number to trigger resizing if exceeded? how many items per bucket can we have if the hash function is good and we spread the items all over the hash table?

# Answer
There is actually a very simple answer: Measure. If you cannot measure the difference between different load factors then the whole question is pointless.

The actual optimal load factor depends on the cost of calculating hash values, cost of comparing items with same hash value, performance cost of having a larger hash table, and all these depend on your exact implementation.
> 1 votes

# Answer
According to this Python does a rehashing when the load factor reaches $2/3$.
> 0 votes

# Answer
When you look up a value in a hash table, the minimum cost is: One calculation of the values hash code. One calculation of a location where the value would likely to be stored if it was present in the hash table. One comparison of two hash codes. If they match, one comparison of values.

Additional cost is: Checking whether the slot is unused (in that case there is no value with the hash code), and visiting additional locations.

The case that there is an entry with the correct hash code but the wrong value should be extremely rare. If it is not, that's not a problem with the load factor - fix the hash function instead. We can basically ignore this.

So we need to rebuild the hash table if the cost of finding more possible locations and comparing hash values is large compared to the cost of calculating one hash value and comparing two values that are equal. If the values to be hashed are integers, calculating the hash value and comparing two values is quite cheap. If the values to be hashed are strings containing Unicode with *correct* comparison, calculating hash codes and comparing strings will be expensive, and you can allow quite a large load factor.

And storage isn't free. A larger hash table (same number of entries but smaller load factor) will be slower purely because of its larger size.
> 0 votes

---
Tags: algorithms, data-structures, hash-tables
---


# Question
Title: Determining number of elements divisible by at least one prime of set
I have an array ($|A|\leq 10^6$) of numbers ($A\_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

> Array: {3,5,7,15,21,143}
>
> Set: {3,5,7}
>
> Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count\[3\]=3, count\[5\]=2, count\[7\]=2, count\[11\]=1, count\[13\]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?

# Answer
One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.
> 1 votes

# Answer
If the number of numbers in the given array is no more than $10^6$, each of which is no larger than $10^6$, and the number of primes is no more than 10, then the way to move forward is apparently the following simplest algorithm in usual situations.

```
Initiate a boolean array A of False of size 1 plus the maximum of all numbers or just 1000001.
for each given prime number p:
    mark elements at A[p], A[2p], A[3p], etc until the end of array as True.
let count = 0
for each given number n:
    if A[n] is False, add count by 1
return count

```

The above algorithm is simple to code. It runs very fast since there is no division. It is likely to be faster than all other algorithms when the density of numbers is over 1/10, such as over $10^4$ numbers each of them is smaller than $10^5$, or over $10^5$ numbers each of them is smaller than $10^6$.

The algorithm could be improved if we also know or compute the smallest and the maximal number of all given numbers.

This algorithm will be very inefficient if we just have, for example, two numbers, 1 and $10^6$, and 10 primes numbers. However, it won't need a split of second on a normal computer, still. There is no visible incentive to go for a more efficient algorithm, which will probably be harder to code.
> 1 votes

# Answer
Ok, so first and foremost: If some number X appears multiple times in A, we can calculate the answer for X once and just check the precalculated answer.

So basically, now we have 10^6 distinct numbers. AKA, 1,2,3...10^6. Good! So we just have to calculate the answer for all numbers between 1 and 10^6.

The second observation it's trivial to see that if the divisors set contains repeated numbers we can just erase the repetitions.

So now the divisors set only has distinct elements. Cool! Now a kinda brute force algorithm will work.

For each divisor X we will mark their multiples as "divisible". Please notice the number X has 10^6/X divisors.

You can see the code below of how this works:

```
#include <iostream>
#define MAX 1000005
///If I already added X to the set
bool already_computed[MAX];
///If the number X is divisible by someone in the set
bool seen[MAX];
int main(){
    ///First and foremost, we are reading the set
    int N;///Number of elements in the set
    std::cin>>N;
    for(int i=0;i!=N;++i){
        int x;
        std::cin>>x;
        ///If we didn't add x yet
        if(!already_computed[x]){
            ///Mark that you checked x
            already_computed[x]=true;
            ///Now I'm going to iterate EVERY single number upto 10^6
            ///I'm just checking the numbers that are divisible by X
            ///Please notice I'm checking 10^6/X numbers.
            int b=x;
            while(b<MAX){
                seen[b]=1;
                b+=x;
            }
        }
    }
    ///Now I'm reading the array
    int M;
    std::cin>>M;
    int answer=0;
    for(int i=0;i!=M;++i){
        int x;
        std::cin>>x;
        ///Notice that we already calculated our answer above :)
        answer+=seen[x];
     }
     std::cout<<answer<<"\n";
     return 0;
}

```

Here's the example the author gave us in the code's input format:

```
3
3 5 7
6
3 5 7 15 21 143

```

Ok, cool. At first glance this may seem like an optimized O(N^2), but it's actually O(N log N).

Proof: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...\frac{1}{N}\approx log(N)$

Now multiplying the above equation by N:

$\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+...\frac{N}{N}\approx N\cdot log(N)$

And the below fraction is EXACTLY the complexity of what we are doing in the loop where we insert the numbers contained in the set.

If you are interested in this equation please check the Harmonic Series https://en.wikipedia.org/wiki/Harmonic\_series\_(mathematics)

In my simulations the code above runs in around 30ms even in the worst-case scenarios, so I would say it's pretty efficient to solve the problem mentioned above.
> 0 votes

# Answer
Put all the primes in a sieve, ignoring duplicates. O(n), giving about n / ln n primes.

Put all the numbers in a sieve, counting multiplicity. O(n).

Take each prime in turn, count all multiples and how often they are present, then remove the multiples. The time is n / p, summed over the primes from 1 to n. I think that is O(n) as well.
> 0 votes

# Answer
I think this process might give you the results Step1. know the no of elements Step2. Load the first prime number and check for divisibility. Step3. If the number in the array is divisible replace it with the prime you are dividing else Skip it. Step4. Load the next prime & repeat the process up to last prime in the set. Step5. Output={no of elements that are grater than largest prime number in the set}. I think the program goes like this

`#include <stdio.h>#include < math.h>
Int main()
{
Int x[100],y[20],z[100],I,j;
Scanf/give x&y;
For (i=1;i<=100;i++){
z[i]=x[i];
}
For (j=1;j<=20,j++)
{
For(i=1;i<=100;i++)
{
z[i]=x[i]%y[j];
If(z[i]==0)
{
z[i]=y[j];
}
else
{
z[i]=x[i];
}
}
}
j=0;
for (i=1;i<=100;i++)
{
If(z[i]>y[20])
{
j++;
}
}
Printf j;
return 0;
}`

Ps:I skipped some syntax & I forgotten some syntax.
> -1 votes

---
Tags: number-theory, primes
---


title: Seating arrangement problem

text:
# Question
Title: Seating arrangement problem
$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$

Each professor has people they like to sit next to and people they do not want to sit next to. Given a $n\times n$ (non-symmetrical) matrix $M$ where $M\_{ij}$ gives the score assigned by professor $i$ if s/he is made to sit next to professor $j$ and $M\_{ii}=0$, the goal is to output a symmetrical indicator matrix $I$ where $I\_{ij} = 1$ if professor $i$ is sitting next to professor $j$ such that $\sum M.\*I$ is maximized (I used Matlab notation here to denote elementwise multiplication of two matrices). How can we find this optimal arrangement? Lets assume we are dealing with even $n$.

From my side I spent some time calculating the total # of possible arrangements for given $n$ and arrived at this formula: $\frac{C^n\_{n/2}}{2}(\frac{(n/2)!}{k})^2$ where $k = 1$ if $n = 2$ and $k = 2$ otherwise.

I wrote the following program to calculate the # of different arrangements for given value of $n$ (assume even $n$) according to above formula.

```
public static void main(String[] args) {
        for(int i = 2; i <= 10; i += 2)
        {
            System.out.printf("%d\t%s\n", i, foo(i).toString());
        }
    }

    static BigInteger foo(int n)
    {
        BigInteger t1 = binomial(n, n/2).divide(BigInteger.valueOf(2));
        BigInteger t2 = factorial(n / 2);
        BigInteger t3 = n >= 4 ? BigInteger.valueOf(4) : BigInteger.ONE;
        return t1.multiply(t2).multiply(t2).divide(t3);
    }

    // http://stackoverflow.com/a/2929897/147530
    static BigInteger binomial(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N-k))
                    .divide(BigInteger.valueOf(k + 1));
        }
        return ret;
    }

    static BigInteger factorial(int n) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 2; k <= n; k++) {
            ret = ret.multiply(BigInteger.valueOf(k));
        }
        return ret;
    }

```

Output:

```
2   1
4   3
6   90
8   5040
10  453600

```

# Answer
> 7 votes
Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(.

**NP-Hardness**

Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or above some $k$?

This problem is NP-Complete.

First, clearly this decision problem is in NP, as if one can provide you with such an assignment then you can compute the total score and verify that their solution works.

Next, note that this problem is essentially equivalent to finding two distinct highest-cost paths that go through the same amount of nodes, and together go through every node. Using this idea, we will solve the hamiltonian path problem.

Given two hamiltonian path instances $G\_1=(V\_1, E\_1)$ $G\_2=(V\_2, E\_2)$ of the same size $n$, consider the combined graph $G=(V\_1\cup V\_2, E\_1 \cup E\_2)$, and then create an instance of our seating arrangement problem where every edge is a $1$ if it occurs in our combined graph, and a $0$ otherwise. Because these graphs are undirected, the preferences will be the same in both directions.

The question "is there some way to assign seating positions to professors such that the total score obtained is greater than or equal to $\vert V\_1 \vert + \vert V\_2 \vert$" is NP-Complete, as it is only possible to do this if a hamiltonian path exists in both graphs.

**Approximation algorithm ideas**

NP-Hardness just guarantees that a problem can't always be solved exactly unless $P=NP$, however, it doesn't tell us anything about how difficult it is to approximate. Here is one idea I had, it's incomplete, but is at least something to get you started.

For simplicity, I will now consider the problem where there is a single circle of chairs, and we are trying to place professors in the same way you require. We will also restrict all preferences to be greater than or equal to 0. This can most likely be extended to your problem but I haven't got around to that yet, so I will update this problem once that is accomplished, or you can do this yourself.

With this "roundtable" problem, it turns out there is an algorithm I found that is guaranteed to find a solution that is no less than 8 times the optimal solution.

This algorithm does the following:

1. Place each person randomly around the table.
2. Consider a pair of people (any will do), and see if swapping them will increase the total score. If so, swap them.
3. Repeat until no swap will increase your total score.

This is guaranteed to halt in polynomial time because each swap strictly increases the total score (I think? Still a little fuzzy about this part but I'm fairly sure that is true and will formalize it in a bit).

How good does this algorithm do? Well, call $Opt$ the optimal ordering of professors, and $Val$ the ordering of professors that this algorithm gives when it is done.

Now, consider any set of edges $(a, x)$, $(x, b)$, $(c, y)$, $(y, d)$ in your graph, where $a, x, b, c, y, d$ are professors. We will denote these edges $(a,x,b)$ and $(c, y, d)$ since by definition given any arrangement of professors they are next to each other.

We know that, if $y$ and $x$ could be swapped our algorithm would have done so. Call $\mid (a, x, b)\mid$ the score of edge $(a, x)$ plus the score of edge $(x, b)$. Then, if $(a, y, b)$ and $(c, x, d)$ are in val, we know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)|$$

Because either our algorithm swapped $x$ with $y$, or there was equal score regardless of the swap, in which case we have

$$|(a, y, b)| + |(c, x, d)| = |(a, x, b)| + |(c, y, d)|$$

Note that we technically also know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)| \geq |(c, y)|$$

Which is true because $|(a, x, b)| + |(c, y, d)|$ contains $|(c, y)|$ in it. Now we can look at the terms on both ends, and this gives us

$$|(a, y, b)| + |(c, x, d)| \geq |(c, y)|$$

Which holds for all edges $(c, y)$. Note that given any $(c, y)$, there is only one such pair of $(a, y, b)$ and $(c, x, d)$, because the positions $c$ and $y$ are fixed.

We know that the value of $Opt$ is equal to the sum of all it's edges $(v\_1, v\_2)$, $(v\_2, v\_3)$, ..., $(v\_{n-1}, v\_n)$, $v\_n, v\_1)$ (where $v\_i$ is some professor), so for each of these, we get a single inequality. Consider the edge $(a, y)$. $|(a, y)|$ will only appear in an inequality if $a$, $y$, or the professor before $a$ is contained in the edge in Opt. Thus, worst case $(a, y)$ is counted 8 times, because each variable can be in at most two edges, by definition.

If we sum all of the edges on both sides, we get

$$8\*Val\geq Opt$$

Thus

$$(8 \geq \frac{Opt}{Val})$$

which is a factor 8 approximation, as desired.

# Answer
> 0 votes
Super late to this party, but Phylliida is correct. This is an NP-hard problem so there is no "efficient" solution, and the proposal is known as "simulated annealing" which is the best you are going to get.

Look up wedding seating for a bunch of articles on why it is NP complete.

-- Henry

# Answer
> 0 votes
If the table is round, then this problem is a variant of the famous Travelling Salesman Problem and any of the many solutions in published literature can be consulted for solving it.

---
Tags: algorithms, counting, assignment-problem
---


# Question
Title: No parameterised reduction for a problem indicates FPT or not?
I am currently working on **parameterized complexity**, especially on the hard proofs. There is a problem that I am currently working on, denoted by $P$ and a parameter $x$, I discovered that there is no parameterized reduction for $P$ w.r.t the parameter $x$ from any *W*-class. I have tried to give a reduction from a *W*\[2\]-hard, Dominating set problem parameterized by the solution size but got to know that due to the problem definition of $P$ and the structure of the parameter $x$, it is not possible. In fact, the reduction from any *W*-class is not likely to exist. My question is: What does this indicate? Does it mean the problem is *fixed-parameter tractable* (FPT) or something else?

# Answer
> 1 votes
Proving that there is no such reduction would only establish that the problem is not $W\[2\]$-hard. But that just means that the problem is not complicated in one particular fashion, it doesn't mean that the problem is easy. There are problems that are not $W\[1\]$-hard but are far, far from being FPT.

However, it would really surprise me if a somewhat natural problem is neither FPT nor $W\[1\]$-hard.

So given what you know about your problem, I'd expect the problem to be FPT; and you probably should try and prove that next.

---
Tags: np-hard, parameterized-complexity
---


# Question
Title: Is a specialized hardware instruction always faster than a software implementation, and if so, is there a general reason?
I started wondering this after reading about the x86-SSE instruction `rsqrtss` being faster (and more accurate) than the Fast inverse square root. I have also read about other specialized hardware instructions that replaced staple software algorithms for better performance. Can a specialized hardware instruction generally be designed to be more efficient than the most optimized software algorithm? I'm entirely ignorant about how hardware or compilers work, so I'm hoping for a very "for dummies" answer; right now I'm imagining the hardware has to do *some* algorithm, but custom circuit magic saves time compared to an equivalent software code compiled to a sequence of less specialized hardware instructions.

# Answer
It is easy to show that the answer is definitely yes (specialized hardware can beat software).

Because a software algorithm runs on a general-purpose CPU, which is a piece of hardware. So any software algorithm is at the same time a hardware one. And it can be beaten as soon as optimizations/shortcuts can be found in the implementation, which are not possible in software.

As a simple example: a floating-point multiply can be split in the product of the mantissas and the addition of the exponents; these operations have to be sequential in software, but can be (and are) performed in parallel in hardware.
> 2 votes

# Answer
The Motorola 68,000 processors used to come with a co-processor for floating-point arithmetic, but also for things like logarithm, sine, cosine etc.

On the 68040 processor, the co-processor was integrated into the CPU, with the complex functions removed. The reason given was that an implementation using standard floating-point arithmetic was faster (and cheaper, obviously). It's generally very much a matter of cost.

And there is the question whether the hardware can handle parallelism well. Like two different implementations of a square root, one might be slower for one square root, but might perform multiple instructions in parallel for two or four square roots, or be able to use 512 bit vector instructions for 16 ops in parallel. The cost for 16 hardware square roots would be very high, software would be for free.
> 0 votes

---
Tags: algorithms, performance, instruction-set
---


# Question
Title: Memory allocation algorithm over a growing storage
I am going to story data in a growable persistent storage. I need to implement allocation/deallocation (like malloc/free and possibly realloc but in Rust) of continuous regions of memory on this storage.

Allocation should never fail, but the storage grow if out of allocated storage.

Priorities:

* Should do alloc/dealloc quick (i.e. desirably logarithm time of data size). That is the most important priority.
* Prefer not to grow the persistent storage if possible (because the persistent storage price is proportional to its size).

Please describe a data structure holding allocated and free regions of memory an algorithm matching the requirements.

I am writing this in Rust. If this helps, I write/read persistent storage by one word, so reading/writing are relatively slow operations.

As a bonus, if not too hard to implement, I would like also abillity of splitting long regions of allocated storage into blocks (as in fragmented filesystems).

# Answer
There is this Rust allocator described as "blazingly fast".

It remains to rewrite it with I/O functions instead of direct memory access.
> 0 votes

---
Tags: algorithms, data-structures, memory-allocation, storage
---


# Question
Title: What is the Kripke semantic for a linear temporal logic?
I've read that in general for a modal formula P, a world w and a Kripke frame ⟨W,R⟩

w⊨□P if and only if for every u∈W, if wRu then u⊢P

In case of LTL, being a modal logic, I assumed that the worlds are different moments in time and the relation R is the chain of "arrows" between those moments. However, in this case the semantic of □ in LTL would not correspond to the definition above.

What did I misunderstood?

# Answer
> 0 votes
In LTL, you don't have $\diamond$ and $\Box$, but you have $X$ and $U$, meaning *next* and *until*, respectively.

In LTL, every world has a unique successor.

Next is defined as $w \models X \phi$ if $w' \models \phi$, where $w'$ is the successor of $w$.

Until is defined as follows: $w \models \phi U \psi$ if there exists $w''$ such that $w'' \models \psi$ and for every $w'$ between $w$ and $w''$, we have that $w' \models \phi$.

Now, from these modalities, we can construct other modalities, such as *globally*, $G \phi$, and *finally*, $F \phi$. It is common to denote

* $X \phi$ as $\bigcirc \phi$
* $F \phi$ as $\diamond \phi$
* $G \phi$ as $\Box \phi$.

# Answer
> 1 votes
**tl;dr** The accessibility relation needs to be the reflexive transitive closure of what you had in mind.

Details: Let $P$ be a set of atomic proposition. Write $\Sigma$ for $P$'s powerset. Write $T$ for $\Sigma^{\mathbb{N}}$ (infinite traces).

A Kripke frame $\langle W, R\rangle$ where the meaning of formulas agrees with that of the fragment of LTL using just $P$, boolean connectives, $\square$ and $\diamond$ would consist of $W = T\times\mathbb{N}$ (ie infinite traces with an index) and $R = \\{~((\sigma,i),(\sigma,k))~|~\sigma\in T\wedge i\leq k\in\mathbb{N}~\\}$.

---
Tags: logic, linear-temporal-logic, temporal-logic, modal-logic
---


title: Why use the term "beta equality"?

text:
# Question
Title: Why use the term "beta equality"?
In lambda calculus (I will use untyped) if a term containing a redex is beta-reduced to another term, then for some reason they are considered "beta-equal". But the lambda calculus only works one way! Assume that 3 conditions are met:

1. The original term is finite (for simplicity: it consists of a finite number of characters in de Bruijn notation);
2. The original term contains at least 1 redex, the number of redexes is unlimited (but finite, which, however, follows from condition 1);
3. Exactly 1 reduction step can be performed on any redex.

Thus, we get a one-tier tree, where the root is the original term, and the vertices are the terms obtained after the reduction steps over each of the redexes. If I understand correctly, the root term is "beta-equal" to each of the vertex terms.

However, if you try to do the same in the opposite direction, then you should ask the question: for a given (final) term, which ones can be "original"? In other words, which of the (desired) terms can be beta-reduced to a given term?

In this case, obviously, the number of such terms is infinite, since you can take absolutely any term and apply it to a function that erases one of its arguments, while leaving the other as is. But the point is not even that the number of these terms is infinite, but rather that it's *pointless* to be engaged in finding their complete list; beta reduction is a *computational step*, not "equality".

In general, it seems to me that the concept of "equality" is rather vague and inapplicable in purely theoretical mathematics and computer science. For example, is 1 + 2 *equals* 3? In the "algebraic" context - yes, in the "computational" - no, 3 can be obtained both by adding 1 and 2, and, for example, by subtracting 0.141592653589... from pi - options an infinite number, and more than countable. However, even in an "algebraic" context, the relation of equality is too vague and simplistic in most cases.

Moreover, in the lambda calculus, generally speaking, "relationships" like beta reduction belong purely to the metatheory of the lambda calculus, in other words, "inside" the lambda calculus we just reduce, "outside" we think about reduction and talk about the "reduction relation". But there is no "equality" here at all. Why then use this term at all?

Thanks in advance.

# Answer
> 1 votes
It seems you are mixing up beta *reducibility* and beta *equality*.

Beta contraction (here: from $P\_1$ to $P\_2$) is a single redex collapsing step:

```
P1
  >
   P2

```

Beta reducibility (here: from $P\_1$ to $P\_5$) is the existence of a series where each step is a beta contraction (collapsing of a redex) or an alpha conversion (renaming of bound variables):

```
P1
  >
   P2 ≡ P3
          >
           P4
             >
              P5

```

Beta equality (here: between $P\_1$ and $P\_7$) is the existence of a series where each step is a beta contraction forwards, a beta contraction backwards, or an alpha conversion; i.o.w., two terms are beta equal iff there exists a term (here: $P\_5$) that both ends of the equality be reduced to:

```
P1
  >
   P2 ≡ P3          P7
          >        <
           P4    P6
             >  <
              P5

```

So beta equality is by definition *not* one-directional.

Beta reducibility implies beta equality. It is a special case where the conversion goes strictly in one direction, and the common term that both can be reduced to is the term right of the equivalence sign itself. It is customary to only speak of equivalence even when reducibility holds since that is usually of less interest; perhaps that's what's causing your confusion.

---
Tags: lambda-calculus
---


# Question
Title: How is the memory address structured when the number of blocks per cache set is not a power of 2?
When it comes to defining the memory address structure given the RAM size, cache size, and other parameters such as the cache block size..., we can have the following generalization: $$Address = TAG|Index|offset$$ We then have: $size(offset) = log\_2(word \ count \ per \ block)$

For the index, we will have: $$size(index) = log\_2(number \ of \ sets \ in \ cache)$$ which gets reduced to the following: $$size(index) = log\_2(\frac{cache \ size}{block \ size \ \times \ degree \ of \ associativity})$$

And finally, for the tag, we find: $$size(TAG) = log\_2(\frac{RAM \ size \times degree \ of \ associativity}{cache \ size})$$

My question is related to the case where the degree of associativity is not a power 2, there are many CPUs that have a non power of 2 degree of associativity such as the Intel i7-4700HQ.

My question is related to how the target set is identified in the cache given a certain word address. What complexities are aligning in this case, and how they are handled?

# Answer
6-time associativity means one cache line can be stored in six different locations. So the hardware identifies six locations where the data *might* be stored and checks all six.

The description assumes associativity is a power of two, there is no need for that. Just assume you had six caches with no associativity and tried all six in parallel. The only change you need: You only have a cache miss if all six caches miss. And you need LRU information per line so you know which cache to use when there is a miss.

In each non-associative cache, the hardware needs to identify the cache line for an address very, very fast. With a power of two size that is very easy.

In theory, if you had a power-of-2 design and you thought about either doubling the size or say increasing the size by 50%: Take the highest 3 bits of the address that you use to calculate the cache line index and take two more bits. That’s 32 values that you currently map to 8 by dropping the highest two bits. You can map them to 16 values by dropping one bit. Or you can map them to 11 values (by subtracting 11 if \>= 11 and subtracting 22 if \>= 22). So the number of cache lines increases by 3/8ths. I think that would work, but nobody does it. Because you get the same effect with associativity (change 4-way to 5-way to increase cache size by 5) much easier, and you want high associativity anyway.
> 1 votes

---
Tags: computer-architecture, memory-management, cpu-cache, memory-hardware
---


# Question
Title: find maximum in arbitrary expression tree
Originally posted on SO.

I have a very simple language that gets compiled to an Expression tree, and then evaluated. Users can define mathematical operations, use variables and control flow. Moreover, from the script it's also possible to read an external input, which is fixed for a given evaluation (i.e. it outputs the same value if called repeatedly). For example this is a valid script:

```
if readInput() < 10 then
    x = 2 * readInput()
else
    x = 0
end

```

My problem: I need to compute the maximum and minimum value of `x`, for a given input domain, e.g. `[0, 1000]`.

Solutions I have thought of:

* assign to `readInput()` the boundaries of the domain and evaluate the values of `x`. It works in many cases but fails in many others, for example in the one above it evaluates to `x = 0` in both `0` and `1000`
* compute the max/min numerically, which would work in many cases but is compute intensive, and doesn't guarantee to reach the maximum, especially when there are discontinuities
* somehow convert the tree and use a symbolic math library to compute the boundaries

Are there any other alternatives that I'm missing?

# Answer
The general solution is to use symbolic execution.

Let me start by explaining how to solve this if you have straight-line code, with no conditional statements (no if's). First, for each program variable `x` (or intermediate value/expression), you introduce a mathematical variable $x$. Second, for each line of code, you form a constraint that expresses how the value of the variable assigned by that line of code relates to the other variables in that line. For each `readInput()`, you have no constraints on the mathematical variable that corresponds to it, or set an upper and lower bound based on the range of values it could receive. Finally, you conjoin all the constraints, and ask a solver to find the maximum value of the final result, subject to all of the constraints.

For instance, consider the following straight-line code:

```
a = readInput()
b = 2*a + 3
c = readInput()
d = b/c + c/b

```

You introduce mathematical variables $a,b,c,d$, and then convert the above to the constraints

$$\begin{align\*} 0 &\le a \le 1000\\ b &= 2a + 3\\ 0 &\le c \le 1000\\ d &= b/c + c/b \end{align\*}$$

Finally, you construct a boolean formula via the conjunction of these constraints,

$$(0 \le a \le 1000) \land (b = 2a+3) \land (0 \le c \le 1000) \land (d = b/c + c/b),$$

and you ask a solver to compute the maximum possible value of $d$, subject to this boolean formula. For instance, you could use the Z3 solver to compute this maximum.

That only works for straight-line code. What about an expression tree, such as you list?

You can do something similar once you introduce conditional statements, but now you need to introduce the notion of path constraints.

Pick any one path through the tree. This corresponds to a sequence of straight-line code, corresponding to the statements that are executed along this path. We can create a boolean formula $\varphi$ from this straight-line code, as above. Also, we can create a boolean formula $\psi$ from the conjunction of the conditional expressions that are evaluated along this path through the tree. For instance, if at the top-level we branch on `a < 17`, and this branch is taken, then we add $a\<17$ to $\psi$. If at the next level we branch on `a*b > 5`, and this branch is not taken, then we add $ab \le 5$ to $\psi$. We take the conjunction of all of these, e.g., $(a\<17) \land (ab \le 5)$, to be $\psi$. Here $\psi$ is known as the path constraint. It encodes what conditions must be true for execution to follow that path.

We then maximize the final value along this execution path, subject to the boolean constraint $\varphi \land \psi$. This can again be solved with a solver.

Finally, we repeat this, once per path (i.e., once per leaf of the tree), and take the largest value that is possible along any of the paths.
> 1 votes

---
Tags: optimization, trees, syntax-trees, symbolic-execution
---


# Question
Title: Book-length overview of all of computer science
I was wondering what books are there that give you nice overview of the computer science field.

I'm not interested so much on the details of the trees, but on the forest. I was thinking it would have to be something like a popular introductory book, preferably up to date.

I hope this question is within the forum's scope.

# Answer
> 1 votes
*(Disclaimer: I'm not a computer scientist and have not read most of these books. I wish more people would address this interesting question.)*

CS courses usually provide an introduction to the field which may be supported by corresponding textbooks, for which various options exist out there. Many of them have titles in the lines of *"Introduction to Computer Science"*, *"Fundamentals of Computing"*, etc.

For example, I enjoyed reading *CS for All: An Introduction to Computer Science Using Python* last year, although I haven't worked through its introduction to objects because I had a bit of trouble with the Python graphics library of their choice (the issue possibly had an easy solution but I did not put much effort into it), so I just glanced its contents since objects were already a familiar topic.

I was satisfied with its treatment of Python, functions and recursion, as well as other subjects I wanted to delve into a bit deeper, so it was a generally enjoyable read.

I've found it relatively short and now I'm looking for supplementary texts. So, other titles whose TOC (Table of Contents) caught my attention for various reasons, in no particular order (but still rather Python-centric), were:

* *Introduction to Computation and Programming Using Python - John V. Guttag*
* *Computer Science Illuminated - Nell Dale and John Lewis*
* *Python Programming: An Introduction to Computer Science - John Zelle*
* *Explorations in Computing: An Introduction to Computer Science and Python Programming - John S. Conery*

And there are certainly many others available and more or less up-to-date.

BTW, regarding being up-to-date, this is probably bad advice (and possibly worth questioning separately), but I once misread the introduction from *Simply Scheme* (which is also an introductory CS book, and is known as a prequel to *Structure and Interpretation of Computer Programs*) as stating that CS books have a ten-year lifespan or so in terms of how well they address the ever-changing trends from the field (certainly a terrible misread, and people would throw *SICP* at me as a counterexample - BTW, there is a JavaScript edition of SICP now). But it stuck with me, and now I personally tend to favor more recent introductory CS books such as the ones I mentioned.

So that is just something to consider. You are probably okay reading any book or edition that is not terribly old or adopts an unfavorable language to teach its concepts. Python is a popular language choice today, Java had its heyday some time ago, languages such as Scheme are considered good for teaching CS concepts, and you certainly can find more or less up-to-date choices for C and other relatively popular languages you might be familiar with, or even language-agnostic options (such as the *Computer Science Illuminated* one that I mentioned earlier, with which you are free to adopt any language you prefer).

# Answer
> 0 votes
For all of CS, I'm not so sure. For instance, I'm imagining that you don't want to do programming. So you might have luck looking into CS's different parts, trying books not so much aimed at practitioners as at those who are just interested. Along that line, perhaps for just the Theory part, *The Golden Ticket: P, NP and the Search for the Impossible* by Lance Fortnow.

---
Tags: books
---


# Question
Title: Is it true to say that machine languages have some degree of abstraction?
I think anyone would agree that assembly languages ("threshold languages") have some very little abstraction but is it true to say that also machine languages have some degree of abstraction?

# Answer
Depends on what you consider the most non-abstracted.

Memory addresses get translated from the virtual address space to physical RAM address space through the page table.

The instruction set can address a number of registers, however in many CPUs there are more register locations available in the register file than can be addressed by the machine code. In the back end there is a register renaming mechanism to map the instruction register to the actual bit of SRAM in the register file.

Out of Order CPUs don't execute the instructions in order (it's kinda in the name), instead it only pretends to do so and instead shuffles around actual execution in the functional units as the results of previous instructions become available to execute upon.
> -1 votes

---
Tags: computation-models, abstract-data-types
---


title: How to show a language is in NP?

text:
# Question
Title: How to show a language is in NP?
(I reorganized my question.) We have a function $f$ mapping the integers $\\{1, . . . , 2^k\\}$ ONTO the integers $\\{1, . . . , 2^k \\}$ such that when these integers are represented in binary, and $f$ is polynomial time computable but the inverse function $f^{-1}$ is not polynomial time computable. Define a language $L =\\{(x,y) | f^{-1}(x)\<y\\}$. Show that this language $L$ is in NP.

$f$ is surjective, so $f^{-1}$ is adjective. Since $f$ is polynomial time computable, so we can find $f(f^{-1}(x))=x$ in polynomial time, but $f^{-1}(x)$ is not polynomial time computable, how can we compare $f^{-1}(x)\<y$?

# Answer
You have already figured out that $f^{-1}(x)$ can be used as a potential NP certificate. You are just missing the crucial part in the definition of NP.

You don't have to compute the certificate, you can non-deterministically guess this certificate and verify if it is a good certificate in polynomial time. How hard or easy it is to produce such a certificate doesn't matter in NP, all that matters is its existence. Since $f$ is polynomial time computable, for any $z$, you can efficiently verify if $z = f^{-1}(x)$.
> 0 votes

# Answer
The value $f(x)$ is a polynomial length certificate for the language, since it has the same size as $x$, and can be checked in polynomial time by verifying that $f^{-1}(f(x)) = x$ and that $f(x) \< y$.
> 0 votes

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


# Question
Title: Is there an algorithm to test for an acyclic undirected graph, using edge data, not node data (e.g. adjacency matrix)
Given an adjacency matrix or other data based on the nodes, there are many algorithms for determining whether the graph is acyclic (e.g. row reduction or leaf trimming).

If I have only a set of edges (e.g. ${(a,b), (b,c), (d,b)}$), I could obviously convert that into an adjacency matrix and proceed from there.

I'm wondering if there is a good algorithm that works directly with the edges.

# Answer
You could use a disjoint set (union-find) data structure and iterate through the edges one by one. For each edge $(u, v)$, if the two vertices already belong to the same subset, then the graph is not acyclic. Otherwise, you merge the subset containing $u$ with the subset containing $v$. If all edges are added successfully, the graph is acyclic.

This runs in $O(E\alpha(V))$, where $V$ is the number of vertices, $E$ is the number of edges and $\alpha$ is the inverse Ackermann function.

In principle, however, I don't think that this is any faster than iterating through the edges to build an adjacency list and then use that for determining if the graph is acyclic.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Given required total area and capacity, choose an amount for each of three given modules
Suppose you have three modules $m\_1,m\_2$ and $m\_3$, each with a capacity of $c\_i$ and area $a\_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each module so that the sum of areas is exactly $A$ and the sum of the capacities is exactly $C$? All variables including the amount of each module are positive integers.

I tried to formulate this as an optimization problem but I can't find a function to maximize or minimize. I also tried to think of it as a kind of Knapsack problem, but my programmed solution that adds and removes modules randomly for backtracking is not working.
Any suggestions on how I may proceed?

# Answer
> 1 votes
#### An approach that uses integer linear programming (ILP)

The given condition can be consider the requirement $AX+s=b$ of an ILP in standard form. However, as noted in the question, there is no function to maximize. Well, that is not big obstacle at all. We can specify any function to maximize. For example, we can maximize the amount of $m\_1$. Or maximize the amount of $m\_2$.

There are various algorithms that solve ILP. However, the problem of integer linear programming is NP-hard. It is not clear which algorithm might be efficient for the current problem.

#### Another approach with a linear algorithm

Let us use math a bit. What we need is the method of elimination of variables and the extended Euclidean algorithm that solves linear Diophantine equation of two variables. Throughout the explanation below, I will skip various easier cases so that we can focus on the main idea. All variables will be integers.

---

Let the amount of $m\_i$ be $x\_i\in\Bbb N\_{\>0}$. The requirements are $$ a\_1x\_1+a\_2x\_2+a\_3x\_3=A\\ c\_1x\_1+c\_2x\_2+c\_3x\_3=C$$

Consider $x\_1$ a constant, we can solve $x\_2, x\_3$. $$rx\_3=p\_2x\_1-q\_2\\ rx\_2=p\_3x\_1-q\_3$$ where $p\_3=c\_1a\_3-c\_3a\_1$, $\ q\_3=Ca\_3-Ac\_3$, $\ p\_2=-(c\_1a\_2-c\_2a\_1)$, $\ q\_2=-(Ca\_2-Ac\_2)$, $\ r=a\_2c\_3-c\_2a\_3$.

I will skip the easy case when $r=0$. Assume $r\not=0$.

The original problem is equivalent to finding a positive integer $x\_1$ such that both $p\_2x\_1-q\_2$ and $p\_3x\_1-q\_3$ are positive multiples of $r$. Thanks to the elimination of variables $x\_2$ and $x\_3$, we will deal with a single integral variable $x\_1$ only.

**Fact**. Let $a, b, n$ are integers, $a\not=0$, $b\not=0$. We can use the extended Euclidean algorithm or here to find $d=\gcd(a,b)$ as well as an integral solution $(x,y)=(x\_0,y\_0)$ of the equation $$ax+by=d.$$

* If $n$ is a multiple of $d$, all integral solutions to $ax+by=n$ are given by $$(x\_0\frac nd+\frac bdk, y\_0\frac nd-\frac adk),$$ where $k\in\Bbb Z$.
* If $n$ is not a multiple of $d$, there is no integral solution to $ax+by=n$.

Consider the condition that $p\_2x\_1-q\_2$ is a positive multiple of $r$. I will skip the easy case when $p\_2=0$. This condition asks us to solve the Diophantine equation $p\_2x\_1+ry\_1=q\_2$ with positive $x\_1$ and $y\_1$. I will skip the easy case when $q\_2$ is not a multiple of $\gcd(p\_2, r)$. So all integral solution to $p\_2x\_1+ry\_1=q\_2$ are $(x\_1, y\_1)=(s\_0+s\_1k\_1, s\_2-s\_3k\_1)$, where $k\_1\in\Bbb Z$ for some constant $s\_0, s\_1, s\_2, s\_3\in\Bbb Z$ that can be computed according to the fact above. The condition that $x\_1$ and $y\_1$ are positive will mean $k\_1$ must be in some interval (possible empty or infinite). In summary, $x\_1=s\_0+s\_1k\_1$ for some integer constant $s\_0, s\_1$ where integer $k\_1$ is in some known interval.

Similarly, with some easier cases skipped, the condition that $p\_3x\_1-q\_3$ is a positive multiple of $r$ will mean $x\_1=t\_0+t\_1k\_2$ for some integer constant $t\_0, t\_1$ where integer $k\_2$ is in some known interval.

Combining both conditions, we find the problem is reduced to finding integers $k\_1, k\_2$ in some know intervals respectively such that $s\_0+s\_1k\_1=t\_0+t\_1k\_2$. The last equation is again a linear equation of two variables $(k\_1, k\_2)$, which can be solved by the fact above.

---

If we implement the approach above properly, the algorithm will have $O(\log(\max(c\_1, c\_2, c\_3, a\_1, a\_2, a\_3, A, C)))$ time-complexity and $O(1)$ space-complexity.

---
Tags: algorithms, optimization, integer-programming, diophantine-equation
---


# Question
Title: Trying to understand the time complexity of IDDFS
I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.

For BFS it is intuitive to me that we take the exponent of each level of depth since we are expanding all nodes.

For IDDFS, the equation to my understanding is looking at the deepest level, taking the breadth of that (d)b since it was only looked at once, then the level prior to that (d-1) needs to have its nodes expanded twice, hence it is b^2.

Then after the ... we are multiplying breadth by 3, to the power of depth-2? (i.e 3b^d-2).

Is someone able to explain this? Also any recommendations for sources that give a clear breakdown of what is happening? Just seeing formulas restated isn't helping on my learning journey, would be great to find a source that talks it through and/or gives a visual breakdown.

# Answer
> 0 votes
You can read the details of the analysis of the algorithm here.

But the idea is that, the target node will be found at depth $d$, with respect to a specified source/root node. Then this node, along with all other nodes with the same depth, will be visited once, and there are at most $b^d$ of them. That accounts for the last term in your summation. Now moving backwards, the parents of these nodes will be visited twice - once when the algorithm sets the depth to $d-1$, and another when the depth is set to $d$. The number of such nodes is at most $b^{(d-1)}$, which gives the $2b^{(d-1)}$ term. You can continue this until you get to the nodes at depth 1, which will be visited $d$ times and there are at most $b$ of them.

---
Tags: algorithms, data-structures, big-o-notation
---


title: Why NP is not certain subset in P/poly?

text:
# Question
Title: Why NP is not certain subset in P/poly?
Complexity class P/poly includes languages, which cannot be calculated by means of classic Turing machine, including unary halting problem
However, class NP is relatively simple, can be calculated via Turing machine and is placed on lowest level in polynomial hierarhy

So every NP-complete problem, which can be represented as NP-language recognition, can be easily turned into P/poly class:
Step 1: Make Turing maching which recognises apropriate NP-complete language. If language is not inside NP, perform force stuck in infinite loop
Step 2: Make unary representation of that turing machine
Step 3: Solve halting problem for this machine via boolean circuit, that lies in P/poly class
Step 4: If machine halts, original language is NP-language, that had been proved in P/poly-wide scope. So, NP lies in P/poly

Where is my misunderstooding? Thanks!

# Answer
The problem is that you have to transform the input for the original machine into a unary input for the unary machine. This cannot be done in polynomial time in the size of the original input, therefore your proposed algorithm is not a $\mathsf{P/poly}$ algorithm.
> 3 votes

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


# Question
Title: Why is this proof that CHESS is in EXPTIME correct?
I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by proving that $\texttt{CHESS}$ is in $\texttt{EXPTIME}$, but I don't understand at all the fragment highlighted in pink (the final implication).

I understand how they derived that the maximum possible number of configurations is bounded by an exponential, however I don't immediately see why that would imply that there exists an algorithm with time complexity $O(2^{p(n)})$ where $p(n)$ is a polynomial.

The algorithm I assume would be similar to a MiniMax algorithm, traversing the entire game-tree of $\texttt{CHESS}$. We can also say that if in a branch black can force the same configuration (and turn of play) to reappear, then it's an immediate draw (because white must do better than an infinite loop).

However, since in different branches the same configuration can reappear, wouldn't this be a time complexity $n^n$, worse than exponential?

Whats exactly the algorithm or catch that I'm missing?

**IMAGE TRANSCRIPT**:

Let $Q$ be the following question: Given an arbitrary position of a generalized chess game on an $n \times n$ cheessboard from our class of chess games, can White (Blacn) win from that position? We define Exptime to be the set of all decision problems with time complexity bounded above by $2^{p(n)}$ for some polynomial $p$ of the input size $n$. Since in chess there are six distinct pieces of each color, the number of configurations in $n\times n$ chess is bounded above by $13^{n^2}$, hence $Q \in$ Exptime.

# Answer
> 0 votes
If you keep track of previous computation, then the same configuration appearing multiple times would not require multiple computations.

That means that a Min-Max algorithm would require a time complexity linear in the number of configurations times the number of possible moves for a given configuration. This is indeed exponential in $n$.

---
Tags: algorithms, time-complexity, search-algorithms, board-games
---


# Question
Title: How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?
Define a graph problem as follows. Given a graph $G$ and two integers $c$ and $k$, delete $k$ nodes and all edges incident to them, such that, in the remaining graph, every connected component has at most $c$ nodes.

What can I say about the time complexity class of the above problem? I can easily prove that under the condition that $c=1$, I can reduce Vertex Cover to the problem in polynomial time, and thereby prove that the problem is NP-hard under these parameters.

My work book says that this, accompanied with a polynomial verification, is enough to prove that the problem is NP-complete, but I have a hard time accepting this since we have only observed the problem under a certain set of parameters?

# Answer
If a problem $P'$ is a special case of problem $P$, this means that $P'$ can be reduced to $P$. Therefore, if $P'$ is NP-hard, it follows that $P$ is NP-hard (because if any problem $H$ in NP can be reduced to $P'$, then it can also be reduced to $P$).

If you also have a proof that $P$ is in NP (your proof of polynomial verification; for $P$, not just for $P'$), then you have a proof that $P$ is NP-complete.
> 2 votes

# Answer
“X is NP hard” means: Any instance of any problem Y in NP can be solved by constructing and solving the right problem in X. “X is NP complete” means that in addition X is in NP.

If a subset P’ is NP complete or NP hard, then obviously P is NP hard: Just pick the same instance to solve any instance of an NP problem, not one of the added ones.

For P to be NP-complete you need to prove that P is in NP. This is never the case if P’ is not in NP.
> 1 votes

---
Tags: graphs, time-complexity, np-complete
---


title: Elemination of duplicate premise

text:
# Question
Title: Elemination of duplicate premise
Suppose that I have proof tree starting with some statement |- B in a sequent calculus, leading to two premises/leafs |- A. Is it always possible to transform such a proof tree into another proof tree, which only contains one leaf |- A only using standard rules of natural deduction?

More schematically I want to perform the following transformation:

```
  |- A     |- A                       |- A
------------------    ---->     ---------------
      |- B                            |- B

```

# Answer
> 0 votes
"All $A$ are $B$" and "All $B$ are $C$" then "All $A$ are $C$", it is called deductive reasoning.

If two premises are identical then you don't get actually the deduction, you get only the implication.

For example "All $A$ are $B$" then you get the implication "some $A$ are $B.$" "No $A$ are $B$" you get the implication "some $A$ are not $B.$"

# Answer
> 0 votes
If I understand your question, I do not think so. That is, maybe the premise $\mathscr{A}$ is used for multiple things in the proof. Consider the following proof of $\mathscr{B}=(A\rightarrow (B\rightarrow C))\rightarrow (A\wedge B \rightarrow C)$:

$$\rightarrow I\_2\cfrac{\rightarrow E\cfrac{\rightarrow E \cfrac{\wedge E \cfrac{\[ A\wedge B\]^1}{A} \quad \[A\rightarrow (B\rightarrow C\]^2}{B\rightarrow C} \quad \wedge E \cfrac{\[A\wedge B\]^1}{B}}{\rightarrow I\_1\cfrac{C}{A\wedge B \rightarrow C}}}{(A\rightarrow (B\rightarrow C))\rightarrow ((A\wedge B)\rightarrow C)}$$

As you can see in the above proof we have the formula $\mathscr{A} = A\wedge B$ which is used two times. Though both are omitted by using the rule $\rightarrow I\_1$, they really need to be used more than once (One time for deduction of $A$ and one time for deduction of $B$).

---
Tags: logic, reasoning, natural-deduction
---


# Question
Title: What does it mean for a shell to parse its command line and to identify the PATH?
After accepting the command entered by user,the shell generates a readily executable simple command line by parsing it evaluating variables(if present),performs command substitution,interprets metecharacters like * and ?(if present) and identifies the PATH.

Can anyone explain to me in simple terms the parsing part and identifying the Path part?

\*text is taken from Unix and shell programming by M.G.Venkateshurthy

# Answer
> 1 votes
This is a question about Unix and shell programming. When you run a command like `cp dir/* $destination` the shell has to do several things to simplify this command before executing it:

* Replace `dir/*` with a list of all the paths matching `dir/*` e.g. `dir/file1 dir/file2 dir/file3`
* Replace `$destination` with the value of the variable `destination` e.g. `otherdir`

There are other steps not shown here, like command substitution - for example `$(ls)` is replaced by running the command `ls` and replacing it with whatever `ls` outputs.

Finally as a last step, generally separate from the others as it does not actually edit the command, the shell has to find the actual path of the `cp` command, usually at `/bin/cp`. It does this by looking at the variable `PATH`, which holds a list of directories, then looking in each directory to find an executable called `cp`.

---
Tags: operating-systems
---


# Question
Title: Is this how endianess work relative to memory?
So I've been trying to understand endianess for the past couple of days but I'm not sure if I'm overthinking this or not and I don't have anyone I can ask to confirm things.

Here is how I look at things.. Say you have a defined value which represents the amount of pebbles there are in my city.

Decimal: `1193046`

Hex: `0x123456`

Binary: `0001 0010 0011 0100 0101 0110`

These all carry the same weight but they're represented in various different ways, they all have one thing in common and that's that the most significant number is located all the way to the left due to how positional notation works.  Which means that the most significant byte would be `0001 0010` and this has nothing to do with endianess afaik.

Now say we create an int variable and store the decimal representation in it, that means that the computer will allocate 4 bytes of space in memory.

*Unassigned allocated memory*

`0 (0000 0000) - 1 (0000 0000) - 2 (0000 0000) - 3 (0000 0000)`

What I'm about to explain next is based off of the fact that I *think* it's safe to assume that a CPU always reads left to right, no matter endianess, is that something that's safe to assume? Because endianess only dictates how the CPU decides to store the bytes from a given value, right?

This is a more visual representation of what I think is going on

```
ALLOCATE 4 Bytes
PLACE Bytes (LE/BE)

```

LE `0 (0000 0000) - 1 (0001 0010) - 2 (0011 0100) - 3 (0101 0110)`

BE `0 (0000 0000) - 1 (0101 0110) - 2 (0011 0100) - 3 (0001 0010)`

My theory is strongly based off of the fact that I think that the lowest memory address is always to the left, and that the CPU reads/writes bytes from left to right no matter it's architecture, however when it stores a value that's greater than 1 byte, it stores the most significant byte first **or** last based on it's endianess.

Am I super wrong here or do I kind of have a slight idea of what's going on?

# Answer
> 1 votes
Memory is first split into bytes. Bytes are 8 or more bits with 256 or more values. (Octets are 8-bit bytes. Bytes can be larger). Bytes can only be read or written completely.

Programming languages and computer hardware use integers larger than 8 bits. For example 64 bit integers. You need eight 8-bit bytes to store a 64 bit integer.

So to read a 64 bit integer at address x, you must read eight bytes at addresses x to x+7. And these bytes must be combined to form a 64 bit value. If the bytes are named a, b, c, d, e, f, and g, then the value is a + b*0x100 + . . . + g*0x100000000000000.

There are 8! ways a to g could be assigned to these eight memory location. One way is called bigendian, one is called littleendian, and the others have no names and are not used in practice.

# Answer
> 0 votes
The 32-bit number is split into 4 8-bit groups (bytes):

```
00000000 00010010 00110100 01010110
hex: 00     12       34       56

```

In little-endian order 56 is stored at the lowest address, then 34, then 12, then 00. In big-endian order 00 is stored at the lowest address, then 12, then 34, then 56. So when you read them with the lowest address at the left, in little-endian you see 56 34 12 00 and in big-endian you see 00 12 34 56.

CPUs don't know about left or right, just lower and higher addresses. Lower address at the left just happens to be the way us humans write memory dumps, and MSB at the left just happens to be the way us humans write numbers.

# Answer
> 0 votes
It is important to know that endianness applies to multi-byte primitive data types. These occupy 2 (short), 4 (int, float) or 8 bytes (long log, double) and are stored as a whole.

There are two obvious ways to store these bytes: by increasing (little-endian) or decreasing weights (big-endian). The qualifier refers to the weight of the first byte (by increasing addresses).

Endiannes does not apply to data types such as strings or byte buffers, and the bytes themselves are not "reversed".

---
Tags: computer-architecture, cpu, memory-access
---


# Question
Title: Are lambda calculus forms with different variable names the same?
Someone suggested to me that the halting problem could be solved by a lambda calculus "program", which reduces to $\lambda y.y$ if an input program halts and $\lambda n.n$ if it does not. Therefore it is not possible to extend this into a program that halts if it thinks it doesn't halt. (That's just background, not the question proper)

I said this is nonsense, because obviously these are the same term written differently. He says we can just look at the output and see whether the variable is called $y$ or $n$, even though a lambda calculus program can't.

I think the lambda calculus reduction rules allow any variable to be renamed at any time for no reason whatsoever, so we can't reliably say what variables will be called after reducing a lambda calculus expression.

Are $\lambda y.y$ and $\lambda n.n$ considered "the same" or equal in lambda calculus?

# Answer
You are right and your someone is wrong. Lambda terms that only differ in the names of bound variables are beta equivalent, and considered the same program. If the lambda calculus can't see the difference, this means that this implementation in that system is not a solution to the problem.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: $n$ students want to exchange books among themselves
This is a problem from my Algorithms course in uni

There are $n$ students, each have a single book. They come into a party to exchange books among themselves. Each have a list of students that have the book that they want.

Give and prove an algorithm that says if a switch of books is possible, i.e. every student got the book that they want.

\*A student can't write themself in their list

\**If student $i$ took student $j$'s book, it doesn't mean that student $j$ also took student $i$'s book

My algorithm is as follows: Go over the lists from shortest to longest **(if there are several lists of same size, start with the list that belongs to biggest number, and progress in ascending order)**: In the list $i$, take the minimal student's number which isn't marked taken, and mark it as taken. If there is none, return with false

When you're done, return with true

I didn't manage to prove it, so I don't even know if it's true. Thanks in advance

# Answer
> 1 votes
If you reformulate this problem as a graph problem with students as the vertices and directed edge from $i$ to $j$ when $i$ wants $j$'s book, then this problem translates to finding a sub-graph over all vertices which is a union of simple directed cycles.

You can probably do this by computing the SCC decomposition and then finding cycles in each connected component.

Also, here's an example with 6 students for which your algorithm doesn't work. $ 1: \\{2,3\\}, 2: \\{4,5,6\\}, 3: \\{1,5,6\\}, 4: \\{2,5,6\\}, 5: \\{2,4,6\\}, 6: \\{2,4,5\\}$. A solution would be the decomposition into cycles $(1,3)$ and $(2,4,5,6)$ but your algorithm makes the wrong choice for $1$ in the first step itself.

# Answer
> 0 votes
It seems if you have the same number of people wanting a book and having a book then you can have a swap by everyone putting their book on a pile, then everyone picking the book they want. And if you don’t have the same numbers then you can’t swap.

---
Tags: algorithms
---


title: How does the Program Counter work?

text:
# Question
Title: How does the Program Counter work?
I think it stores the address of the current instruction. And if this instruction is completed the program counter is incremented by 1, to get the next instruction. But now my question is, how do you increment the program counter by 1? It would mean you increment an address by 1, how does this work?

# Answer
> 3 votes
Assuming a 32-bit architecture (with alignment), then instructions are words; that is, every instruction is composed of 4 bytes.

That implies that the bottom two bits of the address are byte offsets within the word; that is, the address 10001111 denotes 4th byte of the word at 10001100. When we're talking about instructions, however, we'll never need to fetch individual bytes -- we want whole words.

Different textbooks handle the program counter differently, but given that whichever paradigm you're using has the program counter incremented by 1 (rather than 4), that leads me to believe that the PC stores **word** address, rather than byte address.

Then, if the program counter is at 10001111 and we increment by 1, we do in fact get 10010000. To turn this **word** address into a byte address (so we can fetch the instruction from memory), we can simply left-shift by 4.

In short, if the program counter is at 10001111 (the **word** address), then the **byte** address of the instruction we'll actually be fetching is 1000111100. To fetch the next instruction, we can just increment the program counter by 1.

# Answer
> 0 votes
The program counter indicates the memory address of the current instruction. Depending on the architecture of the CPU it may be incremented by a fixed or a variable amount in order to point to the address of the next instruction. "You" the author of the program running on the CPU do not need to increment the PC, and it may not even be accessible to you. Instead the CPU itself handles incrementing it, which could be part of the circuitry of a hardware CPU, or part of the software of a CPU implement by a virtual machine.

# Answer
> 0 votes
Instructions are not necessarily of length 1 (byte).

After an instruction has been read from memory and interpreted\*, the address held by program counter is incremented by the appropriate number of bytes (simply using an adder), ready to fetch the next instruction.

\*In case of variable length instructions, the instruction decoder determines the instruction length on the fly.

# Answer
> 0 votes
You're correct that the program counter (PC) is a register that stores the memory address of the next instruction to be executed by the processor. After the current instruction is completed, the PC is incremented to point to the next instruction in memory.

Regarding your question on how the PC is incremented by 1, it's important to understand that the size of an instruction in memory is not always fixed. Depending on the architecture and instruction set of the processor, instructions can have different sizes.

For example, in a typical x86 processor, the size of an instruction can range from 1 byte (e.g., NOP instruction) to 15 bytes (e.g., complex instructions with prefixes). In such processors, the PC is incremented by the size of the instruction that was just executed.

To do this, the processor uses a technique called "instruction decoding". This involves analyzing the bits of the instruction in memory to determine its size, and then incrementing the PC accordingly. The processor may use various techniques to optimize this process, such as pre-fetching instructions from memory or caching recently executed instructions.

So, the size of the instruction is determined during the decoding phase, and the PC is incremented by that size to point to the next instruction in memory.

# Answer
> -1 votes
The program counter stores the address of the next instruction i.e the instruction that is next to be executed. When the current instruction is executed,the program counter is incremented by 1.

# Answer
> -1 votes
Program Counter- it is a location where the instruction executed is stored at a current time, and where the next execution is set.

---
Tags: computer-architecture
---


# Question
Title: A proof of the completeness of PLTL (Propositional Linear Temporal Logic)
In what paper(s), textbook(s), and/or classnote(s) can I find a detailed proof of the completeness of a certain proof system for PLTL (Propositional Linear Temporal Logic)?

# Answer
The proof system "DUX" in *On the temporal analysis of fairness.* D Gabbay, A Pnueli, S Shelah, J Stavi. POPL 1980 is perhaps closest to what you're after. Being a conference paper, the completeness proof is rather terse but with a bit of luck you can fill in the details.
> 1 votes

---
Tags: reference-request, linear-temporal-logic
---


title: Unlimited use subset sum

text:
# Question
Title: Unlimited use subset sum
Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\\{ a\_1,...,a\_{\left| A\right|}\right\\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $k\_1,...,k\_{\left| A\right|}$ such that:

$$ \sum\_i k\_i \cdot a\_i = z$$

It is a generalization of regular subset, and seems to me as a much more complex version. Specifically, how can I reject a *no* case?

I am looking for an algorithm that can always halt, regardless of its runtime. Or a possible reduction to show one cannot exist.

Clarification: $Z$ may contain negative numbers.

# Answer
Compute $g = \gcd(z\_1,z\_2,\dots,z\_n)$, where $Z=\\{z\_1,\dots,z\_n\\}$. If $g | z$, then you can use the extended Euclidean algorithm to find such a linear combination. Otherwise, there does not exist any solution.
> 2 votes

# Answer
If the $k\_i$ are restricted to be positive integers (please clarify whether this is the case or not in your question), D.W.'s nice approach could give an invalid answer (i.e., an answer with some $k\_i$ negative). But in this case there is an efficient and quite intriguing algorithm:

A Fast and Simple Algorithm for the Money-Changing Problem (Böcker and Lipták, 2007)
> 1 votes

---
Tags: complexity-theory, turing-machines, subset-sum, recursively-enumerable
---


title: Shuffling two related sets together

text:
# Question
Title: Shuffling two related sets together
Given two sets of values $a\_1, a\_2, ... a\_n$ and $b\_1, b\_2, ... b\_n $ what would be a good way to shuffle them together while keeping $a\_i$ and $b\_i$ at least $gap$ spots apart?

For example, if we have `A B C` and `a b c`, then `b A C a B c` is a valid 2-gap shuffle, but not a valid 3-gap shuffle (because of the a's placement).

The obvious solution is to shuffle each set the same way and then append one to another. A slight variation is then also swap some element pairs ($a\_j$ and $b\_j$). These are no bueno however, because I am after an actually random shuffle across the entire combined set.

They way I have it now is - combine two sets, shuffle them, then traverse from the front and check for the constraint violation. If an item is in violation, i.e. we saw its twin less than `gap` spots back, then swap it with the first element from the tail that resolves the violation. This clearly doesn't guarantee to converge for every shuffle, so when it doesn't, reshuffle the whole thing and restart. Very crude, but works well for `gap` values that are substantially smaller than the set size.

Is there a better, non-restarting way to do the same?

# Answer
> 2 votes
If you need something that is guaranteed to be unbiased -- i.e., that will generate each possible valid outcome with equal probability -- I don't know of a way to achieve this efficiently. The simplest way to achieve it is with brute force: Generate a full solution, e.g., with the Fisher-Yates shuffle, then test whether it satisfies the constraints, and start over if it doesn't. You can gain a small speed advantage by restarting Fisher-Yates as soon as you detect a constraint violation (this is allowed since no later decision made by the algorithm can undo an existing violation).

If you aren't bothered by some potential bias, the following simple method takes $O(n^2)$ time:

1. Randomly shuffle the $a\_i$.
2. For $i$ from 1 to $n$:
    * Pick a random location in the valid ranges for $b\_i$ (there could be two, one on each side of $a\_i$'s location) and *insert* it there.

This works because inserting a new value never causes an existing feasible solution to become infeasible, because all pair distances stay the same or increase by 1. Note that this approach likely introduces bias, since values inserted early in step 2 will on average be pushed further apart than values inserted late. Inserting the $b\_i$ in random order might help.

You could improve the time complexity to $O(n\log n)$ by replacing the array with a self-balancing binary search tree, but my feeling is that that's probably overkill for a practical application. If the running time of the naïve algorithm is too high, it's probably easier just to shrink the constant in front of the $n^2$ by leaving regular "gaps" in the original array.

**NOTE:** This algorithm can still fail if the gap is $\> \lfloor n/2 \rfloor$: If $a\_1$ ends up in the middle, there will be no valid locations for $b\_1$ in the first iteration of step 2. In this case you can either rerun it, or (likely at the cost of further bias) pick some other $i$ value to work with on that loop iteration. To see that there always exists an $i$ value that will work whenever the gap is $\< n$:

1. Initially, there are two known-working $i$ values, corresponding to whichever $a\_i$s landed in the first and last positions.
2. After the first $b\_i$ is inserted, the second and second-to-last positions hold valid $i$ values.
3. In general, after $k$ insertions of $b\_i$ values, there are $2(k+1)$ known-working $i$ values, at most $k$ of which have been used already.

---
Tags: randomized-algorithms
---


# Question
Title: what are the performance differnces (space and time complexity) between count-min sketch and quotient filter?
what is the space and time complexity (lookup, insertion) of count-min sketch and quotient filter?

I could not find these complexities. I would like to make a program which find the frequencies of objects in a set in the fastest way, so the time complexity is really important for me.

I read the research article about those objects, about quotient filter from "Don’t Thrash: How to Cache your Hash on Flash", it was said there that its lookup and insert actions are faster than bloom filter which is O(k) (k is number of hash function).

I also read from "Count-Min Sketch" and "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" but could not find the big O complexity of both of these data structures.

Thank you

# Answer
> 0 votes
**Quotient Filter**

*Time complexity*

The quotient filter offers a constant time complexity of O(1) on average with most operations. However, in the worst case, all operations might take logarithmic time complexity O(log(n)), where n is the number of buckets in the filter.

*Space complexity*

The quotient filter does not store the data items but a part of the fingerprint yielding a constant space complexity of O(1).

Reference: systemdesign.one

---
Tags: complexity-theory, bloom-filters
---


# Question
Title: Can we transfer every DFA to DFAs with start state having no in edge?
The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of limit in DFA (deterministic finite automaton).

I have doubt between two awnsers which are:

1. It depends on the language and is not possible for every DFA.
2. *Yes* we can.

If the answer is positive then how ?

# Answer
> 15 votes
It is possible. You just need to duplicate the start state, one copy becoming the starting state with no in-edge, the other copy becoming a state that can have in-edges.

Formally, if $A = (Q, \delta, q\_0, F)$ is a DFA, then consider $B = (Q', \delta', q\_0', F')$ with:

* $Q' = Q\cup \\{q\_0'\\}$;
* $F' = F$ if $q\_0\notin F$, or $F' = F\cup \\{q\_0'\\}$ otherwise;
* for $q\in Q$ and $a\in \Sigma$, $\delta'(q, a) = \delta(q, a)$;
* for $a\in \Sigma$, $\delta'(q\_0', a) = \delta(q\_0, a)$.

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


# Question
Title: Transform a non-regular language into a regular one using sort
Is there a way where sort turns a non regular language into a regular one. What I mean by sort is this: Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively. If there is, do you have an example. If not can you provide a proof if you can.

# Answer
No the class of all non-regular languages is not closed under sort. For example take the language $L=\\{a^nba^n\\}$. It is clearly not regular (by the pumping lemma). However, $sort(L)$ is the language defined by even many $a$s and then a $b$. This language is clearly regular.
> 1 votes

---
Tags: regular-languages, finite-automata
---


# Question
Title: How does a Turing machine read a transition table as a function?
I am learning about Turing machines. I understand the alphabet set of symbols and the states a machine can be in. However, I do not understand how the transition function works.

I come from a maths background and functions always follow a simple input output. The table of transtions seems out of place.

How does a computer read a table as a function?

# Answer
You can think of a function $f:S\times \Sigma \rightarrow S$ as a "table", where the rows are elements of $S$, the columns are elements of $\Sigma$, and the cell's contents is the result $f(s,\sigma)\in S$ of the $s$ of the current row, and the $\sigma$ of the current column.

This is just a more convenient way to write complex transition functions and doesn't have a real semantic meaning.
> 3 votes

---
Tags: turing-machines, transition-systems
---