# Question
Title: Big O vs Big $\Theta$ during coding interview
Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview":

> "In industry (and therefore in interviews), people seem to have merge Θ and together. Industry's meaning of big O is closer to what academics mean by Θ , in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is O(N)"

In an interview context, would it be considered ok to say $\Theta$ instead of O?
If the interviewer is asking : "What's the Big O of this algorithm?", is it alright to answer :"The time complexity of this algorithm is $\Theta$(n)"?
I'm wondering if most interviewers would think I'm trying to outsmart them by saying that. But I don't feel comfortable by replacing O by $\Theta$ since they don't have the same meaning.

# Answer
Here is an answer from reddit that I found the most useful:

> I guess I would say, if someone says, "what's O of insertion sort?", you want to say "it's $O(n^2)$". Sure it's not precisely the same thing as saying that it's "$\Theta(n^2)$ in the worst case", but it's a convention that everyone understands, and it takes less time to get the words out of your mouth.
> 0 votes

# Answer
I think its fine. It just shows the interviewer you actually know what the real meaning of big-O and theta are. Just make sure its actually true (the $\Omega$ part) when you have a complicated algorithm and you have used some inequality for big-O complexity proof.
> 1 votes

# Answer
If you mention big-theta many interviewers will think you are wrong because they never heard of it. If you then start debating it, then you fail at what the interview is primarily about: Convincing the interviewer that they want to work with you.

Question: You check if X is a prime by testing divisibility by 2, 3, 5, 7, 11 etc. What is the Big-O of the time complexity? If you answer “it’s big-Theta”, what will my opinion of you be?
> 1 votes

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


# Question
Title: Computation Complexity books for a mathematician
I recently attented to some computational complexity talks (or complexity theory, I am not sure which is the correct name) and I fell in love with it. I would like to find some books, online courses... in general resources of any kind to self-study this (securely) wonderfull subject.

My backgrund is pure mathematics with emphasys in discrete mathematics (graph theorey, crypto, coding thoery, combinatorics...), with no background in computer science. I am not sure if the last one is mandatory.

# Answer
> 11 votes
Michael Sipser's text book Introduction to the Theory of Computation is a classic introduction to computation theory, and gives an introduction to complexity theory in the end.

I don't know how to answer the question better than just providing the table of contents of the book.

```
PART 1: AUTOMATA AND LANGUAGES.
1. Regular Languages.
2. Context-Free Languages.

PART 2: COMPUTABILITY THEORY.
3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.

PART 3: COMPLEXITY THEORY.
7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.

```

# Answer
> 8 votes
You might want to consider Computational Complexity: A Modern Approach by Arora and Barak. Roughly speaking, its early chapters overlap with later chapters in Sipser, and it has more material on computational complexity per se.

Arora and Barak's book (A&B) seems self-contained. For example, you don't need to know the parts of Sipser or similar books that A&B don't cover, in order to understand A&B. On the other hand, my sense is that A&B moves a little bit more quickly and requires a little bit more insight than Sipser. I could be wrong. I am reading A&B and have only glanced at parts of Sipser and have read a few comments online comparing the two.

In terms of content, my guess is that A&B is one good option for your interests, and if the level of A&B is inappropriate for you, it will be because it is too easy (it's not, for me), and because some other book goes into ideas more deeply more quickly.

# Answer
> 2 votes
I can recommend the book *Computational Complexity Theory*, edited by Steven Rudich and Avi Wigderson, which is based on a graduate summer school by the IAS/Park city mathematics institute, with lectures by various experts in the field.

The purpose of this book is to provide the basics, some history and a glimpse into the research in some areas of computational complexity theory, aimed at mathematics students.

As such, this book is not a replacement for an introductory book such as Sisper's, but can be read independently to get a feeling what some sub-fields of complexity theory look like, and can help to guide a future focus.

For completeness, I'll list a summary of the table of contents as well (see this Google books preview for the full table):

```
Week One:
COMPLEXITY THEORY: FROM GÖDEL TO FEYNMAN

Steven Rudich, Complexity Theory: from Gödel to Feynmann
Avi Wigderson, Average case Complexity
Sanjeev Arora, Exploring Complexity through Reductions
Ran Raz, Quantum Computation

Week Two:
LOWER BOUNDS

Ran Raz, Circuit and Communication Complexity
Paul Beame, Proof Complexity

Week Three:
RANDOMNESS IN COMPUTATION

Oded Goldreich, Pseudorandomness - Part I
Luca Trevisan, Pseudorandomness - Part II
Sadil Vadhan, Probabilistic Proof Systems - Part I
Madhu Sudan, Probablistically Checkable Proofs

```

---
Tags: complexity-theory, books
---


# Question
Title: Why NAT is a disadvantage when TCP source port field is 16 bits?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:

My question is on the second paragraph. From what I understand, basically this part talks disadvantage of using NAT(Network Address Translation). I don't understand what second paragraph is trying to say about disadvantage of using NAT because it seems to me that the second paragraph is saying about benefit of using NAT because by using NAT, we can solve the problem of depletion of IP address.

Can anyone explain to me what the second paragraph is trying to convey?

# Answer
The practical limit to the number of hosts that can use a single NAT'd address is much less than 61,440. This is because even a modest Internet-capable computer will use many simultaneous TCP connections to hosts beyond the firewall. Each of these connections, while it is open or being negotiated open or closed, counts against that 61,440 figure. If each local host needs to reliably be able to initiate 200 external TCP connections at once, then that 61,440 value is reduced to only 307 hosts. This won't be a problem for a typical home network (yet), but a small business could easily reach this limit.

If the TCP source port size were larger, then that would offer a correspondingly larger number of address:port pairs for address translation to use, permitting many more hosts and connections from behind the firewall.
> 1 votes

---
Tags: computer-networks
---


title: Complexity of Integer Factorization

text:
# Question
Title: Complexity of Integer Factorization
In *Quantum Information and Quantum Computation* by Nielsen and Chuang, they define the complexity class **NP** as follows (page 142):

> A language $L$ is in **NP** if there is a turing machine $M$ with the following properties.
>
> 1. If $x\in L$ then there exists a witness string $w$ such that $M$ halts in the state $q\_Y$ ("yes state") after a time polynomial in $|x|$ when the machine is started in the state $x$-blank-$w$.
> 2. If $x \not \in L$ then for all strings $w$ which attempt to play the role of a witness, the machine halts in state $q\_N$ ("no state") after a time polynomial in $|x|$ when $M$ is started in the state $x$-blank-$w$.

This definition is motivated by the factoring decision problem, where they identify "witness strings" $w$ with possible factors of $x$.

My confusion is, based on how **NP** is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $x$, start the factoring turing machine $M$ in the state $x$-blank-$w$ for all $w \< x$, and check whether the machine ever halts in $q\_Y$. Since there are $O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $x$ has factors in polynomial time.

Clearly this shouldn't work, but I am unsure where the flaw in my logic is.

# Answer
The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in pseudo polynomial time.

Additionally, it seems that you are confusing factoring and primality testing. A possible decision version of factoring is given $(n,x)$ check whether $n$ has a factor $\le x$ (while your proposal refers to the case where only $n$ is given, and you loop to find a possible factor). While checking if a given number is prime is known to be in $P$, FACTORING is believed to lie outside of P.
> 5 votes

---
Tags: complexity-theory, turing-machines, time-complexity, decision-problem
---


title: Picking the most cost efficient sets

text:
# Question
Title: Picking the most cost efficient sets
I have two 2D arrays: $P\[n\]\[s\]$ and $C\[n\]\[s\]$, $s \leq n$.

P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P\[2\]\[2\]$ is $C\[2\]\[2\]$ and a set $p \in P = \\{ s\_0, s\_1, ..., s\_{n-1} \\}^q, q \leq n$, e.g. $p=\\{s\_0, s\_3\\}$.

For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $\\{s\_0, s\_1, ..., s\_{n-1} \\}$.

How do I find the least expensive picks in linear time?

# Answer
If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.

Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \\{S\_1, \dots, S\_m \\} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup\_{S\_i \in S'} S\_i = X$ and $|S'|$ is minimized.

This is exactly your problem once you set $n=|X|$, $s=1$, $P\[i\]\[1\] = S\_i$, and $C\[i\]\[1\]=1$.
> 1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Converting If-else integer equation to Linear Programming
I have an if-then-else condition with three binary variables A, B and C:

> `if A + B = 1 then C = 0`

How do I express this as an integer linear program with equality constraints?

# Answer
Your condition is effectively excluding $(0,1,1)$ and $(1,0,1)$ corners of the unit cube. Thinking of it pictorially gives you a quick formulation: (i) construct the cube, (ii) chop those corners off and (iii) ensure integrality.

In (ii), the corners we want to get rid of are on the $BC$ and $AC$ planes. We can cut from the correctly aligned diagonals on those planes. However, moving in $+A$ direction, the cut should shrink and vanish at $A=1$ to include $(1,1,1)$.

\begin{align\*} &\text{(i) } 0 \leq A,B,C \leq 1 \\ &\text{(ii) }-A+B+C \leq 1, A-B+C \leq 1 \\ &\text{(iii) }A,B,C \in \\{0,1\\} \end{align\*}
> 1 votes

---
Tags: linear-programming
---


# Question
Title: Minimum cost of "signal" cover in a tree with DP
I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ with $n$ being a node and $i$ being the signal strenght. The cost for each node may vary, the only assumption one can make is that $f(n, i) \geq f(n, j)$ for $i \> j$.

I need to find the minimum cost to cover the whole tree.

Example:

For $f(n, i) = (i + 1)^2$, the minimum cost would be 7:

Setting a signal with strenght 0 for every node covers the whole tree for the cost of 7. Setting a signal with strenght 1 for the nodes $b$ and $c$ covers the tree for the cost of 8 and setting a signal with strenght 2 for node $a$ results in a cost of 9.

Using Dynamic Programmming this task should be achieved in $O(n^2)$. This is an assignment so I'd be grateful for tips.

# Answer
> 1 votes
Let $T$ be your tree, and root it in an arbitrary vertex $r$. Given a vertex $v$, let $T\_v$ denote the subtree of $T$ rooted at $v$. For simplicity, let $f(0, v) = 0$.

For $i \ge 0$, define $D\[v,i\]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance smaller than $i$ from $v$ are always considered as covered. Intuitively this means that the signal "coming into $T\_v$" is strong enough to cover all vertices of $ T\_v$ at distance at most $i-1$ from $v$.

For $i \ge 0$, define $U\[v,i\]$ as the minimum cost needed to cover the subtree $T\_v$ rooted at $v$ with the constraint that the selected signal strengths should also be a feasible solution for the tree obtained by appending a path of $i$ vertices to $v$. Intuitively this means that the signal "outgoing from $T\_v$" is strong enough to cover all vertices of $T \setminus T\_v$ at distance at most $i$ from $v$.

Notice that, by definition, $D\[v,i\] = U\[v,i\]$.

If $v$ is a leaf of $T$, then $$ D\[v, i\] = \begin{cases} f(v, 0) & \mbox{if } i=0 \\ 0 & \mbox{if } i\>0 \\ \end{cases}, $$ and $$ U\[v, i\] = f(v, i). $$

If $v$ is not a leaf of $T$, then let $C\_v$ be the set of children of $v$. For $i=0, \dots, n-1$:

$$ U\[v, i\] = \min \begin{cases} U\[v, i+1\] & \mbox{only if $i \neq n-1$}\\ f(v,i) + \sum\_{u \in C\_v} D\[u, i\] \\ \min\_{z \in C\_v} \left\\{ U\[z, i+1\] + \sum\_{u \in C\_v \setminus {z}} D\[u, i\] \right\\} & \mbox{only if $i \neq n-1$} \end{cases}, $$

and, for $i=1,\dots,n$:

$$ D\[v, i\] = \min \begin{cases} D\[v, i-1\] \\ \sum\_{u \in C\_v} D\[u, i-1\] \end{cases} $$

You can then compute all values $U\[v, i\]$ and $D\[v,i\]$ where $v$s are considered in postoder w.r.t. $T$ and the order of subproblems for a fixed vertex $v$ is $U\[v,n-1\], \dots, U\[v,1\], U\[v,0\] = D\[v,0\], D\[v,1\], \dots, D\[v,n\]$.

As far as the computational complexity is concerned notice that there are $O(n^2)$ subproblems. The *overall* time needed to evaluate the second argument of the minimum of $U\[v,i\]$ and $D\[v,i\]$ is $O(n^2)$ since, for each value of $i$, computing $\sum\_{u \in C\_v} D\[u, i\]$ takes time proportional to $|C\_v|$ and $\sum\_v |C\_v| = O(n)$.

Suppose then that all the values $\sum\_{u \in C\_v} D\[u, i\]$ are known for free (since the time needed to compute them has already been accounted for). The *overall* time needed to evaluate the third argument of the minimum of $U\[v,i\]$ is again $O(n^2)$ since, for each value of $i$, $\sum\_{u \in C\_v \setminus {z}} D\[u, i\]$ can be found in time $O(1)$ by difference, and the inner minimum ranges over $|C\_v|$ elements. Once again $\sum\_v |C\_v| = O(n)$.

---
Tags: dynamic-programming, trees
---


# Question
Title: Solving linear system of nonhomogenous equations that are known to have natural solutions
Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 to 4 at most), but in exchange, there are a lot of equations (30-60).

The system is known to **always** have these properties:

* The equations are linear and nonhomogenous, coefficients and solutions are natural. In other words, equation $k$ has form $a\_{k1}x\_{k1}+a\_{k2}x\_{k2}+...+a\_{kn}x\_{kn}=b\_k$ where
    + $b\_k\in N$
    + $a\_{k1},a\_{k2},..,a\_{kn} \in N$
    + $x\_{k1},x\_{k2},..,x\_{kn} \in N$
* There is at least one non trivial solution.

Currently I am going with a bruteforce and heuristic approach that tries to narrow down the range I need to bruteforce before trying out all possible values but it can get messy pretty quick when I get a tricky system.

# Answer
You can represent the system as a matrix equation as $Ax = b$, where $k^{th}$ row of $A$ is the coefficients $\[a\_{k1},a\_{k2}...,a\_{kn}\]$, $x = \[x\_1, x\_2,...,x\_n\]$ and $b = \[b\_1,b\_2,...,b\_m\]$.

**Unique Solution:** If the system has a unique solution, you should be able to get $A$ into row-echelon form. Then, you'll find a row with only one non-zero coefficient, corresponding to an atomic expression like $x\_j = b\_k$. Plug this in by dropping the $j^{th}$ column and the $k^{th}$ row and updating all other rows as $b\_l' = b\_l - a\_{lj}b\_k$. Recursively keep doing this until all values are found. I finally remembered that the name of this procedure: Gaussian Elimination. Here is a nice concise description with a solved example.

**Underdetermined System:** If there are multiple solutions, then the number of linearly independent rows is less than the number of variables. Since you seem to have many more equations than variables, this is great news. Using the row-echelon form, you can weed out redundant equalities and end up with a much smaller system of equations.

Now, let $$z\_k = \min\_{\substack{1 \leq i \leq m \\ a\_{ki} \neq 0}}\left\\{\frac{b\_i}{a\_{ki}}\right\\},$$

so we get $1 \leq x\_k \leq z\_k$ as the feasible set for each variable. One way to shrink the brute-force approach is to order the variables by their upper bounds. If $z\_{k\_1} \geq z\_{k\_2} \geq ... \geq z\_{k\_n}$, suppose variables satisfy $x\_{k\_1} \geq x\_{k\_2} \geq ... \geq x\_{k\_n}$. Then, you can enumerate the solutions under this constraint by enumerating.

For example, let's say $z\_1 = 3, z\_2 = 2, ...$. Then, you would have $(3,2,..),...,(3,1,..),...,(2,2,..),...,(2,1,...),...,(1,1,...),...$.

With this ordering assumption you are searching over a much smaller set. Once you have that, you can check the permutations of these solutions and if they are feasible for all variables, they are valid solutions.

For example, for $x\_1 + x\_2 + x\_3 = 3$, let's say we break the tie as $x\_1 \geq x\_2 \geq x\_3$. Then, the constrained solutions are $(3,0,0), (2,1,0), (1,1,1)$ and the permutations of these give you the whole set since they are all the feasible due to $z\_1=z\_2=z\_3$.
> 0 votes

---
Tags: algorithms
---


# Question
Title: proving existence of TM that accepts the next language
I have an idea of how to approach the problem, but I'm not sure about it. Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run uses endless cells of the tape. However, I am not sure how I can use the number of states and what I should check. What confuses me is that entering an endless loop does not necessarily require the use of endless cells of the film.

$L\_k=\\{\<M\>| \\,M\\,\\,\\,is\\,\\,a\\,\\,TM\\,\\,that\\,\\,uses\\,\\,at\\,\\,most\\,\\,k\\,\\,tape\\,\\,cells\\,\\,\\,when\\,\\,\\,running\\,\\,\\,on\\,\\,\\,\epsilon\\}$

prove that: $L^\*=\bigcup\limits\_{k\\,\in\\,\mathbb{N}} L\_k\\,\in\\,\\,\\,RE\setminus R$

# Answer
The language $L^\*$ consists of all Turing machines $M$ which either eventually halt or repeat a configuration. For each machine $M$, by simulating the machine you can easily observe that one of these possibilities has happened.
> 1 votes

---
Tags: turing-machines, reductions
---


# Question
Title: How is expected value in entropy derived?
I was self learning about entropy and came across this equation. $$ H = - \sum p(x) \log p(x) $$

The equation for entropy in expected value, $$ H(x) = \operatorname\*{\mathbb{E}}\_{X \sim P}\[I(x)\] = -\operatorname\*{\mathbb{E}}\_{X \sim P}\[\log P(x)\]. $$

But the expected value is written as

$$ \mathbb{E}\[X\] = \sum\_{i=1}^k x\_i p\_i = x\_1p\_1 + x\_2p\_2 + \cdots + x\_k p\_k $$

Using the above expected value formula, I expected the entropy equation looks something like this

$$H(x)= -\operatorname\*{\mathbb{E}}\_{x \sim P(x)}\[\log P(x)\]= - \sum xP(x)\log P(x) $$

where is the $x$ gone in the real entropy formula in summation notation?

# Answer
Here is the definition of the expectation of a discrete random variable $Y$: $$ \mathbb{E}\[Y\] = -\sum\_y \Pr\[Y = y\] \cdot y. $$ In your case, $Y = \log P(X)$, where $X \sim P$. Therefore $$ \mathbb{E}\[X\] = \sum\_y \Pr\[\log P(X) = y\] \cdot y. $$ Notice that $$ \Pr\[-\log P(X) = y\] = \sum\_{x\colon \log P(x)=y} \Pr\[X = x\] \cdot y = \sum\_{x\colon \log P(x)=y} \Pr\[X = x\] \cdot \log P(x). $$ Therefore $$ \mathbb{E}\[X\] = \sum\_y \sum\_{x\colon \log P(x) = y} \Pr\[X = x\] \cdot \log P(x) = \sum\_x \Pr\[X = x\] \log P(x) = \sum\_x P(x) \log P(x). $$
> 2 votes

---
Tags: discrete-mathematics, information-theory, mathematical-foundations, entropy
---


# Question
Title: Language of lists of words, not all of which are different, is not context-free
How do I prove that the following language isn't context-free using the pumping lemma? $$ L=\\{w\_1\\#w\_2\\#\dots\\#w\_k \colon k ≥ 2, w\_i \in \\{0,1\\}^\*, w\_i = w\_j \text{ for some } i \ne j\\} $$

I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to approach this. If someone could please help me with this, I would appreciate it.

# Answer
If $L$ were context-free then so would $L' = d(L \cap (0+1)^\*\\#(0+1)^\*)$ be, where $d$ is the homomorphism that deletes $\\#$. However, $L'$ is the language of squares (words of the form $w^2$), which is well-known not to be context-free.

If for some reason you have to prove that $L$ is not context-free directly using the pumping lemma, this suggests looking at the proof that $L'$ is not context-free and trying to adapt it.
> 0 votes

---
Tags: formal-languages, context-free, proof-techniques, pumping-lemma
---


# Question
Title: Does the Hack computer from "The Elements of Computing Systems" use Von Neumann architecture?
I'm reading "The Elements of Computing Systems" (subtitled "Building a Modern Computer from First Principles - Nand to Tetris Companion) by Noam Nisan and Shimon Schocken.

Chapter 4 is about machine language, and more specifically the machine language used on their computer platform called Hack. Section 4.2.1 says this about Hack:

> The Hack computer is a von Neumann platform. It is a 16-bit machine, consisting of a CPU, two separate memory modules serving as instruction memory and data memory, and two memory-mapped I/O devices: a screen and a keyboard.
> … The Hack programmer is aware of two distinct address spaces: an instruction memory and a data memory. … The CPU can only execute programs that reside in the instruction memory. The instruction memory is a read-only device, and programs are loaded into it using some exogenous means.

With that distinction between instruction memory and data memory, is it really a von Neumann architecture? According to my understanding of the difference between von Neumann and Harvard, that description sounds much more like a Harvard architecture.

# Answer
> 3 votes
I had the same suspicion going through the Nand to Tetris course.

Indeed, if you look at John K. Bennett's annotated version of "The Elements of Computing Systems", specifically Chapter 5, he calls this out:

> The Hack architecture would more properly be called a “Harvard Architecture,” since the data and instruction memories are separate.

---

We can also do some digging for ourselves.

If we consult Wikipedia, it states that the Harvard architecture is distinguished by:

> The term "von Neumann architecture" has evolved to mean any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time because they share a common bus.
>
> The design of a von Neumann architecture machine is simpler than a Harvard architecture machine—which is also a stored-program system but has one dedicated set of address and data buses for reading and writing to memory, and another set of address and data buses to fetch instructions.

The latter is indeed the architecture of the Hack machine, which has two separate memories and can do an instruction lookup, data lookup, and computation all in one step\* of the CPU. You can see this in the book's diagram:

Last, this is also explicitly stated at the end of Chapter 5 of the original book:

> Unlike Hack, most general-purpose computers use a single address space for storing both data and instructions. In such architectures, the instruction address as well as the optional data address specified by the instruction must be fed into the same destination: the single address input of the shared address space. Clearly, this cannot be done at the same time.... In contrast, the Hack architecture is unique in that it partitions the address space into two separate parts, allowing a single-cycle fetch-execute logic.

\*Note: In the Hack machine language, it actually takes two steps (e.g. `@dataaddr` then `D = M + 1`) to do an operation on data in memory. However, during the second instruction, both the instruction and the data in memory can be read by the CPU simultaneously.

# Answer
> 0 votes
This is rather surprising.

If we look at the specification of the Hack Computer, I found this (consistent with your query):

***Instruction memory (ROM)***
***Data memory: Memory (RAM)***

Also, I've been studying Computer Architecture- MIPS-64 bit by Hennessy, which is based on von Neumann's, like most of the general-purpose computers in the mainstream. Harvard machines are generally specialty products. But there has been an increasing number of machines with Harvard-Neumann's Hybrid. These are the highlighted points which provides a reason:

* Split-cache (or almost-von-Neumann) architecture
* Instruction-memory-as-data architecture
* Data-memory-as-instruction architecture

So, it's fairly safe to assume the conundrum of The Hack being a von Neumann one.

---
Tags: terminology, computer-architecture
---


title: mapping reductions from R to RE

text:
# Question
Title: mapping reductions from R to RE
Let $L\_1$ be some language in $R$. Let $L\_2$ be some language in $RE$. Is it necessarily that $L\_1 \leq\_m L\_2$ ? I know that for non trivial $L\_1$,$L\_1$ in $R$ it is right to say that $L\_1 \leq\_m L\_2$. But I can't prove the first case.

and another question: I am almost certain that the following is true, though I have not found any reference to it on the Internet: The identity function is a mapping reduction from $\emptyset$ to $\emptyset$.

# Answer
> 2 votes
**If $L\_2 \neq \Sigma^\*$ and $L\_2 \neq \emptyset$ then $L\_1 \in R$ and $L\_2 \in RE$ implies $L\_1 \le\_m L\_2$.**

Let $T$ be a Turing machine that decides $L\_1$. Let $a,b \in \Sigma^\*$ such that $a \in L\_2$ and $b \not\in L\_2$. For $x \in \Sigma^\*$, define $\phi(x) = \begin{cases} a & \text{ if $T(x)$ accepts }\\ b & \text{ if $T(x)$ rejects } \end{cases}$. It is easy to check that $\phi$ is a mapping reduction from $L\_1$ to $L\_2$.

**If $L\_2 = \Sigma^\*$ then $L\_1 \in R$ and $L\_2 \in RE$ does not imply $L\_1 \le\_m L\_2$.**

This can be seen, e.g., by choosing $L\_1 = \emptyset$.

**If $L\_2 = \emptyset$ then $L\_1 \in R$ and $L\_2 \in RE$ does not imply $L\_1 \le\_m L\_2$.**

This can be seen, e.g., by choosing $L\_1 = \Sigma^\*$.

---
Tags: turing-machines, reductions
---


# Question
Title: Algoritm to sample an even subgraph of a graph
In some problems related to the Ising model in physics and mathematics the following problem comes up:

Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep all the vertices and some of the edges such that each vertex has even degree.There is always at least one since the empty spanning subgraph is always even. Now, among all the even spanning subgraphs of $G$ I want to sample one uniformly at random.

Is there an fast and preferably easy to implement algoritm to do that?

Is this a well studied problem? If yes: could you point me to some references?

Some background: The space of even spanning subgraphs of a graph has some nice structure since if you have two of them then you can take their symmetric difference and it will still be an even spanning subgraph. This means that it is a vector space of the field $\mathbb{F}\_2$ and you can pick a basis of that space - in particular this shows that the number of even spanning subgraphs is always a power of 2. I wonder how difficult it is to find the basis elements since if you have some you just flip coins for each and take the symmetric difference of all the graphs where you get head. Another point is that there might be a smart low-tech randomized way to do this.

# Answer
Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph.

Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v\_1,...,v\_n$, and given $i\>1$ let $P\_i$ be some simple path from $v\_1$ to $v\_i$ (such path exists since $G$ is connected).

Given $A\subseteq\\{2,..,n\\}$ and some spanning subgraph $H$, define $H^A$ to be the graph obtained from $H$ by flipping the edges in each $P\_i$ for $i\in A$, i.e. if $H$ is represented by $x\_H\in\mathbb{F}\_2^{|E|}$, and $P\_2,...,P\_n$ are represented by $x\_2,...,x\_n\in \mathbb{F}\_2^{|E|}$, then $H^A=x\_H\oplus\left(\bigoplus\limits\_{i\in A} x\_i\right)$. Note that for $A\neq B$ we have $H^A\neq H^B$. $H^A=H^B$ for some $A\neq B$ iff there exists nonempty $A\subseteq\\{2,...,n-1\\}$ such that $\bigoplus\limits\_{i\in A}x\_i=0$ (i.e. the vectors $x\_i$ are dependent). Suppose $i\in A$, and let $G\_A$ denote the spanning graph represented by $\bigoplus\limits\_{j\in A}P\_i$. Flipping the edges of any path $P\_j$ only changes the parity of the degrees of $v\_1$ and $v\_j$. Thus, as $G\_A$ is obtained by starting with the empty graph and flipping the edges of every $P\_j$ with $j\in A$, $deg\_{G\_A}(v\_i)$ is odd, which means $G\_A$ is not the empty graph.

Now we can define the following equivalence relation on subgraphs of $G$, $H\_1\sim H\_2\iff\exists A\subseteq\\{2,..,n\\}:H\_2=H\_1^A$. Based on the previous observation, each equivalence class contains $2^{n-1}$ different elements.

The second key observation is that each equivalence class contains a unique even subgraph of $G$. Given a subgraph $H$, for any vertex $v\_{i\>2}$ with odd $deg\_H(v\_i)$ flip the edges in $P\_i$. This only changes the parity of the degrees of $v\_1,v\_i$ in $H$. Proceed in this manner until $deg\_H(v\_2),...,deg\_H(v\_n)$ are all even. Since the sum of the degrees is always even, $deg\_H(v\_1)$ must now be even too, which means that the newly obtained equivalent graph $H'$ is an even spanning subgraph. For uniqueness, suppose for the purpose of contradiction that $H\sim H'$ are two different equivalent even spanning subgraphs of $G$, i.e. $H'=H^A$ for some non empty $A\subseteq\\{2,..,n\\}$. Let $i\in A$ be some path index in $A$, then clearly $deg\_{H'}(v\_i)$ is odd, since $deg\_{H}(v\_i)$ is even and its parity is only changed while flipping the edges of $P\_i$.

This was covered in the linked answered by Yly. Now you have a simple sampling algorithm that requires $O(|V|+|E|)$ preprocessing time. Execute BFS from $v\_1$ to obtain the paths $P\_2,...,P\_n$. Sample uniformly a spanning subgraph $H$, now for each $v\_i$ with odd $deg\_H(v\_i)$ flip the edges of $P\_i$. In this manner you find the unique even spanning subgraph in $\[H\]$, using $O(n^2)$ time. Uniformity follows from the fact that all equivalence classes have the same size, and each contains a unique even spanning subgraph.
> 1 votes

---
Tags: algorithms, reference-request, combinatorics
---


# Question
Title: Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept
Originally posted in Stack Overflow but was told to post here.

Context: I am doing a PCA on a $M \times N \\, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these values, so I need to remove all of them, which means I need to delete the whole corresponding row or column. Of course I want to keep the maximum amount of data. The invalid entries represent ~30% of data, but most of it is completely filled in a few lines, few of it is scattered in the rest of the matrix.

Some possible approaches:

* Similar to this problem, where I format my matrix such that valid data entries are equal to 1 and invalid entries to a huge negative number. However, all proposed solutions are of exponential complexity and my problem is simpler.
* Computing the ratio (invalid data / valid data) for each row or column, and deleting the highest ratio(s). Recompute the ratios for the sub-matrix and remove the highest(s) ratios. (not sure how many lines or columns we can remove safely in one step), and so on until there is no invalid data left. It seems like an okay solution, but I am unsure it always gives the optimal solution.

My guess is that it is a standard data analysis problem, but surprisingly I could not find a solution online.

# Answer
> 1 votes
Here is a solution based on back-tracking. You probably need to double check but it seemed ok on my side. Should take 1h on a 30x900 matrix, but you can use multi-threading in the bottom for loop to speed it up.

```
import numpy as np
from tqdm import tqdm

def hash_list(l1, l2):
    return str(sorted(l1)) + str(sorted(l2))  # could be faster

def max_matrix(a):
    # the process:
    # we construct list of rows and columns to select, which keep only valid values (a[rows, columns] = 1 everywhere)
    # at each step, for each other row/column, if it can be added in a valid way, we carry on deeper
    # when it's not possible to extend anymore
    # we backtrack to where we were and try to add the next possible row/column.
    # we store in res the visited valid rows/columns, which prevents most redundant computations
    res = {}
    M, N = a.shape

    def make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right'):
        assert len(sel_columns) + len(other_columns) == M
        assert len(sel_rows) + len(other_rows) == N
        h = hash_list(sel_columns, sel_rows) + d
        if h in res: # we went through this already
            return

        # attempting to add a column
        if d == 'right':
            for i in other_columns:
                if 0 not in a[i, sel_rows]:
                    # we can append it: let's try to go left or right from there
                    other_columns.remove(i)
                    sel_columns.append(i)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')

        # attempting to add a row
        else:
            for j in other_rows:
                if 0 not in a[sel_columns, j]:
                    # we can append it: let's try to go left or right from there
                    other_rows.remove(j)
                    sel_rows.append(j)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')

        # this position has been visited.
        res[h] = (sel_columns, sel_rows)

    # now launching from all possible first positions.
    for i in tqdm(range(M)):
        for j in range(N):
            if a[i, j] == 1:
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='right')
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='left')

    return res

if __name__ == '__main__':
    a = np.random.uniform(size=(30, 900))
    a[a > 0.3] = 1
    a[a <= 0.3] = 0
    a = a.astype(np.uint8)
    print(a)
    res = max_matrix(a)

    # just looking through the results to see the best configuration. (all valid configurations are stored btw)
    res_max = 0
    l1_max, l2_max = [], []

    for _, (l1, l2) in res.items():
        if len(l1) * len(l2) > res_max:
            res_max = len(l1) * len(l2)
            l1_max = l1
            l2_max = l2
    print(res_max, l1_max, l2_max)

```

---
Tags: algorithms, graphs, data-structures
---


title: Diameter of a disconnected graph

text:
# Question
Title: Diameter of a disconnected graph
Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?

# Answer
The distance $d\_G(u,v)$ between two disconnected vertices $u,v$ of a graph is usually defined as $+\infty$.

As a consequence the diameter of a disconnected graph $G=(V,E)$ is $$ \textrm{diam}(G) = \max\_{u,v \in V} d\_G(u,v) = + \infty. $$
> 6 votes

---
Tags: graphs, shortest-path, hamiltonian-path
---


# Question
Title: Find the number using binary search against one possible lie
We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.

But what if the interactor may lie to us in one case? For example, the number is $3$ and the maximum number we can guess is $10$, but when we ask whether it is *greater than* $5$ and it replies *yes* and for the rest of queries it answers correctly. A simple binary search would fail.

How to proceed in this case? What is the minimum number of query in the worst case?

# Answer
> 9 votes
A generalization of this class of problems is widely studied. See, e.g., this paper for a survey.

In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result.

There are other elegant ways to handle up to $k$ of lies by only using $O(\log n + k)$ time (where $k$ might be a function of $n$).

# Answer
> 7 votes
If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the truth, this happens only once.

I suspect you can do better. If the number is from 1 to 100 and I check the numbers 40 and 60 then knowing that *one* answer is true will give me *some* information.

More difficult if he can lie once, but can repeat the lie (so asking the same question ten times reveals nothing). For example if the number is from 1 to 100, and the liar insists that it is equal to 87 *and* equal to 88 (one is true, one is a repeated lie) you have no chance finding out what the number is.

# Answer
> 1 votes
If it was wrong one time, but right all of the other times **after** it, then we notice it will return you always the same thing after that wrong decision, **and** it would be the negation of them. In this example, it would mean that one time it said "above" and was wrong, but all of the other times after it, it would always answer "below".

Thus, you can just trace this back to the last time it "changed it's mind" and continue normal binary search

# Answer
> 1 votes
The key to this question is understanding that it is impossible to find out what the unknown number is *and that is all*. All you can find out is *both* what the unknown number is *and* which question was answered with a lie.

To take a concrete example, suppose that the number is between 1 and 10, and suppose that we **know** that one answer is a lie. We ask six questions. At the end, we will have distinguished between $10$ possibilities (which number it is) and also between $6$ possibilities (which question was answered falsely). $10\times 6=60$, and since $2^6=64$, six yes-or-no-questions will indeed have identified not only the number but also the false answer.

To be precise, the number $k$ of questions needed to distinguish between $n$ numbers, where one answer is definitely a lie, satisfies $$k\geq\log\_2n+\log\_2k$$

On the other hand, if there only *might* be a lying answer, then we have to allow for the "no lie" possibility, and the criterion is $$k\geq\log\_2n+\log\_2(k+1)$$

Can we achieve this bound, or do real algorithms need more? This depends on whether or not you are expected to ask all the questions before you receive any answers. If you aren't, then life is a little easier, and here is a sketch of how you would proceed in the case of $n=10$ and $k=6$.

**Question A** *Is the number 1, 2, 3, 4, or 5?* If the answer is Yes, then the possibilities are 1B, 1C, 1D, 1E, 1F, 2B, 2C, 2D, 2E, 2F, 3B, 3C, 3D, 3E, 3F, 4B, 4C, 4D, 4E, 4F, 5B, 5C, 5D, 5E, 5F, 6A, 7A, 8A, 9A and 10A, where the number denotes the value of the unknown number and the letter denotes which answer was a lie. There are 30 possibilities, so we have done a perfect binary chop on the original space of 60.

Supposing that the answer was Yes:

**Question B** *Is the number 1, 2, 3 or 10?* If the answer is Yes, then the possibilities are 1C, 1D, 1E, 1F, 2C, 2D, 2E, 2F, 3C, 3D, 3E, 3F, 4B, 5B, or 10A. There are 15 possibilities, so we have done a perfect binary chop on the previous space of 30.

If the answer to question A had been No, then question B would have been different (for instance, "1, 8, 9 or 10?").

Supposing that the answer to question B was also Yes.

**Question C** *Is the number 1 or 2?* If the answer is Yes, the possibilities are 1D, 1E, 1F, 2D, 2E, 2F, and 3C. That makes 7 for a Yes or 8 for a No, which is the closest to a bisection that we can get. Question D will therefore have to distinguish between either 7 or 8 possibilities.

The rest of this process is left as an exercise for the reader.

Note that the choice of each question does depend on the answers to the previous questions. If this is **not** what you want, then the field of error-correcting codes comes into its own, since an error-correcting code effectively transmits a whole batch of answers to a set predetermined questions, and the receiver's job is to deduce the value on the basis of those answers.

# Answer
> 1 votes
In this answer it's assumed there's at most 1 lie in the sense that if you ask the same question twice and get the same answer twice, you know for sure that it's not a lie.

Using the observation in Nir Shahar's answer, an algorithm can be constructed that performs at most $\lceil\log\_2{n}\rceil + 2\lceil\sqrt{\lceil\log\_2n\rceil}\rceil + 1$ (or slightly less) comparisons.

The observation is that when a binary search repeatedly made the same decision (say "bigger than" each time) during the last steps up to the current point, the lie can only be right before that, so at the last time it made the other decision (in that case "smaller than") (or the lie still has to come or the lie was the last decision). More generally while doing a normal binary search, if the lie has come already the lie was the last time the other decision was made than the last one (or the lie was the last decision).

fix a constant $c = \lfloor \sqrt{\lfloor \log\_2n\rfloor}\rfloor$ and let the search depth at each point be $d$.

Just perform the normal binary search until c the same decisions are made in a row (since the last time we made this same check). At this point, check if the decision at the last change was correct (that is, at depth $d-c$). If that was not a lie, we know there was no lie up to this point using only 1 extra comparison per $c$ steps. If it was a lie, we found the lie while doing less than about $\frac{log\_2 n} c + c \approx 2 \sqrt{\log\_2 n}$ extra comparisons.

I think this solution is optimal for 1 potential lie, but I'm not sure. A proof that no better solution exists would require a complex reasoning along the lines of https://cs.stackexchange.com/a/51499/28999

# Answer
> 1 votes
A similar problem, named "Black Hole", appears as one of the problems of 2019 Russian Olympiad of schoolchildren in computer science.

The problem asks for a program that interacts with a jury program simulating probe sensors and determines the radiation level of each black hole. The sensor mounted on the probe can answer the following queries: determine the x value by the value of x, whether it is true that the radiation level is greater than or equal to x. Unfortunately, due to a software error, the sensor response may not be correct. Fortunately, after the first incorrect answer, the sensor of this probe changes its state and gives only correct answers to all subsequent requests.

---

The following section is the solution to that problem given in the link provided by user my pronoun is monicareinstate. It is translated from Russian into English by Google.

---

Note that if we were given the same answer twice for the same request, this answer must be correct. Therefore, for subproblem 1 (n ≤ 1000, q ≤ 30), we can perform a regular binary search, repeating each query three times and believing that the answer is repeated twice. For subproblem 2 (n ⩽ 1000, q ⩽ 21), we note that the query should be repeated the third time only if the first two answers were different, and after that the answers to all the queries will be sure to be correct. Thus, the number of requests will be 3⌈log2 n⌉ and 2⌈log2 n⌉ + 1, respectively.

In all other subtasks, it is required to meet the minimum number of requests, sufficient for any strategy for responding to requests for a given n. The first few subtasks (n ⩽ 12 or n ⩽ 25) can be completed by enumerating possible strategies. As possible optimizations, one can set the enumeration state with a multiset of all received answers, and also use the fact that the number of allowed queries is small (no more than 9 for n ⩽ 25).

To obtain a polynomial-time solution, we note the following. Let us be told as answers that the answer belongs to prefixes of length p1 ⩽ p2 ⩽. . . and suffixes of length s1 ⩽ s2 ⩽. . .. Then the answer about the prefix of length p2 could not be wrong, since then the answer about the prefix of length p1 would also be incorrect; similarly, the answer about the suffix of length s2 is also exactly correct. Therefore, the search state can be uniquely defined by the numbers p1, p2, s1, s2. We will calculate the values ans p1, p2, s1, s2 - the required number of queries to guess the number in this state. The number x must belong to the union of the ranges \[n − s1 + 1, p2\] ∪ \[n − s2 + 1, p1\]; if the length of this union is 1, then the value is 0. Otherwise, for an arbitrary query? x we go into one of two states whose parameters are easily calculated (we denote these states by L (x) and R (x)); the optimal query x must minimize max (ansL (x), ansR (x). To calculate ans ... we use dynamic programming. In this solution, we have O (n4) states, in each of which O (n) transitions are possible, therefore the total difficulty is O (n5). Such a solution gains 30–35 points (in addition to 15 points for subtasks 1 and 2).

Consider several ways to optimize this solution:

• Let the prefix of length p1 and the suffix of length s1 do not intersect. This means that by this moment one of the answers was definitely incorrect, and in the remaining range of possible values you can use the usual binary search. We turn to more convenient notation for the case when this is not true: let b be the length of the intersection \[1, p1\] ∩ \[n - s1 + 1, n\], a = p1 - b, c = s1 - b.

• Note that the values of ans p1, p2, s1, s2 and ans p1 + d, p2 + d, s1 − d, s2 − d coincide, and the strategies for these states differ by shifting all requests to d. This allows you to set the state by numbers p2 - p1, p1 + s1, p2 + s1, and the complexity of the solution with this optimization is O (n4) (35–40 points).

• Note that in any state, the optimal number of requests after the response \<to the request? x does not decrease with increasing x; likewise, the number of requests after an answer\> = x does not increase. This means that the optimum max (ansL (x), ansR (x)) can be searched by binary search on x, which reduces complexity to O (n3log n) (along with the previous optimization 40–48 points).

• It is easy to show that, for example, with increasing c, the position of the optimal response does not decrease; this allows us to search for the optimal transition amortized over O (1). Together with previous optimizations, we get O (n3) complexity (55-60 points).

• Note that the response value is O (log n). We swap the value of the answer and one of the DP parameters: let maxc k, a, b be equal to the maximum value of c at which in state (a, b, c) it is possible to guess the number for k queries, or −∞ if this cannot be done either which c. Then the following transitions are possible:

* if maxc k − 1, a, b ̸ = −∞, then maxc k, a, b ⩾ maxc k − 1, a, b + 2k − 1 - b. Indeed, in the state (a, b, c + 2k − 1 - b), we make a query leading to the states (a, b, c) and (b, 0, 2k − 1 - b), in the second of them the usual bin search .
* if a ⩾ 2k − 1 - b, then, by a similar argument, maxck, a, b ⩾ maxc k − 1, a− (2k − 1 − b), b.
* let us make a query that breaks the middle part of length b into parts of length x and b - x, then the transitions are made to the states (a, x, b − x) and (x, b − x, c). Then if satisfied maxc k − 1, a, x ⩾ b - x, then maxc k, a, b ⩾ maxc k − 1, x, b − x. Together with all previous optimizations, we obtain the complexity O (n 2log n) (60–70 points, +15 for the first two subtasks).

In order to go through the remaining subtasks, you need to find the strategy locally and carefully save it in the program code. Let f (k) be equal to the maximum n at which one can guess the number in k queries. Note that the strategy for f (k) allows us to guess the number in k queries and for any smaller n. Then, to solve the problem, it is required to find strategies for f (1), f (2),. . . , f (maxk = 19) and maxn = 30,000.

For a specific k and n, the strategy can be represented as a decision tree of depth k. Such a tree can be obtained by local calculations on your computer, even if the solution does not fit in time in the testing system.

To prevent the tree from getting too large for large k, we note the following:

• tree vertices corresponding to the same search conditions can be saved only once.
• if we need to save several strategies at once, overlapping states between these strategies can also be saved only once.
• let b = 0 in any search state (that is, the smallest prefix and suffix do not intersect). Then we can use the usual bin search, and such a tree branch can obviously not be saved.

Using these optimizations, the jury's reference solution builds a compressed decision tree with \<2000 vertices. The constructed code takes 72 kilobytes, and the construction takes 3 minutes and uses \<6 gigabytes of memory.

XXXI All-Russian Olympiad of schoolchildren in computer science, final stage, all tasks Innopolis, April 11-17, 2019

---

If some symbols or statements in the above translation are not clear enough, the original text in Russian could help you decipher the meanings.

---
Tags: algorithms, dynamic-programming, binary-trees, information-theory, binary-search
---


# Question
Title: What does "If P1 is reduced to P2, then P2 is at least as hard as P1" mean?
I am having trouble understanding the following statement regarding Turing reduction:

> "If P1 is reduced to P2, then P2 is at least as hard as P1."

Does this mean that

(i) P2 can be harder or as hard as P1, or (ii) P2 can be easier or as hard as P1?

To represent this visually...

I would appreciate any insight on the matter. Thank you.

# Answer
> 1 votes
Interpretation (i) is correct: "$A$ is at least as hard as $B$" means that $A$ is as hard as or strictly harder than $B$. (Think about numbers: "$a$ is at least as big as $b$" means "$a=b$ or $a\>b$.")

Note that not only does "$A$ is at least as hard as $B$" rule out $A$ being strictly weaker than $B$, it also rules out $A$ and $B$ being of *incomparable complexity*. Complexity isn't a linear order; we can find problems such that neither helps us solve the other.

---
Tags: complexity-theory, reductions
---


# Question
Title: Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution
Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.

(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text while solving the recurrence and the statements are given as ordered list at the end. Simply because I want to master the text.)

> $$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$$

Now the authors attempt to first find a good guess of the recurrence relation using the recursion tree method and for that they allow sloppiness and assumes $T(n)=3T(n/4) + cn^2$.

Though the above recursion tree is not quite required for my question but I felt like including it to make the background a bit clearer.

The guessed candidate is $T(n)=O(n^2)$. Then the authors proof the same using the substitution method.

> In fact, if $O(n^2)$ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The ﬁrst recursive call contributes a cost of $\Theta(n^2)$ , and so $\Omega(n^2)$ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ We want to show that $T(n)\leq d n^2$ for some constant $d \> 0$.

Now there are a few things which I want to get clarified...

(1) *if $O(n^2)$ is indeed an upper bound for the recurrence*. Here the sentence means (probably) $\exists$ a function $f(n) \in O(n^2)$ such that $T(n)\in O(f(n))$

(2) *$\Omega(n^2)$ must be a lower bound for the recurrence* Here the sentence means probably $\exists$ a function $f(n) \in \Omega(n^2)$ such that $T(n)\in \Omega(f(n))$

(3) *$T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$* This sentence can be interpreted as follows assume that $T'(n) = 3T'(\lfloor n/4 \rfloor) + cn^2$ and $\exists$ a function $T(n) \in O(n^2)$ such that $T'(n)\in O(T(n))$

(4) *$T(n)\leq d n^2$ for some constant $d \> 0$* We are using induction to verify to the definition of Big Oh...

I feel that the author could simply have written the $T(n)$ is *Upper Bounded by $n^2$* and *Lower Bounded by $n^2$* or the author could have simply written $T(n) = O(n^2)$ and $T(n)=\Omega(n^2)$, did the author just use the above style of statements as pointed out in $(1),(2),(3)$ just for more clearer explanation or there are some extra meaning conveyed which I am missing out.

# Answer
1. "$O(n^2)$ is indeed an upper bound for the recurrence" means $T(n) \in O(n^2)$. That is, $\exists n\_0 \ge 1, c\>0, \forall n \ge n\_0, T(n) \le c n^2$.
2. "$\Omega(n^2)$ must be a lower bound for the recurrence" means $T(n) \in \Omega(n^2)$. That is $\exists n\_0 \ge 1, c\>0, \forall n \ge n\_0, T(n) \ge c n^2$.
3. This is exactly the same as 1).
4. Yes. In this step you use induction to show that $T(n) \le d n^2$ for some choice of a constant $d \> 0$.
> 1 votes

---
Tags: asymptotics, recurrence-relation, definitions
---


# Question
Title: Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time
I wonder what is the best data structure I can use in order to achieve the following:

Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ greatest values in $O(1)$.

I thought about maintaining another balanced BST and a variable containing the middle value, but I don't think it's a good idea, since the root of a balanced BST might not divide the tree into 2 halves so that the $\lfloor\frac{n}{2}\rfloor$ largest elements are to the right (the tree might be right heavy). Another idea was to use heap, but I don't see how it can help me.

Do you have any idea how to implement it? What do you think about mine?

# Answer
Maintain two BSTs $T\_1$ and $T\_2$ such that $T\_2$ always contains the largest $\lfloor n/2 \rfloor$ elements, and $T\_1$ contains the remaining elements.

Insertions and deletions can be implemented in $O(\log n)$ time by performing the corresponding operation in a suitably chosen tree and then moving at most one element from one tree to the other.

For example, to insert an element $x$ proceed as follows:

* Find maximum element $m$ of $T\_1$
* If $x \le m$:
    + Insert $x$ in $T\_1$
    + If $|T\_2| \neq \lfloor n/2 \rfloor$:
        - Delete $m$ from $T\_1$
        - Insert $m$ in $T\_2$
* Otherwise:
    + Insert $x$ in $T\_2$
    + If $|T\_2| \neq \lfloor n/2 \rfloor$:
        - Find the minimum element $m'$ of $T\_2$
        - Delete $m'$ from $T\_2$
        - Insert $m'$ in $T\_1$

Deletions are handled similarily.

The same approach also works if you maintain two heaps (a max-heap and a min-heap) instead of two BSTs.

See also this answer that uses a similar idea.
> 1 votes

---
Tags: data-structures, binary-search-trees
---


# Question
Title: Clarification of the proof involving the regularity condition in Master Theorem
I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem.

> (The Statement of Master theorem) Let $a \geqslant 1$ and $b \> 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be deﬁned on the nonnegative integers by the recurrence( the recursion divides a problem of size $n$ into $a$ problems of size $n/b$ each and takes $f(n)$ for the divide and combine)
>
> $T(n) = aT(n/b)+ f (n)$ ;
>
> where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:
>
> 1. If $f(n)=O (n^{\log\_ba - \epsilon})$ for some constant $\epsilon \> 0$, then $T(n)=\Theta (n^{\log\_ba})$.
> 2. If $f(n)=\Theta (n^{\log\_ba})$, then $T(n)=\Theta (n^{\log\_ba}\lg n)$
> 3. If $f(n)=\Omega (n^{\log\_ba + \epsilon})$ for some constant $\epsilon \> 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c \< 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

For $n$ as exact powers of $b$ we restrict the domain of T(n) as follows:

> $$T(n)= \Theta(1), n=1$$ $$T(n)=aT(n/b)+f(n) ,n=b^i$$

Now in the proof of Master's Theorem with *$n$ as exact power of $b$* the expression for $T(n)$ reduces to :

$$T(n)=\Theta(n^{\log\_ba})+\sum\_{j=0}^{\log\_bn -1} a^jf(n/b^j)$$

Then the authors assume the following,

$$g(n)=\sum\_{j=0}^{\log\_bn -1} a^jf(n/b^j)$$

Then for the proof of the 3rd case of the Master's Theorem the authors prove the following lemma,

> *Lemma 1* : If $a\cdot f(n/b)\leqslant c\cdot f(n)$ for some constant $c\<1$ and for all $n\geqslant b$ then $g(n)=\Theta(f(n))$

They say that:

*under their assumption that $c\<1$ and $n \geqslant b$*,they have $a \cdot f(n/b)\leqslant c \cdot f(n) \implies f(n/b)\leqslant (c/a) \cdot f(n)$

then **iterating $j$ times** yields, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$

I could not quite get the mathematics used behind **iterating $j$ times**.

Moreover I could not quite get the logic behind the assumption of $n\geqslant b$ for the situation that $n$ should be sufficiently large. (As the third case of the Master's Theorem says.)

The proof of the lemma continues as follows:

> > $$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n)$$ So, $$g(n)=\sum\_{j=0}^{\log\_bn -1} a^jf(n/b^j)$$ $$\leqslant \sum\_{j=0}^{\log\_bn -1} c^jf(n)$$ $$\leqslant f(n)\sum\_{j=0}^{\infty} c^j,$$ as $c\<1$ we have an infinite geometric series $$= f(n) \left(\frac{1}{1-c}\right)$$ $$=O(f(n))$$ as $c$ is a constant. (Note that $T(n)=\Omega(f(n))$ from the recursion diagram.)
>
> Then the authors proof the third case of the Masters Theorem for $n$ as exact power of $b$:
>
> > *Lemma 2*: Let $a \geqslant 1$ and $b\>1$, if $f(n)=\Omega (n^{\log\_ba + \epsilon})$ for some constant $\epsilon \> 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c \< 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.
>
> > So $$T(n) = \Theta(n^{\log\_ba}) + g(n) = \Theta(n^{\log\_ba}) + \Theta(f(n)) =\Theta(f(n))$$ as $f(n)=\Omega (n^{\log\_ba + \epsilon})$

Moreover in the similar proof for the third case of the general master theorem (not assuming $n$ as exact powers of $b$) there again the book assumes that $n\geqslant b+b/(b-1)$ to go with the situation of sufficiently large $n$.

**I do not quite understand what the specific value has to do and why such is assumed as sufficiently large $n$**

(I did not give the details of the second situation as I feel that it shall be something similar to the first situation but however it can be found here)

# Answer
> 2 votes
Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: the proof is just sloppy. You cannot assume that $f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n$ is a power of $b$.

They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for $n \ge b + b/(b-1)$. Using the idea of the proof of the special case where $n$ is a power of $b$, you can complete the proof of the general case. I would, however, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and you can trust the authors that it works out. Nothing interesting is hidden under the rug.

---
Tags: algorithm-analysis, proof-techniques, master-theorem
---


title: Lexicographic permutation

text:
# Question
Title: Lexicographic permutation
Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements **lexicographical** . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now consider this notation $Q(n,k)$ as position of number $k$ in **lexicographical** sorted permutation. $Q(11,2)=4$. We are given $k$ and $m$ we need to find minimum $n$ such that $Q(n,k)=m$ holds.

I could only find that $n\>=max(m,k)$ and for next i do not know how to solve it .

Source of question link

# Answer
> 0 votes
First, there is one special case of $k$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

* 1 is always at the 1st position.
* 10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
* 100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
* And so on.

We should process this peculiar case first.

The position of $k$ in the lexicographically sorted sequence is determined by the numbers that are before $k$ (lexicographically). These numbers fall into three categories.

* the numbers that are smaller than $k$. If a permutation of 1, 2, ..., $n$ contains $k$, it must contain all these numbers as well.
* $k$ itself.
* the numbers that are bigger than $k$.

Let us compute how many numbers before $k$ are smaller than $k$. For example, take k $=$ 619. Any number smaller than $k$ has at most three digits.

* All three-digit numbers before 619 constitute the interval \[100, 619).
* All two-digit numbers before 619 constitute the interval \[10, 61\].
* All one-digit numbers before 619 constitute the interval \[1, 6\].

In total, there are 519 + 52 + 6 $=$ 577 numbers that are smaller than 619 and before 619. So if $m\le$ 577 + 1, where 1 stands for 619 itself, no $n$ can satisfy $Q(n,\\,$619$)=m$. If $m=$ 578, the minimum $n$ is 619 itself.

Otherwise, the given $m$ is bigger than 1 plus the number of numbers smaller than $k$ and before $k$. We have to include numbers bigger than $k$ that are before $k$ to increase the position of $k$. For the same example, when $m\gt 578$, $n=$ 619 is not enough.

* Try adding the number between 1000 inclusive and 6190 exclusive.
* If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
* If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
* And so on.

---

---
Tags: algorithms, combinatorics, discrete-mathematics
---


# Question
Title: checking configuration history of Turing machine using PDA
I am trying to understand the technique of using configuration history in proofs.

To prove that: $\\{\<M\>|M\\,\\,\\,is\\,\\,\\,a\\,\\,\\,TM\\,\\,\\,and\\,\\,\\,L(M)=\sum^\* \\}\notin RE$

given $\<M,w\>$ we have built a Turing machine that accepts all words except M accepting configuration on w. (and then simple reduction)

To prove that: $\\{\<P\>|P is\\,\\,\\, a\\,\\,\\, PDA\\,\\,\\, and\\,\\,\\, L(P)=\sum^\*\\}\notin RE$

we showed the same proof, only that we built a PDA that accepts all the words except the accepting configuration of M on w.

Does PDA's ability to determine whether input is an accepting configuration of M on w actually means that I can simulate M's run on w with a PDA? Or testing whether configuration is an accepting configuration is different from a simulation

# Answer
PDAs are strictly weaker than TMs. For instance, PDAs always halt after precisely $|w|$ steps, but there are algorithms (aka TM) for questions that take more steps than that.

sorting an array for example, would take definitely more than $\Omega(|w|log(|w|))$ which is larger than $|w|$ at some point.

It cannot simulate running a machine on a word as it simply takes more time! Checking configuration history takes less time because it's length is proportional to the running time of $M$ on $w$.
> 1 votes

---
Tags: turing-machines, pushdown-automata
---


# Question
Title: How to estimate the complexity of sequential algorithm given that we know the complexity of each step?
First case: I was stumble upon a two step sequential algorithm where the big O complexity of each step is $O(N^9)$.

Second case: Also if the algorithm have three steps where the complexity of step 1 is $O(N^2)$, the complexity of step 2 is $O(N^3)$ and the complexity of step 3 is $O(N^9)$

What would be the complexity of the first case and second case ?

# Answer
> 1 votes
In the first case, we have $O(n^9)+O(n^9)$ and according to it's summation properties we have $O(n^9)+O(n^9)=O(2n^9)=O(n^9)$.

For the second case, both $n^2$ and $n^3$ are smaller than $n^9$, so we have $O(n^2)+O(n^3)+O(n^9)=O(n^2+n^3+n^9)\<O(n^9+n^9+n^9)=O(3n^9)=O(n^9)$

In the general case, if we have time complexities $t\_1,t\_2,...,t\_k$, then $O(t\_1)+...+O(t\_k)=O(max\\{t\_1,...,t\_k\\})$

---
Tags: time-complexity
---


# Question
Title: Issue with Campaign problem to find distinct valid campaigns
**Question:**

> An email campaign has a sequence of email messages where each email message belongs to one of two categories: transactional (and/or) marketing.
>
> Given the campaign size n and the gap length k, find the total number of distinct valid campaigns.

**My Approach:**

My initial thoughts were around generating all the valid permutations for each scenario and then counting it. However, I am not sure if that's the way to go!

I would appreciate any insights.

# Answer
Let $DP\[i\]$ be the number of distinct valid campaigns whose **last** marketing email is the $i$-th email, $i$ from $1$ to $n$. As an extension, let $DP\[0\]=1$, which is the number of distinct valid campaigns without marketing emails.

---

For all $i\le k+1$, it is clear that the only valid campaign whose last marketing email is the $i$-th email is the campaign that has no marketing email other than the $i$-th email. That is, $$DP\[i\]= 1\quad\color{#d0d0d0}{\text{ for all }i\le k+1.}$$

For all $i\gt k+1$,

* Consider a valid campaign $\mathcal C$, whose last marketing email is the $i$-th email. If the last marketing email of $\mathcal C$ is changed to a transactional email, $\mathcal C$ will become another valid campaign, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails.
* Conversely, consider a valid campaign $\mathcal D$, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails. If we change the $i$ email of $\mathcal D$ to a marketing email, $\mathcal D$ will still be a valid campaign, whose last marketing email is the $i$-th email.

So, we have

$$DP\[i\]= DP\[0\] + DP\[1\] + \cdots + DP\[i-k-1\]\quad\color{#d0d0d0}{\text{ for all }i\>k+1.}$$

The number of all distinct valid campaigns is $$DP\[0\] + DP\[1\] + \cdots + DP\[n\].$$

If we implement the above approach to compute the array $DP$ iteratively, we can get an algorithm that runs in $O((n-k)^2)$ time and $O(n)$ space.

---

The algorithm above runs in time that is quadratic of $n$ when $k$ is not near $n$. It might not be fast enough when $n$ is large.

Let us do better. Since

$$DP\[i+1\]= DP\[0\] + DP\[1\] + \cdots + DP\[i-k-1\] + DP\[i-k\],$$

we have the following simpler recurrence relation,

$$DP\[i+1\]= DP\[i\] + DP\[i-k\]$$

for all $i\ge k+1$. Now we can write an algorithm that runs in $O(n)$ time and $O(k)$ space.

---

Here is a sample implementation in Python. For simplicity, $O(n)$ space is used.

```
def ways(n, k):
    dp = [1] * (n + 1)

    for i in range(k + 1, n):
        dp[i + 1] = dp[i] + dp[i - k]

    print(dp)  # for educational purpose.
    return sum(dp)

def test():
    print(5, 0, ways(5, 0))
    print(5, 1, ways(5, 1))
    print(5, 2, ways(5, 2))
    print(5, 3, ways(5, 3))
    print(5, 4, ways(5, 4))
    print(5, 5, ways(5, 5))

test()

```
> 1 votes

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


# Question
Title: Computability of Kolmogorov Complexity of Turing-Incomplete language
I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows:

$A;B \text{ - executes instructions A and B one after the other.}$
$!x\_i! \text{ - sets variable } x\_i \text{ to the value }2.$
$\\{x\_i\\} \text{ - doubles the value of the variable }x\_i$
$\[x\_i\] \text{ - halves the value of the variable } x\_i \text{ and rounds it up.}$
$"w" \text{ - prints the string } w \in \\{a,b,...,z,A,B...,Z\\}$
$\lambda(x\_i,A) \text{ - executes instruction } A \text{ exactly } x\_i \text{ times, regardless of later changes to } x\_i$

Specifically, I need to know whether the Kolmogorov Complexity relative to this language is generally computable. The program which computes this complexity may be written in a Turing-Complete language.

I understand that for any Turing-Complete language, the Kolmogorov complexity is not computable. This language here does lack the ability to create an infinte loop, though, and as such is less than Turing-complete. I am not feeling any intuition arising from this observation though. I'd assume that, this language being weaker, the Kolmogorov complexity may be computable now. Yet I can not find a proof for this. Giving an algorithm that fulfills this task appears overly complicated. The use of this language seems like a special case of the more general computability of the Kolmogorov complexity and as such, I can't derive from the attributes of the general case if the general case is not computable. This may still be.

I am not finding any ground to stand on with this problem and would welcome any tips and pointers towards a solution. Can we deduce anything else from this language than what I have mentioned so far? Does it's lower power relative to Turing-complete languages help us with this situation?

# Answer
The important thing to notice is that your programs always halt. This makes computing the Kolmogorov complexity an easy task, since given a string $w$, you can go over all possible programs of length $\le|w|+2$ to find the shortest program whose output is $w$. The upper bound $|w|+2$ follows from the fact that for any string $w$, "w" is a program whose output is $w$.

In fact, you could probably compute the complexity of a string in polynomial time, since compression is only possible in the case of repetitions (you can not take advantage of a more general structure). Something along the following lines should work $KC(w\_1...w\_n)=\min\limits\_i \big(KC\left(w\_{i+1}...w\_n|w\_i\right) +KC(w\_1...w\_i)\big)$, where $KC\left(w|w'\right)$ is just $KC(w)$ if $w'$ is not a prefix of $w$, and $KC(w'')+O(\log j)$ otherwise where $w=w'^jw''$ and $j$ is the maximal number satisfying this. The point is that you only need to compute the complexity of substrings of $w$, of which there are $O(|w|^2)$.
> 2 votes

---
Tags: computability, kolmogorov-complexity
---


title: Time complexity of addition

text:
# Question
Title: Time complexity of addition
Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits.

Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known algorithm. I want to know, because the complexity of addition, underscores all other arithmetic operations and all algorithms which use them.

Is it theoretically impossible, to get an addition algorithm that runs in $o(n)$? Or are we bound to linear complexity for addition.

# Answer
> 20 votes
If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (stored for example in 8MB text files). Of course, addition can be done very quickly compared to the *value* of the numbers; it runs in $\mathcal{O}(\log(N))$ time, if $N$ is the value of the sum.

This does not mean you can speed things up a little; if your processor handles 32 bits each operation, then you use $\frac{n}{32}$ time, but that is still $\mathcal{O}(n)$ and not $o(n)$.

# Answer
> 7 votes
In order for complexity analysis to make any formal sense at all, you have to specify a formal computational model within which the algorithm in object is being executed, or, at the very least, a *cost model*, which specifies what the basic operations are and their costs.

In most contexts, arithmetic operations are assumed to take $\Theta(1)$ time. This is usually reasonable, as we are interested in algorithmic complexity irrespectively of the numbers involved. This is called the *uniform cost model*.

If numbers can grow unbounded, or we are interested in analyzing the operations themselves, arithmetic operations are taken to have cost $\Theta(|x|)$, proportional to the size of input.

Now, can operations have a cost that's less than that? Possibly, however you'll have to formally define a computational model in which it can happen.

# Answer
> 5 votes
The input to addition is two *arbitrary* numbers. Since they are arbitrary, you must read each bit, and therefore the algorithm is $\Omega(n)$.

Imagine your algorithm successfully adds 1010100110 and 0010010110 without reading each bit. In order for you algorithm to be able to add *arbitrary* inputs, I should be able to randomly flip any one of these bits, and the algorithm still output a correct (but different) addition. But if your algorithm doesn't read every bit, how could it tell that the flipped input was any different than the original input?

# Answer
> 4 votes
When the time complexity of a computation such as adding two $\lg n$-bit numbers $x$ and $y$ is considered, it is often assumed that the bits in $x$ and $y$ are available all at once unless the algorithm in question is bit-serial and bits of $x$ and $y$ arrive over time. So, while it is true that every bit counts and we can't ignore any given bit, one doesn't need to spend $O(\lg n)$ time to wait for bits of $x$ and $y$ to arrive before the computation begins or in-between the successive bit additions. With this convention in place, $x$ and $y$ can be added using a Brent-Kung prefix adder in $O(\lg\lg n)$ time complexity using constant fan-in and constant-fan-out gates. Brent-Kung uses a particular prefix gate with two inputs and two outputs and $O(1)$ gate delay to achieve this time complexity.

One other point is that time and space complexities of an algorithm or computation cannot not be expressed in terms of implementation specific figures such as address or data bus widths, RAM or register size (number of bits, bytes, words), clock rates, etc of a particular physical system made out of a constant number of components. Such complexities involve variables such as $n,\lg n,$ etc, whereas an implementation of an algorithm on a specific piece of hardware or system can be determined down to a nanosecond if all system and component time and space values are accurately predictable. As far as time and space complexities are concerned, all physical systems built out of a constant number of components have $O(1)$ time and $O(1)$ space complexity.

The classic references on this sort of question are:

(1) Winograd, Shmuel. "On the time required to perform addition." Journal of the ACM (JACM) 12.2 (1965): 277-285.

(2) Brent, Richard P., and Hsiang T. Kung. "A regular layout for parallel adders." IEEE transactions on Computers 3 (1982): 260-264.

The $O(\lg \lg n)$ time complexity of B-K prefix adder is consistent with Winograd's lower bound given in \[1\].

# Answer
> 0 votes
To extend on other answers: When we are interested in average-case time complexity, it is possible to get an addition algorithm that adds in $\log n$ steps in the average case (assuming certain bitwise operations are $O(1)$), see \[1\] and \[2\]. And modern computer architectures add in parallel, so the number of steps to add two $n$-bit numbers using a hardware adder is almost always better than $O(n)$, assuming we have polynomially many processors; see AYO's answer, for example.

\[1\]: Richard Beigel, William Gasarch, Ming Li, and Louxin Zhang. "Addition in $\log\_2 n+O(1)$ Steps on Average: A Simple Analysis"

\[2\]: G. Schay, "How to add fast–on average". American Mathematical Monthly, 102:8 (1995), 725-730.

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


title: Predicitve Parser LL(1) condition

text:
# Question
Title: Predicitve Parser LL(1) condition
Lets say we use the predictive parser LL(1). Why is it necessary that

$FIRST(\alpha) \cap FIRST(\beta) = \emptyset$,

for all $\alpha, \beta$ right side of alternative productions i.e., productions associated to the same non-terminal. Why is this condition necessary?

# Answer
> 1 votes
Here's an intuitive explanation:

It follows essentially from the nature of LL(1) parsers: LL(1) parsers build a LL(1) parsing table. The rows of the table are nonterminals, and the columns are terminals. We can think about LL(1) parsing as doing LL(1) table lookups upon encountering each symbol in the input: we look at the entry determined by the current nonterminal and the input terminal, and apply a corresponding production rule. Thus, the LL(1) table cannot contain multiple production rules at each entry, otherwise, the parser cannot decide which rule to apply.

If the right hand side of a production $\alpha$, $\beta$ have intersecting FIRST sets, then we'd have multiple rules at a single entry in the LL(1) table (i.e. duplicate/conflicting entries) --- having nontrivial intersection of FIRST sets essentially prevents us from constructing the LL(1) parsing table.

*If you're still unclear about why this condition is necessary*, I suggest you construct an example with intersecting FIRST sets on the right hand side of a production, and then try to manually construct an LL(1) parsing table or use one of the online visualization tools; you'll immediately find a conflict.

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


# Question
Title: Is this push-down automaton non-deterministic, as JFLAP states?
There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.

In this example it is detecting non-determinism in state `q0`:

The first symbol in the transition represents the symbol read as input; the second symbol represents the symbol extracted from the stack; and the third symbol is the symbol pushed to the stack. λ represents the empty symbol, so this is an empty transition without checking the stack or pushing anything to it.

I am surprised, as that state seems to fulfill the conditions for determinism for push-down automatons (if only because it only contains a single transition!). I would expect the next state to be `q1` under any circumstance.

In comparison, JFLAP doesn't find any non-determinism here:

Mind you, the transition is the same, it only changes that this one adds something to the stack. Am I missing something or is JFLAP wrong in the first instance?

# Answer
> 1 votes
All deterministic push-down automatons are also nondeterministic push-down automatons, so it is correct to say that your automaton is nondeterministic.

That said you are correct in saying that your first push-down automaton is **also** deterministic, according to the definition on Wikipedia.

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


# Question
Title: Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem
I recently came across the sentence in the Book Introduction to Algorithms section **4.1** The maximum sub-array problem:

> We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days.

Here $n$ is the number of days taken as an example to show the changes in price of stock.

We can consider this is the size of an array A.

Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

> To explain more specifically it means for an array $A$ of size $n$ we need to check $\binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $\binom{n-1}{2}$ sub-arrays?

If we take an array of size **5** could someone please explain to me why we need only **6** sub-arrays. Won't the sub-arrays be:

```
[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]

[3...5]
[4...5]

```

Please correct me if I am wrong. References: Maximum Subarray Problem

Thank you.

# Answer
> 2 votes
You have found a bug in one of the most famous textbooks on computer science!

---

While there are $n$ days, there are only $n-1$ changes in price of stock. So there are $\binom{n-1}{2}$ subarrays of the array of the changes in price of stock, assuming that a subarray starts and ends at different indices.

That explain away, I believe, why the books says "we still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days".

---

However, in fact, you are right that we still need to check $\binom n2$ subarrays.

Let $B$ be the array of the daily prices for a period of $n$, starting at index (day) 0. Let $A$, as in the book, be the corresponding array of the price changes, starting at index (day) 1. If you select to buy on day $i$ and sell on day $j$, making a profit of $B\[j\]-B\[i\]$, it corresponds to subarray $A\[i+1\\,..\\,j\]$, i.e., $(A\[i+1\], A\[i+2\], \cdots, A\[j\])$. Please note the change of indices from $i$ and $j$ in $B$ to indices $i+1$ and $j$ in $A$. While $i$ and $j$ must be different always as "you are allowed to buy one unit of stock only one time and then sell it at a later date", $i+1$ and $j$ are the same when $j=i+1$, i.e., when you sell the next day.

Let us verify the sum of selected numbers in $A$ is indeed $B\[j\]-B\[i\]$. $$\begin{aligned} &\quad A\[i+1\]+A\[i+2\]+\cdot+A\[j\]\\ &=(B\[i+1\]-B\[j\])+(B\[i+2\]-B\[i+1\])+\cdot+(B\[j\]-B\[j-1\])\\ &=B\[j\]-B\[i\].\end{aligned}$$ Note the formula does hold when $j=i+1$.

Besides the subarrays of $A$ that start and end at different indices, we must consider the subarrays with the same starting index and ending index. There are $n-1$ of them, i.e., the subarray whose only element is $A\[1\]$, the subarray whose only element is $A\[2\]$, ... and the subarray whose only element is $A\[n-1\]$. Since $\binom{n-1}2+(n-1)=\binom n2$, we still need to check $\binom n2$ subarrays.

For example, if the daily prices for a period of $3$ days are $B=(85, 105, 102)$, the changes of prices are $A=(20, -3)$. If we do not check the subarray of $A$, $(20)$, which stands for buying at price $85$ on day $0$ and selling at price $105$ on day $1$, we will miss the optimal profit, $20$.

---

This simple and obvious bug is not listed on the errata page for *Introduction to Algorithms*, *Third Edition*. It is incredible that this bug has been living comfortably in that popular book for over ten years before you pointed out explicitly.

On the other hand, many people might have been aware of that bug, although I did not notice it. The focus of that mistaken statement is "we still need to check $\Theta(n^2)$ subarrays for a period of $n$ days". The actual number of subarrays that should be checked is not that critical, as long as its level of asymptotic growth is correct. While misleading otherwise, that bug does not harm much the development of a better algorithm.

---
Tags: algorithms, divide-and-conquer, maximum-subarray
---


# Question
Title: How did MacLisp's garbage collector "run in the register set"?
Olin Shivers, ‘History of T’:

> Maclisp on the \[PDP\]-10 had used a mark&sweep GC (one version of which famously "ran in the register set," though that is another story)

This implies, in my interpretation, that the garbage collector used no storage other than the registers of the machine. Is my understanding of this correct, and if so, how did it achieve this efficiently? Was a paper ever published on its implementation?

# Answer
The 16 high-speed registers of the PDP-10 ISA were addressible as locations 0-15 of physical memory, so that the code *literally* could run in the registers if it was short enough and you could devote a block of registers to it. Not only could it use registers for temporary storage, it could use them as a code cache as well.
> 1 votes

---
Tags: programming-languages, memory-management, garbage-collection, lisp
---


# Question
Title: What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?
The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?

# Answer
> 1 votes
> Is there a way to find the upper bound on the total number of nodes in the tree?

Yes. There is actually a formula for the exact number: see e.g. these notes:

> A full $m$-ary tree with $l$ leaves has $n = \frac{ml - 1}{m - 1}$ vertices and $i = \frac{l-1}{m-1}$ internal vertices.

Here, **$m$-ary** means that every internal node has between $1$ and $m$ children, and **full** means that every internal node has exactly $m$ children (the maximum). So in your case, for a full binary tree, just plug in $m = 2$ to these formulas.

---

By the way, to derive such formulas, you can count the number of vertices in the tree in two ways. First, they are either internal or leaves, so $$ n = i + l $$ Second, we can obtain the total number of vertices by adding up the number of children over all nodes, plus the root, so $$ n = 1 + \sum\_{v \in V} \text{children}(v) = 1 + mi, $$ because each internal node has $m$ children and leaves have no children. Now set the two equal and we have $$ i + l = 1 + mi, $$ from which we can derive the above results.

---
Tags: trees
---


title: An independent d-division

text:
# Question
Title: An independent d-division
I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):

Let $G = (V,E)$ an undirected graph whose vertices $V = \\{v\_1,\dots,v\_n\\}$ appear in this order on the real line (meaning forall $1 \leq i \< j \leq n$, $v\_i$ appears before $v\_j$).

A *$d$-divison* of $G$'s vertices is a division into $d$ different intervals, meaning the choice of $d-1$ indices $1 \leq i\_1 \< i\_2 \< \dots \< i\_{d-1} \< n$ which define the intervals: $$ \[v\_1,\dots,v\_{i\_1}\], \[v\_{i\_1+1},\dots,v\_{i\_2}\],\dots,\[v\_{i\_{d-1}+1},\dots,v\_n\]. $$

A $d$-division is called *independent* if there are no two neighboring vertices in the same interval. Meaning, the division is independent if forall $0 \leq r \< d$ and forall $i\_r \< j\_1 \< j\_2 \leq i\_{r+1}$ we have $\\{v\_{j\_1},v\_{j\_2}\\} \notin E$, where $i\_0 = 0$ and $i\_d = n$.

Offer an algorithm with time complexity $O(V+E)$ that finds an independent $d$-division of $G$ such that $d$ is minimal. Prove the correctness of the algorithm.

Notice: The division in this exercise is "continuous". For instance, if $v\_1$ and $v\_3$ are on the same interval, then $v\_2$ is on the same interval with them. Also, there are no edges between any two vertices in the same interval. For instance, if the first interval in the division is $\[v\_1,v\_2,v\_3\]$, then $\\{v\_1,v\_2\\},\\{v\_2,v\_3\\},\\{v\_3,v\_1\\} \notin E$.

Thanks a lot,

# Answer
Think about what happens when you manage to find the first interval, say it is $\[v\_1,...,v\_k\]$ for some $k$. Then what would you be able to say about the minimal division of $v\_{k+1},...,v\_n?$

Think also about how you could find the first interval. Starting from an empty interval and expanding it (how?) should do the trick.
> 0 votes

---
Tags: greedy-algorithms
---


# Question
Title: What are the known ambiguities in C language grammar?
I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we can modify the BNF grammar to avoid those ambiguities, including the known one mentioned above?

# Answer
> 3 votes
Not sure if this answers your question, but I will contribute two details regarding lexing/parsing ambiguities in C in general. I hope these are still helpful.

Consider the expression `T ** c;`. Since C supports type declarations via `typedef`, the parser itself cannot decide whether this is multiplication with variables `T` and `*c` or a variable declaration of a pointer to pointer `c` of type `T**`. We'll need information fed into the parser by the lexer to decide which situation we're parsing (the lexer will resolve each valid type name to a type).

Another situation similar to the situation above gives rise to an ambiguity in the C syntax: In general, statements like `a +++ b` are ambiguous, since both `(a++) + b` and `a + (++b)` are valid. In this kind of situation, the C compiler follows the "longest match" rule: the compiler will match against the *longest* sequence of characters it can match.

---
Tags: context-free, formal-grammars, c, syntax, syntax-trees
---


# Question
Title: Euclidean geometry theorem proving complexity
Euclidean geometry is complete, so the problem of determining whether a statement $A$ is provable is computable. Do we know its time complexity?

# Answer
> 3 votes
It is common to prove the decidability of first-order Euclidean geometry by encoding the language of Euclidean geometry into the language of real closed fields and then showing that the latter is decidable. A singly-exponential space upper bound on deciding the first-order theory of real closed fields was proven in Ben-Or, Kozen, and Reif (1986). This implies a doubly-exponential time upper bound.

I believe this is the best known complexity for the decision problem for general first-order sentences in the language of real closed fields. However, I am not sure whether deciding real closed fields is *equivalent* (bidirectionally) to deciding Euclidean geometry, since a typical encoding of (say) the language of Tarski's axioms into the language of real closed fields only uses a small subset of the possible polynomials. So maybe first-order Euclidean geometry can be decided with lower complexity than this. It is at least PSPACE-hard, since TQBF is easily encoded into first-order Euclidean geometry.

---
Tags: time-complexity, computational-geometry
---


# Question
Title: Greedy sequential/parallel task scheduling
We have `N` tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task `i` we know how much time it needs to spend in each part, namely mi for the guarded part, and ai for the part that can be executed in parallel.

The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.

My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending ai order.

For example given the tasks with:
m1 = 3, a1 = 9
m2 = 2, a2 = 7
m3 = 6, a3 = 10

The optimal solution is the permutation 3, 1, 2.

However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?

# Answer
I have a pretty messy proof. I'm sure this can be cleaned up with a bit of work. Let me know if you need me to simplify the proof.

For the sake of the proof, lets rearrange all the terms such that $a\_1 \geq a\_2 \geq a\_3 \ldots$. Let $f(1), f(2), \ldots, f(N)$ be some schedule. The total time spent for any schedule $f$ is given by the following. $$T(f) = \max \\{m\_{f(1)} + a\_{f(1)}, m\_{f(1)} + m\_{f(2)} + a\_{f(2)},\ldots, \sum\_{i = 1}^N m\_{f(i)} + a\_{f(N)} \\}$$.

For the sake of contradiction, suppose that your greedy method is not the optimal solution. There exists some schedule $\phi$ such that $T(Id) \> T(\phi)$ (here $Id$ is the identity). Choose $k$ such that $\sum\_{i = 1}^k m\_{i} + a\_k = T(Id)$. Let $h$ be the smallest number such that $\\{1,\ldots, k\\} \subset \\{\phi(1), \ldots, \phi(h)\\}$. Note that $\phi(h) \leq k$. Because $\\{1,\ldots, k\\} \subset \\{\phi(1), \ldots, \phi(h)\\}$, $\sum\_{i = 1}^h m\_{\phi(i)} \geq \sum\_{i = 1}^k m\_i$. Because $a\_1 \geq a\_2 \geq \ldots$, we know that $a\_{\phi(h)} \geq a\_k$. This means that $$\sum\_{i = 1}^k m\_i + a\_k \leq\sum\_{i = 1}^h m\_{\phi(i)} + a\_{\phi(h)}$$ But $T(Id) = \sum\_{i = 1}^k m\_i + a\_k \leq \sum\_{i = 1}^h m\_{\phi(i)} + a\_{\phi(h)} \leq T(\phi)$. This is a contradiction.
> 2 votes

---
Tags: greedy-algorithms, scheduling, permutations
---


# Question
Title: Complexity of enumeration vs complexity of counting
I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm.

Now, I have problem with the following. Let say that we have to count the number of positive integers less or equal than positive integer $N$. We know that the answer is $N$ and therefore we can solve the counting problem in $\mathcal{O}(1)$. Corresponding enumeration problem is to output every positive number and this can be done in $\mathcal{O}(N)$ steps and I believe that this is pseudo-polynomial complexity and that in fact complexity is exponential.

Are these complexity assumptions correct? Is the number of solutions of counting problem always bounded by the time complexity of corresponding enumeration algorithm?

Any hints or suggestions appreciated.

# Answer
Yes. An enumeration algorithm executes at least 1 step (an instruction, line of code, or whatever else your metric is) for every instance it finds, so there's at least as many steps as there are instances to count.

Just remember that if you use an asymptotic time complexity like $O(N)$, it doesn't tell you enough for an exact bound on the count. For example, it takes $O(N)$ time to enumerate $1,\dots,2N$.
> 2 votes

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


# Question
Title: Is the complement of this decision problem in $P$?
*Are there any two primes that are **NOT** a factor of $M$ that multiply up to $M$?*

**Fact:** Any two primes that multiply up to $M$. Must be factors of $M$!

Thus because of the fact above an $O(1)$ algorithm exists. It always outputs $NO$

## Complement

*Are there any two primes that are a factor of $M$ that multiply up to $M$?*

**Fact:** A complement of a decision problem does not always require to always return $YES$ or $NO$. It can be either one!

(eg. $M$ = 6 and two primes that multiply up to $M$ are $3$,$2$.)

Well, this I find interesting this is deciding $Semi-Primes$.

## Question

Shouldn't $Semi-Primes$ be in $P$, because what was shown above?

# Answer
Careful how you come up with a complement. The original problem asks to satisfy the following, given M: $$\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ As you say, the answer is always NO.

The complement of the problem should by definition have the opposite answer (YES) for ever $M$. To see why that's the case, negate the original problem (carefully): $$\neg\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ Distributing through the $\exists$ gives: $$\forall p,q: \neg((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ And distributing again makes this pretty trivial: $$\forall p,q: ((p\text{ or } q \text{ is not prime})\lor (p\mid M)\lor (q\mid M) \lor (pq\ne M))$$ So the complement is really asking: *Given $M$, is it true that every pair of numbers $p$ and $q$ either has a non-prime or a divisor of $M$ or they don't multiply to $M$?* It's a bit strange to claim this, but it's always true.
> 1 votes

---
Tags: algorithms, primes
---