# Question
Title: NP completeness of closest vector problem
Let $\mathcal{B} = \\{v\_1,v\_2,\ldots,v\_k\\} \in \mathbb{R}^n$ be linearly independent vectors.

Recall that the *integer lattice* of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations of elements of $\mathcal{B}$ using only integers as coefficients. That is $$L(\mathcal{B}) = \\{ \sum\_{i=1}^k c\_i b\_i \mid c\_i \in \mathbb{Z}\\}.$$

The *closest vector problem* asks us to find a nonzero vector $v \in L(\mathcal{B})$ such that $||v||$ is minimized.

It is apparently well known that this problem is NP-complete though I was not able to find a reduction to any of the "well known" NP-complete problems.

The first proof of this claim seems to be in *P. van Emde Boas. "Another NP-complete problem and the complexity of computing short vectors in a lattice".*, but I cannot find a copy of this paper.

Can someone give a polynomial reduction of some well known NP complete problem to the closest vector problem?

# Answer
As far as I know, it is not known that the shortest vector problem is NP-hard for any $L^p$ norm other that $L^\infty$. It is known that the shortest vector problem is "NP-hard under randomized reductions" for all $L^p$, a result first proved by Ajtai. See for example Miccanccio's paper and the results he references. Since then better inapproximability results have been obtained, but as far as I can tell nobody could prove an unconditional NP-hardness result.
> 5 votes

# Answer
There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something different.

If you are asking about the SVP, as your mathematical formulation implies, it is known to be NP-hard in the $L\_\infty$ norm but not known to be NP-hard in any other norm. The proof is found in the paper Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, by P. van Emde Boas. Confusingly, the terminology has changed over time: van Emde Boas calls this problem the "closest vector problem", but under modern naming conventions, this is known as the SVP in $L\_\infty$ norm. That said, there is strong evidence that the SVP in $L\_2$ norm is almost certainly hard, even though we do not have a proof that it is NP-hard.

If you are truly asking about the CVP, then your mathematical formulation is incorrect, under the standard naming terminology that is accepted today. The CVP is known to be NP-complete in the $L\_2$ norm (and possibly in other norms as well). This proof is also due to van Emde Boas. Confusing, he calls this problem the "nearest vector" problem, but under modern naming conventions, this is known as the CVP in $L\_2$ norm.

The difference between the CVP vs SVP is that the SVP asks to find the shortest lattice vector, i.e., the lattice vector that is closest to $0$ (the all-zeros vector); in contrast, the CVP is more general, as the input includes a vector $v$, and the goal is to find the lattice vector that is closest to $v$. So CVP is at least as hard as SVP. See https://en.wikipedia.org/wiki/Lattice\_problem.
> 0 votes

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


# Question
Title: What is the complexity of minimising a convex quadratic function over the integers?
The problem of interest is $$ \min\_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x $$ where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the closest lattice vector problem (in $\ell\_2$ norm) can be reformulated in the above form. Do we have a proof of $\mathsf{NP}$-hardness for a corresponding decision problem - does there exist $x\in\mathbb{Z}^n$ so that the above quadratic takes a value less than or equal to $f^\* \in \mathbb{R}$?

I don't find a proof of $\mathsf{NP}$-hardness of the closest lattice vector problem in $\ell\_2$ norm. If such a proof is found, then this problem is solved.

# Answer
The closest lattice vector problem is NP-hard in the $L\_2$ norm. See NP completeness of closest vector problem for a reference to the proof.
> 2 votes

---
Tags: complexity-theory, np-hard, integer-programming, quadratic-programming
---


# Question
Title: Is there a CPU architecture which allows early register access?
In Intel's x86 architecture, imul (integer multiply) usually has latency of a few clock cycles. Those CPUs are very smart in filling the time (e.g., pipelining or out-of-order execution), but do any commercial CPUs simply let the program access the intermediate unfinished result?

To be realistic, one clock cycle after imul, the output register probably has not changed at all. So, in this case, my question becomes: Is there any commercial CPU which would allow you to read that register in the following clock cycle though it still gives the old contents?

If the compiler plans for these latencies, it seems that this architecture might be useful. It basically passes the burden of pipelining from the CPU to the compiler. I'm sure this approach has a name, but I am just a curious beginner.

# Answer
> 2 votes
You are describing pipeline forwarding for data hazards. Here is a wikipedia article about it: https://en.wikipedia.org/wiki/Operand\_forwarding

This is a common feature of in-order processors (such as MIPS32). Since they are not operating out-of-order, the data hazard detection logic detects that the result will not be available during the clock cycle immediately after the instruction executes. The pipeline scheduling logic could either stall the pipeline or forward the result from the arithmetic unit (e.g., the multiplier) directly into where the next instruction would expect the result (e.g., one of the inputs to the ALU for example).

The compiler isn't required to be aware of this feature, however, in some scenarios it can optimize for these types of architecture features.

I won't say it is impossible or even say it isn't performed, but doing this in an out-of-order processor is much harder because the instruction window is tracking dependencies of each instruction via register indices. The control logic for the instruction window is significantly more complex if it is allowed to detect all possible data hazards opportunistically.

# Answer
> 2 votes
Classic VLIW architectures provide this feature. Operations are statically scheduled with fixed latency and the old value would be associated with a register name until an overwriting operation completed. Texas Instruments' TMS320C66x DSPs are modern examples.

The MIPS R2000 had a limited form of this in its delayed load slot. Since loads had a latency of two cycles, an instruction immediately following a load could read the old value from the loads destination register *if the load was a cache hit* (a cache miss would return the newly loaded value).

(Delayed branches are similar except that instead of the old value of the program counter being preserved, the expected value if there was not a branch is provided. ARM, which mapped the program counter to a general purpose register, also had an interesting feature of exposing the pipeline delay (of the original implementation) between instruction fetch and register read for execution such that a read of the program counter would not give the address of the executing instruction.)

If an architecture does not define a non-zero latency of operations, hardware cannot determine when a new value would become visible. With architectural zero-latency operations, an instruction's result may be sourced by an immediately following instruction, requiring hardware checks for availability in a superscalar design (or a scalar design with greater than one cycle execution latency) but making limited instruction fusion more practical. With non-zero latency operations, software must ensure that data dependencies are expressed, that a dependent operation is executed in a later cycle.

Static scheduling introduces significant constraints with respect to binary compatibility if hardware is to remain simple; the latency of an operation cannot change. With explicit parallelism but one cycle latencies, all operations within a cycle-chunk can execute in parallel without dependency checks and a straightforward operand availability check can stall the next chunk of internally independent operations; this represents a compromise between the extremely simple hardware of classic VLIW and the more complex hardware of in-order superscalar designs.

(The handling of write-after-write hazards for an in-order design with out-of-order completion seems loosely related. A later but lower latency instruction must be prevented from hiding the result of an earlier but higher latency instruction to the same destination. One way of doing this is by having register writeback in the same cycle for all instructions and using register name versioning in the result forwarding network.)

# Answer
> 0 votes
Typically the destination register isn’t touched until the final result is stored. If you wanted for example an imul instruction where you can access intermediate results after one and two cycles plus the final result, you’d need three writes to the register. Register writes are a very limited resource. This would for example waste the register write capabilities that two add instructions need.

And a multiplication typically has nothing useful to show at all after one or two cycles. 64x64 bit multiplication will produce 4096 individual bits, then use tons and tons of full adders to reduce the number of bits until you end up with two 64 bit numbers that need adding. I would assume that these two numbers are available some time after the start of the third cycle.

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


# Question
Title: Solve a recurrence using Akra-Bazzi method where $p$ is not integer and integration is not easy
I recently faced this problem in *CLRS ed.4* and couldn't find out how to attack it and solve it. Here's the recurrence: $$T(n)=3T(\frac{n}{3})+8T(\frac{n}{4})+\frac{n^2}{\log{n}}$$

Here's what I tried: $$\frac{3}{3^p}+\frac{8}{4^p}=1$$ For $p=1$, we get $\frac{3}{3}+\frac{8}{4}\>1$ and for $p=2$, we get $\frac{3}{3^2}+\frac{8}{4^2}\<1$. So we conclude that $1\<p\<2$. Using numerical methods, we get $p\approx1.85674$. Then we can write: $$T(n)=\Theta\left(n^p(1+\int\_1^n{\frac{x^2}{x^{p+1}\log{x}}}\\,\mathrm{d}x)\right)=\Theta\left(n^p+n^p\int\_1^n{\frac{1}{x^{p-1}\log{x}}}\\,\mathrm{d}x\right)$$

Here's where I'm stuck. I know $1\<p\<2$ but I can't figure out or guess the intergral answer. I suspect we don't need to calculate the integral actually, but then how can we solve the recurrence then?

Any hint or help is so much appreciated!

# Answer
The integral is in $\Theta(\frac{n^{2-p}}{\log n})$ and, substituing it back in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int\_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int\_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int\_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align\*} \int\_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int\_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int\_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int\_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int\_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align\*} $$
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: What would happen SHA-256 collision were to be found?
As far as I and this wikipedia page know, there are no collisions (2 inputs with the same output) found in SHA-256 (yet). what would happen if a collision were to be found,

**1. would it be easier to find more collisions? (based on the first collision found)**

**2. is a single collision found a major security risk as the only thing an attacker can do is switch between those inputs? (or is there a way to reduce any different inputs to the collision found input)**

**3. would (and should) it stopped being used?**

# Answer
> 1 votes
If given some data we could at will create different data with the same SHA that would be a bad problem. Dump SHA.

If we could at will create two sets of data with the same SHA, someone will figure out a way to turn that into a fatal problem.

If someone uses a supercomputer to create *one* collision at a cost that would be outside my reach, I think that wouldn’t be a problem.

---
Tags: hash, security
---


# Question
Title: What does it mean to prove the halting problem is undecidable "using arithmetization"?
In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of the curriculum states that students should be able to

> Use arithmetization and diagonalization to prove Turing Machine Halting/Undecidability.

I am quite familiar with using a diagonalization argument to prove that the halting problem is undecidable, but what does it mean to use arithmetization to prove this result? I don't believe I've come across a proof using this technique in any texts I've read before. Everybody seems to go with the diagonalization argument.

# Answer
> 14 votes
I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a description of a Turing machine as a bit-string and hence as a natural number). See, e.g., https://en.wikipedia.org/wiki/Halting\_problem#Formalization.

In other words, the requirement is not that students should know how to use diagonalization to prove Turing Machine Halting/Undecidability, and also know how to use arithmetization to prove Turing Machine Halting/Undecidability. It is not that there are two separate ways to prove the undecidability of the halting problem and students should know both. Rather, it is that there is a standard proof of the halting problem, and this proof relies on both diagonalization and on "arithmetization" as defined above, and students should know the standard proof and grok those two aspects of it.

# Answer
> 3 votes
TLDR: It means that they are using a technique to represent Turing machines as **numbers** in order for the circularity to be possible, hence "arithmetization".

It is not trivial (especially, it was not at the time) that such a thing as code existed, or that things like binary numbers (which are just numbers) could be used to list or index all possible programs.

After Turing introduced the concept of a Turing machine, he specified that there were sets of instructions that would define what particular machine one is talking about. But it is not immediately obvious from this, that everything about those instructions, could, in fact, be described using a finite number.

Look into Gödel numbering also. Gödel showed that numbers can be used also to index all possible proof theories that can be used as foundations of mathematics (rules for what is a valid proof).

It is more evident, however, from Turing's definition, that Turing machines could do operations *on* numbers. It was just less obvious that they could be described *by* numbers. Because of these two connections, it is possible to set up circular situations where Turing machines are calculating properties of other Turing machines, including, in particular, themselves.

This allowed Turing to create a machine that "halts (returns a value) only for numbers of (code of) Turing machines that will never halt". If the halting problem were solvable, such a machine would have to exist, because their (own) number would come up in the list of machines. Since this is a contradiction, it proves the halting problem is undecidable by any machine that is equivalent to a Turing machine, i.e. finite, mechanical.

---
Tags: undecidability, halting-problem, education, diagonalization
---


# Question
Title: Maximum reachable checkers on a checkerboard
This is a problem inspired by a video game that I've been thinking about for a long while, and I haven't convinced myself that I can do any better than brute force + pruning techniques, which would still take way too long to solve.

Is there anything better? Any class of algorithm I should look into more?

## Problem description

* You are on a checkerboard. Let's say 8x8 for now, but interested in general solutions too.
```
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

```
* There is a "start square" on the board, somewhere along the edge.
```
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

```
* You may place checkers onto the board anywhere you like, with the following restrictions:
    + You cannot place a checker on the start square.
    + Each square may contain 0 or 1 checker; you can't place multiple in one square.
    + All checkers must be "reachable" (described further in the next bullet).
* From the start square, you are able to traverse the board, using up/down/left/right movements to adjacent squares (diagonals are not considered adjacent).
    + You cannot "traverse" into a square that is occupied by a checker.
    + You must remain on the board.
    + To "reach" a given checker, you must be able to traverse to a square adjacent to the square that checker is placed on.
* **What is the *maximum* amount of checkers you can place on the board?**

## Examples

* Valid (but **not** the maximum solution: this has 36, I've found 38 by hand for this start square configuration):
```
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

```
* Valid (but definitely not the maximum):
```
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ ● │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ ● │ S │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

```
* Invalid (corner checker is not "reachable"):
```
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ ● │ ● │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

```

## My current approach

My current approach is just brute force, unfortunately:

* Generate a 2d bool array (for an 8x8 checkerboard, I'd just use a 64-bit int)
* Flood-fill from the start square for "reachability"
* Check every checker and make sure it's "reachable"
* As you find valid boards with `n` checkers, you can stop trying any board that has `<= n` checkers.

Obviously, for an `n` by `m` board (with one start square), you'd have to check `2^(n*m-1)` different combinations to be sure you found the maximum. Not great.

One realization I've had is that if a given checker configuration is invalid, adding more checkers to it won't magically make it valid. So, there's some opportunity to prune the problem space that way, but I'm not sure if there's an efficient way to implement it. Turning this into a recursive problem ("if you have a valid board, try adding one more checker to it in all available locations, and recurse for any of those boards that are valid") would end up either:

* trying certain configurations much more than once (depth-first), or
* turning the problem into a `2^(n*m-1)` memory complexity problem to prevent that, I think? (breadth-first).

# Answer
One approach would be to express this as an instance of SAT, and use an off-the-shelf SAT solver. See Boolean constraints for a connected component of a graph for a technique for encoding reachability and thus enforcing all of your constraints via a CNF formula.

In particular, you can use SAT to check whether there exists a solution with (for example) at least 37 checkers. Then, you can use binary search to vary the number 37 and find the largest number such that there exists a valid solution.

Alternatively, you could encode it as an instance of integer linear programming, where the goal is to maximize the number of checkers (which is a linear objective function), and then solve it with an off-the-shelf ILP solver. See also Express boolean logic operations in zero-one integer linear programming (ILP) for how to convert logical constraints to ILP.
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: Is there a known polynomial time complexity problem with bad constants?
As you know, big O notation hides all constants. For instance, both runtimes $T\_1=n$ and $T\_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$). Is there an iconic problem whose best known solution has a terrible (large) constant in the runtime expression?

# Answer
> 27 votes
Such algorithms are called Galactic Algorithms.

# Answer
> 13 votes
A simple one: Given n chess positions, find an optimal move for each position.

The game of chess is finite, so finding an optimal move for any position is O(1), and for n positions it is O(n). With a huge constant.

# Answer
> 7 votes
To add another perspective on this: there is a class of problems known as fixed parameter tractable (FPT) which has been studied extensively. In this area of research, one studies problems that, given a *fixed* additional integer parameter $k$ on the input, can be solved in polynomial time.

For example, suppose you are given a graph $G$ such that the tree-width of the graph is a known parameter $k$. Then one studies problems that are decidable in time $$ f(k) \cdot \text{polynomial}(|G|) $$

where $f$ is some function purely depending on $k$. So if $k$ is fixed, then these are polynomial time algorithms.

But the problem is that typically, the function $f$ turns out to be extremely fast growing. For example, $f$ might be exponential, or doubly exponential, or even non-elementary. So a problem might be FPT, but for, say, tree-width 4 or 5, you would already get a huge, astronomical constant in front of the polynomial.

# Answer
> 0 votes
Another simple one, that turned up in another question. Given a finite set S, sorting any array of elements of S can be sorted in linear time using counting sort (or without any additional storage: By moving every element s of S to the beginning of the array). This is linear instead of n log n, but has the size of S as a constant factor.

Problem: Sort any array of 256 bit integers in linear time.

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


# Question
Title: Optimal randomized algorithm for set cover
This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem which achieves an approximation ratio of $1$ (with high probability)? Is it possible to achieve such an algorithm, or is this still unknown?

# Answer
> 1 votes
Approximation ratio of 1 means that it outputs an exact solution (so it is not an approximation algorithm but rather an exact algorithm). Set cover is known to be NP-hard, so there is no such polynomial-time randomized algorithm, unless RP = NP.

---
Tags: algorithms, approximation, randomized-algorithms
---


# Question
Title: Can an unreocognizable language be Turing-reducible to a recognizable language?
Suppose $L\_1\preccurlyeq\_T L\_2$, and $L\_1$ is unrecognizable, can $L\_2$ be recognizable?

With decidability, if $L\_1$ is undecidable, then $L\_2$ is undecidable, because $L\_1$ is the “easier” question. Would this apply to recognizability, too?

# Answer
> 0 votes
Any set $A$ Turing-reduces to its complement $A^c$.

Hence, the non-recognizable set $K^c$ Turing-reduces to the recognizable set $K=(K^c)^c$, where $K$ is the Kleene set (or, if you prefer, your favorite variation on the halting problem).

---
Tags: algorithms, turing-machines, computability, reductions, turing-recognizable
---


# Question
Title: Can this reccurrence recurrence be solved using Master Theorem?
Assume we have: $$T(n)=7T(\frac{n}{2})+n^2\lg{n}$$ Can we solve it using master theorem?

As we know $n^{\lg\_2{7}}\approx n^{2.81}$. On the other hand, we have $f(n)=n^2\lg n$. So we should compare $n^.081$ and $\lg{n}$. As I know, $\lg{n}=\mathcal{O}(n^{0.81})$. So the answer should be $T(n)=\Theta(n^{\lg7})$. Am I right? Can we use Master Theorem here? the logarithm make me unsure about it.

# Answer
Yes, that recurrence can be solved using the master theorem, and you got the correct answer but your justification is missing on a detail.

In particular it is false (in general) that a recurrence of the form $T(n) = aT(n/b) +f(n)$ has solution $T(n) \in \Theta(n^{\log\_b a})$ when $f(n) \in O(n^{\log\_b a})$. As a concrete example, $T(n) = 4T(n/2) + n^2$ satisfies $f(n) = n^2 \in O(n^{\log\_2 4})$ but it has solution $T(n) \in \Theta(n^2 \log n)$ (and not $T(n) \in \Theta(n^2)$). A trickier example is $T(n)=2T(n/2) + \frac{n}{\log \log n}$, where $\frac{n}{\log \log n} \in o(n) \subset O(n)$, but the master theorem does not apply.

What you actually need is $f(n) \in O(n^{\log\_b a - \varepsilon})$ for some constant $\varepsilon\>0$. This is clearly the case in your recurrence since $\log n \in O(n^c)$ for all constants $c\>0$ (so you can choose any $\varepsilon$ in the non-empty open interval $(0, \log\_2 7 - 2)$).
> 0 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Solve the recurrence $T(n)=T(n-1)+\frac{1}{n}$
Assume this recurrence: $$T(n)=T(n-1)+\frac{1}{n}$$

As we can use Master Theorem and Akra-Bazzi method here, I tried to draw a recurrence tree and I reached the whole cost of this tree is $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$. What's a tight upper and lower bound for this recurrence (I'm talking about $\Theta$, not $\mathcal{O}$)? Is it even possible to find a $\Theta$ for it?

# Answer
> 2 votes
The quantity $H\_n = \sum\_{i=1}^n \frac{1}{i}$ is known as the $n$-th harmonic number. It is well-known that $H\_n = \Theta(\log n)$.

To see this notice that the function $\frac{1}{x}$ is monotonically decreasing, which means that the area under $\frac{1}{x}$ in the range $i \le x \le i+1$ is at most $\frac{1}{i}$ (i.e. the area of a rectangle of width $i+1 - i = 1$ and height $\frac{1}{i}$). In formulas: $\int\_{i}^{i+1} \frac{1}{x} \text{d}x \le \int\_{i}^{i+1} \frac{1}{i} \text{d}x = \frac{1}{i}$.

$$ H\_n = \sum\_{i=1}^n \frac{1}{i} \ge \sum\_{i=1}^n \int\_{i}^{i+1} \frac{1}{x} \text{d}x = \int\_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Omega( \log n). $$

Similarly, the area under $\frac{1}{x}$ in the range $i \le x \le i+1$ is at least $\frac{1}{i+1}$, i.e., $\int\_{i}^{i+1} \frac{1}{x} \text{d}x \ge \int\_{i}^{i+1} \frac{1}{i+1} \text{d}x = \frac{1}{i+1}$.

$$ H\_n = 1 + \sum\_{i=1}^{n-1} \frac{1}{i+1} \le 1 + \sum\_{i=1}^{n-1} \int\_{i}^{i+1} \frac{1}{x} \text{d}x = 1 + \int\_{1}^{n} \frac{1}{x} \text{d}x=1+\ln n = O(\log n). $$

---
Tags: recurrence-relation
---


# Question
Title: What is the proof in FLP for statement that "clique with majority of processes exist" if majority of the processes live?
The FLP paper provides proof in section "4. Initially Dead Processes" that consensus is possible if majority of processes live and no process dies during the consensus protocol. The proof has 4 main steps:

1. Build G graph in way that each process broadcast it's process number and waits for the message from L other processes (L=\[(N+1)/2\])
2. Calculate transitive closure of G: G+
3. Determine clique of G+. The paper says that clique has cardinality at least L. (Node k is in the clique iff k is itself an ancestor of every node j that is an ancestor of k)
4. Make a decision based on the initial values of the processes in the clique

**I would have the following question about step 3:**

* What guarantees that clique described in step 3 exist?

# Answer
Firstly, we need to prove that `G` is a single connected component. If `n` is a node in a connected component of `G`, then there are `L-1` other nodes that are also in that component (the ones from which `n` received their messages). So this component has the size of at least `(L-1)+1 = L` nodes. So each connected component has at least `L` number of nodes and `L` is bigger than the half of the number of the nodes, so can be a single connected component only.

By the definition of the transitive closure, `G+` will also have a single connected component. This means that it has only a single initial click. An initial click is a set of nodes that does not have incoming edges. Let's assume that `n` is a member of the initial click of `G+`. Let `m` be another node such that there is an edge from `m` to `n` in `G`. By definition, there is an edge in `G+` from `m` to `n` as well. Because of the definition of initial click, there cannot be an incoming edge to `n` from outside of the initial click, so `m` must be in the initial click as well. By the construction rules of `G`, there is `L-1` number of such `m` nodes that has an edge to `n` in `G`, so they are also part of the initial click along with `n`. So the initial click has the size of at least `L` nodes.
> 0 votes

# Answer
It can be proven with the following two steps that clique with cardinality at least L exist:

1. There is at least one node which is in the clique of G+
2. If a node is in the clique of G+ than all of its predecessors are in the clique

For #1 we use proof by contradiction. So we will assume that no such node exist which is ancestor of all its ancestor:

1. If no such node exist than for each node X there is at least one node Y that X is not ancestor of Y in G+
2. If X is not ancestor of Y in G+ than it can not be predecessor of Y predecessors in G either
3. So X can not be the predecessor of the L -1 predecessors of Y and Y itself in G
4. There are L-1 nodes left in G. It includes X so X can have maximum L-2 nodes predecessor
5. If each X has maximum L-2 predecessors in G it means that each node has maximum L-2 outgoing edges. It is contradiction because each node has L-1 incoming edges in G

For #2 the proof is the following with node X which is in the clique of G+:

1. For each Y node in G+ where X is the ancestor of Y than each Z ancestor of X is also ancestor of Y
2. For each Z it is true that its ancestors are subset of X ancestors
> 0 votes

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


# Question
Title: Formally Verify if a Sequence of Regex-Based Modifications is Idempotent
I'm performing a sequence of text formatting using regex in Python.

I'm curious to know if it's possible to formally verify whether a single (or a sequence of) regex modification(s) is idempotent, which means that for every `text`, `d ∘ d (text) = d (text)`, where `d` denotes the resulting total modification.

To be precise, by a single regex modification, I refer to the function `f_regex_subst: text |-> re.sub(regex, sub, text, 0, re.MULTILINE)`. When a sequence of such modifications is applied, the resulting function is simply the composition of these functions.

The motivation is ensuring the formatting process yields stable result for any text.

# Answer
This is likely to be a very hard problem, so hard that I don't think you should expect a useful solution that can handle all possible regexes.

The extended regular expressions supported by Python's `re.sub` are very expressive and powerful, which makes the verification problems involving them very hard. These advanced features (backreferences, capture groups, lookahead, lookbehind, etc.) make these regexes very expressive. For instance, it is known that the problem of testing whether a string matches a regex (that might contain backreferences) is NP-complete. As another example, it is known that testing equivalence of two such regexes is undecidable, as is testing whether such a regex matches every string, or testing whether such a regex matches a regular language. For proofs, see the following paper:

Extended Regular Expressions: Succinctness and Decidability. Dominik D. Freydenberger. *Theory of Computing Systems*, vol 53, pp.159-193, 2013.

The takeaway is that verification problems involving this type of regex tend to be very hard. I don't know of anyone who have studied idempotency of a sequence of `re.sub` operations, but I would imagine that likely it is also very hard... possibly also undecidable.

I would suggest that you figure out what your actual goals are, and then see if you can find some alternative approach to achieve your real goals. Perhaps you only need to reason about a subset of regexes (e.g., only those that can be represented by a finite-state machine / regular transducer)? Perhaps it suffices to use testing to check idempotency, without having any formal guarantees? Perhaps you can find a way to structure your code so you don't need to verify this property? It is hard to know, without more context.

See also https://cstheory.stackexchange.com/q/448/5038, https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html, Which languages do Perl-compatible regular expressions recognize?, What is the computational complexity of "real-life" regular expressions?.
> 0 votes

---
Tags: regular-expressions, software-verification, transducers
---


# Question
Title: Prove NP-completeness of deciding satisfiability of monotone boolean formula
I am trying to solve this problem and I am really struggling.

A *monotone boolean formula* is a formula in propositional logic where all the literals are positive. For example,

$\qquad (x\_1 \lor x\_2) \land (x\_1 \lor x\_3) \land (x\_3 \lor x\_4 \lor x\_5)$

is a monotone boolean function. On the other hand, something like

$\qquad (x\_1 \lor x\_2 \lor x\_3) \land (\neg x\_1 \lor x\_3) \land (\neg x\_1 \lor x\_5)$

is not a monotone boolean function.

How can I prove NP-completeness for this problem:

> Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$?

Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.

I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x\_1$ with $z\_1$, and then I tried forcing $x\_1$ and $z\_1$ to be different values. I haven't quite been able to get this to work though.

# Answer
The "parent" of the problem you're looking at is sometimes called Weighted Satisfiability (WSAT, particularly in parameterized complexity) or Min-Ones (though this is normally an optimization version, but near enough). These problems have the "at most $k$ variables set to true" restriction as their defining feature.

The restriction to monotone formulae is actually surprisingly easy to show hardness for, you just need to think outside satisfiability problems for a moment. Instead of trying to modify a SAT instance, we instead start with Dominating Set (DS).

See if you can get it from there. More is in the spoilers, broken into bits, but avoid them if you can. I won't show membership in NP, you should have no problem with that.

> Given an instance $(G, k)$ of DS (i.e. we want a dominating set of size at most $k$ for $G$), we can construct an instance $(\phi,k)$ of WSAT where the formula $\phi$ is a monotone CNF formula:

The basic construction:

> For each $v\in V(G)$ we have a variable $v' \in \text{var}(\phi)$, for each $v \in V(G)$ we have a clause $c\_{v} = \bigvee\_{u\in N(v)} u'$.

A sketch of the proof:

> Each vertex either has to be in the dominating set, or have a neighbour that is, so if we can find $k$ vertices that form a dominating set, the corresponding $k$ variables can be set to true in $\phi$, and each clause must contain at least one of them. Similarly if there is a weight $k$ satisfying assignment, the true variables correspond to the vertices we place in the dominating set - every clause $c\_{v}$ must have at least one, so each $v$ is dominated (by itself or otherwise).
> 14 votes

# Answer
There is a simple reduction from SAT. Introduce a new variable $z\_i$ to represent $\neg x\_i$. Given a formula $\phi$, we create a new formula $\phi'$ by replacing each occurrence of $\neg x\_i$ with $z\_i$, and adding the clause $x\_i \vee z\_i$ for each variable. We set $k$ to be the number of original variables. The new formula $\phi'$ is monotone, and is satisfiable with at most k variables set to true if and only if $\phi$ is satisfiable. (This is because the $k$ disjoint clauses $x\_i \vee z\_i$ causes any satisfying assigment for $\phi'$ to have at least $k$ variables to True; but then the only way to have at most $k$ is to have exactly one of them set to true for each pair {x\_i, z\_i}.)
> 3 votes

# Answer
IMO, it is intuitive to reduce Vertex-Cover to the problem that you are describing (which will show that the problem you are describing is at least as hard as Vertex-Cover). At the core of the problem you describe, you have to find $k$ literals such that setting them to 1 will satisfy the boolean formula. This is just like Vertex-Cover, where you have to find $k$ vertices such that all of the edges are covered.

Here are some more tips on the reduction:

> Each vertex becomes a literal in the boolean formula.

> Each edge is a clause in the boolean formula.
> 1 votes

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


# Question
Title: Are there any (theoretical-esque) computer science "competitions" at Undergrad level similar to Putnam?
I have searched for a bit eventually arriving at well known websites like codeforces, atcoder, codewars, codinggame or the various OJs. They mostly involve solving tasks where usually the main focus is elementary discrete maths + data structures and algorithms.

However, I cannot find any that target the more theoretical side of Computer Science with topics including Complexity, Theory of Computation, Logic, Algorithms, Probability & Linear Algebra questions etc.

So do such contests exists? If so, please list! Bonus if there are any contests for high schoolers as well.

# Answer
> 0 votes
The closest thing that I found was the from the Indian based college(?) Chennai Mathematical Institute (CMI)'s STEM's competition for Computer Science (Category A & B).

Some tangentially relevant discussion is in the doi: 10.1007/978-3-319-25396-1\_9

---
Tags: theory, programming-contest
---


# Question
Title: Explaination of incremental push's amortized time
In the Narasimha's data structure book, there is a line

> The amortized time of a push operation in the incremental growth of array stack (realloc on every push) is $O(n) \[O(n^2) / n\]$.

I am confused with this Big-O notation here, what does it mean? Is arithmetic legal on big-o notation functions?

# Answer
It just means that the amortized time complexity is $O(n)$, amortized over $n$ pushes. The $\[O(n^2)/n\]$ indicates that the $O(n)$ amortized time comes from a total time complexity of $O(n^2)$ divided by the $n$ pushes.

The total time complexity is $O(n^2)$ because a push in a stack of size $k$ costs $O(k)$, thus: $$\sum\_{k=1}^n k \ = \ \frac{n(n+1)}{2} \ = \ O(n^2) \ . $$
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$
Assume this recurrence: $$T(n)=T(n-2)+\frac{1}{\lg{n}}$$ I tried to draw its recurrence tree and I reached that the whole cost is $\dfrac{1}{\lg{n}}+\dfrac{1}{\lg{n-2}}+\dots+\dfrac{1}{x}$ that $x$ is $2$ if $n$ is even, otherwise is $3$. So somehow we should solve $\sum\_{i=1}^{\frac{n}{2}}{\dfrac{1}{\lg{2i}}}$ or $\sum\_{i=1}^{\lfloor\frac{n}{2}\rfloor}{\dfrac{1}{\lg{2i+1}}}$ that both equal to the same $\Theta(f(n))$. I read somewhere that it equals $\Theta(\dfrac{n}{\lg{n}})$, but I can't find out how. The lower bound is easy, but what about the upper bound?

# Answer
> 3 votes
Ignoring rounding (which does not affect the asymptotic growth rate): $$ \sum\_{i=1}^{n/2} \frac{1}{\log 2i} \ge \sum\_{i=1}^{n/2} \frac{1}{\log n} \ge \frac{1}{2} \cdot \frac{n}{\log n} = \Omega\Big(\frac{n}{\log n}\Big), $$ and

$$ \begin{align\*} \sum\_{i=1}^{n/2} \frac{1}{\log 2i} &= \sum\_{i=1}^{\sqrt{n}/2} \frac{1}{\log 2i} + \sum\_{i=\sqrt{n}/2}^{n/2} \frac{1}{\log 2i} \le \sqrt{n} + \frac{n}{\log \sqrt{n}} \\ & = O(\sqrt{n}) + \frac{1}{2} \cdot \frac{n}{\log n} = O\Big(\frac{n}{\log n}\Big). \end{align\*} $$

# Answer
> 0 votes
Every recursion formula of the form $T(n) = T(n-k) + f(n)$ for sum fixed $k$ can be turned into a sum: $T(n)$ is the sum of $f(n - i\times k)$ for those $i$ where $f(n - i\times k)$ is not known, plus the first known value. In your case you would need to know $T(1)$ and $T(0)$ without the recursion formula.

Note that for $\sqrt n ≤ j ≤ n$ we have $(\log j) / 2 ≤ \log j ≤ \log n$.

---
Tags: recurrence-relation
---


title: Multithreaded quicksort

text:
# Question
Title: Multithreaded quicksort
The runtime of Quicksort can be significantly reduced if multiple threads running on multiple cores can be used. With just two cores, just partition an array into two halves and let another thread sort the second half.

The problem is that with many cores, say eight, the initial partition of the array takes a very significant amount of time.

Does anyone have an idea how the partitioning of an array could be made faster if multiple cores running multiple threads are available?

# Answer
> 1 votes
Yes. Below is one idea that comes to me. Suppose for simplicity of description that you have 8 cores. There are three phases; the partitioning and sorting phases are the most expensive, and both can be parallelized.

1. Pivot selection phase: Select 7 pivots in any convenient fashion. For instance, randomly sample 128 items from the array, then use quickselect or quicksort on these 128 items to select the items ranked 16, 32, 48, 64, 80, 96, 112.
2. Partitioning phase: Divide the array into 8 equal-sized chunks. For instance, the first chunk contains the first 1/8th of the array, the second chunk contains the second 1/8th of the array, and so on. Each thread is responsible for one chunk. The thread's job is to partition its own chunk into 8 partitions, using the 7 pivots. At the end of the partitioning phase, we obtain 64 partitions.
3. Sorting phase: Each thread is responsible for 8 partitions, one from each chunk. It should coalesce those 8 partitions and then sort them. For instance, the first thread is responsible for coalescing and sorting the smallest partition from each chunk, the second thread is responsible for coalescing and sorting the second-smallest partition from each chunk, and so on.

Wikipedia describes some other schemes: https://en.wikipedia.org/wiki/Quicksort#Parallelization.

---
Tags: quicksort, multithreaded
---


# Question
Title: How many random bits does this algorithm use on average?
Here, `flip()` is a function that returns `0` or `1` with equal probability. It can be proved function `Random(n)` returns a number from `0` to `n-1` with identically distributed probabilities (using loop invariant).

```
function Random(n):
    v = 1;
    c = 0;
    loop
        v = 2v;
        c = 2c + flip();
        if (v >= n) then
            if (c < n) then
                return c;
            else
                v = v - n;
                c = c - n;
            end if
        end if
    end loop
end function

```

My question is how many random bits does this algorithm use in average (expected number of times that the `flip()` function is called)?

# Answer
> 1 votes
I don't have a formal proof, but I expect the expected value is $\lg n + O(1)$ bits. In particular, heuristically I am expecting something like $\lg n + 2.9$ bits or so (but I don't trust that the constant is exactly right, so take this with a large grain of salt).

Where did I obtain this from? Well, after $\lg n$ steps, $v$ will be of size comparable to $n$.

Now as a heuristic, suppose that $v$ is uniformly distributed in the range $\[n/2,n)$ at a particular step. Of course $c$ will be uniformly distributed on the range $\[0,v)$, as this is an invariant of the algorithm. Then this step will terminate if $c \< n/2$. The probability of this is

$$\begin{align\*} \Pr\[c\<n/2\] &= \sum\_{v=n/2}^n \Pr\[c\<n/2 \mid v\] \Pr\[v\] = \sum\_{v=n/2}^n {n/2 \over v} \cdot {1 \over n/2}\\ &\approx \int\_{1/2}^1 {1 \over x} \\; dx = \log 2 \approx 0.69. \end{align\*}$$

On the other hand, if $c\>n/2$, then it will not terminate, and after the next step, $v$ will be uniformly distributed on $\[0,n-1)$ and $c$ uniformly distributed on $\[0,v)$. Starting from a point where $v$ is uniformly distributed on $\[0,n-1)$, it takes approximately 1 more step (on average) to reach a point where $v$ is uniformly distributed on $\[n/2,n-1)$, and then we're back to where we started. We expect to have to repeat this procedure $1/0.69 \approx 1.45$ times before it terminates, and each repetition takes 2 steps, so in total once we reach the point where $v$ is uniformly distributed on $\[n/2,n)$, we expect the algorithm to take $2 \times 1.45 \approx 2.89$ steps (on average) before terminating.

Summing these up ($\lg n$ steps in the first phase and $2.89$ steps in the second phase, on average) yields a number like $\lg n + 2.9$.

I have made some approximations and shortcuts and used some heuristics here, so this answer is a bit sketchy, but I would bet that it is approximately correct, though the constant term might not be exactly right.

---
Tags: algorithms, probability-theory, probabilistic-algorithms
---


# Question
Title: Hardness of approximation for Disjoint Group Steiner Tree
Does anyone know any *constant factor* approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group?

The (intuitive) reduction from Set-Cover seems to fail in that case, and it also feels easier. It seems to me you could solve this if the underlying graph is a tree in polynomial time. Is this case still NP-hard to approximate within a constant factor for general graphs?

I've searched for partition/non overlapping/disjoint Group Steiner Tree etc. But I can't find anything, so I imagine this particular variant might have a specific name.

Group Steiner Tree is the following problem:

Instance: a weighted graph $G=(V,E)$, a collection of vertex sets (groups) $S\_1,...,S\_n \subseteq V$.
Find: a minimum-cost connected subgraph of $G$ that contains at least one vertex of every group $S\_i$.

What I am interested in is the special case where there is some set $W \subseteq V$ such that $S\_1 \bigcup \cdots \bigcup S\_n = W$ and $S\_i \bigcap S\_j = \emptyset$ for all $i\neq j$.

# Answer
As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are pairwise disjoint wlog for any Group Steiner Tree instance. Suppose $v$ is a vertex in $k \geq 2$ groups, $g\_1, \ldots, g\_k$. We can create $k$ dummy nodes, $v\_1, \ldots, v\_k$ attached to $v$ by edges of cost 0. Then set each dummy node $v\_i$ to be in group $g\_i$ and remove $v$ from all groups.
> 0 votes

---
Tags: complexity-theory, optimization, combinatorics, approximation
---


# Question
Title: optimal hamiltonian cycle in the Nearest Neighbor algorithm for the Traveling Salesman Problem
how to prove that in the Nearest Neighbor algorithm for the Traveling Salesman Problem with one modification, if it finds a hamiltonian cycle, it's the optimal cycle. the modification is if the shortest path it could choose is an edge to a node already visited, the algorithm stops.

# Answer
> 0 votes
First, I want to make sure I understand you correctly. You are considering the following algorithm, which I will call $\mathscr{A}$.

1. Given: a set $V$ of $n$ nodes/points and a metric $d:V \times V \to \mathbb{R}$
2. Pick $v\_1 \in V$ arbitrarily
3. For $i=1,2,\ldots, n-1$:

3.1. Find $u^\* = \arg\min\_{u \in V\setminus\\{v\_i\\}} d(u, v\_i)$

3.2. If $u^\* = v\_j$ for any $j \in \\{1,\ldots,i-1\\}$ return FAIL.

3.3. Otherwise set $v\_{i+1} = u^\*$
4. If $d(v\_1, v\_n) \> \min\_{u \in V} d(u, v\_n)$ return FAIL.
5. Otherwise return the Hamiltonian cycle $(v\_1, \ldots, v\_n, v\_1)$.

\[I am a little unsure if this is exactly the algorithm you are proposing, since normally in the nearest neighbour algorithm there is no check that $v\_1$ is the nearest neighbour of $v\_n$. However, without this the statement you want to prove is false. If I am wrong about the algorithm please correct me.\] You then want to prove that if $\mathscr{A}$ returns a Hamiltonian cycle, then it returns the optimal Hamiltonian cycle. I feel like there should be a proof that follows the strategy used for proving the correctness of many greedy algorithms: look at an optimal solution, suppose it is different from the greedy solution, arrive at a contradiction. However, I admittedly keep hitting roadblocks.

---
Tags: hamiltonian-circuit
---


# Question
Title: Absolute difference between largest IEEE754 number and its predecesor
In simple precision format, the largest possible positive number is

$A = 0 ~~~ 11111110 ~~~ 111\ldots 111$

Its predecessor is

$B = 0 ~~~ 11111110 ~~~ 111 \ldots 110$

But what is the absolute difference (in decimal) between these?

Appealing to scientific notation,

$A = 0.(2^{22}+2^{23}+\ldots + 2 + 1) \times 2^{2^{7}+2^{6} + 2 + 1 - 127}$

and

$B = 0.(2^{22}+2^{23}+\ldots + 2 + 0) \times 2^{2^{7}+2^{6} + 2 + 1 - 127}$

So they have only a difference of one point in the last decimal digit. The exponent tells us there are $2^{7} + \ldots + 2 + 1 - 127$ such decimal points. Let $e$ denote that quantity. Is it correct to say the difference is

$$0.\overbrace{000\ldots 000}^{e \text{ times}}1$$

or am I missing something?

# Answer
> 1 votes
The IEEE-754 `binary32` format comprises a sign bit, eight exponent bits, and twenty-three *stored* significand bits. The stored exponent is biased by 127. For *normal* operands, the significand actually comprises twenty-four bits that encode values in $\[1, 2)$. Since this means that the most significant bit of the significand is always 1, it is not stored. If we denote the largest finite `binary32` operand by $a$ and its immediate predecessor by $b$, their binary encodings are

```
       s exponent significand
   a = 0_11111110_11111111111111111111111  largest finite binary32
   b = 0_11111110_11111111111111111111110  its immediate predecessor

```

The most significant bit of the *stored* significand has numerical weight $2^{-1}$, while the least significant bit of the *stored* significand has numerical weight $2^{-23}$. If we take into account exponent bias, the numerical values of the two operands are

```
                   2⁰ 2⁻¹                   2⁻²³
                    ↓ ↓                     ↓
   a = 2⁽²⁵⁴⁻¹²⁷⁾ * 1.11111111111111111111111
   b = 2⁽²⁵⁴⁻¹²⁷⁾ * 1.11111111111111111111110

```

The difference $a- b$ is therefore $2^{(254-127)} \cdot 2^{-23} = 2^{104} \approx 2.02824096 \cdot 10^{31}$. We could also confirm this experimentally, for example with the following ISO-C99 program:

```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main (void)
{
    uint32_t ai = 0x7f7fffff; // largest finite binary32
    uint32_t bi = 0x7f7ffffe; // its immediate predecessor
    float a, b, diff;
    memcpy (&a, &ai, sizeof a);
    memcpy (&b, &bi, sizeof b);
    diff = a - b;
    printf ("diff = %15.8e  %15.6a  log2(diff)=%f\n", diff, diff, log2f (diff));
    return EXIT_SUCCESS;
}

```

---
Tags: floating-point, binary
---


# Question
Title: Why not n^2 comparisons in the Alien Dictionary problem on leetcode?
Here's the problem statement (as given on GeeksForGeeks website):

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of characters in the alien language.

Explanation: We're given a sorted dictionary having N words. Here a dictionary is an ordered list. A word is a sequence of allowed characters. There are 'K' allowed characters. These characters are first K alphabets of roman script. For example, K=5 implies that the allowed characters are {a, b, c, d, e}. But the ordering of the allowed characters is different in the alien language from standard roman script. For example, in the alien language the order of characters could be \[b, d, e, a, c\]. The words in the given dictionary are sorted lexicographically. Using the dictionary, we've to figure out the ordering of characters in the alien language.

Example test case: N = 5, K = 4, dict = \["baa","abcd","abca","cab","cad"\]

Solution: {b, d, a, c}

Now the solution requires building a DAG. We iterate over the dictionary and compare every word to its next word to get information about the ordering of alphabets in the alien dictionary, i.e., pair-wise comparisons. In an optimal approach, (N-1) comparisons will be required to create the DAG (N being number of words in the dictionary). Every time we compare 2 word, we can infer something about the ordering of alphabets. This information is used to build the order of alphabets in the alien dictionary.

My first intuition was that every string in the dictionary can be compared to every string succeeding it thus totalling comparisons in order of N^2, i.e. \[(n-1)+(n-2)+...+2+1\] comparisons. But it turns out that N^2 comparisons aren't required. If we use only (N-1) comparisons as mentioned in previous paragraph, the information is sufficient to deduce the order of alphabets. How can I prove that the extra comparisons made in the N^2 approach will always be redundant giving no useful information?

# Answer
Each pair of adjacent words $w\_i,w\_{i+1}$ in the dictionary list $\[w\_1,\ldots,w\_N\]$ generates at most one edge in the DAG. Why "at most"? (a) because that edge may be present already and (b) because $w\_i$ could be a prefix of $w\_{i+1}$. The suggested $N-1$ comparisons suffice because nothing new can be learned from studying $w\_i,w\_{i+\ell}$ for $\ell \> 1$ that was not learned already by iterating through the $N-1$ adjacent pairs.

Let's prove that last claim. Roughly, this works as follows. Let $\Sigma$ be the alien alphabet. Suppose $m,n,o$ are minimal such that $m\<n\<o\leq N$ and comparing $w\_m$ with $w\_o$ adds the edge $(\alpha,\beta)$ to the DAG $(\Sigma,E)$ we obtained by comparing the $N-1$ pairs $(w\_i,w\_{i+1})$ for $1\leq i \< N$ and then forming the transitive closure.

For easier access to the letters of the three relevant words, set $x\_1\ldots x\_{k\_m} = w\_m$, $y\_1\ldots y\_{k\_n} = w\_n$, and $z\_1\ldots z\_{k\_o} = w\_o$. We know there exists $j$ such that $\alpha = x\_j \neq z\_j = \beta$ and, for all $1\leq k\<j$ we have $x\_k = z\_k$. (Otherwise we would not add $(\alpha,\beta)$.) We also know that $x\_k = y\_k = z\_k$ for all $1\leq k\<j$ and that $x\_j\leq y\_j\leq z\_j$ according to $E$. One of those "$\leq$" is strict, i.e., already in $E$. Either way, since we formed the transitive closure, $(x\_j,z\_j)$ is already in $E$ (or this is not the minimal example of $m,n,o$).
> 1 votes

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


title: Objective function

text:
# Question
Title: Objective function
I want to learn how to write objective functions for any problem or real-life action(not mathematical problems) can anyone suggest a good source? On online I am mostly finding objective functions for mathematical problems. Can anyone tell from where can i learn or practice those ?

# Answer
A simple one: You go to a restaurant, sit down at a table, and want a nice meal.

Define, as precisely as possible, leaving nothing out, what you want to achieve.
> 0 votes

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


# Question
Title: Why does lexer has O(n) time complexity?
According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a language. (there are some other reasons, e.g. to find the 'longest matching pattern' to distinguish between `if a`(keyword) and `ifa`(identifier))

Then, the lexer repeats this process until the input string ends, producing N tokens as a result. So I ended up with the conclusion that lexer has $\mathcal O(n^2)$ time complexity. But every resource and book says lexer takes linear time because the DFA has linear time complexity. What I am missing?

\*Edit: What was wrong is that I assumed the lexer uses multiple DFAs for each token. In reality, the lexer forms a single DFA to represent all token types in a given regular language, and it can identify token types with it's final states. Thus it takes $\mathcal O(n)$.

# Answer
> 0 votes
Your assumption of execution is based on a suboptimal backtracking implementation based on NFA needing to explore all paths through it.

A more optimal implementation would have a bitset of all states the NFA is in simultaneously. This lets you represent all $2^n$ states without explicitly listing them all.

For a lexer doing tokenization you might not be doing keyword recognition yet and instead leave that to a next parser step that checks whether a potential keyword is an actual keyword. This makes the lexer DFA much smaller.

If however you need to differentiate between keywords and identifiers then you would put the final state after seeing the first character that *cannot* be part of a identifier. In most programming languages once you know you are in a identifier it lasts until the first non-alphabetic character, so there is no point in backtracking.

The lexer DFA doesn't have a final state per se (other than actual EOF) but instead a output transition that would emit a token to the output. When after the `f` of a `if` the next non-identifier character would make it emit a IF token, if instead the character possible as part of an identifier it would transition into a general IDENTIFIER state looping back into itself until it sees a non-identifier character.

# Answer
> 0 votes
If you wrote a lexer for C++ and the next character is an “a” then the token is asm, auto or an identifier. Three choices only. Processing an identifier with a length k should take no more than O(k).

A reasonable n would be the number of characters or code points in the input. Sure, with a million characters you could have 1000 identifiers of 1000 characters each. But you would have n = 1,000,000 and the time a smallish multiple of n, say 100 million nanoseconds.

And you don’t need the longest matching pattern to distinguish between if and ifa: Just three characters.

---
Tags: time-complexity, finite-automata
---


title: Conditional milp formulation

text:
# Question
Title: Conditional milp formulation
I have two binaries, $\alpha\_{ts,it}$ and $\alpha\_{ts,gshp} \in \\{0,1\\} $, and two reals $T\_{it}$ and $T\_{ts}$ which have upper and lower bounds. How can I model $\alpha\_{ts,it}=1$ if the following constraints are met:

1. $T\_{ts}\geqslant-7$
2. $T\_{it}\leqslant14$
3. $T\_{ts}-T\_{it}\geqslant5$
4. $\alpha\_{ts,gshp}=0$

Regards

SR89

# Answer
> 0 votes
I might have found a solution to my problem by using four auxiliary binary variables $\alpha\_1$, $\alpha\_2$, $\alpha\_3$ and $\alpha\_4$ $\epsilon\ \\{0,1\\} $. The constraints 1.-4. are rewritten using the big-M method.

---

## Constraint 1

* $T\_{ts}\geqslant -7-M\cdot (1-\alpha\_1)$
* $T\_{ts}\leqslant -7+M\cdot \alpha\_1$

## Constraint 2

* $T\_{it}\leqslant 15+M\cdot (1-\alpha\_2)$
* $T\_{it}\geqslant 15-M\cdot \alpha\_2$

## Constraint 3

* $T\_{ts}-T\_{it}+M\cdot (1-\alpha\_3)\geqslant 5$
* $T\_{ts}-T\_{it}-M\cdot \alpha\_3\leqslant 5$

## Constraint 4

* $\alpha\_{ts,it}=1-\alpha\_{ts,gshp}$

## Constraint 5

* $\alpha\_{ts,it}\geqslant \alpha\_1+\alpha\_2+\alpha\_3+\alpha\_4-3$
* $\alpha\_{ts,it}\leqslant \alpha\_1$
* $\alpha\_{ts,it}\leqslant \alpha\_2$
* $\alpha\_{ts,it}\leqslant \alpha\_3$
* $\alpha\_{ts,it}\leqslant \alpha\_4$

---

This might be a solution. Unfortunately computational time is exploding. Does someone know a less time-consuming workaround?

Best SR89

# Answer
> 0 votes
That’s the problem with ILP; it is NP-complete so times can explode.

A simple strategy is to solve and optimise a problem as an ordinary linear programming problem, get the solution, and check where your other rules are violated. For example if you find an optimal solution where x = 12.381 but x must be an integer, then you solve two problems, one with x \<= 12 added, and one with x \>= 13 added. (If you do this by hand you can also handle cases like “x must be the square of a prime”: Either x \<= 9 or x \>= 25).

In your case, you just solve ignoring your condition. If your condition is fulfilled, great. Otherwise you solve the problem once with a (ts, it) = 1 added, and once with a (ts, it) = 0 and (one of the four conditions is not met) added.

---
Tags: linear-programming, integer-programming, constraint-programming
---


# Question
Title: How to calculate the time complexity if the upper bound is decreasing as well?
For example if the condition is i\<=n, and the n is decreasing in the loops, how can i calculate the time complexity? Lets say we have nested loops like below:

```
 for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            x = x + 1;
        }
        n = n - 1;
    }

```

Or if the decrement of n is being done in the inner loop:

```
for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            x = x + 1;
            n = n - 1;
        }
    }

```

# Answer
You do a bit of maths. To avoid confusion, assume we were given N and we first let n = N.

The outer loop will end when both i and n equal N/2. The number of iterations in the inner loop goes from N to N/2. So the inner loop is executed N/2 times, with 0.75N iterations on average, for a total of $0.375 \cdot N^2$ iterations.
> 0 votes

# Answer
In your second example, with a given n at the start of the inner loop, there will be n/2 iterations until both j and n are set to the original value of n, divided by 2.

So you have n/2 iterations with i = 1, n/4 iterations with i = 2 etc. with a total of less than n iterations.

Again, like in the first answer, you analyse what the code does and that will give you the answer. There’s no recipe.
> 0 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Runtime analysis of prime-set computation
I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :

we are maintaing a one pointer from node $i$ of the list $L$ to index $i$ of array $N$ and one pointer from index $i$ of $N$ to $i$th node of list $L$. We will use a doubly linked list in such a way that we mark each element of $N$ exacly once.

1. Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q\_{k-1}$.
2. Starting from the first node, walk up the list $L$ in increasing order until we find the smallest number $r$ in it such that $r\cdot i \ge k-1$.
3. Walk down the list $L$ (crucially, in decreasing order) from the node $r$, and for each $l$ in $L$, seen, mark the element $N\[i\cdot l\]$ and delete the node containing $i\cdot l$ from $L$ ( this node in $L$ is accessed through the pointer from the $(i\cdot l)$th location in $N$ ).
4. If $N$ has any unmarked element $\ge 2$, go back to first step

In the first round all the multiple of 2 will get marked. It is easy to verify that each element in the array will get marked just once.

> Question : How to show that above algorithm has Running time $O(k)$?

After first iteration all multiples of 2 will be marked in the array $N$ and all multiples of 2 will be removed from the list $L$. In the second iteration multiples of 3 and so on.

$$ \begin{align\*} \text{Total time}: &= c\_1k + c\_2\frac{k}{2} +c\_3\frac{k}{2 \times 3} +c\_4\frac{k}{2 \times 3 \times 5} + c\_5 \frac{k}{2 \times 3 \times 5 \times 7}+\cdots\\ &=k \left(c\_1 + c\_2\frac{1}{2} +c\_3\frac{1}{2 \times 3} +c\_4\frac{1}{2 \times 3 \times 5} + c\_5 \frac{1}{2 \times 3 \times 5 \times 7}+\cdots \right) \\ &= O(k) \end{align\*} $$

Reference : link

# Answer
> 0 votes
The key is already shown in your link: each composite number is marked only once in this algorithm.

Consider a composite number $x=p\_1^{\alpha\_1} p\_2^{\alpha\_2}\cdots$ where $p\_1\<p\_2\<\cdots$ are primes and $\alpha\_1,\alpha\_2,\ldots$ are positive integers. In the iteration for $p\_i$ ($i\>1$), note $p\_1^{\alpha\_1} p\_2^{\alpha\_2}\cdots p\_i^{\alpha\_i-1}\cdots$ has been deleted from $L$ in the iteration for $p\_1$ because $p\_1^{\alpha\_1} p\_2^{\alpha\_2}\cdots p\_i^{\alpha\_i-1}\cdots$ is a multiple of $p\_1$, so $x$ will not be marked in the iteration for $p\_i$. As a result, $x$ will be marked only once in the iteration for $p\_1$.

In each iteration, traveling the list costs the same asymptotically as the marking process, because each element in the list corresponds to a number to be marked.

Hence the total time is equal to the time for marking asymptotically, which is $O(n)$.

# Answer
> 0 votes
Now while this has a nice big-O value, you use one pointer in the array, and one node containing two pointers for every integer in this range.

Using for example 1GB of memory, you can construct a sieve with 1 bit for each odd integer, or 16 billion integers. Using 3 pointers per integer, using 4 byte per pointer lets you handle just 83 million integers, almost 200 times fewer.

---
Tags: algorithm-analysis, runtime-analysis
---


title: Enumerating proper intersections

text:
# Question
Title: Enumerating proper intersections
Let

* $U \subset \mathbb{N}$ be a finite universe set;
* $B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup\_{b \in B} b = U$, and if $b \in B$ then $b \subseteq U \wedge b \neq \emptyset$;
* $c(i) = \\{ b \in B : i \in b \\}$ be the set of all subsets containing element $i \in U$;
* $\cap(C) = \bigcap\_{b \in C} b$ be the intersection of all sets in $C \subseteq B$; And
* $\cup\_E(C) = \\{ i \in U : c(i) \subseteq C \\}$ be the *exclusive* union of all elements in $C \subseteq B$; here the word 'exclusive' stands for *proper*, in a sense that an element $i$ belongs to the exclusive union of $C$ iff. the sets containing $i$ ($c(i)$) are covered by $C$.

We say that an element $i$ *dominates* an element $j$ iff. $i \neq j$ and

$$\exists\_{C \subseteq B} (|C|\ge 1 \wedge i \in \cap(C) \wedge j \in \cup\_E(C))\tag{Dominance}$$

That is, $i$ dominates $j$ iff. the elements are different, and there exist some set of sets $C \subseteq B$ such that $i$ belongs to the intersection of $C$ and $j$ to the exclusive union $\cup\_E(C)$.

For instance, in the picture below, we have that:

* 1 dominates 2, 3 and 9: Since $1 \in \cap(\\{b\_1, b\_2\\})$ and $2, 3, 9 \in \cup\_E(\\{b\_1, b\_2\\}) = \\{1, 2, 3, 9\\}$;
* 5 dominates 6 and 9: Since $5 \in \cap(\\{ b\_2, b\_3 \\})$ and $6, 9 \in \cup\_E(\\{ b\_2, b\_3 \\}) = \\{ 5, 6, 9 \\}$; And
* The remaining dominance relationships;

A straightforward strategy for determining whether there is a dominance relationship between two elements $i$ and $j$, is to algorithmically check the condition $(\text{Dominance})$, which would take a time complexity of $\mathcal{O}(2^{|B|})$, as it would be required to enumerate the power set of $B$.

My question is, given a pair of elements $i$ and $j$, is there any strategy for determining whether such set of sets $C \subseteq B$ exist in a polynomial time?

# Answer
> 1 votes
Yes. If there is any $C$ that works, then taking $C = c(i)$ works \[\*\]. It is easy to compute $c(i)$ and then check if it satisfies your definition.

Better yet, the following is a simpler characterization of dominance: $i$ dominates $j$ if $i\ne j$ and $\forall b \in B$, $j \in b \implies i \in b$. This makes it easy to check for dominance in linear time, by iterating through all sets in $B$ and checking whether $j \in b$ and whether $i \in b$.

---

Footnote \[\*\]: Why is this true? It is easy to verify that if you have two candidates $C\_1,C\_2$, where $C\_1 \subseteq C\_2$, and if $j \in \cup\_E(C\_1)$, then $j \in \cup\_E(C\_2)$ too. So we might as well take $C$ to be as large as possible, subject to the restriction that $C \subseteq B$ and $i \in \cap(C)$, and then check whether $j \in \cup\_E(C)$. $c(i)$ is the largest such set.

---
Tags: time-complexity, sets, polynomial-time, enumeration, set-cover
---


# Question
Title: Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\\{0^m1^n:0\le m\le n^2\\}$ is not a CFL. Here is what I have so far.

Suppose for contradiction that it is a CFL and let $N$ be the pumping length. Set

$$ s = 0^{N^2} 1^N $$

Let $u,v,x,y,z$ be a decomposition $s = uvxyz$ such that $uv^ixy^iz\in L$ for every $i\in \Bbb N$, and $|vxy|\le N$ and $|vy|\>0$. If $vxy$ is entirely in the 0 block, we can pump it up and violate the conditions of the pumping lemma; likewise if $vxy$ is in the 1 block.

What I'm having trouble with is producing a contradiction if $vxy$ crosses from the 0 to 1 block. I can show, in this case, that $v$ must consist only of 0's and we can assume the number is strictly greater than 0. Likewise $y$ consists only of 1's and is not empty. Of course also $2\le |vy|\le N$.

But from here I'm stuck. I produced this formula for the total number of 0's in $uv^ixy^iz$:

$$ N^2 + (i-1)r $$

where $v=0^r$. The number of 1's is

$$ N + (i-1)s $$

where $y=1^s$. Since the pumping lemma implies that this is in $L$ then we must have

$$ N^2 + (i-1)r \le (N+(i-1)s)^2 $$

But I wasn't able to obtain any contradiction from this. Certainly if $i$ goes to infinity then this inequality is guaranteed to be true.

---

Because this seems like a dead-end, and I can't see why picking a different $s$ would be any better, I'm thinking perhaps I need to significantly change strategy. I thought about proving that the complement language is not a CFL but since CFLs are not closed under complementation, that shouldn't work right?

# Answer
> 1 votes
In the last case, you should consider $uxz$. It is useful to note that $(N-1)^2 \< N^2 - N$ if $N \> 1$.

Indeed, if we suppose $v= 0^r$ and $y = 1^s$, with $r \> 0$ and $s\>0$, we also have $r \< N$ (because $|vxy| \leqslant N$).

Then, $uxz = 0^{N^2 - r}1^{N-s} = 0^m1^n$. But: $$m = N^2 - r \> N^2 - N \> N^2-2N+1 = (N-1)^2 \geqslant (N-s)^2 = n^2$$ So $uxz\notin L$.

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


# Question
Title: How to modify Dijkstra's algorithm to model the path of an electric car?
I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks.

Somebody online asked (but nobody answered) how one would go about modifying Dijkstra's algorithm to determine if an electric car can travel to every town in a weighted, undirected graph with a limited number of recharges.

I was curious if anybody had any insight about this.

# Answer
Wanting to travel to every town transforms this problem into a Traveling salesman problem, and Dijkstra cannot be of any (known) help for that.

There is an easy reduction from TSP to your problem: consider that there is a recharge station only in the first town, and ask if it is possible to do a tour with only your battery.
> 2 votes

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


# Question
Title: A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem:

A directed graph $G = (V, E)$ is **singly connected** if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

I took this to mean the following: for each $u, v \in V$, there is at most one simple path from $u$ to $v$ in $G$.

According to this preprint, the authors of CLRS indicate that an algorithm can be created that runs in time $O(|V||E|)$ by doing a DFS from each vertex and if each DFS yields only tree and back edges then the graph is singly connected.

The authors of the preprint then proceed to provide an algorithm for dense graphs that runs in $O(|V|^{2})$. They state and prove the following theorem:

**Theorem 2.1**: Let $H$ be a strongly connected graph. $H$ is not singly connected iff at least one of the following conditions holds. The DFS search either yields a cross edge, a forward edge, or a vertex $v$ such that from the subtree rooted at $v$, there are at least two back edges to proper ancestors of $v$

Given this theorem, I'm a bit confused about the algorithm provided by CLRS. CLRS states that as long as the search only yields tree and back edges, the graph is singly connected. However, it would seem that the theorem above provides another case that CLRS do not consider. Namely, a vertex $v$ such that from the subtree rooted at $v$, there are at least two back edges to proper ancestors of $v$.

The definition for a singly connected graph provided by CLRS seems to be inclusive enough to include the kind of graph the preprint is considering, so I'm confused how to reconcile them. What am I missing here?

Also, how does the CLRS algorithm run in time $O(|E||V|)$? Wouldn't it be $O(|V|(|V|+|E|))$?

Here's the case I have in mind:

# Answer
Note that the algorithm by CLRS runs DFS for each vertex separately. Therefore, for the case you mentioned, the algorithm declares the graph as *non-singly connected* when performing DFS starting from the vertex $v$. In that case, one of the back edges will be a cross-edge in the DFS tree, thus declaring the graph as not singly connected.

Please note that, CLRS algorithm in a single DFS call, checks if the root vertex has at most one simple path to each of the other vertices; that's all.

And, yes I too believe that the running time complexity of CLRS algorithm should be $O(|V| (|V| + |E|))$. The running time complexity of $O(|V||E|)$ is incorrect since for the case when $|E| = 0$ it implies that the complexity is $O(1)$; however the algorithm must visits each vertex at least once.
> 1 votes

# Answer
After doing more research, I believe the author of the preprint wasn't clear on the algorithm provided by CLRS. I think what CLRS meant is the following: for each $u \in V$ , run DFS-VISIT(u). In particular, we only visit all nodes in the DFS tree rooted at $u$; we do not visit other trees. This indeed provides a $O(|V||E|)$ algorithm to determine whether a graph $G$ is singly connected. Since DFS-VISIT(u) $\in O(|E|)$ and we need to check all nodes in the worst case, the overall time complexity is $O(|V||E|)$. Here's the full explanation: https://www3.cs.stonybrook.edu/~cse548/548hw5sol.pdf
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal, depth-first-search
---


# Question
Title: Process Synchronization and Atomic Instructions
According to the book " Operating Systems Concepts ", ninth edition , page 210, we have the following statement :

> Many modern computer systems therefore provide special hardware instructions that allow us either to test and modify the content of a word or to swap the contents of two words atomically—that is, as one uninterruptible unit.

This means that an atomic instruction is an instruction that must run and complete without any interrupts. In the same page, we have :

> The test and set() instruction can be defined as shown in Figure 5.3. The important characteristic of this instruction is that it is executed atomically. Thus, if two test and set() instructions are executed simultaneously (each on a different CPU), they will be executed sequentially in some arbitrary order. If the machine supports the test and set() instruction, thenwe can implement mutual exclusion by declaring a boolean variable lock, initialized to false. The structure of process Pi is shown in Figure 5.4.

According to the above statement, we can add another characteristic to the atomic instruction, which is two atomic instructions cannot be executed simultaneously. I think this statement is valid if these two atomic instructions share the same variable `lock` and this make sense, because if two atomic operations ( like test\_and\_set()) operates on the same lock variable can be executed at the same time by two processes ( running in parallel on two cores ) and they wish to enter the critical section at the same time , then a race condition can occur. So can we say that an atomic instruction is an instruction that run without any interruptions and cannot run in parallel when it is called on the same lock variable on two or more different cores by two or more different processes or an atomic instruction is the one that cannot be interrupted and to achieve synchronization it should be supplemented by the capability that if two processes call it with the same lock variable then this atomic instruction cannot run on two processor simultaneously ?

# Answer
This is just a matter of wording. “Uninterruptible” implies that the instruction cannot execute in parallel with an identical instruction - that would be the ultimate interruption.

But that’s implementation details. The important thing is that these operations are *atomic*. That is *indivisible*. If the description contains multiple parts, then all these parts will happen simultaneously.
> 1 votes

---
Tags: operating-systems, synchronization
---


# Question
Title: Can Dijkstra's algorithm be used this way?
Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose distance to every other node on the graph is equal to zero. Can I run Dijkstra's algorithm (either alone, or with other DP functions) to return to the shortest path after trying all paths from a location on the graph (the dummy node), with an exit condition that once every node has been visited,return to zero? If the solution is ran with the dummy node as the starting point, the final result must contain the sequence "start - dummy node - end". Wouldn't this lead to the shortest Hamiltonian path?

# Answer
> 0 votes
I could be misunderstanding you, but the answer is no. Dijkstra's requires you to specify the start node and the end node, and returns the shortest path between them.(It can actually tell you the shortest path from the start node to every other node, but that isn't crucial here.) There is no reason that this path would contain all of the nodes of the original graph.

---
Tags: algorithms, graphs, graph-traversal, weighted-graphs
---


# Question
Title: Is the Theory of Computation Necessary for a General-Purpose Beginner?
I'm interested in developing a solid CS/Electrical Engineering foundation that would enable me to branch out in the future to any CS-related field. I've read other literature recommendations and have recently gotten ahold of Sipser's second edition Intro. to the Theory of Computation, contains the theories of finite automata, complexity, and computability.

As a noobie, I didn't expect the book to read like a math textbook, and I found it difficult to stay interested in the material as it was difficult to feel it's relevance to any kind of practical computation. I'm not terribly interested in theory, but I want to develop a deep understanding of computers.

Is there some other platform missing that would enable me to appreciate the TOC? Is the TOC simply a starting point that I must grind through?

# Answer
As a computer science student I suggest to have a look on theory of computation because the concepts in theory of computation have useful and vital applications used by general purpose languages and this theory has useful and easy solving problems through which Logical building, analytical thinking will be improved not only that many new technical skills will be improved.

Every one is beginner from beginning ,Even I don't know about this theory when I was young and I got fascinated after learning and solving questions on this theory ,it is fascinating for those who are interested in coding, debugging etc.

Through exploration of different field there will be a grasp of knowledge and will excel in their general purpose domains like machine learning, cloud servicing, ethical hacking

This is not just a theory but also makes us to understand to solve the real world problems in a simple way. Such a complex problems are solvable in affable and simple methods

In This way I message that theory of computation is a necessary for a general purpose beginner
> 0 votes

# Answer
You say you're seeking solid foundation in Computer science and Electrical Engineering. There is not a school in this world that teaches these subjects without teaching not only theory of computation, but also linear algebra, analysis, logic, and discrete mathematics. These *are* the foundations, and are unavoidable.

If we remove the words "science" and "engineering", then perhaps you can get by without the foundations. But you're not going to be an engineer of any sort.
> 0 votes

---
Tags: education
---


title: 3 bit binary multiplier?

text:
# Question
Title: 3 bit binary multiplier?
I have the following 2-bit binary multiplier

<sub>(source: wikimedia.org)</sub>

How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier?

I notice that there are 2 half-adders, and there are a bunch of ANDs to begin with. It is tricky to see a pattern here, I would normally use a truth table but there would be a wopping 64 combinations. Any other strategies I could use here?

# Answer
> 0 votes
There is a pattern in the first stage: the two pairs of *and*s stand for the four bitwise products. Then follows a three-bits adder stage with carries ($C\_0$ is immediate).

The generalization fill involve three triples of *and*s and two adders.

# Answer
> 0 votes
For an n-bit by n-bit multiplier you use $n^2$ ANDs which each give a single bit in some bit position. For example in a 64 bit multiplier $x\_{52} and $y\_{22} would be a bit in position 74.

You arrange this in columns for each bit position, then any three bits in the same position are added with a full adder, giving one bit in the same and one in the next higher position. You repeat this as long as you have three bits in the same position, and then you have two numbers to add. Each full adder removes one bit, so you need $n^2$ full adders arranged in c * log n levels.

Your mobile phone probably has a few dozen 64x64 bit multipliers with 4096 ands and 4096 full adders each.

---
Tags: computer-architecture, logic, circuits
---


# Question
Title: Is there an algorithm to detect race conditions in logic circuits?
I'm writing a logic gate simulator. I would like to prevent user from constructing circuits prone to race condition such as flip-flops, and instead provide them as separate building blocks. Is that possible?

**edit:** I've got an idea. I **guess** that race conditions can only arise from logic circuit outputs directly or indirectly affecting their own inputs. So one way to check their validity would be to compare the truth tables of their inputs and outputs.

example one: NOT gate feeding itself

```
    A = !A
A | A   A | !A
--+--  ---+---
T | T   T | F
F | F   F | T
the truth tables do not match!

```

example two: SR NOR latch

```
!(A || B) = C
!(C || D) = B
!((!(A || B)) || D) = B // C => !(A || B)

 A | B | D | !((!(A || B)) || D)           B | B
---+---+---+--------------------          ---+---
 F | F | F |          F                    F | F
 F | F | T |          F                    F | F
 F | T | F |          T                    T | T
 F | T | T |          F (wrong!)           T | T
 T | F | F |          T (wrong!)           F | F
 T | F | T |          F                    F | F
 T | T | F |          T                    T | T
 T | T | T |          F (wrong!)           T | T

```

I hope you understand what I'm trying to convey. However, I have nothing to back it up, and I struggle to define it into an algorithm, and even if I could, it would have horrible complexity. I will try to refine it tommorow.

online truth table generator tool I used

**edit 2:** this is what I found in logisim manual:

> Logisim will not attempt to detect sequential circuits: If you tell it to analyze a sequential circuit, it will still create a truth table and corresponding Boolean expressions, although these will not accurately summarize the circuit behavior. (In fact, detecting sequential circuits is provably impossible, as it would amount to solving the Halting Problem. Of course, you might hope that Logisim would make at least some attempt - perhaps look for flip-flops or cycles in the wires - but it does not.) As a result, the Combinational Analysis system should not be used indiscriminately: Only use it when you are indeed sure that the circuit you are analyzing is indeed combinational!

However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

# Answer
> However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

There are two different problems here. The simple solution (**the one you should implement, in my opinion**) is to simply look at the connection graph of the gates, and detect if the *graph* contains any cycles. If yes, simply reject the input.

The problem logisim refers to, which would amount to solving the halting problem, is one where *you allow cycles*, but *reject sequential circuits*.

This is different, because not every cycle in the graph affects the output, or worse, it affects the output but not in an sequential way.

> However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

Initially I disagreed, but after some more thinking, I agree. Do note that we have infinite time here - we can supply infinite sequences of inputs to the circuit in an attempt to get sequential behavior.

Under the condition that we always let a circuit stabilize before changing the inputs (or rejecting the circuit as sequential in case it never stabilizes), a finite circuit is a finite state machine. The crux is that the output of the circuit depends on the input *plus* the internal state of every gate in the circuit.

To prove that a circuit is non-sequential you can use the following algorithm:

1. Add the all-zero internal state to a queue.
2. While the queue is not empty, pop an internal state from the queue and construct the truth table for all inputs using that initial internal state. Also add the internal state to some set tracking internal states we have handled. For each internal state reached from this internal state while computing the truth table, add it to the queue if it's not inside our handled set.
3. If at any point in 2 a circuit does not stabilize, return sequential. If at any point during 2 the generated truth table does not equate the one from the all-zero internal state, return sequential. Otherwise return non-sequential.

Since there are a finite amount of possible internal states, this algorithm always terminates. And it fully explores all reachable states. Nevertheless, this algorithm is very, very much infeasible.
> 1 votes

# Answer
Let’s say somewhere in your circuit there is a logical AND calculating a AND b. Now as you change the inputs that change will move through your circuit and change things.

a and b start with a certain state. The inputs can affect them in faster and slower ways, until eventually the outputs are stable. Now it is possible that a = true and b = false and both change simultaneously. The output should stay false. However they never change simultaneously so b could change to true *just* before a changes to false so the output could change for a tiny amount of time. That’s something you want to avoid.
> 0 votes

---
Tags: algorithms, logic
---


# Question
Title: Halftone Circle Pattern Algorithm Implementation
The problem is implementation of specific halftone circle pattern algorithm, which should generate a bitmap image composed of **black** and **white** **circles** reflecting the halftones of the original image. When viewed from a distance, the image should display smooth shading, but up close, it should consist of only pure white or pure black circles.

The most similar result I could find is the halftone screen option in Photoshop:

```
Image -> Mode -> Bitmap -> Halftone Screen -> Round shape

```

Below are examples of the source and result images: Source image:

Result image (input DPI: 83, result 300 pixels/centimeter):

As demonstrated, the primarily dark areas contain white circles, while the primarily bright areas have black circles.

The fundamental concept of halftoning involves mapping pixel intensity to the size of the target circle by following these steps:

* Obtain the average intensity of the pixel group in the area.
* Draw the dot such that its surface area is proportional to the average intensity percentage (from white to black).

This approach may produce images like this:

However, this outcome does not align with the goals, as it only consists of circles of one color and features overlapping circles that create undesirable "stars."

On a closer look on Photoshop's algorithm, we can see that the primary challenge lies in the transition areas. When the average pixel intensity between black and white is 50%, the algorithm forms squares and then smoothly transitions from black circles on white areas to white circles on black areas:

Real example of this haltone algorithm:

Looking for assistance with the mathematics and algorithms that could produce a similar output!

# Answer
Consider the surface of equation $z=(1-x^2)(1-y^2)$ in the domain $\[-1,1\]\times\[-1,1\]\times\[0,1\]$.

The cross-section by the plane $z=0$ is a square, and when you move it up, it progressively turns to a circle.

Now you can rotate the coordinates and work with $x=u+v,y=u-v$ to make the square a diamond. Fill a cell with white when the function exceeds $z$ and black below, and black outside the diamond (or conversely).

A last difficulty is to linearize the scale, i.e. find the $z$ that corresponds to a desired fraction of the area. Analytic integration might be difficult. You can tabulate once for all for different values of $z$ by simple pixel counting, and resort to inverse interpolation. Accuracy is not critical.
> 1 votes

# Answer
I have 'solved' this, but I could use some help figuring out how to apply it correctly as a pattern to grayscale images at different angles.

The solution uses rectangles whose corner radius changes. When the corner radius is half the length of the sides of the rectangles, they will appear to be circles.

My solution is here: https://editor.p5js.org/corbinlinder/sketches/IlTJpWDT5?fbclid=IwAR3BABd1\_XLH4FvPPEGzdOBu5cE2im7RcJUxkhuPlwDFsMHmTnMDR9VWCCc

I generated 256 grayscale images, each with a different L value between 0-255. I then used Photoshop to generate those images' round halftone bitmap version. I then used those images to create an animation in which I could use a slider and mouse wheel to move between frames. By doing this I was able to notice that the circles were actually rounded rectangles.

The reference animation is here:https://editor.p5js.org/corbinlinder/sketches/p51wiEcar

I just don't know where to go from here.
> 0 votes

---
Tags: algorithms, computer-graphics
---


# Question
Title: Derivation trees to show a given grammar is ambiguous
Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string can be produced with these rules through more than one leftmost or rightmost derivation, then the grammar is ambiguous.

As such, I tried to get two ways that derive the string "ab" using leftmost derivations: \begin{align} S \Rightarrow aSb \Rightarrow a\lambda b \Rightarrow ab\\ S \Rightarrow SS \Rightarrow aSbS \Rightarrow a\lambda b\lambda \Rightarrow ab \end{align}

Because there are two different leftmost derivations of the same string "ab", the grammar must be ambiguous.

However, my professor indicated to me that my answer is wrong, and I did not use all the production rules. I thought I had, though. He told me I could instead derive the string "aabb" to prove the ambiguity, but I don't know what would make that fundamentally different.

Can anyone help explain why this relatively simple string "ab" doesn't work, at least as I attempted to prove it? Thanks!

# Answer
> 1 votes
I believe your professor is wrong. You exhibited two leftmost derivations, which is all that is required to show a grammar is ambiguous. Although, one small thing: $S \Rightarrow SS \Rightarrow aSbS \Rightarrow a\lambda b\lambda \Rightarrow ab$ should have another rule as you have followed two rules at once, $S \Rightarrow SS \Rightarrow aSbS \Rightarrow abS \Rightarrow ab$ (in other words, you eliminated two $S$ variables at once). Also, as you have mentioned, you actually did use every production rule.

# Answer
> 0 votes
if the ambiguity was the problem, then your solution is completely correct, showing 1 example, where derivation isn't unique is enough to prove that grammar is ambiguous in this case.

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


title: Graph Algorithms (SSSP vs MST)

text:
# Question
Title: Graph Algorithms (SSSP vs MST)
I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to understand why (and also to come up with a counter example)...

# Answer
> 1 votes
A graph with a unique MST $T$ can definitely have a SPT that differs from $T$.

In fact, there are graphs where both the MST and the SPT (from a given source) are unique (so it doesn't matter which algorithms you use to compute them) and these two trees differ.

Consider for example a triangle graph with vertices $1,2,3$ and edge weights $w(1,2)=w(2,3)=2$, $w(1,3)=3$. The only MST contains the edges $(1,2)$ and $(2,3)$. The only SPT from $1$ contains the edges $(1,2)$ and $(1,3)$.

---
Tags: graphs, weighted-graphs
---


# Question
Title: Constructing a PDA for the language $\{a^mb^n | m > n\}$
i saw in a book how to construct a PDA for a case with *m* is equal to *n* . It's pretty simple, just push a symbol for every **a** and pop this symbol for every **b** that the PDA reads. But, i don't found a way to construct a PDA for this particular case. Every help is welcome.

# Answer
> 2 votes
You can think about the scheme you proposed (push a symbol for every a, pop for every b) as using the stack as a counter. When you see an a, you increment the counter (push a symbol onto the stack) and when you see a b, you decrement the counter (pop from the stack). In the case where $m=n$, the stack should be empty after processing the whole string, or in other words the value of the counter should be 0. Following the same scheme, how would we know from the count that $m \> n$? What would the stack have to look like in that case?

# Answer
> 0 votes
According to me if no. of a's is greater than no. Of b's and once the pushing of string a is completed in the stack then we start popping out every a for every b we get,then at last more than 1 no. Of a will be left in the stack as no. Of a's is greater in no..Hence keeping this concept in mind you can draw the transition diagram and table as well.

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