# Question
Title: Why this greedy algorithm fails in rod cutting problem?
Recall the rod cutting problem.

> Given a rod of length $n$ inches and a table of prices $p\_{i}$ for $i=1,2,3,4,\\,.\\,.\\,.$ determine the maximum revenue $r\_n$ obtainable by cutting up the rod and selling the pieces. You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

> Show, by means of a counterexample, that the following ‘greedy’ strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p\_i/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $4$ are $p\_1=1, p\_2=5, p\_3= 8, p\_4 = 9$ respectively. So, densities are $d\_1=1, d\_2 = 2.5, d\_3= 2.67, d\_4 = 2.25$ respectively.

If we are given a rod of length $4,$ then an optimal way of cutting the rod to maximize revenue is $2$ pieces of length $2$ each, generating $5+5 = 10.$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $3$ and $1$, generating revenue $8+1=9.$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting the rod.

# Answer
Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective *single* rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, *most* optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.
> 4 votes

# Answer
Greedy algorithm doesn't always generate optimal solution. To get optimal solution with it, the problem needs to have some good property such as optimal substructure or matroid. The optimal substructure means optimal solution can be constructed from the optimal solutions of divided problems. Matroid theory shows another good property to characterize where greedy algorithm works: Edmonds–Rado Theorem claims that (best-in) greedy algorithm works with any weight function if and only if the independence system is matroid. Here, independence system is a kind of formalization used to many combinatorial optimization problems. I don't explain the details, but wanted to explain greedy algorithm works for problems with good properties, that the rod cutting problem doesn't hold.
> 3 votes

# Answer
Actually, there is a simple optimal greedy strategy with these prices: "Don't cut if n ≤ 3. Cut a piece of length 2 if n = 4 and cut a piece of length 3 otherwise, then cut the rest according to this strategy".

Here's two interesting problems:

1. Given 4 prices, find out if the originally proposed greedy algorithm is optimal.
2. Given 4 prices, find a simple optimal greedy algorithm.
> 0 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: Big O of dynamic array

text:
# Question
Title: Big O of dynamic array
Skiena's Algorithm Design Manual, 3rd Ed p.71 gives the time complexity of a *dynamic array* according to the number of movements, $M$, as:

$$ M = n + \sum\_{i=1}^{lg(n)} 2^{i-1} = 1 +2+ 4+\ldots+\frac{n}{2} + n \stackrel{?}{=} \sum\_{i=0}^{lg(n)} \frac{n}{2^i} $$

For the life of me, I can't figure out how he's getting from the left hand summation to the right hand one. It's crucial that it does, because his next step is to say the right hand side is less than the geometric series as $i\rightarrow\infty$ which converges to $2n$.

There is a known errata,

> (\*) Page 71, formula on line 10: the lower index of the second summation $i=i$ should be $i=0$.

I have written the right hand side with the correction.

The only possible operations I see are rewriting the exponent...

$$ \sum\_{i=1}^{lg(n)} 2^{i-1} = \sum\_{i=1}^{lg(n)} 2^i\cdot2^{-1}= \sum\_{i=1}^{lg(n)} \frac{2^i}{2} = \frac{1}{2} \sum\_{i=1}^{lg(n)} 2^i $$

or adjusting the index...

$$ \sum\_{i=1}^{lg(n)} 2^{i-1} = \sum\_{i=0}^{lg(n)-1} 2^{i} $$

Neither of which help.

When I expand the right hand side, I get

$$ \frac{n}{1} + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \ldots $$

I don't see any way to rearrange or finagle that so it equals $1 +2+ 4+\ldots+\frac{n}{2} + n$.

# Answer
> 1 votes
If we assume that $n$ is a power of two (I'm assuming the author assumes this), first we can rewrite $n$ as a power of two, and shift the index over by one. Then we can combine the two into one sum:

$$n + \sum\_{i=1}^{\lg(n)} 2^{i-1} = 2^{\lg(n)} + \sum\_{i=0}^{\lg(n)-1} 2^{i} = \sum\_{i=0}^{\lg(n)} 2^{i}$$

For step two, take a look at this sum reversal identity:

$$\sum\_{i=0}^k f(i) = \sum\_{i=0}^{k} f(k - i)$$

So we can reverse our sum by substituting $i$ with $\lg(n) - i$:

$$\sum\_{i=0}^{\lg(n)} 2^{i} = \sum\_{i=0}^{\lg(n)} 2^{\lg (n) - i} = \sum\_{i=0}^{\lg(n)} \frac{2^{\lg(n)}}{2^i} = \sum\_{i=0}^{\lg(n)} \frac{n}{2^i}$$

# Answer
> 1 votes
$$n+\frac n2+\frac n4\cdots \frac nn=n\left(1+\frac12+\frac14+\cdots\right)\sim n\\,2.$$

---
Tags: summation, dynamic-array
---


# Question
Title: Nonexistance of collection of 'transformers' that 'trivially modify' Turing machines?
For a given recursive language $L$, let $TL$ be the language of turing machines that accept $L$, for some encoding of turing machines. $TL$ is countably infinite. Does there exist a set $S = \\{S\_1,S\_2,\cdots\\}$ of computable functions that take as input a turing machine and output a turing machine, such that if $T$ is in $TL$ then $S\_i(T)$ is also in $T\_L$, and that acting the $S\_i$ on a given $T$ generates all of $TL$ eventually?

If there exists a set (which probably there isn't), does there exist a finite such set?

The motivation is that the $S\_i$ can be thought of as transformations on the space of turing machines that don't change their behaviour, i.e. they are ways to 'rewrite' turing machines, and I wonder if there is a universal collection of such 'rewrite' algorithms. Examples include an $S\_i$ that appends an additional, useless, calculation (states) to its input.

# Answer
> 1 votes
Call such a set "universal transformer".
Yes, there is a universal transformer.

---

Let $\mathcal{ALL}$ be the set of all Turing machines, that is, $\mathcal{ALL}=\\{\langle M\rangle\mid M\text{ is a Turing machine}\\}$, where $\langle\cdot\rangle$ is some fixed encoding scheme for Turing machines.

By abuse of notation, we will treat an element $\langle M\rangle$ in $\mathcal{All}$ either as a string or as the Turing machine $M$ that is encoded in that string.

Given two Turing machines $M\_1, M\_2\in \mathcal{ALL}$, let $\delta\_{M\_1, M\_2}: \mathcal{ALL}\to\mathcal{ALL}$ be such that

* $\delta\_{M\_1, M\_2}(M)=M$ for all $M \not= M\_1$.
* if $L(M\_1)=L(M\_2)$, then $\delta\_{M\_1, M\_2}(M\_1)=M\_2$. Otherwise $\delta\_{M\_1, M\_2}(M\_1)=M\_1$.

Note that for all $M$, $L(\delta\_{M\_1, M\_2}(M))=L(M)$. It is easy to check that $\delta\_{M\_1, M\_2}$ is well-defined and computable.

Let $S=\\{\delta\_{M\_1,M\_2} \mid M\_1, M\_2\in \mathcal{ALL}\\}$.

Suppose language $L$ is accepted by $T\in\mathcal{ALL}$.

* For any $s\in S$, $s(T)\in TL$.
* If $L(T')=L(T)$, then $\delta\_{T,T'}(T)=T'$.

So, $S$ is a universal transformer.

---

Let $L$ be the empty language. $TL$ is the subset of $\mathcal{ALL}$ of all Turing machines that accept no strings.

There are infinitely many Turing machines that accept no strings. For example, the Turing machine $E\_i$ that moves left forever after having moved to the right $i$ times.

So, a universal transformer cannot be a finite set.

---

As said above, $S$ is a universal transformer.

However, $S$ is not useful in the sense that $S$ is undecidable. That is, it is not decidable whether we can check a string $s$ is in $S$ or not, assuming that we represent each element in $S$ by some fixed encoding scheme. In fact, $S$ is not computably-enumerable nor co-computably-enumerable.

---

Call a set $S$ "weakly-universal transformer" if given a language $L$ and a Turing machine $T$ such that $T$ accepts $L$, for any Turing machine $T'$ such that $T'$ accepts $L$, there exists a sequence of elements in $S$, $s\_1, s\_2, \cdots, s\_n$ such that $s\_n(s\_{n-1}(\cdots(s\_1(T))\cdots))=T'$.

Claim: A weakly-universal transformer is not computably-enumerable.
Proof: For the sake of contradiction, suppose $S$ is a computably-enumerable weakly-universal transformer. Then the set of all finite sequences of elements in $S$, $$S^\*=\\{(s\_1, s\_2,\cdots, s\_n)\mid n\text{ is a positive integer}, s\_i\in S \\}$$ is also computably-enumerable.

Let $L$ be the empty language. $TL$ is the subset of $\mathcal{ALL}$ of all Turing machines that accept no strings. Since $S$ is a weakly-universal transformer, $TL=\\{q\in S^\*\mid q(E\_0)\\}$, where $E\_0$ is the Turing machine that keeps moving left. Since an element in $S$ is a computable function, $TL$ is computably-enumerable. However, we know that $TL$, the language of all Turing machines that accept no strings is not computably-enumerable. This is a contradiction. $\quad\checkmark$

Corollary: A weakly-universal transformer is not finite.

---
Tags: formal-languages, turing-machines
---


# Question
Title: Problem in $NP \cap coNP$ and in P implies $NP=P$?
Suppose that we have a problem in $NP \cap coNP$, if we find an algorithm that solves the problem in P, does this mean that $NP=P$?

# Answer
> 2 votes
No. $P$ is a subset op both $NP$ and $coNP$ so any problem in $P$ is in $NP\cap coNP$. To show that $NP=P$ you need to show that all problems in $NP$ have a polynomial time solution.

If you would show that a $NP$-complete problem is in $NP\cap coNP$ however you would show $NP=P$.

# Answer
> 1 votes
Not at all.

Take *any* problem in P. Then the problem is automatically in NP and in co-NP, and therefore in the intersection, so you would conclude that P = NP. Because of one problem in P. That's obviously not correct.

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


# Question
Title: How much larger is the next representable value if 2^59 is stored in a double?
This is an exam question I couldn't solve

If I store 2^59 as double, that would give me

1 * 2^58. Is the answer just 2? I.e. next value is 2^60??

# Answer
> 1 votes
Write down the exponent.

Then look at the mantissa. It has a certain number of bits. The highest bit is not stored because it is always 1, and that bit has a value of $2^{59}$. How many bits of the mantissa are stored, and how many bits are there? Figure out the value of the lowest bit. You get the next representable number by changing that bit from 0 to 1. So how much was the value of that lowest mantissa bit again?

---
Tags: floating-point
---


title: AVL-tree insertion complexity proof

text:
# Question
Title: AVL-tree insertion complexity proof
I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how. I also tried to find it somewhere on the Internet, but I could not find any good results. Do you guys have any ideas how do we proof that?

# Answer
Interesting question. For a better *theoretical* understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311):

> As an immediate consequence of this lemma, we can implement the dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR , and PREDECESSOR in $O(\log n)$ time on red-black trees, since each can run in $O(h)$ time on a binary search tree of height $h$ (as shown in Chapter 12) and any red-black tree on n nodes is a binary search tree with height $O(\log n)$.

Red-Black trees do not differ from AVL-trees from a strict computational point of view: https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/. An AVL tree is a subset of a Red-Black tree: http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948. So from a theoretical point of view, you can map them together (computational-complexity wise).

Regarding a pure understanding of why the INSERTION is $O(\log n)$, check this implementation example. There you can clearly see that what makes an AVL differ from a standard BST are the rotations, that can be performed in constant time. With those you get a balanced tree, and with a balanced tree you get $O(\log n)$ INSERTION.
> 1 votes

# Answer
An insertion could at worse cause a rotation on every level, hence with complexity $O(h)$ where $h$ stands for the height.

Now thanks to balancing, $h=O(\log n)$.
> 0 votes

---
Tags: algorithms, trees, avl-trees
---


# Question
Title: TCP Warp Around time - Sequence number Problem
Consider a long-lived TCP session with an end-to-end bandwidth of 1Gbps. The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closet integer) before this sequence number can be used again is \_________.

The solution given for above question was : \[(2^32)\*8\]/(10^9) = 34.3597 sec

But what I think it should be : \[(2^32)208\]/(10^9) = 687.194 sec

I have multiplied it by 20 because minimum size of TCP packet is 20Bytes.

Please help me to clear the confusion which answer should be right and why. If there is another answer for the above question please let us know.

# Answer
> 0 votes
I suggest you read up on how TCP works and why do we need the sequence number. It is just a matter of unit conversions once you understand it. But I'll try to explain it in simple terms.

A packet consists of bytes. In TCP every byte has a sequence number. What do we need it for? In short to avoid duplicates, indicate lost packets and have in-order delivery. Even shorter, it ensures reliability(partially). TCP uses a 32-bit sequence number, **so you can have 2^32 distinct sequence numbers before you use a particular sequence number again**. Now you know how many **bytes** you need to transmit in order to reuse a number. And you have the **bandwidth given in bits/sec**. Do you understand the calculation now?

> basically time needed to transmit 2^32 bytes over 1Gbps bandwidth \[(2^32)\*8\]/(10^9) = 34.3597 sec

---
Tags: computer-networks, tcp
---


# Question
Title: Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.

This is similar to the notion of quaslinear complexity, which refers to a complexity of $O(n \log^{O(1)} n)$.

It is clear that quasilinear complexity is a subset of "almost-linear" complexity. However, I am unable to find an example of a complexity which is "almost-linear" yet not quasilinear. What is the differentiating factor between these two complexities?

# Answer
> 1 votes
Let $f\_a(n)=n^{1+(\log n)^{-a}}$, where $a\ge0$.

* $a=0$.
$f\_0(n)=n^2$ is not "almost-linear".
* $0\<a\<1$.
Since $(\log n)^{-a}=o(1)$, $f\_a(n)$ is almost-linear.

For any constant $c$,

$$\begin{aligned} \lim\_{n\to\infty}\frac{f\_a(n)}{n(\log n)^c} &=\lim\_{n\to\infty}\frac{n^{(\log n)^{-a}}}{(\log n)^c}\\ &=\lim\_{n\to\infty}\frac{\left(e^{\log n}\right)^{(\log n)^{-a}}} {\left(e^{\log\log n}\right)^c}\\ &=\lim\_{n\to\infty}e^{(\log n)^{1-a}-c\log\log n}\\ &=\lim\_{m\to\infty}e^{m^{1-a}-c\log m}\\ &=\infty\\ \end{aligned}$$

So, $f\_a(n)$ is not quasilinear.
* $a = 1$.
$f\_1(n)=en$ is quasilinear, where $e$ is Euler's number.

We can view $f\_a$ where $0\<a\<1$ as a family of functions that "differentiates" between "almost-linear" functions and quasilinear functions.

---
Tags: complexity-theory, time-complexity, asymptotics, space-complexity, complexity-classes
---


# Question
Title: Why do the 2-SAT techniques do not work for 3-SAT?
i just want to know why the techniques we use to solve the 2-SAT problems cannot be used to solve the 3-SAT problem. So the techniques that i know that help solve 2-sat are the naive on where you just take one variable in the formula and give it a truth value and go on from there by deleting clauses where the variable is in it and so on. Why won't that work for 3-SAT so when i chose a variable and set it to true i do the same things that i would do for 2-SAT, shouldnt that also work? The second technique that i know that helps solve 2-SAT is where you create an implication graph from the formula with 2 implications per clause with the form being a$\Rightarrow$b, where a and b are literals. if i convert that to 3-SAT i could generate 3 implications per clause a$\Rightarrow$b$\lor$c where a,b and c are literals. why won't that algorithm work for 3-SAT the same way it works for 2-SAT?

# Answer
The issue might be that 2SAT can be solved in polynomial time while 3SAT is NP-complete and can't. When the computational complexity becomes much higher, the proofs of your 2SAT method might not translate well to 3SAT or it works but you just don't have time to wait around for the solution.

It's hard to say unless you tell us what you mean by "work".

As I understand, going from 2 to 3 SAT you're changing the information structure of the problem **a lot**. So a lot can go wrong.
> 2 votes

---
Tags: complexity-theory, 3-sat, 2-sat
---


title: What is memcomputing?

text:
# Question
Title: What is memcomputing?
In recent article of PM the memcomputing is presented. But I did not understand how it works, according to the text.

What is the general principle of work for this `memcomputing`? How it is done in hard-ware?

# Answer
> 7 votes
It *doesn't* work. I am paraphrasing Scott Aaronson in this answer, whose article on the subject gives more details.

They claim to have some way of solving the subsetsum problem efficiently. The basic gist being that they encode all of the numbers in the instance as electrical signals, and then throw all the electrical signals together in to a big melting pot. They then measure the output signal and try to find whether it contains a signal corresponding to a solution.

However, this requires an exponentially precise signal (to be able to figure out whether the particular frequency/signal you want is there) so it isn't really a viable approach to solving $NP$-complete problems. The article claims that this is likely to be resolved in the future and that the general principle of memcomputing might one day become viable but I think that claim should be taken with a grain of salt. It seems that whatever trade-off you make, be it time, energy, memory or precision, you always end up hitting some barrier that requires exponential resources.

# Answer
> 3 votes
The answer above which claims "it doesn't work" doesn't quite make sense. Doesn't work for what? Which implementation of it? I realize I'm writing this with the luxury of 7 years having passed, but it's worth updating.

Scott Aaronson assumed in his 2015 blogpost that a MemComputer is purely an analog machine (which it was in the implementation he talked about) and used a concern that's very valid for analog machines to cast doubt on MemComputing's scalability in general. But the authors of the 2015 paper he talks about are clear that the implementation they were studying as a proof of principle is not unique. They specifically say that digital versions of it are possible. Since a machine with digital input/output doesn't need exponentially increasing precision to extract an output, you can't so easily claim that the exponential was simply moved to frequency space. (You could say that simply pointing to a different implementation is a bit cheap, but MemComputing as a concept was built over multiple papers, different papers addressing different things, this one simply didn't attempt to address scalability because it was beyond the scope. This should be possible in research.)

The general claim is simply that MemComputers leverage physics to compute in a way similar to quantum computers (except in a non-quantum system that exhibits dynamical long-range order), in the sense that long range correlations (loosely analogous to entanglement) are used to solve hard problems which can be interpreted as having such long-range correlations baked into problem statements. This would simply be a machine that is more expressive than a Turing machine (the way some people expect quantum computers to be more expressive than Turing machines) and would thus not threaten the generally held conjecture that $P\neq NP$, since that is a statement about Turing machines. Though it would clearly have implications for some versions of the Church-Turing thesis, the same way quantum computers do.

So, to answer the question: the general principle behind it is the type of dynamical long range order (a kind of collective behavior in physical systems) which has been shown to arise from time non-locality (memory). This is why MemComputing is more than just in-memory computing: it computes *with* memory as well. As for the question of "how is it done in hardware?": the hardware implementation of Digital MemComputing Machines (DMM), the most modern instantiations of a MemComputer, is based on self-organizing logic gates. These are (among other desirable aspects) invertible and strongly correlated even at large distances. This provides a type of collective behavior which we expect to be more advantageous than mere parallelization.

For more details, see the textbook MemComputing: Fundamentals and Applications, by Di Ventra. This is published by Oxford University Press and is thus peer-reviewed.

---

***More details if needed:***

The above should fully answer the original questions and you may stop reading if you want to, but I want to add a couple of paragraphs for those computer scientists whose intellectual alarm bells are probably and understandably ringing right now if they haven't heard of this before.

It is true that MemComputing is perhaps a bit more uncomfortable than quantum computation from a computer science perspective, because in quantum computation, the exponential complexity of NP-complete problems is *explicitly* moved somewhere: the exponentially increasing Hilbert space which doesn't have to be simulated by a physical quantum computer since that quantum computer just *is* quantum mechanical to begin with. But MemComputing is really not so different, except that, instead of moving the exponential complexity somewhere explicitly, it addresses the exponential complexity of NP-complete problems more *implicitly*, by recognizing that NP-hard problems are so difficult precisely because they are often very interconnected. So a physical computer which is similarly interconnected may have an edge. There is, in fact, a deeper reason why MemComputers are so efficient: topology. We use the language of topological field theory to analyze the MemComputing dynamics and find that what drives DMMs towards a solution are instanton states, topological objects that aid the DMM in leveraging "global" information over "local" information in the physical phase space. This also makes DMMs incredibly noise-robust (this topological robustness is, in fact, why some people hope to develop topological quantum computers, since quantum computers are incredibly noise sensitive, hence the difficulty in realizing them.)

Another issue is that if MemComputers are classical instead of quantum, then we can simulate these classical systems *efficiently* on an ordinary computer and let those simulated DMMs solve NP-complete problems for us. Since this constitutes and algorithm on a Turing machine, it would immediately follow that $P=NP$. Yay!

But alas, no. The dynamics of a DMM are governed by non-linear differential equations. These admit chaos and quasi periodic orbits in the physical phase space, which can be a big problem. Luckily, physical DMMs don't admit chaos or quasi-periodic orbits unless a massive amount of noise is dumped on the DMM, which would cause the state of the DMM to become chaotic and preventing it from ever finding a solution more effectively than a random walk. It has been shown that the noise necessary to do this to a physical DMM is equivalent to a temperature which would fry the electronics used to implement the self-organizing logic gates, so that's great. But physical noise enters the dynamics linearly, numerical noise from simulating the DMM *very much does not*.

So the theorems and studies that make us expect physical DMMs would solve NP-complete problems efficiently don't necessarily hold for simulated DMMs, since those are an entirely different beast to tame. Luckily that doesn't mean simulated DMMs can't be useful. They've been demonstrated to be useful for quantum measurements and the training of some types of neural networks. The company MemComputing Inc. uses simulated DMMs to solve industrial scale NP-complete problems (like shipping, route/schedule optimization for oil rig helicopters, and DoD applications) often by blindly receiving CNF files from them and solving them in 3SAT. This is a bit difficult, since you have to create a model that balances efficiency in simulating the system (getting a reasonably good degree of the polynomial overhead of the simulation) as well as faithfully representing the physics of a MemComputer in a way that's able to solve the type of problem at hand. MemComputing Inc. is a commercial company and therefore bound by NDAs, so unfortunately we don't have insight into their work. But it clearly works in a useful way, otherwise they'd be bankrupt.

Below is a figure of an empirical study on simulated DMMs that used hard instances that were specifically designed as benchmarks for SLS solvers and compares the results to some typical SLSs, including the state of the art SID algorithm.

You can see that in this setting, the DMM can easily solve the hard test instances at multiple 3SAT clause to variable ratios (4.3 being the hardest) and apparently retains the polynomial scalability on these instances (some people might think that these might still be exponentials with small coefficients, but the exponential fits we do for scalability either don't converge or are really bad, while polynomial fits are good fits). It's also worthy to note that the last data-point of the hardest ratio, 4.3, took 15 hours to complete with completely un-optimized, sequential code (other than the optimized hyperparameters of the physical dynamics). Extrapolating from the scalability for the state-of-the-art SID algorithm, it would have taken SID longer than the age of the universe to complete the same data-point.

It is worth stressing that none of this should be taken as some sort of experimental evidence that $P=NP$! There are still very good heuristic and historical reasons to believe $P\neq NP$ and even if that turns out to be false, empirical studies are certainly no way to prove $P=NP$, you need a mathematical proof.

---
Tags: computer-architecture
---


# Question
Title: Is finding a path with more red vertices than blue vertices NP-hard?
Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either **red** or **blue**, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

I think it should be possible but our TA said this was NP-hard.

Idea for a solution:

From $G$ create $G'=(V',E')$ as follows:

* Split all $v \in V\setminus \\{s,t\\}$ in two vertices $v\_{in}$ and $v\_{out}$. $V'$ is made up of the split vertex pairs and $s$ and $t$.
* For all $e=(u,v) \in E$ introduce an edge $(u\_{out},v\_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x \in \\{s,t\\}$ create edge $(x,v\_{in})$ or $(u\_{out},x)$ resp.). Also, introduce an edge $(v\_{in},v\_{out})$ for any of the split vertices. So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.

Now, we introduce weights as follows:

* $w((v\_{in},v\_{out})) = -1$ if the corresponding vertex $v$ was **red**.
* $w((v\_{in},v\_{out})) = +1$ if the corresponding vertex $v$ was **blue**.
* $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.

Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $\<0$ and you are done.

Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard? Is there an elegant reduction to show NP-hardness?

# Answer
> 9 votes
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.

I think the best to show NP-completeness, is to use the Hamiltonian path problem. Let's take a graph $G'$ of $N$ red vertices.

Then you build a graph $G$, adding $s$, $t$ and $N-1$ blue vertices to $G'$. You first chain with edges all the blues vertices from the source to the last blue one ($s$-\>$b\_1$-\>$b\_2$-\>...-\>$b\_{N-1}$). Then you put edges from $b\_{N-1}$ to every red vertex and an edge from every red vertex to $t$.

So a single path from $s$ to $t$ passes necessarly through all blue nodes ($N-1$) and then have to pass to all red nodes ($N$) to answer to

**Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?**

which is thus like answer to:

**Is there an Hamiltonian path in $G'$**

So your problem is indeed NP-complete.

# Answer
> 0 votes
This answer is based on Optidad's original answer and I feel like to make it more clear. (It meant to be in the comment but I want to illustrate with pictures.)

**Hamiltonian Path** problem:

> Given a directed graph $G$, does it contains a Hamiltonian path?

Note that the path is allow to start at any node and end at any node. But we can define **s-t Hamiltonian Path** problem where the start node must be s and the end node must be t, that is

> Given a directed graph $G$ and two node $s,t$ in $G$, does it contains a Hamiltonian path that starts at $s$ and ends at $t$?

The s-t Hamiltonian path problem is also NP-complete: since an algorithm that solves the s-t Hamiltonian path problem can be used to solve the Hamiltonian problem by repeatedly calling the algorithm for each ordered node pair.

Next we use the following example to show the reduction from $s$-$t$ Hamiltonian Path to OP's problem.

In the example, $G=\\{V,E\\}$ has an $s$-$t$ Hamiltonian path: $s\rightarrow 1\rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow t$. Then we construct an instance of OP's problem $G'$: color nodes in $V\setminus \\{s,t\\}=\\{1,2,3,4\\}$ red and for each outgoing arc from $s$, i.e., $(s,1),(s,2),(s,4)$, we insert $|V|-3=3$ blue nodes along the arc. Thus any simple path starting at $s$ contains exactly $|V|-3=3$ blue nodes and there are exactly $|V|-2=4$ red nodes in $G'$. Then it is easy to see the reduction is valid.

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


title: Convert ((ba ∪ ab)∗ ∪ b)* to NFA

text:
# Question
Title: Convert ((ba ∪ ab)∗ ∪ b)* to NFA
How do I simplify this $((ba \cup ab)^∗ \cup b)^\*$? I can draw the NFA for the '$ba$', '$ab$' and '$b$' term but when it comes to linking the '$ba \cup ab$' to the '$)^∗ \cup b)^\*$' i am unsure how to draw the asterisk. Is it just an epsilon transition back to the starting state?

# Answer
> 0 votes
The $\*$ (kleene closure) allows you to have 0 or more instances of the string so think of it as a self loop. Think of union as different paths. So you can have something like a state where on $ab$ or $ba$ you reach the same state and on a $b$ to another state. You can do it with epsilon transitions too, but in this case they don't seem necessary.

# Answer
> 0 votes
Here is one way to do it, the number of epsilons can probably be reduced though:

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


# Question
Title: Optimal path problem with constraint of minimal weight
Given an undirected weighted graph $G$ and two vertices $s, t$. We want to find a path $P$ from $s$ to $t$ that minimizes the following objective function $L$

$$L(P) = max(len(P), max\\{c(e) \mid e \in P\\})$$

For example, consider the following graph

Here we have two ways to go from the green node to the red node. Either with the left path or the right path. Here we choose the left path because $L(\text{left path}) = max(6, 2) = 6$ and $L(\text{right path}) = max(3, 7) = 7$.

Initially, I thought the problem can be solved easily by doing breadth-first search. However, the standard BFS would not work. For example, consider another graph

For this graph, the optimal path from $a$ to $g$ is $(a, d, e, f, g)$ with a goodness of $max(4, 4) = 4$. However, this path is not optimal to go from $a$ to $d$. For minimal cost from $a$ to $d$ we need to go $(a, b, c, d)$ with a cost of $max(3, 3) = 3$ instead of $(a, d)$ with a cost of $max(4, 1) = 4$.

In conclusion, the algorithm does not work because a sub-path of an optimal path does not have to be optimal.

Any hint for this problem would be highly appreciated.

# Answer
> 5 votes
Let's restrict ourselves to the case in which $s$ and $t$ are connected in $G$ and the length of the shortest path from $s$ to $t$ in $G$ is not larger than the maximum edge cost (otherwise the problem is trivial).

Consider this simpler problem first: Given an integer $c$, return the length $\ell(c)$ of the shortest $s$-$t$ path in the subgraph $G\_c$ of $G$ induced by all the edges with cost at most $c$. If $s$ and $t$ are not connected in $G\_c$ then $\ell(c) = +\infty$.

Clearly this problem can be solved in time $O(m + n \log n)$ using Dijkstra's algorithm, where $n$ and $m$ are the number of edges and vertices of $G$, respectively.

Let $c\_1, c\_2, \dots, c\_k$ be the costs of the edges in $G$, in increasing order (no repetitions) and let $c\_0 = -\infty$. Notice now that $\ell(c\_i)$ is monotonically non-increasing with respect to $i$. Hence, if $j \ge 1$ is the smallest value of $i$ for which $\ell(i) \le c\_i$, you have that the optimal solution to your problem has cost $\min\\{ c\_{j}, \ell(c\_{j-1}) \\}$.

The value $j$ can be found by binary searching over $c\_0, c\_1, c\_2, \dots, c\_k$. Since there are at most $m$ distinct costs, this requires computing $O(\log m) = O(\log n)$ values $\ell(\cdot)$ and the overall time complexity is $O(m \log n + n \log^2 n)$.

---
Tags: graphs, optimization
---


# Question
Title: How many bits are required to encode information in probability set G = [0.001, 0.002, 0.003, 0.994]?
I am currently working on data compression and thought it would be a good time to read up on the basics of information theory to better understand data compression and its algorithms.

As I understand, given a set of data, we can compute the minimum no. of bits on average required to encode the data my multiplying the rounded-up entropy value with length of the set. Following is the formula to compute the entropy of a set:

$$H ( X ) = −\sum i = 1 N p ( x\_i ) \text{log}\_2  ( p ( x\_i ) )$$

So, for a set $G = \\{A,B,B,C,C,C,D,D,...D\\}$ of length 1000, the probability set would be $\\{0.001, 0.002, 0.003, 0.994\\}$ and the Entropy would be 0.06. Rounding this up would give 1. This means 1 * 1000 = 1000 bits would be required to encode this set.

This would entail I use only 1 bit per symbol to encode this whole set. I am unable to understand how can I use just 1 bit per symbol when there are 4 unique symbols in the set. Won't I require 2 bits per symbol at least? $G = \\{00, 01, 01, 10, 10, 10, 11, 11, ..., 11\\}$.

But this would lead to a usage of 2000 bits in total betraying the value computed using entropy. What am I missing here?

# Answer
Using a fixed-length code, you indeed need two bits and the average length is 2.

With a variable-length code, you will reserve a single bit (say 0) for the most frequent symbol, and two or three bit numbers (say 10, 110 and 111) for the remaining cases. The average length will remain close to 1.

> More precisely 1.009.
> 1 votes

---
Tags: information-theory, data-compression, entropy
---


# Question
Title: Non-overlaping fixed-width ranges with most occurrences
I have encountered a following problem:

Given the list of $k$ values from range $\[v\_{min}; v\_{max}\]$, find $m$ non-overlaping ranges of length $l$, such that maximises the number of values from the original range that would fit into those new ranges.

For example:
Given a list `[2, 3, 4, 5, 10, 11, 12, 21, 22, 30, 31, 32, 33, 40, 60, 61]`, if I wanted to find $m = 2$ ranges of length $l = 3$, the best solution would be choosing the ranges $\[2; 5\]$ and $\[30; 33\]$, for the total of eight common values—`[2, 3, 4, 5, 30, 31, 32, 33]`.

Mind you, in general case, there is *no* assumption that the values are integers.

Is that a known problem? What should I look for?

# Answer
I didn't encounter that question, but what I would do is use Counting sort(Because we have the range of values) and then I would loop over the sorted array and choose those m parts, I didn't quite understood the part - " find m non-overlaping ranges of length l, such that maximises the number of values from the original range that would fit into those new ranges." but, in general, this costs you a linear time and choosing ranges will also cost you linear time, so in general: $O(n)$
> -1 votes

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


# Question
Title: Does 'reverse' mean 2 separate things in contexts of tree vs. graph traversal?
I'm somewhat confused about the Wikipedia terms about the meaning of 'reversed' in the context of tree & graph treversals

Suppose I have a tree:

```
         1
        / \
       /   \
      /     \
     /       \
    2         3
   / \       /
  4   5     6
 / \       / \
7   8     9  10

```

Tree traversal article describes reversed traversal as going right-to-left as opposed to left-to-right;

so according to it the tree has preorder traversal

1 2 4 7 8 5 3 6 9 10

and reverse preorder traversal

1 3 6 10 9 2 5 4 8 7

However, the DFS article describes reverse orderings as just the reversed version of a usual one (while left-to-right vs. right to-left is AFAIU left undefined);

so according to this article both of the above are preorderings, while

10 9 6 3 5 8 7 4 2 1 is the reverse preordering for the 1st one, and

7 8 4 5 2 9 10 6 3 1 is the reverse preordering for the 2nd one.

(I realize the last two are the two post-order traversals in the first article's sense.)

So, are there two different terminologies in contexts of trees and general graphs respectively? Isn't there a mistake in some of these articles?

If there's no mistake, then, if asked to find a reverse preorder of a given graph (tree), I guess I should clarify which meaning of 'reverse' a person implies, right?

# Answer
You are right. "Reverse" in the context of *binary trees* does not mean the same as "reverse" in the context of general graphs. In general graphs, "reverse" preorder/postorder simply means putting the nodes in the opposite order as they appear in the normal preorder/postorder trace. For example, if the preorder trace is A, B, C, D, the reverse preorder trace will be D, C, B, A. The same goes for postorder. However, in binary trees, it means a different thing; swapping left and right child nodes in the recurrence relations (or going *right-to-left* instead of *left-to-right*):

```
Preorder:          root, (left), (right)
Reverse preorder:  root, (right), (left)

Postorder:         (left), (right), root
Reverse postorder: (right), (left), root

# this ordering only exists in binary trees
Inorder:           (left), root, (right)
Reverse inorder:   (right), root, (left)

```

Notice that `(node)` means to recursively apply the ordering to the specified node.

Also, bear in mind the difference between preorder/postorder in a graph and preorder/postorder in a binary tree. In a binary tree only one preorder and postorder traversal exists, whereas a graph can have many preorder and postorder traversals, since the order in which successors should be expanded is not defined (i.e. there is no concept of left or right child in a general graph). Another difference is that with general graphs, one has to take care of preventing cycles and handling disconnected components, which by definition, do not occur in a tree:

> A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
> 3 votes

---
Tags: binary-trees, graph-traversal
---


# Question
Title: Efficiently determine which nodes should leave a graph while maintaining connectedness
Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:

If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a node has positive weight, it is "unhappy", and can be kicked out of the graph.

How do I efficiently calculate which **unhappy** nodes I should kick out of the graph in order to minimize unhappiness, i.e., the total weight of all unhappy nodes, while making sure that the graph remains connected?

For instance, in this case, I can't get rid of more than three unhappy nodes, since that would disconnect the graph. Out of the possible sets of three unhappy nodes, {10, 10, 8} disconnects the graph as well. Thus the optimal solution is removing the three unhappy nodes at bottom, so that only the two unhappy nodes at top remain. The unhappiness of the graph becomes 2 + 10 = 12, which is the minimum.

(Motivation: I was wondering how many unhappy counties can secede from a U.S. state without breaking the state into disconnected components, and got this graph problem that I can't figure out.)

# Answer
The problem is equivalent to the node-weighted version of the Steiner tree problem. Happy nodes correspond to terminals, and non-removed unhappy nodes correspond to Steiner vertices.

This problem is NP-hard even for planar graphs. The NP-hardness can be proven by reducing the edge-weighted Steiner tree problem: insert one vertex in the middle of each edge.

The Dreyfus-Wagner algorithm can be used for the node-weighted version as well, and runs in $O(3^k \mathrm{poly}(n))$ time where $k$ is the number of terminal nodes. If $n - k$ is small compared to $k$, bruteforcing Steiner vertices gives $O(2^{n-k} \mathrm{poly}(n))$ time bound.
> 5 votes

---
Tags: graphs, optimization, weighted-graphs, connected-components, max-cut
---


# Question
Title: What is the definition of a redex and what are they for in programming languages literature?
I saw the word "redex" in the context of proramming language theory/semantics in 2018 and now when I was reading a neurosymbolic research paper (machine learning with neural nets + symbolic algorithms).

The research paper said:

> Constructing $I\beta'$ (operator that inverts one step of beta-reductions/function applications) depends on careful consideration of the reduction operator we aim to invert (see \[39\] and Appen- dix F). The operator $I\beta'$ builds both top-level redexes and also recurses to build redexes within the body of an expression

The 2018 course says:

> In an RSEC language definition one starts by defining the syntax of evaluation contexts, or simply just contexts, which is typically done by means of a context-free grammar (CFG). A context is a program or a fragment of program with a hole, where the hole, which is written $\Box$ , is a placeholder for where the next computational step can take place. If $c$ is an evaluation context and $e$ is some well-formed appropriate fragment (expression, statement, etc.), then $c\[e\]$ is the program or fragment obtained by replacing the hole of $c$ by $e$. Reduction semantics with evaluation contexts relies on a tacitly assumed (but rather advanced) parsing mechanism that takes a program or a fragment $p$ and decomposes it into a context $c$ and a subprogram or fragment $e$, called a redex, such that $p = c\[e\]$. This decomposition process is called splitting (of $p$ into $c$ and $e$). The inverse process, composing a redex $e$ and a context $c$ into a program or fragment $p$, is called plugging (of $e$ into $c$). These splitting/plugging operations are depicted in Figure 3.28.

**So is a redex just a fragment of a program? Is that all? Curious why this needs a term of its own. It's use and importance.**

---

cross: https://www.quora.com/unanswered/What-is-the-definition-of-a-redex-and-what-are-they-for-in-programming-languages-theory

# Answer
A redex is an expressions on which we can perform a computation step, such as:

1. `fst (a, b)` is a redex, it computes to `a`
2. `snd (a, b)` is a redex, it computes to `b`
3. `(λ x . x + x) 6` is a redex, it computes to `6 + 6`
4. `if true then A else B` is a redex, it computes to `A`

Here are some examples which are *not* redexes: `fst p`, `if x < 6 then 3 else 4`, `42`, `λ x . x + x`.

An expression may *contain* a redex, for instance in

```
λ x . if x < 6 then fst (4, 5) else x

```

there is a redex, namely `fst (4, 5)`. In general, an expression may contain main redexes. Which ones are evaluated and in what order depends on how the language is designed.
> 2 votes

---
Tags: programming-languages, semantics, operational-semantics, denotational-semantics
---


title: Big O- and Omega-Notation for functions

text:
# Question
Title: Big O- and Omega-Notation for functions
I want to find out how to check, if the following relationships are true or false.

f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false;

f(n) = 3n^2; g(n) = 9^(base3-logn); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false;

I am very new to this topic, so i would be very grateful, if someone could explain it to me. If something is not understandable, don't hesitate and ask me.

Thank you in advance.

# Answer
> 0 votes
In second example if you have $f(n)=3n^2$ and $g(n)=n^2$, then, of course $f(n)=\Theta(g(n))$.

For first enough to note, that $n! \< (2n)^{3n}$.

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


title: Paxos made simple -- two details

text:
# Question
Title: Paxos made simple -- two details
I'm missing two details from Paxos made easy

**P1. An acceptor must accept the first proposal that it receives.**

1. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. *Upon receiving a proposal: acceptor memorizes the proposal as most recent proposal; if acceptor is not waiting with a running countdown, a countdown of Xmsec is set up; upon a countdown timeout acceptor accepts the most recent proposal*

I'm **not** proposing the above rule as better or more interesting -- rather I'm posing a question of which exactly requirement is fulfilled by following P1.

**Observe that P1a subsumes P1.**

2. What does this mean? That P1a is more general? Fulfilling P1a fulfills P1? At least scenario mentioned in section 2.4 suggest P1a does not imply P1. What am I missing?

# Answer
> What exactly is the reason for rule P1?

The paper says:

> We use the customary asynchronous, non-Byzantine model...

In other words, it assumes that everything can take an arbitrarily long time to happen, but no messages are corrupted in transit and all agents obey the protocol.

What this means is that it would be perfectly fine to write the timeout-based rule as you describe, but it would be harder to describe and analyse and yet it would not satisfy any different properties from a protocol that has no timeouts: the asynchronous model already allows for arbitrary delays and message-reordering, so adding any further delays and message-reordering doesn't gain anything.

> What does "P1a subsumes P1" mean?

It means it replaces P1. The sentence after P1 starts ...

> But this requirement raises a problem.

... which means that P1 isn't the correct requirement. The correct requirement is in fact P1a.
> 2 votes

# Answer
Regarding your second question, it means $P1^a$ is stronger and therefore implies $P1$. Therefore it "includes", "absorbs", "subsumes" $P1$.
> 0 votes

# Answer
1. > What exactly is the reason for rule P1?

P1 satisfies liveness property only in cases without failure or message loss. That is what the paper says:

> In the absence of failure or message loss, we want a value to be chosen even if only one value is proposed by a single proposer.

Unlike P2 which guarantees the crucial safety property, P1 did not guarantees liveness property in general cases.

2. > What does "P1a subsumes P1" mean?

In context of P1, there's no concept of "A promise never again to accept a proposal numbered less than n" in `prepare request`. In other words, in context of P1a, a proposal could be either `acceptable` or `not acceptable`, but in context of P1, all proposal is `acceptable`. In context of P1a, P1 could be rewritten as:

*P1. An acceptor must accept the first **acceptable** proposal that it receives.*

and P1a indicates:

*An acceptor must accept **all acceptable** proposal that is receives*

which means P1a is stronger and subsumes P1.
> 0 votes

---
Tags: distributed-systems, concurrency, consensus
---


# Question
Title: Prove that the language of all Turing machines that accept finitely many words is decidable or not
Question: we have the following language: $$A = \\{\langle M \rangle :| L( M)| \< \infty \text{ and } M\text{ is a Turing machine}\\}$$ where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is the language accepted by $M$. Prove $A$ is a decidable language or not.

---

My idea was to use reduction on this but I can't find the proper one and I don't even know if it is decidable or not.

# Answer
We can reduce from $A\_{TM}$ to prove $A$ is undecidable and also from $\overline{A\_{TM}}$ to prove $A$ is unrecognizable. We proceed with the first claim. I recommend you pause here and think about how it could be done before moving forward. The core idea is excatly what Steven suggested that is to specify a Turing machine $M'$ to simulate another Turing machine $M$. (in the case of reduction from $A\_{TM}$, the machine-input pair $\langle M, w \rangle$ has to be manipulated by $M'$ such that $M'$ accepts finitely many strings if and only if $M$ accepts $w$.) We can describe $M'$ informally as follows:

1. On input $n \in 1^+$ (namely reject all but unary representations)
2. Simulate $M$ on $w$ for at most $n$ steps. If $M$ halted and accepted during simulation, reject $n$. Otherwise accept $n$.

If $M$ accepts $w$ after $k$ steps, $L(M')$ would be $\\{1, 2, \dots, k - 1\\}$. Otherwise, $L(M') = \mathbb{N}$. Therefore $\langle M, w \rangle \in A\_{TM} \iff M' \in A$ or $A\_{TM} \leq\_m A$. Similarly by swapping "accept" and "reject" in the description of $M'$, we obtain the mapping reduction $\overline{A\_{TM}} \leq\_m A$.
> 1 votes

---
Tags: formal-languages, turing-machines, reductions, undecidability
---


# Question
Title: Peterson's Algorithm | Context switch after turn=process
Suppose we have two processes P0 and P1 using Peterson's Algorithm to access a critical section.

Process P0 starts executing and sets its interested to TRUE and turn is set to 0. A context switch happens right after and process P1 starts executing. P1 sets `interested[1]=TRUE` and `turn=1`. But since process P0 is also interested, process P1 will end up in a busy waiting (caused by `interested[other]==TRUE`). Eventually a context switch back to P0 will happen but since `turn=1` it will also end up in a busy waiting (caused by `turn==process`).

`P0 P1`
`----------------------------------------`
`other=1`
`interested[0]=TRUE`
`turn=0`
`**CONTEXT SWITCH**`
`other=0`
`interested[1]=TRUE`
`turn=1`
`while()`
`.`
`.`
`.`
`**CONTEXT SWITCH**`
`while()`
`.`
`.`
`.`

Wouldn't this cause a problem since both processes are waiting and neither can access the critical section? Am I missing some details?

# Answer
> 0 votes
The algorithm snippet you linked is wrong. Processes in Peterson's algorithm are humble. So, when P0 wants to enter critical section, it sets `interested[0] = TRUE` and `turn = 1`. Yes, it lets other process to have a turn. Similar for P1. Here is the correct pseudocode.

`P0 P1`
`----------------------------------------`
`other=1`
`interested[0]=TRUE`
`turn=1`
`**CONTEXT SWITCH**`
`other=0`
`interested[1]=TRUE`
`turn=0`
`while()`
`.`
`.`
`.`
`**CONTEXT SWITCH**`
`while()`
`**P0 enters critical section**`
`.`
`.`

---
Tags: critical-section
---


# Question
Title: Why we dont use dot operator with int or any other datatype
Okay so imma noob as my question itself will suggest . And I know that of If I want to access a public class member we have to use the dot operator with the object . So we know that int , float etc are also classes ..so why don't we use dot operators with the variables of that data type...?

# Answer
There are languages where "everything is an object". The archetype is Smalltalk, although Smalltalk does not think in terms of "method calls", but rather "messages".

In Smalltalk (and its offshoots like Squeak), mathematical operations on numeric classes are binary messages. This has interesting implications when it interacts with Smalltalk's syntax. This:

```
3 + 2 * 5

```

returns `25`, not `13`, because you send the "plus 2" message to 3, and then the "times 5" message to that. There's no reason why there can't be better syntactic sugar, of course.

This approach also has nontrivial interactions with the type system of the language, especially if the language is more strongly typed, because real algebras are often many-sorted. Consider, for example, how you would represent `time` and `duration` types. Conceptually, a `duration` is the difference between two `time`s. It makes sense to add one hour to three hours (`duration + duration`), and it makes sense to add one hour to 3pm (`duration + time`), but it doesn't make sense to add 3pm to 4pm (`time + time`).

Expressing this as methods in a way that also allows generic functions which take any two types that can be "added together" is not easy when you have a Simula-like object model.

In most programming languages where most things are objects, basic types typically are not objects. As Steven pointed out in a comment, this isn't true of Java, but Java provides classes which wrap them if you need to treat them as objects. It's a similar (though not identical) story with C#.

Another increasingly common approach is to use what Haskell calls "type classes" and Rust calls "traits". In these languages, a class is not a type, but a collection of types which have common operations. Both Haskell and Rust have ways to declare that a type is a member of a numeric operation class without making those operations "methods" of the type.
> 3 votes

---
Tags: object-oriented
---


title: How to show that $n^2 = O(f(n-1)+n)$?

text:
# Question
Title: How to show that $n^2 = O(f(n-1)+n)$?
This is from Ex. 0.2.(b) from "Computational Complexity" by Arora and Barak (2009):

One needs to find a non-recursively defined function $g$ s.t. (1) $f = O(g)$ and (2) $g = O(f)$, where $f(n)=f(n-1)+n$ for $n \> 10$ (and $f(1) = ... = f(10) = 1$). Solution booklet says that $g(n) = n^2$, but I cannot see how to prove (2) i.e. I cannot show that for some $c$, $n^2 \leq c(f(n-1)+n)$ for large enough $n$.

# Answer
> 1 votes
$$f(n)=f(n-1)+n = f(n-2)+(n-1)+n = \\ =\cdots =\\ =n + (n-1) + (n-2)+ \cdots +(n-(n-10)+1)+f(n-(n-10))$$ Hope, You can finish from here.

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


# Question
Title: Is there a theorem of the form "for any complexity class $C$ satisfying $X$, there exist $C$-complete problems"?
From what I've read, there are $C$-complete problems for all the complexity classes $C$ that I have looked at: $P$, $NP$, $EXPTIME$, $PSPACE$. But I also know that there is an infinite hierarchy of complexity classes. I'm wondering if there are uniform/general reasons that complexity classess have problems that are complete for that class, or whether the "reason" for this is different for each class, i.e. requires a specific idiosyncratic proof. Is there a general proof that shows for a large set of complexity classes $C$ that they have $C$ complete problems?

# Answer
> 3 votes
> Is there a general proof that "for any complexity class , there exist -complete problems"

No, there is no general proof of this. In fact, while the complexity classes you mention (P, NP, PSPACE, EXPTIME) are known to have complete problems, beyond these many complexity classes don't.

Probably the simplest case of this phenomenon is when C is defined as an infinite union, as some important complexity classes are. For example, the polynomial hierarchy, which is an infinite union of complexity classes that generalize NP and coNP. The easiest way to understand it is that we can define an operation $\Delta$ on complexity classes that contains union of N and coN for that complexity class, so $\Delta$P contains both NP and coNP, and then we can keep repeating $\Delta$ to get bigger and bigger classes: $\Delta$P, $\Delta \Delta$P, $\Delta \Delta \Delta$P, and so on. The complexity class PH (polynomial hierarchy) is the union of all of these.

Now the reason that PH doesn't have (as far as we know) any complete problems is this: while each individual class P, $\Delta$P, $\Delta \Delta$P, ... has complete problems, most researchers believe that each one is bigger than the next. And if you have a union of bigger and bigger complexity classes, each with complete problems, then the result can't have any complete problems. (In particular: any candidate complete problem in PH must be a member of one of the individual classes $\Delta^i$ P for some $i$, but then it wouldn't be complete for the problem in $\Delta^{i+1}$ P and not in $\Delta^i$ P.)

Finally, it's important to note that what count as a "complete class" depends on what type of reductions you are considering. The most common type of reductions to consider are polynomial-time reductions, but for complexity classes smaller than P, there are a bunch of other kinds of reductions considered, including logarithmic-space reductions and first-order reductions.

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


# Question
Title: What are common ways to distinguish between local minima and long run-time in hyperparamteer optimization
I'm using Bayesian optimization for a pretty cost expensive function in the context of neural networks in order to optimize hyperparameters for the neural net.

Is there a general, quantitative way to distinguish between becoming stuck in a local minimum in the optimization or just long running time of the process?

# Answer
In general, no. Perhaps here is only one unique input that makes the function produce an enormously negative output; or perhaps there is none. You can't tell the two apart without having examined a large fraction of all possible inputs to the function.
> 5 votes

---
Tags: optimization, machine-learning, neural-networks
---


# Question
Title: Relationship between cartesian product and dependent product type
**Introduction:**

Hi, I'm quite new to types so apologies in advance for the basic question and for any abuse of terminology. I believe I have a critical misunderstanding of dependent product types (and probably about types in general to be quite honest). My questions is based on a reading of Andrej's very helpful answer here.

I see the relationship between dependent ***sum*** types and the cartesian product, but I do not see the relationship between dependent ***product*** types and the cartesian product.

**Question / Ask:**

I was wondering if someone could provide a slower, step-by-step walkthrough of how to get to cartesian products from a special case of dependent product types (specifically how we get an ordered tuple from a dependent function).

**My Thoughts:**

In the first and second paragraphs of Andrej's answer, he relates a binary product to a dependent product type, stating first that we can write a binary product of sets as $\Pi\_{i\in I}X\_{i}$ and then stating second that we can write a dependent product type as $\Pi(i:I)X(i)$ which can then be used to get a binary product $A \times B$ as a special case if we take $I = \text{Bool}$, $X(\text{false})=A$, and $X(\text{true})=B$.

However, in my head these two $\Pi$ symbols mean something fairly different. In the first ($\Pi\_{i\in I}X\_{i}$), we are describing a set of ***ordered tuples*** $\\{(x\_1,x\_1,\ldots,x\_n) \space | \space x\_1 \in X\_1 , x\_2 \in X\_2, \ldots, x\_n \in X\_n\\}$ where every combination of $(x\_1, x\_2, \ldots, x\_n)$ is accounted for, whereas in the second ($\Pi(i:I)X(i)$), we are describing the type of a ***function*** that maps every element $i : I$ to an element in $X(i)$, where it's not necessarily true that for every $x \in X(i)$ there exists a function $f\_x$ such that $f\_x(i) = x$. How do we get an ordered tuple from a function?

To add to my confusion, the explanation of dependent product types on ncatlab here explicitly states the following:

> It \[dependent product types\] includes function types as the special case when B is not dependent on A. Note that a binary product type is rather different, being actually a special case of a dependent sum type.

# Answer
> 1 votes
Lets introduce $\[n\] = \\{1,...,n\\}$ as a convenience type and look a function $f$ in $\Pi (i:\[n\]) X(i)$. Now $f\[i\]$ maps to $x\_i \in X\_i$. So we could think of $f$ as an ordered sequence/tuple: $f \simeq (x\_1,...,x\_n)$. Of course for different indexing types its not an ordered tuple in the "classical integer index" sense.

Also $\Pi (i:\[n\]) X(i)$ contains *all* of the $n$-long tuples and just some as you thought; so for every $x \in X\_i$ there is $f\_x: \Pi(i:I)X(i)$ with $f\_X(i) = x$.

The last quote is easy to misunderstand; what they try to say is $A \times B = \Sigma (a:A) B $. Where the second object is a dependent sum type $\Sigma (a:A) B(a)$. With $B(a) = B$ constant. I usually think of inhabitants of $\Sigma (a:A) B(a)$ as a pairs $(a, b\_a \in B(a))$ and of $\Pi(i:I)X(i)$ as functions $f(i) = x\_i \in X\_i$. At "runtime" the a function can be evaluated at any $i$ but a pair is fixed.

---
Tags: type-theory, dependent-types
---


# Question
Title: State Complexity of DFAs for Restricted Languages
Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.

Definitions: If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $L \subseteq \Sigma^\*$, define $L\_n \subseteq L$ to be the set of strings in $L$ of length $n$: $L\_n = \\{s \mid s \in L \\; \textrm{and} \\; |s| = n \\}$.
Since $L\_n$ is finite, it can be recognized by a deterministic finite-state automaton (DFA) $M\_{L,n}$ that is minimal and acyclic.
A $\textit{level}$ of an acyclic DFA is the set of all states at the same depth as measured from the start state.

We are given the following constraint on $L$:

$$ | L\_n | = O(n^c) $$ where $c$ is a constant that depends on $L$ but not on $n$.

Now if we take the set of all prefixes of a certain length $d$,

$$ S\_{n,d} = \\{ v \mid vw \in L\_n, |v| = d \\} $$

$S\_{n,d}$ is also similarly bounded:

$$ | S\_{n,d} | = O(n^c) $$

So even if, in the worst case, all strings in the $S\_{n,d}$ are Myhill-Nerode distinguishable from each other, there are therefore only $O(n^c)$ states at depth $d$ in $M\_{L,n}$.

> So can we conclude that: given a language $L$ such that $ | L\_n | = O(n^c) $ where $c$ is a constant, the minimal acyclic DFA that recognizes the subset $L\_n \subseteq L$ has only $O(n^{k})$ states for some fixed $k$?

# Answer
> 1 votes
If $L\_n$ contains $m$ words, then it is accepted by a DFA having at most $nm + 2$ states. The DFA has a state for each prefix of each word in $L\_n$, together with a sink state. In particular, if $|L\_n| = O(n^c)$, then the state complexity of $L\_n$ is $O(n^{c+1})$.

The following example shows that a loss of a factor of $n$ is inevitable. Consider the language $L$ over $\\{0,1\\}$ of all words containing at most $\ell$ runs. For example, if $\ell = 2$ then the language is $0^\*1^\* + 1^\*0^\*$. For this language, $|L\_n| = \Theta(n^{\ell-1})$ while the state complexity of $L\_n$ is $\Theta(n^\ell)$.

If $|L\_n| = \Theta(n^c)$ for some regular language $L$ then $c \in \mathbb{N}$, so the example above covers all possible cases.

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


# Question
Title: Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?
Assume we have an algorithm consists of several (assume m and m\<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m\*O(\log N)$ or it is $O(\log N)$. which one? Based on what I understand as the complexity is an approximation, the complexity is $O(\log N)$ but it does not make sense.

what about when we have different combination of big-Os like $O(N), O(N^2), O(N/2)$? we should choose the worst one; $O(N^2)$.

# Answer
We have property $$O(f)+O(f)=O(f)$$ which means, that you can add big-$O$ fixed amount times and still get same. It's like your program have several consecutive parts with one and same complexity. Then all program have that complexity.

As to second question, then you can try to prove following $$ O(n^{k}) + O(n^{m}) = O(n^{m}) $$ when $ m\>k\>0 $

**Addition.**

Assume $ \varphi \in O(n^{k}) + O(n^{m}) $. This means, that $ \varphi = \varphi\_{1} + \varphi\_{2} $, where $ \varphi\_{1} \in O(n^{k}) $ and $ \varphi\_{2} \in O(n^{m}) $, i.e. are true following sentences: $$ \exists C\_{1} \> 0, \exists N\_{1} \in \mathbb{N}, \forall n \> N\_{1},\ \varphi\_{1} \leqslant C\_{1} \cdot n^{k} $$ $$ \exists C\_{2} \> 0, \exists N\_{2} \in \mathbb{N}, \forall n \> N\_{2},\ \varphi\_{2} \leqslant C\_{2} \cdot n^{m} $$ So we can write $$ \varphi = \varphi\_{1} + \varphi\_{2} \leqslant C\_{1} \cdot n^{k} + C\_{2} \cdot n^{m} = n^{m}\left( C\_{1} \cdot n^{k-m} + C\_{2} \right) $$ when $n\>\max(N\_1,N\_2)$. Because $ n^{k-m} \<1 $, then $ \varphi \leqslant C \cdot n^{m} $, where $ C = C\_{1}+C\_{2} $. So, we obtain $ O(n^{k}) + O(n^{m}) \subset O(n^{m}) $.
> 2 votes

---
Tags: asymptotics, big-o-notation
---


title: Simulated Annealing - Intuition

text:
# Question
Title: Simulated Annealing - Intuition
Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below:

```
Let s = s0
For k = 0 through kmax (exclusive):
  T ← temperature( 1 - (k+1)/kmax )
  Pick a random neighbour, snew ← neighbour(s)
  If P(E(s), E(snew), T) ≥ random(0, 1):
    s ← snew
Output: the final state s

```

I am having trouble understanding how this algorithm does not get stuck in a local optima as the temperature cools. If we jump around at the start while the temp is high, and eventually only take uphill moves as the temp cools, then isn't the solution found highly dependent on where we just so happened to end up in the search space as the temperature started to cool? We may have found a better solution early on, jumped off of it while the temp was high, and then be in a worse-off position as the temp cools and we transition to hill climbing.

An often listed modification to this approach is to keep track of the best solution found so far. I see how this change mitigates the risk of "throwing away" a better solution found in the exploratory stage when the temp is high, but I don't see how this is any better than simply performing repeated random hill-climbing to sample the space, without the temperature theatrics.

Another approach that comes to mind is to combine the ideas of keeping track of the "best so far" with repeated hill climbing and beam search. For each temperature, we could perform simulated annealing and track the best 'n' solutions. Then for the next temperature, start from each of those local peaks.

# Answer
> 1 votes
Yes of course it can get stuck in a local optimum. The idea is that hopefully we get closer to the global optimum, and if we get stuck in a local optimum, hopefully it'll be close to the global optimum... or maybe even exactly in the global optimum.

It's important to understand that there are no guarantees. Simulated annealing is a heuristic. So, yes, it is absolutely possible that it goes awry. And it doesn't necessarily find the absolute global optimum -- even just finding a near-optimal solution might be considered a victory.

---
Tags: algorithms, optimization, combinatorics, search-algorithms, simulated-annealing
---


# Question
Title: Factor a number in the longest possible product of distinct numbers
I got stuck with quite a simple problem:

Given a positive number $X$ find the largest number $k$, for which exists the positive **distinct** integers $Y\_1,…,Y\_k$ such that $(Y\_1+1)(Y\_2+1)⋯(Y\_k+1)=X$

Any of my approaches based on integer factorization or working with the divisors of the $X$ have failed. For example all my tries have failed to solve the problem for $X=684913065984000$. A correct solution in this case is $k=15$, with $Y=\[1,2,3,4,5,6,7,8,9,11,15,19,23,31,63\]$.

Can anyone help me with a solution? My guess is that we may need some *DP* but I can't come with any kind of practical approach.You may find this problem on the **Kattis** online judge here

# Answer
> 2 votes
First, we factorize the integer and then we convert the problem to a multiset partition problem. The multiset partition problem can be solved by a **backtracking** algorithm.

Given an integer $n$, let its factorization be $n=p^{a\_1}\_1\cdot p^{a\_2}\_2 \cdots p^{a\_m}\_m$ where $p\_1, \cdots, p\_m$ are distinc primes. We list all the primes in a multiset $S=\\{p\_1, \dots, p\_1, \dots, p\_m,\dots, p\_m\\}$. For example, if $n=3600=2^4\cdot3^2\cdot5^2$, we have $S=\\{2,2,2,2,3,3,5,5\\}$. Then the problem is equivalent to partition $S$ into distinct subsets such that the number of the subset is maximized. This is because, if two sets of primes are different, then the product of primes in one set is not equal to that in another set.

Then we can use a standard backtracking algorithm to solve the multiset partition problem. In each step of the algorithm, a subset that hasn't been subtracted yet is obtained and deleted from the current $S$. The search acts like a depth-first search for trees. As an example, the backtracking tree of a set $\\{a, a, b\\}$ is given below. Each non-root node stands for the currently obtained subset. The red leaf means that after we subtract the subset of the red leaf from $S$, all the subsets of $S$ are already used in previous steps. The path from the root to a white leaf stands for a feasible partition.

Note: This is the most naive backtracking algorithm. I believe it can be improved by some observations. For example, the subset that contains exactly one element must be in one optimal solution (can someone prove it?). And if the number of two elements is the same in $S$, can one element be pruned in the recursion tree?

# Answer
> 2 votes
This answer is on the **dynamic programming** algorithm to solve the problem. I think it's better to present it as a new answer, instead of attaching it to my previous answer about the backtracking algorithm.

Define a *distinct* factorization as the factorization of distinct factors. Let the *order* of a factorization be the number of factors in that factorization. And let an *optimal* factorization be a feasible factorization of the maximum number of factors. Note that $1$ is not considered in all factorizations.

Given $n, m\in \mathbb{N}$, let $f\[n,m\]$ be the maximum order of distinct factorizations of $n$ whose smallest factor $\ge m$. Thus, $f\[n,2\]$ is exactly what we want. We distinguish between two cases depending on whether $m$ is chosen as a factor or not. If not, then we increment $m$ by $1$ and have $f\[n,m\]=f\[n,m+1\]$. Otherwise, we have $f\[n,m\]=f\[n/m,m+1\]$. Note that if $m/n$ is not an integer, the procedure has to stop. Also, if $n\< m$, by the definition of $f\[n,m\]$, the procedure also terminates. Finally, if $n=m$, we have $f\[n,m\]=1$. The transition function is as follows:

$$ f\[n,m\]= \left\\{ \begin{array}{} -1, & \text{if } n \notin \mathbb{Z} \text{ or } n \< m \\ 1, & \text{if } n=m \\ \max\\{f\[n,m+1\], f\[n/m,m+1\]+1\\}, & \text{otherwise} \end{array}. \right. $$

The dynamic programming algorithm runs in $O(n^2)$. It is pseudo-polynomial time.

**Note**: The intuition is that given an integer $n$, instead of carrying out the prime factorization immediately and then dealing with the prime factors, we can just divide $n$ by $2$, if divisible, we divide $n/2$ by $3$, if divisible, divide $n/(2\cdot3)$ by $4$, and so on and so forth (that's what I did before I came up with this dynamic programming algorithm). Of course, the method may give a non-distinct factorization, for instance, $12=2\cdot 3 \cdot 2$. Even when a distinct factorization is obtained by this method, it may not be the one of the maximum order (the number $684913065984000$ given by the OP is of this case).

# Answer
> 0 votes
Solving this problem will in the worst case require an exhaustive search with possibly exponential growth. We modifiy the problem slightly to reduce the search space.

Given $X ≥ 2$, we call $X\_1, X\_2, ... , X\_k$ an "exact factoring of $X$" if the $X\_i$ are all distinct, greater than 1, and their product $P$ equals $X$. An "optimal exact factoring of $X$" is an exact factoring that has the largest possible number $k$ of factors, and we want to find an "optimal exact factoring of $X$".

Instead we call $X\_1, X\_2, ... , X\_k$ a "factoring of $X$" if their product $P$ is not necessarily equal to $X$, but only divides $X$. An "optimal factoring of $X$" is a factoring with the largest number $k$ of factors.

Given an optimal factoring of $X$ with $k$ factors we can easily solve the original problem: An optimal factoring has $k ≥ 1$ since $X\_1 = X$ is one possible factoring. As long as $P ≠ X$, let $p$ be any prime factor of $X / P$, find an $X\_i$ that has the factor $p$ raised to the highest power (which may be 0), and multiply $X\_i$ by $p$. Eventually this gives us an exact optimal factoring with the same $k$. Since an exact optimal factoring of $X$ is also an optimal factoring, it cannot have more than $k$ factors; and we found an exact optimal factoring that has exactly $k$ factors, therefore the exact optimal factoring has indeed $k$ factors, and we found it.

We may assume that $X$ has the form $X = 2^{n\_1} \cdot 3^{n\_2} \cdot 5^{n\_3} ...$. If not, then we factor $X$ into a product of prime powers, arrange the product by sorting the exponents in non-descending order, replace the primes with 2, 3, 5, 7 and so on, solve the problem, then replace the primes back with the original ones. For example if $X = 3 \cdot 7^3$ then we find an optimal factoring of $X = 2^3 \cdot 3$ with the solution \[2, 3, 4\], and replace it with \[7, 2, 49\].

So we just solve the problem of finding an optimal factoring of $X$. Next we add a restriction to the solution that we want to find: We want an optimal factoring of $X$ with the property that if $X\_i$ is a factor, and $2 ≤ Y \< X\_i$ divides $X\_i$, then Y is also one of the factors: If this is not the case, then we replace $X\_i$ with Y and get another optimal factoring with smaller numbers, and we can repeat this until no such Y exists.

We call such a factoring a restricted optimal factoring. There is always a restricted optimal factoring with the same number $k$ of factors, and it should be easier to find because the search space is smaller. This means that for example a restricted optimal factoring containing a factor $a \cdot p$ with $a ≥ 2$ and p prime, then it must also contain factors a and p, therefore $X$ is divisible by $p^2$.

If $X$ has a factor $p$ but not $p^2$ for some prime $p$, then one of the factors must therefore be $X\_i$ = p. So in this case we can solve our problem by finding a restricted optimal covering for $X / p$ and adding a factor $p$. This will simplify many problems; as a special case, the optimal factoring for a square free number is the set of its prime factors.

If a restricted optimal covering has a factor $X\_i = p^n$ for some prime p, $n ≥ 2$, then it has also factors $p^j$ for $1 ≤ j \< n$. $X$ is therefore divisible by $p^{t(n)}$, where t(n) is the n-th triangular number (number in the sequence 1, 3, 6, 10, 15, 21, ...)

If $X$ has a factor $X\_i = a \cdot p^n$ for some prime $p$, $a ≥ 2$, and $n ≥ 1$, then it also has factors $a \cdot p^j$ for $0 ≤ j \< n$, and factors $p^j$ for $1 ≤ j ≤ n$, so $X$ is $X$ is divisible by $a^{n+1}$ and by $p^{2 t(n)}$.

With the example number $=2^{30} \cdot 3^6 \cdot 5^3 \cdot 7$ (more to follow ...)

# Answer
> -1 votes
It does indeed have to do with divisors and factorisation. Let the factorisation be $N=p\_1^{a\_1} p\_2^{a\_2}\cdots p\_k^{a\_k}$ with $a\_i \geq 1,$ and $p\_1\<p\_2\<\cdots\<p\_k$ be the distinct primes dividing $N.$

Form the list of all prime powers dividing $N$ so that for example $p\_1$ is represented as $p\_1,p\_1^2,\ldots,p\_1^{a\_1}$ in this list. Sort the list from small to large entries and denote the list by $\[x\_1,x\_2,\ldots,x\_{a\_1+a\_2+\cdots+a\_v}\].$

By a greedy heuristic you should first divide by the *smallest* number in this list, remove that entry, and then apply the same algorithm to the remaining list and to $N/a\_1.$ Then repeat. Some powers won't divide evenly, ignore them, they've been represented as parts of lower powers.

Example Code from Online Magma Calculator at here:

Output:

---
Tags: dynamic-programming, numerical-algorithms
---


# Question
Title: Assembly language addressing mode instructions
I am studying assembly language. I feel very difficult in understanding few instruction.

ADD R1,R2,\[R3\]

ADD R1, R2, R3

What is the difference between these two instructions. I think second instruction takes the value in R3 register and add it to the value in R2 register and store it in R1 register. Then what does it mean by the first instruction. How does encoding works ? How does CPU knows the difference between two instruction?

# Answer
The assembly instructions you learn are used by the assembler to generate machine code. Every operation has a unique machine code. The 2 add operations are different in this case as their addressing modes are different, but their opcode would be the same as the operation to be done remains same in both cases, just the way the operand is fetched differs. In the first one R3 contains a memory address which in turn contains some data that will be added to content of R2 and in the second one the content of R3 is directly added to the content of R2. In both the cases their result will be stored in R1.
> 1 votes

# Answer
`R3` denotes the content of the register R3. `[R3]` denotes the content of the memory at the address contained in R3. (This implies that the registers are able to store addresses.) This mechanism is call *indirect addressing*. Without it no serious program could be written and computers would be of little use.

---

As regards the encoding, I don't think that the details of a particular implementation are instructive. But of course, the information contained in the assembly text (the desired addressing mode) is converted to some bit(s) in the instruction opcode.
> 1 votes

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


# Question
Title: Algorithm to find number of occurrences in mutually exclusive sets
Given multiple sets of three items, how can I find the most-commonly occurring item among the sets using only one item from each set. The sets don't have duplicates, but if I'm thinking about this properly, it shouldn't matter.

Example: (1,2,3), (5,3,6), (4,3,7), (8,7,9), (5,1,8) I want to see which number is the most common if I can only pick one number from each set. So If I pick 3 from the first set, I can't use the 1 or the 2 in that set.

My guess is to make a ton of for loops and cycle through all the items in each set and generate an obscene number of tallies for the occurrences of each item and then compare them at the end, but this seems super inefficient, especially for larger sets and larger numbers of sets. So using this example, if I picked the first number of every set, the tally would look like this dictionary with item:#\_of\_occurrences, 1:1, 4:1, 5:2, 8:1 so since 5 occurred twice, it is the most common for this single tally. The problem is that I would need to do a ton more of them to actually compare all of the scenarios. The actual answer is that 3 is the most common number, and I'm looking for an efficient way to calculate something like that.

# Answer
Concatenate all lists, and count which element appears the most times. Using a hash table, this can be implemented in linear time, and otherwise, you can obtain an $O(n\log n)$ algorithm (where $n$ is the total size of the lists) which sorts the concatenated list.
> 8 votes

# Answer
You can also use a balanced BST to achieve $O(n \log n)$ running-time. Use as key of a node an element of a set. Along with the key is a counter that gets incremented when inserting an existing key. Once all elements are inserted, perform a traversal to find the node with the highest counter and return its key.

If the elements of your sets are guaranteedto be integers from $\\{0,1,..,m-1\\}$, such that $m =O(n) $. You can create an array of size $m$ such that each entry of the array is a counter. Iterate over the elements of each set and for element $e$, increment index $e$. Finally, find the index with the highest value to get the element with the most occurrence. This should give you an $O(n) $ running time.
> 2 votes

# Answer
> The sets don't have duplicates

That fact massively simplifies the problem down to a simple histogram of all the elements across all sets.

Nothing ever stops you from selecting all the `3`s for example, because each one must be in a different set.

As the other answers point out, a histogram needs some kind of dictionary data structure to map keys to counts, e.g. a hash table, or even a flat array if the key range is small/dense enough.

Both of those are O(n) for searches (with possible insertion), with the array not having any resizing to amortize, and a lower constant factor. A tree-based dictionary is O(n log n) for `n` searches and O(n) insertions. (Some will just be increments of an existing key, but that still costs log(n) time in a balanced tree, unless you have a lot of duplicates across sets so the tree depth grows very slowly).

---

You can keep track of the highest-seen-count on the fly, checking every increment to see if you should update the max\_count and max\_key. Otherwise you'd loop over the counts at the end, finding the key with the highest count. Your dictionary indexes on key, not count (otherwise would need costly re-sorting after every increment), so this is linear time O(n).

As far as complexity classes, another O(n) step at the end doesn't change anything, nor does an extra constant factor increase in work per increment in an abstract model of computation.

But on real CPUs, you might well come out ahead. A compare/2x cmov or compare/rarely-taken-branch might not cost any extra time inside the histogram loop, if it's mostly bottlenecked on cache misses in a large histogram, not instruction throughput. (Superscalar pipelined out-of-order exec.) But looping over a large data structure again would happen separately, not hidden by out-of-order exec.

In terms of total abstract work, it's O(keys) compares if you do it every increment, vs. O(unique\_keys) if you do another pass at the end. But traversing some dictionaries includes extra work, too; e.g. an array will have some unused entries where there weren't any counts, so O(key\_range).
> 0 votes

# Answer
You can create a dictionary by looping all items in the set. New Item will be key and you can increase its value once it is appeared. In the diction if a new item which is appeared first time, you will add it to dictionary and make its value as 1. Finally, you can find out max value in its dictionary.
> 0 votes

---
Tags: algorithms, sorting, counting
---


# Question
Title: I'm trying solve a problem using different versions of SAT, how exactly does mixing SAT affect the hardness of the problem?
I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But I don't see how those can be combined to give me an idea of comparative hardness of 3SAT vs 2,3,4 SAT. By how hard, I mean what's the scaling with increasing numbers of variables.

# Answer
I think Steven's comment answers this sufficiently: 2SAT is in P, anything above that is NP-hard. By mixing it I just have two different NP-hard problems. How exactly 3SAT and 2,3,4 SAT differ in scaling probably depends on my algorithm.
> 1 votes

---
Tags: complexity-theory, complexity-classes, 3-sat, 2-sat
---


# Question
Title: Is this a context free language? I need to make PDA but I don't think it is doable
I got a question: Design a pushdown automata that can recognize strings in L= {$ a^n b^{2n} c^{3n} | n ≥ 0 $} . I tried to think and design it, but I couldn't find it. The best that I can think of is L= {$ a^n b^{m} c^{m+n} | m,n ≥ 0 $} . I only can make sure that c appears as much as a+b appear. So, I'm wondering, is this language context free? Could we make a PDA for it? Thank you.

# Answer
> 0 votes
For $L= \\{a^n b^{2n} c^{3n} | n ≥ 0 \\}$ you will be failed to make PDA with one-stack. Because here is two comparisons, one $a$ should be checked against with $2b$ and $3c,$ but when you complete one $a$ checked against with $2b$ then stack will be empty, and there will be pending of $c$'s computation. This two comparison intuitively proved that your language is CSL accepted by LBA.

# Answer
> 0 votes
Consider this homomorphism: $ f(a)=a\ ,f(b)=bb,\ f(c)=ccc $

Context free languages are close to revered homomorphism

What is $ f^{-1}(L)? $

I hope that gives you a hint

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


# Question
Title: How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?
I'm trying to use the Pumping Lemma to prove that $L = \\{ wsw \mid w \in \\{0,1\\}^\*,\ s \in \\{2\\}^\*\text{ and } |w| = 2\cdot|s| \\}$ is not a CFL.

# Answer
lets choose $ z = (01)^n2^n(01)^n$ when $n$ is the constant of the lemma

$ z = uvwxy,\ |vx|\geq1,\ |vwx|\leq n,\ uv^iwx^iy\in L$

The core concept is to prove that all possible disassemling is not pumpable for this $z$

case 1: $u=(01)^s, vwx = (01)^t,\ s,t\leq n,\ y=(01)^{n-t}2^n(01)^n \rightarrow uv^iw^ixy \notin L$ because letters added with $i$ are not added to the second $w$.

case 2: $vwx = (01)^t2^s,\ s+t\leq n,\ y=2^{n-s-t}(01)^n $

sub case 2.1: if both $v,x$ are $\in 2^\*,\ uv^iw^ixy \notin L$ because $|w|\not=2⋅|s|$

sub case 2.2: $x$ or $v$ contain $\\{0,1\\}^\*$ so the first $w$ will be different after pumping

from case 3 it kinda goes pretty much the same
> 0 votes

---
Tags: turing-machines, regular-languages, context-free, proof-techniques, pumping-lemma
---


# Question
Title: Why are restricted Boltzman machines not considered useful?
I've been under the impression that RBM can be used for a variety of applications and a cursory search on google seems to confirm this. But I've heard from multiple people (including a peer reviewer) that they're not considered to be "good," whatever that means. Is there a limitation of RBMs that I'm not aware of? Is it just that less shallow neural nets can learn better or is there a deeper reason why RBMs might be limited?

# Answer
Empirically, the performance of RBMs on many important tasks is (so far) not as good as other competing approaches.

Answering "why" questions about why one model does better than other is very hard. We don't really understand why neural networks work as well as they do; but empirically we can measure their performance and we can use them, even if we don't have a convincing explanation for "why" questions.
> 2 votes

---
Tags: machine-learning, artificial-intelligence, boltzmann-machine
---


# Question
Title: How can we prove QuickShuffle uniformly permutes it input array?
I'm studying *Algorithms* by Jeff Erickson. Consider this exercise from that textbook:

> Prove that the following algorithm, modeled after quicksort, uniformly permutes its input array, meaning each of the $n!$ possible output permutations is equally likely. \[Hint: $ \binom{n}{k} =\frac{n!}{k!(n-k)!} $\]
>
> $\quad\text{QuickShuffle}(A\[1\cdot\cdot n\])$:
> $\quad\quad$if $n ≤ 1$
> $\quad\quad\quad$return
> $\quad\quad j \leftarrow 1; k \leftarrow n$
> $\quad\quad$while $j \le k$
> $\quad\quad\quad$with probability $1/2$
> $\quad\quad\quad\quad$swap $A\[j\] \leftrightarrow A\[k\]$
> $\quad\quad\quad\quad k \leftarrow k − 1$
> $\quad\quad\quad$else
> $\quad\quad\quad\quad j \leftarrow j + 1$
> $\quad\quad\text{QuickShuffle}(A\[1..k\])$
> $\quad\quad\text{QuickShuffle}(A\[j..n\])$

My attempt: To solving above problem, I think we should achieve below
$$\frac{1}{\binom{n}{k}}\frac{1}{k!}\frac{1}{(n-k)!}=\frac{1}{n!}$$ but how we can achieve above to solve the problem?

# Answer
This exercise is interesting. One key idea is to understand the effect of the while loop. It may help if you try exercise 2 below first, since exercise 2 is a generalization.

---

Let us fix the input $A$. WLOG, assume all $n$ elements in $A$ are distinct.

Since the only kind of change made to $A$ is a swap, $A\[j\]\leftrightarrow A\[k\]$, $A$ at the end of the algorithm is a permutation of the original $A$ given as the input.

### Characterization of $A\[1..k\]$ right after the while loop

Consider a subset $B\subseteq A$.

**Claim**. There is a unique series of choices made by the while loop such that right after the while loop, $k=|B|$ and $\text{set}(A\[1..k\])=B$.

**Proof**. The while loop rearranges input $A$ into two parts, the front part $A\[1..k\]$ and the back part $A\[k+1..n\]$. Note that $k$, which is $n$ initially, can be decreased only and $j$, which is $1$ initially, can be increased only. Right after the while loop, $j=k+1$.

How can we let the while loop can end up with $k=|B|$ and $\text{set}(A\[1..k\])=B$?

Viewing $A$ as a double-ended queue, each iteration of the while loop polls one number from either end of the queue and then puts it into one of the two parts.

For each iteration of the while loop, if $A\[j\]\not\in B$, do the swap and decrease $k$, which includes $A\[j\]$ in the back part. Otherwise, increase $j$, which includes $A\[j\]$ in the front part.

It is easy to check this series of choices will ensure $k=|B|$ and $\text{set}(A\[1..k\])=B$ right after the while loop and it is the only possible series of choices to achieve that effect. $\quad\checkmark$

Since that series of choices is unique, right after the while loop, $A$ is completely determined by $\text{set}(A\[1..k\])$.

### The algorithm uniformly permutes the input

**Proof**. Do induction on $n$.

For the base case, $n=1$, it is true trivially.

Let $n\ge2$. Suppose it is true for smaller $n$. Suppose $P=(P\[1\], P\[2\], \cdots, P\[n\])$ is a permutation of $A$.

How can we compute the probability of the algorithm to produce $P$?

For the algorithm to produce $P$, it is necessary and sufficient that at the end of the while loop,

1. $\text{set}(A\[1..k\])=\text{set}(P\[1..k\])$, and
2. after $\text{QuickShuffle}(A\[1..k\])$, $A\[1..k\]=P\[1..k\]$ and
3. after $\text{QuickShuffle}(A\[k+1..n\])$, $A\[k+1..n\]=P\[k+1..n\]$

All possible values of $k$ right after the while loop are $0, 1, 2, \cdots, n$. Thanks to the claim above, for each possible value, there is a unique series of $n$ choices made in the while loop such that right after the while loop $k$ is that number and $\text{set}(A\[1..k\])=\text{set}(P\[1..k\])$, i.e., condition 1 happens on $n$ disjoint situations, each with probability $2^{-n}$.

Once condition 1 is satisfied for a particular $k$, $A\[1..k\]$ and $A\[k+1..n\]$ are determined. Thanks to the induction hypothesis, if $k\neq0$,

* condition 2 is satisfied with probability $1/k!$ and
* condition 3 is satisfied with probability $1/(n-k)!$ independently.

If condition 1 is satisfied with $k=0$, which happens with probability $2^{-n}$, condition 2 will always be satisfied and the algorithm will be calling itself exactly the same in its last step, "$\text{QuickShuffle}(A\[1..n\])$".

If condition 1 is satisfied with $k=n$, which happens with probability $2^{-n}$, condition 3 will always be satisfied and the algorithm will be calling itself exactly the same in its second to last step, "$\text{QuickShuffle}(A\[1..n\])$".

We see that the computation above of the probability of the algorithm producing $P$ does not dependent on the particular choice of $P$. The induction step is complete. $\quad\checkmark$

### Two exercises

**Exercise 1**. Although complete, the proof above does not compute the probability of the algorithm producing $P$. Compute it explicitly. You should obtain $\displaystyle\frac1{n!}$.

**Exercise 2**. Prove the following algorithm permutes its input array uniformly.

$\quad\text{QuickShuffleGeneral}(A\[1\cdot\cdot n\])$:
$\quad\quad$if $n ≤ 1$
$\quad\quad\quad$return
$\quad\quad$Let $B$ be chosen from all subsets of $\text{set}(A)$ uniformly. Let $C=\text{set}(A)\setminus B$.
$\quad\quad$Put $B$ in $A\[1..|B|\]$. Call $\text{QuickShuffleGeneral}(A\[1..|B|\])$
$\quad\quad$Put $C$ in $A\[|B|+1..n\]$. Call $\text{QuickShuffleGeneral}(A\[|B|+1..n\])$
> 1 votes

# Answer
Here is a (in my opinion) simpler argument than John L.'s and the one the book suggests with its hint.

Note that (if the array has more than 1 element) the main loop of QuickShuffle partitions the array in two, $A\[1..k\]$ and $A\[k+1..n\]$, and each element in $A$ has a 50% chance of ending up in either partition. Then we recurse on both partitions. We can phrase the algorithm thusly:

1. Flip a coin for each element of $A$, and assign `0` for tails and `1` for heads.
2. Partition the array so that all elements with a `0` come first, and `1` come after.
3. Recurse on each partition.

Now for each element we can look at the series of coinflips that determined its final location in the array. But before doing so we add a `0.` in front of the sequence, and `...` after. For example for shuffling `[a, b, c, d, e, f]`:

```
a 0.000...
c 0.001...
f 0.10...
d 0.1100...
b 0.1101...
e 0.111...

```

What we have implicitly done is associated a uniformly random real number in $\[0, 1)$ (with an infinite amount of digits!) with each element, written fractional binary, only expanding out those digits necessary to distinguish the order between the real numbers. Note that ties are impossible, the algorithm would keep recursing until the prefix of the infinite stream of digits is distinct from all others as a tie would imply both numbers ended up in the same partition.

In other words, our algorithm is equivalent to associating a distinct random real number to each element and sorting based on that number, which is a classic algorithm for getting a uniformly random permutation.
> 0 votes

---
Tags: algorithms, randomized-algorithms, permutations
---


title: Confusion with Hard Disk structure

text:
# Question
Title: Confusion with Hard Disk structure
Studying Os development I encountered the need to interface with the Hard Disk Drive and thus i started learning how it actually works. One of the problems that i found studying was that different sources said and claimed different things about the Hard Drive's structure. So, i have some questions:

1. Is a Sector a Geometrical Sector of the Platter or an area inside a Cylinder/Track? (i naturally opt for the second)
2. Is there a difference between Cylinders and Tracks? (some claims it)
3. In CHS (Cylinder, Head, Sector) addressing mode when incrementing the value of Head do you actually change the Platter?

Thanks in advance.

# Answer
I'm not an expert but here is how I understand it.

1. A sector describes a radial slice of each platter, i.e., it contains a portion of each track. The term is somewhat ambiguous as it is often used to refer to a particular portion of a given track. Wikipedia calls the former a "geometrical sector" and the latter a "disk sector". See B and C in the following figure from Wikipedia:

2. A cylinder is the collection of all tracks on all platters at the same distance from the spindle.
3. You either go to another platter or to the other side of the same platter (if the disk has heads on both sides).
> 2 votes

---
Tags: storage
---