# Question
Title: Determine whether a flow can satisfy node demands in a directed acyclic graph
I have the following problem that I'm unsuccessfully trying to solve:

I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - the nodes merely demand that there would be a flow of strength *k* flowing through them. The graph is acyclic, however, it is not a tree - multiple routes exist from the higher to the lower nodes.

The question is, whether a flow of strength *R* can satisfy all of the nodes' demands. Of course, a flow with strength more than *k* can flow through a node with demand *k*. Also, there are no capacity limits in the input graph.

I need to reduce this problem to the max-flow problem. I have been trying to reduce it to Circulation with lower bounds and Circulation with demands, but unsuccessfully, as I am unable to find out a good way on how to somehow limit the flow in the nodes to be minimal while satisfying the demands and measuring it at the same time.

# Answer
> 2 votes
Add a new source $s'$ and the edge $(s', s)$ with maximum and minimum capacity $R$.

For each vertex $v$ with demand $d$ do the following:

* Replace $v$ with two vertices $v\_1$ and $v\_2$.
* Replace all the former edges $(u,v)$ with $(u, v\_1)$
* Replace all the former edges $(v, u)$ with $(v\_2, u)$.
* Add the edge $(v\_1, v\_2)$ with minimum capacity $d$.

The problem is now equivalent to checking whether there exists a feasible flow in a network with minimum and maximum edge capacities.

This problem is well known and can be reduced to max-flow (see, e.g., "Balances and Pseudoflows" in the book Algorithms by Jeff Erickson).

Essentially, if $D$ is the sum of all the edges' minimum capacities:

* Add a new source vertex $s^\*$ and a new target vertex $t^\*$.
* Add the edge $(s^\*, s')$ with maximum capacity $+\infty$.
* For each edge $(u,v)$ with minimum capacity $c \neq 0$ and maximum capacity $C$, add the edge $(u, t^\*)$ with capacity $c$, the edge $(s^\*, v)$ with capacity $c$, remove the minimum capacity from $(u,v)$, and change the maximum capacity of $(u,v)$ to $C-c$ (if $C$ was $+\infty$ then the new capacity is also $+\infty$).
* Check whether the maximum flow from $s^\*$ to $t^\*$ is equal to $D$.

---
Tags: graphs, network-flow
---


# Question
Title: Karp reduction from optimization problems to decision problems
When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.

Focusing on Cook reductions, there exists a natural Karp reduction from the decision version of a problem to optimization version. Is the converse also true?

# Answer
> 1 votes
Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.

---
Tags: np-complete, reductions, np, decision-problem, polynomial-time-reductions
---


title: Algebra for min/max bounds

text:
# Question
Title: Algebra for min/max bounds
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, including the two sets in question and some other ones too. I won't know anything about individual element membership, so need to operate at the set level, and would like to be able to determine whether $a \subseteq b$ is implied by the given constraints.

This sounds like the sort of thing that's been studied before (e.g., for SMT solvers or linear programming), but I can't seem to hit the right keywords to search on. Are there known efficient representations/algorithms for this sort of problem?

---

Here's what I've roughly thought of doing:

```
type Set = Symbol;
type Bound = {kind: 'upper' | 'lower', arg: Set};
type Constraint = {kind: 'lt' | 'gt', arg: Bound};

const max = (b1: Bound, b2: Bound): Bound => ...;
const min = (b1: Bound, b2: Bound): Bound => ...;
const checker = (a: Constraint, b: Constraint): bool => ...;

```

My idea would be to build two `Constraint`s, one for $a$ and one for $b$. $a$ would have a `lt` constraint and $b$ would have a `gt` constraint. I suspect `Bound` forms an algebra with `max` and `min`, which would allow me to put two `Bound`s in quasi-canonical form and break things down that way.

I'm not certain this will work, so before I spend several hours fleshing this out figured I'd ask if this had been solved before!

# Answer
> 2 votes
After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be translated to `x -> y`, the final `checker` would simply look for a path between $a$ and $b$ in this graph. (Using DFS or BFS per this SO question).

# Answer
> 1 votes
You can identify each set $A$ with a unary predicate $A(x)$. For example, the constraints $A \subseteq B$ and $B \subseteq C$ correspond to the constraints $$ \forall x \\, A(x) \to B(x) \\ \forall x \\, B(x) \to C(x) $$ Suppose we want to understand whether these constraints imply $A \subseteq C$, that is $$\forall x \\, A(x) \to C(x)$$ This holds if for every particular element $x$, $$ (A(x) \to B(x) \land B(x) \to C(x)) \Rightarrow (A(x) \to C(x)) $$ To check whether this is a tautology, we can replace all predicates with Boolean variables: $$ (A \to B \land B \to C) \Rightarrow (A \to C) $$ We have obtained a problem which can be handled by a SAT solver.

In this way you can also express Boolean operations such as union, intersection and complementation.

---
Tags: lower-bounds, constraint-satisfaction, upper-bound, algebra
---


# Question
Title: How to prove finding two paths that are at least k edges apart is NP-hard?
Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s\_1$ and $s\_2$ and two end vertices $t\_1$ and $t\_2$ is there a path from $s\_1$ to $t\_1$ and $s\_2$ to $t\_2$ such that the closest number of edges between the two paths is at least $k$? Two paths are $k$ close if the minimum of the shortest distances between any vertex on the first path to any vertex on the second path is $k$.

I was thinking of reducing from 3SAT and letting the first path represent the variables and the second path represent the clauses, but I am unsure where to go from there.

# Answer
> 1 votes
You can reduce from 3SAT.

The graph has two parts. One part is the "variable" part. For each of the variables $v\_1,\ldots,v\_n$ there are two three vertices $v\_i^+,v\_i^-,v\_i$, and this part consists of the following edges, for $i \in \[n\]$:

$$(v\_{i-1},v\_i^+),(v\_{i-1},v\_i^-),(v\_i^+,v\_i),(v\_i^-,v\_i)$$

Here $v\_0$ is a new vertex, identified with $s\_1$, and $v\_n$ is identified with $t\_1$.

The second part is the "clause" part. For each of the clauses $C\_1,\ldots,C\_m$ there four vertices $w\_j^1,w\_j^2,w\_j^3,w\_j$, connected much as before, with $s\_2$ and $t\_2$.

We connect $v\_i^b$ with $w\_j^r$ via a path of length $k$ (for some large enough constant $k$) if the literal $v\_i^b$ (either $v\_i$ or $\overline{v\_i}$, according to $b$) is the *opposite* of $j$'th literal in $C\_j$.

Also, we take all the mindpoints of these paths, and connect all of them (making them into a clique).

We can think of an $(s\_1,t\_1)$-path as a truth assignment, and of an $(s\_2,t\_2)$-path as identifying a satisfied literal in each clause. The minimal distance is more than $k$ if this is indeed the case, and only $k$ otherwise.

You also need to verify that there is no point for the paths to cross between the parts. If only one of the paths crosses, then the two paths will be close together (at some constant distance, which for large enough $k$ will be smaller than $k$) immediately after the crossing. If both cross, then the midpoint clique will ensure that they are at distance at most 1.

---
Tags: graphs, np-hard, 3-sat
---


# Question
Title: How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1?
I can't figure out how to find a good asymptotic approximation for the following recurrence relation: $$T(n) = T(n/2) + T(n/3) + 1.$$

# Answer
You can write your recurrence as $$ T(n) = \sum\_{i=1}^k a\_i T(b\_i x + h\_i(n)) + g(n) $$ with:

* $k=2$
* $a\_1 = a\_2 = 1$
* $b\_1 = \frac{1}{2}$, and $b\_2 = \frac{1}{3}$
* $h\_1(n) = h\_2(n) = 0$
* $g(n) = 1$

From Akra–Bazzi theorem, the solution to your recurrence is $T(n) = \Theta\Big( n^p \big(1 + f(n)\big)\Big)$, where $p$ is such that $a\_1 b\_1^p + a\_2 b\_2^p =1$ and $f(n) = \int\_1^n \frac{1}{u^{p+1}} \text{d} u$.

Substituting, we have $2^{-p} + 3^{-p} = 1$, which shows that $0.78 \< p \< 0.79$.

Therefore: $$ f(n) = \int\_1^n \frac{1}{u^{p+1}} \text{d} u \le \int\_1^\infty \frac{1}{u^{p+1}} \text{d} u = \frac{1}{p} = \Theta(1), $$

and the solution to your recurrence is $T(n) = \Theta( n^p )$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Minimum amount of time for two enemies to reach their destinations?
Given an undirected, unweighted, and connected graph $G = (V, E)$, what is the minimum amount of time it takes for party $X$ to go from $s\_x$ to $t\_x$ and party $Y$ to go from $s\_y$ to $t\_y$? At each unit of time, $X$ and $Y$ can either move to a vertex adjacent to their current position or not move at all. $X$ and $Y$ are enemies with each other and if they go less than a distance of $k$ to each other they will go to war. The distance of $X$ and $Y$ is defined as the number of edges between them on the shortest path. What is an efficient algorithm to find the two optimal paths such that $X$ and $Y$ do not go to war and they both reach their destinations in the minimum amount of time? Note that the two paths can share edges as long as $X$ and $Y$ do not go less than k units of each other during their traversal. In the example below with $k$ = 1 the optimal path for $X$ is in blue and y is in red. This allows for both $X$ and $Y$ to reach their destination in two units of time Notice, if $X$ instead took the black path, this would be suboptimal as $Y$ would have to rest for one unit of time as $X$ moved out of the way. (This would take 3 units of time.)

So far I've started by computing the shortest paths between all pairs of vertices in $V$ by doing a BFS at each vertex. This will take $O(EV)$ Then, I suggest the following greedy algorithm:

At each time tick, $X$ and $Y$ should move to the vertex that is closest to their destination. If that vertex is less than k edges from the other party, choose the next closest vertex and so on. If no such vertex exists, then the current party will rest until the other party moves at least k units away from any of the adjacent vertices. Give priority to $X$ or $Y$ based on who has fewer options.

However, I don't think the greedy solution will work. Some other ideas include A\* or a max flow reduction.

# Answer
Generate the graph $G'$ of all legal configurations. A legal configuration is an ordered pair of vertices $\langle u, v \rangle$ in $V^2$ such that $d\_G(u,v) \ge k$, where $d\_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.

There is an edge from $\langle u\_1, v\_1 \rangle$ to $\langle u\_2, v\_2 \rangle$ in $G'$ if and only if $d\_G(u\_1, u\_2) \le 1$ and $d\_G(v\_1, v\_2) \le 1$.

The amount of time you are looking for is now equal to $d\_{G'}(\langle s\_x, s\_y \rangle, \langle t\_x, t\_y \rangle)$.
> 0 votes

---
Tags: graphs, breadth-first-search
---


title: Deletion in a Binary search Tree

text:
# Question
Title: Deletion in a Binary search Tree
The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works theoretically).

Algorithm:

```
abc_delete(T, z) // z is the node that must be eliminated
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

```

For example, I want to delete the node number $7$:

But, shouldn't the end result be this?

# Answer
> 1 votes
You choice is certainly correct.

However, there is nothing wrong with your teacher's code, either. Here is an excerpt from CLRS.

> The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold.

We certainly prefer the operation be made in the easiest way or the fastest way. However, there is no requirement the modification must be made in the easiest way or even in any easy way. Nor does it require that the modification be made in the fastest way or even in any fast way. All it requires that the operation of deletion should produce another binary search tree that has all nodes from the given binary search tree without that specific node (and no more nodes). How those remaining nodes form a binary-search-tree is completely free of restraints.

Your teacher's code, on the other hand, is probably the shortest clear code that does the job. The more I study it, the more ingenuity I find.

# Answer
> 0 votes
Your drawing is the correct solution, however ur parsing to ur teacher code is not accurate (u mis interepreted the code)

When I first saw ur Q I didn't read the code thoroughly & I thought (from the 1st pic/drawing) ur teacher is performing a delete operation for a special kind of BST that has extra conditions than the relative order, but this is not the case

When deleting from a BST (trying to follow ur code variables, Z is the node to be deleted)

If Z is a leaf node (no children) just replace the parent pointer to it with NULL

if Z has 1 child (whether left or right doesn't matter) make the parent pointer points to its only child

That's very simple coding, in a semi pseudo code

If (Z.left == NULL) { Physical\_Delete(Z, Zright); return(); //either we have only right subtree or none }

// Here we r sure there is a left subtree

If (Z. right == NULL) { Physical\_Delete(Z, Z.left); return(); }

//physical\_Delete has the replacement as the 2nd parameter, all the loops in ur teacher code is to find out what is it incase we have two subtrees

If Z has 2 children, then u have to elect one of them to take its place, and here comes ur teacher's code (not in the previous case)

In ur pic imagine u r deleting "5" this long code is for adjusting the remaining subtree of its 2 children (how to link 7 & 3 & their children to node 12 keeping the BST constrain)

If u need detailed tracing we may do that, but only if u found this helpful as a start

---
Tags: algorithms, binary-trees, search-trees
---


# Question
Title: Does checking the middle bit of an input require a log(n) space pointer?
Let `n` be an even integer.

Let `i` be an input of length `n`.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We cannot overwrite the input tape.

We have finite amount of working-memory tapes to compute with (in case more than 1 is useful).

Space-complexity is the maximum amount of non-empty tape cells to ever appear across all work tapes at any point during the execution.

(That way, in practice, this can correspond to virtualizing a Turing machine and adding or removing physical hard drives to back each logical working-memory tape.)

Each pointer can be moved left or right one cell.

One way to decide the problem is with a counter of length `O(log(n))`: Initialize to 0's, then increment until the counter equals `n/2`, then check the bit.

That takes `O(log(n))` space.

Can we do better? Or is `O(log(n))` the best space-complexity we can do?

If we can do better, in general, then there's a system of representing integers more space-efficient than polynomial bases (decimal, binary, etc.).

For example, if we had access to the corresponding busy-beaver machine for `n/2`, then we could use that (and instead of printing out a 0, we could move our input tape by 1). However, in general, we cannot compute the (optimal) busy-beaver for `n/2`.

So, is there a way to compute a "sub-optimal busy-beaver" and use that to get to `n/2` instead of a `O(log(n))` counter?

# Answer
> 1 votes
You can do this with constant amount of memory (according to your definition of space complexity). Assume $n \ge 2$ (the complementary case is trivial). Mark the work tape on the starting position of the input, then move right until you reach the end of the input and mark the last position of the input on the work tape.

Repeat the following:

* Go back to towards the beginning of the input until you find a marked position on the work tape.
* If the position immediately to the right is already marked, report the current position as the middle of the input.
* Otherwise, remove the mark from the current position (i.e., write the empty symbol), move right, and mark the current position.
* Advance towards the end of the input until you find a marked position on the work tape.
* If the position immediately to the left is already marked, report that position as the middle of the input.
* Otherwise, remove the mark from the current position, move left, and mark the current position.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: When setting a variable in python, why does the order matter?
```
def calculate_error(m, b, point):
    x_point, y_point = point
    y = m*x_point + b
    distance = abs(y-y_point)
    return distance

print(calculate_error(2, 0, (5, 5)))

```

I ran the code above and it worked. But I do not understand why it doesn't work when I tried setting point = x\_point, y\_point instead?

# Answer
In most programming languages, the `=` operator is an *assignment operator* which *assigns* to the left the *values* on the right.

Sometimes there are variations on the semantics, but it rarely means *equal*.

Coincidentally, though, which may cause confusion, after `x = y`, that is, after `x` has been assigned the value of `y`, the two values are equal, denoted in many languages (including Python) with `x == y`.

Hence, if you write

```
y = 3
y = x

```

the program crashes because `x` hasn't been given a value.
> 1 votes

---
Tags: python, syntax
---


# Question
Title: Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)
Let `n` be an even integer.

Let `I` be an input of length `n`.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We may move the pointer left or right. We cannot overwrite the input tape.

We have a single working-memory tape to compute with. We have a single pointer to it. We may write a 0 or a 1. We may move the pointer left or right. We may not move to the left of, or overwrite the start symbol of the working-memory tape. The working-memory tape is initialized to either the start symbol or immediately to the right.

Space-complexity is the position of the largest cell we write to. This way we "reuse" space.\[1\]

One way to decide the problem is with a counter of length `O(log(n))`: Initialize to 0's, then increment until the counter equals `n/2`, then check the bit.

That takes `O(log(n))` space.

Can we do better? Or is `O(log(n))` the best space-complexity we can do?

\[1\] If space complexity was just the total in-use space at any given point in time, we could "move around" the space we're using, using a larger total range of space, but only a smaller portion at any point in time. Defining space as the max position keeps us from "moving around" the space we're using.

# Answer
You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all!

(The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make do with constant additional space, by implementing the pointers as spaces.)
> 1 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: How does a hard drive knows what bit is the beginning of of a byte/word?
I'm guessing I could replace the words "hard drive" with "random access medium" but let's be more specific here. Also for the sake of this question, let's not consider SSDs. Just plain old hard-drives with heads and magnetic discs.

I'd guess that the hard drive doesn't care about things as bytes and receives instructions from the OS on about where to move it's head, but that'd assume that the OS has knowledge of sectors, cylinders or whatever physical properties of the drive and it's stored data so that doesn't feel right.

So, how does this work?

# Answer
Simplified, the operating system sees disk storage as a randomly accessible set of sectors, each sector containing some fixed number of bytes. The OS asks the disk controller for a sector using some standard protocol and it is the responsibility of the disk controller to retrieve the sector with the bits and bytes in the same order in which they were written. The communication protocol (e.g. SCSI) specifies both bit and byte order for reads and writes so there is no space for confusion about where the data starts and stops.

Operating systems can and do take into account the characteristics of storage media for the sake of efficiency, such as existence of onboard cache, rotational delays, and head movement, but those things have no bearing on where bytes and sectors start.
> 2 votes

# Answer
Prior to the 1990s, disk drives were somewhat like a tape recorder with a short loop of tape, and an ability to move the drive head to select a track. Information is written to disks using sequences of magnetic pulses with varying amounts of time between them. Depending upon the physical properties of the media, there will be limits as to the minimum and maximum amounts of time between pulses, as well as the timing accuracy with which that time can be measured. To allow for this, bytes are encoded using different patterns of pulse lengths. Certain patterns of pulse lengths will never appear in data and are thus used as synchronization markers.

When a disk is low-level formatted, the head is moved to each track and set to record, at which time the drive will then write the sequence "sync marker + sector header, short gap, sync marker + sector data, longer gap" once per sector. Each sector header contains the sector number recorded within it; to read a sector, the drive starts by listening for a sector header with a proper sector number, and then once that is heard, listens for the next sync marker and captures the data that follows. To write a sector, the drive waits for the sync marker for the proper sector, switches to write mode, writes a sync marker along with the proper data and a small amount of trailing junk which is guaranteed not to look like a sync marker, and switches to read mode.

Note that while a drive is reading data, it can "round" pulse widths up or down so as to tolerate variations in rotation speed. When writing a sector, the widths of pulses will be fixed independent of rotation speed. Thus, speed variations may cause an overwritten sector to not precisely match the length of the original. The gaps between sectors make it possible for a drive to tolerate this imprecision, but such imprecision makes it impossible to write part of a sector. Effectively, every separately-writable area of the disk must be preceded by a sector header and followed by a gap. The more finely one wants to be able to update individual chunks of data, the larger the fraction of overall space that will be devoted to the headers and the gaps.
> 1 votes

# Answer
I think that you should first bear in mind that computer architecture is based on the mechanism of abstraction in order to make it easier, for instance, to manage and access data, and avoid the hurdle of having to take care of the specific hardware that needs be accessed.

Having said that, you can understand that the OS itself can't be allowed, also for efficiency reasons, to make distinctions between an USB or an hard disk access and so on. This premise is to confute the fact that the hard disk "doesn't care about bytes" and that the resolution of the data address is all on the OS. In fact, the hard disk DOES have an internal controller and circuitry that needs to identify and translate the address that the OS requests in the number of disk, cylinder and sector, the xyz coordinates in HD technology. The operating system instead interfaces with a file system that is built based on the disk content, without overweighting it with more "circuitry matters"
> -1 votes

---
Tags: memory-hardware, memory-access
---


# Question
Title: Why is the Nintendo Entertainment System (NES) referred to as an 8-bit system, rather than a 1-byte system?
As far as I've understood it, referring to this system as an 8-bit system points out that one can access 8 bits of data in one instruction.

While I understand that we're not saving vast amounts of time by calling it "one byte" instead of "eight bits", is there a particular reason why the latter is/was preferred?

# Answer
> 80 votes
"Back in the day" computers were defined more by their word size, for example the PDP-8 had 12-bit words composed of two 6-bit "bytes". A "nibble" was half a byte, or 3 bits in this case (and here the op codes were 3 bits).

It is only in recent decades that 8-bit bytes became so prevalent as to make them the default.

Calling the NES 8-bit is less ambiguous than calling it 1 byte, keeping in mind we're talking about a system that came out in 1983.

# Answer
> 44 votes
A) Historically, machines have been characterized by number of bits per 'machine word'. Why should NES be handled differently?

B) Calling it a 'byte' is not as clear since historically a 'byte' has not always been composed of eight bits (e.g some early machines had six bits per byte). Admittedly this is not so strong a point anymore.

C) On a side note: I don't think saying 'one byte' actually saves any time compared to saying 'eight bit(s)'.

# Answer
> 1 votes
It is true that in more modern computer architectures, 8 bits is roughly synonymous with a single byte. However that doesn't always mean that we count things in bytes.

Think about a soft drink, maybe a Coca-Cola or something. What are some typical sizes it might be sold in? I will use my memory of Japan and the US as examples:

```
Japan:     US:
375 mL  ~  12   fl oz
500 mL  ~  16.9 fl oz
           20   fl oz
  1 L   =  1    L
  2 L   =  2    L

```

Notice that, even on Japan's side of the chart, we're switching between units: milliliters and liters. ...Could we just as easily say things like "1000 mL" and "2000 mL", or either ".375 L" and ".5 L"? Yes, absolutely!

Then why don't we? *Because as the general size of the drink container is scaled, the units that we find most useful scale with it.*

So think of the NES, which was an 8-bit system. Later you had the Sega Genesis and SNES, which were both 16-bit. The original PlayStation was 32-bit, the N64 (Nintendo likes abbreviations, don't they?) was 64-bit, the Sega Dreamcast was 128-bit, and so on.

Have you ever heard of a normal 64-***byte*** or 128-***byte*** computer architecture? No, of course not. Even the Sega Dreamcast and similar systems had merely *"8-byte" architectures*. And as other answers have stated, 8 bits hasn't always been completely synonymous with a single byte.

(And to be completely pedantic, 8 bits aren't exactly the same thing as a byte on anything, since they could each belong to different bytes, if you just pick them out randomly. A byte is technically an ordered ***collection*** of bits.)

Think about how tiny a single computer instruction is. It is *small* compared to a lot of what we would normally count in bytes. In fact, when you're dealing with Assembly, you're dealing with quite a lot of detail, including individual bits.

So in the same way that we go from measuring soft drink sizes in liters to milliliters, just because of the scale being different, we go from measuring things in bytes and gigabytes to individual bits, just because of the scale.

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


# Question
Title: Probabilistic Turing machine - Probability that the head has moved k steps to the right on the work tape
I have a PTM with following transition:

$\delta(Z\_0, \square , 0) = \delta(Z\_0, \square , L, R)$,

$\delta(Z\_0, \square , 1) = \delta(Z\_0, \square , R, R)$

Suppose that this PTM executes n steps. What is the probability that the head has moved k steps to the right on the work tape (in total, i.e., k is the difference between moves to the right and moves to the left) ?

# Answer
It seems to me as first thought, it is the summation of all moves i to R, j to L where
( i+j = n) AND (i - j = k) which leads to
i =(n+k) /2

Assuming the prob of each step of the walk is indep. from the current position (I can't read the probs u r writing, the 2nd parameter is appearing as a square). So, it would be something like

Pij= (PR ^ i) * (PL ^ j)

Ps

(I'm talking probability, I do not have a fresh memory of Probabilistic Turing m/cs at the moment)
> 0 votes

---
Tags: turing-machines, probabilistic-turing-machines
---


# Question
Title: How to wiggle sort an array in linear time complexity?
The wiggle sort is nums\[0\] \< nums\[1\] \> nums\[2\] \< nums\[3\] \> nums\[4\] ...

For an input: `nums = [1, 5, 1, 1, 6, 4]`, the expected output is `[1, 4, 1, 5, 1, 6]` and there can be many other possible outputs satisfying the aforementioned criteria.

I realised that the problem has a pattern: nums\[1\] will be greatest among nums\[0:3\], nums\[3\] will be greatest among nums\[3:6\],...

So, I targeted at getting the next greatest element. This made me implement the heap:

```
import heapq

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_heap = []
        for num in nums:
            heapq.heappush(nums_heap, -1*num)
        i = 1
        while i < len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2
        i = 0
        while i<len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2

```

However, the time complexity of my solution is O(n) along with O(n) space complexity. I want to solve this in O(1) space complexity and that would require me to not use heap(extra space).

How to do that?

The complete question is also posted here.

# Answer
### Some characterizations of wiggle-sort

Skip this section if you would like to see the algorithms right away.$\def\A{\mathcal A}$ $\def\S{\mathcal S}$

Given an array $\A=(\A\_0,\A\_1, \cdots, \A\_{n-1})$ of numbers, let us call the $\lceil n/2\rceil$-th smallest entry in $\A$ as well as each entry that is equal to that entry a **median** of $\A$. (This definition of median differs slightly from its usual definition when $n$ is even. For example, the median of $(3,4)$ is $3$ instead of $3.5$)

Call $A$ **wiggle-sorted** if $\A\_0\<\A\_1\>\A\_2\<\A\_3\>\A\_4\<\cdots$. Call $A$ **wiggle-sortable** if we can rearrange its entries so that it becomes **wiggle-sorted**. An array is always wiggle-sortable if all numbers in it are distinct. If all numbers are not distinct, the array may or may not be wiggle-sortable. For example, $\[1,2,2\]$ is not wiggle-sortable while $\[1,1,2\]$ is wiggle-sortable.

A permutation of $\\{0,1,\cdots, n-1\\}$, $\sigma$, is called **a wiggling permutation** if $\sigma(\A)=(\A\_{\sigma(0)},\A\_{\sigma(1)}, \cdots, \A\_{\sigma(n-1)})$ is wiggle-sorted as long as $\A$ is sorted.

For all $n$, define a permutation $$w\_n=\pmatrix { 0 &1 &2 &3 &4&5&\cdots\\m &n-1 &m-1 &n-2 &m-2 &n-3 &\cdots},$$ where $m=\lceil n/2\rceil-1$. For example, $$w\_5=\pmatrix { 0 &1 &2 &3 &4 \\2 &4 &1 &3 &0},$$ $$w\_8=\pmatrix { 0 &1 &2 &3 &4&5&6&7\\3 &7 &2 &6 &1 &5 &0 &4}.$$ **Characterization of wiggle-sortable arrays**. The following propositions are equivalent.

1. $\A$ is wiggle-sortable of size $n$.
2. (Not too many medians) The number of medians of $A$ is no more than $\lceil n/2\rceil$.
3. If we have just sorted $A$ (in the usual sense), then $w\_n(\A)$ is wiggle-sorted.

**Uniqueness of wiggling permutation.** For even size $n$, $w\_n$ is the unique wiggle permutation. For odd size $n$, $w\_n$ and $\overline{w\_n}$ are the only two wiggling permutations, where $\overline{w\_n}$ is the "reverse" of $w\_n$, i.e., $\overline{w\_n}(i)=n-1-w\_n(i)$ for all $i$.

This uniqueness explains the fact that all solutions to the wiggle-sort problem arrange the given array the same way basically.

---

Here is the problem again: given an array of numbers, how can we wiggle-sort it?

### A simple approach that runs in $O(n\log n)$ time

The easiest approach to implement, as illustrated in the question, is to sort the array, explicitly or implicitly, and rearrange the array.

Input: an array $\A$ of $n$ numbers with indices $0, 1, n-1$.
Output: None if $\A$ is not wiggle-sortable. Otherwise, return $\A$ that has been wiggle-sorted.
Procedure:

1. Sort $A$ into a temporary array. (Most sorting libraries run in $O(n\log n)$ time on average.)
2. Copy the largest number, the next largest number, and so on of the temporary array to $A$ at index $1, 3, 5,\cdots$ until the index is out of bound.
3. Copy the next largest number, the next largest number, and so on of the temporary array to $A$ at index $0, 2, 4,\cdots$ until all numbers are exhausted.
4. Check if the $\A$ is wiggle-sorted. Return accordingly.

```
# assume the given array, nums is wiggle-sortable
def wiggle_sort(nums):
    arr = sorted(nums)
    for i in range(1, len(nums), 2): nums[i] = arr.pop()
    for i in range(0, len(nums), 2): nums[i] = arr.pop()

```

---

To achieve better performance, we have to avoid sorting the array.

### The outline of a faster algorithm

Procedure:

1. find the median of $\A$ by some $O(n)$ algorithm.
2. Count the number of all medians. If it is greater than $\lceil n/2\rceil$, return None.
3. Put all entries larger than the median in positions with odd indices, $1, 3, 5,\cdots$ in that order.
4. Put all entries smaller than the median in positions with even indices from the largest-even-indice going downwards.
5. Fill the remaining entries of $A$ with the median. Return $\A$.

The problem is shifted to how to find the median and arrange the numbers

### Find the median in linear time and constant space

To implement the algorithm in linear time and constant space we need to find the median in linear time and constant space.

There are various ways to achieve that deterministically, for example, linear-time in-place selection in less than 3n comparisons, 2005 and linear-time in-place selection with ⋅ element moves, 2006. Unfortunately, all these algorithms are somewhat complicated.

We can find the median in average linear time and constant space using a simple algorithm, quickselect. Here is the python code.

```
def k_smallest(nums, k, start, end):
    """
    Returns the k-th smallest number in nums[start:end+1].
    """
    if k <= 0 or end - start < k - 1:
        return None

    k = start + k - 1

    while True:
        if start >= end:
            return nums[start]

        # pivot = nums[random.randint(start, end)]
        pivot = nums[end]
        left, right, m = start, end, start
        while m <= right:
            if nums[m] < pivot:
                nums[left], nums[m] = nums[m], nums[left]
                left += 1
                m += 1
            elif nums[m] > pivot:
                nums[right], nums[m] = nums[m], nums[right]
                right -= 1
            else:
                m += 1
        if left <= k <= right:
            return pivot
        elif k < left:
            end = left - 1
        else:  # k > right
            start = right + 1

m = k_smallest(nums, (n + 1) // 2, 0, len(nums) - 1)  # m is the median

```

If we relax the space requirement slightly, we can find the median in linear-time and logarithmic-space using the median of medians algorithm.

**Arrange the numbers in linear time and constant space**

Once the median has been found, the problem is shifted to arrange the number as specified. Any reasonable implementation will run linear time. What is not obvious is how to do it in constant space as well.

We can imagine the entries of $\A$ is actually arranged in the memory consecutively as $A\_1$, $A\_3$, $A\_5$, $\cdots$, $A\_{n\_1}$, $A\_0$, $A\_2$, $A\_4$, $\cdots$, $A\_{n\_0}$, where $n\_1$ and $n\_0$ are the largest odd and even number not exceeding $n$. Here is the explicit access pattern when $n=8$:
$\quad$ Accessing memory at index 0 actually accesses $A\_1$.
$\quad$ Accessing memory at index 1 actually accesses $A\_3$.
$\quad$ Accessing memory at index 2 actually accesses $A\_5$.
$\quad$ Accessing memory at index 3 actually accesses $A\_7$.
$\quad$ Accessing memory at index 4 actually accesses $A\_0$.
$\quad$ Accessing memory at index 5 actually accesses $A\_2$.
$\quad$ Accessing memory at index 6 actually accesses $A\_4$.
$\quad$ Accessing memory at index 7 actually accesses $A\_6$.
Or, in general, the memory at the index $p$ refers to $\A\_{(1+2p)\pmod{n\\,|\\, 1}}$.

With this mapping between indices, the problem is transformed to the Dutch national flag problem or, what is the same, the tri-color problem on LeetCode. We can apply the tri-color algorithm almost verbatim, which runs in $O(n)$ time and $O(1)$ space (thanks to StefanPochmann for his post).

```
# Put numbers larger than pivot at smallest odd-indices.
# Put numbers smaller than pivot at largest even-indices.
def tri_color_clustering(nums, pivot):
    n = len(nums)

    def map_index(p):
        return (1 + 2 * p) % (n | 1)

    i, j, k = 0, 0, n - 1
    while j <= k:
        if nums[map_index(j)] > pivot:
            nums[map_index(j)], nums[map_index(i)] = nums[map_index(i)], nums[map_index(j)]
            i += 1
            j += 1
        elif nums[map_index(j)] < pivot:
            nums[map_index(j)], nums[map_index(k)] = nums[map_index(k)], nums[map_index(j)]
            k -= 1
        else:
            j += 1
    # print(nums)

```

---

A previous version of this answer shows a simple and fast algorithm to wiggle sort an array in $O(n)$ time and $O(1)$ space, assuming all numbers in the given array are distinct.
> 4 votes

---
Tags: algorithms, sorting, python
---


# Question
Title: Create an algorithm for computing the shortest path in O(m + nlogn)
So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non negative) graph $G = (V, E)$, a set of vertices $X \subset V$, and two vertices $s, t \in V \setminus X$. The graph is given with adjacency lists and we can assume that it takes $O(1)$ time to determine if a vertex is in $X$. I'm trying to write an algorithm which can compute the shortest path between $s$ and $t$ in $G$ such that the path includes at most one vertex from $X$ if such a path exists in $O(m + n \log n)$ time. I know that this algorithm would require a modified Dijkstra's algorithm but I'm unsure how to proceed from here.
Could anyone please help me out?

# Answer
> 1 votes
Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$.

Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given a vertex $v$ let $v\_A$ be it's copy in $A$ (if any) and $v\_B$ be its copy in $B$ (if any).

The edges of $G'$ are as follows:

* For each edge $(u,v) \in E$ with $u,v \in V \setminus X$ add to $G'$ the edges $(u\_A, v\_A)$ and $(u\_B, v\_B)$ with the same weight as $(u,v)$.
* For each edge $(u,v) \in E$ with $u \in V \setminus X$, and $v \in X$, add the edge $(u\_A, v\_A)$ with the same weight as $(u,v)$.
* For each edge $(u,v) \in E$ with $u \in X$, and $v \in V \setminus X$, add the edge $(u\_A, v\_B)$ with the same weight as $(u,v)$.
* Ignore all the edges $(u,v)$ with $u,v \in X$.
* Finally, for each vertex $v \in V \setminus X$, add the edge $(v\_A, v\_B)$ with weight $0$.

Your problem now amounts to that of finding the shortest path between $s\_A$ and $t\_B$ in $G'$, which can be done in $O(m + n \log n)$ time using Dijkstra's algorithm.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs, dijkstras-algorithm
---


# Question
Title: What is the difference in time-complexity for sorting these 2-d arrays?
Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements

Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements.

It is given that each row is sorted in ascending order, Can you sort each of these in $O(n\log(n))$ or better using comparison sort?

I'm leaning towards k-way merge implementing a min-heap following this implementation merging sorted arrays, but I can't seem to figure out what the difference between this cases is.

$B$ for example will have $10$ elements constantly in the min-heap, so the time complexity will be $10n \log(10) \in O(n)$? Is this even possible in comparison sorts?

While $A$ would have $n/10$ elements in the min-heap, but are the run times equivalent?

# Answer
The algorithm you suggest for $B$ is a comparison-based algorithm with complexity $O(n \log h)$, where $h$ is the maximum number of elements in the heap. Since $h = \Theta(1)$, you have that $B$ can be sorted in time $O(n)$.

Regarding $A$, the lower bound of $\Omega(m \log m)$ on any comparison-based algorithm that sorts $m$ elements still applies. Indeed, the first elements on each row (i.e., those of the first column) can be in any order relation with one another.

Any algorithm that sorts $A$, is also an algorithm that sorts the $m = \frac{n}{10} = \Theta(n)$ elements in the first column, and therefore it must have time $\Omega(m \log m) = \Omega(n \log n)$.
> 1 votes

---
Tags: algorithms, time-complexity, data-structures, heaps, heap-sort
---


# Question
Title: Shortest path in a maze where you can break one wall
How would I solve the following problem?

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0, 0) and the door into an escape pod is at the bottom right (w−1, h−1). Write a function that generates the length of a shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans.

I know that without destroying the walls this could be easily solved with the use of Dijkstra. But how to take into account the fact I can destroy one wall?

The only solution I could come up with was to remember two distances for each node: one distance is the "real" shortest path, the second one is the shortest past when I break one (any) wall.

At first I would count all the "real" shortest paths with classic Dijkstra. In the second run I would use Dijkstra again to compute the second parameter of each node: shortest path with exactly one wall broken.

In each iteration the closest node to be chosen (I need to check even vertices that are "one wall away") in Dijkstra is the one with the shortest "real" path or path with a broken wall (whichever is smaller). In case the vertex is one wall away, I only check the "real" path property of course.

This seems correct to me. But is there a better (more efficient) solution?

# Answer
> 1 votes
No. There is not a more efficient solution. It's possible to solve the problem in linear time using two iterations of Dijkstra's algorithm, if you implement the second run appropriately (which doesn't seem to be described in the question; but I will assume you know how to do it). You can't do better than linear running time; any algorithm will have to examine all of the input (or at least a constant fraction of it). Therefore, there is no possibility of an algorithm that is asymptotically better; it's not possible to find an algorithm that is more than a constant factor faster.

I didn't verify your specific algorithm, because I couldn't understand the next-to-last paragraph of your question, but I do know the problem can be solved in linear time.

# Answer
> 4 votes
You can use any search algorithm (including A\*) with a tiny alteration from the standard one.

In each node you store whether the path from the start has a broken wall or not. Then when generating the neighbours you can move into a wall only if that flag is false and the neighbours that move into a wall get it set to true.

When Comparing Nodes for equality (for replacing in the heap and or the closed set) that flag counts alongside the position.

# Answer
> 3 votes
## Introduction

While solving `google foobar` I stumbled upon this problem. I approached the problem with `A*` along with a few modifications. As this algorithm correctly outlines the core concepts, I would like to go further ahead and add some detailing to this.

## Algorithm:

Each node will have the following parameters:

1. parent: The immediate parent of the node.
2. position: This is the `(x,y)` position of the node.
3. f,g,h: These are the heuristics needed for A\* to work.
4. wall\_broken: This is a boolean flag that would account for a broken wall in the path to the node. By default is set to `False`.

After we set up our pre-requisites, we move into the algorithm.

1. Create the start and end node.
2. Initialize the `open` and `closed` lists. The open list must contain the `start` node.
3. Iterate until we have visited each node.
    1. Take the node with least **f** from the open list. This is our current node. Remember putting it inside the visited list.
    2. Check whether the current node is the end node. When comparing equality, we will compare the **positions** of the nodes only. If yes, then hurray! Return the path that has been traced. If no, perform the next step.
    3. Generation of children from the current node.

    * Check for validity of the position.
        * Check if the position has a wall. If it does, then we need to check whether the current node has any broken walls in its path (this is where we will need the wall\_broken property of the node). We destroy the wall if we have no prior destruction. We make sure to assign the wall\_broken property of the child which broke into a wall to True.
        * We do not generate children if they already have been visited.5. Iteration on the children to decide which goes into the open list and which don't.

    * Assign heuristics to each child.
        * Look for a better child in open to replace. Else add it into the open list.

## Conclusion

This algorithm is a modification of the A\*. It conveys the core concept. If you want a detailed walkthrough of the concept with code, I have a gist written in python.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Can you apply neural networks to design algorithms?
I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math problems.

A few CS/math friends were teaching me about P=NP and I was wondering whether a potential way to identify an algorithm that can convert the exponential time it takes to solve NP solutions into polynomial time is to use a genetic algorithm that applies brute-force until such an algorithm is identified.

Apologies if I’m misunderstanding anything or being too naive. Thank you for your time.

# Answer
> 2 votes
There are a few issues to consider.

If P!=NP, this approach is doomed from the start because you can't try every one of the infinite number of possible algorithms in finite time. That's I think the main deal-breaker here. Unless P=NP, which most people doubt, then the best you could ever do is say "my AI failed to find a polynomial-time algorithm in X amount of time", which doesn't mean no such algorithm exists. If you assume that P=NP, then in principle, an evolutionary algorithm, neural network, or other search technique could potentially find an example of a polynomial algorithm for an NP-complete problem, and that's all you need to prove that P=NP.

In practice, there are some challenges to deal with. I'm sure certain approaches would be more natural to try than others. Neural nets require numeric vectors of inputs and outputs, so you need to develop some way to encode an algorithm as a vector and a way to determine a binary "is\_polynomial" so that you have an error gradient to follow. Or I suppose a continuous function measuring "degree of polynomial-ness" if such a thing makes sense. You're certainly going to need some way to measure success regardless of approach, but something like Genetic Programming could theoretically eliminate the need for a cumbersome translation of algorithm to real vector, since GP operates directly on an executable representation. Give it a Turing-complete set of operators to work with and it could presumably eventually find a polynomial solution if such a thing exists.

It's also far from clear that you have a friendly search space to work with here. I think most of the time, your hypothetical GP or whatever is going to wander around a very flat plateau of individuals that don't even successfully solve the problem, regardless of run-time. You could attempt to introduce a gradient to follow by favoring shorter programs or programs that terminate faster or whatever thing you came up with, but there's no good reason to think that gradient points in the direction of the prize-winning algorithm you're looking for. Theoretically, there are fairly easy conditions to meet that say given infinite search time, a given algorithm will eventually find any arbitrary solution that exists, but a workable algorithm in practice tends to require there be some structure in the search space that can be exploited. If you make a local move somewhere in the space that looks like it's better, you want that move to take you generally closer to the solution you're looking for. If the world looks basically random in terms of what moves me closer or further away, search algorithms struggle to do better than just randomly trying things.

Short answer, it's conceivably possible to build an algorithm that searches for poly-time solutions to an NP-hard problem, but the world is likely constructed so that that won't actually solve the problem you hope to solve.

---
Tags: neural-networks, p-vs-np, genetic-algorithms
---


# Question
Title: NPC PROBLEM minimum sum of vertex coloring
For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don't understand how to do a reduction to check the minimum. I got a hint to do a reduction from 3-NAE-SAT but I don't understand how. would appreciate some help. even some source I can read about this problem if you know about something.

# Answer
> 2 votes
We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable?

Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \\{1,2,3\\}$, whose edges are $$ \\{((i,a),(j,a)) \mid (i,j) \in E, a \in \[3\]\\} \cup \\{((i,a),(i,b)) \mid i \in V, 1 \leq a \< b \leq 3 \\}. $$ In words, we take three copies of $G$, and connect all copies of the same vertex.

If $G$ is 3-colorable then $G'$ can be 3-colored: given a 3-coloring $\chi$ of $V$, color $(i,a)$ with the color $\chi(i) + a \bmod 3$. The sum of the colors is $6|V|$.

Conversely, suppose that $G'$ has a coloring $\chi'$ whose sum is at most $6|V|$. Note that the three copies of each vertex $(i,1),(i,2),(i,3)$ must be assigned different colors, which sum to at least $6$. Therefore $\sigma \chi' \geq 6|V|$ for *any* coloring $\chi'$, and $\sigma \chi' = 6|V|$ iff $\chi'$ is a 3-coloring. Considering one of the copies of $G$, we see that $G$ is 3-colorable.

---
Tags: np-complete, reductions, colorings
---


# Question
Title: Are there NP languages whose verification is P-complete?
A decision problem is in NP if a candidate "yes" can be verified in polynomial time.

Are there decision problems whose "yes" is verified with an algorithm that is P-complete (reducible in logspace)? Are those problems in NP?

If so, can the "yes" be verified in logspace?

I'm told "for every NP language we can find a verifier that uses only logspace."

# Answer
> 3 votes
Every language in NP has a logspace verifier.

Indeed, let $L$ be any language in NP. Therefore, there is a polynomial time machine $T$ and a polynomial $p$ such that $x \in L$ iff some string $y$ of size at most $p(|x|)$ makes $T(x,y)$ accept.

While the witness $y$ may be hard to check, we can make help a logspace machine verify it by including the *transcript* of the accepting computation. We construct another machine $T'$ which accepts a new witness $z$. The witness $z$ consists of a sequence of configurations of the machine $T$, starting with an initial configuration encoding $x$ and $y$, and ending at an accepting configuration. Since each configuration has polynomial length, a logspace machine can verify that $z$ indeed consists of a valid sequence of configurations.

---
Tags: complexity-theory
---


title: checks if a tree is a full binary tree

text:
# Question
Title: checks if a tree is a full binary tree
I have to write an algorithm that checks if a tree is full binary tree (each node, except the leaves, must have 2 children), but I don't know if this version is correct.

```
 isComplete(u)
{
        if(u == NULL)
                return false
        else
        {
                left = isComplete(u.left);
                right = isComplete(u.right);
                complete = left && right;

                return complete.
        }
}

```

# Answer
Since your algorithm is recursive you need to consider:

* the initial / final case : the leaves
* and the general case : the nodes

For example in the case of factorial:

* the initial case $f(1) = 1$
* and the general case is $f(n) = n\*f(n-1)$

Formally, to prove its correctness you can use induction.
> 2 votes

---
Tags: algorithms, binary-trees
---


title: Unique 1-in-3 SAT

text:
# Question
Title: Unique 1-in-3 SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.

*I know the value of each bit of the unique assignment because it was made from a binary multiplication circuit where I multiplied two primes numbers A and B such that A\*B=S where S is a semiprime number. I added the conditions that A != 1, B != 1 and A \<= B, then added the value of S to the formula make sure the assignment is unique. The only way to satisfy the formula is to put the values of A and B in correct order in the input bits.*

The number of true literals in each clause is either 1, 2 or 3. Because I know the value of each bit, I can tell exactly which literals are true in each clause, and count them. For example, I know which clauses are satisfied by exactly 1 literal. And that literal is logically part of the unique solution.

My question is simple: If I remove all the clauses with more than 1 true literal, will the assignment necessarily still be unique?

In other words, if I wanted to write down a resolution proof (likely exponentially long) to demonstrate that the solution is unique (Another Solution Problem, in Co-NP), can I write it down using only the clauses with 1 true literal?

Intuitively, I think so, but I am unable to defend my point of view, even when thinking about the 2SAT equivalent.

# Answer
Consider the following CNF: $$ (a \lor \lnot b) \land (\lnot a \lor b) \land (a \lor b). $$ It has a unique satisfying assignment, $a=b=\top$, which satisfies the last clause twice. However, if you remove the last clause, then you get another satisfying assignment, $a=b=\bot$.
> 1 votes

---
Tags: np, satisfiability, 3-sat
---


title: Do ‘unspoofable’ email protocols exist?

text:
# Question
Title: Do ‘unspoofable’ email protocols exist?
Been getting a lot more spam lately and this question came to mind. We already use SSL certificates to authenticate websites, can we do something similar for email?

If so, why do I still receive spoofed emails?

# Answer
> 0 votes
If you use PGP or MIME to sign emails with public-key cryptography, this can prevent spoofing of emails. The greatest challenges are key management, human factors, and convincing enough people to sign emails.

Therefore, in practice we use weaker mechanisms, like SPF, DKIM, and DMARC.

# Answer
> 1 votes
There are several protocols actually:

* **SPF Sender Policy Framework** is used to verify that the e-mail address used to send the message is valid e.g. if the sender had rights to use the given domain. Recipients can verify this by checking the ips of the agent dropping the mail against the allowed ips listed in the domain DNS records.
* **DKIM DomainKeys Identified Mail** is used to verify that a given message hasn't been tampered in transit. Recipients can verify this using the public key of a given domain along with the signature included in DKIM signed e-mails.

These are actively used in SPAM filtering. You can see it in action by looking at the headers of most e-mails today. You can look for the headers: *Authentication-Results, DKIM-Signature, Received-SPF.*

---
Tags: authentication
---


# Question
Title: Time complexity of DFS and recurrence relation
Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?

# Answer
> 1 votes
**For an implicit graph the recurrence can be written as follows:**

Let $b$ be the number of branches of every node (assumed to be constant)

let $d$ the depth of the graph

For depth 1 there are $b$ branches:

$T(b,1) = b$

For the next levels it can be written as

$T(b,d) = b + b\*T(b,d-1)$

where $b$ are the nodes at this level, and are the $b\*T(b,d-1)$ nodes at next level.

If you substitute the definition for $T(b,d-1)$ you get

$b * (1 + b\*(1+T(b,d-2)) = b + b^2(1+T(b,d-2))$

If you further substitute the definition of $T(b,d-2)$ you get

$b + b^2(1+b+b\*T(b,d-3)) = b + b^2 + b^3 + b^3\*T(b,d-3)$

If you continue to expand you get

$T(b,d) = b + b^2 +b^3 +... + b^{d-1}\*T(b,1)$

Since we know that $T(b,1) = b$, we can substitute

$T(b,d) = b + b^2 +b^3 +... + b^{d-1}\*b$

Thus

$T(b,d) = b + b^2 +b^3 +... + b^d$

Using Big-O Notation. $O(b^d)$

**For explicit graphs with $V$ vertex and $E$ edges**

We assume you have an adjacent list. That is for every $V$ you have a list of adjacent edges. You can think of a Table of $E$ edges (columns) x $V$ vertex (rows).

We can write our recurrent relation based on the navigation of that table.

$T(V,E) = 1 + e\_0 + T(V-e\_0,E-e\_0)$

We count $1$ for visiting the first row, and $e\_0$ for the number of edges adjacent to that first vertex. For the next rows we use the recurrent relation except this time we have $V-e\_0$ vertex and $E-e\_0$ edges to visit.

If we substitute our definition for the 3rd. element in our relation we get:

$T(V,E) = 1 + e\_0 + 1 + e\_1 + T(V-e\_1,E-e\_1)$

if you keep expanding you get

$T(V,E) = 1 + 1 + .. + 1 + e\_0 +e\_1 + .. + e\_V$

1 for every row visited and a certain number of edges for a given vertex. In total the number of edges is $E =e\_0 + e\_1 + .. e\_V$.

$T(V,E) = V + E$

in Big-O Notation $O(V+E)$.

---
Tags: time-complexity, depth-first-search
---


# Question
Title: Efficient algorithm to compare arrays problem
I was submitted an interesting problem, but I wasn't able to find a solution.

Define a function `p(x, y)` that takes int x and y, with `y > x` and returns an int.

`p(x, y) = x & (x+1) & (x+2) & ... & (y-1) & y`

There are then two arrays X of length N and Y of length M representing x and y, in binary with `M >= N > 0`. X and Y are consistently indexed, so that `X[0]` and `Y[0]` represent the least significant digit of x and y.

The final goal is to write an efficient algorithm that computer `p(x, y)`. The ideal solution would be to have a time complexity of *O(M)* and a space complexity of *O(M)*. We can assume that the bitwise AND operator is already implemented with a complexity of *O(M)* in both time and space. There's also no need to work on the binary representation of the numbers. Pseudocode is fine.

# Answer
You can write $x$ and $y$ in binary as \begin{align} x&=x\_{M-1} \ldots x\_0 \\ y&=y\_{M-1} \ldots y\_0 \end{align} (This is exactly the contents of your arrays.) Since $x \neq y$, there must be a first bit (from the left) at which they differ. Say that this bit is $x\_i \neq y\_i$. Since $y \> x$, we know that $y\_i = 1$ and $x\_i = 0$. Thus \begin{align} x &= x\_{M-1} \ldots x\_{i+1} 0 x\_{i-1} \ldots x\_0 \\ y &= x\_{M-1} \ldots x\_{i+1} 1 y\_{i-1} \ldots y\_0 \end{align} The following two integers are in the range $x,\ldots,y$: \begin{align} &x\_{M-1} \ldots x\_{i+1} 0 1 \ldots 1 \\ &x\_{M-1} \ldots x\_{i+1} 1 0 \ldots 0 \end{align} This shows that if you take the AND of all integers from $x$ to $y$, you get $$ x\_{M-1} \ldots x\_{i+1} 0 0 \ldots 0 $$
> 2 votes

---
Tags: algorithms, time-complexity, arrays, space-complexity, efficiency
---


title: Unique 3SAT to Unique 1-in-3SAT

text:
# Question
Title: Unique 3SAT to Unique 1-in-3SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.

*It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such that A\*B=S where S is a semiprime number. I added the conditions that A != 1, B != 1 and A \<= B, then added the value of S to the formula make sure the assignment is unique. The only way to satisfy the formula is to put the values of primes A and B in correct order in the input bits.*

In 1-in-3SAT, we force that exactly 1 literal should be true in each triplet and two others false. If exactly 2 literals are true we can flip all the literals in the clause to get an equivalent 1-in-3SAT clause (in other words 2-in-3SAT is the same problem).

*Basic observation: While a regular OR clause eliminates 1 possibility out of 8, a 1-in-3 clause eliminates 5 possibilities out of 8.*

3SAT can be reduced to 1-in-3 SAT, such that if the 3SAT formula is satisfiable then so is the reduced formula.

However, reductions do not seem to preserve the number of assignments, by introducing new variables without forcing their value.

Can Unique 3SAT be reduced to Unique 1-in-3SAT?

# Answer
> 3 votes
Yes, a 3-SAT formula $\phi$ can be transformed into a 1-in-3 SAT formula $\phi'$ while preserving the number of satisfying assignments. To avoid ambiguities I will use "$\vee$" between literals of a 3-SAT clause, and commas between literals of a 1-in-3 SAT clause.

---

Let me preliminarily show that, given two literals $a$ and $b$, we can simulate a new type of clause $(x = a \wedge b)$ that forces the value of a new variable $x$ to be $a \wedge b$ using only 1-in-3 SAT constraints, without introducing any new solution.

Consider the cluases: $$ (\overline{b}, c, x) \wedge (a, c, d) \wedge (\overline{a}, e, x) \wedge (b, e, f) $$

If $a=\top$, and $b=\top$, then the 2nd and 4th clauses ensures that $c=d=e=f=\bot$. The 1st and 3rd clauses then ensures that $x=\top$.

If $a=\top$, and $b=\bot$, then the 2nd clause ensures that $c=d=\bot$. The 1st clause then ensures that $x=\bot$. The 3rd clause ensures that $e=\top$, and the 4th clause implies $f=\bot$.

The case $a=\bot$, and $b=\top$ is symmetric.

If $a=\bot$ and $b=\bot$, then the 1st and 3rd clauses imply $c=e=x=\bot$. The 2nd and 4th clauses ensure $d=f=\top$.

---

I am now ready to transform a formula $\phi$ of 3SAT to a formula $\phi'$ of 1-in-3 SAT. Consider now a clause $(a \vee b \vee c)$ of $\phi$. This can be transformed into the following equivalent 1-in-3 SAT clauses:

* Add a new variable $x$ that is true iff $a$ is false and $b$ is true. This is encoded by the clause $(x = \overline{a} \wedge b)$.
* Add a new variable $y$ that is true iff $a$ is false, $b$ is false, and $c$ is true. We will need an additional variable $z$. The clause $(z = \overline{a} \wedge \overline{b})$ ensures that $z$ is true if and only if $a$ is false and $b$ is false. Then, the value of $y$ can be enforced by the clause $(y = z \wedge c)$.
* If $(a \vee b \vee c)$ is true then at least one of $a$, $b$, or $c$ is true. This means that exactly one of $a$, $x$, and $y$ is true. On the converse, if $(a \vee b \vee c)$ is false, then at all of $a$, $x$, and $y$ are false. This shows that $(a \vee b \vee c)$ is satisfiable if and only if $(a, x, y$) is satisfiable.

We have then constructed an equivalent 1-in-3 SAT formula $\phi'$ that uses a superset of the variables of the original 3 SAT formula $\phi$. A truth assignment to the variables of $\phi'$ satisfies $\phi'$ if and only if the assignment restricted to the variables of $\phi$ satisfies $\phi$. Therefore, if any new solution to $\phi'$ is introduced, it must be because of the newly added variables $x$, $y$, and $z$ (one set for each clause). However, the values of these variables are completely determined by the values of the variables of $\phi$.

# Answer
> 3 votes
Such a reduction is described in Appendix B of Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane. Barbanchon attributes it to previous work (\[9\] in the bibliography). Elsewhere, I have seen an attribution to Schaefer's celebrated paper in which he proves his famous dichotomy theorem, among else giving a reduction from 3SAT to 1-in-3SAT, which is supposedly parsimonious (I haven't checked).

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


title: Analysis of Universal Hashing

text:
# Question
Title: Analysis of Universal Hashing
I was reading universal Hashing from *Introduction to Algorithms by Cormen et al.*, and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables:

> ***Corollary 11.4***
>
> Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(n)$ to handle any sequence of $n$ **Insert**, **Search**, and **Delete** operations containing $O(m)$ **Insert** operations.
>
> ***Proof*** Since the number of insertions is $O(m)$, we have $n = O(m)$ and so $\alpha = O(1)$. The **Insert** and **Delete** operations take constant time and, by Theorem 11.3, the expected time for each **Search** operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of $n$ operations is $O(n)$. Since each operation takes $\Omega(1)$ time, the $\Theta(n)$ bound follows. $\quad\blacksquare$

1. How is the author able to say that $n = O(m)$, in the first line of the proof?
2. Also, what does $n=O(m)$ mean? Because $n$ is a variable and $m$ is a constant, therefore the statement seems wrong.
3. Also, if $n=O(m)$ is true, then obviously $n=\Omega(m)$ is true, thus yielding $n=\Theta(m)$.

# Answer
> 2 votes
The statement of the corollary is extremely sloppy. Here is a correct statement and proof.

> ***Corollary 11.4***
>
> Fix $c \< 1$. Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(N)$ to handle any sequence of $N$ **Insert**, **Search**, and **Delete** operations containing at most $cm$ **Insert** operations.
>
> ***Proof*** Since the number of insertions is at most $cm$, we have $n \leq cm$, where $n$ is the number of elements in the table, and so the load factor satisfies $\alpha \leq c$. The **Insert** and **Delete** operations take constant time and, by Theorem 11.3, the expected time for each **Search** operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of $N$ operations is $O(N)$. Since each operation takes $\Omega(1)$ time, the $\Theta(N)$ bound follows. $\quad\blacksquare$

Roughly speaking, there are two problems with the book version:

1. The variable $n$ is used both for the number of elements in the table and for the number of operations.
2. The number of Insert operations should be $O(m)$, **with a hidden constant bounded away from $1$.**

---
Tags: algorithm-analysis, hashing
---


title: Single Cycle Data-path Requirements

text:
# Question
Title: Single Cycle Data-path Requirements
How does having separate instruction and data memories help in implementing a single cycle datapath for a MIPS instruction set? I want to know why we can only use a datapath element once in a cycle for making the datapath capable of executing any instruction in a single cycle.

# Answer
> 1 votes
Each element in that data path is purely logical, thus in each cycle an element can perform only a single operation. If you had only one memory element, you would've possibly need to perform two operations in one cycle: (1) read the instruction (2) read/write data. This is impossible with a logic-only (sateless) elements within a single cycle.

---
Tags: computer-architecture
---


# Question
Title: N 3d integer points in box with maximum average distance
given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary approach I can take to this, so in each step the solution will be improved?

Thanks!

# Answer
Note that maximizing the average distance between every pair of points is the same as maximizing the total distance between every pair of points.

Let's look at an m x m square first. When N = 4, it is clear that the optimal solution is placing a point in each corner.

For N = 5, the next picture explores two alternatives of placing the 5th point when the other 4 are in the corners. It appears it is optimal to place the 5th point also in a corner. Note that in the right picture, which is already sub-optimal, the total solution does not improve when moving any of the other four points (which are in the corners).

This solution does not work for all N, but it generalizes to cubes when N is a multiple of 8. Then all points are in the eight corners in an optimal solution.
> 1 votes

---
Tags: search-algorithms
---


# Question
Title: Natural deduction: understanding bottom elimination (¬e)
I am new to natural deduction and upon reading about various methods online, I came across the rule of bottom-elimination in the following example.

I do not understand the step in line 10.

Upon inspection, my initial thought would be that the assumption of ¬p and p both being true is absurd, hence anything can be inferred ( in this case 'p'). However, if this were the case where would you stop (this seems to be an overly powerful tool)? So I assume that this idea is wrong.

Could someone help me understand the rule?

**NOTE**: I came to StackExchange due to the lack of resources and specific information online.

# Answer
Usually in practice we weld the two steps together and just say that from $p$ and $\lnot p$ anything follows, but in formal logic this is a combination of two rules of inference:

1. $p$ and $\lnot p$ both together entail falsehood $\bot$,
2. from $\bot$ anything follows.

These are precisely lines 9 and 10 in your proof.

We often take $\lnot p$ to be an abbreviation for $p \Rightarrow \bot$, in which case the rule "from $p$ and $\lnot p$ follows $\bot$" is just a special case of modus ponens "from $p$ and $p \Rightarrow r$ follows $r$".
> 2 votes

---
Tags: logic, first-order-logic, natural-deduction
---


title: facts about ieee 754

text:
# Question
Title: facts about ieee 754
Someone told me this and I would be interested to know if it is true:

> In the ieee 754 format approximately half of the positive numbers are in the interval \[0, 1\]

# Answer
> 3 votes
"Floating point" means a representation in which the position of the fraction indicator (the "point") in a number is allowed to take on a range of values, allowing the fixed-length representation of numbers with a wide range of magnitudes, all with the same (relative) precision. This is done by decomposing the number into two fixed-length fields: the significand (or "mantissa" \[Note 1\]) and the exponent. The significand is a fixed-point value (usually the fixed point immediately follows the first digit and the first digit is required to be non-zero); the exponent is an integer exponent of some representation-defined base.

A common manifestation in ordinary discourse is the use of so-called scientific representation, in which numbers are decomposed into the product of a fixed-point decimal fraction (with the decimal forced to come right after the first digit, as above) and an integer power of 10. So, for example, the number 299742958 would be written $2.99742958\times10^8$. (That's the speed of light in metres/second, by the way.) If I was working in an environment where I could only use six decimal digits of precision, I would approximate that to $2.99743\times10^8$. And so on. In ordinary discourse, it's not usual to limit the size of the exponent, mostly because numbers so large that the exponent would need to be limited don't come up that often, but typographical and practical considerations force us to write a googol as $10^{10^{100}}$ rather than writing out the exponent in full. In a strict fixed-length representation, it might well turn out to be impossible to represent a googol other than by saying "a number too large to represent", which we might abbreviate as "$\approx\infty$".

IEEE-754 defines several binary floating point formats which have similar characteristics, except that they are in base 2 rather than base 10. They differ slightly from the above in that:

* one bit is reserved for the sign
* since the significand is forced to start with a `1`, that being the only binary digit other than `0`, only the fraction part of the significand is actually present (this is not true of extended precision versions).

The exponent is signed, but it is not stored in 2's complement. Instead, it is stored as an unsigned number representing the exponent offset by some integer. But the offset is close to the middle of the possible range of values, so the effect is similar to 2's complement. Also, the largest and the smallest exponent values are reserved for other purposes. For example, a number with largest exponent value is either $\infty$ or a NaN, depending on whether or not the significand is all 0s. (Also note than IEEE 754 $\infty$ is really $\approx\infty$, as above.)

With all that behind us, let's look at how many positive values are in the range $\[0, 1\]$. (Since the representation has a separate sign bit, exactly half of the possible numbers are negative and the other half are positive, except that 0 can be represented either as a "positive 0" or a "negative 0". In IEEE754 both representations of zero are allowed and must be considered equal. Zero is one of the special values referred to above, in case you were curious.)

If we leave out the limits of this range, we can see that all numbers whose offset exponents are less than 0 are in the range. (There are actually two more numbers in the range -- the limits -- but that doesn't significantly affect the count.) If the number of possible negative offset exponents is roughly equal to the number of non-negative offset exponents, then the count of representable values in the range $\[0, 1\]$ will be roughly half of the count of representable positive values. And, indeed, IEEE-754 sets the offset close to the middle of the range. (The range of possible exponent values has an even number of possible values, so the precise middle is impossible.)

But that's not just a feature of IEEE-754. Pretty well any general-purpose floating-point representation, regardless of precision or base, is going to have the same characteristic. The only requirements are that the significand and exponent are represented separately as fixed-length fields, and that the representation of the exponent is roughly balanced between positive and negative values.

---
Tags: number-formats
---


# Question
Title: Formal definition of a language accepted by PDA
I am a bit confused on how to give a formal definition of the language accepted by A?

I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" and I have tried to give a formal definition by:

L(A) = {a^n c^n b^n | n ∈ N}

Is that the correct way to define it?

# Answer
I would say it's $L(A)=\\{a^n c^m b^{2n}| n,m \in \mathbb{N}, m \geq 2\\}$

For every a push 2 zeros on the stack, so it's for now just called a^n. The number of c's is m, because it is not related to the number of a's. You can accept any number of c's (larger than 2) no matter how many a's were there. The number of b's is twice the number of a's because you accept for every 0 on the stack 1 b, but wrote twice 0 for every a on the stack.

In fact the language $L(A)=\\{a^n c^n b^n| n \in \mathbb{N}\\}$ can't be accepted by any PDA, but only a linear bounded automate(LBA) or a Turingmachine (or other similar models) The reasoning is that if you count the number of a's and want to have the same number of c's and b's later(not mixed) your stack will be empty after you sucessfully counted all the c's and the PDA will have forgotten the number to check whether the b's appear in this number.
> 1 votes

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


title: Counting directed graphs

text:
# Question
Title: Counting directed graphs
I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which means $A$ is containing equivalence classes defined by isomorphism.

i.e, given a graph (class) example $\[G\] \in A$ where $V\_G = \\{1,2\\}$ and $E\_G = \\{(1,2)\\}$ then if $G'$ is defined by $V\_{G'} = \\{3,4\\}$ and $E\_{G'}=\\{(3,4)\\}$ then $G' \in \[G\]$ and also if $G''$ is defined by $V\_{G''} = \\{1,2\\}$ and $E\_{G''}=\\{(2,1)\\}$ then $G'' \in \[G\]$.

In general $G' \in \[G\]$ if and only if $G'$ is isomorphic to $G$.

I need it to fulfill the restrictions:

1. If $|V\_{\[G\]}| \leq |V\_{\[G'\]}|$ then $f^{-1}(\[G\]) \leq f^{-1}(\[G'\])$
2. If $|E\_{\[G\]}| \leq |E\_{\[G'\]}|$ then $f^{-1}(\[G\]) \leq f^{-1}(\[G'\])$

I think the steps should be to give order to $\[G\], \[G'\]$ such that $|V\_{\[G\]}| = |V\_{\[G'\]}|$ and $|E\_{\[G\]}| = |E\_{\[G'\]}|$ in some natural way, find how to calculate the number of $\[G'\] \in A$ such that $|V\_{\[G\]}| = |V\_{\[G'\]}|$ and $|E\_{\[G\]}| = |E\_{\[G'\]}|$ as function of $n=|V\_{\[G\]}|, m=|E\_{\[G\]}|$ and then somehow find $f$. Not sure how to go about these steps, or how to find $f$ in some other way?

Thanks for any help!

# Answer
> 1 votes
Sure. Such a function exists. You have specified it. Basically, you order the equivalence classes according first to number of vertices, and second by number of edges. There are countably many graphs, so countably many equivalence classes, so they can be enumerated. When you can enumerate them, they can be put into bijective correspondence with $\mathbb{N}$.

This function is computable, by enumerating all graphs with a certain number of vertices and edges. e.g., for each $n:=1,2,3,\dots$, for each $m:=0,1,2,\dots,n^2$, for each graph containing $n$ vertices and $m$ edges, test whether it is isomorphic to any you have computed before, and use that to enumerate the graphs. Of course, this will be a particularly inefficient algorithm.

In principle there is no known polynomial-time algorithm for computing graph isomorphism, so I would not expect a polynomial-time algorithm for $f$ (but this is not a proof; and it's still possible there might exist algorithms that are relatively efficient in practice).

---
Tags: algorithms, graphs, combinatorics
---


# Question
Title: Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic
So a tournament is just a complete directed graph, I believe.

I'm having trouble proving this problem. I know it is induction however. I was thinking the base case is $2^1$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $2^{n + 1}$. But I'm not sure how to approach this. Any ideas would be extremely appreciated.

# Answer
A tournament is a loop-free directed graph $G=(V,E)$ in which, for each pair of distinct vertices $u,v \in V$, exactly one of $(u,v)$ and $(v,u)$ is in $E$.

The proof of your claim is by induction.

For $n=0$ the claim is true since a tournament $G$ with $2^0=1$ vertices is trivially acyclic, and its only sub-tournament with $0+1=1$ vertices is $G$ itself.

Assume now that the claim holds up to some $n \ge 0$ and consider a tournament $G=(V,E)$ with $|V|=2^{n+1}$. Pick an arbitrary vertex $v \in V$, and partition the vertices of $V \setminus \\{ v \\}$ into two sets $L = \\{ u \in V \setminus \\{ v \\} \mid (u,v) \in E \\}$ and $ R =\\{ u \in V \setminus \\{ v \\} \mid (v,u) \in E \\}$. One of $L$ and $R$ must contain at least $\left\lceil \frac{|V \setminus \\{v\\}|}{2} \right\rceil = \left\lceil \frac{2^{n+1} - 1}{2} \right\rceil=2^n$ vertices. Arbitrarily select $2^n$ vertices from this set, and call the set of the selected vertices $S$. By inductive hypothesis $S$ contains an acyclic sub-tournament $S'$ of size $n+1$, and since either $S' \subseteq S \subseteq L$ or $S' \subseteq S \subseteq R$, we have that $S' \cup \\{v \\}$ is also acyclic. This proves the claim since $|S' \cup \\{v \\}| = |S'| + 1 = n+2$.
> 1 votes

---
Tags: algorithms, graphs, induction, dag
---


# Question
Title: What solution to apply for finding the optimal parameters?
For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (`input_array`) and depending on their values it produces an output (response) signal.

The `input_array` contains 4 real values (parameters P1-4), with given and separate ranges. The output signal's quality is measured by calculating its signal-to-noise ratio (SNR). Each `input_array` variant can be applied to the system once every 3 seconds (not faster than 3 s).

I have to find the optimal `input_array` that produces the greatest SNR (preferably, in the least amount of time). That is, the combination of the 4 real values that maximizes the SNR (an optimal solution is sufficient; an absolute solution is welcomed, but not necessarily required). If helpful in finding a solution, the 4 parameters can be discretized, but their ranges would include hundreds of possible (discrete) values.

The values can be considered independent, no prior knowledge is available for them except their ranges, and their individual influence on the SNR is unknown. The SNR is a real value that is influenced by noise (thus, for the same `input_array` applied consecutively, it can have different (but close) values).

**What solution(s) can be applied to this problem?**

1. The simplest solution that comes to mind is to perform an **exhaustive search of the parameters domain**, but it is no applicable because the time required will be too long.
2. Initially, I was considering of applying **reinforcement learning** algorithms for continuous action spaces, by considering each parameter a separate action and returning a positive/negative reward when the SNR increases/decreases (e.g., +/-1). However, I think they would require too much time; nonetheless, I can stop the learning process at any time I consider that the `input_array` produces an acceptable SNR.
3. After further thinking, this problem seemed like a search problem, so I thought that **(heuristic) searching algorithms** may be appropriate.

**Does anybody have an idea what would be the most appropriate solution to this problem?**

# Answer
> 1 votes
It appears that you have a function $f:\mathbb{R}^4 \to \mathbb{R}$ and you want to find $x$ that maximizes $f(x)$, but you cannot compute $f$ directly; you can only obtain a noisy estimate of its value.

Many optimization methods can be adapted to this setting. A simple thing you could try would be an iterative method like gradient ascent or Newton's method, but with more iterations to account for the noise; the idea is that the noise will average out given enough iterations.

For instance, gradient ascent requires that you be able to compute the gradient $\nabla f (x)$ for any point of your choosing. In your case, this can be done by estimating

$$\nabla f(x) = ((f(x+e\_1)-f(x-e\_1))/2, \dots, (f(x+e\_4)-f(x-e\_4))/2),$$

where $e\_1=(1,0,0,0)$, $e\_2=(0,1,0,0)$, and so on. Now given the ability to compute $f$ on a point of your choice, by computing $f$ on 8 inputs, you can estimate $\nabla f(x)$ and then take a single step of gradient ascent; and repeat until convergence.

A more sophisticated approach would be to try using Bayesian optimization, such as Google Vizier.

---
Tags: algorithms, optimization, search-algorithms, heuristics, reinforcement-learning
---


# Question
Title: quicksort invariant 3 conditions with loop invariant
in studying Quicksort using the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the loop, the initialization, the maintenance and termination of the loop.

Based on the following algorithm, I don't understand properties 1 and 2 below:

Here is the algorithm I'm referencing:

Might someone help me understand conditions

1) if $p \leq k \leq i$ then $A\[k\] \leq x$

In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have `i = p-1`

2) if $i + 1 \leq k \leq j - 1 $ then $A\[k\] \> x$

In the algorithm for example, when we first enter the for loop, and j = 1, then $i$ would be 0.... I don't see how this works.

Thanks

# Answer
> 1 votes
> If $p \leq k \leq i$ then $A\[k\] \leq x.$ In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have `i = p-1`

Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ has been increased, for at least $k=p$, we have $p\le k\le i$.

Note that when $p\le i$ does not hold, i.e., when there is no $k$ such that $p\le k\le i$, the condition "if $p \leq k \leq i$ then $A\[k\] \leq x$" holds automatically. (Recall that the proposition "if false, then anything can happen" is always true.) To falsify that condition, we have to find an instance of $(p,k,i)$ such that $p \leq k \leq i$ but $A\[k\]\gt x$.

You should be able to figure out the case of the second loop invariant now.

# Answer
> 0 votes
I'm not in the mood of tracing a code rightnow, but understand that u start with A\[r\] =X and ends with A\[i\] =X

(the pivot, which seems to be chosen as the last element $r$ in the given code, reaches its correct position with the rest of the list get paritioned)

-At a first glance maybe the code has some errors, there is no need for the exchange in the then brackets, and the other exchange should be bet A\[r\] & A\[j\] inside the $ else $

---
Tags: quicksort, loop-invariants
---


# Question
Title: Can radix sort reach exponential time complexity?
For example, assume the input array is $$\[121212,212121\]$$ Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case example for radix sort?

If so, can I generalize this and say that given $k$ is the total number of digits, a worst case for the sort would be $\frac{k}{2}$ elements to sort?

# Answer
Let $n$ be the number of integers to sort, $M$ be the maximum integer, and $b$ be the chosen base.

Each execution of counting sort will take time $O(n + b)$ and the number of such executions is $O(\log\_b M)$. The total time complexity is then $O((n+b) \log\_b M)$.

If you want to ensure that this complexity is exponential in the input size $s$ (which is at most $O(n \log\_2 M)$) you need to select an exponential value of $b$, e.g., $b = 2^n$ if $M = O(2^{\text{poly}(n)})$.

If $b$ is constant (e.g., base $10$) then the time complexity of radix sort will always be $O(n \log M)$, which is always polynomial in the input size $s = \Omega(n + \log M)$ since $O(n \log M) = O( (n + \log M )^2 ) = O(s^2)$. This bound is tight when $M = \Theta(2^n)$.
> 1 votes

---
Tags: algorithms, time-complexity, radix-sort
---


# Question
Title: Is the language of words containing equal number of 001 and 100 regular?
I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a language such as $L$, where $L$ = $\\{ w \mid$ number of instances of the substring "001" equals the number of instances of the substring "100" $\\}$ regular? Note that the string "00100" would be accepted.

My intuition tells me it isn't, but I am unable to prove that; I can't transform it into a form which could be pumped via the pumping lemma, so how can I prove that? On the other hand, I have tried building a DFA or an NFA or a regular expression and failed on those fronts also, so how should I proceed? I would like to understand this in general, not just for the proposed language.

# Answer
**An answer extracted from the question.**

Yes, it is regular; below is an automaton that accepts it.

As pointed out by Hendrik Jan, there should be an additional 0 self-loop at q5.
> 6 votes

# Answer
It's a trick question. Try constructing a string that contains two 001 and doesn't contain a 100, and see why you can't do it. If X = "number of 001", and Y = "number of 100", then X = Y or X = Y ± 1.

Once you realise the trick, it becomes highly unlikely that the language is irregular, and then constructing a DFA is quite simple. There are only 8 states with their transitions if the next symbol is 0/1:

```
State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0

```

The initial state is S0, and S0, S1, C0, C1, C2 are accepting states.
> 5 votes

# Answer
We can write every string in $\\{0,1\\}^\*$ in the form $$ 0^{i\_0} 1 0^{i\_1} 1 0^{i\_2} \cdots 0^{i\_{m-1}} 1 0^{i\_m} $$ Here $i\_j \geq 0$, and $m$ is the number of $1$s.

The number of copies of $001$ is the number of indices $i\_0,\ldots,i\_{m-1}$ which are at least $2$.

The number of copies of $100$ is the number of indices $i\_1,\ldots,i\_m$ which are at least $2$.

We conclude that the number of copies of $001$ is the same as the number of copies of $002$ iff $$ i\_0 \geq 2 \Leftrightarrow i\_m \geq 2. $$ This leads to the following regular expression: $$ 0^\* + (\epsilon+0)(10^\*)^\*1(\epsilon+0) + 000^\*(10^\*)^\*1000^\*. $$
> 1 votes

# Answer
$L=\\{\epsilon, 0, 1, 01, 10, 010, 101, 00, 000, 0000,..... , 1, 11, 11111,......, 01110, 1001, 00100,.........\\}$ The pattern I can observe here is whenever we see a '001' as a substring then it has to be followed by 00 to make $n(001)=n(100)$ and whenever we see '100' as a substring then it has to be followed by 1 to make it '1001' to make $n(100)=n(001)$
> 0 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: About computable sets

text:
# Question
Title: About computable sets
Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that:

TOT = {e : ($\forall$x)($\exists$y)\[(e, x, y) $\in$ B\]

This definition means that TOT is a set of all Turing machines e such that they halt on all inputs. The "for all" x denotes all inputs to that machine, and "there exists" a y denotes that e halts under y steps. x consists of 0s and 1s, y and e are Natural numbers too ( e denotes Turing machine $T\_e$ if we were to number all our turing machines)

EDIT: SOLVED

# Answer
Let $T$ be the set of all Turing machines.

Let $B = \\{ (e,x, y) \in T \times \\{0,1\\}^\* \times \mathbb{N} : e(x) \text{ halts in $y$ steps}\\}$, and define $C = \\{e \in T : \forall x \in \\{0,1\\}^\*, \\; \exists y \in \mathbb{N}, \\; (e, x, y) \in B\]$.

We start by proving $\text{TOT}=C$.

If $e \in \text{TOT}$ then, $\forall x \in \\{0,1\\}^\*$, $e(x)$ halts. Let $y\_x$ be the number of steps needed for $e(x)$ to halt. Then $ \forall x \in \\{0,1\\}^\*$ there is a choice of $y \in \mathbb{N}$, namely $y = y\_x$, such that $(e,x,y) \in B$, showing that $e \in C$ and hence $\text{TOT} \subseteq C$.

If $e \not\in \text{TOT}$, then $\exists x \in \\{0,1\\}^\*$ such that $e(x)$ does not halt. Then $\exists x$, such that $\forall y \in \mathbb{N}$, $(e, x, y) \not\in B$, showing that if is false that $\forall x \in \\{0,1\\}^\*, \exists y \in \mathbb{N}$ such that $(e, x, y) \in B$. As a consequence $e \not\in C$ implying $\text{TOT} \supseteq C$.

It remains to show that $B$ is computable. To decide whether any given triple $(e, x,y) \in T \times \\{0,1\\}^\* \times \mathbb{N}$ belongs to $B$ it suffices to consider a Turing machine $T'$ that simulates $e(x)$ for $y$ steps. If $e(x)$ halts, then $T'$ accepts. Otherwise, if $e(x)$ does not halt by the end of the $y$-th step, $T'$ rejects.
> 0 votes

---
Tags: turing-machines, computability, undecidability, discrete-mathematics, church-turing-thesis
---


# Question
Title: Can I solve my decision problem in $O(n)$ time?
*My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms.*

Decision Problem: Given an input list $A$, can our target string $S$ be made from any of the elements of $A$?

If just one element does not exist in $A$ (which exists in $s$) then the algorithm returns false.

```
A = input_array
s = input_target_array

for i in s:
  if i in A:
    (all elements ∈ s) ∈ A
  else:
    break

(if any element ∈ s) ∉ A:
  return False
else:
  return True

```

**Output**

```
Enter your input for A and include spaces:
Enter letters WITH SPACES: "ab" "cd" "ac"
enter your input for s:
 "abxd"
^ False ^
 "abcd"
^ True ^

```

I'm looking for an algorithm that solves my made up decision problem faster than $O(n^2)$ time.

## Question

Are there any methods that can be used from an algorithmic standpoint that would make this $O(n)$ time?

# Answer
I use set difference to find out if there are any elements in $s$ that don't exist in $A$. This should be $O(n)$ in the best cases if there is a good hash. Since I'm dealing with integers it should be $O(n)$ Explained here

I then use $len(s)$ and $len(A)$ which takes $O(1)$ time according to here.

```
A = [1,2,3,4,9]
s = [1,2,3,4,9]

elem_not_in_A = set(s) - set(A)

if len(s) >= len(A):
    if len(elem_not_in_A) > 0:
        output False
    else:
        output True
else:
    output False

```

If the set difference remains $O(n)$ and all the other statements remain $O(1)$ then yes it can be solved in $O(n)$ time.
> 2 votes

---
Tags: algorithms, strings
---


title: Time complexity problem

text:
# Question
Title: Time complexity problem
Let Σ = {0, 1} and let A ⊆ Σ* be a language contained in DTIME(4n), and define

B = {xx | x ∈ A}.

(a) Show that B ∈ DTIME(2n).

(b) Prove that A ≤pm B.

I'm new to complexity theory. how can I show that if the language has the time complexity O(4n) how can i got about proving that its sublanguage has the complexity O(2n). also any help with the part(b) would also be appreciated.

# Answer
By hypothesis there is a Turing machine $T$ that decides $A$ in time $O(4^n)$.

Regarding a): you can design a Turing machine $T'$ that given $x$ operates as follows:

* First, it computes $|x|$ (i.e., $n$) in time $O(n)$. If $|x|$ is odd it rejects.
* If $|x|$ is even, it simulates $T$ on the input $y$ of consisting of the first $\frac{|x|}{2}$ characters of $|x|$. $T'$ accepts if $T(y)$ accepts and rejects otherwise. Simulating $T(y)$ takes time $O(4^\frac{|x|}{2}) = O(2^n)$.

Regarding b): Given $x \in \Sigma^\*$ it suffices to consider $y=xx$. It is easy to see that $y$ can be constructed in polynomial time and that $x \in A \iff y \in B$.
> 0 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis
---