# Question
Title: Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?
I have read this question on compile time gc and what I understand from it is that the compiler wouldn't know if a variable is referenced or not by some other object due to conditional statements (because they are computed at runtime), and that is why runtime GCs are used, as they can dynamically check if a variable is referenced or not. My question is, if a compiler would simulate every conditional statement in a program, could it then always find when a variable has 0 references to it, and then add a delete/deallocation statement?

# Answer
> 9 votes
No, it's not possible for a compiler to do that. Doing so is an undecidable problem.

To get some intuition for why it is hard, consider the combinations of loops and conditional statements. It's not clear how you would simulate all possibilities since you don't know at compile time how long the loop will iterate. (In fact it is impossible, as shown by the undecidability of the halting problem.)

# Answer
> 6 votes
Even without (appropriately) invoking the halting problem, there are situations where this is impossible: for instance when the allocation/deallocation scheme depends on the particular values of the input data, which are unknown at compile-time.

# Answer
> 5 votes
What D.W. said is correct in one way: It is impossible for a compiler in general to decide that at point X in a program, object O is not referenced anymore and can be deallocated.

However, you can (and lots of software does that) use reference counting instead of garbage collection. So you count at runtime how many references to an object O there are, and when the number of references goes down to 0, it is deallocated. That is what happens for practically all MacOS and iOS software.

In this particular case, circular references are not handled as they should be. If object A has a reference to B, and B has a reference to A, both have a reference count of 1 if there are no other references, and will never be deallocated. To solve this problem, they rely on the developer not creating such a situation, and the compiler detecting both situations where a circular reference is created, and detecting situations where it cannot prove that no circular reference is created.

They also support "weak references", that is references that don't keep an object alive. For example, if an array contains 100 objects, and each object has a reference to the array, then those backward references would be typically weak references. So the array can be deallocated if there are no other references than those from the objects that it contains. (And when the array is deallocated, the reference counts of many objects might go to 0, and then those objects are also deallocated).

# Answer
> 3 votes
For a more practical example, imagine writing a program that reads in a graph, performs some operations on it, and prints it out. It's possible a command in the middle deletes a node, dropping half the graph. The only way the program could know to delete the associated memory, however, is to read the graph in, execute the operations, and then trace the graph/memory to find if there's any abandoned parts. That's inherently a run time operation.

# Answer
> 3 votes
> ... if a compiler would simulate every conditional statement in a program ...

You forget about programs that have some input:

Let's say we have two variables: `A` and `B`. Both are pointers (or references) to objects.

If the user presses `X` on the keyboard, a new object is generated and the reference is written to `A`.

if the user presses `Y` on the keyboard, the value of `A` is copied to `B`, so `B` points to the same object as `A`.

Question: Do we have to deallocate an object if the user presses `Y`?

The answer: This depends on what the user typed **before** the `Y`:

If the user typed `Y` before typing `Y` again, the object must not be deallocated because `A` points to the same object. If the user typed `X` before typing `Y`, the object `B` points to (before being overwritten) must be deallocatd.

Your next question could be:

**"What if we store some additional information - such as if the last key pressed was `X` or `Y`"?**

The information you need to store is how often some object is referenced - this means: How many variables point to an object.

The compiler must increment or decrement this value for each object and if the value becomes zero, it deallocates the object.

This approach is really done (e.g. in the GTK toolkit (used in many Linux programs) or in Windows OLE/COM). However, according to Wikipedia, it is less efficient than garbage collection.

And your next question could be:

**"What about programs that do not have input?"**

In this case, what you are suggesting is nothing but **running** the program a first time and using the results for the optimization of the program.

If you have a program which is terminating (halting), you can of course do this.

However, in this case, you could also simply store the output of the program and when running the program again, simply use the saved pre-calculated output instead of doing the calculations again.

---
Tags: compilers, garbage-collection
---


# Question
Title: How do we run programs which are bigger than RAM itself
I know that whenever click on .exe, it will be moved into RAM so cpu can execute machine code line by line. But what if .exe is bigger than RAM?
for eg: I play games which take up more space than my RAM. My RAM is 8gb, but i can still play them. How's that possible

# Answer
For the sake of clarification I'll answer this :

> I play games which take up more space than my RAM. My RAM is 8gb, but i can still play them. How's that possible

Games are typically made up of large amounts of data and less code. Quite a lot of the data will typically be textures and other data related to graphics. It's becoming common for games to have e.g. 50+ GB of mostly data. I have an install of the game Fallout 4 (with some mods) which is about 36 GB in size on the disk however only about 1 GB is executable code.

The computer does not usually need all that data at the same time. When it does it fetches just the data it needs. It will make room by removing (from memory) data it does not think it will need. This is complicated by the common scenario of a CPU with RAM and a GPU with it's own graphics memory on the graphics card. The memory on the GPU (which is specifically designed for GPU operations) will then be the limiting resource not the RAM. There's also a lot of management going on behind the scenes. The CPU/OS will be caching files and parts of files it thinks it needs and managing that caching. The GPU/graphics engine will be also managing the GPU's use of memory particularly textures.

If you don't have enough RAM to load the executable and required library files then the game is unlikely to even launch. In principle an executable can run using virtual memory but in practice the executable will have to at least fit in available free physical memory or the OS is unlikely to even launch it. Where virtual memory comes into play is when it needs to swap between executable code or data which is paged in and paged out. Essentially the OS makes an educated guess as to what it expects to need and what it can let go to free up space.
> 2 votes

# Answer
Your computer's operating system uses memory paging, which addresses this problem by loading only part of the .exe in memory at any one time, based on what parts are currently needed. See also https://en.wikipedia.org/wiki/Virtual\_memory.

That said, in practice, .exe files are rarely larger than the amount of RAM. When you say that games take up more than 8 GB, it's more likely that this size is due to the data that they load. Some programs are written to only load data that they need at any time, and unload it when it is unneeded, so that they don't exceed the amount of RAM you have. If that fails, or if for whatever reason a program loads/uses more data than you have RAM for, memory paging is used to keep in RAM what is currently being used and temporarily store the rest on disk.
> 1 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Show that if a DFA accepts all words of length < 2n then it accepts any word
Is it true that if a given DFA $M = \langle Q, \Sigma, \delta, q\_0, F\rangle$ with $|Q| = n$ accepts all strings $w \in \Sigma^\*$ such that $|w|\leq 2n$ then it accepts any $w \in \Sigma^\*$ ?

# Answer
Suppose that a DFA with $n$ states accepts some word $w$ whose length is at least $n$. According to the pumping lemma, we can decompose $w$ as $xyz$, where $|xy| \leq n$, $y \ne \epsilon$, and the DFA accepts $xy^iz$ for all $i \geq 0$.

See if you can use this to develop a criterion for your problem (determining whether a DFA accepts all strings by checking all strings up to a particular length).
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, does this necessarily imply that for any 2 nodes V1 and V2 in the MST, that the path between V1 and V2 is definitely the smallest weight?

I'm looking at a leetcode problem (https://leetcode.com/problems/minimum-costs-using-the-train-line/), and if you look at the diagram, it is showing a graph which shows the cheapest route to get to each node from the **start node**. However, you can clearly see that the cheapest route doesn't necessarily include the cheapest route **between ANY 2 nodes**

You can see that while 1+8+2+3+5 is the cheapest route from 0 to 4, it is not necessarily the cheapest route from 1 to 2.

So does this mean the MST doesn't necessarily have the cheapest route between any 2 nodes?

By the way, I am NOT looking for the answer to the leetcode problem. I am just linking it as an example of my question.

# Answer
Yes, MSTs usually don't contain the shortest path for any pair of nodes. The simplest example is probably just the MST of 3 nodes connected to each other all with edge weight $1$.
> 3 votes

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


# Question
Title: Is solving Binary String Matching equivalent to Solving All type of string matching?
This might be an irritating, naive question, but please bear with me. If an algorithm/code solves the string matching problem for a binary string, does not it imply that the algo/code actually solves the string matching problem in general?

Because, in hardware everything is converted to `0` and `1` and then calculation is done.

The idea is binary string matching could be easier than the general case, so if we have a faster algorithm we (may) use that in machine code, and obtain faster general solution.

# Answer
Computers work with string encodings which are literally mapping of symbols to binary strings. As a practical matter, real computers use fixed size registers and and string matching algorithms implemented on those computers are working with register-sized data anyways.

Of course you can build a special purpose computer for bitstring processing (eg. special hardware for processing say DNA sequences), you are only going to get a constant factor improvement, if any. i.e., the same algorithm operating on bitstrings and general strings will have same asymptotic complexity.
> 0 votes

# Answer
String matching performed bit by bit would be much slower than character by character, because a character is made of 8 or 16 bits and a processor can handle them in a single go.

Also note that string matching is based on comparisons, that conclude "equal" or "different", whether the symbols are bits or characters (or anything else). For this reason binary string matching is not easier than character string matching.
> 0 votes

---
Tags: algorithms, computability, strings, binary, assembly
---


# Question
Title: Are really only ~1% of the physical CPU space used for computing
In a Talk by Herb Sutter C++ and Beyond 2012: Herb Sutter - atomic Weapons 1 of 2 at 46:30 the point is made that only around 15% of the physical space (or the transistors) on a CPU do actual processing while the rest is basically just caches.

Further it is mentioned that of those 15%, only around 1% account for actual processing while the rest contains the logic for e.g. out of order execution, branch prediction, pipelining etc.

This is the slide shown:

In the bottom right corner the source is shown to be from 2004 (the talk itself is from 2012).

Now my question is:

**Is this statement true for modern processors as well or did the ratio change significantly in either direction?** And are there any more sources that show this (either for old or for new CPUs)? When I tried to find more information I mostly found articles about cache sizes and how it matters or not matters but that is not what I am interested in.

# Answer
I don't have any numbers for you, but that's partly because I don't know what Herb Sutter meant by "actual processing". What I think he meant is, essentially, ALUs. So you have to consider what you're comparing with.

This is a die shot of the Intel 8086, a top-of-the-line CPU from 1978.

What I want you to notice about this is that about 2/3 of the die is control logic, and only about 1/3 (over on the left) is the data path, and about half of that is the register file. There is a lot of die space on the right-hand side that isn't occupied by wires, transistors, and pads, so this may be a little tricky to estimate, but it seems to me that only about 10-15% of the die space seems to be used for "actual processing", if by that you mean ALUs.

So that 1% figure is 10% of 10%. When you put it that way, it doesn't seem like such a small number, at least to me.

Alternatively, let's say you do count the register file as "actual processing". Computation doesn't really "happen" inside it (not in a modern CPU, anyway), but it's pretty important; if you got rid of cache, the CPU might go much slower, but if you got rid of the register file, it wouldn't work at all.

Then consider that modern register files are multi-ported for superscalar execution, and expanded for register renaming, and this all consumes die area. How much of that is it fair to assign to "actual computation"?

The Itanium may be a bit of a special case. Just consider its user-visible register set, which is quite something:

* 128 64-bit general-purpose registers. (Or possibly 127; register 0 was hardwired to the value zero as with MIPS.)
* 128 82-bit floating point registers. (Again, two are hardwired to constants.)
* 128 64-bit special purpose "application registers".
* 8 64-bit registers just used for the targets of indirect branches.
* 64 1-bit predicate registers.
* A whole bunch of other stuff that you may not think of as "registers" (e.g. performance monitoring counters), but is still part of the "stored state" when you context switch.

The Itanium also has an unusual approach to register spilling. When you have so many registers, you almost never need to spill registers except when performing function calls. But the Itanium avoids that too by managing general and floating-point registers as a stack (similar to SPARC), and spilling those "stack frames" *implicitly* behind the scenes, automatically during spare memory cycles.

Is this "actual processing"? Arguably not, but it's not just a performance issue, it is part of the CPU's user-visible semantics.

The Itanium is unusual in how much of the CPU implementation is exposed to the programmer. Other CPUs go the opposite route: a lot of the non-"actual processing" circuitry there is to *hide* the caches and the speculative execution. Well, up until you get a Spectre-like vulnerability that exposes the detail by accident...

A few things have changed since 2004. Increasing transistor density influences the design of functional units, sometimes in strange ways.

Consider an integer adder. One of the things we learn early on is how to manage ripple carry as the width of an adder gets larger, through look-ahead. Modern thinking is to use a fast single-cycle circuit which works on 95% of addition problems, and then use a second cycle to "repair" the answer if it turned out to have a difficult carry pattern. You can think of this as yet another form of speculative execution, so it's getting much more difficult to see where that stops and "actual processing" begins.

Another thing that's changed is the rise of SIMD. Wide vector units allow CPU designers to add more arithmetic and logic for the essentially the same amount of instruction decoding overhead; one add instruction might trigger 4-8 parallel additions. But it does mean that some busses also need to be wider.

Finally, many CPUs have ubiquitous integrated GPUs, which complicate the "processing vs overhead" calculation further.

One last comment is that you have to remember is that people have to design and manufacture these CPUs, and CPU design is also influenced by what we can physically build. When you have 6 billion transistors to place, it's inevitable that they are designed from units that can be designed once and then replicated a lot, whether that's putting multiple cores on a die or putting in large arrays of cache memory.

The fabrication process is not perfect, either; a lot of CPUs are thrown away because they failed testing, and others are packaged and sold as lower-grade chips (e.g. lower speed, fewer cores) if they only partially failed. Some kinds of circuit are easier to test than others, and at least some of the die space is used by test infrastructure which is never used outside the factory.
> 3 votes

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


# Question
Title: Comparing automata sizes given Myhill-Nerode equivalence under a function
Consider two finite languages, $L\_A$ over alphabet $A$ and $L\_B$ over alphabet $B$. $A$ might be the same as $B$.

Since $L\_A$ and $L\_B$ are finite languages, there exist minimal acyclic deterministic finite-state automata to decide them: $M\_A$ and $M\_B$ respectively. So $x \in L\_A$ iff $M\_A$ accepts $x$, and $y \in L\_B$ iff $M\_B$ accepts $y$. We are also given that $L\_A$ is bigger than $L\_B$: $|L\_A| \> |L\_B|$.

We are given a function $f:A^\*\to B^\*$. We also have the constraint that acceptance is preserved under $f$: $\ \ x \in L\_A$ iff $f(x) \in L\_B$ \[modeled below by formula $\eqref{eq1}$\]. It was established by the answer to my previous question that if two strings $u$ and $v$ map to the same Myhill-Nerode equivalence class in $B^\*$ under $f$ \[modeled by formula $\eqref{eq2}$\], they map to the same equivalence class in $A^\*$ \[modeled by formula $\eqref{eq4}$\]. This was done by showing that formula $\eqref{eq3}$ follows from $\eqref{eq1}$ and $\eqref{eq2}$, and $\eqref{eq4}$ follows from $\eqref{eq3}$.

$\forall x\in A^\*\ \ ((x \in L\_A) \leftrightarrow (f(x) \in L\_B)) \tag{1} \label{eq1}$

$\forall z\in A^\*\ \ ((f(uz) \in L\_B) \leftrightarrow (f(vz) \in L\_B)) \tag{2} \label{eq2}$

$\forall z\in A^\*\ \ ((uz \in L\_A) \leftrightarrow (f(uz)\in L\_B) \leftrightarrow (f(vz)\in L\_B) \leftrightarrow (vz\in L\_A)) \tag{3} \label{eq3}$

$\forall z\in A^\*\ \ ((uz \in L\_A) \leftrightarrow (vz \in L\_A)) \tag{4} \label{eq4}$

Questions: Given the constraints and results above, can we conclude that $|M\_A| = |M\_B|$? $|M|$ is the number of states in the finite automaton $M$. Is the reasoning below correct?

I think this would be true, because if it were not, there would be a counterexample where two strings $u$ and $v$ would map to the same state in one automaton but two different states in the other automaton.

Case 1. There are two strings $u$ and $v$ which map to one state in $M\_A$ but two states in $M\_B$. So $uz \in L\_A$ and $vz \in L\_A$ and $f(uz) \in L\_B$, but $f(uz) \notin L\_B$. This violates formula $\eqref{eq1}$ under the substitution $x \mapsto uz$.

Case 2. There are two strings which map to one state in $M\_B$ but two states in $M\_A$. So under this assumption, there would exist $u$ and $v$ such that $f(uz) \in L\_B$ and $f(vz) \in L\_B$ and $\ uz \in L\_A$ but $vz \notin L\_A$. This also violates formula $\eqref{eq1}$, under the substitution $x \mapsto vz$.

# Answer
> 0 votes
> It was established by the answer to my previous question that if two strings $u$ and $v$ map to the same Myhill-Nerode equivalence class in $B^\*$ under $f$ \[modeled by formula (2)\], they map to the same equivalence class in $A^\*$ \[modeled by formula (4)\] ...

No, formula (2) does not describe the condition that two strings $u$ and $v$ in $A^\*$ are mapped to the elements that belong to the same Myhill-Nerode equivalence class in $B^\*$. The correct formula that describes that condition should be

$$\forall z\in B^\*~((f(u)z \in L\_B) \leftrightarrow (f(v)z \in L\_B)) $$

Hence I am afraid this question does not make much sense.

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


# Question
Title: Myhill-Nerode equivalence classes of $\{1^n0^n\}$
I have the following task and its solution.

**Question**

> Given the language
>
> $$ A \triangleq\left\\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\\} \text { with } \Sigma\_{A} \triangleq\\{1,0\\}, $$
>
> give all equivalence classes of the Myhill-Nerode relation.

**Solution**

> * $\[1^k\]\_{\equiv A} = \\{1^k\\}$ for $k \in \mathbb N$.
> * $\[1^\ell0\]\_{\equiv A} = \\{1^{\ell+i-1} 0^i \mid i \geq 1\\}$ for $\ell \in \mathbb N^+$.
> * $\[0\]\_{\equiv A} = \\{ 0x, 1^n 0^m, x01 y \mid x,y \in \Sigma\_A^\* \land n,m \in \mathbb N^+ \land m \> n \\}$.

What are they doing in the second bullet of the solution?

The first and third bullets are clear. In the first they construct the equivalence classes of all $1$'s including $\lambda$.

In the third bullet they construct just one equivalence class with all the words which are not in the language $A$.

But what are they doing in the second bullet? What does the exponent $\ell+i-1$ mean? Why don't they write $\[1^n0^m\]\_{\equiv A} = \\{1^n 0^m \mid n,m \in \mathbb N^+\\}$?

# Answer
> 3 votes
I think it makes sense to answer your subquestions out of order.

---

> Why they don't write $\[1^n0^m\] = \\{1^n 0^m | n,m \in N^+\\}$

They're supposed to be equivalence classes. $\[1^n0^m\]$ would break up lots of classes, and duplicate lots of the states from line 3.

---

> What does the Exponent $n+i-1$ mean?

Firstly, $n+i-1 \ge i$, so there are at least as many $1$s as $0$s.

Secondly, $n$ is the parameter which defines the class.

So $\left\[1^{\mathrm{l}}0\right\]\_{\equiv \mathrm{A}}$ is the set of states which need $0^{l-1}$ to reach the accepting state.

# Answer
> 2 votes
There are infinitely many equivalence classes:

* For each $k \geq 0$, the equivalence class of $1^k$, which consists only of $1^k$.
* For each $\ell \geq 1$, the equivalence class of $1^\ell 0$, which consists of $1^{\ell-1+i} 0^i$ for all $i \geq 1$.
* All other words (the equivalence class of $0$): words beginning with $0$, words containing a substring $01$, and words of the form $1^n0^m$ with $m \> n$.

The last equivalence class is easiest to understand: it consists of those words which cannot be extended to words in $A$.

The equivalence class of $1^\ell 0$ consists of all words whose only extension in $A$ is by $0^{\ell-1}$.

Finally, $1^k$ can be extended to a word in $A$ by adding $1^j 0^{k+j}$ for arbitrary $j \geq 0$.

Using this, it is easy to check that all of these equivalence classes are actually distinct. In particular, it is definitely not true that all words of the form $1^n 0^m$ belong to the same equivalence class, if only since some of them belong to $A$ and some don't.

# Answer
> 0 votes
If you have parsed the input $1^l 0$ then to get a string in the language, we must have l ≥ 1, and the only possibility is to produce $1^l 0^l$, so the prefix $1^l 0$ has only one possible suffix $0^{l-1}$. The set of possible suffixes is $\\{ 0^{l-1} \\}$, for l ≥ 1.

Now which other prefixes can be turned into a string of the language by adding a string of the form $0^{l-1}$? That's the strings where we have k more 1s and k more 0s, so $1^{l+k} 0^{1+k}$. These are exactly the strings where adding l-1 more 0's produces a string in L and adding any other suffix doesn't: $1^{l+k} 0^{1+k} 0^{l-1}$ = $1^{l+k} 0^{l+k}$ which is in the language.

I personally find it easier to find the possible sets of suffixes. There are quite obviously three kinds of suffix sets: If you have parsed k 1's so far, you can add another n 1's for a total of n+k 1's, and then n+k 0's. So you have a set of suffixes $\\{ 1^n 0^{k+n} \\}$, n ≥ 0. For each different k, you get a different set of suffixes.

If you have parsed k 1's and n 0's, for 1 ≤ n ≤ k, then you cannot add another k; to get a string in the language you need to add exactly $0^{k-n}$, one choice only. k-n can be any integer, so for every different value of n-k we get a different set containing exactly one suffix.

And finally if we parsed k 1's and either n \> k 0's, or 1 ≤ n ≤ k 0's followed by a 1, or either followed by more symbols, then there is no way to get a string in L, so the set of suffixes is the empty set.

In total, we have an infinite number of different sets of suffixes (which implies L is not regular). If we only wanted to show that L is not regular, we didn't have to calculate all the sets precisely. It is enough to state that $1 1^k 0$ can only be extended to a string in L by adding k 0's, so we have an infinite number of sets of suffixes, and an infinite set of equivalence classes, and no regular languages, even if we didn't bother to figure out these sets and strings exactly.

---
Tags: formal-languages, regular-languages
---


# Question
Title: prove that there does not exist a Turing machine with a particular property
> Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite.

> The above question came from a set of final practice problems for a computability course.

Suppose such a Turing machine M exists. Maybe one can contradict known theorems about decidability (e.g. the halting problem isn't decidable). Or perhaps Rice's theorem might be useful? Clearly the class of languages $L(K)$ so that $L(K)$ is infinite is nontrivial, so by Rice's theorem, the language $A := \\{\langle M\rangle : L(M)\text{ is infinite}\\}$ is undecidable. It might be possible to use the Turing machine M to decide A. M can be used to decide the language $B := \\{\langle M\rangle : L(M)\text{ is infinite and M halts on all inputs}\\}$. But the problem is that $M$ may not halt even if the input is of the form $\langle K\rangle$ for some Turing machine K.

# Answer
> 1 votes
The language of all Turing machines $T$ that do not halt on empty input is well-known to not be recognizable.

If the Turing machine $M$ of your question existed then you could decide the above language as follows:

* Generate (the description of) a Turing Machine $K$ that, on input $x$, simulates $T$ on empty input for (up to) $|x|$ steps. If the simulation of $T$ does not halt within the $|x|$-th step, then $K$ accepts. Otherwise $K$ rejects.
* Invoke $M$ with input $K$. $M$ accepts if and only if $L(K)$ is infinite, i.e., if and only if $T$ does not halt on empty input.

---
Tags: formal-languages, turing-machines, undecidability, halting-problem
---


title: Page fault question

text:
# Question
Title: Page fault question
How many page faults are there in the following accesses of pages in case of FIFO mechanism where page frame size is 8? $$11,21,23,53,8,7,10,3,3,38,3,37,7$$

Soln: This question appeared in one of my the entrance tests for a company and I am pretty sure I got it right but there was no option matching what I had thought. Am I going wrong somewhere?

My approach: first 8 will fail next when we replace the new ones we shall replace from the beginning since FIFO mechanism, so basically we first search for the newly found page in the frame and if not present we pop off the first one from the frame and add new ones at the back. Is this right?

# Answer
| Page Number | Frame Contents | Page Fault |
| --- | --- | --- |
| 11 | 11 | +1 |
| 21 | 11, 21 | +1 |
| 23 | 11, 21, 23 | +1 |
| 53 | 11, 21, 23, 53 | +1 |
| 8 | 11, 21, 23, 53, 8 | +1 |
| 7 | 11, 21, 23, 53, 8, 7 | +1 |
| 10 | 11, 21, 23, 53, 8, 7,10 | +1 |
| 3 | 11, 21, 23, 53, 8, 7, 10, 3 | +1 |
| 3 | **11**, 21, 23, 53, 8, 7, 10, 3 |  |
| 38 | 38, 21, 23, 53, 8, 7, 10, 3 | +1 |
| 3 | 38, **21**, 23, 53, 8, 7, 10, 3 |  |
| 37 | 38, 37, 23, 53, 8, 7, 10, 3 | +1 |
| 7 | 38, 37, 23, 53, 8, 7, 10, 3 |  |

Total Page Faults=10.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Performance of smooting vs viterbi algorithm with HMMs
To experiment, I implemented a discrete HMM; the transition matrix and emission model are randomly, uniformly generated. Then, a sequence of random states and emissions are produced by the HMM. Then I run smoothing (forward-backward algorithm) to identify the most likely states at each time. Finally I run the viterbi algorithm to identify the most likely sequence.

Because I know the true sequence of states, I can compare how well the two algorithms predict the actual sequence. With #states = 2, #emission types = 2, and sequenceLength=100, viterbi gets about 60% of the states correct, while smoothing gets about 73% correct.

Does this make sense? My prior was that viterbi would get more correct than smoothing, but I'm relatively uncertain. Also, it seems disappointing that viterbi is only 10% better than random guessing. I'm wondering if there's a bug in my implementation.

Any confirmation one way or the other would be greatly appreciated.

# Answer
> 0 votes
Viterbi is not necessarily always better than smoothing. Viterbi returns the MAP estimate, but for some region in the input space, there might be too high of uncertainty that it is better to go with the "reject option". This is mentioned in Kevin Murphy's "Machine Learning: a probabilistic perspective" section 17.4.1, and I quote:

> It is not surprising that smoothing makes fewer errors than Viterbi, since the optimal way to minimize bit-error rate is to threshold the posterior marginal.

I can't say I completely understand this issue with Viterbi, but wanted to share nontheless i

---
Tags: hidden-markov-models
---


# Question
Title: Why do we need to "allocate" an amount of space in the context of space-complexity?
In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146):

> It is tempting to say that sub-logarithmic space machines are not more useful than constant space machines, because it seems impossible to allocate a sub-logarithmic amount of space. This wrong intuition is based on the presumption that the allocation of a nonconstant amount of space requires explicitly computing the length of the input, which in turn requires logarithmic space. However, this presumption is wrong: The input itself (in case it is of a proper form) can be used to determine its length (and/or the allowed amount of space)

It then goes on to say that not DSPACE(O(1)) = DSPACE(O(log(n))) as this wrong intuition would let us believe, but rather DSPACE(O(1)) = DSPACE(O(log(log(n)))), I think because we can encode the input length in the input itself.

However, I don't understand what this paragraph is even about in the first place. E.g. what does "allocating" space resources even have to do with space complexity? Most algorithms I know don't "allocate" any space resources, they just use it, and they don't need to know the length of the input explicitly. E.g. to add two integers, we can just start adding the final bits together, taking over the carry, and so forth. We don't first "compute the length of the input".

**Could someone explain why we would need to "allocate" space, and thus why either DSPACE(O(1)) = DSPACE(O(log(n))) or DSPACE(O(1)) = DSPACE(O(log(log(n)))) is even plausible in principle?**

# Answer
> Most algorithms I know don't "allocate" any space resources, they just use it, and they don't need to know the length of the input explicitly

The statement that "Most algorithms I know don't 'allocate' any space resources, they just use it" is red herring, since most algorithms use space beyond input and output.

* Without space beyond read-only input and write-only output, an algorithm is equivalent to a finite state machine.
* Without space beyond readable-and-writable input and write-only output, an algorithm is equivalent to a linear bounded automaton.

Note that we, or the book *Computational Complexity: A conceptual perspective* by Goldreich considers the space beyond input and output must have been allocated in this discussion, whether implicitly (as "they just use it") or explicitly (such as described below).

How do most algorithm "allocate" space? Or, in equivalent terms, how do most algorithm find and use space other than the input and output?

Let us ignore the algorithms that "allocate" $O(1)$ auxiliary space, since they are irrelevant to this investigation.

Let us consider the algorithm that "allocate" more than $O(1)$ auxiliary space, i.e., some space whose size is not bounded by a constant. In other words, we are considering dynamic memory allocation.

In the model of Turing machines explicit memory allocation is rarely seen, since a Turing machine enjoys unbounded memory by definition. Extra memory will be used by an algorithm as they become needed. (However, "extra memory" used implies none other than memory allocation.)

Hence, the initial (correct or wrong) intuition for memory usage pattern does not come from the descriptions of algorithms by Turing machines. Instead, those intuition come mostly from people writing programs in pseudocode, c/c++ that deal with memory allocation explicitly.

A dynamic memory allocation requires a size as a parameter. This size should not be a constant; otherwise, we can use static memory allocation.

How does a variable size arise? One of the most common variables that come from input is the length of the input. So it is natural that a variable size might be computed from the length of the input.

* For example, allocate an array that is as large as the input array as the working space to sort the input array.
* For example, allocate an array of size that is the same as the number of given edges to track whether edges have been visited or not.
* (May I say there are too many examples...)

Hence, Goldreich refers to "the allocation of a nonconstant amount of space" that "requires explicitly computing the length of the input" as a natural "presumption". Or so I understand.

Of course, we should mention, as Goldreich pointed out, that intuition is wrong.
> 2 votes

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


# Question
Title: What is ridge in hill climbing algorithm?
I am studying hill climbing algorithm and this topic seems so confusing.

1. What is ridge basically?
2. Can you show an example while searching using hill climbing when ridge occurs?

I have researched in internet about this topic but it only left me with more confusions. It seems like ridge seems very similar to local maximum imo. In the sense there are some big hills later on. But it says a lot of other things which I found very confusing. Need some help here. Here is the pdf that I collected by studying from various sources.

I would like to visualize and understand this figure-:

I have collected some resources for studying this topic. If It is legal to share it here is it-:

https://jmp.sh/OMZtkWF

I first asked this in other forums here are responses from other forums that I didn't understand that deeply-:

My confusion with this is that-:

> if that's the case all of hill climbing is filled with ridge. i don't understand this. its name is hill climbing but it says that it can only travel in x or y directions. what does this mean..if we are in a steep hill then how can we travel only x direction or y direction, how can maxima and minima exists in that case if we are moving only in x or y direction? i don't quite get it. Also you say every direction we are allowed to move in sends us downhill. From which point are you talking can you show that in that above figure?

Sadly the guy could not elaborate further so I am here on stackexchange. That conversation is just for reference, no need to answer that, just to get you a view of what I am confused.

# Answer
> 2 votes
Ridges are maxima that are very elongated in one direction. When you sample such a function, the sampling points will not fall exactly on the ridge line and will "fluctuate randomly", giving the impression of numerous local maxima.

# Answer
> 0 votes
ridge \[rɪdʒ\] NOUN a long, narrow hilltop, mountain range, or watershed: "the North-East ridge of Everest" synonyms: mountain · hill · height · alp · aiguille · serac · puy · crag · tor · inselberg · \[more\]

by looking at the definition of "ridge" I think we can simply understand it as a hill. although we need to keep in mind that there could be more than one ridges in the plot. some of these ridges will be the local optimum (lower ridges) and only one can be the true optimum (highest ridge)

---
Tags: algorithms, artificial-intelligence
---


# Question
Title: Are there adaptive algorithms/data structures for sparse and non sparse vectors?
A sparse 1D array of integers is commonly encoded as pairs of \[index, value\], which consumes 2 memory spots per value.

A dense 1D array is commonly encoded as a linear array of values \[value1, value2, ..., valueN\], consecutive in memory.

If an array is encoded as a sparse array, but grows in density, until it becomes dense, then it uses 2X the memory of the array encoded as a dense array.

The question is, is there an encoding that gradually changes from sparse to dense, without wasting memory, and being fast to randomly read and write?

For example, to manage arrays which may be sparse or dense, anything in the middle, and change sparsity as they get manipulated.

# Answer
> 3 votes
Consume M + 2 slots per each continuous sequence of M values in sparse array: \[index, length, value1, value2, .., valueM\]. When you append a new value to a sequence check if it is possible to join the next sequence to this one.

If N is the high index of the array it will consume N + 2 slots when fully filled. In the worst case \[value, NULL, value, NULL, value, ...\] the array consumes 1,5N memory slots.

---
Tags: algorithms, optimization, arrays, efficiency, encoding-scheme
---


# Question
Title: Are there pseudorandom number generators (PRNG) with no finite period?
> The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period?

For this question it is not necessary that it be practical or used in real-world implementations.

# Answer
If the state of the PRNG is finite, then it has a finite period. (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite. For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)

In practice, worrying about the period of the PRNG may be akin to arguing over angels on a pinhead. A 256-bit state is large enough that a well-designed PRNG will never repeat within the lifetime of the universe. Therefore, concerns about repetition are pretty much irrelevant for any reasonable, well-designed PRNG.

In practice, the real challenge is to make the PRNG unpredictable (or close enough for the application's purposes); ensuring it won't repeat is much easier, relatively speaking.
> 13 votes

# Answer
Yes, this is possible if you are willing to use unbounded space. Consider a generator that stores every previously generated value in an internal history buffer.

Since every infinite cyclic sequence $S^\*$ (capital letter $S$ representing a finite sequence of outputs, $S^\*$ representing an unbounded repetition of it) must have some prefix $SS$, all that is required is to check if the next output that would be produced would make a sequence $SS$ for any $S$, and produce any other value instead. One can do this by using any underlying PRNG, and modifying outputs when such a length-2 cycle would be detected.

If by 'period' you mean 'period of the suffix', all that is needed is to occasionally drop elements from the front of the internal history buffer before generating a value, say once every other generated value. A proof by contradiction is simple.

Assume this generator generates a sequence with a periodic suffix. The generated sequence must therefore be $PS^\*$ for finite sequences $P$ and $S$, where $S$ is much longer than $P$. Eventually the in-memory history buffer must be $RrR$ (lowercase $r$ representing any single output) where $Rr$ is a rotation of $S$, because the history will at some point have that length and $P$ will have been dropped by that point.

But if the history is $RrR$, $r$ cannot be generated again (by construction), so the period of the suffix must be longer than $S$.
> 0 votes

# Answer
You can easily construct an aperiodic RNG with 2 building blocks:

1. An unbounded counter c as internal state and
2. a (cryptographic) hashing algorithm H().

Then your RNG is H(c) and you increment the state c after every application.

As some others have noted, an aperiodic RNG is a theoretic construct, because you need unbounded memory for its state. This is no difference here, because for an unbounded counter variable, you need unbounded space.

An example for a hashing algorithm is SHA256.

With an extremely unlucky / bad choice for H(), you might accidentally end up with a periodic RNG with this construction. But for certain H() you can prove that they will not have a period. I'll give a very simple example, which is certainly not a good choice for the RNG, but which illustrates the concept:

Use

H(c) = second\_most\_significant\_bit(3^c),

which raises 3 to the power of c and then takes the 2nd most significant bit (because the most significant bit is always 1, thus not random). This 2nd most significant bit of the powers of 3 in binary can be shown to be aperiodic, because log₂(3) is a transcendental number.
> 0 votes

# Answer
To try and answer your question as posed, one possible way to build a PRNG with "no period" would be to have a generator that re-seeds itself periodically by using a subroutine that stores randomly selected output bits and then uses this block of bits as a "new seed" for the generator. So any given seed is only used for a period much smaller than its mathematical potential . So technically the output string is a concatenation of an endless series of generators with "small seeds" that goes on forever. The notion of a period, like the period of a shift register sequence, only has meaning if you assume a fixed seed for the register. If the seed is constantly changing, the notion of a "period" becomes meaningless no matter what the length of the shift register is.
> -4 votes

---
Tags: reference-request, number-theory, pseudo-random-generators
---


title: RAM access time vs cycle time

text:
# Question
Title: RAM access time vs cycle time
About Random Access Memory (SRAM and DRAM), if multiple read or write operation take place, many books calculate the average access time of those operations. Given the definition of access time, I think that it is wrong to talk about access time. If multiple operation take place, I think that would be better to talk about average CYCLE TIME, because the cycle time includes the time that the RAM spent to set-up itself after each operation. Could someone tell me if this reasoning is correct? Thank you

# Answer
Cycle time is usually a constant value representing the time between any two clock ticks. This also defines how many operations we can do in the cpu per second. This value is mostly constant, except for some special cpu-s that don't use clocks.

But the RAM is a totally different object that takes different time for different requests (depending on how you built it, the number of caches, their size, etc...). So a notion of "average time" here in my opinion is much more meaningful than a notion of average clock cycle time. In addition, since a RAM is a totally different entity, it could operate with an external clock, or using some other mechanism. For the cpu it doesn't matter if it provides the same API. This in some sense, is a sort of abstraction of how the cache really works physically, which makes the "average time" even more useful, as we don't always know exactly how much time a request from the RAM will take.
> 2 votes

# Answer
The operations under scrutiny are memory reads and writes, i.e. accesses. So you care about average *access time*.

There is no reason to call that *cycle time* (unless you would be studying the average cycle time, whatever that means).
> 2 votes

---
Tags: cache
---


# Question
Title: Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation
I'm trying to identify an algorithm to solve this computational problem

Input:

* Bipartite graph `(V, W, E)`, with `E ⊆ V×W`
* A fixed order for both `V` and `W`: `V = (v1, ..., vn)` and `W = (w1, ..., wm)`

Output:

* The subset of `E` of maximum cardinality in which there are no crossing edges.

The mental image is that the two vertex sets are arranged in two parallel arrays with edges between them, which may or may not cross. More formally, edges `(vk, wl)` and `(vp, wq)` cross if either 1) `k < l` and `p > q`, or 2) `k > l` and `p < q`.

Does anyone know about any published literature on this problem?

It seems that there is a much larger body of literature on the problem of choosing permutations of `V` and `W` to minimize edge crossing, which is NP-Hard. However, I'm working with a fixed permutation for both sets.

I've also identified a few papers that count the number of edge crossings under a fixed permutation:

However, none of these papers discuss the problem of minimizing edge crossings by removing edges.

There are a few more papers in which the algorithm selects a maximum non-crossing matching under a fixed permutation.

This is closer to the mark since it's maximizing the cardinality of an edge set, but I don't want to restrict the edge set to being a matching. Any leads?

# Answer
> 1 votes
Without loss of generality, assume every vertex has degree 1. Create $\deg(u)$ copies of a vertex $u$, then sort the created vertices in the order of the opposite vertex of the corresponding edge.

Then, the bipartite graph can be represented by a permutation as in permutation graphs. Now, a set of edges in the bipartite graph is non-crossing if and only if the corresponding sub-sequence of the permutation is increasing. This longest increasing subsequence problem is solvable in $O(n \log n)$ time, therefore the original problem is solvable in $O((|V| + |W| + |E|) \log (|V| + |W| + |E|))$ time.

---
Tags: algorithms, graphs, bipartite-graph
---


# Question
Title: Any ideas for Parallel Computing Project?
I have to make an application as my Parallel Computing university course project. The application should make use of parallel processing. Any ideas or examples for these kinds of applications ??

# Answer
Here are a few ideas for your project. You can parallelize an existing sequential algorithm, which one clearly depends on your interest and/or knowledge of the field. You may also exploit this as an opportunity to learn something new.

# Data mining

* CountSketch
* Count-Min
* HyperLogLog
* Space Saving
* Frequent
* Spectral clustering
* BIRCH
* Singular Value Decomposition
* CHARM (closed frequent itemsets mining)
* EM (Expectation-Maximization) clustering
* CPC (Compressed Probabilistic Counting) Sketch
* Q-Digest (quantiles)

# Nature inspired optimization

* Moth-Flame Optimization Algorithm
* Raven Roosting Optimization Algorithm
* Emperor Penguin Optimization Algorithm
* Shark Smell Optimization
* Grey Wolf Optimization
* Fish School Search
* Dragonfly Algorithm
* Bat Algorithm
* GSA (Gravitational Search Algorithm)

# Numerical algorithms

* tridiagonal linear systems
* numerical integration using Romberg’s method
* Matrix Multiplication: SUMMA Algorithm
* FFT
* Snyder Matrix Multiplication
* Fast Hartley Transform
* Bareiss algorithm (for computing the determinant of a matrix)
* Levinson-Durbin algorithm (for linear systems with Toeplitz matrices)

# Puzzles

* solver for the Aristotle's Number Puzzle (magic exagon of order 3)
* solver for Futoshiki puzzle (board 10 × 10)
> 1 votes

---
Tags: parallel-computing, applications
---


title: Confusion about NP vs. LINSPACE

text:
# Question
Title: Confusion about NP vs. LINSPACE
I am working through Sipser, and have come accross the following claim, *"any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$"*, which can be proven by looking at the upper bound on the number of configurations a Turing machine that uses space $f(n)$ can take. An implication of this claim is that a $f(n) = n$ space bounded Turing machine runs in time $2^{O(n)}$, and hence I take it this means that any Turing machine running in time $2^{O(n)}$ is a $O(n)$ space Turing machine.

Now there is an excersise I am doing that asks that you prove that $NP \not= SPACE(n) = LINSPACE$ (see problem 4). Using the logic above from Sipser, I am arguing that if $NP \not\subseteq SPACE(n)$ then there is an NP-complete problem $A$ not in $TIME(2^{n}$). But what would such a problem $A$ look like? I take it that it would need to be a problem in say $TIME(n!)$ or $TIME(n^n)$ (i.e. a language decidable by a superexponential time Turing machine)?

Moreover, as stated in the link, it is unknown if $NP \subseteq SPACE(n)$ or $SPACE(n) \subseteq NP$. So is the reason why we cannot prove $NP \not\subseteq SPACE(n)$ for example because all the known NP-complete problems are in $TIME(2^n)$? For example in subset-sum for a set of $n$ integers there are $2^n$ possible subsets, and indeed all NP-complete problems are similar.

# Answer
The relationships between time and space on which you are relying are not correct. In particular, it is true that

$\forall \ \mathrm{T}(n) \ \mathrm{DSPACE}\_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{DTIME}\_{\mathrm{TM}}\left(\mathrm{T}(n) 2^{O(T(n))}\right.)$

and

$\forall \ \mathrm{T}(n) \ \mathrm{NSPACE}\_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{NTIME}\_{\mathrm{TM}}\left(\mathrm{T}(n) 2^{O(T(n))}\right.)$

This is because a TM that uses $T(n)$ space can have at most $T(n)\cdot 2^{O(T(n))}$ different configurations. However, the converse is not true:

$\forall\ \ \mathrm{T}(n) \ \mathrm{DTIME}\_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{DSPACE}\_{\mathrm{TM}}(\mathrm{T}(n))$

and

$\forall \ T(n)\ NT I M E\_{T M}(T(n)) \subseteq \text { NSPACE }\_{T M}(T(n))$.

Indeed, at each step, a $k$ tapes TM can write on at most $k = O(1)$ previously unwritten cells; therefore, a TM operating in time $T(n)$ can use at most $T(n)$ space.

Having said that, you need to show that $NP$ and $SPACE(n)$ are different sets. For this you may use the well-known fact that $NP$ is closed with regard to log-space reductions (i.e., the reductions used to show that a problem in $P$ is a $P-$Complete problem) and prove that, instead, $SPACE(n)$ is not closed with regard to log-space reductions. For this, you can use the Space Hierarchy Theorem. For the details, please see this answer by @YuvalFilmus.
> 1 votes

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


# Question
Title: Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?
I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.

# Answer
> 0 votes
One solution would be to convert the original graph to a graph with only edge costs, and then use Dijkstra's algorithm.

To do this we can replace a single node with *n* nodes which are fully connected to each other. *n* is the number of edges entering that node.

Note: This solution assumes that weights are non negative.

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


# Question
Title: What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?
# First Few Iterations of the Algorithm

We have an algorithm in which a squirrel visits the nodes of a directed graph.

Our graph has two colors of edges: black and white.

Initially, the graph has black edges only, and no white edges.

The squirrel never changes the color of an edge from black to white. The squirrel simply inserts an additional white edge from time-to-time, or the squirrel deletes a white edge.

Between node $x$ and node $y$ we can have:

* no edges (no black and no white)
* one black edge from $x$ to $y$, but no white edges.
* one black edge from $y$ to $x$, but no white edges.
* two black edges going in both directions, but no white edges.
* one black edge from $x$ to $y$ and a white edge running in parallel
* one black edge from $x$ to $y$ and one white edge in the opposite direction
* one black edge from $y$ to $x$ and a white edge running in parallel
* one black edge from $y$ to $x$ and one white edge in the opposite direction
* two black edges going in both directions, and one white edge going one of the two directions.

There is always zero or one white-edge between two nodes, but never two white edges going in opposite directions.

No matter what iteration of the algorithm we are on, white edges always describe a path beginning at the root node where no nodes are repeated on that path.

Our squirrel begins at the root node. The squirrel will always be stationed at one of the graph's nodes.

We move the squirrel node-by-node to trace an arbitrary path beginning at the root node.

With each step, the squirrel draws a white arc from the node it came from to the most recently visited node.

Initially, our algorithm looks like depth-first search, but it will change later.

The squirrel continues along the path until the squirrel can go no further.

The squirrel can go no further because all successors of the node which the squirrel stops at are already on the squirrel's path. That is, all successors of the current node are the root node or have a white edge going into them.

At this point, the graph contains exactly one white path.

The graph will always have just one white path.

As this point, we order the squirrel to back-trace a short ways, deleting white edges as it goes.

At all times, the graph must contain exactly one white path.

We re-visit the same vertex many times. In particular, we should **leaf-ward** visit node $x$ the same number of times as the number of paths from the root to node $x$.

Leaf-ward visits occur when lengthening the white-path, not shortening the white-path. Shortening the white path is known as back-tracking or a backtrace.

This is not canonical depth-first search of a graph because we do visit the same node many times.

We cannot visit a node if that node is already in the "active" (white) path.

I am stuck (not sure what to do) after the first deep path is constructed.

# Maze Analogy

Suppose you had a maze with a single starting point. I asked you for an algorithm which would provide me with the $(x, y)$ coordinates of every dead-end in the maze.

One is tempted to use something like **depth-first search**.

There are some complications:

* the maze represents an arbitrary graph, not a tree. Our maze contains cycles.
* I require that each dead-end in the maze be visited a number of times equal to the number of distinct paths to that dead-end from the beginning of the maze.

# Question about an Algorithm

Can you describe an algorithm which:

* accepts a ***rooted directed*** graph $G$ as input.
* returns a container (such as a set, array, or linked list) which contains every “***pseudo-sink***” of the input graph.
* Initially, all nodes are painted zero times. If $k$ is the number of paths from the root node to node $x$, then $x$ gets painted by the algorithm (visited) exactly $k$ times before the algorithm returns.

We will eventually provide a mathematically formal definition of a “***pseudo-sink***”.

Informally, a node is a “***pseudo-sink***” if there exists a path going to that node which cannot go any further without repeating a node previously seen on the path.

# Example

Here is a picture of a rooted graph.

The black node is the root-node.
The white nodes are ***pseudo-sinks***.
Grey nodes are not ***pseudo-sinks*** and are not the root node either.

# Definitions

### Definition of “*rooted*

A ***rooted*** digraph is a digraph which has exactly one of its vertices designated as a special “*root node*”.

## Definition of “*Pseudo-Sink*

For any rooted directed graph $G$, and any node $z$ in digraph $G$, we say that $z$ is a “*pseudo-sink*” in digraph $G$ if and only if node $z$ is the end of a ***maximally long*** path originating at the root of digraph $G$.

### Definition of ***maximally long***

For any directed graph $G$, for any node $x$ in $G$, and for any path $P$ in graph $G$ ending at node $x$, we say that $P$ is a “*maximally long*” in graph $G$ if and only if for any node $y$ in digraph $G$, if $(x, y)$ is an edge in digraph $G$, then $y$ is a node in path $P$.

Definition of ***path***: In the definition given above, a path is not allowed repeat any vertices. Also, a path's first node may not be the same as the last node in the same path.

### Definition of ***digraph***

Note that we allow $G$ to have self-loops $\begin{pmatrix}(x,x)\in AS \end{pmatrix}$.
An example of a digraph might have:

* $VS(G) =\begin{Bmatrix} 1, 2, 3, 4 \end{Bmatrix}$
* $AS(G) =\begin{Bmatrix} (1, 2), (2, 3), (2, 4), (4, 4), (3, 2), (3, 3)\end{Bmatrix}$

## Alternative definition of ***Pseudo-Sink***

Let $G$ be a directed graph. Let $r\_{G}$ be the designated root node in digraph $G$.

A ***Pseudo-Sink*** of digraph $G$ is any leaf-node of the “*Path Tree*” rooted at node $r\_{G}$ in directed graph $G$.

**Definition of Path**: Suppose for a moment that for any “***path***$P$ in graph $G$ there exists $m \in \mathbb{N}$ such that $P$ is a mapping from the set $\begin{Bmatrix} n \in \mathbb{N} \cup \\{0\\} : n \leq m \end{Bmatrix}$ to the vertices of graph $G$ such that $\forall a, b \in \begin{Bmatrix} n \in \mathbb{N} \cup \\{0\\} : n \leq m \end{Bmatrix}, b = a + 1 \implies \begin{pmatrix} P\[a\], P\[b\] \end{pmatrix} \in AS(G), \text{ and } a \neq b \implies P\[a\] \neq P\[b\]$

A “*Path Tree*” of digraph $G$ rooted at node $r \_{G} \in G$ is defined to be a tree $T$ such that there exists a mapping $\mathcal{toG}$ from the vertex set of the tree $\begin{pmatrix} VS(T) \end{pmatrix}$ to the vertex set of the graph $VS(G)$ such that all of the following are true:

* There exists a unique tree-node $r\_{T}$ such that $\mathcal{toG}(r\_{T}) = r\_{G}$
* For any tree-path $P\_{T}$, there exist a path $P\_{G}$ in graph $G$ such that $\forall k \in \mathtt{domain}(P\_{T}), \mathcal{toG} \begin{pmatrix} P\_{T}(k)\end{pmatrix} = P\_{G}(k)$
* For any path $P\_{G}$ in graph $G$, there exists a path $P\_{T}$ in tree $T$ such that $\forall k \in \mathtt{domain}(P\_{T}), \mathcal{toG} \begin{pmatrix} P\_{T}(k)\end{pmatrix} = P\_{G}(k)$
* If there are two tree-paths $P\_{T}$ and ${P^{\prime}}\_{T}$ and there exists a path $P\_{G}$ in graph $G$ such that $\forall k \in \mathtt{domain}(P\_{T}), \mathcal{toG} \begin{pmatrix} P\_{T}(k)\end{pmatrix} = P\_{G}(k)$ and $\forall k \in \mathtt{domain}({P^{\prime}}\_{T}), \mathcal{toG} \begin{pmatrix} {P^{\prime}}\_{T}(k)\end{pmatrix} = P\_{G}(k)$ then $P\_{T} = {P^{\prime}}\_{T}$
* if there are two graph paths corresponding to the same tree path then the two graph paths are equal to each-other.

# Notation for Pseudo-Code

In pseudo-code, for any object `x` and function `f` feel free to assume that both of the following are equivalent:

```
result = x.f(y, z)
result = f(x, y, z)

```
* The vertex set of a graph is denoted as $\mathtt{VS}(\mathtt{G})$ and also written as $\mathtt{G}. \mathtt{VS}()$
* We can assume that the following array-like function named $\mathtt{KIDS}$ is included as part of the input graph $G$:

> $\mathtt{KIDS}(\mathtt{Knode} \text{ } \mathtt{vert})$: returns an ordered container to the children of node $\mathtt{vert}$.
> As some example pseudo-code, we might write the following:

```
for KID in KIDS  {
    print(KID)
}

for V in G.VS() {
    print(V)
}

for V in VS(G) {
    print(V)
}

```

The input to our algorithm is not necessarily a tree object. However, we may wish to build a tree as an intermediate step.

* For an ordered tree, $\mathtt{PARENT}(\mathtt{TreeKnode} \text{ } \mathtt{vert})$: returns the parent of node `vert` or `NULL`.
* For an ordered tree, $\mathtt{SIB}(\mathtt{TreeKnode} \text{ } \mathtt{vert})$ returns the eldest sibling of node `vert`. If there is no sibling, then it returns $\mathtt{NULL}$ .

* $\mathtt{SIB}(\mathtt{Knode} \text{ } \mathtt{vert}, \mathtt{int} \text{ } \mathtt{dist})$
    + returns $\mathtt{SIB}(\mathtt{vert})$ if $\mathtt{dist} == 0$.
    + For $\mathtt{d} \in \begin{Bmatrix} n \in \mathbb{N}: n \geq 1 \end{Bmatrix}$, it returns $\mathtt{SIB}(\mathtt{vert}, \mathtt{d} - 1)$

# Answer
Here is a recursive algorithm, written in Python. For simplicity, assume vertices are $0,\cdots, n-1$.

The idea is basically the same as that of the usual depth first search. At each recursive call, the algorithm will explore all paths that starts from the current source node without revisiting any visited nodes. However, when it back-traces from a visited node, it will consider that node as unvisited. This extension of unvisited nodes enables the algorithm to traverse all paths without using exponential working memory.

A squirrel can search a graph/maze by following procedure `complete_dfs` recursively.

* Upon entering the procedure given a pair of `visited_nodes` and `source`, the squirrel will find and remember kids to be explored.
* At `visited_nodes.add(kid)`, the squirrel will move leaf-ward from `source` to `kid`, entering the next level of the procedure with updated `visited_nodes` and `kid` as the new `source`.
* At `visited_nodes.remove(kid)`, the squirrel will back-trace from `kid` to `source`, since `kid` is considered as having been explored for the updated set of visited nodes.

By the way, pseudo-sink and maximally long path can also be defined in an undirected graph. Replacing kids by neighbors, the same algorithm can find pseudo-sinks and numbers of paths of an undirected graph with respect to a source node as well.

```
def compute_pseudo_sinks(n: int, root: int, kids: list[list]) -> set:
    """ kids is a rooted directed graph with nodes 0, ..., n-1
        kids[u] is the list of kids of node u
        Return the set of all pseudo-sinks.
    """

    pseudo_sinks = set()
    painted_times = [0] * n  # painted_times[i] will be the number of paths from root to node i

    def complete_dfs(visited_nodes: set, source: int):
        """ visited_nodes is the set of nodes in a path from the root
            Explore all paths that start from source avoiding visited_nodes
        """
        is_pseudo_sink = True
        for kid in kids[source]:
            if kid not in visited_nodes:
                is_pseudo_sink = False
                visited_nodes.add(kid)
                painted_times[kid] += 1
                complete_dfs(visited_nodes, kid)
                visited_nodes.remove(kid)
        if is_pseudo_sink:
            pseudo_sinks.add(source)

    painted_times[root] = 1
    complete_dfs({root}, root)
    return pseudo_sinks  # , painted_times

# an example
n, r, kids = 5, 0, [[1], [2, 3], [1, 2, 3], [2], [3]]
ps = compute_pseudo_sinks(n, r, kids)
print("pseudo-sinks:", ps)  # pseudo-sinks: {2, 3}

```
> 0 votes

---
Tags: graphs, graph-traversal, colorings, depth-first-search
---


# Question
Title: Is there a hierarchy of computational expressivity that is sensitive to evaluation strategies?
Various computational hierarchies describes the relative expressivity of different classes of languages, machines, or other models of computing, with the classic progression for Automata Theory \[0\] being: Deterministic Finite Automata (DFA) \< Push-Down Automata (PDA) \< Turing Machines (TM). These correspond to the following containment relations in the Computability hierarchy \[1\] of languages: Regular \< Context-Free (CF) \< Recursively Enumerable (RE).

Turing Complete programming languages are of computability class RE, and thus correspond to the automata class TM. However, for a given Turing Complete programming language, for example the Lambda Calculus, different evaluation strategies \[2\] can be specified which affect its behavior. In particular, there are expressions that can be reduced via lazy evaluation that cannot be reduced using a strict evaluation strategy \[3\]. Furthermore, between CF and RE is another computability class, the Recursive (R) languages \[4\]. These correspond to total functional programming languages \[5\], and the automata class of decidable Turing Machines (those which always halt) \[6\]. The set of reducible expressions of a total language is not affected by the choice of evaluation strategy. Indeed, if it is provable that all expressions can be reduced to identical normal forms under both lazy and strict strategies, then a language can be proven to be total, that is, in R and not RE. Thus, the behavior of a language under different evaluation strategies can be relevant to determining its computability classification.

What then is the computability relation between a given recursively enumerable language L equipped with lazy evaluation, and the same language equipped with strict evaluation? L is contained in RE. Would it be correct to say that L+LE and L+SE are both contained in RE? That L+SE \< L+LE? What about other evaluation strategies? Does the Computational Complexity hierarchy capture these distinctions?

One can also consider this from the viewpoint of pure versus impure relational logic programming, e.g. minikanren or Prolog without and with the cut operator, respectively. Pure relational minikanren is a Turing Complete (RE) language, but certain programs that would halt when written with impure operators do not halt when written in pure style. What hierarchy of expressivity captures this behavior? In some respects Pure mk = Impure mk (because both are contained in RE), but in others Pure mk \< Impure mk, because of the incidence of divergence in pure style programs.

References:

\[0\] https://en.wikipedia.org/wiki/Automata\_theory

\[1\] https://en.wikipedia.org/wiki/Computability\_theory

\[2\] https://en.wikipedia.org/wiki/Evaluation\_strategy

\[3\] "And with certain programs the number of steps may be much smaller, for example a specific family of lambda terms using Church numerals take an infinite amount of steps with call-by-value (i.e. never complete), an exponential number of steps with call-by-name, but only a polynomial number with call-by-need."

https://en.wikipedia.org/wiki/Lazy\_evaluation#Performance

\[4\] https://en.wikipedia.org/wiki/Recursive\_language

\[5\] https://en.wikipedia.org/wiki/Total\_functional\_programming

\[6\] https://en.wikipedia.org/wiki/Decider\_(Turing\_machine)

# Answer
Most (or all) reasonable programming are Turing-complete, and thus can be used to compute exactly the computable functions, i.e., to decide the decidable languages, nothing more and nothing less. So details like strict or lazy evaluation don't make a difference to their expressiveness, in this sense.

---

> a given recursively enumerable language L equipped with lazy evaluation

This is a fundamental misunderstanding. There are two meanings of the word "language" in computer science.

One meaning is a formal language: a subset of $\\{0,1\\}^\*$. See https://en.wikipedia.org/wiki/Formal\_language#Definition. A formal language can be recursively enumerable or not.

Another meaning is a programming language: a way of expressing computer programs. See https://en.wikipedia.org/wiki/Programming\_language. A programming language can use lazy evaluation or strict evaluation or neither.

It makes no sense to mix these two. Even though both use the same word ("language") in their name, they are fundamentally different concepts.
> 1 votes

---
Tags: turing-machines, computability, lambda-calculus, evaluation-strategies, church-numerals
---


# Question
Title: Must the evaluation strategy for a language be specified in order to apply the Church-Rosser Theorem?
The Church-Rosser Theorem \[0\] states that the Lambda Calculus (LC) is confluent: between a source expression S and target expression T, the latter in normal form, for any given P, a sequence of permissible reductions that begins with S, there is some subsequent sequence of reductions Q (possibly the empty sequence) that can be applied after P to arrive at T. Thus, for all P, there exists Q such that Q(P(S)) = T.

Evaluation strategies \[1\], in this context, are rules for applying reductions to LC terms. These rules can include the order in which reduction are applied. Certain terms will diverge under strict evaluation strategies, that under lazy evaluation will successfully reach a normal form. For example, consider a constant C, and the Omega (M) and K combinators, M = ,\y.(y y)(,\y.(y y)), and K = ,\a.,\b.a. Under lazy evaluation, KMC = C - the K combinator discards M without evaluation. Under strict evaluation, KMC diverges because M diverges (in keeping with the definition of a strict function \[2\]).

How does this relate to the Church-Rosser Theorem, and the confluence property of LC? Is LC+Strict Evaluation *not* confluent? Are proofs which are dependent on the C-R Theorem sensitive to the evaluation strategy of the language to which they refer?

This is related to my question elsewhere \[3\] about the sensitivity of the computability classification of languages to their evaluation strategies.

\[0\] https://en.wikipedia.org/wiki/Church%E2%80%93Rosser\_theorem

\[1\] https://en.wikipedia.org/wiki/Evaluation\_strategy

\[2\] https://en.wikipedia.org/wiki/Strict\_function

\[3\] Is there a hierarchy of computational expressivity that is sensitive to evaluation strategies?

# Answer
> 2 votes
The Church-Rosser theorem gives you the following guarantees:

* A term has *at most one* normal form. That is, there aren't different normal forms depending on your choice of evaluation strategy.
* If a term has a normal form, then no matter what evaluation strategy you use, the result of that evaluation strategy will be a term that can be further reduced (possibly in zero steps) to that normal form.

It does *not* guarantee that a particular evaluation strategy will find the normal form if it exists. But it does guarantee that your evaluation strategy won't transport you to a dead end from which the normal form can't be found by any strategy.

---
Tags: lambda-calculus, normal-forms, combinatory-logic, evaluation-strategies
---


# Question
Title: Why is this code for dining philosophers deadlock free?
```
monitor DiningPhilosophers
{
 enum {THINKING, HUNGRY, EATING} state[5];
 condition self[5];
 void pickup(int i) {
 state[i] = HUNGRY;
 test(i);
 if (state[i] != EATING)
  self[i].wait();
 }
 void putdown(int i) {
  state[i] = THINKING;
  test((i + 4) % 5);
  test((i + 1) % 5);
 }
 void test(int i) {
 if ((state[(i + 4) % 5] != EATING) &&
 (state[i] == HUNGRY) &&
 (state[(i + 1) % 5] != EATING)) {
  state[i] = EATING;
  self[i].signal();
 }
}
 initialization code() {
  for (int i = 0; i < 5; i++)
   state[i] = THINKING;
  }
 }

```

The code is invoked as follows:

```
DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

```

This code is taken straight from Abraham Silberschatz, Operating Systems, 9th edition. In the book, they say that the above code is a solution to the dining philosophers problem that doesn't allow deadlocks, and also guarantees mutual exclusion, i.e. two adjacent diners cannot both be eating at the same time.

But it doesn't seem true. Let's say diner 1 and 2 are next to each other, and diner 1 calls pickup(1). Inside pickup(1), Diner 1 sets his state to HUNGRY, then calls test(1). Inside test(1), DINER 1 finds that he is hungry and that his neighbors are not EATING, and therefore enters the IF statement block. At this point, let's suppose that *before* he is able to set his state to EATING, diner 2 runs pickup(2) and similarly also enters the IF statement in the test(2) call. Then both diners will be in a situation where they both set their state to EATING, violating mutual exclusion. What's the deal here?

# Answer
> 1 votes
So apparently my confusion has to do with not realizing what a monitor really is. "The monitor construct ensures that only one process at a time is active within the monitor" This means that in my example, once process 1 runs the pickup() call in the monitor, process 2 cannot begin its own pickup() call until process 1 has finished executing pickup() (or waits on a signal within that call).

---
Tags: operating-systems, concurrency, mutual-exclusion
---


# Question
Title: How to determine the set of real numbers corresponding to a given floating point number?
Let's say we consider IEEE 754 double precision floating-point numbers, and we use RNTE - Round To Nearest, Ties to Even - rounding. I know that the RNTE rounding works this way: given two consecutive floating-point numbers, a and b, and a real number x,

* if a \<= x \< (a+b)/2, x gets translated to a
* if (a+b)/2 \< x \<= b, x gets translated to b
* if x = (a+b)/2, x gets translated to the number with an even significand between a and b

For example, I want to know which are the real numbers that are "mapped" to 1, where 1 is a floating-point number. How should I proceed? I thought that I must consider both the cases where 1 is a and where 1 is b in the above definition, and so consider both the previous and the next floating-point number. Is it correct? Is there a simpler way?

# Answer
> 1 votes
Today, my professor explained how to sove this problem. Since I think that it might be useful to other users, I'll post here the answer.

Given a floating-point number $f$ in a particular encoding (for example IEEE 754 single/double precision), we want to know which subset of real numbers corresponds to $f$, that is to say which real numbers gets rounded to f when converted to the same encoding. We're using RNTE (Round To Nearest, Ties to Even) rounding.

We represent the encoding as a quadruple $\mathbb{F}(\beta,t,M\_1,M\_2)$, where $\beta$ is the base, $t$ is the number of significand digits after the point and $M\_1$,$M\_2$ are the lower and upper bounds for the exponent range, respectively.

For example, let's choose to work with IEEE 754 double precision numbers, which we can denote as $\mathbb{F}(2,52,-1023,1024)$.

Let $f = 17 = (10001)\_{2} = 1.\overbrace{00010...0}^\text{52 digits} \times 2^{4} \in \mathbb{F}$.

We have to determine the predecessor and the successor of $f$, both of which are in $\mathbb{F}$. Let's call them $a$ and $b$, respectively. In order to do this, we have to find the distance between $a$ and $f$ and between $f$ and $b$. We know that $17 \in \[16, 32\] = \[2^{4},2^{5}\]$, so we can use the formula $y-x=\beta^{p-t}$ to get those distances, where $x,y \in \[\beta^{p},\beta^{p+1}\]$, $\beta=2$, $p=4$, $p+1=5$ and $t=52$.

So, $a = 17 - 2^{4-52} = 17 - 2^{-48}$,

and $b = 17 + 2^{4-52} = 17 + 2^{-48}$

Now we can apply the RNTE rounding, which states that a real number $x$ is rounded to its nearest number in $\mathbb{F}$ and, if there are two candidates, it chooses the one with an even mantissa (or significand). The latter case means that $x$ is the midpoint between two consecutive numbers in $\mathbb{F}$.

The midpoint between $a$ and $17$ is $ x\_1 = 17 - \frac{1}{2} 2^{-48} = 17 - 2^{-49}$,

the midpoint between $17$ and $b$ is $ x\_2 = 17 + \frac{1}{2} 2^{-48} = 17 + 2^{-49}$

Each real number between $x\_1$ and $x\_2$ gets rounded to $17$, including $x\_1$ and $x\_2$, because 17 has an even mantissa in our representation. So the answer is $\\{x \in \mathbb{R} \mid 17 - 2^{-49} \leq x \leq 17 + 2^{-49}\\}$.

# Answer
> 0 votes
The powers of two are more interesting than most other numbers.

Assume you are using double precision IEEE 754 format floating point numbers. Let $u = 2^{-52}$, Then the next floating point number larger than 1 is $1+u$, and the next floating point number smaller than 1 is $1 - u/2$.

A real number x is rounded to 1 if $1-u/4 ≤ x ≤ 1+u/2$. For any floating-point number f with $1 \< f \< 2$, x is rounded to f if $f - u/2 ≤ x ≤ f + u/2$ if the last bit of f is even, and if $f - u/2 \< x \< f + u/2$ if the last bit of f is odd.

Numbers x with $f - u/2 \< x \< f + u/2$ are always rounded to f, because f is the nearest floating point number. For the numbers $x = f ± u/2$, $f$ and $f ± u$ are equally far away, so the round-to-even rule decides.

# Answer
> 0 votes
**Short answer:**

If the mantissa is not all ones, the next floating-point number is $1$ ulp more.

* E.g. $1.1000\_b\times 2^7\to1.1001\_b\times 2^7$ ($192\_d\to200\_d$), the difference is $2^{7-4}=8$.

If the mantissa is all ones, the next floating-point number is all zeroes with the next exponent, and the difference is again 1 ulp.

* E.g. $1.1111\_b\times 2^7\to1.0000\_b\times 2^8$ ($248\_d\to256\_d$), the difference is $2^{7+1}-(2^{7+1}-2^{7-4})=8$.

---
Tags: arithmetic, floating-point, numerical-analysis
---


# Question
Title: What is standardization in computer science?
I was reading about the differences standards and specifications for C.
I understood that programming languages are usually stadardized and I learnt that there are different approches to stadardization.
Anyway I did not understand yet what this terms refer to.
If I think to C, I believe it refers to a standard API, the API of the C standard Library (libc).
This seems to make sense to me, as if someone told me "Look these are the only functions, types, Macros....etc you can use", because they're the only thing you "see" after you downloaded the library and they make your code portable.
Anyway, I don't know if my idea of standardization is in some-ways correct, if it's totally wrong or if it's a simplified version, so here I am.

# Answer
A standard for a programming language is a document defining the syntax and semantics for that language. Usually, for real-world languages, this document involves a (hopefully) precise description in intuitive terms, rather than a formal semantics, written in mathematical terms.

Still, this document acts as a contract between the programmer and the language implementation (usually a compiler/interpreter, plus some "standard libraries").

The programmer knows that, if they stick to what the standard mandates, they will get back the intended result from the implementation. Vice versa, the implementor of the language can assume that the programmer used no other features than those mandated. Often, the implementor will also provide non-standard features (additional APIs, additional language constructs, OS-specific libraries, etc.).

Note that the standard does not only involve describing the APIs in the standard library. In the case of the C language, as mentioned by the OP, the standard defines among others: the syntax, the type system, the memory model, the statements, the variable declarations, etc.

For instance, what happens if we write `int *x; *x=0;`? The ISO standard answers that: an implementation printing `mooo!` on screen is perfectly conforming (as any other implementation is).

So, summing up, a standard is the authoritative document which answers questions like "is running code C guaranteed to have behavior B?".

Most standards are written by a committee made of the most prominent organizations which developed / are developing the most widespread implementations. They vote on which features should be in or out, until they reach an agreement on what should be the standard definition. Some languages are revised every few years, so to include more features.
> 4 votes

# Answer
Standardization is the process of developing, promoting and possibly mandating standards-based and compatible technologies and processes within a given industry.

Standards for technologies can mandate the quality and consistency of technologies and ensure their compatibility, interoperability and safety. Standards organizations such as ANSI , IEEE and IETF exist to promote standardization and endorse official standards for given applications.

A lack of standardization often manifests in large numbers of incompatible proprietary formats for a given technology and for technologies that must interoperate. That all-too-common situation hinders the adoption and advancement of the technology and industry.

The burgeoning Internet of Things (IoT) is a current case in point. The main purpose of the IoT is enabling almost any object imaginable to be connected and to transmit data over the Internet. Although that scenario is increasingly becoming realized, incompatible formats and market fragmentation are slowing adoption.
> 3 votes

# Answer
Standards are simply a list of software guidelines that a project will need to conform to. These standards can be a mixture of requirements. There could be special format and documentation of the code needed. You many need to program the flow of routines in a certain way. How you name functions, files, and variables may need to fit into certain schemes. There could be limits on the types of features that a developer can use while working in some platform.

The reason why it is important to know about standardization in C is that many compilers have been built to default to various versions or even only support only one standard of C programming. You may be forced to work with a particular compiler or a legacy system that may not be able to support a new version of C. Luckily, C programmer did not see many changes of features between the ANSI-C and the C99 standards.
> 1 votes

# Answer
*I wrote this to help someone understand standardization in the context of c++.*

Most programming languages have a committee that works on a specification of the language called a standard. Individual vendors then implement interpreters or compilers that conform to this standard.

The idea is that code should be portable between compilers. Sometimes code works on one compiler and not on another. The standard is then consulted to see whether it is the code that doesn't conform to the standard or whether it is the compiler that doesn't conform.

Consider for a second Chomsky's work on grammar. There are infinitely many grammatically correct sentences, but we are all endowed with the ability to tell if any given one is grammatical.

There are infinitely many pieces of code. A programming language standard is a specification from which we can determine if a given piece of code is correct.

If it is correct, it is said to conform with the standard or to be well defined by the standard. Otherwise it is said not to conform and it's behaviour is then called undefined behaviour (as it might happen to work on some vendors implementations of the language, and not on others i.e. not guaranteed to work, rather than guaranteed not to work).

It's a good idea to write code that is well defined/conformant. Otherwise the vendor might change their implementation, and break your code. They would be considered to be in the right, since they are conformant. In this way, it's a little like the law.
> 1 votes

---
Tags: terminology, programming-languages, c
---


# Question
Title: Multi-Paxos Full Disclosure: How does the acceptor know about the chosen value after it marks an entry as chosen?
I am learning multi paxos from the slides of this made by John Ousterhout and Diego Ongaro.

In this section talking about Full Disclosure, it says the acceptor mark entry 6 as chosen, since the proposer tells it, with the same proposal 3.4 and firstUnchosenIndex 7.

My Question is: As you can see, proposal 3.4 is for entry 8 now, how can the acceptor simply mark entry 6 as chosen without knowing the chosen value?

# Answer
i think because when proposer become leader.it send accept RPCs in it's term with firstUnchosenIndex ,so if the accepter found it's index\<firstUnchosenIndex and acceptedProposal\[index\]'s proposalNum == leader's proposalNum. it knows that this leader has chosen index's value,because there is acceptedProposal\[index\],so log\[index\] shoud has value which comes from proposer who has the proposalNum. so it konws index is the chosen one which in picture is 6.
> 0 votes

---
Tags: consensus
---


# Question
Title: Are there any problems which are known to be both NP-complete and EXPTIME-complete?
Are there any problems which are known to be both NP-complete and EXPTIME-compelte? My guess is no, because we know that $P$ is not equal to $EXPTIME$ and EXPTIME-complete problems are not in $P$, and hence a problem that was both NP-complete and EXPTIME-complete would imply $P \not= NP$. Is my thinking correct?

Note that in a difference in notation, here $EXPTIME=EXP$.

# Answer
No, that is not currently known. If such a problem were known, it would prove that:

$$NP=EXPTIME$$

Incidentally, it would also prove that $NP=PSPACE$, because it is known that:

$$P \subseteq NP \subseteq PSPACE \subseteq EXPTIME$$

We don't know which of these subset relations are strict subset relations, but at least one of them must be, because by the time hierarchy theorem:

$$P \subset EXPTIME$$
> 3 votes

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


title: How to prove feasibility?

text:
# Question
Title: How to prove feasibility?
Let's say I have a optimization problem P1, where the constraints are linear but the objective function is not. Let's say I have another optimization problem which is linear in constraints and linear in the objective function.

The goal of the problem is to show that if P1 has a bounded optimum value then P2 has the same optimum value.

Now we want to prove two things to achieve that.

1. Prove that for every feasible solution $x$ of P1, there is a feasible solution $y$ of P2 with f(x) = g(y)
2. Prove that for every feasible solution $y$ of P2, there is a feasible solution $x$ of Pq with f(x) = g(y)

My questions are as follows:

1. Is there a difference between the proofs of the two statements above?
2. How do I go about proving that for every feasibile solution of P1 there is a feasible solution for P2 and vice versa? I am looking for a high level template or a series of steps to achieve this, nothing specific.

# Answer
> 3 votes
The theorems are true iff the images of the feasible sets by their respective function coincide (whatever the kind of constraints and kind of functions). This has no reason to occur in general.

One of the theorems can hold accidentally if one of the images is a subset of the other. For instance if the P2 function is such that it reaches the minimum and maximum of the P1 function, the first theorem holds.

# Answer
> 1 votes
Consider a P1 where the values of the objective function are constrained.

```
P1
Objective: max f(x) = Sin(x)
Constraints: 0 <= x <= 10

P2
Objective: max g(x) = x
Constraints: 0 <= x <= 10

```

It should be obvious that in this case, 1. holds but 2. does not.

A proof could look like that:

For 1.: `0 <= x <= 10` implies `min(g(x)) = 0 <= min(f(x)) = 0` and `max(g(x)) = 1 <= max(f(x)) = 10` therefore (with Intermediate value theorem which lets us know all values between the min and max are reached) 1.

For $\neg$ 2.: `0 <= x <= 10` implies `max(f(x)) = 10 > max(g(x)) = 1`, so 2. is not true since there is no feasible solution with g(x) = 10.

---
Tags: linear-programming
---


# Question
Title: Are there absolute reasons to prefer row/column-major memory ordering?
I've heard it said that "fortran uses column-major ordering because it's *faster*" but I'm not sure that's true. Certainly, matching column-major data to a column-major implementation will outperform a mixed setup, but I'm curious if there's any *absolute* reason to prefer row- or column-major ordering. To illustrate the idea, consider the following thought experiment experiment about three of the most common (mathematical) array operations:

## Vector-vector inner products

We want to compute the inner product between two equivalent-length vectors, `a` and `b`: $$ b = \sum\_i a\_i x\_i. $$ In this case, both `a` and `b` are "flat"/one-dimensional and accessed sequentially, so there's really no row- or column-major consideration.

Conclusion: Memory ordering doesn't matter.

## Matrix-vector inner products

$$ b\_i = \sum\_j A\_{ij} x\_j $$

The naive multiplication algorithm traverses "across" `A` and "down" `x`. Again, `x` is already flat so sequential elements are always adjacent, but adjacent elements in `A`'s *rows* are most often accessed together (and I suspect this is likely true for more sophisticated multiplication algorithms like the Strassen or Coppersmith-Winograd algorithms).

Conclusion: Row-major ordering is preferred.

(If you let vectors have transposes you can define a left-multiplication of matrices, $x^T A$, in which case column-major does become preferable, but I think it's conceptually simpler to keep vectors transposeless and define this as $A^T x$.)

## Matrix-matrix inner products

$$ B\_{ik} = \sum\_{j} A\_{ij} X\_{jk} $$

One more time, the schoolbook algorithm traverses across `A` and down `X`, so one of those traversals will always be misaligned with the memory layout.

Conclusion: Memory ordering doesn't matter.

## Additional consideration: strings & text

ASCII (or similar) strings are most frequently read across-and-down. There's a lot more to consider since a multidimensional array of characters could be ragged (different length rows, e.g. in storing the lines of a book), but the usual traversal pattern at least suggests a preference for row-major ordering.

Conclusion: Row-major ordering is preferred.

---

Of course, this analysis is extremely crude and theoretical, but it at least suggests row-major ordering is a little more "natural" (from a performance perspective) for multidimensional arrays. Does this stand up to real-world examination? Are there any similar analyses that lean the opposite way and suggest an *absolute* advantage to column-major ordering?

# Answer
> 4 votes
Whether row-major or column-major order is more efficient, depends on the storage access patterns of a specific application.

The underlying principle of computing is that accessing storage in sequential locations tends to be the most efficient pattern possible, whereas accessing storage at disparate locations incurs an overhead in seeking to the data on each iteration, so organising the storage to suit the typical algorithms performed on the data by a particular application, can result in a performance gain.

It's also worth considering what we mean by rows and columns. By a "row" we typically mean a set of fields that relate to one logical/conceptual entity - a row *contains* fields (in a hierarchical relationship). By a "column", we typically mean a set of fields that share a common meaning or type, but where each field relates to separate logical/conceptual entities - a column is a *cross-cut* of fields taken from multiple logical entities.

I suspect row-major ordering tends more often to be the default, because it is more common for algorithms to want to access the related fields of the same logical entity at once, than it is for them to want to access fields with the same meaning but across different entities at once.

I suspect also, given the definition of rows and columns above, that row-major aligns with how programmers are most readily inclined to think about accessing data - it's most likely to accord with their *mental model* of how data is organised. Deviating to column-major is something you then do for a specific performance or algorithmic reason, not by default.

# Answer
> 1 votes
Similar answer to that of Steve.

The most appropriate storage order depends on the traversal patterns. But the programmer has some freedom to optimize the pattern in a way that is cache-friendly.

E.g. a matrix-vector multiply can be implemented as

* clear all $b\_r$,
* loop on the matrix rows:

+ loop on the matrix columns:

    - accumulate $A\_{rc}x\_c$ to $b\_r$.

or

* clear all $b\_r$,
* loop on the matrix columns:

+ loop on the matrix rows:

    - accumulate $A\_{rc}x\_r$ to $b\_c$.

These two versions trade vector cache-friendly accesses for matrix cache-friendly ones. For matrix-matrix products, there are yet more options.

---

In full-fledges linear algebra libraries, the access patterns are so numerous and varied that every use case might have a differently affinity for one storage order or the other, and an absolute preference is impossible.

# Answer
> 0 votes
The fact is that with current computer hardware, the time to access one cache line (often as large 64 byte) of consecutive bytes is practically the same as the time to access a single word (say 8 bytes) in a cache line, so it is much more efficient to access items that are stored in consecutive memory positions. And accessing items that are say exactly 4,096 bytes apart can be especially inefficient.

Many languages don't support two-dimensional arrays, they support arrays of arrays instead. The first index will specify a subarray. The second index will specify an element within that subarray. Since any objects (including arrays) are stored consecutively, changing the second index will access consecutive items in memory; changing the first index will access items far apart.

(I have seen hardware that actually cached small squares or rectangles in one cache line. So accessing diagonal elements, or more importantly small triangles of data, required fewer cache lines. This required an allocator that would allocate rectangular data)

---
Tags: memory-access, performance, matrix-multiplication
---


# Question
Title: Confused about Telescoping/Domain Transformation Question
I have been working on the following domain transformation problem however, I am stuck on how to continue to receive the solution. I would greatly appreciate it if someone can explain how I can complete this:

T(1) = 0

T(n) = T(n/2) + n^2

The following is what I have so far:

# Answer
> 0 votes
Here is how you can write the telescope more clearly.

$$\begin{array}{ll} S(k)-S(k-1)\phantom{S(k-2)-S(k-3)S(2)-S(1)-S(0)}&=(2^{k})^2\\ \phantom{S(k)-}S(k-1)-S(k-2)\phantom{-S(k-3)S(2)-S(1)-S(0)}&=(2^{k-1})^2\\ \phantom{S(k)-S(k-1)}S(k-2)-S(k-3)\phantom{S(2)-S(1)-S(0)}&=(2^{k-2})^2\\ \phantom{S(k)-S(k-1)S(k-2)}\cdots\phantom{S(2)-S(1)-S(0)}&\cdots\\ \phantom{S(k)-S(k-1)-S(k-2)-S(k-3)}S(2)-S(1)\phantom{-S(0)}&=(2^{2})^2\\ \phantom{S(k)-S(k-1)-S(k-2)-S(k-3)S(2)-}S(1)-S(0)&=(2^{1})^2\\ \end{array}$$ Summing up all equalities above, we will cancel all terms between one another except the first term and the last term. We have $$\begin{align} S(k)-S(0) &= (2^{k})^2+(2^{k-1})^2+(2^{k-2})^2+ \cdots + (2^2)^2 + 2^2\\ &= 2^{2k}+2^{2k-2}+2^{2k-4}+ \cdots +2^4+ 2^2\\ &= \frac {2^{2k+2}-4}{3} \end{align}$$ So $$S(k)=\frac {2^{2k+2}\ -4}{3}+S(0) = \frac {2^{2k+2}\ -4}{3} = \frac {4(2^{k})^2\ -4}{3}$$

Now substitute $\log\_2n$ for $k$. Note $2^k=n$. $$S(\log\_2n)=\frac43(n^2-1)$$ The left side is $T(2^{\log\_2n})=T(n)$. So $$T(n)=\frac43(n^2-1)$$ The equality holds only when $n=2^k$ for some nonnegative integer $k$.

# Answer
> 0 votes
We have:

$$T(n) = \begin{cases} 0 & n = 1\\ T\left(\tfrac{n}{2}\right) + n^2 & n \> 1 \end{cases}$$

You are then correct, let $n = 2^k$. We can then rewrite $S(k) = T(2^k)$ as:

$$S(k) = \begin{cases} 0 & k = 0 \quad \text{because } 2^0 = 1\\ S\left(k-1\right) + 2^{2k} & k \> 0 \end{cases}$$

This then immediately turns into the sum:

$$\begin{align\*} S(k) &= \sum\_{i = 1}^k 2^{2i}\\ &= \sum\_{i = 1}^k 4^i\\ &= \frac{4^{k+1} - 1}{3} - 1 & \text{by geometric sum rules} \end{align\*}$$

We can then plug $n$ back in such that $k = \log\_2 n$:

$$\begin{align\*} T(n) & = S(\log\_2 n) \\ & = \frac{4^{\log\_2 n + 1} - 1}{3} - 1\\ & = \frac{4 \cdot 2^{2\log\_2 n} - 1}{3} - 1\\ & = \frac{4 n^2 - 1}{3} - 1\\ & = O(n^2) \end{align\*}$$

# Answer
> 0 votes
The recurrence can be written $$\begin{cases}S(0)=1=4^0\\S(k)=S(k-1)+4^k\end{cases}$$ and you should recognize the sum of a geometric series, by

$$S(k)=S(k-1)+4^k=S(k-2)+4^{k-1}+4^k=S(k-3)+4^{k-2}+4^{k-1}+4^k=\cdots\\\=S(0)+4^1+\cdots4^{k-1}+4^k=\frac{4^{k+1}-1}3=\frac{4(2^k)^2-1}3=\frac{4n^2-1}3.$$

# Answer
> 0 votes
You can find the solution "manually" by successive doublings and by writing the recurrence as

$$\frac{T(n)}{n^2}=\frac{T\left(\dfrac n2\right)}{n^2}+1.$$

The sums are

$$\frac{T(1)}1=1,\\\frac{T(2)}4=\frac14+1,\\\frac{T(4)}{16}=\frac1{16}+\frac14+1,\\\frac{T(8)}{64}=\frac1{64}+\frac1{16}+\frac14+1,\\\cdots$$

The RHS quickly tend to $\dfrac13$ and $T(n)=\Theta(n^2).$

---
Tags: algorithms
---


# Question
Title: Is frontend slang term is it used in teaching in univ
I have a question : is the term front-end in this context phpmyadmin is frontend for mysql slang is it taught in academy in this context I don't want to use slang term

# Answer
Front-end and back-end are very common terms, with several meanings.

https://en.wikipedia.org/wiki/Frontend\_and\_backend

They are *jargon*, not *slang*. You *should* use them rather than periphrases.
> 1 votes

# Answer
According to Merriam Webster frontend is not slang.
> 0 votes

---
Tags: terminology
---