# Question
Title: Example of progress and preservation failing in a commonly used programming language like Java
I am wondering if my solution is correct or I am on the right track. I have searched online and found a paper about Java type system being unsound but that doesn't really answer the progress and preservation issue.

Question:

Give a non-obvious problem in the language definition that would prevent “progress” from being true.

Give a non-obvious problem in the language definition that would prevent “preservation” from being true.

My attempt:

Progress: If $· \vdash e : τ$ then either $e \to e'$ for some $e'$ or $e$ is a value.

```
class A {
 String name;
 String getName() { return this.name; };
}

A a = null;
String b = a.getName(); // we don't get to another evaluation step nor we get to a value

```

I think this is correct because the expression doesn't evaluate to another expression nor do we get a value ... and the program crashes.

Preservation: If $· \vdash e : τ$ and $e \to e'$ then $· \vdash e' : τ$

```
class A {
 String name;
 String getName() { return (String)((Object)12); };
}

A a = new A();
String b = a.getName(); // after evaluation of RHS, the assignment is not really valid

```

This one I am not so confident. The up-cast to object and down-cast to integer cause the assignment to not type check.

# Answer
> 2 votes
The definitions of progress and preservation used in the question only really make sense in the context of term-rewriting, but there is no canonical definition of Java's semantics in that form. It may be possible to define Java's semantics in such a way that your answers are correct, but it is possible to define Java's semantics in such a way that they aren't, because "throwing an exception" could still count as progress. To expand on that, the Java Language Specification defines what it means for an expression or statement to "complete normally" by producing a value (or no value for a statement), or to "complete abruptly" with some control-flow effect.

If we define Java as a term-rewriting system where "value" means what we traditionally call a value, then your first answer seems correct, but your second answer doesn't. Specifically:

* The term `(String)((Object) 12)` has type `String`,
* After one evaluation step the term becomes `(String)(new Integer(12))`, which still has type `String`,
* There is no further evaluation step; the program next throws a `ClassCastException`, and throwing an exception means the expression does not produce a value in the traditional sense.

For preservation to fail, there must be progress to some term which does not have the correct type. At this point in your example there is no further progress, so there is no failure of preservation.

---

However, I think this definition of Java's semantics is flawed, because it does not account for statements such as `return 5;`, `break;` or `throw new Exception();` which "complete abruptly". If Java must be defined as a term-rewriting system (which sounds like a monumental undertaking), it should be done in a different way, more in the spirit of the Java Language Specification.

* Let the "values" in our system be $\mathrm{Normal}(v)$ where $v$ is a value in the traditional sense (or some unit value, for statements which complete normally without producing values in the traditional sense), and $\mathrm{Abrupt}(e)$ where $e$ is a control-flow effect, such as returning, breaking, or throwing an exception.
* $\mathrm{Normal}(v)$ has type $T$ if $v: T$ in the traditional sense, and $\mathrm{Abrupt}(e)$ has type $\bot$, meaning it has type $T$ for all $T$.

Then, your examples each evaluate to $\mathrm{Abrupt}(\dots)$, specifically the first throws a `NullPointerException` and the second throws a `ClassCastException`. Each of these is a "value" (progress), and each has type $\bot$ implying they also have type `String`, as required (preservation).

With this more robust definition of Java's semantics, though, we can still give examples where both progress and preservation fail:

* Progress fails for the statement `while(true) {}`. There is no evaluation step to take for this statement, but it is not a "value". (Technically, this depends on how the semantics have been defined; We could add a rule saying that `while(true) {}` is rewritten as `while(true) {}` in which case there is technically "progress" because some rule is applicable, but the program obviously diverges.)
* Preservation fails precisely if Java's type system is unsound; this is the *definition* of an unsound type system. You have found a paper discussing this, so I won't go into further detail.

# Answer
> 2 votes
Progress and preservation are properties of a semantics, not of a language. It's possible to define a programming language in different ways which do not necessarily all have the same properties. Both are properties of semantics defined by an evaluation relation (either a partial evaluation as in small-step semantics or a complete evaluation as in big-step semantics).

The point of progress is to ensure that the semantics is well-defined on all programs that are considered valid. It says that any valid program evaluates to something. The opposite of progress is that there are valid programs that do not have a well-defined semantics: depending on the language, this can mean:

* that the semantics is not precise enough to fully describe the language;
* or that some programs encounter a fatal error (which could actually be modelled in the semantics by defining “fatal error” as a special “value” $\bot$);
* or that some programs have undefined behavior: programs for which the semantics does not specify the behavior are unpredictable and can do anything — which is really bad.

The progress property only addresses valid programs. It's pointless to try to give a semantics for programs that the compiler would reject. Typing is a convenient way of defining valid programs: well-typed programs are valid, and ill-typed programs are invalid. The compiler rejects ill-typed programs, and this way all well-typed programs are valid. In this perspective, preservation is mostly useful for small-step semantics, where the semantics of a program is a sequence of programs (or program states) obtained by successive rewriting. Preservation says that if you evaluate a valid programs, all the intermediate evaluation steps yield valid programs. And progress says that at each step, there is a way to continue evaluating.

Java does not have undefined behavior. (At least not until you get into dark corners such as linking with programs written in other languages.) Ill-typed programs like `"a" * "b"` or calling a method that doesn't exist have well-defined behavior: they throw an exception which is documented in the language definition. You can express the language definition with a small-step semantics where the intermediate states include the state of the whole memory. This semantics does have the progress and preservation properties. The “trick” is that the type system in this semantics is not Java's full type system: it's a type system where all objects have the same type, since it's always possible to attempt a cast at runtime. (In earlier versions of Java, there were also built-in types like `int` that could not be cast to objects or vice versa. I believe that this is no longer the case in more recent versions.)

If you take Java's runtime types into account, evaluation does not preserve types. You might certainly want to define a semantics that takes all types into account and where evaluation does preserve types. This can let you guarantee that programs don't throw certain exceptions. It certainly is useful to know that your program won't throw a `ClassCastException` or a `NullPointerException`. But then your semantics will not cover the full language. Catching a `ClassCastException` is often bad practice, but it's well-defined and it is occasionally the right thing to do.

---
Tags: programming-languages, lambda-calculus
---


# Question
Title: Are there any updates to CYK parsing that handles epsilon rules in arbitrary nonterminals?
I am a researcher starting to work on the field of parsing and recognition of languages.

As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in CNF. This however, is restrictive, as it forces the grammar to be restructured to remove $\epsilon$ rules from arbitrary nonterminals (allowing it only on the start symbol). The problem with this is that, when transforming the CYK recognizer to a CYK parser, a naive parse tree generation algorithm simply extracting the parse tree from the chart produces a parse tree that has a different structure from the original grammar before conversion to CNF. The main difference is that such a parse forest is finite in size, with no possibility of infinite recursion due to epsilon rules.

Hence, one may ask; can CYK parser be modified such that the restriction of CNF format on the grammar be relaxed, such that we can use arbitrary context-free grammars? It is fairly trivial to modify the CYK such that the other restrictions such as (1) either one terminal symbol or (2) two nonterminal symbols on a production rule is relaxed. However, arbitrary epsilons on rules is slightly harder because adding them likely changes the algorithm structure a little bit (one needs to pre-compute nullable nonterminals, handle nullable nonterminals in subparse checks etc.).

So, my question is, are there any updates to CYK that allows epsilon rule to be used as production rule for arbitrary nonterminals (not just the start symbol)?

# Answer
If you want to build a representation of all parse trees, I think a GLR (Tomita) parser is a better fit than something based on CYK. A GLR parser outputs a compact representation of the set of all parse trees, and does not require transformation to CNF.
> 1 votes

---
Tags: context-free, parsers
---


title: What is a cache write miss?

text:
# Question
Title: What is a cache write miss?
I'm reading *Computer Organization and Design MIPS Edition 5th Edition The Hardware/Software Interface* on how memory cache works. I came across the following paragraph on page 393;

> The other key aspect of writes is what occurs on a write miss. We first fetch the words of the block from memory. After the block is fetched and placed into the cache, we can overwrite the word that caused the miss into the cache block. We also write the word to main memory using the full address.

I understand what a cache read miss is i.e. when the required word isn't present in the cache, but I'm having trouble understanding what a write miss is(how can we miss to write data?) and hence the subsequent paragraphs.

# Answer
My understanding is that a write-miss occurs when we want to write data to a location in main memory whose data is not currently in its corresponding cache block.

This is similar to a read miss: if the cache block that a memory location is mapped to does not contain the data of that memory location (indicated by differing tags), then some other memory location also mapped to that same cache block is currently present, and a miss occurs.

Similarly, we "miss" on a write if the memory location we want to write to isn't currently "in" its corresponding cache block, but rather, some other memory location's data currently occupies it.

The important question that follows a write-miss is "do we update the cache block corresponding to the memory location we just updated with that new data, or leave the old?" Perhaps the memory-location's data already occupying that cache block is more useful or being used more frequently than what we just wrote.
> 5 votes

# Answer
There are several strategies for handling writes, most common are "write-thru" vs. "write-back" and "allocate on write" vs "non alloocate on write".

* When a write access hits the cache, either only the cache is updated, this is "write back", or the write operation is forwarded to main memory, this is "write thru". Write back is more efficient, but more complex as data can be more up-to-date in the cache than in main memory, so coherency must be handled carefully.
* When a write access misses the cache, either the write is directly forwarded to main memory, this is "don't allocate on write", or the cache line is read before doing the write access, this is "allocate on write", this is what is described in your book. Depending on system architecture, one mode can be more efficient than the other. Write-back tend to be associated with "allocate on write" though.

(When there are several levels of caches, L2,L3,L4...), each level can have different strategies on allocate/no allocate, write-thru/write-back, inclusive/exclusive, etc.)
> 2 votes

# Answer
This is an old question, but I don't think any of the other answers quite explain what the text is saying.

A word is typically smaller than a cache line; a system might, for example, have words that are 8 bytes in size, but L1 cache lines that are 64 bytes in size. A write of a word means overwriting some portion of that cache line, not the whole cache line. Therefore, to perform such a write, you would typically need to load the *rest* of the 64-byte aligned line into cache, so that just the modified portion can be overwritten.

Another issue that the text doesn't mention, but is important in practice, is cache coherency.

On many multiprocessing architectures, memory semantics demands that every CPU sees every write occur in the same order. Those that have more relaxed semantics still need *some* kind of memory sequencing otherwise CPUs can't synchronise.

The upshot is that a CPU often must gain some kind of exclusive write access to a cache line before it is allowed to write. So even if a CPU has a copy of the cache line in its L1 cache, it may need to acquire that access, which is also a kind of write miss.
> 2 votes

# Answer
Reading data is easy to understand: *cache missed, then read it from memory.* But writing data add more complexity: *write the data to both cache(s) and memory or only cache(s)?*

## Write after missed

If the answer of ❸ and ❹ is *yes*, then you are using **Write-through**, else if the answer of ❸ is *no* but ❹ is *yes*, then you are using **Write-back**.

Why call it write-back? It is because the write to the backing store(`cache2`) is postponed until the modified content is about to be replaced by another cache block.

The idea is critical, please think it again and make sure you are understood.

> It will write-back to `cache2` when original block in `cache1` is replaced by another cache block.

### What's the side-effect after replaced by another cache block?

The answer is: **write missed**.

## How to handle write-missed?

As you can see, after the replacement(❶) (if you are using write-back strategy than it will trigger write-back(❷)) next time processor try to write new data(`k1 -> x2`), it realized that the data is *dirty* and start making decision to handle this situation.

There have two main strategy to handle this: **write-allocate** and **no-write allocate** which is answered by @TEMLIB.

---

As you can see, when implement the write-back strategy, there is *stale* value in the `cache2`, how to avoid this situation?

As @Pseudonym answered, communication protocols between the cache managers which keep the data consistent are known as coherency protocols.
> 2 votes

# Answer
When system copies a data from the lower level to cache, it also copies the memory location address. Therefore, each location in cache represents the location memory in the lower level of the memory hierarchy. When an instruction tries to write to the memory, it specifies the full address of the destination. You cannot write to the cache the data destinated to the memory address that is not related to any location in cache. This is when the write miss happens.
> 0 votes

# Answer
From my understanding, there are two things to consider while writing a cache : one is cache index which is implicit and other is tag which is explicit. When we want to write to cache, we have a full memory address in which we want to write the block. Firstly, from the memory address we calculate the index of the cache. We go to that index and check the tag of that index. We also have to calculate tag from the memory address (in which the block should be written) along with cache index. If the calculated tag is not equal to the found tag on the cache index then a 'write miss' has occurred.
> 0 votes

# Answer
There are Two types of writes either to update exist track or to write a new track. For the new tracks not meant for Cache hit miss the cache hit miss is for updating existing tracks, So if the Track is existing in the Cache and the updated happened in the Cache That's mean a successful Write Hit. If the Track doesn't exist in the cache and it will be fetched from disk then updated in the cache that's mean Write miss.
> 0 votes

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


# Question
Title: Types and programming languages: strange term construction?
Pierce's *Types and Programming Languages* has the following definition of terms:

> $$S\_0=\emptyset$$ $$S\_{i+1} = \\{true,false,0\\} \cup \\{succ(t), pred(t),iszero(t)|t \in S\_i\\} \cup\\{if(t\_1)then (t\_2)else(t\_3) |t\_1,t\_2,t\_3\in S\_i\\}$$

So then that means this language has terms like $succ(false)$ and $if(succ(0))then(true)else(false)$, am I interpreting that correctly?

# Answer
> 2 votes
You're interpreting this correctly. $S\_1$ contains the constants, $S\_2$ contains the terms you can build using one application of if/else, the successor function, the predecessor function and the zero predicate with these constants. The language is the limit $S = \bigcup\_i S\_i$ which can be interpreted as allowing any number of applications of these constructions.

If you're confused about using $\mathtt{succ}\\;0$ as the condition in an if-statement then notice that it is still a term in the language but one that is 'meaningless'. See section 3.5 Evaluation for more on this and see 3.5.15 specifically for more on these terms.

# Answer
> 1 votes
By applying the definition,

$$S\_0=\emptyset\\ S\_1=\\{\text{true},\text{false},0\\}\\ S\_2=\\{\text{true},\text{false},0,\\ \text{succ}(\text{true}) , \text{pred}(\text{true}) , \text{iszero}(\text{true}) ,\\ \text{succ}(\text{false}) , \text{pred}(\text{false}) , \text{iszero}(\text{false}) ,\\ \text{succ}(0) , \text{pred}(0) , \text{iszero}(0) ,\\ \text{if }(\text{true})\text{ then }(\text{true})\text{ else }(\text{true}) ,\\ \text{if }(\text{true})\text{ then }(\text{true})\text{ else }(\text{false}) ,\\ \text{if }(\text{true})\text{ then }(\text{true})\text{ else }(0) ,\\ \text{if }(\text{true})\text{ then }(\text{false})\text{ else }(\text{true}) ,\\ \text{if }(\text{true})\text{ then }(\text{false})\text{ else }(\text{false}) ,\\ \text{if }(\text{true})\text{ then }(\text{false})\text{ else }(0) ,\\ \text{if }(\text{true})\text{ then }(0)\text{ else }(\text{true}) ,\\ \text{if }(\text{true})\text{ then }(0)\text{ else }(\text{false}) ,\\ \text{if }(\text{true})\text{ then }(0)\text{ else }(0) ,\\ \text{if }(\text{false})\text{ then }(\text{true})\text{ else }(\text{true}) ,\\ \text{if }(\text{false})\text{ then }(\text{true})\text{ else }(\text{false}) ,\\ \text{if }(\text{false})\text{ then }(\text{true})\text{ else }(0) ,\\ \text{if }(\text{false})\text{ then }(\text{false})\text{ else }(\text{true}) ,\\ \text{if }(\text{false})\text{ then }(\text{false})\text{ else }(\text{false}) ,\\ \text{if }(\text{false})\text{ then }(\text{false})\text{ else }(0) ,\\ \text{if }(\text{false})\text{ then }(0)\text{ else }(\text{true}) ,\\ \text{if }(\text{false})\text{ then }(0)\text{ else }(\text{false}) ,\\ \text{if }(\text{false})\text{ then }(0)\text{ else }(0) ,\\ \text{if }(0)\text{ then }(\text{true})\text{ else }(\text{true}) ,\\ \text{if }(0)\text{ then }(\text{true})\text{ else }(\text{false}) ,\\ \text{if }(0)\text{ then }(\text{true})\text{ else }(0) ,\\ \text{if }(0)\text{ then }(\text{false})\text{ else }(\text{true}) ,\\ \text{if }(0)\text{ then }(\text{false})\text{ else }(\text{false}) ,\\ \text{if }(0)\text{ then }(\text{false})\text{ else }(0) ,\\ \text{if }(0)\text{ then }(0)\text{ else }(\text{true}) ,\\ \text{if }(0)\text{ then }(0)\text{ else }(\text{false}) ,\\ \text{if }(0)\text{ then }(0)\text{ else }(0)\\} $$

The expansion of $S\_3$ is huge ($59475$ terms). That of $S\_4$ astronomical ($210379467994775$ terms).

---
Tags: programming-languages, recursion, type-theory, language-design, typing
---


title: Prove the NP-hardness of problem

text:
# Question
Title: Prove the NP-hardness of problem
Prove the $NP$-hardness of $CONNECTEDNESS$ \- the problem of counting over an oriented graph $G$ and two vertices $s$ and $t$ the number of subgraphs of $G$ in which from $s$ to $t$ can be traversed by an oriented path. Does the corresponding problem of recognition in $P$? If necessary, one can use the $NP$-hardness of the problem of calculating the permutation of a matrix.

I'm doing a problem-solving book for a foreign language problem book, and would appreciate your help:)

# Answer
> 0 votes
This problem is called $s$-$t$ $\texttt{NODE CONNECTEDNESS}$ and was proved to be $\\#\mathsf{P}$-complete by Valiant in 1979 in *The Complexity of Enumeration and Reliability Problems*.

As such, it is $\mathsf{NP}$-hard: if it could be solved in polynomial time, you could solve $\\#\texttt{SAT}$ in polynomial time, and then solve $\texttt{SAT}$ in polynomial time.

However, the corresponding decision problem, deciding if there exists a path from $s$ to $t$, is in $\mathsf{P}$ (in fact, it is even $\mathsf{NL}$-complete). That is not contradictory as there are other examples: for example, $\\#2\texttt{SAT}$ is $\\#\mathsf{P}$-complete, but its decision version is in $\mathsf{P}$.

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


# Question
Title: Difference between bare metal hypervisor and operating system
I'm currently studying virtualization and while looking at hypervisors I realized that bare metal hypervisors are quite similar to operating systems.

So while from an application standpoint they are different, can an operating system theoretically be viewed as bare metal hypervisor?

# Answer
> 23 votes
I think you're right to notice this strong connection. At a high level, there is a strong similarity between a hypervisor and a microkernel operating system.

There are also some differences. Hypervisors are specialized to supporting virtual machines. Conventional operating systems are specialized to supporting user-mode applications. For instance, conventional operating systems often include many device drivers, support for scheduling of user-mode tasks, and other functionality that isn't relevant or needed for hosting virtual machines. Hypervisors tend to allocate/manage/schedule resources at a coarser granularity and using less sophisticated scheduling/allocation schemes.

# Answer
> 16 votes
The term "operating system" is actually a fairly loose one, and many arguments can be had about its definition. For instance, is Linux (the kernel) an operating system, or do you need GNU/Linux (the kernel plus some minimum set of services), or even Debian GNU/Linux (a complete user-ready environment running on top of those)? Does the answer change if the architecture is radically different - a highly-layered microkernel architecture vs a non-time-sharing mainframe OS, for instance?

A clearer definition can be made for some of the *roles* that system software plays. For instance, a "supervisor" is responsible for "supervising" running processes, managing their access to memory, storage, and other resources.

A "hypervisor" is so called because it "supervises supervisors" - it performs the same role as a traditional "supervisor", but at an additional layer of abstraction. The facilities needed by a virtualized or paravirtualized OS are similar to, but not quite the same as, those needed by an application process in a multitasking OS. So it is reasonable to say that "a hypervisor is a specialised type of supervisor", but not "any supervisor is also a hypervisor".

A "bare-metal hypervisor" may also provide other facilities beyond this "supervisor of supervisors" definition, so you could loosely call it "an operating system for running operating systems". Again, that makes the hypervisor *a type of* operating system, but does not make other operating systems hypervisors.

# Answer
> 10 votes
If you wanted a definition of an "operating system" it could be something like: a system of software that runs on a machine and manages its resources, providing an environment for other software to run within.

(Actual software packages that are marketed as operating systems would almost invariably contain a lot of ancillary stuff that isn't strictly part of this role, in addition to parts that can be viewed as fitting the actual definition of the term "operating system")

In that sense a bare metal hypervisor is in fact an operating system, if we accept that "other software" running within an operating system can include virtual machines.

But I would rather say that bare metal hypervisors are a specific subcategory of operating systems, not the other way around. Hypervisors *specifically* have functions to do with creating and managing virtual machines; operating systems *in general* do not necessarily have this specific functionality (although you can run virtual machines inside, e.g. Windows, it is other third-party software you'll need to install inside Windows that provides the hypervisor functionality, not the Windows operating system itself). So I would not view a "normal" operating system as a bare metal hypervisor.

# Answer
> 6 votes
I don't want to repeat what has already been written in other answers. Instead I will focus on two things: one, a comparison of features, and two, a pair of examples.

I hope you will see in the end that Operating Systems and Hypervisors are closely related and also that there is no real sharp boundary, but rather a sliding scale of "Hypervisory-ness".

# Comparison of Operating Systems and Hypervisors

## Similarities between Operating Systems and Hypervisors

There are some things which are similar between Operating Systems and Hypervisors: both of them provide isolation between and scheduling of "tasks" (processes in the case of the OS, VMs in the case of the Hypervisor). Both of them provide resource management, resource isolation, and resource virtualization. Both of them provide memory management. Both of them provide a storage abstraction: in the case of the OS, you have a hierarchical file system, in the case of the Hypervisor, you have images; you can think of images like very big files and you can think of the way images are bound to VMs as simple directories.

## Differences between Operating Systems and Hypervisors

However, there are also important differences: Operating Systems manage and schedule a large number of small processes, whereas Hypervisors manage and schedule a small number of large VMs. Operating Systems manage a large number of small files in deep hierarchies, Hypervisors manage a small number of large images in flat (often single level) "directories".

# Case studies

But the similarities between the two have not gone unnoticed.

You need to be able to manage your VMs somehow, start and stop them, create, configure, and delete them, download and upload them, etc. For these management / service tasks, most bare-metal Hypervisors have some traditional OS features as well such as a console, GUI, web server, etc. All of these need to be implemented by the hypervisor.

In addition, the hypervisor needs to be able to use the hardware of the host platform, at the very least network interfaces and storage, but for the service features possibly also keyboard, mouse, display, etc. For this, it needs drivers. On many platforms, the hypervisor will also be – at least partially – responsible for thermal management, for which it will again need drivers to read the temperature and fan speed sensors, control the fan controller, etc.

These are all things that an OS also needs. However, hardware vendors will typically only provide drivers for the most popular Operating Systems (e.g. Windows, macOS, Linux) but not Hypervisors (e.g. ESXi). And third-party or Open Source driver developers will also typically focus on systems with the largest installation base, which are again the popular OSs. As a result, driver support in hypervisors is often lagging behind the "big three" OSs, in availability (it takes longer for a driver to be available at all), features, performance, stability, reliability, and quality.

Think, for example, of the rapid evolution of storage solutions in the last years with ever-changing interfaces, protocols, APIs, and features between AHCI (SATA), SCSI (SAS, FiberChannel, iSCSI), NVMe (M.2, U.2, U.3, EDSFF), and more "exotic" ones such as Optane.

## Xen

The developers of the Xen bare-metal hypervisor have recognized this and have come up with the following solution: in Xen, there is a *Domain 0 (Dom0)* ("Domain" is Xen's term for a VM), which is a VM with special privileges that can, for example, access hardware directly. This Dom0 runs a normal OS with some slight modifications. (Xen itself maintains support for Linux and there is partial support for NetBSD and OpenSolaris / Illumos.)

In this way, the Xen developers don't have to develop drivers for the tens of thousands of network cards, storage controllers, etc. and they don't have to develop a console, a terminal, a shell, a GUI, or a web server. All they need to do is to develop a way to pass devices from the Dom0 to the Xen Hypervisor.

This leads to some interesting questions: can you call Xen a Hypervisor if it cannot do its job independently without the help of the Dom0 (which is a full-blown OS)? What is the Hypervisor in Xen's case? Is it Xen? Is it the combination of Xen and the Dom0? Does that mean that a Hypervisor is an OS plus something extra?

It turns out this architecture leads not only to some awkward questions, it also leads to a slightly awkward and complicated design, where Dom0 runs on top of the Hypervisor (i.e. depending on the Hypervisor's services) while at the same time providing services to the Hypervisor (i.e. the Hypervisor depending on the Dom0's services).

## Linux Tasks

Let's compare this to modern (para-)virtualization on Linux.

Many Operating Systems have several different types of "Scheduler Entities" which differ mostly in their "weight" and level of isolation. Most Operating Systems have some sort of concept of *Processes* (more heavyweight, but better isolated) and *Threads* (more lightweight, but less isolation, e.g. Threads of the same Process share their memory). Some Operating Systems have even more, e.g. Windows NT has Processes, Threads, and *Fibers*.

Linux has gone down a different route, though. When developers asked for native Kernel-scheduled Threads to be added to Linux because Processes were too heavyweight and slow, Linux's Lead Architect Linus Torvalds decreed: if Processes are too heavy, then the solution is not adding more complexity to the kernel by adding an additional type of Scheduler Entities (like most other OSs have done) but making the Processes lighter, thus fixing the root cause of the problem. As a result, unlike many other Unix-like Operating Systems which have both Processes and Threads in their kernels, Linux only has a single type of *Kernel-Scheduled Entities (KSEs)*: *Tasks*.

Tasks are the only KSEs in Linux: on a fundamental level, there are no Processes nor Threads. Instead, when creating a Task, you can pass a set of flags which define which parts of the system are shared with the parent task and which aren't. So, by passing the appropriate set of flags, you can create a new process (by telling the OS that you don't want to share memory) or a new Thread (by telling the OS that you *do* want to share memory).

This "sharing" (and conversely isolation) is defined through *Namespaces*. They are actually much more sophisticated than a simple "share / don't share" flag mechanism. First off, there can be many Namespaces, and each Namespace can contain many Tasks. Secondly, there are many kinds of namespaces, not just for sharing memory: there are network namespaces, filesystem namespaces, process ID namespaces, user ID namespaces, namespaces for hostnames and name resolution, even time namespaces (allowing different Tasks to have different system clocks), etc. Thirdly, they can be nested.

Using only those two features, Tasks and Namespaces, a lot of features that exist in other OSs can be implemented:

* Processes (Tasks which share everything except instruction pointer, stack, and memory),
* Threads (Tasks which share everything except instruction pointer and stack),
* `chroot` (Processes which have as the root of their filesystem namespace a sub-node of the parent namespace), or
* FreeBSD `jail` like functionality, or
* Solaris Zone like functionality.

The developers of OS-level Container solutions quickly realized that a group of Processes that share most of the system (except memory) with each other but none of the system with the rest of the Processes would act as an OS-level Container. The *Linux Containers* Project (aka LXC / LXD) uses this approach. Similarly, Application Containers can be built this way, too. Docker uses this approach.

And it didn't take long until an Israeli virtualization company named Qumranet realized: hey, wait a minute, if we have these features that allow us to build anything on a sliding scale from Threads which share everything to Containers which share nothing except the kernel … what if we just slightly extend this scale just a little bit further so that Tasks don't even share the kernel?

We get a Hypervisor with a world-class scheduler, memory management, and network stack, drivers for tens of thousands of devices, support for dozens of architectures, and an established ecosystem for remote configuration and management. And all of that practically for free!

The result of that realization is KVM, which essentially turns the Linux kernel into a bare-metal Hypervisor, but one built out of an existing OS.

Compared to Xen, this solves the "awkwardness" of having the Hypervisor depend on the privileged OS and at the same time having the privileged OS depend on the Hypervisor by effectively collapsing the two into one. It solves the driver problem of something like ESXi by simply *being Linux*, an OS which already has drivers for almost everything under the sun. It solves the problem of having to develop APIs, tools, servers, and infrastructure for (remote) administration, management, maintenance, and configuration, since all of those tools already exist for Linux.

Just imagine how much harder it would be to build something like the Proxmox web GUI if you first had to write (or port) your own web server, port Python (or PHP / Ruby / Node.JS / Java / …), database, etc. Or the fact that Proxmox disk images can be stored on half a dozen different network filesystems, Proxmox can authenticate users against half a dozen authentication providers, etc. None of this had to be developed, it already existed as part of the Linux ecosystem.

I don't know much about Hyper-V, but I believe it has a similar architecture with using the NT kernel as the Hypervisor kernel and thus getting access to NT drivers, libraries, and applications.

# Conclusion

Hypervisors share many similarities with OSs. They can be regarded as a special kind of OS or they can be regarded as something different but closely related. Real-world implementations show the tight relation with Hypervisors relying on OSs and even OSs being used as Hypervisors.

# Answer
> 3 votes
In the simplest terms, an operating system manages the hardware on behalf of user-mode programs, where a hypervisor manages the hardware on behalf of a VM, itself pretending to be hardware.

An "operating system" traditionally consists of an "executive" or "kernel", a collection of utility programs, and at least one command shell.

It sounds like you're referring specifically to the kernel, which manages hardware on behalf of user processes. It handles hardware interrupts from devices and passes them off to drivers, and passes commands, usually issued via software interrupts, along to devices. It mediates communication between user processes and devices. It manages myriad blocks of memory owned by processes.

A hypervisor is simpler. It keeps track of which of the VMs owns which CPUs, which devices and what range of the memory address space. It passes hardware interrupts through to the appropriate VM where they're seen by the OS it hosts and handled by that OS' drivers, and intercepts software interrupts from the OSs on hosted VMs to the devices which that OS' VM owns. It manages a few blocks of memory on behalf of VMs.

This is oversimplified, but those are the principal differences.

They're similar in some ways, but a hypervisor is a lot thinner; it has fewer details to keep up with.

# Answer
> 2 votes
From what we've seen so far, we can confirm that there is no single answer.

The answer depends on the context in which you want to compare “operating system” to “hypervisor”, however for basic/conceptual understanding we could say:

* Both are specialized programs to support and run programs;
* Both orchestrate, access and execute the functionalities of a HW in a shared way for all the applications that are running in their workload;
* Both orchestrate access to CPU, RAM, disks and other hardware resources, one or the other being able to support or not a device, due to the existence or not of a connection drive.

The question is:

* hypervisor consists of a specialized program to orchestrate the resources of the hw to pseudo-computational virtual-computers, simulating HW computers, providing isolation of access to the resources of the HW in a shared way.
* operating system consists of a specialized program to orchestrate hw resources for general purpose applications, which can even be virtualization programs, such as virtualbox, vmware-workstation, kvm, etc;

You might then ask, why should I use hypervisor instead of operating system?

Basically we can say (a very simple answer without much detail): sharing resources in a decentralized way for different purposes, ensuring that actions in an application do not affect actions in other applications, creating isolated environments.

# Answer
> 1 votes
Great conversation so far...

I spend a fair bit of time with hypervisors in edge devices, and the discussion about what is Type1 and Type2 has always fascinated me. Type1 is usually associated with 'bare metal' whereas Type2 is associated with 'operating system hypervisor'. Bare metal must be always better right?
But many people forget what was mentioned above, that with a bare metal hypervisor you need some form of serviceOS (Domain0) to manage the VIRTIO device backends as well as other constructs needed by the hypervisor. So is it really 'bare metal'?
If my guest needs a comms channel to route a request to serviceOS and then the serviceOS does the pass-thru to hardware (drivers exist in serviceOS) does that make my hypervisor a 'bare metal'?
Semantics and marketing.

What I see happening are three things:

1. The silicon vendors are biasing their solutions towards setups where the virtual machine is hosted by a rich operating environment. Leading technology on this is VHE on ARM (virtualization host extensions). The entire SoC is geared towards fast transitions between exception levels (when needed). This silicon vendor bias is better for setups where there is an operating system hypervisor (hence the word 'host' in VHE)
2. Complexity. VIRTIO is becoming more and more complex with more and more devices with extensive setups like graphics, audio, bluetooth etc. being virtualized, especially in the Android 13 world. This biases towards setups where guest is communicating with a rich host environment, sharing buffers etc.
If I now need to maintain a Linux build as my VIRTIO support layer, who is doing that for me?
3. Safety and security. Removing the need for a serviceOS by having a rich and safety-certified host operating environment gives me a simpler path to certification of my device.

All comments above are my own.

---
Tags: operating-systems
---


# Question
Title: Does the computer change the content of the virtual adress
My book(digital design and computer architecture ARM edition) explains loads and stores like this:

> To perform a load or store, the processor must first translate the virtual adress to a physical adress and then access the data at that physical adress. The processor extracts the virtual page number from the virtual adress and adds it to the page table register to find the physical adress of the page table entry. The processor then reads this page table entry from the physical memory to obtain the physical page number. If the entry is valid, it merges this physical page number with the page offset to create the physical adress. Finally, it reads or writes data at this physical adress. Because the page table is store in physical memory, each load or store involves two physical memory access.

From what I understand this means that loads and stores are made on the physical adress? But when we turn of the computer we lose the content in RAM(physical adress), so does the computer always update the content of the virtual adress with the corresponding content in the physical adress?

# Answer
> 1 votes
Maybe the confusion resides between the difference between the MMU and the caches.

The MMU translates virtual to physical addresses, it uses some pagination tables stored somewhere in memory.

Actual data is stored in various memories. It can be DRAM, it can be caches, it can be even some disk (like when computers are turned off with "suspend to disk". Data is copied between different levels of cache and memory.

DRAM is accessed by physical addresses, and caches can be indexed either by virtual or by physical addresses, although nowadays they tend to use physical addresses, to ease coherency management.

# Answer
> 0 votes
The computer cannot predict that you are about to turn it off, so yes, it updates the content of the virtual address when requested to do so, and this implies a change in content at the corresponding physical address.

(In reality, the changes to physical memory can be postponed when there are caches, but this is yet another story.)

---
Tags: memory-management, virtual-memory, memory-allocation
---


# Question
Title: Determining the minimum number of edges to add to a graph to obtain a clique of size $k$
As part of a hobby project I stubmled into the following question which has me stumped:

Given an undirected graph $G = (V, E)$ and an integer $k$, what is that smallest number of edges that need to be added to $E$ such that the new graph $G' = (V, E')$ has a complete induced subgraph of size $k$, and what vertices would be involved?

I have never studied graph theory, so I wouldn't even know where to start with this problem. I can see the brute force solution which would be to look at all $\binom{|V|}{k}$ subsets of the vertices, and count how many of the $\frac{1}{2}k\cdot(k-1)$ necessary edges are already present in $G$. The subset with the smallest number of missing edges is the one I'm looking for. If we assume that $|V| \gg k$, that means looking at $\sim|V|^k$ subsets, and every edge of $E$. Is there a better way of doing things?

I have tried to see if anyone else has thought about this problem before, but I haven't found the right search terms. It seems that there's a class of problems known as graph editing problems, which I think this falls under, but I haven't been able to find anything when searching for that.

So, I fundamentally have two questions:

1. Does this problem have a name?
2. Is there a known solution that's better than brute force?

# Answer
> 4 votes
The problem is called **Defective $k$-Clique** \[Yu et al., Bioinformatics (2006)\]. The optimization problem is:

**Problem:** *Defective $k$-Clique*
**Input:** A graph $G$ and $k \in \mathbb{N}$.
**Output:** The minimum number, $\ell$, of edges to add to $G$ such that $G$ has a $k$-clique.

Clearly, $G$ has a $k$-clique if and only if $\ell = 0$, hence the problem is NP-complete. There is likely no algorithm running in time $f(k+\ell) \cdot n^{o(k + \ell)}$ \[Chen et al., Inf. Comput (2005)\]. Hence, brute force seems like the only option.

That said, there's a difference between brute forces (PDF). You can enumerate maximal cliques, you can try to use SAT solvers or ILP. You can try with branch & bound, and branch & reduce algorithms. You can play around with densest subgraph-algorithms, etc. Don't give up hope of a practical algorithm just because theory says no.

---
Tags: algorithms, graphs, reference-request, clique
---


title: O(Log n) Search - Array

text:
# Question
Title: O(Log n) Search - Array
So, there's a LeetCode problem that has you find a O(log n) solution to finding a target number in a rotated sorted array.

As an example:

```
array = [5,6,7,1,2,3]
target = 4

```

Basically, the trick is that you can find the point of rotation in O(log n) time and then you can do a binary search over the appropriate subsection in O(log n) time to find the index of the target (if it exists) in the array.

This sort of got me thinking, what are the conditions under which you can do a O(log n) search for an element in an array in which all numbers are distinct?

Clearly, you can still do a O(log n) search even if the array is something less than strictly sorted. But, I don't know how far you can push the array before it is no longer searchable in log n time.

How would one look to solve or describe a problem like this?

# Answer
I think you essentially answered it yourself (and @Yves Daoust) with the point that there's an O(log(n)) trick.

**We could say that it's the set of problems for which you can modify a known O(log(n)) algorithm by adding O(log(n)) operations.**

You asked for "the conditions" under which an array can be searched in O(log(n)). The answer above is informal, but I expect there's a nice mathematical way to express it. That might start with defining a *problem* as a set of arrays, such as a set identified by some conditions or specification; e.g., "any array that is a rotation of a sorted array."

In the case of the rotated array, the added operations are finding the smallest or largest element, which can be done in O(log(n)).

Another example: if you have an array of numbers such that every number is no more than 10 positions away from where it would be if sorted, then you modify a binary search algorithm by walking the 20 positions surrounding the point where the algorithm expected to find it. That's just adding a constant number of operations (~20), which is less than O(log(n)).

I think we could keep coming up with new O(log(n)) problems by taking one of these that we've discovered and "perverting" it. For example, we could have a rotated array with numbers no more than 10 spots away from their rotated-sorted position. That sounds a little more complicated, but I expect it's still O(log(n)).

I believe the ways the problem could be modified are infinite and potentially very complicated, so it's probably not worth trying to identify them . . . unless you are looking for good job interview questions.
> 1 votes

# Answer
I would begin by considering the time complexity of an array in absolute worst or best case before concerning with any slight deviations from average. I don't know if you are going to get discernable results.
> 0 votes

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


# Question
Title: what is the time complexity of this while loop nested in a for loop?
I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length:

```
def smallest_subarray_sum(s, arr):
    window_sum = 0
    min_length = math.inf
    window_start = 0

    for window_end in range(0, len(arr)):
        window_sum += arr[window_end]  # add the next element
        # shrink the window as small as possible until the 'window_sum' is smaller than 's'
        while window_sum >= s:
            min_length = min(min_length, window_end - window_start + 1)
            window_sum -= arr[window_start]
            window_start += 1
    if min_length == math.inf:
        return 0
    return min_length

```

Also, please share some material to look into to understand big O for nested loops

# Answer
Forget about there being a nested loop. There could be 10 nested loops; it wouldn't make a difference.

Ask yourself: How often is window\_start increased? From that you can conclude how often the inner loop is executed and that solves the problem.

Note: It takes experience and training / practice to read code like this and figure out in your head what exactly it does. The easiest way is to write a program, then use a debugger, run the program, and see what happens. If you did that, say for an array of size 20, you would figure out easily what exactly is happening.
> 0 votes

# Answer
**Hint:**

You cannot analyze this code in terms of two nested loops like in simpler cases, because the number of iterations of the inner loop varies depending on the data.

But you can solve this with a simple remark: as `window_start` grows by units, from `0`, and will not exceed `n:= len(arr)`, the total number of inner iterations cannot exceed `n`.
> 0 votes

---
Tags: big-o-notation
---


title: Proof that STCON is in NL

text:
# Question
Title: Proof that STCON is in NL
What is the proof that STCON (returns 1 if there is a path in the directed graph $G = (V,E)$ from $ s \in V$ to $t \in V$ and else, 0.

is indeed in NL? (Non-deterministic turing machines with logarithmic memory)

# Answer
> 1 votes
Here is an NL algorithm:

* Input: Graph, nodes $s,t$
* Count the number of nodes $n$
* Guess $\ell \in \\{0,\ldots,n\\}$
* Repeat $\ell$ times: Guess an out-neighbor $s'$ of $s$ and set $s \gets s'$
* Verify that $s = t$

---
Tags: complexity-theory, graphs
---


# Question
Title: Why does Michael Sipser state that $0^p0^p$ is a bad choice for proving $L=\{ww|w \in \{0,1\}^*\}$ is non-regular a bad choice?
I feel that choice should work great for proving non - regularity of the mentioned language.

If $L=\\{ww|w \in \\{0,1\\}^\*\\}$ and we choose $s=0^p0^p$, meaning s is atleast as long as 'p'. Then we can decompose s as follows $x=empty \ string,\ y = 0^p, \ z = 0^p$

Then we can pump 'y' according to the rules of pumping lemma we will end up with 2p zeroes which is more than the number of zeroes in 'z'

And we have reached a contradiction because this new string is not in the language and according to the pumping lemma it should have, so why does michael sipser say that it's a bad candidate for proving non regularity in this langauge?

# Answer
Your proof doesn't work. First of all you can't choose your favorite decomposition of $s$: the pumping lemma just ensures that such a decomposition **exists** so your argument needs to work for all possible decompositions.

Nevertheless, even with your decomposition it is false that the "pumped" word does not belong to the language. To see why suppose that the pumping length $p$ happens to be $2$. Then $s=0^20^2=0000$, $x=\varepsilon$, $y=0^2=00$, and $z=0^2=00$.

Now let's pump $y=00$ to, e.g., $y^2 = 0000$. The resulting word is $xy^2z = \varepsilon\\, 0000\\, 0^2 = 000000$. As you can see $000000 \in L$ (by choosing $w=000$).

You run in the same problem regardless of how many times (possibly $0$) you pump $y$.
> 3 votes

# Answer
First of all, you don't get to pick the decomposition. So one decomposition you'd need to handle is $x = \varepsilon$, $y = 00$, $z = 0^{2p-2}$. Now if we pump $y$ for $i$ times, we get $xy^iz = 0^{2p + 2i - 2}$, which belongs to $L$.
> 1 votes

---
Tags: pumping-lemma
---


title: Duplicate rules in CFG

text:
# Question
Title: Duplicate rules in CFG
Suppose I have the following CFG that I would like to bring to CNF

```
S -> TA | bA | Ab | b

A -> Aa|a

T -> Ab

```

Then I have two options to get rid of the nonsolitary terminal a in Aa

1 - Make a new nonterminal K and introduce the rule

The grammar in this case becomes

```
K->a

S -> TA | bA | Ab | b

A -> AK|a

T -> Ab

```

2 - Observe that A-\>a already and use it

The grammar in this case becomes

```
S -> TA | bA | Ab | b

A -> AA|a

T -> Ab

```

My intuition is that both should be correct since I don't see that changing a nonterminal's name would change the language the grammar generates but I am not entirely sure.

Thanks.

# Answer
> 1 votes
In this case, both are correct, but in general, you should use method 1.

For example, suppose that you had

$$A \to Aa|a|b.$$

You might be tempted to say that we have $A \to a$ already, so let's just use $A$ instead of creating a new non-terminal, and convert this to

$$A \to AA|a|b.$$

This would be an incorrect transformation, because originally $A$ generates the language $a,b,aa,ba,aaa,baa,\cdots$, and after the (incorrect) conversion, $A$ generates $a,b,aa,ab,ba,bb,aaa,aab,\cdots$

So, use method 1. Method 1 is always correct. It is just a "happy accident" that method 2 happens to work in this case, but in general, it often won't work.

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


# Question
Title: What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
I'm trying to figure out a more efficient solution to the following problem.

**Dataset:** A set of arrays of key-value pairs `(K, V)`. The arrays have varying lengths, and the keys are non-zero 16-bit unsigned integers.

Examples:
`[(3, 100)]`
`[(1, 200), (1, 100), (2, 300)]`
`[(2, 200), (2, 300)]`

**Input:** A fixed-length array of key-value pairs `(J, U)`. The keys are non-zero 16-bit unsigned integers.

Example:
`[(2, a), (1, b), (5, c), (1, d)]`

The example is 4 elements, in the actual implementation it's always 8.

**Expected Output:** An array with length equal to one of the dataset arrays. The array elements are pairs of values from the dataset and input. I'm not sure how to express this in mathematical notation, so here's some pseudocode for a naive implementation:

```
for arr in dataset {
  let out_arr = []
  for (k, v) in arr {
    let result = null
    for (j, u) in input {
      if k == j {
        result = (j, u)
        break
      }
    }
    if result == null { break }
    input.remove((j, u))
    out_arr.push((v, u))
  }
  if out_arr.length == arr.length {
    return out_arr
  }
}
return null

```

This algorithm, when ran for the above dataset and input, would produce the following array: `[(200, b), (100, d), (300, a)]`

To attempt to state the algorithm in words: I need to see if there exists an array in the dataset for which every pair has a matching (by key) pair in the input. If there is such an array, I need to construct an output array of pairs of the values from each matching pair between the dataset and the input.

**Caveat:** The algorithm above is actually insufficient because if there are multiple valid outputs, one needs to be chosen *at random*, or at the very least in a way that prevents aliasing. In practice I'm doing this by shuffling the input array and using the solution below. This is also what makes it difficult to consider solutions that require sorting the input array.

The current working solution I have is to store a tree containing all possible continuation nodes given input in any order. Nodes which represent the completion of one of the dataset arrays also have the `V` values from the array in the order the array was traversed. For example the array `[(1, 200), (1, 100), (2, 300)]` may be represented by the tree in the following diagram (with the output values in red boxes):

In this case, I find the solution like this:

```
let node = root
for (u, j) in input {
  let next = tree.get(u)
  if next { node = next }
}
if node.output return node.output

```

The time taken to construct the data structure is not important, nor is maintenance cost or cost of any operation other than lookup, and generally there is plenty of space but I would like a structure that can be stored contiguously in memory.

Sorry if the way I've described the problem is confusing, I don't have the background in mathematics to know any of the terminology to help describe it. Please do ask for clarification in the comments.

# Answer
> 1 votes
If I understand correctly, we can reformulate your problem as following:

We have a database that contains a set of sets $S\_1,\dots,S\_n$. You are given an input set $I$. The goal is to determine whether there is any set in the database that is a subset of $I$: i.e., does there exist $i$ such that $A\_i \subseteq I$?

Here I am treating each array as corresponding to the set of key values in the array. The above contains the core challenge of your problem. If such a set exists, and we can find which one it is (which is a "full match"), then we can easily derive the mapping to values and obtain the desired array of pairs.

So, you want to support subset queries. Unfortunately, this is a hard problem. You can take a look at the following questions to see if any of the methods mention there will be of use to you:

I don't know whether these will be useful to you in practice.

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


# Question
Title: Convert regex for comma separated value to CFG grammar
I have the following regex that I'm trying to convert to a CFG: `e|a(,a)*` (`e` representing the empty state). Basically I want to match a comma-separated list (without a leading or trailing comma) or nothing at all. Here are some of my attempts:

```
S = A
A = e | a | a , A

```

This doesn't work, it matches `,a` (leading comma).

```
S = A | B
A = e
B = a C
C = , C | a | e

```

This doesn't work either, it matches `a,` and `aa` (trailing and missing comma).

Is my regex even representable as a CFG?

Thanks in advance

# Answer
> 0 votes
At the heart of your regex is an alternation {$\alpha|\beta$), which means that the regex matches $\alpha$ or $\beta$. That's how you should write the CFG: $$\begin{align}S\to&\\;\alpha\\ |&\\;\beta \end{align}$$ Here, $\alpha$ is $\varepsilon$ and $\beta$ is the subexpression $a(,a)^\*$, for which we'll define the non-terminal $A$.

It's easy to see what $A$ is: it starts with an $a$ and can be extended arbitrarily with $, a$: $$\begin{align}S\to&\\;\varepsilon\\ |&\\;A\\ A\to&\\;a\\ |&\\;A\\;,a \end{align}$$

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


# Question
Title: Collisions in hash table - Is this table wrong?
I have the following hash table with hashcodes being quadratic numbers.

Why do 0, 16, and 64 have different number of collisions when they map to the same number (line %16). Also how is it possible for 64 to have 6 collisions?

# Answer
> 2 votes
Here collisions means the number of (occupied) positions visited before finding a free spot and placing the number.

64 goes to 0(occupied by 0) - 1(by 1) - 2(by 16) - 3(by 49) - 4(by 4) - 5(by 36) - 6(bingo)

The table is consistent with linear hashing and stepsize $1$.

---
Tags: hash-tables
---


# Question
Title: Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph
I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest". I thing that the claim may be false (i.e there might be an example of a disconnected undirected graph so that the prim algorithm doesn't return MSF) but I cannot think of such example.

Also when I look at the algorithm- it seems to me that when we are done with one connectivity component, we'll just extract from Q (a min heap) a vertex that in another connectivity component so it would just work fine. What am I missing?

$\text{MST-PRIM}(G, w, r):$
$\quad\quad\textbf{for }\text{each }u\text{ in }G.\\!V$:
$\quad\quad\quad u.key = \infty$
$\quad\quad\quad u.\pi = \text{NIL}$
$\quad\quad r.key = 0$
$\quad\quad Q = G.\\!V$
$\quad\quad \textbf{while }Q\not=\emptyset:$
$\quad\quad\quad u = \text{EXTRACT-MIN}(Q)$
$\quad\quad\quad\textbf{for }\text{each } v\in G.\\!Adj\[u\]:$
$\quad\quad\quad\quad\textbf{if }v\in Q\text{ and }w(u, v) \< v.key:$
$\quad\quad\quad\quad\quad v.\pi = u$
$\quad\quad\quad\quad\quad v.key = w(u, v)$

The above description is taken from CLRS, chapter *Minimum Spanning Trees*, where the algorithm will return $\\{(v,v.\pi): v\in G\\!.V-\\{r\\}\\}$.

# Answer
It depends on how *you/we* understand/define what is Prim's algorithm when the given graph is disconnected. You did not missing anything important.

"The most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs.", said by Wikipedia. That most basic form starts with a vertex and only grow edges that connect to the vertices that has been added. Many descriptions of Prim's algorithm such as here on cp-algorithms/, here on programiz and here on javatpoint stick to this simplest form.

However, suppose we consider the pseudocode shown in the question as the definition of Prim's algorithm. Then it will find a minimum spanning forest (MSF) for the given graph, since at the end of the algorithm all vertices will be extracted from queue $Q$ that was initialized with all vertices. Here we assume, of course, that "Extract-Min" will not malfunction when the minimum value of the keys is $\infty$. As you noted, when we are done with one connected component, we'll just extract from $Q$ (a min heap) a vertex that in another connected component. In this sense, the name of the procedure, "MST-Prim" could have been "MSF-Prim". So, you can be correct in asserting "the claim may be false".

---

In contrast, whatever description is used for Kruskal's algorithm, it will return a minimum spanning forest of the given graph. There is no ambiguity here.
> 0 votes

---
Tags: weighted-graphs, minimum-spanning-tree, prims-algorithm
---


title: Prove that $coNP \neq NTIME(n^2)$

text:
# Question
Title: Prove that $coNP \neq NTIME(n^2)$
I need to prove that

> $coNP \neq NTIME(n^2)$ using time hierarchy theorem.

as we know $DTIME(n^4)\subseteq P\subseteq coNP$

from time hierarchy theorem we can derive that $DTIME(n^4) \not \subseteq DTIME(n^2)$

therefore $DTIME(n^2) \neq coNP$

Also

as we know $NTIME(n^4)\subseteq NP$

from time hierarchy theorem we can derive that $NTIME(n^4) \not \subseteq NTIME(n^2)$

therefore $NTIME(n^2) \neq NP$

But anyway, I could not derive $coNP \neq NTIME(n^2)$ from any combination. Can someone give me a clue?

# Answer
You should use the fact that $\textsf{NTIME}(n^2)\subsetneq \textsf{NP}$.

If $\text{co}\mathsf{NP} = \textsf{NTIME}(n^2)$, then $\text{co}\mathsf{NP} \subsetneq \mathsf{NP}$ and you can reach a contradiction.
> 0 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?
I have the following problem to solve:

Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs exactly once in the array. The desired output is the unique number with the lowest position in the array.

For example, consider the following array A:

```
   A[0] = 4
   A[1] = 10
   A[2] = 5
   A[3] = 4
   A[4] = 2
   A[5] = 10

```

In this array, the unique numbers are 5 and 2. The first unique number with the lowest position is 5 because A\[2\] = 5.

The problem requires an algorithm and the time complexity for finding the first unique number in the given array. The algorithm should be able to handle a generic case where the given array A can have any size N and any set of integers.

# Answer
> 1 votes
Simples. Use a hash table. Fill it with a\[n-1\], a\[n-2\] ... a\[0\] in that order. When you add a number to a hash table you will know if it was there already or not. What you want is the last number you added that wasn't in the hash table before you added it.

(It is obvious that you need to examine all array elements, because one that you don't examine could contain the same value as the array element that you thought was the first unique one, and you would get the wrong answer).

A hash table of reasonable size will work in constant times average.

# Answer
> 0 votes
Here's one idea.

1. Pair up each element with its index.

```
 [(4, 0), (10, 1), (5, 2), (4, 3), (2, 4), (10, 5)]

```
2. Sort.

```
 [(2, 4), (4, 0), (4, 3), (5, 2), (10, 1), (10, 5)]

```
3. It is now easy to recognize unique elements, because if any duplicates exist they are right next to each other. Keep only the unique elements.

```
 [(2, 4), (5, 2)]

```
4. Sort again but on the other half of the pair.

```
 [(5, 2), (2, 4)]

```
5. Take the first result.

---
Tags: algorithms, complexity-theory, arrays, first-order-logic, integers
---


# Question
Title: Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex
Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$

I've narrowed the solution to 3 situations, in $G$: $d(v)\<k , \\d(v)=k\\d(v)\>k$

When $d(v)\<k$, it is clear that there cannot exist a spanning tree of $G$ such that $d(v)=k$, since $d(v)$ was never of value $k$ to begin with.

When $d(v)\>k$, we know that we can create a graph $G'$ in which we remove a finite amount of edges $i$ in such a matter that we reduce $d(v)$ to be $k$, and check whether $G'$ is connected or not (we can use BFS), since $d(v)\leq |V|$, the complexity would be $O(|V|\cdot (|V|+|E|))$, however I feel this is extremly inefficient.

For the case where $d(v)=k$ in $G$, I am uncertain on how to proceed.

EDIT: I've managed to update the case where $d(v)\>k$ to be in linear time:

if $d(v)\>k$, we'll have to remove edges from the graph.

We'll perform $DFS$ on $v$, since $d(v)\>k$ there will be back edges, we can (in linear time) count how many back edges are going into(or out of) $v$, if the number of back edges is greater than $m-k$ where $|E|=m$, we can remove $m-k$ back edges from $G$, if the number of back edges is smaller than $m-k$, there cannot be a spanning tree in which $d(v)=k$.

The updated solution to the case was given to me by a colleague, I dont completely understand it yet I am trying to wrap my head around it.

About the case where $d(v)=k$, I am still uncertain.

# Answer
> 5 votes
First, verify that $G$ is indeed connected, otherwise say no.

Second, if $G - v$ (the graph after deleting $v$) has more than $k$ components, we can say no.

Pick any $k$ neighbors of $v$ with the restriction that you pick at least one from each component of $G-v$ and mark them. The edges from $v$ to these marked vertices are in the spanning tree.

For each connected component $C$ of $G-v$, pick a marked vertex $x$. Run a DFS from $x$ and pick the edges you traverse as long as you see an unvisited vertex. If you meet a visited vertex, you ignore the edge. If you meet a *marked* vertex, simply do not put that edge into the spanning tree.

---
Tags: graphs, spanning-trees
---


# Question
Title: A sufficient condition for unsatisfiability
Let $\varphi = \bigwedge C\_k$, in which $C\_k$ is a clause in *X3SAT* (exactly-one *3SAT* or one-in-three *3SAT*). That is, $C\_k = (l\_i \odot l\_j \odot l\_u)$ such that $l\_i \in \\{x\_i, \overline{x}\_i\\}$ for any $i$. Then, $C\_k$ is true iff exactly one of $\\{l\_i, l\_j, l\_u\\}$ is true. Hence, if $C\_k$ is true, then $\[l\_i \Rightarrow (\overline{l}\_j \wedge \overline{l}\_u)\] \wedge \[l\_j \Rightarrow (\overline{l}\_i \wedge \overline{l}\_u)\] \wedge \[l\_u \Rightarrow (\overline{l}\_i \wedge \overline{l}\_j)\]$ is satisfiable. Thus, $\phi\_k = (\overline{l}\_i \vee \overline{l}\_j) \wedge (\overline{l}\_i \vee \overline{l}\_u) \wedge (\overline{l}\_j \vee \overline{l}\_u)$. Let $\varphi' = \bigwedge \phi\_k$, which is in *2SAT*. If $\varphi'$ is unsatisfiable, then $\varphi$ is unsatisfiable. Is this result significant?

For example, consider $\varphi = (x\_1 \odot \overline{x}\_2 \odot x\_3) \wedge (\overline{x}\_1 \odot \overline{x}\_2 \odot x\_4) \wedge (x\_2 \odot \overline{x}\_3 \odot x\_4)$. Then, $\varphi' = (\overline{x}\_1 \vee x\_2) \wedge (\overline{x}\_1 \vee \overline{x}\_3) \wedge (x\_2 \vee \overline{x}\_3) \wedge (x\_1 \vee x\_2) \wedge (x\_1 \vee \overline{x}\_4) \wedge (x\_2 \vee \overline{x}\_4) \wedge (\overline{x}\_2 \vee x\_3) \wedge (\overline{x}\_2 \vee \overline{x}\_4) \wedge (x\_3 \vee \overline{x}\_4)$

# Answer
> 0 votes
No. It is not significant. $\varphi'$ is a much weaker condition. $\varphi'$ allows each clause to have either 0 or 1 satisfied literals. It's much easier to satisfy that restriction. I don't expect that this will be useful in practice, and it has no value for proving new theoretical results that I can see.

If the $x\_i$'s are all variables (i.e., positive literals), then $\varphi'$ is always satisfiable (consider the assignment that assigns every $x\_i$ to False), so the result is trivial.

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


# Question
Title: Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I'm currently stuck showing $NP$-hardness of a problem of mine.

An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:

> Given a set of tupels $B=\\{(b\_1,1),\ldots,(b\_n,1)\\}$, with $b\_i\in\mathbb{N}\_{\>0}$.
> Goal: A partition of $B$ into two subsets $S\_1, S\_2$ such that each element $b\_i$ is exclusively either in $S\_1$ or in $S\_2$ and $$(\sum\_{i\in S\_1}b\_i)+|S\_2|=(\sum\_{i\in S\_2}b\_i)+|S\_1|$$

This can be seen in the following way. When $b\_i$ is choosen from the pair $(b\_i,1)$ to be in $S\_1$ the other Element (in this case always $1$) must be in $S\_2$.

I assume that this problem is $NP$-hard and that this can be shown by using the "classical" $2$-Partitioning-Problem where the goal is to partition a set $A=\\{a\_1,\ldots,a\_n\\}$ (with $a\_i\in\mathbb{N}\_{\>0}$) into subsets $S\_1,S\_2$ s.t. the sum of these subset equals.

This far I wasn't able to show that the "classical" $2$-Partiting-Problem can be reduced to (simple) pairwise $2$-Partitioning.

---

My first attempt was to model some arbitrary but fixed instance of the $2$-Partitioning Problem with $A=\\{a\_1,\ldots,a\_n\\}$ to an instance of (simple) pairwise 2-Partitioning by constructing $B=\\{(a\_1-1,1),\ldots,(a\_n-1,1)\\}$ but somehow wasn't able to show that each $YES$-Instance of $A$ also is some $YES$-Instance of $B$.

# Answer
I think you took the problem the wrong way, but your idea is good.

Let $A = \\{a\_1, …, a\_n\\}$ be an instance of $2$-$\texttt{Partition}$. Let $B = \\{(a\_1 + 1, 1), …, (a\_n+1, 1)\\}$. Then $A$ is a positive instance of $2$-$\texttt{Partition}$ if and only if $B$ is a positive instance of $\texttt{Pairwise}$ $2$-$\texttt{Partition}$:

* suppose there exists $I\_1\subset \\{1, …, n\\}$ such that $\sum\limits\_{i\in I\_1}a\_i = \sum\limits\_{i\notin I\_1}a\_i$. Then: \begin{align} \sum\limits\_{i\in I\_1}b\_i + |\overline{I\_1}| & =\sum\limits\_{i\in I\_1}(a\_i +1)+ |\overline{I\_1}|\\ & = \sum\limits\_{i\in I\_1}a\_i + |I\_1| + |\overline{I\_1}|\\ & =\sum\limits\_{i\notin I\_1}a\_i + |I\_1| + |\overline{I\_1}|\\ & = \sum\limits\_{i\notin I\_1}b\_i + |I\_1| \end{align}
* the other way is done in the same manner.
> 1 votes

---
Tags: reductions, np-hard, partitions, polynomial-time-reductions
---


# Question
Title: Correctness of FIPS 186-4 square test algorithm
Federal Information Processing Standard 186-4 appendix C.4 gives (without reference) an algorithm intended to test if a positive integer $C$ (which can be thousands bits) is a square:

1. Set $n$, such that $2^n\>C\ge2^{(n-1)}$.
2. $m=\lceil n/2\rceil$.
3. $i=0$.
4. Select $X\_0$, such that $2^m\>X\_0\ge2^{(m-1)}$.
5. Repeat
5.1 $i=i+1$.
5.2 $X\_i=((X\_{i-1})^2+C)/(2X\_{i-1})$.
Until $(X\_i)^2\<2^m+C$.
6. If $C=\lfloor X\_i\rfloor^2$, then *status* = `PERFECT SQUARE`.
Else *status* = `NOT A PERFECT SQUARE`.
7. Return *status*.

At step 5.2, can we compute $X\_i$ by Euclidean division (that is rounding down to the nearest integer)? In the affirmative, how do we prove the algorithm terminates, and yields correct *status*, regardless of the choice made at step 4? Towards this, what invariant condition should we prove is maintained during step 5?

---

I observe that in step 6 it's used $\lfloor X\_i\rfloor$ rather then just $X\_i$, and that's strange if $X\_i$ is intended to be an integer. Also, the notes after the statement of the algorithm, intended to prove it correct, seem written with real values in mind.

Remark: A practical implementation could suppress $i$ (thus steps 3 and 5.1), and use a single $X$ for all the $X\_i$. It could use an arbitrary integer type or class for at least $C$ and $X$.

# Answer
This is more or less Newton's method applied to the function $f:x\to x^2 - C$. The algorithm finds $r = \left\lfloor \sqrt{C}\right\rfloor$ and check whether $r^2 = C$ or not.

If we define $g(x) = x - \frac{f(x)}{f'(x)} = x - \frac{x^2-C}{2x} = \frac{x^2+C}{2x}$, then the computed sequence is $(x\_k)\_{k\in\mathbb{N}}$ such that $x\_{k+1} = \left\lfloor g(x\_k)\right\rfloor$.

Assume $x\_k \> \sqrt{C}$ for some $k$. Then: $$x\_{k+1}=\left\lfloor g(x\_k)\right\rfloor\leqslant g(x\_k) = \dfrac{x\_k^2+C}{2x\_k}\<\frac{2x\_k^2}{2x\_k} = x\_k$$

But since $x\_0 \>0$, let us distinguish:

* if $x\_0 \< \sqrt{C}$, then $2x\_0(g(x\_0) - \sqrt{C}) = x\_0^2 + C -2\sqrt{C}x\_0 = (x\_0 -\sqrt{C})^2 \> 0$. That means that $g(x\_0)\> \sqrt{C}$ and that $x\_1 \geqslant \left\lfloor \sqrt{C}\right\rfloor$;
* otherwise $x\_0 \geqslant \left\lfloor \sqrt{C}\right\rfloor$.

With the previous properties, we conclude that there exists $k\>0$ such that $x\_k \leqslant \left\lfloor \sqrt{C}\right\rfloor$ (otherwise $(x\_k)\_{k\>0}$ is a strictly decreasing sequence with $\left\lfloor \sqrt{C}\right\rfloor$ as a lower bound).

Let $k$ be the first integer $\>0$ such that $x\_k \leqslant \left\lfloor \sqrt{C}\right\rfloor$. That means that $g(x\_{k-1}) \> \sqrt{C}$. Since $x\_k = \left\lfloor g(x\_{k-1})\right\rfloor \leqslant \left\lfloor \sqrt{C}\right\rfloor$, we conclude that $x\_k = \left\lfloor \sqrt{C}\right\rfloor$.

Since (as stated in your document), $x\_k^2 \< 2^m +C$ implies $x\_k-\sqrt{C}\<1$, that means that $x\_k \leqslant \left\lfloor \sqrt{C}\right\rfloor$ so we conclude on the termination and the correctness of the algorithm.
> 10 votes

---
Tags: algorithms, correctness-proof, integers
---


# Question
Title: Find MST with bounded edge weight in O(|V|+|E|)
I need to describe (even in words) an algorithm that gets a connected, undirected, weighted graph so that the weight of each edge is either 1,2 or 3; and returns MST of that graph is time complexity O(|V|+|E|).

I thought to take kruskal algorithm and change the sorting algorithm to be counting sort (O(|E|) instead of comparison based sort (O|ElogE|) however this doesn't give well enough time complexity because of the "cost" of the set data-stracture (makeset,findset,union). Maybe some modification of the Prim's algorithm can work although I can't think of anything.

I'd love to get some help with this; I am struggling to find anything that would work in the required time complexity.

Thank you in advance!

# Answer
> 2 votes
You should use Prim's algorithm instead of Kruskal's algorithm.

Given a weighted undirected graph $G = (V, E, f)$ with $f(E) \subseteq \\{1, 2, 3\\}$ as an adjacency lists array, the following should work:

* Let $W$ be a boolean array of length $n = |V|$, with all values set to false, except $W\[0\]$ set to true.
* Let $T$ be a graph (as an adjacency lists array) with $n$ vertices and no edge.
* Let $E\_1$ (resp. $E\_2$ and $E\_3$) be the sets (or linked lists, as your prefer) of edges incident to the vertex $0$ of weight $1$ (resp. 2 and 3).
* While $T$ has less than $n-1$ edges:
    + pick $\\{u, v\\}$ an edge in $E\_1$ or $E\_2$ or $E\_3$ in this order, stopping with the first non empty set;
    + assume WLOG that $W\[u\]$ is true. If $\neg W\[v\]$ then:
        - add $\\{u, v\\}$ to $T$;
        - $W\[v\]\leftarrow $ true;
        - add to $E\_1$ (resp. $E\_2$ and $E\_3$) all edges incident to the vertex $v$ of weight $1$ (resp. 2 and 3).

This is exactly Prim's algorithm, but the extraction of the minimum weight edge is done using $E\_1$, $E\_2$ and $E\_3$, so it is done in constant time. Each edge is added and extracted from $E\_i$ sets at most twice (one for each of its extremities). If an edge $\\{u, v\\}$ such that $W\[u\] \land W\[v\]$ is extracted, it is just ignored. All other operations in the loop are in constant time, so the overall complexity is indeed in $\mathcal{O}(|V| + |E|)$.

---
Tags: algorithms, graphs, data-structures, minimum-spanning-tree, prims-algorithm
---


# Question
Title: $|v|$ and $|x|$ factorizations (in Pumping lemma for context-free) have the same length?
When i iterate $v$ and $x$ factorizations to see if a word is still in a language $L$, do i have to assume that $|v| = |x|$ always or could happen theirs lengths are different?.

I'm asking because i found a grammar for this language: $L$ = { $a^nb^m, |n-m|$ is even } , so it should be context-free.

But if i try to apply pumping-lemma using the word $a^nb^n$ , and i place $v$ in the first half and $x$ in the second half, and i assume that $|v|$ and |x| lengths could be different, it could happen the number of $a$ could be odd and the number of $b$ could be even, so an odd number minus an even number is an odd number, so the word is not in the language.

Thanks in advance.

# Answer
Note: the language is even regular.

The pumping says that **THERE EXISTS** a decomposition $s = uvwxy$ verifying the three conditions. It does not mean that such a decomposition is unique, nor that any decomposition works.

In your example, a decomposition $v = a$ and $x = b$ works, but so does $v = \varepsilon$ and $x = bb$, or $v = a$ and $x = aaaaa$, and so on…
> 1 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Do i really need to study monstrously long intel manual?
I want to be an OS developer. I can say I am a bit comfortable after i read few tutorial on x86 assembly. But I see a lot detailed in intel manual, does an OS developer really need to study whole manual for its architecture.

1. Is there any alternative ?
2. Will I miss something important if only reading short tutorial rather than manual of architecture

# Answer
If you want to develop an operating system, you have responsibility for things that most developers don't care about. For example, how to make virtual memory work. How to switch from process A to process B without B being able to access any information from process A, and so on. And everything you do must be 100% reliable, not 99.999999%.

You will need deep knowledge of the processor architecture, so you can avoid situations where the same algorithm would work fine on one Intel processor but not on an ARM processor, or an AMD processor, or a different model of Intel processor, or vice versa. You find that knowledge in the Intel manuals.

But starting at page 1 and reading to the end is not the right approach. I'd do one pass skimming through it so that you know what's in the manual, and then leave it on your desk whenever you need it.
> 2 votes

# Answer
You don't become an OS developer in a few days, but in years. And most probably you will never become an OS developer for the highly complex x86 architecture at all. This takes whole teams of specialists. Nowadays the major OSes for this platform (Linux & Windows) are there and there's no need for others.

This said, an OS is built with a little of assembly code for the most critical/hardware dependent parts and that takes deep understanding of the most difficult part of the manual related to memory management, interrupt handling, kernel modes and other technicalities. The rest of the code is written in a higher level language such as C and the compiler will take care of the translation to assembly somewhat out of your control. So a great deal of the manual is irrelevant for you.

To develop skills in OS development, you should start by reading theory, and work on projects for simpler architectures or even pure software simulations.
> 1 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Finding a 2SAT instance that has a specific solution set
Is there a 2SAT instance of variables $(a,b,c,d,e,f,g)$ that has exactly the solution set $S=\\{ (1,0,0,0,0,0,0),(0,1,0,0,0,0,0),(0,0,1,0,0,0,0),(1,1,0,1,0,0,0),(1,0,1,0,1,0,0),(0,1,1,0,0,1,0),(1,1,1,1,1,1,1) \\}$? It sounds plausible, but other than enumeration, I can't seem to find a way to prove/disprove that it exists.

# Answer
Let me teach you a systematic way to answer this type of question.

First, write a program to enumerate over all possible clauses, test for each whether it is satisfied by every assignment in $S$, and keep the ones that are satisfied. There are only $O(n^2)$ possible clauses, where $n$ is the number of variables, so this is feasible.

Next, create a formula $\varphi$ by taking the conjunction of all of those clauses. By construction, every assignment in $S$ is satisfied by $\varphi$. Test whether there is any other satisfying assignment to $\varphi$. If there is, the answer is that there is no formula whose solution set is exactly $S$. If there is not, then you have found that there is such a formula, and $\varphi$ is one such.

Since this is your exercise, I will let you write out the details of the proof for why this algorithm works, and how to test whether there is any other satisfying assignment to $\varphi$ (see, e.g., Finding all solutions if you can find one, Rina Dechter and Alon Itai, UC Irvine tech report, 1992-09-16; or Network Flow and 2-Satisfiability, Feder, Algorithmica 1994, vol 11, pp.291--319, Section 8; or just use a SAT solver).
> 1 votes

# Answer
Let $\varphi$ a 2CNF with $S$ as solution set.

* Since $(1,1,1,1,1,1,1)$ satisfies $\varphi$, each clause must contain a positive litteral.
* Since $(1,0,0,0,0,0,0)$ satisfies $\varphi$, each clause must contain either a negative litteral $\neq a$ or $a$.
* Since $(0,1,0,0,0,0,0)$ satisfies $\varphi$, each clause must contain either a negative litteral $\neq b$ or $b$.
* Since $S \neq \\{0,1\\}^7$, no clause can contain a variable and its negation.
* Since $(0,0,1,0,0,0,0)$ satisfies $\varphi$, there is no clause $(a\lor b)$ in $\varphi$ (and neither $a$ alone or $b$ alone).

Using the above properties, we conclude that each clause contains a positive litteral and a negative litteral.

But the last claim prove that $\mu = (0, 0, 0, 0, 0, 0, 0)$ satisfies $\varphi$. Since $\mu\notin S$, we conclude by contradiction that such a $\varphi$ cannot exist.
> 1 votes

---
Tags: satisfiability, counting, 2-sat
---


# Question
Title: Are there any implementations of algorithms on hardware that are (nearly) optimal?
Consider the notion of optimal implementation as follows. Suppose we have some algorithm $A$ whose execution for some problem of size $N$ requires $T(N)$ operations (e.g. arithmetic operations). A library optimally implements this algorithm when it executes a routine for implementing the algorithm for a problem of size $N$ on a CPU (or some other hardware), the CPU performs exactly $T(N)$ operations. That is, algorithm A is optimally implemented on a CPU if the routine has exactly 0 overhead. More generally, one might say that it implements it nearly optimally if there is some small fraction of overhead.

When looking around for examples, I believe to have found only one analysis of a nearly optimally implemented algorithm (namely the Smith-Waterman algorithm on GPUs here). In this case, they find that the algorithm requires 11 operations per cell update, so a GPU that can perform X integer operations/second should be able to execute X/11 cell updates per second. They find that their routine gets 70% to the X/11 number and is therefore quite close to optimal.

I'm interested in having examples of other algorithms that have been shown to be near-optimally implemented on some hardware platform. Other pointers for how I can find relevant examples would also be appreciated.

# Answer
> 2 votes
As far as I understand your question, there is no such concept. The "minimum" number of operations to achieve a given task is completely dependent on the instruction set of the particular CPU. And if you don't limit yourself to existing CPUs, many options remain for custom designs (FPGAs, ASICs...), where the minimum is not even always defined, as it can depend on some design decisions and additional criteria, as well as on the measurement unit.

It is for a similar reason that algorithm complexities are usually estimated to an arbitrary factor (the "hidden constant" in BigOh). So there are no studies on this topic, except in very narrow cases/private circles. (Should I add that researchers will more often be after - or claim - optimal solutions rather than near-optimal ones.)

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


# Question
Title: Measuring and maintaining the diversity of individuals in Genetic Algorithm
While I was using the Genetic Algorithm to generate full correct Sudoku grids starting from a population of random grids, I occasionally face the problem of the process being stuck on a local maxima until the population loses its diversity.

So, I decided to find a mechanism for maintaining the diversity of the population to avoid the problem. What I thought about was:

* Measuring the diversity of each individual by computing how different it is from the rest of the population:

For each individual $i$ : $$diversity\_i = \sum\_j distance(i, j)$$ and I used the hamming distance as the $distance$ function.
* Ranking the individuals (for selection) based on both their diversity and their fitness.

I faced two problem with this approach:

1. Computing the diversity this way is expensive as it requires $n^2$ call to the $distance$ function (which is itself not a constant time function), raising the following question: what is a relatively optimal way for measuring the diversity of a population?
2. How to rank the individuals of a population based on both diversity and fitness?

# Answer
> 10 votes
> How to rank the individuals of a population based on both diversity and fitness?

You can combine diversity and fitness into a single score: $$score(i) = fitness(i) + k \cdot diversity(i)$$

It's a standard approach and doesn't require significant changes to the algorithm. Unfortunately $k$ is **problem-specific**.

---

Alternatively change the standard GA to a multi-objective evolutionary algorithm (MOEA).

This needs a lot of changes (e.g. the algorithm now needs to maintain a set of Pareto optimal individuals).

MOEA is probably a overkill for what you're doing. Indeed it's very interesting and a good training.

---

> Computing the diversity this way is expensive... What is a relatively optimal way for measuring the diversity of a population?

The genotypic / structural approach to diversity isn't the only workable one.

Instead of measuring how differently the individuals look like, measure how differently those individuals behave (***phenotypic diversity***).

A great advantage is the ease of computation: often an acceptable approximation is the simple fitness value.

Schemes like Fitness Uniform Selection / Fitness Uniform Optimization generate selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness:

*Evolution of the population under FUSS versus standard selection schemes (STD): STD may get stuck in a local optimum if all unfit individuals were eliminated too quickly. In FUSS, all fitness levels remain occupied with “free” drift within and in-between fitness levels, from which new mutants are steadily created, occasionally leading to further evolution in a more promising direction (from **"Fitness Uniform Optimization" - Marcus Hutter & Shane Legg**).*

# Answer
> 4 votes
What you suggest is OK, but should be done with caution. After all, there is no functional difference between keeping the population from converging on a local peak and keeping the population from converging on the global peak.

One approach is to use this variant of **@manlio**'s formula $$\mathrm{score}(i) = \mathrm{fitness}(i) + k(g)\\, \mathrm{diversity}(i)\\,,$$ where now instead of a scaling constant $k$ we apply a scaling function $(g)$ that decreases with increasing generation number $g$. The idea is that initially $k(g)$ is high, keeping diversity up, but drops with time as the population becomes more and more likely to have generated a point in the vicinity of the global peak, allowing convergence to that peak.

Of course, like all suggestions, this one comes with no guarantees.

# Answer
> 1 votes
Here's a thought, not tried, and not backed up by literature. But at least it's more computationally efficient than your current approach. If anyone has thoughts or references, please leave a comment.

I'll assume that your chromosomes consist of binary genes, but an extension to real-valued genes might be possible.

For each gene *g* you could compute the expected value *E*(*g*) of that gene, which is just the average across all individuals. If *g* is 0 in 20% of the population and 1 in the other 80%, then *E*(*g*) would be 0.8. This is an *O*(#individuals × #genes) computation.

The diversity of an individual *i* can then be calculated as the inverse of the probability *P*(*i*) of encountering that individual. For each gene *g* in the individual, compute *P*(*g*); e.g. if *g* is 0 in this individual and *E*(*g*) is 0.8, then *P*(*g*) is 0.2. The final *P*(*i*) is simply the product of *P*(*g*) over all genes. Since this is lower for more "diverse" individuals, we take the reciprocal 1 / *P*(*g*) as a measure for diversity. This is again an *O*(#individuals × #genes) computation.

---
Tags: genetic-algorithms, evolutionary-computing
---


title: How might we hash two trees?

text:
# Question
Title: How might we hash two trees?
Suppose that you had two trees.

Our goal is to convert the two trees into two integers such that two trees are the same if and only if the two integers are the same.

Suppose that we have a function named `leaf_hash()` which converts the leaves of the trees into integers such that for any two leaves `x1` and `x2`, we have `x1 == x2` if and only if `leaf_hash(x1) == leaf_hash(x2)`

I want to convert trees, each having many nodes, into integers so that two trees can be compared for equality.

# Answer
> 1 votes
What you are looking for may be *encoding* instead of *hash*.

This can be done using some steps, however, the corresponding integers may be big.

* given $a$, $b$ two integers, denote $\langle a, b\rangle$ an encoding of the couple $(a, b)$. The expression $\langle a, b\rangle = \dfrac{(a+b)(a+b+1)}2 + a + 1$ is suitable, since it defines a bijection from $\mathbb{N}^2$ to $\mathbb{N}$.
* given a list $\ell = (a\_1, …, a\_n)$ of integers, define $\langle \ell \rangle = 0$ if $n = 0$ or recursively $\langle \ell \rangle = \langle a\_1, \langle a\_2, …, a\_n\rangle \rangle$.
* given a tree $t$, define $\langle t\rangle = 0$ if $t$ is the empty tree, or, if $t = \text{Node}(a, t\_1, t\_2, …, t\_n)$, $\langle t \rangle = \langle a, \langle t\_1\rangle, \langle t\_2 \rangle, …, \langle t\_n\rangle\rangle$.

This is indeed a bijection from trees to integers, and can be used to test equality between two trees. For example, if $t = \text{Node}(5, \text{Leaf}(3), \text{Leaf}(2))$, then $\langle t\rangle = 286909$.

# Answer
> 1 votes
Hash codes will not be identical "if and only if the data is identical". There are more possible trees than possible hash codes, so there will be many trees with the same hash code. What you *need* to achieve: Two trees that compare equal have the same hash code, and two trees with different hash codes don't compare equal.

First question: When do you consider two trees equal? A tree is really just a sorted list, with some structure to find things quickly, and to add and remove items quickly (faster than in a sorted list using an arrow). So I would consider two trees equal if they are each a sorted list of items with equal hash codes. The tree structure can be different, but we usually don't care about that.

You need an algorithm that calculates the same hash value independent of the actually tree structure. You can with brute force just calculate a hash code from all hash values in the tree structure. Or you can find the elements with index k/8, 3k/8, 5k/8 and 7k/8 where k is the number of elements.

---
Tags: trees, hashing
---


# Question
Title: Self referential hash function possible?
Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \\, || \\, y) = y$? In other words, if we concatenate its output with the input, the result will not change.

Furthermore, is there a simple construction for such functions?

## Example

Let $x =$ `"hello"` and $f(x) =$ `"123"`. Then $f($`"hello123"`$) =$ `"123"`.

While on existing hashing algorithms the question of finding the $y$s is clearly hard, it is easy to create hashing functions with a known fixed point (see this answer). This problem is a simple generalization of the fixed point problem, which gives me hope that it is also not much harder.

If security of $f$s is incompatible with the desired property, then how about an $f$ that at least have the uniform $y$ distribution?

## Applications

Hashes of files often serve as "links" to them. Some files can link to other files, and this way loops may come up. The requested hashing functions should be able to handle the loops, whereas common hashing algorithms cannot.

# Answer
Yes. You can construct such a function. Let $g:\\{0,1\\}^\* \to \\{0,1\\}^k$ be any hash function. We will define $f$ as follows. On input $x = x\_1 \cdots x\_n$, compute:

* For $i := 1,2,3,\dots,n$, do:

+ If $i \ge k+1$ and $z\_{i-k} = x\_{i-k+1} \cdots x\_i$, then set $z\_i = x\_{i-k+1} \cdots x\_i$; otherwise, set $z\_i = g(x\_1 \cdots x\_i)$.
* Output $z\_n$.

We define $f(x)$ to be the output of the above algorithm. This defines a function $f$, and you can verify that it satisfies the condition you required. (Why? The idea is we have the invariant that $f(x\_1 \cdots x\_j) = z\_j$, and moreover the if-statement enforces the desired condition.) Moreover, if $g$ is a good hash function, we can expect $f$ will be a good hash function (at the very least, as good as is possible, given the condition you require).
> 4 votes

---
Tags: algorithms, computability, hash, cryptography, fixed-point
---


title: Pipelining without operand forwarding

text:
# Question
Title: Pipelining without operand forwarding
I've been doing the HPC course from Udacity (https://classroom.udacity.com/courses/ud007/l)

One of the problems is as follows (apologies for the image, as I was unable to format this using $\LaTeX$):

Here, we assume a RISC processor. The text says:

> For consistency with the rest of the text, we use MIPS64, the 64-bit version of the MIPS instruction set. The extended 64-bit instructions are generally designated by having a D on the start or end of the mnemonic. For example DADD is the 64-bit version of an add instruction, while LD is the 64-bit version of a load instruction.

Here F,D,E,M and W refer to the five stages in a pipeline i.e Instruction Fetch, Instruction Decode, Execution/Effective Address Cycle, Memory Access and Write-Back Cycle.

Is the give solution correct?

My attempt was:

Here, in the second instruction i.e DADDI , there are only two stalls. But since there is no operand forwarding, I believe the contents of the register be available after they've been written into the register file and so, there should be three stalls.

From what I could understand in this solution, the value from the register file is available after the M stage, before it is written. Is that possible?

# Answer
You *would* be correct, however the question specifically states:

> Assume registers can be written and read in the same cycle, during writeback

This means that in cycle 5, 'W' and 'D' are allowed to occur simultaneously, and there must be some sort of implicit forwarding between the two. In light of these assumptions, 2 stalls is right, not 3.
> 0 votes

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


# Question
Title: Is it possible to write an AND gate using XOR gates?
How could I express an AND gate using only XOR gates ?

# Answer
You cant.

Since $XOR$ is associative, i.e. $(x\_1\oplus x\_2)\oplus x\_3=x\_1\oplus(x\_2\oplus x\_3)$, you can only implement functions of the form $x\_{i\_1}\oplus...\oplus x\_{i\_k}$ where $x\_{i\_j}\in\\{x\_1,x\_2\\}$. This is equivalent to (depending on the parity of the number of instances of $x\_1$ and $x\_2$) either 0, $x\_1$, $x\_2$, or $x\_1\oplus x\_2$, which are not equivalent to AND.
> 37 votes

# Answer
Hmmm. It can't be done with boolean algebra that's for sure, but I could wire one up physically. The trick is wiring one of the inputs to a power lead of an XOR gate.

```
                     I2
                     |
      0  I1          |
      |   |          |
     \|   |/         |
     |\   / |        |
.|---| \ /  |--------/
     \  V  /
      \   /
       \ /
        V
        |
     AND OUTPUT

```

The XOR gate is wired up as a non inverting buffer. The trick involved is that if you wire VCC to GND (or by extension a logic ground), the output is a weak GND.

Disclaimer: this works on the silicon I have, but might not work on all silicon.
> 19 votes

# Answer
No

Consider W the set of the functions that maps {0, 1}×{0, 1} to {0, 1}. For example, the AND gate (denoted by ^) and the XOR gate (denoted by ⊕) are elements of W.

Now, for f ∈ W, define Val(f) in that way:

Val(f) := f(0, 0) ⊕ f(0, 1) ⊕ f(1, 0) ⊕ f(1, 1)

Its possible to prove that Val(¬f) = Val(f) and that Val(f ⊕ g) = Val(f) ⊕ Val(g). Now, let A(x, y) = x and B(x, y) = y two of the elements of W, and note that Val(A) = Val(B) = 0, and that Val(^) = 1

To finish, suppose that ^ can be expressed using only A, B, ⊕ and negations, so we have something like

A ^ B = ¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B))))

and applying Val in both sides, we have

Val(A ^ B) = Val(¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B)))))

1 = ((Val(A)) ⊕ ((Val(B)) ⊕ Val(A))) ⊕ ... ⊕ (((Val(A))) ⊕ ((Val(A) ⊕ (Val(A) ⊕ Val(B)))))

1 = ((0) ⊕ ((0) ⊕ 0)) ⊕ ... ⊕ (((0)) ⊕ ((0 ⊕ (0 ⊕ 0))))

1 = 0

a contradiction.
> 2 votes

---
Tags: logic, boolean-algebra
---