# Question
Title: Why computer take long time to open huge text files?
Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be opened very fast.

Why the computer doing this ? What is the difference between the two operations?

# Answer
> 8 votes
The difference would be between loading the complete file into memory and reading the file part-by-part as you need each part.

If I open a file in some applications I am asking for it to be fully loaded into memory all in one go.

If I play a movie file or DVD in most player applications the applications will be structured to just fetch data as it needs it, not all at once.

There are different ways to open files and devices in operating systems and they are not all the same.

# Answer
> 0 votes
You must have noticed while performing the seek operation on the movie player it takes a moment (the slightest of it though) to resume the playback. This time is used to bring the desired part of the movie from the disk to the main memory if it is already not present in the cache or the memory. In case of text editors the whole file is loaded at once which takes considerable amount of time and also affects other programs. Moreover the amount of memory allocated to a process by the OS also varies depending on the type of program.

# Answer
> 0 votes
Text editors often need to read the whole file to index and count lines before displaying it. There is also character code conversions (which means that the CPU must parse each byte one by one).

From my experience, non-unicode editors as *nedit* are faster than modern ones, with its regexp parser, it is useful for analyzing crazy large log files.

---
Tags: optimization, performance
---


# Question
Title: What do you call a DAG with a single root/source?
What's the name for a DAG (directed acyclic graph) that has a unique *root* or *source* node from which every other node can be reached?

Alternatively, if you change the direction of the arrows, what's the name for a DAG that has some unique *sink* node that is reachable from every other node?

Here's an example graph:

# Answer
> 9 votes
There isn't a standard name for that, at least none I'm aware of. I've seen that structure being called "rooted DAG", by analogy with "rooted tree".

# Answer
> 9 votes
In a directed graph we do not speak of roots and leaves, but of sources and sinks.

I'm not aware of any term that designates a DAG with only a single source, but you could just call it that: "a DAG with a single source".

# Answer
> 4 votes
If you think of the DAG as a graph whose reachability relation is a partial order relation, then an element with that property would be a minimum element in that relation.

I haven't seen the term "minimum element" used this way before, but I suspect that someone seeing that notation would likely be able to understand it if you included a quick explanatory sentence.

---
Tags: graphs
---


# Question
Title: Runtime of good suffix table creation in Boyer-Moore algorithm
According to Wikipedia, both bad character table and good suffix table can be created in $O(n)$ time, where $n$ is the length of the pattern. It is pretty obvious how bad character table can be computed in linear time, but I don't understand how good suffix table can be computed in linear time. I thought about it a lot, and could not come up with an $O(n)$ algorithm to generate that table. I also looked at the Java implementation provided in Wikipedia, but I think it runs in $O(n^2)$ time. For example, look at the following two lines taken from `makeOffsetTable` method.

```
for (int i = needle.length - 1; i >= 0; --i) {
    if (isPrefix(needle, i + 1)) {

```

Outer for loop iterates `needle.length` (i.e. $n$) times, and within the loop body `isPrefix` is called, which contains a loop that starts with the following header.

```
for (int i = p, j = 0; i < needle.length; ++i, ++j) {

```

Just to make it easier on the eyes, here is the two loops shown together.

```
for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1, j = 0; i2 < needle.length; ++i2, ++j) {

```

I can get rid of `j` of the inner loop to further simplify it.

```
for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1; i2 < needle.length; ++i2) {

```

What I see here is that with each successive iteration of the outer loop, inner loop will have one additional iteration. So, the number of iterations for the inner loop will be $0, 1, 2, 3, 4, ..., (n-1)$ which adds up to $(n-1)n/2$, which is $O(n^2)$, which is not linear.

So, the question is, does it really take more than linear time to compute the good suffix table, or am I making a mistake with runtime calculation?

# Answer
> 2 votes
The implementation provided in Wikipedia is $O(n^2)$. But these tables can actually be built in $O(n)$ time via Z-algorithm. Since you can find Z-algorithm on internet easily, I just provide a sketch here.

Let $s\[i,j\]$ denote the substring of $s$ from $i$-th position to $j$-th position. Like what we see in the $O(n^2)$ code, we want to find the largest value $z\_i$ satisfying $s\[i-z\_i+1,i\]=s\[n-z\_i+1,n\]$ for each $i$ (the longest matching suffix).

Now compute $z\_i$ from back to front. Let $l$ be the smallest number s.t. $s\[l,r\]=s\[n-r+l,n\]$ for some $r\>i$. If $l\le i$, we have $s\[l,i\]=s\[n-r+l,n-r+i\]$, which means we can get some information from $z\_{n-r+i}$. If $z\_{n-r+i}\le i-l$, $z\_i=z\_{n-r+i}$. Otherwise $s\[l,i\]=s\[n-i+l,n\]$ and $z\_i\>i-l$. In this case, we should find the real $z\_i$ by brute force, but at the same time we get a smaller $l$, which provide more information for future computation. Since $l$ is non-increasing, the algorithm works in $O(n)$.

---
Tags: strings, exact-string-matching
---


# Question
Title: Comparing dual of a canonical primal program - Directly and by dual of the standard program
I have it as a homework question to compare dual programs in the following way:

1. Take a canonical program and write its dual
2. Take the same canonical program, write it as a standard program, take the dual of the latter, then write it as a canonical program.

In the following image, option 1 is starting with the upper left square and going right, and option two is (starting with the same place and) going down and then right and then up.

I have tried to do this, both in general and both by example, but I'm getting something strange: First I add slack variables to move from inequalities to equality, and I add the constraint that all slack variables are positive.

Then I write the dual of that program, the inequality look like $\[A|I\]^Ty\leq \[c|0\]$

(here $\[A|I\]$ denotes a block matrix) which gives two sets of inequalities: one is $A^Ty\leq c$ and the other is $Iy\leq 0$. Which is almost like the CD form in the picture - but I got $y\leq 0$ instead of $y\geq 0$.

Why do I get a different result ? I guess I have some error and that I should actually get $y\geq 0$, but I checked multiple times and I don't see any errors.

# Answer
Since $Ax\ge b$, you should make $Ax$ smaller to get equality. Slack variables are also non-negative, so the coefficients should be $-1$. It's $\[A|-I\]$ instead of $\[A|I\]$.
> 2 votes

---
Tags: linear-programming, duality
---


# Question
Title: Understanding x64 and x86 OS with 64bit cpu
Kinda stupid question, but makes me a bit confused. If my OS (Win 7) is 64-bit type system and my CPU is 64-bit, why Program Files directory is marked (x86), x86 stands for 32-bit OS?

# Answer
You should notice there are two directories for your program files. For the directory with the suffix x86 it contains the programs which are based on 32-bit addresses. Any program which is made to produce 32-bit addresses is compatible with 64-bit architecture but not vice-versa. The OS installs the programs based on 32-bit addresses in the x86 directory.
> 0 votes

---
Tags: operating-systems, cpu
---


# Question
Title: What's the point of Indirect Addressing?
Indirect addressing allows you to reference memory locations, larger than the operand limit of a CPU.

i.e

```
1 | ADD 2 3
2 | #2
3 | *32000
...
32000 | #5

```

This will add memory location 2 and 3, 3 points to location 32000, so when it's evaluated, the effect is:

```
1 | ADD 2 32000

```

Even though 32000 may exceed the operand size limit.

My question is, why do this?

Why not simple have this:

```
1 | ADD 2 3
2 | #2
3 | #5

```

It saves time wasted on extra references to memory *and* space in memory.

# Answer
Indirect addressing is possible without instructions that implement it explicitly. These instructions exist for our convenience, and not just for reaching a position that doesn't fit the address space of a direct addressing instruction (although this will become quite natural if your program is big enough): that's how we implement subprograms and arrays, for instance.
> 3 votes

---
Tags: computer-architecture, memory-management
---


# Question
Title: What can be said about the given language?
$L = \left \\{ ab^{n}a^{n}|n\>0 \right \\} \bigcup \left \\{ aab^ka^{2k} | k\>0 \right \\}$

---

What can be said about the given language L ?

---

According to me, I think it is CFL and not DCFL as I tried to somehow parse it through a NPDA but not sure though.

# Answer
The words in the first part start with $ab$, those in the second part start with $aa$.

That should help.
> 1 votes

---
Tags: pushdown-automata, nondeterminism
---


# Question
Title: Are the Confabulation Theories of Thaler and Hecht-Nielsen Isomorphic?
Both S. L. Thaler and R. Hecht-Nielsen have set forth neural-based theories of "confabulation" applicable to machine learning.

The essential mathematics of Hecht-Nielsen is set forth in his paper "Cogent Confabulation". Briefly it is an inversion of Bayesian inference. Bayesian inference is P(x|a&b&c&d...) where one is estimating the probability of x assuming a, b, c, d, etc. Its inversion is P(a&b&c&d...|x), which RHN calls the "cogency" of x given the assumptions.

I haven't seen a similarly succinct description of Thaler's mathematics that would permit comparison to see if the theories are isomorphic. Are they?

# Answer
I don't think they map onto each other, aside from RHN's brief discussion of thalamo-cortical loops, the inspiration for SLT's so-called "Creativity Machines." In SLT's architectures, compelling/cogent solution patterns are sought within a stream of novel activation patterns (i.e., confabulations) driven by various forms of internal disturbances to biological neural nets. RHN's definition of cogency is obviously not the same. The mathematics of SLT's model are scattered over several patents and papers, but the following might provide an overview: Predicting ultra-hard binary compounds via cascaded auto- and hetero-associative neural networks, Journal of Alloys and Compounds, 279(1998), 47-59, Synaptic Perturbation and Consciousness, International Journal of Machine Consciousness, 6(2):75-107, 2014, Cycles of Insanity and Creativity within Contemplative Neural Systems, Medical Hypotheses, 94:138-147, Elsevier, 2016, and Pattern Turnover within Synaptically Perturbed Neural Systems, Procedia Computer Science, 88, Elsevier, 2016.
> 1 votes

# Answer
To further elaborate using Bowery’s explanation, Thaler developed the chaotic neural network methodologies to predict the pattern $(a, b, c, d)$ that could result in $x$, without concern for probabilities. While doing so, he proposed that ideas were false memories or confabulations nucleating from noise, subsequently recognized for their novelty, utility, or value by monitoring neural nets that could then elect to reinforce them as memories. Bayesian probabilities would likely not apply in a system so awash in chaos.

For more math, see *Pattern Turnover within Synaptically Perturbed Neural Systems*, *Procedia Computer Science*, 88, Elsevier, 2016 and *Cycles of Insanity and Creativity within Contemplative Neural Systems*, *Medical Hypotheses*, 94:138-147, Elsevier, 2016.
> 0 votes

# Answer
Actually, there is overlap between the two theories, but Thaler’s model is much more general.

RHN’s 2005 theory pertains only to the co-activation of intact memories, but SLT’s model allows for the inclusion of false or degraded memories (i.e., confabulations). So in terms of the prior comments, not only can **a**, **b**, **c**, and **d** activate in the context of **x**, but also **a’**, **b’**, **c’**, **d’**, and **d’’**, for example, making the probability calculation all the more daunting. That’s why SLT discussed the formation of ideational chains that are a mixture of memories and confabulations in his 1996 paper, A Proposed Symbolism for Network-Implemented Discovery Processes, In Proceedings of the World Congress on Neural Networks, (WCNN'96), Lawrence Erlbaum, Mawah, NJ. So, in what RHN describes as a winner-take-all horse race, the thoroughbreds are not only mutating at the starting gate, but also during the race itself. SLT attributes such ongoing mutations and hybridizations of memories to the injection/withdrawal of synaptic perturbations (e.g., 1998, J. Alloys and Compounds, above) by the limbic system in the form of volume neurotransmitter release (e.g., 2014, IJMC above).
> 0 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, bayesian-statistics
---


title: Improve Java Experience

text:
# Question
Title: Improve Java Experience
In exactly a month I will face a Java exam. My problem is that even if I know all Java theory (the exam won't face GUI), I have problems creating programs: sometimes I can't understand how to make a fast program or how to implement what I want my program to do. So how can I improve my Java habilities? What kind of exercises should I work on? Should I follow some guides or tutorials? Should I re-study all the theory till I understand better?

P.S. If this isn't the right Stack to post this on I will just close the question and look better for the right one

# Answer
> 2 votes
I'm going to go ahead an assume that it's a Java 101 type of exam.

The best way to go about studying for it, in my opinion, is to practice applying the basics. Things such as Data Types, Conditional Statements, using Arrays, etc. A good place that has stuff like this is CodingBat as it gives you answers too. You could even just have a read through a beginner's Java book (a quick google search will bring up loads which you can find a PDF easily).

Then if you want to work on general problems that encompass everything you could do the problems at places like HackerRank (Which is also good practice for coding interviews as many companies use this) or the easy problems at reddit.com/r/dailyprogrammer. There are tonnes of other resources out there but if you would like some more just comment on this.

Good luck in your exam and I hope this helps you a little bit.

# Answer
> 1 votes
After a certain point, I found that reading books and doing tutorials didn't do much for me. Instead, what helped was doing projects. I've been doing code golf over on code golf and programming puzzles, the Euler problems, and just my own projects I want to work on. If you think something's cool, go for it. This sort of unstructured, try to solve problems with code work can be very helpful, and I know that it has taught me personally a whole lot.

Of course, this may not give you enough experience in using specific methods, which is why you should study in other ways as well. However, this will get you more familiar with your language and give you more problem solving skills. Good luck on your exam!

---
Tags: education
---


# Question
Title: How do i get the inputted number,but repeat the same integers twice?
Imagine i get an input `123` my goal is to return `112233`.How can i get that?I can't use strings because i have to multiply that same later

# Answer
> 1 votes
Convert to string, double characters, convert back to number.

---
Tags: mathematical-programming
---


title: Finding proper subsequence

text:
# Question
Title: Finding proper subsequence
I'm preparing for CS201 exam and I stumbled upon an interesting problem.

Input: A sequence of random positive and negative integers (up to 1.0000).

Output: A **contiguous (to be clear: subsequence of consecutive elements)** subsequence of the original sequence, such that after its reversal in the original sequence the balance will remain nonnegative. The contiguous subsequence must be as small as possible.

A few examples:

Example 1.

> Input:
>
> > 3 -4 -2 3 (-4 is the point, where the balance is negative, because 3 + (-4) = -1)
>
> Output:
>
> > -4 -2 3 (the contiguous subsequence to be rotated)
>
> because:
>
> > 3 3 -2 -4 (now: 3 + 3 = 6; 6-2 = 4; 4-4 = 0. The balance is always positive.)

Now there is no point, where balance is negative.

Example 2.

> Input:
>
> > 3 -5 2 -1 (3+(-5)=-2, so the balance is negative at -5)
>
> Output:
>
> > Impossible to find a subsequence to rotate.

Example 3.

> Input:
>
> > 4 -4 -3 5 2 -4 5 -2 (4 + (-4) = 0; 0 + (-3) = -3. The balance is negative at -3.)
>
> Output:
>
> > 4 -4 -3 5 2
>
> Because:
>
> > 2 5 -3 -4 4 -4 5 -2 (2+5=7;7+(-3)=4;4+(-4)=0;0+4=4;4+(-4)=0;0+5=5;5+(-2)=3. The balance is always positive.)

I had multiple approaches to this problem, but none of them cover all possible cases.

# Answer
> 2 votes
I think my answer is exactly the same as Lurr's, but I'm not sure if I should edit it.

Suppose the subsequence is $(l,r\]$ and $b\[i\]$ is the balance at $i$-th position. If $i\notin (l,r\]$, $b\[i\]$ won't change. Otherwise $(l,i\]$, i.e. the first $i-l$ elements of $(l,r\]$ is replaced by the last $i-l$ elements of $(l,r\]$, which is $(r-i+l,r\]$. Therefore, $b'\[i\]=b\[l\]+b\[r\]-b\[r-i+l\]$, where $b'$ is the balance of new sequence. Note that there's a bijection between $b'\[i\]$ and $b\[r-i+l\]$. It means $b'$ is non-negative iff:

1. $\forall i \notin (l,r\], b\[i\]\ge 0$
2. $\forall i \in (l,r\], b\[l\]+b\[r\]\ge b\[i\]$

Note that we can rewrite the second property as $b\[l\]+b\[r\]\ge max\_{i\in(l,r\]} b\[i\]$.

Let $L$ denote the rightmost position s.t. $b\[i\]\ge 0$ for all $i\le L$ and $R$ denote the leftmost position s.t. $b\[i\]\ge 0$ for all $i\>R$. We need $l\le L$ and $r\ge R$ to satisfy the first constraint. We implicitly assume these constraints in all the following statements so we only need to care about the second constraint. We need three more observations:

* If $(l,r\]$ is valid, for all $l'\le l$ we don't need to care about $(l',r'\]$ where $r'\>r$.
* For all $r\<r'$, if $b\[r\]\ge b\[r'\]$, $(l,r\]$ is better than $(l,r'\]$.
* Fix $l$. If $b\[r'\]$ is the largest in $\[R,r'\]$ and $(l,r'\]$ is invalid, $\forall r\<r'$ $(l,r\]$ is also invalid.

The first observation is trivial since we need the shortest subsequence. The second observation is obvious since $b\[l\]+b\[r\]$ is larger, $(l,r\]$ is shorter and the constraint is looser. The condition of the third observation follows the second: if $b\[r'\]$ is not the largest, there exists a better $r$. Now let's see why $(l,r'\]$ is invalid: $b\[l\]+b\[r'\]\<max\_{i\in(l,r'\]} b\[i\]$. Since $b\[l\]$ is non-negative and $b\[r'\]$ is the largest, this can only happen if $b\[l\]+b\[r'\]\<max\_{i\in(l,R-1\]} b\[i\]$.So $\forall r\<r'$, $b\[l\]+b\[r\]\<max\_{i\in(l,R-1\]} b\[i\]$, which means $(l,r\]$ is invalid. Now the flow is clear:

1. Maintain a monotone candidate list of $r$ based on the second observation. Also, maintain $max\_{i\in(l,r\]} b\[i\]$ for all $r$ in order to check the second constraint. Preprocessing takes $O(n)$.
2. Iterate $l$ from $L$ to $1$:
3. If the largest $r$ is invalid, the smaller candidates are also invalid according to the third observation. Skip this $l$.
4. If the largest $r$ is valid, check if the second largest candidate $r'$ is also valid. If so, discard $r$ according to observation one and check again\*. Otherwise, smaller candidates are also invalid so $r$ is optimal for $l$. Update the answer if $(l,r\]$ is better. \*Although this step is a loop, it discards an element of $r$ when it repeats, so the total complexity is still $O(n)$.

Finally we solve the problem in $O(n)$.

# Answer
> 1 votes
First I suggest “integrating” sequence. i.e. building balance sequence. It's funny, but when contiguous subsequence of original sequence gets reversed, corresponding segment of balance sequence plot gets literally rotated for 180 degrees. It means subsequence reversion will remove all negative balance points iff:

1. Subsequence contains all negative balance points inside;
2. Balance inside subsequence is never greater then sum of balances at the beginning (before first element) and the end (after last element) of subsequence. (All points where it’s greater will become negative after rotation.)

It's possible to find shortest subsequence which follows this requirements in $O(n)$.

Keep in mind that any element can be first in the sequence only if balance right before it, is greater than at any point between chosen element and first point where balance goes negative. (Or we can make shorter subsequence starting from this point with bigger sum of balance at the beginning and end.) All such elements form a monotonically decreasing subsequence. And there is corresponding monotonically increasing subsequence of possible last elements. And for each possible first element we need to find only first corresponding possible last element and it is never smaller then possible last element corresponding to the previous first element.

---
Tags: algorithms
---


title: stages of compilation

text:
# Question
Title: stages of compilation
gcc is a collection of compilers, based on the file extension it compiles a source file. But compilers are only supposed to convert a preprocessed code into assembly code. And after that assembling and linking is done and an executable is generated. But several definitions says that compilers are the ones who convert source code into executable code.. i am confused. what actually a compiler is? what is gcc? Can anyone please give me a clear definition? And i have seen in man pages of gcc mentioning the term "compiler proper" what exactly is this?

# Answer
I'm not sure there is a well accepted definition of *compiler*. To some extent this is an informal concept, so you can't expect a mathematical definition like that of a derivative.

Judging from GCC documentation, the compiler proper converts (preprocessed) source code into object code. Several object codes are then linked together to an executable by the linker, but that doesn't form part of the compiler proper. The C/C++ preprocessor also doesn't form part of the compiler proper.

The compiler proper is further composed of two parts: a *front end* and a *back end*. The front end converts source code into intermediate code, and is language specific. The back end converts intermediate code into machine code, and is machine specific. GCC comes with several front ends and back ends, and this is why it is called a compiler *collection*.
> 2 votes

---
Tags: compilers
---


title: What does it mean to "construct a PCP"?

text:
# Question
Title: What does it mean to "construct a PCP"?
I am referring to section 8.1 of this paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf. Can someone kindly give me a concrete definition of what it means to "construct a PCP" and if that is the same as a "PCP verifier". Are they the same things?

Its not clear to me as to what it means to say that "Let the bits in the proof be vertices of a graph and the tests of the verifier be the edges of the graph." How can one encode vertices of a graph as single bits?

---

I am trying to match this to the concepts in the lecture notes by one of the authors, https://courses.cs.washington.edu/courses/cse533/05au/ but its not clear as to how to go about doing it. If someone can help identify the correspondence that would also be a great help!

# Answer
> 4 votes
A PCP is a *probabilistically checkable proof*, and the PCP verifier is the algorithm that checks it. In our case, we are given an instance of Unique Label Cover which is promised to be either at least $(1-\eta)$-satisfiable (Yes instance) or at most $\gamma$-satisfiable (No instance). The (polynomial size) proof, which is similar to a witness in an NP verifier, purports to show that the instance is a Yes instance. It is given by a sequence of bits. The verifier is a probabilistic algorithm which checks the proof. If the instance is a Yes instance then there is a proof which convinces the verifier with probability at least $c$ (the completeness), and if the instance is a No instance then every proof convinces the verifier with probability at most $s$ (the soundness).

This particular verifier chooses two bits $\pi\_i, \pi\_j$ of the proof $\pi$ according to some complicated distribution, and checks that $\pi\_i \neq \pi\_j$. Every Yes instance has a proof such that $\Pi\[\pi\_i \neq \pi\_j\] \geq c$, and for No instances, all proofs satisfy $\Pr\[\pi\_i \neq \pi\_j\] \leq s$.

You can encode this verifier as an instance of Max Cut. The vertices $v\_1,\ldots,v\_N$ correspond to the bits of the proof $\pi\_1,\ldots,\pi\_N$, and two vertices $v\_i,v\_j$ are connected with an edge whose weight is the probability that the verifier chooses to check the two bits $\pi\_i,\pi\_j$. A *cut* in the graph can be though of encoding a proof: vertices on one side of the cut are 0 bits, and vertices on the other size are 1 bits. Under this encoding, an edge $(v\_i,v\_j)$ is cut iff in the corresponding proof, $\pi\_i \neq \pi\_j$.

The upshot is that if the Unique Label Cover instance is a Yes instance, then the Max Cut instance has a cut whose value is at least $c$, whereas if the Unique Label Cover instance is a No instance, all cuts of the Max Cut instance have value at most $s$. Therefore any approximation algorithm for Max Cut whose approximation ratio is better than $c/s$ would be able to solve Unique Label Cover, which is UGC-hard.

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


# Question
Title: Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable
I want to prove that: $\\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^\*$ and $M ∈ B(n,w)$}\\}$ is undecidable.

Here $w$ is a string and $B(n,w)$ is the set of all $n$-state machines that halt on input $w$ after exactly the maximum number of steps. I don't know how to prove this. I tried finding another language to apply the reduction method but also to no avail. Can anybody help me with this?

# Answer
> 1 votes
Given a Turing machine $M$ of $n$ states and a word $w$, you could solve the halting problem for $(M,w)$ if you knew the maximal number of steps $f(n,w)$ that a Turing machine $M$ with $n$ states can spend on $w$. If your language were decidable then you could compute $f(n,w)$ by trying all Turing machines on $n$ states until you find one in $B(n,w)$.

I'll let you figure out the details on your own.

---
Tags: turing-machines, undecidability, computation-models
---


# Question
Title: I am a little bit confused about how to calculate the memory capacity
I am a little bit confused about how to calculate the memory capacity.

```
word=data lines size
byte=8 bit
n=adresse lines size

```

> Most of the people use this formula to calculate the capacity of the memory: C=(2^n\*word)/8 octet

Is this formula correct when speaking about byte-addressable? Because if we have byte-addressable memory, I think the capacity will be 2^n octet.

If this is correct why people use the formula in all cases? If not can you please explain why to me?

Thanks you.

# Answer
This formula assumes that memory is word-addressable rather than byte-addressable. The number of *words* that can be addressed is $2^n$. If you want to convert this from words to bytes, you can use the formula (in which `word` stands for the word size in bits). If you want to convert it to kilobytes, for example, you need to multiply by the word size in bits, and divide by $8192$. And so on. Come up with your own formulas!
> 0 votes

# Answer
You need to distinguish between how RAM is physically organised and how it is accessed, and how the instruction set of the computer allows accessing memory.

For example, on a modern Intel CPU, the instruction set allows reading and writing quantities of 1, 2, 4, 8, 16 or 32 bytes with byte addressing. For example, you could read 16 bytes starting at address 0x1005 according to the instruction set.

However, RAM is organised so that 32 bytes at a time will be transmitted between RAM and CPU, and those bytes must start at an address that is a multiple of 32 bytes. Therefore, the last five bits of the address are never used, and there are no address lines for those five bits.

In the example, the processor would read 32 bytes starting at address 0x1000 into a cache line and then provide the 16 bytes that the instruction wants from that cache line. If you tried to read 16 bytes starting at address 0x1015, then the first 11 bytes 0x1015 to 0x101f would be provided from that cache line, and then the next 32 bytes would be read starting at 0x1020 and 5 bytes provided from that cache line.

Different processors access different amounts of data at a time - a 1970's microprocessor one or two byte at a time, and things have increased since then. Different processors have different abilities to access larger items at unaligned addresses (at all, or at different speeds).
> 0 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: An O(n log sqrt(n)) sorting algorithm? Skiena TADM 2nd Question 4-28
Skiena writes:

> In one of my research papers \[Ski88\], I discovered a comparison-based sorting algorithm that runs in $O(n\log\sqrt{n})$. Given the existence of an $\Omega(n \log n)$ lower bound for sorting, how can this be possible?

I believe the research paper he is referring to is Encroaching lists as a measure of presortedness, and the $O(n\log\sqrt{n})$ algorithm is Melsort. I don't have the full text of the article, but the abstract states that melsort has \[time\] complexity $O(n\log m)$, where $m$ is the number of "encroaching lists" present in the input and $n$ is (presumably) the size of the input.

I suspect that the solution to Skiena's apparent paradox hinges on expected running time vs worst case running time. He notes in the abstract of the '88 paper that melsort is "linear for well ordered sets and reduces to mergesort and $O(n\log{n})$ in the worst case." If the expected number of encroaching lists, $m$, is $\sqrt{n}$ (as apparently conjectured by Skiena, according to wolfram's article on encroaching lists), it would follow that melsort's expected runtime is $O(n\log\sqrt{n})$.

But wikipedia states that "A comparison sort must have an average-case lower bound of $\Omega(n \log n)$ comparison operations," citing Cormen et al. Checking the referenced pages of Introduction to Algorithms, I see only a proof that the worst-case runtime has that bound. Is the Wikipedia article incorrect?

# Answer
> 7 votes
Azzo is correct. It's very simple:

$n\log \sqrt{n} = n\log n^{\frac{1}{2}} = \frac{1}{2}n\log n = \Omega (n\log n)$

Therefore Skiena's $O(n\log\sqrt{n})$ sorting algorithm does not violate the lower bound on comparison sorts.

---
Tags: sorting
---


# Question
Title: What features of a problem make it NP-complete/hard?
This isn't a question about what NP-completeness or hardness is, but about what, in general and informally, make a problem NP-complete? That is to say, what features of a problem might make me suspect a problem is NP-complete/hard?

To elaborate, for instance, lets say I’m seeing the graph coloring problem for the first time, or independent set, etc. Are there intrinsic features of these kinds of problems that might make me suspect they cannot be solved efficiently?

# Answer
> 7 votes
By definition, a problem is **NP**-complete if it's in **NP** and every other problem in **NP** can be reduced to it. The only literal answer to the question is that one: essentially, a problem is **NP**-complete only if it can be proven to be **NP**-complete. Since proof is a creative activity, it's not possible to give a series of rules, along the lines of "If a problem looks like X, Y or Z, then it's **NP**-complete."

However, there are some common features. First, the problem must be in **NP**, which means that we must be able to efficiently check a potential solution (e.g., check a proposed colouring for a colouring problem). Of course, designing efficient algorithms is also a creative act but, usually at least, proving that a new problem is in **NP** is fairly straightforward.

Once I've convinced myself that a problem is in **NP**, the thing that usually makes me feel that it might be **NP**-complete are non-locality and the presence of some kind of conflicting goals. Examples:

* Satisfiability problems are non-local in the sense that choices for the variables in one clause also affect many other clauses. There are competing goals in that clauses containing $X$ want us to make $X$ true, but clauses containing $\neg X$ want the opposite.
* In colouring problems, we wish to use as few colours as possible but features of the graph cause us to need many colours. Choices for colours in one part of the graph may have cause problems far away (see, e.g., Erdös's famous result that, for any $k$, there are graphs of arbitrarily large girth that are not $k$-colourable despite the fact that having large girth means they look locally like trees).
* In something like vertex cover, we're looking for a set that is, in a sense, "small but powerful". We can trivially find large vertex covers but the difficulty is in finding a small set that still does everything that we need.

Another feature can be that the "obvious" algorithm that you first think of seems to involve uncontrollable backtracking when you try to make it really work. For example, you might try to solve independent set greedily by starting with a single vertex and iteratively adding vertices that don't send any edges to the set you've built so far. But you soon realise that a bad choice early on can limit your options later and you start having to backtrack. Satisfiability problems tend to work like this, too.

However, be aware that adding even more restrictions to a problem can make it easier. For example, everything I've said above might make you suspect that 2-colourability and 2-SAT are **NP**-complete. But it turns out that 2-colourable graphs are so special that you can easily detect them and the back-tracking in 2-SAT can be kept under control.

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


title: how to create tokens from CFG

text:
# Question
Title: how to create tokens from CFG
i have a context free grammar

i want to create a tokens from the language

is there any techniques to do that ?

for example , this CFG from Prof.Alex Aiken notes :

```
 D -> D ; P | D

 D -> def id(ARGS) = E ;
 ARGS -> id, ARGS | id
 E -> int | id | if E1 = E2 then E3 else E4 | E1 + E2 | E1 - E2 | id(E1,...,En)

```

how can i crate the tokens ?

the professor explain how i do that in some inputs

for example , if i have the input :

```
x = 10

```

then i have

```
<id.,x> < opp., = > ......

```

but how i can do that from the CFG

thank you All

# Answer
The problem of creating a parse tree given a grammar and a word generated by it is known as *parsing*. The CYK algorithm parses all context-free grammars, but is slow. In practice, only restricted types of context-free grammars are used, and these can be parsed in linear time. The common example is LALR parsing. Perhaps you will learn more about this topic in due time.
> 1 votes

---
Tags: context-free, compilers
---


# Question
Title: Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$)
I seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is $O(\log n)$. Give an $O(n \log \log n)$ worst-case time algorithm to sort such sequences. I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a **deterministic algorithm** for the problem described.

It is from the book *Algorithm Design Manual* by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.

# Answer
> 6 votes
How much time does it take to make $\Theta(n)$ queries in a Red-Black Tree with size $O(\log n)$ ?

A detailed solution follows:

> Let $T$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $A\[i\]$ of the original array, query $T$ for a node which first element is $A\[i\]$. If there is no such node, insert a new node $(A\[i\], 1)$; otherwise, update the node $(A\[i\], m)$ with $(A\[i\], m+1)$.
>
> After you are done with all the elements in A, clear $A$ and visit $T$ in-order. For each node $(x, m)$ of $T$, append $m$ copies of $x$ to $A$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $T$ is $O(\log n)$.

# Answer
> 0 votes
You don't do any sorting at all. Instead, you make one pass through the array S, collecting all unique values into a sorted array U, and for each unique value create a linked list of the indices of all items with that value.

Since U has a size O (log n), you can lookup any value in time O (log log n) using binary search. You do that n times, so O (n log log n) operations. Modifying array U is O (log^2 n) at most. Then creating the sorted array is O (n). Total O (n log log n).

If the number of unique values f (n) is larger you'll need something more clever than a simple sorted array (f (n) ≥ $O ((n log n)^{1/2})$ to do the job in O (n log f (n)).

---
Tags: algorithms, sorting
---


# Question
Title: Word- or byte-addressable? Correct terminology
Seemingly, a byte has established itself to be 8bit (is that correct?). RAM and NOR-flash can be normally accessed on a quite granular level, but it is up to the system architecture to determine if the smallest addressable unit is 8bit, 16bit or any other power of two bit number. Would the correct terminology be to call this word-addressable? Or asked differently, is a word the size of smallest addressable unit? Or is there some other term to describe this?

Are mabye nibble, byte, word, double word all variable in bit-length and only defined by the architecture? And it is therefore only coincidence that a byte is always 8 bit? E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

**Main question:** What is the precise term for the smallest addressable memory block?

**Side question:** What is the antonym to this word I'm looking for (e.g. used in NAND-flash)? Page-addressable, block-addressable? Are both correct or is one inprecise?

# Answer
> 9 votes
From a computer architecture point of view, and with the caveat that nomenclature sometimes varies, especially when there is a family of related architectures which has evolved for a long time, or when the marketing department decides to that the usual terms have to used in another way (either to put the product in better light by using a bigger number, or to have a simple number to differentiate more or less related products).

A *word* has the size normally used for integer operations (often expressed as size of the integer or the general purpose registers, i.e. not address or data, internal or external buses, not address registers, not index registers). A common issue is that when an architecture is an evolution of a previous one, one often keep the term *word* for the initial size and one use "double word" or "quad word" for what is a word if you look at the architecture in isolation. Historically words have not always been a power of two (I know of sizes: 12, 16, 18, 24, 32, 36, 60, 64 and I don't think my knowledge is exhaustive).

*Word addressable* means that the memory is considered as arrays of words, and thus no smaller unit has an individual addresses.

A *byte* has various definitions. The term was introduced to mean the unit used in character encoding at a time where multi-byte encoding didn't exist. It is often used to means the smallest addressable unit for machine which are not word addressable (well as long at it is not one bit). I don't think those two definitions have ever given a different size. (nor a size different from 6 or 8 bits). For word addressable machine it often means some unit smaller than a word that the machine has some support for (for instance the PDP-10 -- a 36 bits word addressable computer -- had byte instructions which could manipulate any size from 1 to 35 or 36 bits). Nowadays it is also often 8 bits. Often several of those definitions are practically equivalent.

*Byte addressable* characterizes machines where the memory is considered as arrays of bytes in one of the above meaning.

AFAIK *nibble* has only been used for 4 bits quantities.

> E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Yes, but I'm not sure if it would make much sense to do so if one keeps the CA usage to use byte for something smaller than the word. Having a word addressable 16-bit processor with no support for something smaller than a word may be a good choice for a special purpose processor.

> Secondarily, what is the antonym to this word I'm looking for? Page-addressable, block-addressable?

Bit-addressable, byte-addressable and word-addressable are the only terms I've seen use. It doesn't make much sense to address only units bigger than the word at the architectural level. Word-addressable is nowadays only used for special purpose processors such as DSP. I don't think bit-addressability has been used for anything else than special purpose one excepted the IBM Stretch.

About your new main question

> What is the precise term for the smallest addressable memory block?

I know of none used in Computer Architecture (*byte* has been used for something smaller in word adressable machines), but is the definition used by C for *byte*.

# Answer
> 2 votes
The Burroughs B1700 was bit addressable (actually the address referred to the space between the bits from which you could read forward or backward an arbitrary number of bits). (So it was not only IBM's Stretch, which was a failure.)

The B1700 was designed to be the most flexible machine. Applications were not meant to be written at the bit level, but different environments built for different application styles. These environments were programmed in microcode, providing the virtual machine engines. Each language (systems SDL for OS, COBOL for business, FORTRAN for COBOL) runtime was written as a separate microcoded environment. Thus the architecture could be tailored to any future application styles.

Wayne Wilner, one of the designers, made the point that other machines of the time forced programmers to lie in the Procrustean bed of fixed-sized bytes and words. Really what each runtime environment required was data structures that suited the application. Unfortunately, most current machine architectures are still Procrustean (and thus programmed in languages like C that expose this machine structure, rather than supporting problem-oriented structures).

Further readings on this fascinating machine and its philosophy are available at:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.590.2624&rep=rep1&type=pdf

and in more detail:

http://ianjoyner.name/Files/Wilner.pdf

So why is the B1700 no longer made?

Burroughs had three main ranges of computers, the large systems B5000-B7000 (ALGOL architecture), medium systems B2000-B4000 (COBOL architecture), and small systems B1000 (anything-you-like architecture).

The large systems were really expensive, until the B5900 which was microcoded on a cheap processor to provide the ALGOL stack machine. Jack Allweis, the designer of the B5900 has pointed out that the large system architecture thus scaled down into small computers, but the B1700 was designed to be cheap and did not scale up.

Thus the B1700 to B1900, while very successful at the time, died for commercial reasons.

Burroughs large systems are still available as Unisys ClearPath MCP and even runs on your PC as an emulation.

As another footnote, IPC on the B1700 was a pain between different virtual machines, but very secure (like today's microkernels). The large systems all ran processes in the same environment where data could be shared in a secure way, but IPC was direct. This is somewhat between microkernel architectures (Mach) and non-kernel (Linux). However, the B5000 is a very secure machine, but also performs well.

Security is the biggest problem in the industry now, and really these machines should be revived and studied to show the way forward.

# Answer
> 2 votes
Main question: What is the precise term for the smallest addressable memory block?

I'll add another answer to address that in a different way. In electronic hardware, we call it the bit - binary digit. That is an entity that can represent any two values. We usually think in terms of 0 and 1, but it could be 3 or 4, 365 or 266, -3 or -4, even 25 or 37.

Any signalling system can be used to represent these values - flag up, flag down, eyes open, eyes closed, +5v, -5v. That is not important.

What is important is that philosophically we are representing the smallest distinguishing amount of information. This could be on, off, or true, false, or up, down, or 0, 1 - anything that distinguishes two separate states. We can map these values onto any of the above signalling systems and many others.

Now the question is, how can we test and set such a small amount of information individually? As I said in previous answer, the B1700 chose to address that smallest amount of information directly.

However, most machines decided to only address larger amounts of information. Let's consider a group of four bits with a single address. So if we get the value of 1011 in our location, how do we test the second bit from the left. We use a mask: 1011 and 0100 tests just the second bit. So how do we set second bit to 1? A little CPU arithmetic says the value will be 15 or 1111, so that entire four bits is written back to memory, even though we have really only set one bit.

Now this is not useful for most applications. Most applications are representing data or information, up, down, true, false, open, shut.

We want to say things like:

if open then ... else ... end

or more likely apply that to a larger entity:

if door is open then -- most likely 'door.open' ... else ... end

'door is open' illustrates hierarchical addressing. The main system addressing gives the entity door, and door has its own addressing which gives access to open (and maybe other attributes).

Most sets also have more than two possible values (a set with one value never changes and therefore does not even need representation, so zero bits). For these we have enumerated sets, like (yellow, green, blue, purple haze, red). These define sets and types and the exact number of bits required is given by the number of values (log2 (number of values)).

Thus the optimal addressing really depends on the entity size used in the application - maybe even variable sized entities. But in most hardware such addresses must be translated to the fixed size the hardware defines. This of course could cost in terms of time. It should also be something that an automatic translator does (compiler or interpreter), not a programmer, just as such a system would generate code to test and set bits as above (if bits aren't directly addressable).

An important point here is not to think in terms of electronics - electronics is just a really good and fast way of processing computations. There is nothing magic about electronic computation that makes it possible to do computations you couldn't do otherwise. The magic is only in the speed. That is why low-level abstractions such as bit, byte, word, or hardware addressing mechanisms (pointers) are really not that useful.

# Answer
> -2 votes
Our computer system used by default Byte addressable memory. Its one cell is pointing to 8-bits information. And cell size does not depend on the processor length. In word addressable memory one cell is pointing to one word information, but the word length depends on the processor length. When we use words addressable memory than its creates an ambiguity. So our computer use by default byte addressable memory.

---
Tags: terminology, computer-architecture, memory-management, memory-access
---


# Question
Title: Find most valuable subset of a node weighed tree
Suppose you got a directed acyclic graph of positvely and negatively weighed nodes $T\hspace{-0.02 in}$.
Now I have to find the the subset  $M\subseteq T$  such that the sum of
the weights of the nodes in $M$ is maximised, but if  $v \in M$  then all
children of $v$ as well as their children, and so on have to be in $M$ too.

For now my algorithm is as follows:

1. calculate the depth of each node (how many nodes you have to
traverse at maximum to reach one which doesn't have any children)
2. for all nodes $v$ of depth $n$ do the following:
    1. add up the weight of $v$ and the weights of all children and grandchildren,
    ... (you get the idea) of $v$
    2. if the last step added up to a positive value then mark $v$ and
    all children of $v$ as in $M$ and don't consider them any further
    3. if the last step marked any node with the current depth then repeat
    for this depth (since the sums changed) otherwise increment n.

This works fine for some DAGs:    (Note:  the edges are directed downwards)

As expected all nodes except the top node are in $M$

But for othes the algorithm falls short:

The algorithm outputs that  $M = \emptyset$ ,  whereas  $M=T$  should be the case.

Is there an algorithm which solves a similar problem?
If no, how can I correct my solution?  Any help is highly appreciated.

PS:    I apollogize for the use of MS Paint.  Sorry for that.

# Answer
I forget the name but it's a classic minimum-cut problem. You can always consider min-cut approach when you want to choose an optimal subset.

(Edit: It's called "project selection problem".)

Think about cutting nodes into two partitions $S$, $T$ and $S$ is what we choose. Ideally we want $S$ to contain all the positive nodes and avoid any negative node. However, it's not always possible. If there exists an edge $(u,v)$, $u\in S\to v\in S$. In the min-cut model, it means we can't cut this edge, so we set $capacity(u,v)=\inf$. Next consider what we should pay if we can't assign them ideally.

Create a source $s$ and a target $t$. For each node $u$, if $w\_u$ is positive, add an edge $(s,u)$ and set $capacity(s,u)=w\_u$. It means we lose $w\_u$ if $u\notin S$. If $w\_u$ is negative, add $(u,t)$ and set $capacity(u,t)=-w\_u$. It means we lose $-w\_u$ if $u \in S$.

The answer is $\sum\_{w\_u\>0} w\_u-min cut(s,t)$, and $M$ is the source partition.
> 3 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Can an NFA have multiple accepting states?
I am currently preparing for exam. While studying Finite Automata, i got confused. I know a DFA can have multiple accepting states, but can an NFA also have multiple accepting states?

# Answer
Whenever one is in doubt about central notions, one must consult the definitions of them. You should do this yourself (I assume that you have a textbook at your disposal).

Below is Definition 1.37 from *Introduction to the Theory of Computation* by Michael Sipser:

A nondeterministic finite automaton is a 5-tuple $(Q,\Sigma,\Delta,q\_0,F)$, where

1. $Q$ is a finite set of states,
2. $\Sigma$ is a finite alphabet,
3. $\delta: Q \times \Sigma\_{\epsilon} \rightarrow \mathcal{P}(Q)$ is the transition function,
4. $q\_0 \in Q$ is the start state, and
5. $F \subseteq Q$ is the set of accept states.

Item 5 tells us that $F$ is just a set of states, which means that it can be the empty set, a singleton set or a set with several states as elements.
> 6 votes

---
Tags: finite-automata
---


# Question
Title: What is the initial state of DFA equivalent to an $\epsilon$-NFA?
I am unsure I expressed myself correctly.

Anyway, I want to figure out what is the initial state of an automata who had its epsilon transitions removed and who was determinised.

In my text book it is stated, that suppose A is NFA with $\epsilon$-moves, suppose $q\_0$ its initial state. Then the initial state of the equivalent DFA is the E-closure of $q\_0$.

Yet in one of the softwares recommended by one of my teachers, $\epsilon$-NFA to DFA algorithm always puts the initial state as $q\_0$ and not E-closure($q\_0$).

# Answer
There is no god-given algorithm for converting $\epsilon$-NFAs to DFAs. You can do it in several ways, and the results could well be different. It could be that your textbook's construction and the one in the software are simply different.
> 3 votes

---
Tags: finite-automata
---


title: Time Complexity of Shifting

text:
# Question
Title: Time Complexity of Shifting
I'm developing a IMHO very interesting algorithm for integer division. This algorithm uses boolean shifting(It shifts left for multiplication by 2). I'm wondering if `<< c` is $O(c)$ or $O(n)$. I'm hearing it depends on architecture. Algorithms ideally should be architecture independent. So for the purposes of analysing the time complexity of my algorithm, should I consider `<< c` as `1` primitive operation or `c` primitive operations.

I've looked at the other questions here, and they are saying it depends on the machine.

I'm using RAM model of computation, but don't want to assign `<< c` a cost of `1` when it may in fact cost `c`.

# Answer
> 6 votes
Most of architectures use a single instruction for left and right shift.

Usually, this instruction (WLOG we condier only logical shift left) is **LSL**, the syntax is the following:

```
lsl $rd,$rs,#$offset

```

where *rd* is the registry in which load the variable, *rs* is the registry in which store the result and *#offset* is the number of bit to shift.

So you could consider the left or right shift operation as taking $O(1)$, because this operation takes only a single CPU's clock.

# Answer
> 6 votes
In the RAM machine model, operations on "machine words" cost $O(1)$, where a machine word has width $O(\log n)$ bits, $n$ being the length of the input (in bits). This reflects the instruction sets of real world CPUs, as mentioned in the other answers.

While the RAM machine model makes sense for many algorithmic tasks, it is not a good fit for large integer arithmetic, since in practice the machine word is fixed while the integer length is growing. Instead, one usually measures *bit operations*. Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.

These issues are explored in a paper of Martin Fürer, the inventor of the fastest known integer multiplication algorithm (which is also the fastest known integer division algorithm).

# Answer
> 2 votes
On most modern CPU architectures, such as an i5 or i7, bitshifting isn't only constant time, it's typically done in just a couple clock cycles max. It's generally considered one of the fastest operations you can do.

---
Tags: algorithms, algorithm-analysis
---


title: Converting REGEX to BNF grammar

text:
# Question
Title: Converting REGEX to BNF grammar
Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering down sentences).

Can any pure regex be converted into BNF? (ABNF, EBNF, etc.)

Are there well known algorithms (or existing library implementations) that can perform the conversion?

The language I wish to convert from is actually *not* the standard language of regular expressions, but one that conditions on word taggings which are provided per word (part-of-speech tags that come along with the text). So it is a variant of regular expressions, which operates at the word level rather than the character level.

Thanks!

# Answer
Conventional regular expressions as they are commonly found in literature describe exactly the regular languages. Given a regular expression, you can therefore find an equivalent automaton, then find the linear grammar equivalent to such automaton and put it in any form you prefer.

On the other hand, "regular" expressions as they are implemented by most programming languages are *not* equivalent to the set of regular languages; several implementations allow you to describe languages that aren't even context-free.
> 3 votes

# Answer
It depends on your type of regular expressions. Classical regular expressions describe regular languages, whereas BNFs describe context-free languages. Since regular languages are context-free, you can convert every regular expression to a BNF. This is covered in courses on automata theory. There are three steps: convert your regular expression to an $\epsilon$-NFA, then convert the $\epsilon$-NFA to an NFA, then convert the NFA to a regular grammar.
> 1 votes

---
Tags: formal-languages, formal-grammars, regular-expressions
---


# Question
Title: Algorithmic intuition for logarithmic complexity
I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.

In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of the list. $\Theta(n)$ is where I'd walk the entire list once, and $\Theta(n^2)$ is walking the list once for each element in the list.

Is there a similarly intuitive way to grasp $\Theta(\log n)$ other than just knowing it lies somewhere between $\mathcal{O}(1)$ and $\Theta(n)$?

# Answer
> 56 votes
The $\Theta(\log n)$ complexity is usually connected with subdivision. When using lists as an example, imagine a list whose elements are sorted. You can search in this list in $\mathcal{O}(\log n)$ time - you do not actually need to look at each element because of the sorted nature of the list.

If you look at the element in the middle of the list and compare it to the element you search for, you can immediately say whether it lies in the left or right half of the array. Then you can just take this one half and repeat the procedure until you find it or reach a list with 1 item which you trivially compare.

You can see that the list effectively halves each step. That means if you get a list of length $32$, the maximum steps you need to reach one-item list is $5$. If you have a list of $128 = 2^7$ items, you need only $7$ steps, for a list of $1024 = 2^{10}$ you need only $10$ steps etc.

As you can see, the exponent $n$ in $2^n$ always shows the number of steps necessary. Logarithm is used to "extract" exactly this exponent number, for example $\log\_2 2^{10} = 10$. It also generalizes to list lengths that are not powers of two long.

# Answer
> 38 votes
In terms of (balanced) trees (say, binary tree, so all $\log$'s are base 2):

* $\Theta(1)$ is getting the root of the tree
* $\Theta(\log n)$ is a walk from root to leaf
* $\Theta(n)$ is traversing all nodes of the tree
* $\Theta(n^2)$ is actions on all the subsets two nodes in the tree, e.g., the number of different paths between any two nodes.
* $\Theta(n^k)$ - generalization of the above for any subset of $k$ nodes (for a constant $k$)
* $\Theta(2^n)$ is actions on all the possible subsets of nodes (subsets of all the possible sizes, i.e., $k=1,2, \ldots, n$.). For instance, the number of different *sub-trees* of the tree.

# Answer
> 18 votes
For $O(\log n)$ to be possible, you need to be able to cut down the problem size proportionally by some arbitrary amount with respect to $n$ with a constant time operation.

For example, in the case of binary search, you can cut down the problem size by a half with each comparison operation.

Now, do you have to cut down the problem size by half, actually no. An algorithm is $O(\log n)$ even if it can cut down the problem search space by 0.0001%, as long as the percentage and the operation it uses to cut down the problem size stays constant, it's a $O(\log n)$ algorithm, it won't be a fast algorithm, but it's still $O(\log n)$ with a very large constant. (Assuming we are talking about $\log n$ with a base 2 log)

# Answer
> 9 votes
Yes, $\log(n)$ is between $1$ and $n$, but it is closer to $1$ than $n$. What is $\log(n)$? The log function is the inverse function of exponentation. Let me start with exponentation and you should get a better idea of what logarithm is.

Consider two numbers, $100$ and $2^{100}$. $2^{100}$ is $2$ multiplied with itself $100$ times. You can with some effort count $100$ numbers, but can you count $2^{100}$? I bet you can't. Why? $2^{100}$ is such a big number that it is greater than the number of all atoms in the universe. Reflect on that for a moment. It is such a huge number, that it allows you to give each atom a name (number). And the number of atoms in your finger nail is probably in the order of billions. $2^{100}$ ought to be enough for anyone (pun intended :)).

Now, between the two numbers, $100$ and $2^{100}$, $100$ is the logarithm of $2^{100}$ (in base $2$). $100$ is comparatively such a small number than $2^{100}$. Anybody ought to have $100$ different items in their home. But, $2^{100}$ is good enough for the universe. Think home vs universe when thinking of $\log(n)$ and $n$.

Where do exponentation and logarithms come from? Why are they of so much interest in computer science? You may not notice, but exponentation is everywhere. Did you pay interest on credit card? You just paid a universe for your home (Not so bad, but the curve fits). I like to think that exponentation comes from product rule, but others are welcome to give more examples. What's product rule, you may ask; And I shall answer.

Say you have two cities $A$ and $B$, and there are two ways to go between them. What is the number of paths between them? Two. That is trivial. Now say, there is another city $C$, and you can go from $B$ to $C$ in three ways. How many paths are there between $A$ and $C$ now? Six, right? How did you get that? Did you count them? Or did you multiply them? Either way, it is easy to see that both ways give a similar result. Now if you add a city $D$ which can be reached from $C$ in four ways, how many ways are there between $A$ and $D$? Count if you don't trust me, but it is equal to $2\cdot 3\cdot 4$ which is $24$. Now, if there are ten cities and there are two paths from one city to the next, and they are arranged like they are on a straight line. How many paths are there from start to end? Multiply them if you don't trust me, but I will tell you there are $2^{10}$, which is $1024$. See that $2^{10}$ is exponential result of $10$, and $10$ is the logarithm of $2^{10}$. $10$ is a small number compared to $1024$.

The logarithm function $\log\_2(n)$ is to $n$ what $n$ is to $2^n$ (note that $2$ is the logarithm's base). If you multipy $\log\_b(n)$ with itself $b$ times (note that $b$ is the logarithm's base) you get $n$. $\log(n)$ is so tiny, so small compared with $n$, that it is size of your home where $n$ is size of the universe.

On a practical note, $\log(n)$ functions perform very similar to constant functions. They do grow with $n$, but they grow very slowly. If you optimized a program to run in logarithmic time which was taking a day before, you will probably run it in the order of minutes. Check for yourself with problems on Project Euler.

# Answer
> 9 votes
Think about algorithm to convert decimal number $n$ to binary

```
while n != 0:
   print n%2,
   n = n/2

```

This `while` loop runs $\log(n)$ times.

# Answer
> 6 votes
To continue your theme, $O(\log n)$ is like repeatedly guessing where $x$ lies in the list and being told "higher" or "lower" (in terms of index).

It's still based on the size of the list, but you only need to visit a fraction of the elements.

# Answer
> 5 votes
If we have a divide and conquer algorithm, and we make only one recursive call for a subproblem, and it is the second case in Master theorem, i.e. the time complexity of the non-recursive part is $\Theta(\lg^k n)$, then the complexity of the algorithm will be $\Theta(\lg^{k+1} n)$.

In other words, when we have a divide and conquer algorithm with one recursive call to itself on a problem with size a constant factor of the current problem, and the time in the non-recursive part is $\Theta(1)$ (constant), then the running time of the algorithm is going to be $\lg n$.

The binary search algorithm is the classical example.

# Answer
> 2 votes
The intuition is how many times you can halve a number, say n, before it is reduced to 1 is O(lg n).

For visualizing, try drawing it as a binary tree and count the number of levels by solving this geometric progression.

```
2^0+2^1+...+2^h = n

```

---
Tags: algorithms, complexity-theory, time-complexity, intuition
---


# Question
Title: Touchpad driver missing after windows 10 installation in acer E3-111-290X
I was asked by a friend to help installing windows 10 in an acer E3-111-290X that was previously running windows 7, but after installing windows 10 the touchpad stopped working.I've tried several solutions such as synaptics drivers but didn't work. Anyone with an answer or knowing a better place to get the solution for the problem, help please!

# Answer
> 1 votes
According to this link, you may have more luck installing the Synaptics driver from the Acer website in compatibility mode.

---
Tags: os-kernel
---


title: Iteration can replace Recursion?

text:
# Question
Title: Iteration can replace Recursion?
I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only iteration".

There was even a highly upvoted thread with a highly upvoted answer that said yes it's possible.

Now I'm not saying they're wrong. It's just that that answer counters my meagre knowledge and understanding about computing.

I believe every iterative function can be expressed as recursion, and wikipedia has a statement to that effect. However, I doubt the converse is true. For one, I doubt non-primitive recursive functions can be expressed iteratively.

I also doubt hyper-operations can be expressed iteratively.

In his answer(which I don't understand by the way) to my question @YuvalFIlmus said that it's not possible to convert any sequence of mathematical operations into a sequence of additions.

If YF's answer is indeed correct (I guess it is, but his reasoning was above my head) then doesn't this mean that not every recursion can be converted into iteration? Because if it was possible to convert every recursion into iteration, I'd be able to express all operations as a sequence of additions.

My question is this:

> Can every recursion be converted to iteration and why?

Please give an answer a bright highschooler or a first year undergrad will understand. Thank you.

P.S I don't know what primitive recursive is (I do know about the Ackermann function, and that it isn't primitive recursive, but is still computable. ALl my knowledge on it comes from the Wikipedia page on the Ackermann function.)

P.P.S: If the answer is yes, could you for example write an iterative version of a non-primitive-recursive function. E.g Ackermann in the answer. It'll help me understand.

# Answer
It's possible to replace recursion by iteration *plus unbounded memory*.

If you only have iteration (say, while loops) and a finite amount of memory, then all you have is a finite automaton. With a finite amount of memory, the computation has a finite number of possible steps, so it's possible to simulate them all with a finite automaton.

Having unbounded memory changes the deal. This unbounded memory can take many forms which turn out to have equivalent expressive power. For example, a Turing machine keeps it simple: there's a single tape, and the computer can only move forward or backward on the tape by one step at a time — but that's enough to do anything that you can do with recursive functions.

A Turing machine can be seen as an idealized model of a computer (finite state machine) with some extra storage that grows on demand. Note that it's crucial that not only there isn't a finite bound on the tape, but even given the input, you can't reliably predict how much tape will be needed. If you could predict (i.e. compute) how much tape is needed from the input, then you could decide whether the computation would halt by calculating the maximum tape size and then treating the whole system, including the now finite tape, as a finite state machine.

Another way to simulate a Turing machine with computers is as follows. Simulate the Turing machine with a computer program that stores the beginning of the tape in memory. If the computation reaches the end of the part of the tape that fits in memory, replace the computer by a bigger computer and run the computation again.

Now suppose that you want to simulate a recursive computation with a computer. The techniques for executing recursive functions are well-known: each function *call* has a piece of memory, called a *stack frame*. Crucially, recursive functions can propagate information through multiple calls by passing variables around. In terms of implementation on a computer, that means that a function call might access the stack frame of a (grand-)<sup>*</sup>parent call.

A computer is a processor — a finite state machine (with a huge number of states, but we're doing computation theory here, so all that matters is that it's finite) — coupled with a finite memory. The microprocessor runs one giant while loop: “while the power is on, read an instruction from memory and execute it”. (Real processors are much more complex than that, but it doesn't affect what they can compute, only how fast and conveniently they do it.) A computer can execute recursive functions with just this while loop to provide iteration, plus the mechanism to access memory, including the ability to increase the size of the memory at will.

If you restrict the recursion to primitive recursion, then you can restrict iteration to *bounded* iteration. That is, instead of using while loops with an unpredictable running time, you can use for loops where the number of iterations is known at the beginning of the loop¹. The number of iterations might not be known at the beginning of the program: it can itself have been computed by previous loops.

I'm not going to even sketch a proof here, but there is an intuitive relationship between going from primitive recursion to full recursion, and going from for loops to while loops: in both cases, it involves not knowing in advance when you'll stop. With full recursion, this is done with the minimization operator, where you keep going until you find a parameter that satisfies the condition. With while loops, this is done by keeping going until the loop condition is satisfied.

¹ <sub> `for` loops in C-like languages can perform unbounded iteration just like `while`, it's just a matter of convention to restrict them to bounded iteration. When people talk about “for loops” in theory of computation, that means only loops that count from 1 to $n$ (or equivalent). </sub>
> 55 votes

# Answer
Every recursion can be converted to iteration, as witnessed by your CPU, which executes arbitrary programs using a fetch-execute infinite iteration. This is a form of the Böhm-Jacopini theorem. Moreover, many Turing-complete models of computation have no recursion, for example Turing machines and counter machines.

Primitive recursive functions correspond to programs using *bounded* iteration, that is, you have to specify the number of iterations that a loop is executed in advance. Bounded iteration cannot simulate recursion in general, since the Ackermann function isn't primitive recursive. But unbounded iteration can simulate any partially computable function.
> 35 votes

# Answer
As an example to the answer from Gilles, here is an "iterative" algorithm for the Ackermann function (using the common Ackermann-Péter version mentioned by Wikipedia $a(n,m)$).

We need a stack $s$ of integers.

Such a stack has two modifying operations, $\DeclareMathOperator{\push}{push}\push(s, x)$ (which puts a new element $x$ on the stack) and $\DeclareMathOperator{\pop}{pop} x ← \pop(s)$ which retrieves (and removes) the top element, and one querying operation $\DeclareMathOperator{\empty}{empty}\empty(s)$, which returns true if there are no elements left on the stack (false if there are more).

$\texttt{Ackermann}(n\_0, m\_0):$ $\def\ifop#1{\texttt{if(}#1\texttt{):}}$ $\def\elseif#1{\texttt{else if(}#1\texttt{):}}$ $\def\elsop{\texttt{else:}}$

* $s = \emptyset $ (initialize empty stack)
* $\push(s,n\_0)$
* $\push(s,m\_0)$
* $\texttt{while(true):}$
    + $m ← \pop(s)$
    + $\ifop{\empty(s)}$
        - $\texttt{return }m$ (this ends the loop)
    + $n ← \pop(s)$
    + $\ifop{n = 0}$
        - $\push(s, m+1)$
    + $\elseif{m=0}$
        - $\push(s, n-1)$
        - $\push(s, 1)$
    + $\elsop$
        - $\push(s, n-1)$
        - $\push(s, n)$
        - $\push(s, m-1)$

I implemented this in Ceylon. *(The Ceylon Web IDE unfortunately doesn't work anymore.)* (It outputs the stack at the start of each iteration of the loop.)

Of course, this just moved the implicit call stack from the recursion into an explicit stack with the parameters and return values.
> 26 votes

# Answer
There are already some great answers (which I can't even hope to compete with), but I'd like to pitch this simple explanation.

Recursion is just the manipulation of the runtime stack. Recursing adds a new stack frame (for the new invocation of the recursive function), and returning removes a stack frame (for the just-completed innovation of the recursive function). Recursion will cause some number of stack frames to be added/removed, until eventually they all exit (hopefully!) and result is returned to the caller.

Now, what would happen if you made your own stack, replaced recursive function calls with pushing to the stack, replaced returning from recursive functions with popping the stack, and had a while loop that ran until the stack was empty?
> 16 votes

# Answer
As far as I can tell, and in my own experience, you can implement any recursion as an iteration. As mentioned above, recursion uses the stack, which is conceptually unlimited, but practically limited (have you ever gotten a stack overflow message?). In my early days of programming (in the third quarter of the last century of the last millennium) I was using non-recursive languages implementing recursive algorithms and had no problems. I am not sure of how one would prove it, though.
> 2 votes

---
Tags: computability, recursion, iteration
---


# Question
Title: Decidability of the TM's computing a non-empty subset of total functions
I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L\_S=\\{ \langle M \rangle | M \text{ is a TM that computes a function and } f\_M\in S \\}$$

where $f\_M$ is the function $M$ computes.

Prove that for every such none-trivial $S$, $L\_S \notin \mathcal{R}$.

I tried to construct

* $L\_{f}=\left\\{ x\\#y\in{\Sigma^\*}|y=f\left(x\right)\right\\} $
* $\tilde{S}=\left\\{ L\_{f}|f\in S\right\\} $
* $L\_{\tilde{S}}=\left\\{ \left\langle M\right\rangle |L\left\langle M\right\rangle \in\tilde{S}\right\\} $

and then show with Rice that $L\_{\tilde{S}} \notin \mathcal{R}$, when the idea behind it was to eventually show that $L\_{\tilde{S}} \leq\_m L\_S $. But the problem here is that I couldn't show a mapping reduction from $L\_{\tilde{S}}$ to $L\_S$ without assuming $L\_{\tilde{S}} \in \mathcal{RE}$ (which I'm quite sure is not true).
So any other directions will be warmly welcomed!

# Answer
> 1 votes
For any function $f: \Sigma^\* \rightarrow \Sigma^\*$, let

$$L\_f = \\{ x \\# y \mid y = f(x) \\}$$

For any Turing machine $M$, we can construct the description of a Turing machine $M'$ such that $M'$ recognizes $L\_f$ if and only if $M$ computes $f$. $M'$ will receive a string, check that it is of the form $x \\# y$ and then simulate $M$ with input $x$. If the simulation returns $w$, $M'$ accepts if $w = y$. Therefore, the language

$$ A\_f = \\{ \langle M \rangle \mid M \text{ is a TM that computes the function $f$} \\}$$

reduces to the language

$$B\_f = \\{\langle M \rangle \mid L(M) = L\_f \\}$$

The class

$$L\_S = \\{ L\_f \mid f \in S \\}$$

is a nontrivial class of Turing-recognizable languages and therefore the decision problem $B\_f$ is undedicable by Rice's theorem.

# Answer
> 0 votes
You can construct $\ \mathcal{C}=\\{L\in\mathcal{RE}\ |\ \exists f\in S \ \text{such that}\ \ \mathrm{Im} f=L\\}$ and it is clear That $\emptyset \subset \mathcal{C}\subset \mathcal{RE}$ (because it is a set of languages from $\mathcal{RE}$ and it is clearly not empty and there are languges in $\mathcal{RE}$ that do not compute a computable function because they are not decidable) and then by Rice's Theorem you get $\\{\langle M\rangle \ | \ L(M)\in\mathcal{C}\\}\not \in \mathcal{R}$ and this language is exactly $L\_S$ so $L\_S \not \in \mathcal{R}$.

# Answer
> 0 votes
Assume WLOG\* $Id\in S$ ($\forall x\in\Sigma^\*:\ Id\left(x\right)=x$)

Define $f\left(\left\langle M,w\right\rangle \right)\mapsto\left\langle M'\right\rangle$ where $M'$ is a TM that on input x:

* if $M$ halts on $w$ then $M'$ accept (leave $x$ on the tape)

if $\left\langle M,w\right\rangle \in H\_{TM}$ then $M'$ halts on every $x$ and the content of the tape by the end of the run is $x$ ($M'$ computes $Id$) - $\left\langle M'\right\rangle \in F$

if $\left\langle M,w\right\rangle \notin H\_{TM}$ then $M'$ never halts hence $\left\langle M'\right\rangle \notin F$.

Since $H\_{TM}\leq\_m L\_{S}$ and $H\_{TM}\notin\mathcal{R}$ we have $L\_{S}\notin\mathcal{R}$.

**WLOG\*:** if $Id\notin S$ prove for $\overline{S}=F\smallsetminus S$ - since now $Id\in\overline{S}$ the same proof holds, so $L\_{\overline{S}}\notin\mathcal{R} L\_{\overline{S}}=\left\\{ \left\langle M\right\rangle |f\_{M}\notin S\right\\}$ . Assume that $\overline{L\_{S}}=\left\\{ w\in\Sigma^\*|\mbox{ if }w\mbox{ is an encoding of a TM then }w\mbox{ does not compute a function }f\in S\right\\} \in\mathcal{R}$ and $R$ decides $\overline{L\_{S}}$. We can construct a reduction f that on input $w$:

* if $R$ accepts $w$

+ check if w is a TM encoding
    + if w is a TM, accept
* reject

then $w\in\overline{L\_{S}}$ iff $f\left(w\right)\in L\_{\overline{S}}$ so we can decide $L\_{\overline{S}}$ using $R$.

So $\overline{L\_{S}}\notin\mathcal{R}\implies L\_{S}\notin\mathcal{R}$

---
Tags: computability, turing-machines, reductions, undecidability
---


# Question
Title: Hash function to hash 6-digit positive integers
Let UID denote a unique identifier. UID's are represented as 6-digit positive integers.

I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for example, 524309).

If I am not mistaken, since $M$ is prime, dividing an UID with $M$ generates a unique remainder, as there is no common factor, except 1.

**Example 1:** UID = 222222 and $M$ = 524309.

**Example 2:** UID = 524309 and $M$ = 524309. In this example, the UID is hashed to bucket number zero in the hash table. The hash function is `h(UID) = UID % M`.

The question is: can hash function `h` avoid collisions for any 6-digit UID?

If yes, what is the mathematical approach to prove it?

# Answer
A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that maps hash codes to locations in the hash table where the item would be stored.

Hashing every UID to a different 32 bit hash code is trivial - just hash every UID to itself. No collisions. The mapping function of the hash table should be implemented in a way that common hash functions don't lead to many collisions. Many hash functions either produce results that look like random, or like in this case might produce many consecutive values, so using a prime number as the hash table size and (hash code modulo hash table size) as the first location for the location in the table works quite well.

Since you have one million items, and 524309 entries, it's impossible to guarantee no collisions. In practice, that's not a problem. What counts is the time for calculating the hash code, plus the average time for finding and checking one or more locations in your hash table. As long as the average number of collisions is small, you are fine. And there is a simple way that usually keeps the number of collisions small: Use a generous size for the hash table.
> 3 votes

# Answer
A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In your case, $U$ is the set of UIDs. Since $|U|=1000000$ and $M= 524309$, then $M \< |U|$ and, therefore, collisions will inevitably occur (see Pigeonhole principle).

As an answer to your comment:

> When you say generous size for the hash table, Is M = 999,983 fine?

What really determines the performance of a hash table is the load factor, which is the ratio $\alpha = k / M$, where $k$ is the number of items stored in the hash table. The load factor can be controlled by dynamically increasing (or decreasing) $M$, as items are inserted into (or deleted from) the hash table. When to increase/decrease $M$ depends on the hash table implementation:

* In open addressing, keep a load factor of, roughly, $\alpha \leq 0.7$.
* In separate chaining, keep $\alpha$ as a small constant (ideally close to 1). This will guarantee constant-time insertions, deletions, and look-ups.

With these rules of thumb in mind, you can find an appropriate $M$ using existing algorithms for primality testing.
> 3 votes

# Answer
I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're trying to store a mapping of UIDs to usernames or something like that. The naive way of doing that would be to just have an array with one entry for each possible UID so, in this case, an array of 1,000,000 strings. The advantage of that approach is that you can look up the name associated with a UID in constant time: you just write something like `username[uid]` to retrieve it from the array. The problem is that in most applications, you only have maybe a few thousand users at most, so most of your array is empty and you're wasting a lot of space.

You can avoid wasting the space by, for example, storing pairs of UID and username in a linked list: now you only have one entry in the list for each user so you're much more memory-efficient. However, retrieving a username now requires a linear search through the list, as does adding a new username. Using something like a search tree would allow logarithmic look-up and insertion but that's still quite a bit slower than an array.

The point of using a hash table is that it gives you nearly constant look-up and insertion time, like an array, but it doesn't waste as much space. The idea is that, instead of storing a UID's username at `username[uid]`, you store it at `username[h(uid)]` for some function `h` which is fairly easy to compute. You choose a function with a range that is the size of the hash table you're going to use, and the point is to make this a good deal smaller than the number of possible UIDs.

However, doing this *guarantees* that `h` will map at least two UIDs to the same slot in the hash table: this is exactly the pigeonhole principle. Unless you know in advance exaclty what data you're going to be storing, you it's impossible to guarantee that this won't happen; all you can do is try to make it unlikely and deal with the inevitable collisions when they happen.

In a comment, you ask if using a hash table with size 999,983 would work. That wouldn't be a sensible hash table, since it's almost as big as just using an array of size 1,000,000 and forgetting about hashing. In fact, it's bigger because dealing with collisions would require you to store both the UID and username for each entry in the hash table, whereas in an array, you just need to store the username.

In the question, you say

> since $M$ is prime, dividing an UID with $M$ generates a unique remainder

That has nothing to do with whether or not $M$ is prime. Dividing any positive integer by any other positive integer produces a single, well-defined, unique remainder.
> 3 votes

---
Tags: data-structures, hash, mathematical-analysis, primes, hashing
---


# Question
Title: Minimize the maximum Hamming weight of basis vectors spanning a binary subspace
In the course of my research, I stumbled upon a problem which can be recast as the following decision problem:

---

First some notation:

Let $\mathbb{F}=\\{0,1\\}$ be the binary field. For $x\in\mathbb{F}^N$, $N\in\mathbb{N}$ arbitrary, let $w(x)$ denote the *Hamming weight* of $x$, i.e., the number of non-zero components.

Let $B\subset \mathbb{F}^N$ be an arbitrary set of binary vectors. Define the Hamming weight of $B$ as $w(B)\equiv \max\_{b\in B}w(b)$.

Now the problem:

> Given a linear subspace $V\leq \mathbb{F}^N$ and a positive integer $C\leq N$.
>
> Is there a basis $B$ of $V$ such that $w(B)\leq C$ ?

The "size" of a particular instance is the dimension $\rm{dim} V=K\leq N$, as the brute-force solution requires the computation of $w$ for all possible bases of $V$.

Clearly, the evaluation of $w(B)$ requires $\mathcal{O}(KN)$ steps; therefore the problem is in **NP**.

As an example: If $V=\mathbb{F}^N$ and $C\geq 1$, the answer is positive as the standard basis ($e\_i=(0,\dots,1,\dots,0$) has hamming weight 1. Obviously this is not the case for generic, non-trivial subspaces $V$.

---

I think the problem is closely related to the theory of linear binary codes (in fact, $V$ is one). In this context, however, people seem to be more interested in the *minimum* Hamming weights as these relate to the Hamming distance of the code.

As my understanding of and experience in complexity theory is rather sparse (my background is condensed matter physics), I do not know wheter this problem is known in complexity theory. If so, *what is its complexity class (time complexity) ?* Are there any relevant publications for this particular problem? Maybe it's even a simple textbook problem?

Any hint is welcome. Thanks in advance.

# Answer
> 2 votes
This is background, rather than a complete solution of your specific question.

What you're looking at are called linear **anticodes** in the literature, while Ahlswede uses the term "diameter" for the maximum distance of a code. Like normal codes, there are some bounds on maximum size, given length and distance.

The problem may also be stated in terms of the minimum number of coordinates where two codewords agree. If the alphabet is nonbinary, it gets much more complicated, and \[1\] has an upper bound for that case, but also discusses the result from \[2\] which is the following:

Given a binary anticode with diameter (maximum distance) $n-t$ over the binary alphabet (which need not be linear), letting $N\_2(n,t)$ be the maximum cardinality of such a code we have $$N\_2(n,t)=\left\\{ \begin{array}{lrr} \sum\_{i=0}^{(n-t)/2} \binom{n}{i},&\quad& if~n-t~is~even,\\ & & \\ 2 \sum\_{i=0}^{(n-t-1)/2} \binom{n-1}{i},&\quad& if~n-t~is~odd. \end{array} \right. $$

See the reference \[1\] for details. Apparently the binary diametric theorem above was proved by Kleitman in \[2\]. This bound applies to all anticodes and would apply to your linear anticode as well.

Farrell had an earlier article on anticodes which considered linear anticodes obtained by deleting columns from a simplex code, which may also be of interest, it shouldn't be hard to locate the reference.

\[1\] Ahlswede and Khachtarian, The Diametric Theorem in Hamming Spaces:Optimal Anticodes, Adv. Appl. Math:20, 429:449 1998.

\[2\] D. J. Kleitman, On a combinatorial conjecture of Erdos, J. Combin. Theory, Volume 1, pp.209-214, 1966.

---
Tags: time-complexity, arithmetic, linear-algebra, coding-theory
---


title: How fast is this Division Algorithm

text:
# Question
Title: How fast is this Division Algorithm
I wrote an algorithm for integer division. I'm wondering how fast it is asymptotically. I used RAM model myself to asymptotically analyse it, but I found out that:

> Elementary CPU instructions like shifting and adding, are not constant as the integers grow arbitrarily large.

So it seems my analysis is wrong. I'd like to know how fast the algorithm is. I'll leave in my original analysis using RAM model of computation.

---

I think I've found a linear time algorithm to solve this problem. I will attempt to calculate it's time complexity. I hope someone in the community, can point me to where I may have made a mistake. I am assuming the RAM model of computation. In particular, I am making these assumptions.
(1) Addition and subtraction take one primitive operation.
(2) Boolean shifting takes one primitive operation.
(3) Reading from memory takes one primitive operation.
(4) Writing to memory, takes another primitive operation.
(5) Logical comparison takes one primitive operation.
(6) Returning a value takes one primitive operation.
(7) Creating a variable or an array takes one primitive operation.(Irrespective of size of Array)
(8) Assignment takes one primitive operation.

Please correct me if I made any wrong assumptions. I will try to determine the run time complexity of this algorithm. I will use $+i$ to denote a particular piece of code takes $i$ primitive operations and $+k \cdot i$ to denote $ki$ primitive operations. I will attempt to total all the primitive operations. (I will keep a tally at each 'block' of code of total expenditure of that block in the form $T = k$ where $k$ is the total so far)

The section below outlines the algorithm for those who may want to fix, improve, understand, etc.

> The Idea of this algorithm, is that $\log\_2(2^n) = n$ (Initial growth of the quotient using powers of two.) It attempts to reduce time-complexity of the algorithm, at the expense of space complexity.
>
> Multiplication as far as this algorithm is concerned, will be replaced by use of the binary "\<\<" operator.
>
> We Know that the rest of the quotient is between $0$ and the previous value of $k$(Because `b` was lower than `k*a`). So we run a binary search between `0*a` and previous `k*a`. An array of all powers of two up to the current value of `k`(That produced `k*a > b`) are kept. This array is then used to perform a binary search.
> $\log\_2(2^n-1) = n-1$
> $n + n-1 = 2n$ $$f(n) = \Theta(n)$$

`compare(x, y)` A comparison function, that shall be used to aid binary search.
`{`
`if(x == y) return 0`$+1$
`else if(x > y) return -1`$+1$
`else if(y > x) return 1`$+1$
`}`$+1$(for return)

$T = 4$(Whenever this function is called, 4 primitive operations take place.)

`a = divisor, b = dividend, q = quotient, r = remainder` $+4$ (Creating 4 variables) m = Array size. Set it to whatever you want. Ideally it should be $\ge$ maximum size of input $n$
`$state = 1` If the numbers have the same sign `0` otherwise. $+3$(Creating a variable, Logical comparison and assignment)
`divide(a, b, &q, &r)` q and r are passed to the function by reference. So that both may be returned.
`{`
convert `a` and `b` to unsigned integer types. $+2$ `q = 0`$+1$
`k = 1` This will be the multiplier by which `b`will be tested.$+1$
`m = 100` (`m` should be $\ge \log\_2(b)$ or `n`. I'm just arbitrarily picking $100$ `Array[m]` Initialise all elements with 0 (If it increases time complexity of algorithm, initialise only the first element to 0. $+1$ (Or $+m$ it doesn't matter this is a constant and has no bearing on the asymptotic complexity.)
`Array[0] = {0}` $+1$
`i` A variable to be used as a control variable for the array.$+1$
`for(i = 0 ; b >= (a << i) ; i++)` $+3$(One logical comparison, One increment of $i$ each time loop is executed., one shift operation)
`{`//Note that `a*k` is the same as `a << i` $i$ is $\log\_2(k)$
`Array[i] = k //Stores powers of 2 in their corresponding index. These will be used later on in a binary search.`$+1$
`(k << 1) //Doubling k`$+1$
`}`$T = 5$(Loop takes 4 primitive operations whenever called)
`q += Array[i-1] //Previous value of k`$+1$
`b -= (a << (i-1))` //b - (a * previous value of k) $+1$
`if(b < a)`$+1$(`b` will be less than `k` if `q` is the quotient)
`{`
`r = b` $+1$ `return 0 //Function returns with a value, r and q are the values of the variables passed into the function.`
`}`

`else if(b > a) //b is between 0 and Array[i-1]*a. Time to perform a binary search using Array[]. q is between 0 and Array[i-1]`$+1$
`j = i-2`$+1$

`while(true)` //This loop runs a maximum of $(log(2^{(n-1)}))$ times. I.e $(n-1)$ times.
`{`
`det = compare((a << j), b)` Comparing `b` versus some power of `2` times `a`$+5$(compare takes 4 operations, and assignment takes 1)
`if(j != 0)`$+1$
`{`
`if(det == 0)`$+1$
`{`
`r = 0`$+1$
`q += Array[j]`$+1$
`return 0`
`}`$T = 3$

`else if(det == 1)`$+1$
`{`
`q += Array[j]`$+1$
`b -= (a << j)`$+1$
`j -= 1`$+1$
`}`$T=4$

`else if(det == -1)`$+1$
`{`
`j -= 1`$+1$
`}`
`}`$+6$(Only one of the selective code blocks will execute. The costliest, is the second one +1 for the outer block, +1 for testing the first block. +4 for second block.)

`else if(j == 0)`$+1$
`{`
`if(det == 0)`(No remainder `Array[0] = 1` it will be treated as such.).$+1$
`{`
`r = 0`$+1$
`q += 1`$+1$
`return 0`
`}`$T = 3$

`else if(det == 1)`(b \> a, means that there's a remainder(b-a))$+1$
`{`
`q += Array[j]`$+1$
`b -= (a)`$+1$
`r = b`$+1$
`return 0`
`}`$T = 4$

`else if(det == -1)`(b is less than a. Mean current q is quotient, and current b is remainder.)$+1$
`{`
`r = b`$+1$
`return 0`
`}`$T = 2$
$+1$(For final return)
`}`$T = 6$(Same reason as above)

`}`$T = 12$(det takes 5, both loops take 6, the second also has the comparison of the first, so that's +1 5 +7 =12) `q = ($state == 0)?-q:q`$+2$

I will ignore the sum of the constants, since they are irrelevant to the asymptotic complexity.
The time complexity $f(n)$ of the algorithm is given by: $f(n) = O(M\_1\cdot5 + M\_2\cdot12)$
Where: $M\_1 = $ number of times the first loop ran.
$M\_2 = $ number of times the second loop ran. $M\_1 = \log(2^{n+1}) = n+1$ (Worst case when `a` is `1` Loop runs until `k > b`) $M\_2 = \log(2^{n-1}) = n-1$ (Worst case when `b` is $2^n-1$. Loop performs a binary search.)
$f(n) = O((n+1)\cdot5 + (n-1)\cdot12)$
$f(n) = O(5n + 5 + 12n -12)$
$f(n) = O(17n - 7)$
$$f(n) = \Theta(n)$$

Please tell me what the run time complexity of this algorithm is. Especially as $n$ gets large.

# Answer
> 2 votes
Your algorithm runs in $O(n^2)$ bit operations, so $O(n^2/\log n)$ time on the RAM machine. This is the same complexity as long division.

As you mention, there are at most $n$ iterations. Each iteration involves an addition operation which takes $\Theta(n)$ (the comparison operation takes less time on average). Altogether, we obtain the bound $O(n^2)$.

---
Tags: algorithms, algorithm-analysis, asymptotics
---