# Question
Title: Does there exist an context free language L such that L∩L^R is not context free?
By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an example of $L$, but it seems the set of $L \cap L^R$ could only have palindromes (including languages like $aaa \ldots$) and the empty string. However, palindromes in $L \cap L^R$ are always context-free. May I ask if anyone could provide me an example of CFL $L$ such that $L\cap L^R$ is not context-free?

# Answer
Consider $L = \\{ a^n b^n a^m \mid m,n\ge 1\\}$.

In fact you can repeat this to get more equalities $\\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\\}$. Etcetera.

Note that we can get really fun things: For $ L = \\{ a^n b^{2n} \mid n\ge 1 \\}^\* \\;\cup\\; b^+ {\cdot} \\{ a^{2n} b^n \mid n\ge 1 \\}^\* {\cdot} a $ $L\cap L^R$ contains words of the form $ a^1 b^2 a^4 b^8 \dots b^{2^k} $ (and their mirror image).

**Added.** In fact, the trick above can be extended to "encode" all intersections of two arbitrary context-free languages. Let $K\_1,K\_2$ be context-free. Take a new special letter $\square$. Now take $L = \square K\_1 \cup K\_2^R\square$. Then

$L\cap L^R = \square (K\_1\cap K\_2) \\; \cup\\; (K\_1^R\cap K\_2^R)\square $

as words in $L$ are either marked at the start or at the end, depending whether they belong to $K\_1$ or the reversal of $K\_2$.
> 5 votes

# Answer
One of the conventional examples of languages that are not context-free is $X = \\{ a^n b^n a^n | n \geq 0 \\}$. You can use that to construct an example of what you are looking for by setting $L = \\{ a^n b^n a^m | n,m \geq 0 \\}$. $L$ is clearly context-free but $L \cap L^R = M$. You can use similar tricks to construct other conventional non-context-free languages, or at least variations of them.
> 0 votes

---
Tags: context-free, closure-properties, computational-linguistics
---


# Question
Title: Algorithm for constructing a numbering reflecting the order of activities
I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) that needs to be done. An arc between two activities $uv$ means $u$ needs to be done before $v$ and the weight of the arc represents the duration it takes to complete $u$.

A given activity network could look like this:

* $A$: Foundation, duration: 7 days
* $B$: Door frames, duration 2 days
* $C$: Put in walls, 10 days, depends on $A$, $B$
* ...

Based on this, we can draw the graph of the activity network, satisfying the precendence relations.

The book introduces a way to number the vertices in the network in such a way that the precedence relations are satisfied.

A good numbering in this case would be $A \mapsto 1, B \mapsto 2, C \mapsto 3$. What would not be possible is to number $C$ as $1$, since $C$ depends on $A, B$.

The book uses the following algorithm:

* Represent each activity as a vertex. For each vertex, create a shadow vertex.
* Construct a bipartite graph in which one set of vertices consists of the original vertices and the other set cosnstis of the shadow vertices.
* If an activity $Y$ depends on $X$, then draw an edge joining $Y$ to the shadow vertex of $X$.
* Number all the original vertices without edges.
* Delete all numbered vertices and their corresponding shadow vertices.
* Continue until all vertices are numbered.

---

Besides the description and some examples, the book doesn't contain any more details.

1. Is there a name for this algorithm, so that I can look up more information?
2. In particular, why does the usage of a bipartite graph necessarily result in a good numbering?

The book remarks that this algorithm was developed by Fulkerson. Tried to search for it, but mainly his network flow algorithms came up.

# Answer
This is called topological sorting.

There are many algorithms for topological sorting. The one you list isn't the first I would recommend studying, to learn about this topic. There's no fundamental need for shadow vertices or a bipartite graph. See, e.g., https://en.wikipedia.org/wiki/Topological\_sorting#Kahn's\_algorithm. I've always heard this attributed to Kahn, not Fulkerson.

Without context on the specific book you are reading and a quote of the relevant section, I have no way of clearing up why the book presented it that way.
> 0 votes

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


# Question
Title: Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?
I have been trying to find a a CFG for this language generated.

I came to the conclusion that I need three parts

1. When $i \le j$
2. When $j \< 2j \< i$
3. When $j \< i \< 2j$

I was able to come up the production rules for 1 and 2 but I'm getting stuck at 3.

I thought I found a solution in Context Free Grammar for $\\{a^ib^j | i,j ≥ 0; i ≠ 2j\\}$, but when I tried for $0^81^5$ it didn't work.

I was however able to come up with a CSG.

Do you know how to solve this?

# Answer
I will only argue about 3), since this is the case you're having troubles with.

Consider $\\{ 0^i 1^j \mid j \le i \le 2j \\}$ for a moment. You can get a CFG for this language by noticing that you can "match" each occurrence of a $1$ to either $1$ or $2$ occurrences of $0$s (in such a way that every occurrence of $0$ is matched exactly to a single occurrence of $1$).

$$ S \to 0S1 \mid 00S1 \mid \varepsilon $$

To get a CFG for $\\{ 0^i 1^j \mid j \< i \< 2j \\}$ you just need to ensure that a) there is at least one $1$ matched to a single $0$, and b) there is at least one $1$ matched to two $0$s.

Since using the order of the rules is irrelevant and using $S \to 0S1$ followed $S \to S \to 00S1$ generates $3$ zeros and $2$ ones, we can simulate the execution of these rules as the last step each possible derivation by replacing $S \to \varepsilon$ with $S \to 00011$. To summarize, the final grammar is: $$ S \to 0S1 \mid 00S1 \mid 00011. $$
> 1 votes

# Answer
You only need a grammar for i \< 2j and i \> 2j. Have a symbol X that gets converted to 0, 01, 0X, 0X1 or 0X11, so j \< 2i. And a symbol Y that gets converted to 1 or 0Y11Z, with Z converted to eps or Z1, so j \> 2i.

```
S -> X | Y
X -> 0 | 01 | 0X | 0X1 | 0x11
Y -> 1 | 0Y11Z
Z -> eps | Z1

```
> 0 votes

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


# Question
Title: How to find optimum number of cpu cores for a workload
Following bar graph shows maximum percentage cpu utilization of F16sv2 (16vcpu &32GB) azure virtual machine in last 30 days. Only sometimes CPU usage goes more than 60 percentage.

1. How to find the right number of CPU cores for the workload so cpu never goes under utilized?
2. What factors should we consider while doing scale up/down on of VM from historical data?
3. Do I get almost full cpu utilization if I scale down the vm to F8sv2 (8vcpu & 16GB). 16GB ram is okay for me.

# Answer
If you have a supervisor that allocates CPUs exclusively to one VM then you should use a different supervisor.

You have n real CPUs. The can do n times x amounts of work per second. Whether your VM has 2 CPUs at 100% or 4 CPUs at 50% makes very little difference. Unless you pay per CPU
> 0 votes

---
Tags: cpu, threads
---


title: Independent sets generation in a graph

text:
# Question
Title: Independent sets generation in a graph
Is there an algorithm that, given an undirected graph and one independent set **IS1**, finds an other independent set **IS2** by adding and deleting vertices from the first **IS1**?

# Answer
> 1 votes
Yes, most algorithms for *enumerating maximal **cliques*** are based on exactly this principle. Since a clique is just an independent set in the complement, you could simply take $\overline G$ and enumerate cliques. Of course, if your graph is very sparse, this might in practice not be a good idea.

The trivial branching algorithm would just try to add a new vertex to the solution, and delete all its neighbors in the solution.

On the other hand, there is a class of problems called *reconfiguration problems* in which we want to go from one solution to another with certain restrictions, e.g., we want to go from solution to solution with only adding and deleting vertices, or we want to move solutions along edges, etc. There is a paper on this for independent set, Complexity of independent set reconfigurability problems, by Kamiński, Medved, and Milanič.

---
Tags: algorithms, graphs, independent-sets
---


# Question
Title: Choose elements from sets that form a permutation: NP hard?
Let $n$ be a positive integer and $\[n\] := \\{1,2,3,...,n\\}$. You are given $k$ non-empty subsets of $\[n\]$. Decide whether it is possible to select exactly one element from each subset such that the elements selected form a permutation of $\[n\]$. I try to reduce the Hamiltonian cycle problem. However, Hamiltonian cycles only allow one cycle while permutations might have many cycles. How, please?

# Answer
It is currently unknown whether your problem is NP-Hard. However, if it were, then it would be the case that P=NP.

To solve the problem in polynomial-time you can check whether a maximum matching in the following bipartite graph $G=(U \cup V, E)$ has size $n$:

* The set $U$ is $u\_1, \dots, u\_n$.
* The set $V$ is $v\_1, \dots, v\_k$.
* $(u\_i, v\_j) \in E$ if and only if the $j$-th subset contains $i$.
> 2 votes

---
Tags: polynomial-time-reductions
---


# Question
Title: Pseudopolynomials and $NP$ problems like $CLIQUE$
Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be polynomial in the length of its representation and not its value; that is, if we want a solution polynomial in the size of the input.

For example, in his book "Computational Complexity", Papadimitriou says about the dynamic programming $KNAPSACK$ solution in time $O(nW)$ (where $n$ is the number of items and $W$ the weight limit):

> This is not a polynomial algorithm because its time bound $nW$ is *not a polynomial function of the input:* The length of the input is something like $n \log W$.

But doesn't that apply to any problem whose input involves an integer? For example, I find it hard to see how the *nondeterministic* solution of $CLIQUE$ takes polynomial time.

Using nondeterministic-choice pseudocode, the classic solution seems to be:

```
solve_clique(G=(V, E), K):
    S := {}
    for i = 1..K
        S := S u choice(V)

   return check_clique(G, K, S)

```

But isn't the loop from 1 to $K$ *exponential* in the size of the input (of size $\log K$?)?

Even moving away from nondeterminism and thinking about the certificate-definition of $NP$ leaves me confused: the certificate is a clique of size $K$, so to go through all the nodes would require time exponential in $\log K$.

Is the key idea here that the clique size cannot exceed $|V|$? So $K \le |V|$; and since the input already contains the graph (say, represented in $O(|V|^2)$ by an adjacency matrix, then the clique is actually exponential in $\log |V|$ so polynomial in the input size?

# Answer
The number $K$ of iterations of the loop is exponential in the size of the representation of $K$ (which is $\log K$) but it is polynomial in the size of the *input* of the problem. The input of the problem is not just the integer $K$ but both the graph $G$ and $K$. The size of the representation of $G$ is $\Omega(|V|)$ and $K \le |V|$.

The same reasoning applies to the certificate: the length of the certificate needs to be polynomial in the size of the input instance, and the certificate checker also needs to run in polynomial-time w.r.t. the input instance (and hence also w.r.t. the certificate). If you find a clique of size $K$ you can clearly encode this solution in a certificate of size $O(K) \subseteq O(N)$ (for example by listing the "names" of the nodes of the clique).
> 2 votes

---
Tags: np, polynomial-time
---


# Question
Title: How to find the free memory addresses in RAM?
I am currently trying to build a simple computer in Minecraft (8-bit data, 6-bit addresses, no paging or segmentation), with redstone, where I can make run simple programs written similarly to code in the Little Man Computer. However, I have come across the problem that I have no idea which addresses in RAM are free to use.

I have seen Linux, for example, has an array that describes each address (that I am guessing includes if it is free or not). In my case, however, it seems impractical to create a massive block of memory dedicated to this, that will be a very similar size to even the RAM itself, due to having the same length for addresses.

Am I thinking about this the wrong way? Is there a more efficient method than creating a large block of storage? Is there a way to decrease the size of the storage?

# Answer
The memory allocator is typically responsible for keeping track of which areas in memory are free. For instance, the memory allocator might keep a list of which regions of memory are free and available for allocation. This is called, appropriately, the "free list". See https://en.wikipedia.org/wiki/Free\_list and https://en.wikipedia.org/wiki/Memory\_management.
> 0 votes

---
Tags: memory-management
---


# Question
Title: In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?
In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language program which is basically a sequence of instructions. These instructions are easy enough to be implemented in TMs. I am attaching the whole argument in a snapshot. What I am not able to get is that how can TM determine which instruction it has to execute? Of course, we cannot write the complete sequence of instructions in states because number of states is fixed but length of the program may be not.

# Answer
> 1 votes
The tape of the TM stores the code of the program (the sequence of machine instructions), followed by the memory of the program. You design a TM that traverses back and forth between the code section (to find the next instruction to execute) and the memory section (to execute that one instruction and update memory appropriately), repeating until it has finished simulating execution of the program..

# Answer
> 1 votes
They aren't trying to show that there is a single Turing machine that can run every C program (although that's also true). They're trying to show that for every C program, there is some Turing machine equivalent to it. Every C program compiles to a fixed finite number of machine instructions, so you can encode them as states of the Turing machine and end up with a fixed finite number of states.

---
Tags: turing-machines, programming-languages
---


# Question
Title: What are the non-overlapping properties of a function?
Specifically, properties that identify preconditions over which a function can be used without resulting in undefined behavior or data races.

For example, I am familiar with 3 important properties:

My question is whether:

* is this set of properties non-overlapping and complete?
* If not, is there a set of properties that makes it non-overlapping and complete?

Note that there are environment-specific properties (e.g. thread-safe in multi-threaded environments), or programming languages (generic vs non-generic, number of arguments, etc) that are not of relevance in this context. To reason, we can think of properties of a AWS Lambda or Azure Function, where these environment-specific do not apply.

By non-overlapping I mean that no property in the set has an if and only if relationship with a subset of any other properties in the set.

By complete I mean that any other property not in the set of properties can be logically derived from the said set of properties.

# Answer
> 1 votes
There is no complete properties. You can always find one more. In particular, a property is just a subset of functions, and there are infinitely many functions, so there are infinitely many properties.

Assuming I have understood your definition of non-overlapping correctly, these three are non-overlapping. An idempotent function can be pure or not pure; it just must ensure that if it has any side effect (e.g., "launch the missile if it hasn't been launched yet"), then performing that side effect twice is equivalent to performing it once. A pure function can be idempotent or not idempotent; e.g., $f(x)=0$ is idempotent, but $f(x)=2x$ is not. Re-entrancy is an orthogonal consideration.

---
Tags: functional-programming
---


title: What is a safe programming language?

text:
# Question
Title: What is a safe programming language?
Safe programming languages (PL) are gaining popularity. What is the **formal definition** of safe PL? For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to a PL implementation rather than to the PL itself. If so, how do we define what is a safe PL implementation?

# Answer
When we call a language “safe” *in some respect*, that formally means that there’s a proof that no well-formed program in the language can do something we consider dangerous. The word “safe” is also used less formally, but that’s what people here understand your question to mean. There are many different definitions of properties we want a “safe” language to have.

A few important ones are:

* Andrew Wright and Matthias Felleisen’s definition of “type soundness”, which is cited in many places (including Wikipedia) as an accepted definition of “type safety,” and their 1994 proof that a subset of ML meets it.
* Michael Hicks lists several definitions of “memory safety” here. Some are lists of types of errors that cannot occur, and some are based on treating pointers as capabilities. Java guarantees that none of those errors are possible (unless you explicitly use a feature marked `unsafe`) by having a garbage collector manage all allocations and deallocations. Rust makes the same guarantee (again, unless you explicitly mark code as `unsafe`), through its affine type system, which requires a variable to be either owned or borrowed before being used at most once.
* Similarly, thread-safe code is usually defined as code that cannot exhibit certain kinds of bugs involving threads and shared memory, including data races and deadlocks. These properties are often enforced at the language level: Rust guarantees that data races cannot occur in its type system, C++ guarantees that its `std::shared_ptr` smart pointers to the same objects in multiple threads will not delete an object prematurely or fail to delete it when the last reference to it is destroyed, C and C++ additionally have `atomic` variables built into the language, with atomic operations guaranteed to enforce certain kinds of memory-consistency if used correctly. MPI restricts interprocess communication to explicit messages, and OpenMP has syntax to ensure that access to variables from different threads is safe.
* The property that memory will never leak is often called safe-for-space. Automatic garbage collection is one language feature to ensure this.
* Many languages have a guarantee that its operations will have well-defined results and its programs will be well-behaved. As supercat gave an example of above, C does this for unsigned arithmetic (guaranteed to wrap around safely) but not signed arithmetic (where overflow is allowed to cause arbitrary bugs, because C needed to support CPUs that do wildly-different things when signed arithmetic overflows), but then the language sometimes silently converts unsigned quantities to signed ones.
* Functional languages have a large number of invariants that any well-formed program is guaranteed to maintain, for example, that pure functions cannot cause side-effects. These may or may not be described as “safe.”
* Some languages, such as SPARK or OCaml, are designed to facilitate proving program correctness. This may or may not be described as “safe” from bugs.
* Proofs that a system cannot violate a formal security model (hence the quip, “Any system that’s provably secure probably isn’t.”)
> 32 votes

# Answer
There is no formal definition of "safe programming language"; it's an informal notion. Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety is being claimed/guaranteed/provided. For instance, the language might provide type safety, memory safety, or some other similar guarantee.
> 100 votes

# Answer
If you can get your hands on a copy of Benjamin Pierce's Types and Programming Languages, in the introduction, he has a good overview on various perspectives on the term "safe language".

One proposed interpretation of the term that you might find interesting is:

> “A safe language is completely defined by its programmer’s manual.” Let the definition of a language be the set of things the programmer needs to understand in order to predict the behavior of every program in the language. Then the manual for a language like C does not constitute a definition, since the behavior of some programs (e.g., ones involving unchecked array accesses or pointer arithmetic) cannot be predicted without knowing the details of how a particular C compiler lays out structures in memory, etc., and the same program may have quite different behaviors when executed by different compilers.

So, I would be hesitant to use the term "unsafe" to refer to a programming language implementation. If an undefined term in a language produces different behavior in different implementations, one of the implementations might product behavior that might be more expected, but I wouldn't call it "safe".
> 42 votes

# Answer
**Safe** is not binary, it's a **continuum**.

Informally speaking, safety is meant by opposition to bugs, the 2 most often mentioned being:

* Memory Safety: the language and its implementation prevent a variety of memory related errors such as use-after-free, double-free, out-of-bounds access, ...
* Type Safety: the language and its implementation prevent a variety of type related errors such as unchecked casts, ...

Those are not the *sole* classes of bugs that languages prevent, data-race freedom or deadlock freedom is rather desirable, proofs of correctness are pretty sweet, etc...

Simply incorrect programs are rarely considered "unsafe" however (only buggy), and the term safety is generally reserved for guarantees affecting our ability to *reason* about a program. Thus, C, C++ or Go, having Undefined Behavior, are unsafe.

And of course, there are languages with unsafe subsets (Java, Rust, ...) which purposefully delineate areas where the developer is responsible for maintaining the language guarantees and the compiler is in "hands-off" mode. The languages are still generally dubbed *safe*, despite this escape hatch, a pragmatic definition.
> 20 votes

# Answer
While I don't disagree with D.W.'s answer, I think it leaves one part of "safe" unaddressed.

As noted, there are multiple types of safety promoted. I believe it's good to understand why there are multiple notions. Each notion is associated with the idea that programs suffer especially from a certain class of bugs, and that programmers would be unable to make this specific kind of bug if the language blocked the programmer from doing so.

It should be noted that these different notions therefore have different classes of bugs, and these classes are not mutually exclusive nor do these classes cover all forms of bugs. Just to take D.W.'s 2 examples, the question whether a certain memory location holds a certain object is both a question of type safety and memory safety.

A further criticism of "safe languages" follows from the observation that banning certain constructs deemed dangerous leaves the programmer with the need to come up with alternatives. Empirically, safety is better achieved by good libraries. using code that's already field-tested saves you from making new bugs.
> 15 votes

# Answer
A fundamental difference between C and Java is that if one avoids certain easily-identifiable features of Java (e.g. those in the `Unsafe` namespace), every possible action one may attempt--including "erroneous" ones--will have an limited range of possible outcomes. While this limits what one can do in Java--at least without using the `Unsafe` namespace, it also makes it possible to limit the damage that can be caused by an erroneous program, or--more importantly--by a program which would correctly process valid files but is not particularly guarded against erroneous ones.

Traditionally, C compilers would process many actions in Standard-defined fashion in "normal" cases, while processing many corner cases "in a manner characteristic of the environment". If one were using a CPU which would short out and catch fire if numerical overflow occurred and wanted to avoid having the CPU catch fire, one would need to write code to avoid numerical overflow. If, however, one were using a CPU which would perfectly happily truncate values in two's-complement fashion, one didn't have to avoid overflows in cases where such truncation would result in acceptable behavior.

Modern C takes things a step further: even if one is targeting a platform which would naturally define a behavior for something like numerical overflow where the Standard would impose no requirements, overflow in one portion of a program may affect the behavior of other parts of the program in arbitrary fashion not bound by the laws of time and causality. For example, consider something like:

```
 uint32_t test(uint16_t x)
 {
   if (x < 50000) foo(x);
   return x*x; // Note x will promote to "int" if that type is >16 bits.
 }

```

A "modern" C compiler given something like the above might conclude that since the computation of x\*x would overflow if x is greater than 46340, it can perform the call to "foo" unconditionally. Note that even if it would be acceptable to have a program abnormally terminate if x is out of range, or have the function return any value whatsoever in such cases, calling foo() with an out-of-range x might cause damage far beyond either of those possibilities. Traditional C wouldn't provide any safety gear beyond what the programmer and underlying platform supplied, but would allow safety gear to limit the damage from unexpected situations. Modern C will bypass any safety gear that isn't 100% effective at keeping everything under control.
> 8 votes

# Answer
There are several layers of correctness in a language. In order of increasing abstraction:

* Few programs are error free (only those for which correctness can be proven). Others mentioned already that *error containment* is therefore the most concrete safety aspect. Languages which run in a virtual machine like Java and .net are generally safer in this respect: Program errors are normally intercepted and handled in a defined way.1
* At the next level, errors detected at compile time instead of at run time make a language safer. A syntactically correct program should also be semantically right as much as possible. Of course the compiler cannot know the big picture, so this concerns the detail level. Strong and expressive data types are one aspect of safety on this level. One could say *the language should make it hard to make certain kinds of errors* (type errors, out-of bound access, uninitialized variables etc.). Run-time type information like arrays which carry length information avoid errors. I programmed Ada 83 in college and found that a compiling Ada program typically contained perhaps an order of magnitude fewer errors than the corresponding C program. Just take Ada's ability to user-define integer types which are not assignable without explicit conversion: Whole space ships have crashed because feet and meters were confused, which one could trivially avoid with Ada.
* At the next level, the language should provide means to avoid boilerplate code. If you have to write your own containers, or their sorting, or their concatenation, or if you must write your own `string::trim()` you'll make mistakes. Since the abstraction level rises this criteria involves the language proper as well as the language's standard library.
* These days the language should provide means for concurrent programming on the language level. Concurrency is hard to get right and perhaps impossible to do correctly without language support.
* The language should provide means for modularization and collaboration. The strong, elaborate, user-defined types from above help create expressive APIs.

Somewhat orthogonally the language definition should be intelligible; the language and libraries should be well documented. Bad or missing documentation leads to bad and wrong programs.

---

1 But because usually the correctness of the *virtual machine* cannot be proven such languages may somewhat paradoxically not be suitable for very strict safety requirements.
> 6 votes

# Answer
> Please, do not say that every PL has unsafe commands. We can always take a safe subset.

Every language I know of has ways of writing illegal programs that can be (compiled and) run. And every language that I know of has a safe subset. So, what's your question really?

---

Safety is multidimensional and subjective.

Some languages have lots of operations that are "unsafe". Others have a fewer such operations. In some languages, the default way of doing something is inherently unsafe. In others, the default way is safe. In some languages, there is an explicit "unsafe" subset. In other languages, there is no such subset at all.

In some languages, "safety" refers exclusively to memory safety — a service offered by the standard library and/or the runtime where memory access violations are made difficult or impossible. In other languages, "safety" explicitly includes thread safety. In other languages, "safety" refers to the guarantee that a program will not crash (a requirement that includes not allowing uncaught exceptions of any kind). Finally, in many languages "safety" refers to type safety — if the type system is consistent in certain ways, it is said to be "sound" (incidentally, Java and C# do not have completely sound type systems).

And in some languages, all the different meanings of "safety" are considered subsets of type safety (e.g. Rust and Pony achieve thread safety through properties of the type system).
> 2 votes

# Answer
Take this C code:

```
int* p;
*p = 1;

```

C is a very unsafe language. p is uninitialised, so it could point anywhere. Likely effects are an immediate crash, overwriting memory somewhere with no bad side effect, or overwriting something important, and then Things Go Wrong. Now we change it to

```
int* p = NULL;
*p = 1;

```

On many implementations this will crash because that’s storing to NULL will crash on those implementations. But you may have an optimising compiler that throws this and any following code away!

Now in a safe language, the first example would not compile. The compiler must prove that any variable has been assigned a value before it is used. In the second example, assigning NULL is only allowed if p is a nullable variable, but then assigning through that pointer is not allowed unless the value is tested first successfully so the assignment could not happen.

A safe language also needs to handle the case that a pointer becomes invalid. Examples:

```
int* p = malloc(100);
int* q = p;
free(p);

```

Now both p and q are invalid and assignment through either will be unsafe; a safe language prevents this. Or

```
int* p;
{ int x; p = &x; }
*p = 2;

```

At the time of the assignment p has changed from a valid pointer to an invalid one because x doesn’t exist anymore. A safe language will prevent this.
> 0 votes

# Answer
All languages are converted to the same instruction set for execution so at a very low-level view no language can be more or less inherently safe than another.

The words "safe" and "safety" have in recent decades been mutilated by certain politically oriented parts of English-speaking society, such that the common usage has almost no definition. However, for technical matters I define "safety" and "safe" as a device(physical or procedural) that prevents the unintentional use of something or that makes accidental use substantially more difficult; and the state of being under the protection of such a device.

So, a safe language has some device to limit a particular class of bugs. Limits by their nature often come with some other inconvenience or outright lack of ability. This inconvenience or inability to do certain things may or may not be an acceptable tradeoff, and must be judged for each situation.

This also should not be taken to imply that "unsafe" languages will result in bugs. For example, I don't have safety corks on my forks and yet I have, without much effort, managed for decades to avoid stabbing my eye while eating. It is certainly less effort to use bare forks with a bit of care and skill than the effort that would be needed to use the fork-cork. (The fork-cork is an old obscure pop culture reference.) The saved effort frees up resources I can use to improve other parts of my life.
> -2 votes

---
Tags: programming-languages
---


# Question
Title: Explanation of a simple example of how an interaction net computes?
I have briefly looked through the links at the bottom of this page:

* Interaction Nets
* Interaction Combinators
* Implementation of a low-level language for interaction nets, Shinya Sato
* Inpla, Interaction Nets as Programming Language
* Towards a Programming Language for Interaction Nets, Ian Mackie
* An Implementation Model for Interaction Nets
* Interaction Nets Playground
* Bologna Optimal Higher-Order Machine

That covers most of the stuff on the web about interaction nets it seems.

But without being a mathematician, I am struggling to get beyond the basic terminology, which doesn't resonate intuitively upon my initial readings.

* agent
* connection
* port
* net
* rule

They describe that agents are nets which connect through their principle ports, etc.. But what does this mean in terms of practical computation? I don't follow the visual diagrams of the nets either, so they aren't of much use to me yet.

Could you provide an example of some simple function taken from an imperative programming language (such as `add`, `multiply`, or iterating through some list or something), and explain how it would work from an interaction net perspective? What is doing what, how do the 5 names map to the parts of such a simple example program? I am having a hard time understanding the terminology, and applying it to a practical problem of representing some imperative function using the parallelizable interaction net paradigm.

# Answer
Interaction nets are a form of graph rewriting. Nets are graphs made up of some finite number of labelled nodes with connections between them. If two nodes have the same label then they have the same number of ports, that is places where they can connect to other nodes. Exactly one of these ports is noted as a "principal port" and these are important in determining which rewrite rules to follow.

The rewrite rules define how computation is done on a net by defining how to replace nodes.

For example, taking your "add" request, let's consider adding unary numbers: where we use Z to represent zero and Sx to represent the successor of a natural number x. Counting 0,1,2 is therefore Z,SZ,SSZ.

We need to represent Z. All we have is nodes, so lets define a node for Z. All this does is have a label Z on it and a port so it can be connected to other nodes:

We put a little arrow on the wire coming out of it to identify this as a principal port connection. (It has to be a principal port because, as noted above, each node has exactly one principal port).

Then we need a node to represent the successor of a number. This is a node labelled S which has one connection to the number it is a successor of and another connection available to the rest of the net. The connection that is not the principal port we call an auxiliary port:

This way we can represent any natural number either by the Z node alone or the number *n* where *n\>0* by *n* S nodes connected together with a Z node at the bottom.

To implement "add" we need some interaction rules. Interaction rules take a pair of nodes, connected via their principal ports, and define what to replace them with. If nodes are not connected via their principal ports they cannot be rewritten in this way. This is why principal ports are important.

Each pair of nodes has exactly one interaction rule, so if a pair can be rewritten there is no choice of how to rewrite it.

The only other restriction is that we must have the same number of auxiliary ports on both sides of the rewrite rule.

So how do we write rules for "add" given the unary number format?

We can consider two cases:

1. We are adding zero to a number, 0+y, which returns y or
2. We are adding a successor number to a number, Sx+y, which can be rewritten as S(x+y).

So we can use rule 2 recursively until we get down to zero. e.g. 2+1 is SSZ+SZ -\> S(SZ+SZ) -\> S(S(Z+SZ) -\> S(S(SZ) = SSSZ, or 3.

The first rule can be drawn like this where we have a new node "add" which has two auxiliary ports and one principal port:

Where we read out the answer at the "result". Remember y will be a Z node or some stack of S nodes with a Z at the bottom.

And the second rule like this:

The example of 1+2 --\> 3 can be drawn as:

(note that the middle diagram should have an arrow from the top S as this is a principal port).

Then we can go off and define multiply, sorting algorithms etc etc by creating nodes to represent the data and the functions, and a set of rules for the computation we want.

It is a remarkable feature of this system that it is Turing complete.

Hopefully that provides some help to you.
> 1 votes

---
Tags: programming-languages, interaction-nets
---


# Question
Title: Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?
The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one stable matching but there can be several. Traditionally, the problem was solved by having men propose and women accept/reject a proposition, which leads to a stable matching that is male-optimal but at the same time female-pessimal. But it is also possible to switch roles and have women propose and men accept/reject, which leads to the female-optimal stable matching, which at the same time is the male-pessimal.

Now, imagine a network with more men than women. I observed that in this case the male-optimal matching and the female-optimal matching are (so far) always identical, as in this simple example:

```
    Women's preferences
        A   B   C   D
M   U   1   1   1   2
e   V   2   2   2   1
n   W   3   6   5   4
    X   6   3   4   5
    Y   5   4   3   6
    Z   4   5   6   3
Read: Woman A's 1st choice is Man U

    Men's preferences
        U   V   W   X   Y   Z
W   A   1   1   2   2   1   1
o   B   2   2   1   4   2   2
m   C   3   4   3   1   3   3
e   D   4   3   4   3   4   4
n
Read: Men W's 4th choice is Woman D

    M   F   pM  pF
    U   A   1   1
    V   B   2   2
    Y   C   3   3
    Z   D   4   3
    W   NA  0   NA
    X   NA  0   NA
    Read: Man Z is matched up with Woman D. She is his 4th choice, while he is her 3rd choice

```

Above example returns the stable matching consisting of four matches A\<-\>U, B\<-\>V, C\<-\>Y and D\<-\>Z (while men W and X did not find a match), regardless if I start with men proposing or women proposing.

Now, what are the consequences if there is only one stable matching? I would love to understand if my thoughts are correct:

* First, I observed in my model always the same result, regardless if I used female-optimal algorithm or male-optimal. Since male-optimal solution = female-optimal solution, I claim there exists only one stable solution, which naturally is the optimal (and pessimal) solution for both genders.
* Second, given this stable matching, I cannot improve anybody's position in a ranking without making another person's situation worse. The algorithm stops once there is no blocking pair. Therefore, this matching is pareto efficient.
* Third, if only one stable matching exists, there is no possibility for any of the players to improve their situation by changing their strategy and creating a fake preference list (stating their actual preferences is their best strategy). I claim therefore that this is a Nash Equilibrium.

Example: In above example, U and A both have received their very first choice. They cannot be possibly happier. V and B would have liked A and A better than each other, but as U and A are already matched up with their ideal partner, V and B are the next best option. This continues until W and X, who both ended up without a match. However, no matter how they would have ranked their preferences, they always would have ended up without a match

# Answer
> 3 votes
First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^\*$.

However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer.

As the male-optimal and female-optimal matchings coincide, both can be considered the 'optimal' side and therefore is Pareto optimal for both sides.

Your third argument however, is incorrect. While it is true the matching is unique, this is under the *assumption* that all preferences are true. As this is not the case, we cannot use this fact to conclude strategy-proofness on both sides.

However, we have the stronger property that the female and male optimal matchings coincide. This again means that the properties the algorithm assigns to the male side automatically apply to the female side and therefore the matching is strategy-proof for both sides.

(Another way to argue is that any manipulation cannot give the woman them a better result than switching sides with the men. But they already have the result they would get by switching! So they cannot improve by manipulation.)

\*: Further conditions for uniqueness are explored in a paper by Jan Eeckhout:

The 'sufficient' condition for uniqueness (Theorem 1) basically says that if we order all men and women and if

1. All women of rank $i$ prefer the man of rank $i$ to any man of higher rank; and
2. All men of rank $i$ prefer the woman of rank $i$ to any woman of higher rank.

Furthermore, the paper mentions that if we match among a total of $4$ or $6$ persons, these conditions are also *necessary* for uniqueness.

---

If we want to talk about a Nash-Equilibrium, we have to phrase the matching process as a game. We can consider all men and women to be 'players' and their 'strategy' to be the preference profile they submit (which may differ from their actual preference, which determines the payoff). A set of strategies is said to be a Nash-Equilibrium if changing a single strategy of a single player cannot improve the results for that player. As we know that the current matching process is strategy-proof for all players involved, improving on 'everyone reports truthfully' is impossible. So, in this sense, the 'everyone reports truthfully' set of strategies is a Nash-Equilibrium.

In fact, we can say that strategy-proofness of our matching means precisely that the 'every reports truthfully' is a Nash-Equilibrium in the associated game we defined.

# Answer
> 0 votes
This paper provides conditions for uniqueness.

# Answer
> -2 votes
this recently published paper (open access) claims to have resolved the question of uniqueness.

---
Tags: game-theory, pareto
---


# Question
Title: Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:

```
for(int i=0; i<n*n*n; i++) {
        for(int j=0; j<n*n; j++) {
            if(i>n && j<n) {
                for(int k=0; k<n*n*n*n; k++) s++;
            }
        }
    }

```

I need to find its time complexity.

What I tried doing is: I tried determining the times the if clause would be fulfilled, and multiplying that with $n^4$.

However, I have a hard time determining how many times the if clause will be fulfilled. The values of `i` go from $n+1$ to $n^3-1$, while the values for `j` go from $0$ to $n-1$.

Now, for each value of `i` for which the first part of the condition is true, I have that there are $n$ values of `j` for it.

Unfortunately, this is as far as I have come. Could anyone help me out further?

# Answer
Let's divide it in two parts: when the code enters the **if** and when it does not.

1. The **if** is executed when $n\<i\<n^3$ and $0\leq j \<n$. This means that the values of $i$ which satisfy the condition are $n^3-n-1$, while the values of $j$ which satisfy the condition are $n-1$. For each value of $i$ for which the condition on it is satisfied you can choose every values of $j$ which satisfies the condition of it and viceversa. It means that the **if** is executed $(n^3-n-1)(n-1) = \Theta(n^4)$ times. In these cases the inner-most loop is executed $n^4$ times and each execution has a constant cost. So, the total cost of this case is $\Theta(n^4\cdot n^4)=\Theta(n^8)$.
2. In the remaining cases, i.e. $\approx n^5-n^4=\Theta(n^5)$ times, the **if** is not executed and the cost of one iteration the two outer-most loops is constant (just a check on the **if** condition), thus the cost of this case is $\Theta(n^5)$.

Summing up, the total cost is: $$\Theta(n^8)+\Theta(n^5)= \Theta(n^8) \ .$$

PS: If you are not familiar with asymptotic notation, look at it (big-O, Theta, Omega, small-o notations or Landau symbols). You can consider $\Theta(n^i)$ as $\approx n^i$ while reading this answer. Then I suggest you to go check these topics.
> 1 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, big-o-notation
---


# Question
Title: Time complexity of algorithm involving function calls
Me again.

This time I have a more general question.

Suppose I have the following code snippet:

```
int f(int k) {
  int s=0;
  for(int i=0; i<k*k; i++) {
   s++;
}
 return 2*k*k;
}

```

And the expression is:

`f(n) * f(f(f(n)));`

I am told that the complexity is `O(n^2) + O(n^2) + O(n^4) + O(n^8)`

I have several questions:

1. Why is there a plus sign when the function calls itself. Shouldn't it be "\*" in between the last three terms?
2. What if the expression was `f(n) + f(f(f(n)));`, would it still be the same?

And lastly and most importantly,

3. What if it was this expression?

`f(n) + f(z)*f(f(n))`

This also confuses me very much. Most notably because there is a new variable `z`, and also because I am not sure that even if it was `f(n)` instead of `f(z)`, should I multiply the complexity with `f(f(n))` or add it to it.

# Answer
> 0 votes
f(k) performs k^2 operations. f(n) returns 2n^2, f(f(n)) returns 8n^4, so you calculate f(n) * f(8n^4). This takes about 64n^8 operations and the result is 2n^2 * 128n^8 = 256 n^10.

There are O(n^4) other operations which we can ignore because that number is much smaller than 64n^8. The time complexity is O(n^8) or more precise $\theta(n^8)$.

However, any decent compiler will realise that all the additions are not needed and give the result in O(1).

In your second example, you calculate f(z) with z^2 operations, f(f(n)) with 4 n^4 operations, then multiply which is ONE operation. The product takes z^2 + 4m^4 + 1 operations.

# Answer
> 0 votes
Consider the following equivalent way of computing the expression:

```
x_1 = f(n);
x_2 = f(x_1);
x_3 = f(x_2);
return x_1 * x_3;

```

What are the (approximate) magnitudes of the different variables? What is the complexity of each call to `f`? What is the complexity of the multiplication on the last line? Then put this all together.

---
Tags: algorithms, time-complexity, algorithm-analysis, big-o-notation
---


title: Recurrence problem T(n) = 2T(n − 1) + 1

text:
# Question
Title: Recurrence problem T(n) = 2T(n − 1) + 1
Can I solve T(n) = 2T(n − 1) + 1 using the master theorem method? I don't think it cannot be solved with the master theorem because b=1. Please let me know, if my guess is wrong.

# Answer
> 3 votes
Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.

**Method 1: Guessing**

Here are some values of $T(n)$: $$ \begin{array}{c|cccccc} n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline T(n) & 0 & 1 & 3 & 7 & 15 & 31 \end{array} $$ If you're familiar with powers of 2, you will recognize that $T(n) = 2^n-1$. If not, you can look it up on the Online Encyclopedia of Integer Sequences, where you will find it as A000225, under the name *Mersenne numbers*.

**Method 2: Homogenization**

We look for a related recurrence without the "$+1$". The first think one could try is replacing $T(n)$ with $S(n) = T(n) + C$, which satisfies the recurrence $$ S(n) = T(n) + C = 2T(n-1) + C + 1 = 2S(n-1) - C + 1. $$ We see that if $C = 1$ then $S(n) = 2S(n-1)$, and so $S(n) = 2^n S(0) = 2^n$. We conclude that $T(n) = 2^n - 1$.

**Method 3: Reduction**

The recurrence makes it clear that the first order asymptotics of $T(n)$ should be related to $2^n$, and so suggests considering $R(n) = T(n)/2^n$, which satisfies the recurrence $$ R(n) = \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + \frac{1}{2^n} = R(n-1) + \frac{1}{2^n}. $$ This shows that $$ R(n) = R(0) + \sum\_{m=1}^n \frac{1}{2^m} = 1 - \frac{1}{2^n}, $$ and so $T(n) = 2^n - 1$.

If we are only interested in the asymptotics, we could notice that since the series $\sum\_{n=1}^\infty \frac{1}{2^n}$ converges, we clearly have $R(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

**Method 4: Generating series**

We could also solve the recurrence automatically using generating series. Let $$ P(x) = \sum\_{n=0}^\infty T(n) x^n. $$ Then $$ P(x) = T(0) + \sum\_{n=1}^\infty T(n) x^n = 2\sum\_{n=1}^\infty T(n-1) x^n + \sum\_{n=1}^\infty x^n = 2xP(x) + \frac{x}{1-x}. $$ We conclude that $$ P(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x} = \sum\_{n=0}^\infty (2^n - 1) x^n. $$ Therefore $T(n) = 2^n - 1$.

**Method 5: Combinatorial interpretation**

This method is more creative. We find some combinatorial object which we already know how to count, and we show that it satisfies the same recurrence. In this case, we could choose all non-empty subsets of $\\{1,\ldots,n\\}$. Each such subset is either obtained from a non-empty subset of $\\{1,\ldots,n-1\\}$ by either adding or not adding $n$, and additionally the subset $\\{n\\}$, which does not arise in this way. The base cases also match, and so $T(n) = 2^n - 1$.

# Answer
> 1 votes
You can only solve equations using the Master Theorem if they are of form $T(n) = aT(n/b) + f(n)$, where $a \ge 1$ and $b \> 1$.

Here you can't express your recurrence in above form. And your guess of taking $b = 1$ is completely wrong. The reason for not using the Master Theorem is that you can't express your recurrence in form $T(n) = aT(n/b) + f(n)$ where $a \ge 1$ and $b \> 1$. You would able to use the Master Theorem if the equation were $T(n) = 2T(n/2) + 1$, in which case $a = 2$ and $b = 2$.

In order to solve your recurrence equation $T(n) = 2T(n-1) + 1$, you will have to use a recursion tree, and then verify the solution using induction.

# Answer
> 0 votes
A short and direct answer to this question is "NO"

because master can't be applied because `b = 1`. and master method needs a\>=1 and `b>1` not equal

---
Tags: master-theorem
---


title: Fully Connected Graph to Lattice

text:
# Question
Title: Fully Connected Graph to Lattice
I am looking for algorithms (or at least something similar to the problem definition):

Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice graph (where each node, except for the ones at the edges, is connected to 4 other nodes) such that the sum of edge weights in $S$ is minimal.

I realize the problem might be NP-complete; if so, are there good approximation algorithms?

# Answer
Your problem is NP-Hard.

Consider the variant of the problem in which you need to delete the edges of a complete graph with $n$ vertices in order to obtain a $1 \times n$ lattice of minimum weight. This variant is clearly NP-Hard. Indeed, you turn any (not necessarily complete) graph $G=(V, E)$ into a weighted complete graph $H$ by setting the weights of the edges in $E$ to $0$ and by adding all the missing edges with weight $1$. There is a $1 \times n$ lattice (i.e., simple path of length $n-1$) of weight $0$ in $H$ if and only if $G$ is Hamiltonian.

To show that finding a $N \times N$ lattice is also NP-Hard you can augment the graph $H$ by adding $n^2-n$ "dummy" vertices organized into a $(n-1) \times n$ lattice $L$ (so that $N=n^2$). The weights of all the edges in $L$ are set to $-1$. The weights of all the remaining edges are set to $0$.

Let $m\_L$ be the number of edges in $L$.

If there is a Hamiltonian path $P$ in $G$ then you can find a lattice with weight $-m\_L$: the first row is exactly the path $P$ while the rest of the graph is $L$.

If there is a lattice with weight at most $-m\_L$ then it must contain $L$ as a sub-lattice. Therefore the $n$ vertices of $G$ must all be in the topmost/bottom row or in the leftmost/rightmost column and must contribute $0$ to the overall weight. This means that the path $P$ induced by that row/column contains only edges in $E$, i.e., $P$ is a Hamiltonian path of $G$.

If you don't like negative edge weights, you can scale all the weights up by an additive constant. Moreover, by setting the weight of the edges in $V^2 \setminus E$ to some large value, you can create an arbitrarily large gap between the weights of "yes" and "no" instances, ruling out the existence of approximation algorithms (unless P=NP).
> 1 votes

---
Tags: graphs, np-hard, lattices, subgraphs
---


# Question
Title: Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?
I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary alphabet in the proof of Theorem 3.2.

I only get to something like $DSPACE(\log^2n)\subseteq DTIME(\log n)$. (Using the usual line of arguments to count configurations as given in the answer to this related question.

In the paper above it is also mentioned in the same abstract that a TM transducer with operating with space in $O(\log^2 n)$ produces an output of length $O(n^{\log n})$. This too, I can not follow. Assuming an input tape of length $n$, a working tape of length $\log^2 n$, $|Q|$ states, and $|\Sigma|$ symbols; I count a total of:

* $n\*\log^2 n$ positions the TM can be in,
* $|Q|$ states to be in (constant for this examination)
* $|\Sigma|^{\log^2 n}$ working tape configurations. Resulting in a total of $n\*\log^2 n\*|Q|\*||\Sigma|^{\log^2 n}$ configurations the transducer can be in . This gives me $O(n\log^2 n\log n)$ as an upper bound for the output length of a transducer with $O(\log^2 n)$ space. The paper however claims $O(n^{\log n})$.

I am confused. Please help me understand why. Thanks!

EDIT: It seems my confusion might simply be a result of me thinking $\log^2 n = \log\log n$ ... but what is meant is $\log^2 n = (\log n)^2$? o.O

# Answer
My experience is that $\log^2 n$ normally means $(\log n)^2$, unless context indicates otherwise.

The result follows from the fact that $DSPACE(f(n)) \subseteq DTIME(2^{f(n)})$ (proven by using the fact that if a deterministic algorithm repeats the same state twice, then it loops infinitely).
> 1 votes

---
Tags: time-complexity, turing-machines, space-complexity, transducers
---


# Question
Title: Is loading from L2 or L3 of multi level cache direct or require a transfer to L1
(This is mainly about reads, and commercial products not hypothetical machines.) When loading a CPU register with data contained in L2 or L3 of a multi-level cache. Can the data that is in L2 or L3 but not in L1 be read directly, or must the cache line be transferred into L1 before moving to a register?

Another way to ask; do L2 and L3 only act as cache for the next lower level (L3\>L2, L2\>L1) or do they have some direct use by the processor core, and can L2 be skipped (L3\>L1)?

Most interested in the behavior of a modern multi-core with the amd64 ISA.(Though feel free to answer for IBM Power, ARM, or RISC-V if that is your specialty)

Is this use of L1(however it is used) only a matter of design policy or is it physically and logically predestined?

# Answer
> 2 votes
I am not aware of any x86 implementation that supported L1 cache bypassing for cacheable accesses unless one includes NT writes (which go to a special buffer and bypass all caches).

However, the MIPS R8000 (or specifically the R8010 FPU) had all FP memory accesses bypass L1, communicating directly with the L2 cache. For Itanium 2 (and follow-ons): "Floating-point loads are not cached in the L1D and are instead processed directly by the L2." (Intel® Itanium® 2 Processor Reference Manual For Software Development and Optimization, May 2004, p. 40)

Other implementations have had parallel L1 caches for which some accesses were allocated to a specific cache based on information in a page table entry.

The StrongARM SA1110 had an 8 KiB "main data cache" ("This cache allocates on loads to spaces marked B=1 and C=1.") and a 0.5 KiB "minicache" ("This cache allocates on loads to spaces marked B=0 and C=1"), where the B bit indicates "bufferable" and the C bit indicates "cacheable", being stored in a page table entry (Intel® StrongARM SA-1110 Microprocessor Developer’s Manual, June 2000).

The HP PA 7200 had an "assist cache" that was probed in parallel with the main L1 cache. All data accesses would be allocated to the assist cache; usually data evicted from the assist cache would be allocated to the main L1 cache. However, a "spatial locality only hint can be specified in load and store instructions ... Upon replacement, however, the line is flushed back to memory instead of being moved to the off-chip cache." ("Design of the HP PA 7200 CPU", Kenneth K. Chan et al., 1996) One could look at the main L1 cache as a huge direct-mapped victim cache for the assist cache, a reversing of size and associativity from the original victim cache proposal.

One interesting research example was the proposal for an Alpha processor with a vector extension ("Tarantula: A Vector Extension to the Alpha Architecture", Roger Espasa et al., 2002). Vector accesses would have bypassed the L1 data cache.

There is no insuperable barrier to implementing cache bypassing. There is additional wiring complexity (similar to higher associativity) and ideally one would want to know/accurately predict if a particular load is likely to be an L1 hit (out-of-order schedulers commonly assume L1 hits for scheduling dependent operations, if L1-bypassing was somewhat common such a design would have high replay overhead). With a writeback L1 cache, there is also some coherence difficulty if writes to the same cache block had been allocated to L1, but this could be handled by always probing L1 (but not reading data when bypassing is predicted) or marking in L2 that L1 has that data. Designing the L2 cache for somewhat frequent, sub-block accesses also has implications on area, power, and latency. Having a tiny cache in parallel with L1 would allow block-sized transfers that avoid polluting the main L1 and that cache might also be used as a L1 eviction buffer/victim cache/prefetch buffer.

Allocating non-temporal blocks to L1 with a replacement position/annotation for earlier eviction would have some of the benefit of complete bypassing with simpler timing factors, but even this is not (as far as I know) commonly implemented for L1 caches. (Intel has used set duelling to adjust replacement policies for L3 cache.)

Significant research has been done on cache bypassing.

# Answer
> 1 votes
Your processor may use read/write instructions to access hardware, in that case some pages will be marked as uncached, so a read of 4 bytes will directly read from an address that is most likely not connected to RAM.

Otherwise: I have never seen instructions that let you control this, the default is obviously going through L1 cache, so I assume there is no way to change this. It would be costly. If you read eight bytes from L2, and then access the same L2 cache line again, you will slow down. And it’s much easier if there is only one path from cache to registers.

The only *slight* adjustment that I have seen is that a cache line is divided into two halves, and the half containing the right data is transferred first to get the data a tiny bit quicker (but the other half is transferred immediately after that).

Note that you would have to check whether a value is in L1 cache anyway. And you have to build two transfer paths from L1 to registers and L2 to registers. Then if the value is changed you have to write it back to L2 cache, but at that point the cache line might already be evicted. For example x += 1 reads x, for some reason your thread is stopped and writing x+1 might happen a long time later. Now you have multiple cores with multiple threads using the same L2 cache and things get very complicated.

---
Tags: cpu-cache
---


# Question
Title: DFA for even concatenation of strings from a language
If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how would I solve this?

I was considering an approach where I alternate between accepted even multiples of the DFA and unaccepted odd multiples, and essentially connect two copies of the original DFA together to create the even-DFA. However, if I have multiple accept states within the original language this would complicate things as I would need to allow connections from all of these states, and would then need to consider the presence of self-loops.

This will be implemented in Haskell, but insight either from the logic point of view or the coding point of view would be greatly appreciated.

# Answer
The language you are considering is $(W^2)^\*$, so you could combine standard constructions for the concatenation and the star operation.
> 1 votes

---
Tags: finite-automata, logic, haskell
---


# Question
Title: Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \\{(,),\[,\]\\}$ and let $f\_n:A^n\times A^n \to \\{0,1\\}: f\_n(x,y) = 1 \text{ if } xy\in Dyck(2)$ and 0 otherwise. Suppose two parties Alice and Bob are given two n-bit strings $x,y.$ The communication complexity $C(f)$ of $Dyck(2)$ is defined as the minimum number of bits the two parties must exchange to compute $f\_n(x,y).$

My question: what is known about $C(f)$? Can we prove any reasonable bounds?

# Answer
> 1 votes
TL;DR: $n \le C(f) \le n+1$.

We can easily prove that $C(f) \ge n$. Consider the set of $x \in \\{(,\[\\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need to send at least $n$ bits to distinguish among these $x$-values.

Also, we trivially have $C(f) \le 2n$, as there are only $2^{2n}$ different values for $x$.

We can obtain a better upper bound on $C(f)$, as follows. Let the signature of $x$ be the shortest string $x'$ such that, for all $y$, $xy \in \text{Dyck}(2)$ iff $x'y \in \text{Dyck}(2)$. Then every signature $x$' is in $\\{\[,(\\}^{\le n}$, i.e., it uses only \['s and ('s and has length at most $n$. Let $N$ count the number of strings in $\\{\[,(\\}^{\le n}$, i.e.,

$$N = \sum\_{i+j \le n} {i+j \choose i},$$

where the sum is over all $i,j \in \mathbb{N}$ such that $i+j \le n$. Here $i$ counts the number of \['s in $x'$, and $j$ counts the number of ('s in $x'$. Letting $k=i+j$, we can calculate

$$N = \sum\_{k=0}^n \sum\_{i=0}^k {k \choose i} = \sum\_{k=0}^n 2^k = 2^{n+1}-1.$$

Now since every signature is one of these strings, there are at most $N$ different signatures. A valid strategy is for Alice to send the signature of $x$ to Bob (or Bob to send the signature of $y$ to Alice), and that contains everything needed to compute the answer. Since there are at most $N$ different signatures, we have $C(f) \le \lg N = \lg (2^{n+1}-1)$, so $C(f) \le n+1$.

---
Tags: complexity-theory, formal-languages, formal-grammars, communication-protocols, communication-complexity
---


title: A machine with multiple oracles

text:
# Question
Title: A machine with multiple oracles
Suppose a machine $T$, and oracles $A$ and $B$ solve all problems in the complexity classes $\mathcal C\_T$, $\mathcal C\_A$ and $\mathcal C\_B$ respectively.

Let $T^{\\{A,B\\}}$ denote a machine that is equivalent to a machine $T$ that has access to oracles $A$ and $B$. What would be the complexity class of all problems solvable by such a machine? Is it $\mathcal C\_T^{\mathcal C\_A\cup\mathcal C\_B}$, $\mathcal C\_T^{\mathcal C\_A}\cup\mathcal C\_T^{\mathcal C\_B}$ or something else entirely? E.g. could it be that $\mathsf{P^{\\{NP, coNP\\}}=PSPACE}$?

# Answer
The definition of an oracular complexity class is key to answering this question, it is often defined as: $$ \mathsf{C^{A}=\bigcup\_{L\_A\in A}C^{L\_A}} $$

But how do we define two oracles? Well the union definition ($\mathsf{C^{A,B}}=\mathsf{C^{A\cup B}}$) would imply that a Turing machine has access to only one language from either $\mathsf{A}$ or $\mathsf{B}$, which is not quite what we want. We would like that it has a language from both:

$$ \mathsf{A^{B,C} = \bigcup\_{L\_B\in B,\hspace{0.05cm}L\_C\in C} A^{L\_B, L\_C}}. $$

Choosing this definition would imply that $\mathsf{A^{B,C}\not = \mathsf{C^A \cup C^B}}$ either. For counter-example assume there exists some $\mathsf{L\_A\in C^A\setminus C^B}$ and some $\mathsf{L\_B\in C^B\setminus C^A}$. Deciding the language: $$ \mathsf{L}=\\{x\\#y: x\in L\_A, y\in L\_B \\} $$ is in $\mathsf{C^{A,B}}$ under our definition (assuming C is capable of Turing reductions), but it is in neither $\mathsf{C^A}$ or $\mathsf{C^B}$, so it can not be in $\mathsf{C^A \cup C^B}$.

So what is $\mathsf{C^{A,B}}$? Well, it seems to be it is its own object, without a simple equality to some other understood concept. Although, it often can be simplified when $\mathsf{A}$, $\mathsf{B}$ or $\mathsf{C}$ are known. For example, in the case you state there is a simple reduction.

$$ \mathsf{P^{NP,CoNP}=P^{NP} }. $$

This is because $\mathsf{P^{NP}=P^{CoNP}}$ and polynomial time TMs can simulate other polynomial time TMs.
> 1 votes

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: Proving heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree?
How to prove that the heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree? by heaviest edge of any Spanning tree i mean considering any possible Spanning tree, we have to prove that the heaviest edge in mst is not heavier than heaviest edge of that spanning tree.

# Answer
> 1 votes
Let $e^\*$ be the heaviest edge in an MST $T$, and let $A$ and $B$ be the vertices of the two connected components of $T - e^\*$.

Now, by the cut property, $e^\*$ is a cheapest edge with one endpoint in $A$ and one endpoint in $B$.

Since any spanning tree $T'$ must have an edge $e$ with one endpoint in $A$ and one in $B$, this means that $T'$ has an edge of cost *at least* the cost of $e^\*$.

---
Tags: minimum-spanning-tree
---


# Question
Title: supplying water for all houses of a city with either a well or pipe
Consider $n$ houses in a city which each house's water can be supplied with either a well or pipes from other houses. Constructing a well in a house $i$ costs $w\_i$ and connecting a pipe from house $i$ to $j$ costs $c(i,j)$.

The question is to find an algorithm to find the minimum cost to provide water to all houses.

My approach is to use Dijkstra's algorithm to answer it. The weight of each node is $w\_i$ (its well cost). Enter each node's weight into a priority queue. and then it just starts from the minimum of the priority queue, and doing Dijkstra's normally.

I think it's wrong. Can anyone guide me a little?

By the way, my algorithm is using Dijkstra's as you see -- but I think it should use a minimum spanning tree. However, I have some difficulty finding a way to take the weight of each node (cost of a well) into account.

# Answer
> 1 votes
Consider graph $G=(V,E)$ where $V = \\{s, v\_1, v\_2, \dots, v\_n\\}$ and there is an edge $(v\_i, v\_j)$ of weight $c(i,j)$ for all distinct (unordered) pairs $i,j$ with $1 \le i \le n$. Moreover, for each $i=1,\dots,n$, add the edge $(s, v\_i)$ of weight $w\_i$ .

Let $T = (V, E\_T)$ be a minimum spanning tree of $G$. Build a pipe from house $i$ to house $j$ iff $(v\_i, v\_j) \in E\_T$. Build a well on house $i$ iff $(s, v\_i) \in E\_T$. The cost of building these pipes/wells is exactly the weight of $T$. To see that this is optimal notice that any solution that costs $c$ that provide water to all houses implies the existence of spanning tree of $G$ with weight at most $c$.

---
Tags: minimum-spanning-tree, dijkstras-algorithm
---


# Question
Title: How to create a 'hashing' function that maps up to 1 to N numbers uniquely to numbers 1 to N
I would like to use or create a hashing algorithm that takes K inputs from 1 to N and maps them uniquely to different numbers on 1 to N. K can be 1 to N. Ideally I would like the hashing alg to be able to be salted, but I'm not sure that is possible if some of these numbers must be prime.

Someone in #algorithms on libera suggested using $g^i\bmod p$ where $p$ is a prime and $g$ is a generator of the $p$ prime ring, but I never took an abstract algebra class, so this is a bit over my head. I have this:

```
uint64_t primeHash(uint64_t const& i, uint64_t const& p)
{
    uint64_t g = 4294967311; // first prime after sqrt(p_max)
    for (unsigned int _ = 0; _ < i; ++_)
        g *= g;

    return g % p;
}

```

and I am thinking I would set `p` to N, which would be `p = 100`, but `p` is then not prime and the first 3 numbers are not unique:

```
i: 1 gen: 128849019105         g^i mod p: 5
i: 2 gen: 57982058546625       g^i mod p: 25
i: 3 gen: 5870683425282890625  g^i mod p: 25

```

I am all mixed up. Where am I going wrong with my understanding? How do I bound my outputs to 1 to N (here 100) ?

# Answer
> 0 votes
Look for “linear congruential random number generator”. If you take a random number generator with range 0 \<= r \< n that’s basically what you want. And it’s quite fast.

---
Tags: hash, algebra
---


title: $NL$ Leaf languages and $PSPACE$

text:
# Question
Title: $NL$ Leaf languages and $PSPACE$
I am reading Papadimitriou's *Computational Complexity* and got stuck on part d) of the following exercise (pg. 505)

> 20.2.14 A panorama of complexity classes. ... A language $L \subseteq \\{0, 1\\}^\*$ will be called a leaf language. Let A and R be two disjoint leaf languages (the accepting and rejecting leaf language, respectively). Now, any two such languages define a complexity class: Let C\[A, R\] be the class of all languages L such that there is a (standardized) nondeterministic Turing machine N with the following property: $x \in L$ if and only if $N (x) \in A,$ and $x \notin L$ if and only if $N(x) \in R.$ ... Show that, if $A, R \in NL,$ then $C\[A, R\] \subseteq PSPACE.$

How does one show this? I thought there'd be a way to use the result $AP = PSPACE$ directly but I can't see how.

# Answer
> 1 votes
You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the input, and $p(n)$ is upper bounded by a polynomial. Moreover, each non-deterministic choice is labelled as either $0$ or $1$, which induces an order on the computation paths and hence on the leaves of the computation tree (the $\ell$-th computation path corresponds to the non-deterministic choices given by the binary representation of $\ell$). Each of the leaves is also labelled with either $0$ or $1$ (e.g., for reject/accept). The output $N(x)$ of the execution of $N$ on $x$ is the binary string in $\\{0,1\\}^{p(n)}$ that corresponds the labels of the leaves, in the order discussed above.

Now we can actually tackle the exercise. Since $A$ and $R$ are in $NL$, there must be some non-determistic Turing machines $T\_A, T\_B$ that decide $A$ and $B$, respectively, and use space $O(\log n)$.

Given a language $L \in C\[A,R\]$, we can show that $L \in \mathsf{PSPACE}$ by providing a Turing machine $T^\*$ that takes an input $x$ and decides whether $x \in L$ using at most polynomial amount of space.

The Turing machine $T^\*$ first computes the number of steps $p(|x|)$ taken by $N(x)$ (we can simply simulate one computation path of $N(x)$). Then $T^\*$ simulates two parallel execution of $T\_A$ and $T\_B$ on the string $y=N(x)$. Since we cannot explicitly generate $y$ (which has length $2^{p(n)}$), we also "simulate" the views that $T\_A$ and $T\_B$ have over the contents of their tape. Whenever $T\_A$ or $T\_B$ want to write to a location $\ell$ of their simulated tape, we store the index $\ell$ and the written symbol (possibly replacing the previous symbol stored in $\ell$) in the tape of $T^\*$. Whenever $T\_A$ or $T\_B$ want to read a location $\ell$ of their simulated tape, we first check if $\ell$ was previously written to. If that's the case we answer with the symbol we previously stored. If $\ell$ was never written to, then either we return the blank tape symbol (if $\ell \> 2^{p(n)}$) or we return the $\ell$-th symbol of $y$ (when $\ell \le 2^{p(n)}$). To compute the $\ell$-th symbol of $y$ we can simply simulate the $\ell$-th computaton path of $N(x)$.

Notice that the size of the (simulated) input to the simulated versions of $T\_A$ and $T\_B$ is $|y| = 2^{p(n)}$ yet, since $T\_A$ and $T\_B$ use logarithmic space, there are at most $O(\log 2^{p(n)}) = O(p(n))$ distinct locations that are written to (which $T^\*$ needs to keep track of).

Eventually, one of $T\_A(N(x))$ and $T\_B(N(x))$ must accept. In the former case $T^\*$ also accepts, while in the latter case $T^\*$ rejects.

---
Tags: complexity-theory, time-complexity, turing-machines, space-complexity, complexity-classes
---


title: Contradiction via pumping lemma

text:
# Question
Title: Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much more simple but struggling a bit more when it comes to having two conditions as such. Any help would be appreciated

# Answer
> 1 votes
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $w = cb^{4+p}c^{7+p} \in L$. By the pumping lemma, $w$ can be written as $xyz$ with $|xy| \le p$ and non-empty $y$ such that $xy^iz \in L$ for all $i \ge 0$.

By our choice of $w$ either $y = cb^k$ for some non-negative $k \< p$ or $y=b^k$ for some positive $k$. In the former case $x=\varepsilon$ and $xy^0z = z \not\in L$ (to see this, notice that $z$ starts with neither $c$ nor $d$). In the latter case $xy^0z = cb^{4+p-k}y^{7+p} \not\in L$.

Since we reach a contradiction in both cases, we conclude that $L$ cannot be regular.

Alternatively (as per you comment) you can "pump" $w$ as follows. In the former case, $xy^2z$ starts with $cb^kcb^k$, hence $xy^2z \not\in L$. In the latter case $xy^2b = cb^{4+p+k}y^{7+p} \not \in L$ (since $k \ge 1$).

# Answer
> 0 votes
Assume you parsed c b^(m+4) for some m. Show that different m must give different states.

You are in a state where c^(m+7) leads to an accepting state. After parsing c b^(m’+4) for m’ ≠ m the same input does not lead to an accepting state, so you are in a different state. Since there are infinitely many different m a *finite* state machine cannot parse the language.

---
Tags: formal-languages, regular-languages, automata, pumping-lemma
---


# Question
Title: If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine
I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf. Here is the screenshot of the construction of probabilistic Turing machine RP. (https://i.stack.imgur.com/76pyK.png)

The idea of proof is to show that if 3SAT $\in$ BPP, then 3SAT $\in$ RP. I understand the construction of the probabilistic Turing machine for RP, denoted by N. I know If $x \notin 3SAT$, then N must reject x. However, I am confused about the proof of the case where $x \in 3SAT$ (i.e. If $x \in 3SAT$, then P(N accepts x) $\ge$ $\frac{1}{2}$.). Can anyone give me some proof or comments of this case? Thank you!

# Answer
> 1 votes
The idea is to use the self-reducibility of SAT to construct a search-to-decision reduction.

Suppose that we have in our disposal an oracle that solves SAT, and we wish to use it to find a satisfying assignment to a given satisfiable CNF on variables $x\_1,\dots,x\_n$. We use the following algorithm:

* Substitute $x\_1 = \mathsf{True}$, and check whether the CNF is still satisfiable. If so, set $x\_1 = \mathsf{True}$, and otherwise, set $x\_1 = \mathsf{False}$. In both cases, substitute the value of $x\_1$ into the CNF.
* Uncover the values of $x\_2,\dots,x\_n$ in an identical fashion.

This algorithm makes $n$ calls to the SAT oracle, and finds one of the satisfying assignments (indeed, the smallest one, under the correct order).

In your problem, you are not given an oracle to SAT, but rather a BPP algorithm. Nevertheless, you can use the same reduction. You can tune the BPP algorithm so that the error probability is at most $1/2n$ (you do this by running the given algorithm $O(\log n)$ times and taking a majority vote). You assume that the input CNF is satisfiable, and under this assumption, run the algorithm above to obtain a purported satisfying assignment. If the claimed satisfying assignment satisfies the CNF, then the CNF is obviously satisfiable, and otherwise, you declare it to be unsatisfiable.

Why does this work? You only answer "satisfiable" if the CNF is indeed satisfiable. Conversely, if the CNF is satisfiable, then the probability that any of the "oracle" calls in the algorithm fails is (in total) at most $n/2n = 1/2$, and so with probability at least $1/2$, the algorithm will find a satisfying assignment, and so will answer "satisfiable".

---
Tags: complexity-theory, turing-machines, 3-sat
---


# Question
Title: Counting chords intersections in a circle
The problem is:

Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ intersections). What is the complexity of this problem as a function of n?

The solution algorithm is given in this paper. $S$ is like an order statistic tree right? I don't understand why the author put $S\leftarrow S - \\{E\_{j}\\}$ outside $else$. Why you would want to remove $\\{E\_{j}\\}$ at the end of every loop?

$i\leftarrow 1 \\ intersections \leftarrow 0\\ S\leftarrow \phi\\ while(i\leqslant2n)\left \\{\\ \qquad j \leftarrow \sigma \_{i} \\ \qquad if(seen\_{j}=FALSE)\left \\{/\*open\ an\ interval\ for\ j\*/\\ \qquad\qquad seen\_{j}\leftarrow TRUE\\ \qquad\qquad E\_{j}\leftarrow i\\ \qquad\qquad S\leftarrow S\ \cup\ \\{i\\}\\ \qquad\right \\}else\left\\{/\*close\ the\ interval\ for\ j\ and\ count\ intersections\*/\\ \qquad\qquad intersections\leftarrow intersections \ +\ |\\{x|x\in S\ \wedge x\>E\_{j}\\}|\\ \qquad\right\\}\\ \qquad i \leftarrow i+1\\ \qquad S\leftarrow S-\\{E\_{j}\\}\\ \right \\} $

# Answer
There is some printing mistake it seems, the expression S←S−{Ej} must be inside `else` block otherwise `S` will always be empty.Since we are adding the elements in `if` block and removing it at last making no sense. The correct pseudo code looks like below:

$i\leftarrow 1 \\ intersections \leftarrow 0\\ S\leftarrow \phi\\ while(i\leqslant2n)\left \\{\\ \qquad j \leftarrow \sigma \_{i} \\ \qquad if(seen\_{j}=FALSE)\left \\{/\*open\ an\ interval\ for\ j\*/\\ \qquad\qquad seen\_{j}\leftarrow TRUE\\ \qquad\qquad E\_{j}\leftarrow i\\ \qquad\qquad S\leftarrow S\ \cup\ \\{i\\}\\ \qquad\right \\}else\left\\{/\*close\ the\ interval\ for\ j\ and\ count\ intersections\*/\\ \qquad\qquad intersections\leftarrow intersections \ +\ |\\{x|x\in S\ \wedge x\>E\_{j}\\}|\\ \qquad\qquad S\leftarrow S-\\{E\_{j}\\}\\ \qquad\right\\}\\ \qquad i \leftarrow i+1\\ \\ \right \\} $
> 0 votes

---
Tags: algorithms, graphs, combinatorics, balanced-search-trees
---


title: Confusion in 2's complement of 00000000

text:
# Question
Title: Confusion in 2's complement of 00000000
I'm solving the end of the chapter problems of Morris Mano's Digital Design (4th Edition, if that's relevant). In one of the problems, it is asked to simply find the 1's and 2's complement of 00000000. It's 1's complement would be 11111111. Now, for 2's complement, adding 1 to will give 100000000. But in the answer key, the answer is 00000000.

I know that if i'm working with a hardware that is only capable of handling 8 bits, the 1 will not be stored. But, in theory, the 2's complement of 00000000 should be 100000000, right? Or is there something i missed? In the question there was no mention of hardware limitations, or even something like "use only 8 bits".

# Answer
> 2 votes
You have 00000000 as the number, it implies how many bits are used. The 1 at the front comes from carry bit, but two complements does not extend number of bits used, so the answer is 00000000, as the carry is discarded because it doesn't fit given space.

You can check it (to convince yourself) by converting code back from 2's complement to decimal. 00000000 yields 0, while 100000000 gives -256.

# Answer
> -1 votes
for two's complement, complement bits and add 1(after addition discard carry), so complement of 00000000=11111111, now add 1, 100000000, discard last carry bit (write result in 8 bits again), we get 00000000. notice that in 2's complement notation, number 0 has one and only 1 representation, while in 1's complement (as you got in your result), has 2 representations, because -0=0, that's why 2's complement system for signed numbers are preferable in computer systems, computerphile has good video about that, I suggest watching it, you will get general understanding of different ways of handling signed numbers in binary: https://www.youtube.com/watch?v=lKTsv6iVxV4

---
Tags: number-theory, number-formats, binary
---


# Question
Title: how to prove correctness of this BFS algorithm?
Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that it works just fine, but I don't really know how to prove its correctness properly. Here is the pseudo-code:

```
Let s be the root
set parent[s]=s and parent[v]=null for all other v
create queue q ;
enqueue(s,q);
cycle=false;
while (!isEmpty(q) && !cycle) {
 u=front(q);
 for every edge (u,v) incident to u {
 if (parent[v]==null){
  parent[v]=u;
  enqueue(v);
 }
 else if (parent[u]!=v){
   cycle=true;
   keep the edge (u,v)
 }
dequeue(q);
if (cycle){
 print edge (u,v)
 while (parent[u]!=parent[v])&& (parent[v]!=u)&&(parent[u]!=v){
        print edge (u,parent[u]) and  edge (v,parent[v])
        u=parent[u];
        v=parent[v];
    }
    if (parent[u]==parent[v])
        print edge (u,parent[u]) and edge (v,parent[v])
    else
        print edge (u,v)
}
/**************************************************/
/**************************************************/

```

I've been working on the proof but i can't get through it. First i want to prove that if G contains a cycle then the algorithm does detect it. My idea is the following: Let s be the root of the bfs. We know that G contains a cycle, so there is a node such that there are two different paths from s to such a node. Let u be the first node that satisfies this. Since that BFS visits all the nodes, and explores each edge once, and also marks as visited all nodes that were visited, it will reach a step in which it is about to visit the node u for the second time and then it finds the cycle.

Then I want to prove that in the afirmative case, the edges that it prints does forms a cycle, but i'm really stuck with this.

# Answer
> 2 votes
I believe your problem has been resolved as this is an old question, but here is a solution just to add up to your knowledge.

## Proof of Correctness of BFS

First, two kinds of annoying lemmas. These help us formalize what’s going on as the algorithm is running.

**Lemma 1.** At end of BFS, for all $v ∈ V$, $\newcommand{\dist}{\operatorname{dist}}\dist(v)$ is at least the distance from $s$ to $v$.

**Proof.** Will show by induction that at each iteration of loop, this holds for all $v$.

Base Case: 0th iteration.

Inductive Hypothesis: Assume true for the $k$th iteration.

Inductive Case: Consider the vertex $v$ removed from queue on $(k + 1)$st iteration.

* Only changes $\dist(u)$ for a few vertices, and only if $u$ is adjacent to $v$.
* For vertices not changed, use IH.
* Otherwise,
∗ distance from $s$ to $v$
∗ ≤ distance from $s$ to $u + 1$
∗ ≤ $\dist(u)+1$
∗ = $\dist(v)$.

**Lemma 2.** For any $k$, let $(v\_1, \dots , v\_r)$ be the elements of the queue at iteration $k$. At this iteration,

1. $\dist(v\_1) ≥ \dist(v\_r) − 1$
2. For any $i \< j$, $\dist(v\_i) \< \dist(v\_j)$

Proof. Induction

Base Case: Initially, queue is empty.

Inductive Hypothesis: Assume true for $k$th iteration.

Inductive Case: Consider $(k + 1)$st iteration.

* Remove $v\_1$ from queue. New front is $v\_2$.
* Enqueue neighbors of $v\_1$.
∗ Let $u$ be a neighbor.
$\dist(u)$ is set to $\dist(v\_1) + 1 ≥ \dist(v\_r) − 1 + 1 = \dist(v\_r)$, so 2. still holds.
$\dist(v\_2) ≥ \dist(v\_1) = \dist(u) − 1$, so 1. still holds.

**Corollary:** Let $v\_k$ be the $k$th vertex to have $\dist(v)$ set. $\dist(v\_k)$ is increasing in $k$.

Finally, the proof of correctness. At the termination of BFS, if BFS explores $v$, then $\dist(v)$ is the distance from $s$ to $v$.

Proof by contradiction.

* Assume there’s some vertex with $\dist()$ not equal to the distance from $s$.
* Let $v$ be such a vertex which is the smallest distance from $s$.
* Let $u$ be its predecessor on shortest path from $v$ to $u$.
* By lemma 1, $\dist(v) \> $ distance from $s$ to $v$
* = (distance from $s$ to $u$)$ + 1 = \dist(u) + 1$
* Consider when $u$ was dequeued. We’ll contradict the above chain of inequalities in any of the three cases:
– If $v$ wasn’t explored yet, $v$ would have been enqueued with $\dist(v)=\dist(u)+1$. Contradiction to above inequalities.
– If $v$ is on the queue, then $\operatorname{parent}(v)$ has lower $\dist$ than $u$ does, by corollary to lemma 2. Then $\dist(v) = \dist(\operatorname{parent}(v)) + 1 ≤ \dist(u) + 1$, again contradicting the inequalities.
– If v has already been dequeued, then $\dist(v) ≤ \dist(u)$. Contradiction again.

Watch the video for clear understanding, along with visual description

# Answer
> 0 votes
Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle.

Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible distance to $s$. Any two vertices in $S$ can not belong to the same cycle, since then they will form a cycle with a vertex with a smaller depth in the BFS-tree, which contradicts the assumption that they are closest possible to $s$. All these vertices belong to the same level of the BFS-tree since they have the same distance to $s$. The BFS-tree branches at each of them to at least two branches. Sice they all belong to cycles in the graph, there must exist an edge between two branches from the subtree rooted at one of them. This edge has its endpoints between two nodes on the same level in the tree, since else, one of them could have been visited by the other and get a smaller depth. When visiting this edge, our algorithm detects a cycle. The Cycle is hence this edge along with both paths in the BFS-tree from a vertex $v \in S$, to the endpoints of this edge. We output exactly these edges, where we start by printing this edge and backtrack on both branches until we reach back the vertex $v$ .

# Answer
> 0 votes
Theorem (Correctness of BFS)

* Let G=(V,E) be a directed/undirected graph and suppose BFS is run on it from a given source vertex s∈V.
* upon termination of the algorithm we should have d\[v\]=δ(s,v) for all v∈V, where δ(s,v) is the shortest path from s to v. (**Note**: the main difference between d and δ is that d is distance what the algorithm has calculated and δ is the distance of the actual shortest path from s to v.). This is our **Claim**

**Suppose** (the major assumption that drives this correctness),

upon termination, there exists a vertex x such that d\[x\]≠ δ(s,x).

Here we use the **Lemma**: upon termination, for each vertex v∈V, the value d\[v\] computed by BFS satisfies d\[v\] $\geqq$ $\delta$ (s,v)

Therefre by Lemma, d\[x\] $\geqq$ δ(s,x).

let there exist many such x's, where d\[x\] $\gt$ δ(s,x) \[d\[x\]≠ δ(s,x)\].

Among such vertices in G, we choose a vertex v in G which the closest vertex to s.

Observe that

1. v $\neq$ s since d\[s\]=0=$\delta$(s,s)
2. v must be reachable from s.

Suppose , v is not reachable from s, then $\delta$(s,v)=$\infty$, by the property of Lemma d\[v\]\>$\delta$(s,v)=$\infty$ which is impossible.

Suppose v is reachable from s and v$\neq$s, there exists a non-trivial shortest path P from s to v. Let u be the vertex immediately preceding v on P.

$\delta$(s,v)=$\delta$(s,u) + 1

Therefore, $\delta$(s,u)\<$\delta$(s,v). Then by the choice of v, d\[u\]=$\delta$(s,u). This implies

d\[v\]\> $\delta$(s,v) = $\delta$(s,u)+1 = d\[u\]+1

**d\[v\]\>d\[u\]+1** =\> (1)

Now, Consider the time BFS chooses to dequeue the vertex u from Q. At this time the vertex v is either white, grey or black (undiscovered, discovered or discovered and adjacent vertices added to queue)

\[**Lemma**: Suppose x and y are enqueued in BFS and x is enqueued before y, then d\[x\]\<=d\[y\] at the time y is enqueued\]

***Case 1***: The vertex v is white

Then, d\[v\]=d\[u\]+1 which is contradiction to (1).

***Case 2***: The vertex v is grey

This means v is already discovered by some other vertex w$\in$V which was dequeued before u,

d\[v\]=d\[w\]+1

d\[w\]\<=d\[u\]

Thus, d\[v\]\<=d\[u\]+1 which is a contradiction to (1)

***Case 3***: the colour of v is black

This means v was discovered before u or v was dequeued before u. Therefore d\[v\]\<=d\[u\], which is a contradiction.

In all the above three cases, we observe that our assumption d\[v\]\>$\delta$(s,v) is **wrong**. Thus, no such vertex exits and for all vertex v, d\[v\]=$\delta$(s,v)

---
Tags: graphs, algorithm-analysis, graph-traversal, correctness-proof
---


# Question
Title: Can you compute a majority function of n-bits using an O(n) size circuit?
Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like?

I have a feeling it has to do with a Full Adder, but I am unsure.

# Answer
Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.

At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits. Hence the number of gates on the generic $i$-th level is $O(i \cdot \frac{n}{2^i})$ and the overall number of gates is $O\left( \sum\_{i=1}^{\log n} i \frac{n}{2^i} \right) = O(n)$.

Once you have found the sum of the inputs, simply compare it with $\lfloor n/2 \rfloor +1$.
> 2 votes

---
Tags: complexity-theory, circuits
---


title: Trying to implement BFS and I am stuck

text:
# Question
Title: Trying to implement BFS and I am stuck
I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue.

On the one hand the data structure is a tree with each node having n children so in order to tranverse every node of the tree you need recursion

On the other hand though in recursive algorithms the return value is each time for a path from root to a leaf and we dont want this, we want breadth first search ,we want to access in 2 nodes of the same level in the tree before we keep on checking the rest of the tree so I am in a endless loop as you can see.

# Answer
> 1 votes
The pseudo code for DFS using recursion would look something like this:

```
def DFS(node):
    if node is visited:
        return
    mark node as visited
    for each child in node:
        DFS(child)

```

This recursive method works because every time we call the function it goes as deep as it can into the tree before returning. When it returns, it goes to the next child and repeats the process. This ensures that we are going as deep as possible, exploring one branch fully before moving on to the next one.

If you want to avoid recursion, you can also implement DFS using a stack data structure. For example:

```
public void dfsWithoutRecursion(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node current = stack.pop();
        System.out.println(current.value);
        for (Node child : current.children) {
            stack.push(child);
        }
    }
}

```

Here we start by pushing the root node onto the stack. Then we enter a loop that continues as long as the stack is not empty. Inside the loop we pop the top node from the stack and print its value. Then we push all of its children onto the stack. This process continues until the stack is empty which means we've visited every node in the tree.

You mentioned that you wish to implement BFS instead of DFS. The code for BFS can be very similar, simply replace the Stack above with a Queue.

# Answer
> 0 votes
Every tree is also a graph. Therefore, you can use breadth-first search directly on a tree. It doesn't require recursion; you can use a queue and a loop. As soon as you encounter a node that satisfies the condition, you stop and return immediately, without continuing the search.

---
Tags: algorithms, trees, recursion, artificial-intelligence, depth-first-search
---


# Question
Title: Trouble Understanding Yao's "Basic Model" for Hashing
I am trying to understand the probing model proposed by Yao in the paper "Should Tables Be Sorted?". Yao suggests a "Basic Model" (in the section appropriately titled "Basic Model") but there seems to be some disconnect in the way I remember hash tables and the way it is presented here.

Consider sorted table vs cyclic table example Yao gives. My thought process was that the $\\{1, 2\\}$, $\\{2, 3\\}$ and $\\{1, 3\\}$ were key-value pairs. But this cannot be the case. In the cyclic model ${1, 3}$ results in what I believe is a key of $3$ and value of $1$.

Another problem I have is I do not understand what exactly is meant by a "query". I would have assumed that both the sorted and cyclic results in a look up of time of 1, but Yao states the sorted requires $2$ queries. For if one looks at the Sparknotes link above, the hash table will look something like this:

$$1 \to 2, 3$$ $$2 \to 3$$

So, making the query $1$ will give $2$ immediately (and $3$ will require two look ups). Similarly, for cyclic the look up table looks like

$$1 \to 2$$ $$2 \to 3$$ $$3 \to 1$$

and the query $1$ would give $2$ immediately as well.

I suppose in principle, for the sorted example, it could depend how $3$ is inserted, so in the worst case, the sorted table could look like:

$$1 \to 3, 2$$ $$2 \to 3$$

in which case $2$ queries would be needed for $2$. This then goes back to what exactly is query in this context? Sorry if my understanding is completely wrong, any guidance is appreciated.

# Answer
Following @Tassle's comment here is what I have gathered since more careful reading:

The $\\{1,3\\}$, $\\{2,3\\}$, etc. are not key value pairs they are values to be inserted into a table. The boxed values are potential arrangements for a table given the corresponding insertion.

For the example Yao considers for $n=2, m=3$ there are two separate query strategies (one that queries the first entry first, the other that queries the second entry first). For the sorted case, the worst possible number of queries needed to determine if two is in the table is two.

This is because if you query the first entry and see a $1$ then you must query the second entry to determine if a $3$ was inserted or a $2$ was inserted. If you query the second entry first, and you receive a $3$ you must make a further query to determine whether $2$ or $1$ was the first entry. This problem does not exist for the cyclic variation. For instance, if one queries a $3$ choosing the first entry, then it is immediately known that $1$ is the second entry. A similar argument can be seen for the other combinations.
> 0 votes

---
Tags: hash-tables
---