# Question
Title: Source and Destination IP of TCP connection
Five Tuple Identifier of TCP connection is (TCP, local IP, local port, remote IP, remote port).

I have made 3 computers in virtual box and set BOX1 for client, BOX2 for median, and BOX3 for server. And made interfaces between them to communicate.

So I have executed the server program on BOX3 and client program in BOX1. The client program calls 10.0.2.2.

When I captured packets from BOX1 and BOX3, the IP Source and Destination IP address was like this.

```
BOX1's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

BOX3's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

```

What I have thought is that in BOX1, Src must be 10.0.1.2 and Dest must be 10.0.1.1. And in BOX3, it must be 10.0.2.1 for Src and 10.0.2.2 for Dest. Because BOX1 communicates with BOX2 and BOX3 commuicates with BOX2.

Why does IP is like that?

Thanks for your help.

# Answer
If you consider the format of the TCP-IP datagram.

Source Address: The 32-bit IP address of the originator of the datagram. Note that even though intermediate devices such as routers may handle the datagram, they do not normally put their address into this field—it is always the device that originally sent the datagram.

Destination Address: The 32-bit IP address of the intended recipient of the datagram. Again, even though devices such as routers may be the intermediate targets of the datagram, this field is always for the ultimate destination.

You can get more understanding here.
> 1 votes

---
Tags: network-analysis, tcp
---


# Question
Title: Inference and Unification algorithm provided to a Unification graph of two expressions
I am trying to unify two expressions given a unification algorithm $unify$ applied to the unification graph of the two expressions. However, I struggle a lot in understanding how exactly the steps of this algorithm is actually done - and my teacher failed to explain this in much detail. The following example is part of an exercise.

The two expressions I am trying to unify are: $$list(int) * list(alpha)$$ $$alpha * beta$$

With the following unification graph:

```
      *         *
    /   \      / \
   /     \    /   \
 list   list /     \
  |      |  /       \
  |      | /         \
 int   alpha        beta

```

The algorithm is from the `Dragon Book` and shown below:

---

```
boolean unify(Node m, Node n) {
    s = find(m); t = find(n)
    if (s = t) then true;
    else if (nodes s and t represent the same basic type) return true;
    else if (s is an op-node with children s1 & s2 and
             t is an op-node with children t1 & t2) {
        union(s,t)
        return unify(s1,t1) and unify(s2,t2)
    }
    else if (s or t represents a variable) {
        union(s,t)
        return true;
    }
    else return false;
}

```

---

My method of approach with this algorithm yielded the following result:

**(1)** Union the two constructors $\*$ and call unify(list,alpha) and unify(list,beta)\_

**(2)** Since the dragon book states that a variable is a leaf node, I can use Step III to union list \<- alpha, and list \<- beta. This returns true in the function.\_

From above I have that $alpha = list(int)$ and $beta = list(alpha)$. I can then construct the unified type to be: $$list(int) * list(list(int))$$

Can anyone verify for me if this is correct? I found the algorithm a bit tricky to understand, especially since I compare a constructor `list` with basic types in the (2) step.

# Answer
> 1 votes
Yes, your solution and process are correct, assuming that `alpha` and `beta` are variables. It might help to rewrite your terms in a more uniform way, e.g.

```
T1 = *(list(int), list(alpha))
T2 = *(alpha, beta)

```

Here, a term always satisfies the grammar:

```
Term ::= Constant
       | Variable
       | Func "(" Term+ ")"

```

Furthermore, it might clarify things to think of the unification process as taking a third argument: a *substitution* in which the two terms are to be unified. This substitution is simply an association between variables and terms, and it provides a context in which to resolve variables. Additionally, the unification process results in either a failure (if the terms do not unify in the substitution), or a substitution which both indicates success *and* provides a way to construct a "most general unifier".

---
Tags: compilers, type-inference, unification
---


title: Understanding memory leaks in C/C++

text:
# Question
Title: Understanding memory leaks in C/C++
I was looking at an example here: https://blog.parasoft.com/finding-memory-leaks-in-c

```
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char *string, *string_so_far;
    int i, length;     length = 0;
    for(i=0; i<argc; i++) {
        length += strlen(argv[i])+1;
        string = malloc(length+1);

        /*  * Copy the string built so far. */
        if(string_so_far != (char *)0)
            strcpy(string, string_so_far);
        else *string = '\0';
        strcat(string, argv[i]);
        if(i < argc-1) strcat(string, " ");
        string_so_far = string;
    }
    printf("You entered: %s\n", string_so_far);
    return (0);
}

```

and read that when we execute the program with the following arguments:

```
hello this is a test

```

The variable string\_so\_far points to the string “hello” which was assigned as a result of the previous loop iteration. But I don't understand how? A step by step explanation would be really helpful.

Secondly, I came across this example in course material:

```
int countPrimes(int n)
{
   PrimeSet *p = new PrimeSet(n);
      return( p->countPrimeNumbers() );
}

```

It was stated that there's a memory leak here but I don"t really understand how, probably because I am not sure what exactly is happening here.

# Answer
> 1 votes
In the first example, you use `malloc` inside a loop for a variable. The `malloc` call reserves a block of memory and returns the block's first address. You need to delete to block with `free` if you no longer need it. If the programmer wishes to extend the memory block, the better alternative would be `realloc`. Read more about `realloc` at http://www.cplusplus.com/reference/cstdlib/realloc/.

In your second example, the object in which the pointer `p` points to is initialized on the heap and will remain to stay in the heap until the programmer uses `delete`. A safer alternative for creating objects on the heap is creating it on the stack, which will remove every data after a method's call is finished.

```
int countPrimes(int n){
   PrimeSet p(n);
   return( p.countPrimeNumbers() );
}

```

If memory management is not done properly like in the second example, the object can not be deleted after the only reference to it is lost, hence a memory leak happens.

# Answer
> 3 votes
In your second example, you allocate space for a PrimeSet object and initialise it, then you call the countPrimeNumbers function. The PrimeSet object still exists, it still occupies memory, it probably allocated more memory, and all that memory is still occupied but not accessible. That’s a memory leak: Memory that is occupied but unusable.

---
Tags: memory-management, memory-access, memory-allocation, c, c++
---


title: Coin Change Problem(Greedy Algorithm)

text:
# Question
Title: Coin Change Problem(Greedy Algorithm)
In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin\_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?

Example- $(1,3,4)$ are denominations of coin. If I want to pay $Rs.6$ then the smallest coin set would be $(3,3)$. This solution set cannot be found by greedy Algorithm because it does not satisfy $(\frac{4}{3} \> \frac{3}{1})$.

# Answer
> 4 votes
For the set of coins (2,3,11). $\frac{3}{2}\<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to give us 22 cents. Then there is nowhere left to go, we cant possibly get to 23 from here. We do have a solution though with $(0,4,1)$

# Answer
> 0 votes
Check out Beck, *"How to Change Coins, M&M's, or Chicken Nuggets: The Linear Diophantine Problem of Frobenius"*, pp. 6-74 in *Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles* (MAA, 2009). Necessary and sufficient conditions for the greedy algorithm to work are given by Pearson, *"A Polynomial-time Algorithm for the Change-Making Problem"*, TR94-1433, Department of Computer Science, Cornell (1994). They are *much* more complicated to check than your proposal.

# Answer
> -2 votes
Say, set of `coin = {1, 10, 25}`

It doesn't satisfy `25/10 > 10/1` But still can be solved by greedy algorithm.

Now, say `X` is any set of coins in increasing order. Then, for all `a` and `b` in `X` where `a < b`, if `2*a <= b` satisfies, It will be solvable with greedy algorithm.

---
Tags: algorithms, optimization, greedy-algorithms, coin-change
---


# Question
Title: Proof of a greedy algorithm used for a variation of bin-packing problem
We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max\_val, and each weight is at most Max\_val. The variation is that the ordering of weights should not be changed, that is, $W\_i$ should be inside a bin before $W\_j$ is inserted, for all $i \< j$.

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!

# Answer
Let $G$ be the solution produced by the greedy algorithm. For each other solution $S$, let $i(S)$ be the index of the first weight at which $S$ diverges from $G$. Let $O$ be an optimal solution maximizing $i(O)$. Thus $G$ places $i(O)$ in bin $j$ (for some $j$), and $O$ places $i(O)$ in bin $j+1$. If we move $i(O)$ to bin $j$ (which is possible since $O$ is ordered), we obtain a solution $O'$ using at most as many bins as $O$, and satisfying $i(O') \> i(O)$. This contradicts the choice of $O$.

If we try to run this argument on the unrestricted bin packing algorithm, we will have trouble when moving $i(O)$ to bin $j$, since that bin might be occupied with other elements, not leaving enough room for $i(O)$. In the variant you consider, this cannot happen.
> 2 votes

---
Tags: proof-techniques, greedy-algorithms
---


# Question
Title: Construct regular expression that contains the substring
I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.

So far, the even number of b's can be constructed using like this:

```
   (aUb(aUc)*bUc)* or (cUa)*b(cUa)*b(cUa)*

```

to add the substring abcba, do I just attach it to the end of the regular expression and then repeat it or is there a better way?

Any help is appreciated!

# Answer
Any string containing $abcba$ is of the form $xabcbay$, where $x,y$ are strings. This string contains an even number of $b$'s iff $xy$ contains an even number of $b$'s iff either $x,y$ both contain an even number of $b$'s, or both contain an odd number of $b$'s. This leads to the following regular expression: $$ (a+c)^\*(b(a+c)^\*b(a+c)^\*)^\*abcba(a+c)^\*(b(a+c)^\*b(a+c)^\*)^\* + \\ (a+c)^\*b(a+c)^\*(b(a+c)^\*b(a+c)^\*)^\*abcba(a+c)^\*b(a+c)^\*(b(a+c)^\*b(a+c)^\*)^\* $$
> 1 votes

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


# Question
Title: find shortest paths from source to all vertices using Dijkstra’s Algorithm?
For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph ***but*** how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For example : What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.

# Answer
> 1 votes
I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's.

First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column *i* and *j* corresponds to the shortest distance from vertex *i* to vertex *j*.

Second, to mark the all-path shortest paths' path, you simply set the *parent* property of each vertex *j* to the current vertex *i* you are visiting from every time you have to relax the edge going to *j* from *i*. Keeping one set of vertices and edge will be sufficient as an APSP will also produce a tree, similar to a SSSP tree.

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


# Question
Title: Using Dijkstra's algorithm with negative edges?
Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.

Wouldn't an obvious solution to this be to *not delete the node*? Why not keep the node in the queue, so if a future *shorter* distance is found, it can be updated? If I am misunderstanding the problem, what *is* preventing the algorithm from being used with negative edges?

# Answer
Short answer is that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice.

**Here's an analogy:** (that might help, or confuse even more) Take a convex optimization problem and poke a concavity into it. Now ask the question why it can't be solved with a linear program. The problem is that the linear program's premise is that once we reach the edge of a convex surface in the direction of optimality, we know for certain it is optimal. With a concavity, this no longer works and the algorithm falls flat. The negative values are like these concavities, they introduce local extrema making it harder to find the global one.
> 6 votes

# Answer
Yes, not deleting the node is the obvious and accepted solution to negative edges. The trick here is that for whatever historical reasons, and as part of a diabolical scheme to better confuse you, we use a different name for this modified algorithm\*:

Bellman-Ford algorithm.

\*ok, there are some caveats but I'm trying to just gloss over things here...

> The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.
>
> If a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is reachable from the source.\[1\]

---

**Caveats:** As pointed out by nhahtdh in the comments, you need to keep in mind that, if negative edges are allowed, then it might be possible for infinite negative loops to exist and if that is the case, there might be no minimal length path. If someone is not mentioning negative edges to you its likely because they don't want to bother with this kind of detail.

Also, as pointed out by JeffE in the comments, although the basic "relaxation" step is the same in both algorithms, the optimization using the priority queue doesn't really apply when there are negative edges and it can actually turn out to be counterproductive.
> 5 votes

# Answer
A slight variant to Dijkstra algorithm will work on a graph with negative weight, without negative cycle (Competitive Programming 2, Steven Halim). For a general graph (which may contain negative cycle), use Bellman-Ford algorithm, which has fixed time complexity of O(VE), but guarantees termination, and allow detection of negative cycle (we **detects** the negative cycle, since the shortest path is ill-defined in this case).

We can categorize nodes in Dijkstra's algorithm into 3 types of nodes: ***processed*** (whose value will never change), ***unprocessed*** (has non-infinity value, but may change), and ***unreached*** (whose value is infinity, since we haven't reached the node). In the pseudocode for Dijkstra algorithm on Wikipedia (original?), relax operation is never called on processed node.

A variant to Dijkstra's algorithm will only store the unprocessed nodes in a data structure for "get-min" and "update" operation, and pop out node to process it. It will relax **all** neighbors of the node alike, and **push/modify** whichever node whose distance is improved back to the data structure. In this way, the *processed* node can be reverted to an *unprocessed* node, and its neighbors will be updated again when it is popped out. The method is correct, since changes to the current best value of a node is always propagated.

The complexity of the variant on **any** non-negative-cycle graph is in the worst case is exponential time, since it allows reevaluation of the vertices. The actual run-time of the variant is dependent on the data. In the original version, each vertex is only popped out once, while in this variant, a vertex might be popped out more than once.

There is no difference is time complexity if the variant is run on a positive weighted graph.
> 5 votes

# Answer
For directed negative edges: Since a negative edge makes that distance appear shorter, the true shortest path could end up not being given as the answer. Hence the problem.

For non-directed negative edges: You could enter an infinite loop trying find the "shortest path" as the negative edge creates a distance that goes to negative infinity.

This occurs because Djikstra's algorithm is a greedy algorithm, as Gustav mentions in another answer here.
> 1 votes

# Answer
For Dijkstra's Algorithm, at every step, the visited node, v, is done and never visited again (invariant) , the edge to that node v is the min edge.

To show why Dijkstra's Algorithm would not produce a optimized shortest path, let's take this graph with negative edge (A, B) as an example, at the start there are S (source node), A, B, C, D.

1. Starting at source node S, we would choose the edge (S, B) as the edge weight is shorter.
2. Node is would be marked done and the edge (S, B) would be set as the min edge from S to B.
3. Since Dijkstra is a greedy Algorithm, node B is visited and would never be visited again.

But there is a shorter path from S -\> A -\> B of weight 0. Dijkstra would provide a wrong path since it might not be considered due to the invariant of the algo.

> Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated?

It would be slower, keep it only if you need to. If you do that, you are essentially writing the Bellman Ford Algorithm, so I would refer address it as the Bellman Ford Algorithm. It is the original shortest path algorithm. Assume a graph of V vertices and E edges. Note that Dijkstra $ O((V + E) log V) $, is slightly faster than Bellman Ford $ O (VE) $, as it is a optimized version of Bellman Ford.

i. Dijkstra is faster than Bellman Ford due to it's invariant. It would only visit each vertex once and the edges it checks would reduce as vertex visited increases, since it assumes the edges it sets would be the best path. Whereas,

ii. Bellman Ford algorithm would run the relax function for V times on E edges. It works by overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated path. After 1 iteration of relaxing E edges, one edges is the best path.

So if you correctly tweak the program to keep the edge, it would be slower. In algorithm, you often have to trade time and function, time and space, it depends on you.
> -1 votes

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


# Question
Title: Why is two-phase commit better than naive master-slave replication?
In the context of a distributed database, I'm trying to understand why 2PC (as described in e.g. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L6-2pc.pdf) is better than the following hypothetical protocol between a client, master, and slave:

* client tells master to commit
* master commits it
* master tells client the commit succeeded
* master tells slave to replicate the commit. If the slave fails, master keeps on trying until it succeeds and gets the slave caught up on all edits.

This seems to me to satisfy the same properties as 2PC:

* Safety: If the master commits, the slave will also eventually commit. If the slave commits, the master must have committed first. I suppose an advantage of 2PC is that if a participant fails before starting the commit, the transaction will be failed instead of only committing on the TC. However, in the proposed protocol, the commit on the master still eventually gets to the slave.
* Liveness: This protocol does not hang.
* Both rely on the master / TC durably recording the decision to commit. Both assume failed slaves / participants eventually wake up and catch up with the master / TC.
* Both fail if the master / TC goes down.
* In both protocols, it's possible to have temporary inconsistencies where the master / TC has finalized a decision, but the slaves / participants haven't yet committed.

It seems to me that the key theoretical difference in 2PC is that the participant (slave) can vote "no" to the commit, as opposed to merely temporarily failing. That would break the conclusion above where the slave eventually catches up. However, I don't see why the slave would need to vote "no" in the first place. Given the assumption that the slave / participant does not permanently fail, it seems it should either vote "yes" or fail to respond. (Unlike the bank account example, I expect the slave to blindly replicate the master.)

**Distilling all this down, it seems to me that 2PC's assumption that participants don't permanently fail makes it unnecessary to give participants a chance to vote "no" in the "prepare" phase.**

What am I missing here? Presumably there's some advantage to 2PC over the above that I'm not understanding, since 2PC is actually used to build distributed databases.

* Am I incorrect in concluding that a slave shouldn't need to explicitly vote "no", as opposed to temporarily failing? (I'm only talking about the data replication use case, rather than the bank account example.)
* Given the same assumptions as 2PC, and assuming slaves only say "success" or "try again", is there some guarantee 2PC offers that the naive replication above doesn't?

For the purpose of the question, I'd like to ignore practicalities, unless they're critical to the answer. In particular, I'd like to ignore things that could be interpreted as being disallowed by the no-permanent-failure assumption, such as disk full, slave mis-configured, slave corrupt, operator error, buggy software, etc.

# Answer
You are confusing the purpose of the algorithms. The 2PC is a voting algorithm where the two sides have different data and different criteria for choosing a vote. The master-slave is a redundancy algorithm that aims to have identical copies at two places.

Besides, your master-slave is asynchronous where you return to client before replication. The client sees completion but the master can still become irrecoverable before replication, at which point you have data loss. 2PC is not subject to this.

That said, organizations may use 2PC in to implement master-slave, by making the “slave” always vote yes. This is essentially master-slave in synchronous mode, with unnecessary message overhead.

What you want to advocate for is probably synchronous master-slave, where you return to client after the slave confirms. It’s faster than 2PC because you only need one message exchange for each slave, instead of the two exchanges required for 2PC.
> 2 votes

---
Tags: distributed-systems
---


# Question
Title: spanning tree implemented by a min priority queue
if it is executed on unconnected graphs what will it execute? I thought it won't execute since it is unconnected but since it is being implemented by min priority queue, will that affect the results?

# Answer
It would generate the MST for the component of the graph which the MST algorithm starts at, leaving the unconnected components untouched.
> 0 votes

---
Tags: algorithms, minimum-spanning-tree
---


# Question
Title: Checking whether union of two languages is regular
How to check if

$L = \\{c^ka^nb^n \mid k\>0 \wedge n\geqslant0\\} \cup \\{a, b\\}^\*$

is regular ,where

$L\_1 = \\{c^ka^nb^n \mid k \> 0 \wedge n\geqslant0\\}$ is clearly not regular and $L\_2 = \\{a, b\\}^\*$ is... ?

# Answer
> 1 votes
If $L$ were regular than so would the following language be: $$L \cap ca^\*b^\* = \\{ ca^nb^n \mid n \geq 0 \\}.$$ You can show that the latter language is not regular in various ways.

---
Tags: automata, regular-languages, proof-techniques
---


# Question
Title: Is matrix multiplication cheaper than inverse?
In wiki, it is shown that the time complexity of matrix multiplication and matrix inverse is similar. But people always to argue it is easier to do matrix multiplication rather than inverse. Is this claim true? Maybe we need to consider various computation platform, CPU or GPU.

# Answer
> 3 votes
Matrix multiplication and matrix inverse have the same *asymptotic* running time. If we denote the running time of multiplying two $n \times n$ matrices by $T\_1(n)$, and that of inverting an $n \times n$ matrix by $T\_2(n)$, then this means that there exist constants $A,B$ such that $$ T\_1(n) \leq AT\_2(n) \\ T\_2(n) \leq BT\_1(n). $$ However, the constants $A,B$ can be significant. (Also, numerical stability might be an issue.)

Checking your claim is, however, very easy in practice. Choose your favorite matrix library (e.g. LAPACK), and you can determine empirically $T\_1(n),T\_2(n)$ for the values of $n$ that you are interested in, on the hardware platform that you are interested in.

---
Tags: multiplication, matrix, matrix-multiplication
---


# Question
Title: Lower bound time complexity for obtaining an arbitrary entry in a hashtable
I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable, the algorithm should return a pointer to an arbitrary nonempty entry in the hashtable. My answer was quite casual and I am not confident if my proof was correct. I am rephrasing the problem statement below:

* We are allowed to extend the `insert()`/`remove()` operations of a hashtable
* We need to expose a `get_arbitrary()` operation that always returns a nonempty entry in the hashtable if it is nonempty, or nil if it is empty.
* We are allowed to store extra data related to hashtable
* Assume hash keys are uniformly distributed.
* Assume `insert()`/`remove()` have memorylessly equal probability to be called on any key that exists in the hashtable.

This problem asks if it is possible to draw some relation on the lower bounds of the

* time complexity of `insert()` $T\_i(n)$
* time complexity of `remove()` $T\_r(n)$
* time complexity of `get_arbitrary()` $T\_a(n)$
* space complexixty of any extra data we are storing, in addition to the original hashtable $S(n)$

One of the conjectures I thought of (as mentioned in the linked StackOverflow question) is $T\_a(n) = O\left(\frac n{S(n)}\right)$, but I am not sure if this is correct. Also I am interested in knowing something can be said about how $T\_a(n)$ relates to $T\_r(n)$.

# Answer
We usually assume that a reasonable proportion of entries in a hash table are used, or we would be wasting memory. If we know that a hash table is at least 20% full then we can just visit random locations until we find a used one , five or so in this case (starting with a random entry and checking consecutive entries wouldn’t work with badly distributed hash keys). You could do this if you re-hash the table with fewer slots if it gets to empty, or if you know that you never delete any hash entry.

You could have a bitmap of unused entries which would make the search faster by a large constant factor. You could create a linked list of the used slots if less than 20% of slots are used and maintain it until usage exceeds 50%, instead of re-hashing.
> 2 votes

---
Tags: time-complexity, space-complexity, hash-tables, lower-bounds
---


# Question
Title: Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?
If an array $A\[1 \ldots N\]$ is represented using a segment tree having sets in each interval, why does a range query $\[L\ldots R\]$ returns at most $\lceil \log\_2{N} \rceil$ sets (or disjoint intervals)?

If came across this statement while reading this answer.

To quote:

> Find a disjoint coverage of the query range using the standard segment tree query procedure. We get $O(\log n)$ disjoint nodes, the union of whose multisets is exactly the multiset of values in the query range. Let's call those multisets $s\_1, \dots, s\_m$ (with $m \le \lceil \log\_2 n \rceil$).

I tried searching for a proof, but couldn't find it on any site. Can anyone help me prove it?

# Answer
Here's the basic idea.

Let a *dyadic* interval be an interval of the form $$ \[2^b a,2^b(a+1)-1\] $$ for some integer $a,b \geq 0$.

**Claim 1.** If $m \< 2^n$ then any interval of the form $\[0,m-1\]$ can be written as the disjoint union of at most $n$ dyadic intervals.

**Proof.** Expand $m$ as a sum of decreasing powers of 2: $$ m = 2^{a\_1} + \cdots + 2^{a\_k}. $$ Then we can write $$ \[0,m-1\] = \[0,2^{a\_1}-1\] \cup \[2^{a\_1},2^{a\_1}+2^{a\_2}-1\] \cup \cdots \cup \[2^{a\_1} + \cdots + 2^{a\_{k-1}},2^{a\_1} + \cdots + 2^{a\_k}-1\]. $$

**Claim 2.** If $0 \leq m\_1 \leq m\_2 \leq 2^n$ then any interval of the form $\[m\_1,m\_2-1\]$ can be written as the disjoint union of at most $2n$ dyadic intervals.

**Proof.** The binary expansion of $m\_1$ and $m\_2$ is of the form $m\_1 = x0y, m\_2 = x1z$, where $|y|=|z|$. Let $m = x10^{|z|}$. Using Claim 1, we can express $\[0,m\_2-m-1\]$ as a union of at most $n$ dyadic intervals. Shifting these by $m$, we express $\[m,m\_2-1\]$ as a union of at most $n$ dyadic intervals. Similarly, using Claim 1 we can express $\[0,m-m\_1-1\]$ as a union of at most $n$ dyadic intervals. Shifting and inverting, we express $\[m\_1,m-1\]$ as a union of at most $n$ dyadic intervals.

(In both cases, one needs to check that shifting, and possibly inverting, preservers an interval being dyadic.)
> 2 votes

---
Tags: data-structures, arrays, search-trees, intervals
---


# Question
Title: One-way function is not injective when it is in NP
Let us $\Sigma = \\{0,1\\}$ and $f: \Sigma^\* \rightarrow \Sigma^\* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^\* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \rvert ^ k$. Thus, we can say that the function $f$ is *one-way function*.

We have language $L = \\{ w \\; | \\; \exists z \in \Sigma^\*, w = f(z)\\}$. The question is, how to prove that $f$ is not *injective* if $L \in NP \setminus UP$, where $UP$ is the class of unambiguous TM.

It is clear, that if $L \in NP \setminus UP$ then exists NTM which decides this language and may exist at least one acceptable path for $w \in L$.

# Answer
> 2 votes
Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.

Since $L$ is always in $\mathsf{NP}$ (using the very same machine), the contrapositive is exactly the statement you're after.

---
Tags: complexity-theory, turing-machines, np, cryptography, one-way-functions
---


# Question
Title: Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?
This is a question posted for extra practice (*i.e.,* not for credit):

> Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.

I'm not sure how to approach it. I see lots of near-answers online using $O(\cdot)$, but $\Theta(\cdot)$ is a little different because it means there is both an upper and a lower bound of $n^2$ and $n \log(n)$, respectively.

So, at its absolute best case, a $n^2$ algorithm may run in $\frac{1}{a}n^2$ time, which for large $a$ may be very fast compared to most quadratic algorithms. However, since $a$ is constant, as $n \to \infty$, the time for even a $\frac{1}{a}n^2$ algorithm will far surpass a $bn\log(n)$ algorithm, even if $b$ is very large.

This would lead me to believe the answer is **no**, an algorithm that runs in $\Theta(n^2)$ *cannot* run faster than a $\Theta(n \log n)$ algorithm when analyzed asymptotically as I have done.

With this said, if the *thing* that makes the $\Theta(n \log n)$ algorithm $\Theta(n\log n)$ happens very frequently but the *thing* that makes the $\Theta(n^2)$ algorithm $\Theta(n^2)$ does not happen frequently at all (either due to the nature of the algorithm or optimized design), then the *amortized* complexity of the $\Theta(n^2)$ algorithm may in fact be less than that of the $\Theta(n \log n)$ algorithm — even if the asymptotic complexity says otherwise — right?

If the two complexities given were $O(\cdot)$ rather than $\Theta(\cdot)$ then I may be inclined to side with the latter argument. The presence of the lower bound that $\Theta(\cdot)$ implies is giving me second thoughts though. Can anyone help point me in the right direction here and clarify if it seems that I am misunderstanding the use of $\Theta(\cdot)$ for asymptotic versus amortized analysis.

---

Edit: I don't think this is a duplicate of Sorting functions by asymptotic growth. I am familiar with how to use limits, etc. to classify and sort algorithms asymptotically. Speaking strictly in terms of asymptotics, I think the answer to my question is definitely **no**. The question quoted (as worded) seems more general though; it wants to know if there is *any* way that a $\Theta(n^2)$ algorithm can out perform a $\Theta(n \log n)$ algorithm. Is such an occurrence possible when considering amortized analysis rather than asymptotic analysis and the algorithms are structured as described above? Or is this irrelevant and the answer is still **no**?

# Answer
Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about".

For a specific example of this, look at matrix multiplication algorithms. For $n\times n$ matrices, the standard pencil-and-paper algorithm takes time $\Theta(n^3)$. Strassen's algorithm essentially considers the matrix to be a matrix of smaller matrices and improves the running time to $O(n^{2.81})$ but the algorithm is more complicated, so the constants hidden by the big-$O$ mean that Strassen is only likely to be faster for about $n\>100$. Coppersmith–Winograd is $O(n^{2.37})$ but is even more complicated and, as far as I'm aware, isn't used in practice, because it only wins on matrices that are too big for people to want to multiply anyway.

Another aspect is that some algorithms might be better or worse than others on real computers. If an algorithm's data access patterns play nicely with the cache, it can be thousands of times faster than code that sprays memory accesses all over the address space: algorithms based on hash tables are particularly bad at for that. $n^2 \< 1000n\log\_2 n$ for all $n$ less than about $14\\,000$. Likewise, an algorithm with a simpler branching structure in the code might run faster because the CPU pipeline is full more of the time.
> 4 votes

# Answer
The definition of $\Theta$ includes two constants that the function is multiplied with, and a smallest n where the relation applies. (There is an $n\_0$ such that for all n ≥ $n\_0$, $c\_1 g(n) ≤ f(n) ≤ c\_2 g(n)$).

If $n \< n\_0$ then anything can happen. And if one algorithm comes with much smaller constants, then it may stay faster for some quite large n. Asymptotically, no.

Let's say you have an algorithm examining n items. Most of the work is done in linear time. But one in a million of those items is "hard" and you take $\mathcal O(m^2)$ where m is the number of "hard" items. Another algorithm takes $\mathcal O (n \log n)$ no matter what. If $n = 1,000,000,000$ and $m = 1000$, the first algorithm will be a lot faster.
> 2 votes

# Answer
This would hold that for small cases, e.g., let n = 2, we know that $ 100nlogn = \Theta (n \log n)$ will be larger than $ 2n^2 = \Theta (n^2)$.

We can also use our 2 classic sorting algorithm as an example.

Insertion sort is $\Theta (n^2)$ runtime.

Merge sort is $\Theta (n \log n)$ runtime.

For a sorted array, insertion sort runs close to $\Theta (n)$ while merge sort is $\Theta (n \log n)$.
> 0 votes

---
Tags: complexity-theory, time-complexity, asymptotics, amortized-analysis
---


# Question
Title: When is it best to use the second chance replacement algorithm?
I'm going through 'Operating Concepts' by Silberschatz, Galvin and Gagne (The Dinosaur Book) and it mentions the Second-Chance Algorithm (not enhanced) as an improvement on the FIFO replacement algorithm.

My question is, is there ever a case where this algorithm would perform better than, say, the Least Recently Used algorithm or even something like the Farthest-in-Future Algorithm? The book describes how the algorithm works but doesn't offer a lot of information on when it would be useful, other than just in improving 'FIFO'.

To add to this, is there ever a case where 'second chance' would out preform LRU? I'm assuming the answer is yes, as no algorithm is perfect for every situation.

# Answer
Farthest-in-future is optimal, second chance can't be better. Second chance is a way to approximate LRU when the required hardware (access times, sort them) isn't available. Both try to approximate the optimal strategy, there certainly can be cases where one or the other is better.
> 3 votes

---
Tags: operating-systems, paging, page-replacement
---


# Question
Title: Greedy proof: Correctness versus optimality
I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same sentence!

From my best unconfirmed understanding, the optimal proof uses "greedy stay ahead" where I need to show that greedy algorithm constructs a solution set that is no worse than the optimal set

The correctness proof utilizes the swapping argument to show that any difference between output set A and optimal set OPT can be eliminated by swapping the items in the optimal set.

Can someone clarify if I must only use the "greedy stay ahead" proof method for the optimal proof and not the correctness proof? And must I use the swapping argument (with contradiction) to show that swapping items in the optimal set?

Greedy stay ahead: http://www.cs.cornell.edu/Courses/cs482/2007sp/ahead.pdf

Swapping: http://www.cs.oberlin.edu/~asharp/cs280/handouts/greedy\_exchange.pdf (Note that author states that this proves correctness and ends with prove optimality)

Instance where swapping was used to prove optimality, greedy stay ahead used to prove correctness: http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/notes-5z-unit-5-filled-in.pdf

# Answer
You can use whatever proof method you want. Proofs aren't even limited to existing patterns such as "greedy stay ahead" and "swapping". Indeed, in some cases, such as the greedy algorithm for maximizing a submodular function over a uniform matroid, the proof consists of adding together a bunch of inequalities expressing the fact that the random choice was (greedily) optimal.

Usually the proof that a greedy algorithm works compares itself against an optimal solution, though when proving approximation guarantees, it could be enough to compare the greedy solution to the theoretical maximum (a case in point is the derandomized version of the random 3SAT algorithm).

Also, I suspect that "correctness" and "optimality" mean the same thing.
> 4 votes

# Answer
A greedy algorithm splits the solution to a problem into *steps*, and at each step it selects some *locally best* next step. The splitting can typically be done in several different ways, several criteria of best next step are often available. In the extreme, take that one that (by looking forward) *does* give the best solution (not very "local", that one...).

When considering greedy algorithms, you either want it to give an optimal solution (and that is considered "correctness"), or you are interested in it giving a *viable* solution *cheaply* (as an heuristic, or an approximate algorithm), and are interested in how far it is from the optimal solution.
> 0 votes

---
Tags: proof-techniques, greedy-algorithms
---


# Question
Title: RPI cluster performance related to network performance
I'm writing my thesis and i have built a RPI cluster, containing 10 nodes which consists of RPI model 3b. I've them connected to two gigabit switches. I don't know the CAT of the cables. They are not connected to the Internet, they just live in their private network.

Further more, i've calculated the theoretical performance by the formula:

number of cores * average frequency * 16 FLOPs/cycle = x GFLOPS (Got the formula from https://www.slothparadise.com/how-to-run-hpl-linpack-across-nodes/ )

after i applied it, it turns out i should have 76,8 GFLOPS in theory assuming that the source is relaiable and correct. When i benchmark it using HPL 2.1 i've only reached little about 7 GFLOPS at best when trying out various variations.

Now to my question: i've read up on the RPI model, and it says it only have 10/100 Ethernet. Is that the source of my problem? Seeing i get out GFLOPS from a node, but the network transportation is much less then Gigabit speed which would mean 76,8 GFLOPS * 0,1 Gigabit/second = 7,68 GFLOPS (in theory). Or am i way off the tracks in my thinking?

I really appriciate any help, so i can know if i have to keep working on the configuration for the benchmarking or if i can move on. Also, i'm sorry if i have posted in the wrong place.

Stay safe out there!

# Answer
I think i have solved it now. The problem was that in the example in the source they had:

8\*3,50\*16 and i was assuming (which is a very bad thing to do) that i should change everything except the 16, that it was a constant of sorts. Turns out, my RPI should have somewhere between 0 and 2 in the last multiple, alas it should be

4\*1,2\*x where x is somewhere between 0 and 2 (as my estimation) thus i have only to find out the actual number for X, and for some reason it seems hard to find it, one would have thought that the instructions per second or instructions per cycle would be documented for RPI.

bottom line, there was nothing wrong except for my thinking. sorry for this post, i should had read up a little bit more before i posted. I blame it on stress.

EDIT: i forgot to give the source that helped me solve the problem, here it is:

https://www.gpike.com/en/raspberrypi/benchmarking#hplc

and thx for the help!
> 0 votes

---
Tags: computer-networks, clustering, benchmarking
---


# Question
Title: Automaton-based model checking on finite traces
I want to check whether a formula in finite LTL is valid on a finite, linear trace.

For infite traces I would create a Kripke structure of the trace and a Büchi automaton for the negated formula, and check if the intersection is empty. Would this also work with a finite trace and formula in FLTL? I already tried adding another atomic proposition "alive" to the Kripke structure and automaton (like here https://spot.lrde.epita.fr/tut12.html). But how could I do it without this additional atomic proposition?

# Answer
The nice thing about finite traces is that they end at some point. LTLf is now a logic in which you can only look into the future, and not in the past.

This means that you label every character in the word by which subformulas of your LTLf formula hold for a word starting from that character. You start with the last character and just apply the semantics of LTLf there. Then you do the same for the second-last character, where you can use the fact that for the last character, you already know which LTL subformulas hold.

And then you continue in this way until you hit the first letter. Once you are done with that, you know for all subformulas if they hold there. You just have to look at the whole formula as subformula and are done.
> 1 votes

---
Tags: finite-automata, model-checking, linear-temporal-logic
---


# Question
Title: Problems for which a small change in the statement causes a big change in time complexity
I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability.

An example: The Hamiltonian path problem defined as

> Given a graph, determine whether a path that visits each vertex exactly once exists or not.

is NP-Complete while the Eulerian path problem defined as

> Given a graph, determine whether a trail that visits every edge exactly once exists or not.

is solvable in linear time with respect to the number of edges and nodes of the graph.

Another example is 2-SAT (polynomial complexity) vs K-SAT (NP-complete) although someone could argue that 2-SAT is just a specific case of K-SAT.

What do you call this kind of problems --if they even have a name? Can someone provide a list of other examples or some references?

# Answer
* Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$.
* Given a graph, decide if its vertices can be colored with 2 (3) colors. Two colors: it is equivalent to testing the graph for bipartiteness, Three colors: NP-Complete.
* Given a graph, decide if its edges be colored with 2 (3) colors. Two colors: trivial (color an first edge arbitrarily, follow all implied edges, repeat). Three colors: NP-Complete.
* Given a system of Diophantine equations, does it a admit a (non-negative) solution? Solvable in polynomial time if variables can be negative, NP-Complete otherwise.
* Given a graph and two vertices $s$ and $t$, what is the length of the shortest (longest) path between $s$ and $t$? Shortest path: essentially a BFS. Longest path: NP-hard.
* A lot of graph problems that are hard in general, are easy on trees (vertex cover, independent set, dominating set, ...). See Kleinberg & Tardos, perfect graphs, and notice that a minimum dominating set on a tree can be found by greedily selecting a parent $v$ of a leaf, deleting $v$ and its neighbors, and repeating.
* Given a directed graph, can you partition its edges into paths of length 2 (1)? For paths of length 1 the problem is trivial. For length 2 there it is a generalization of 3-dimensional-matching.
* Given a set of numbers, can it be partitioned into groups of 2 (3) elements so that all groups have the same sum? For groups of two elements it is trivial (the match of an element is completely determined by the element itself). For groups of $3$ it is the 3-partition problem.
* Given a NFA, does it accept (reject) at least one word? Accept: this boils down to a connectivity check between the initial state and the final states. Reject: PSPACE-Complete (search Universality problem).
* Given a graph $G$, two vertices $s$ and $t$, and $c \in \mathbb{N}$. Does $G$ contain $4$ ($5$) edge disjoint paths of length at most $c$? For 4 paths the problem is solvable in polynomial time, for 5 paths it is NP-hard.
* Given an edge-weighted graph $G$ and two vertices $s$ and $t$, what is the minimum (maximum) weight of a $s$-$t$ cut in $G$? See minimum-cut (polynomial) and maximum-cut (NP-hard).
* Given a set of linear constraints, is there at least one (integral) point in their intersection? Solvable in polynomial-time if variables are not restricted to be integers, otherwise NP-hard.
> 3 votes

---
Tags: complexity-theory, time-complexity, reference-request
---


# Question
Title: Math behind Multi-class linear discriminate analysis (LDA)
I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction.

So I understand for the algorithm to calculate for $k$ projection vector(s) you need to determine the eigenvector(s) that corresponds to the top $k$ eigenvalue(s). But can anyone explain what you do with those eigenvectors after you have calculated them to get a final output?

My guess is to multiply all of the eigenvectors (projection vectors) together and then multiply that with each point, $x$, in the original dataset to produce a new corresponding point $y$. Does this sound right?

# Answer
Given normalized top $k$ eigenvectors $v\_1,\ldots,v\_k$, you send a point $x$ to the tuple $(\langle x,v\_1 \rangle, \ldots, \langle x,v\_k \rangle)$.

Alternatively, you put the eigenvectors as rows in a matrix $M$, and you map the column vector $x$ to $Mx$ (this is exactly the same thing as above).

Multiplying vectors is an operation that doesn't have much semantic sense here. (How would you multiply them anyway, and why?)

There are reasons why we apply this particular operation, and they have to do with the goal of LDA. If you want to know more, I suggest picking up a decent textbook that explains LDA not only via formulas and algorithms, but also as the solution to an optimization problem.
> 1 votes

---
Tags: machine-learning, linear-algebra
---


# Question
Title: Performing semantic segmentation on images on word documents
At the moment, I'm making a comparative analysis between two different neural networks for a class. The problem they are both trying to solve is detecting tables on documents. Below is an example of one:

One of the algorithms I am analyzing is a *fully convolutional network.* The way the algorithm works is that it goes pixel by pixel and assigns each pixel a label of which class it could be in (in my case, table or not a table).

However, my issue is how should you pre-process/label your data if you're training one of these networks? Because tables themselves have words on them, looking at such a fine resolution to detect tables is not optimal. It would be preferable if I could have the FCN look for structural elements that help us identify tables (big gaps, columns, header, etc).

I'm not sure how to train a network that goes pixel by pixel to search for the bigger structural elements. Any thoughts on this?

# Answer
> 0 votes
There are many papers on document structure analysis. I suggest you read them, rather than trying to reinvent the wheel. As they say, a week in the lab can save a day in the library.

I think there may be some misconceptions. The way we evaluate neural networks is by trying them on a representative workload to see how well they perform. There are effectively no useful methods for performing a "comparative analysis". When you ask "how should you..", the answer with neural networks is typically "whatever works". There are no rules. Often helpful advice is to look for papers that have addressed this problem before and see what they do.

A plausible approach is to just feed in the entire image as input to the network, with no pre-processing (other than the standard pre-processing for images, i.e., to normalize pixels to mean 0 and variance 1).

Labels are more challenging, and that depends on what task exactly that you want to solve. Presumably, you need to manually label the images and then use those as your labels.

How would you train such a network? The same way you train any other network: you construct a training set, choose a loss function, and then use an optimizer to minimize the loss on that training set.

---
Tags: artificial-intelligence, neural-networks, computer-vision, image-processing
---


# Question
Title: P vs NP and Angle Trisection (serious question)
I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.

My understanding from many popular-level sources (like Scott Aaronson's P vs NP for dummies blog post, or this New Yorker article) is that the P vs NP question asks whether a problem that can be checked "quickly” can also be solved "quickly". But to my knowledge there are well-known problems that can be checked quickly but are impossible to solve regardless of time or number of operations.

Take, for example, the (in)famous angle trisection with straightedge and compass. If asked to check that a provided angle really does trisect 60 degrees, you can very quickly verify that fact using a straightedge and compass. But if someone asks you to solve the problem of trisecting that 60 degree angle using the same straightedge and compass, you can’t do it. So the solution here really only goes "one way" (i.e. using classical tools, the 20 degree angle can be checked really quickly, but no finite amount of operations/time will ever solve the problem of constructing it).

How does this relate to P vs NP? My thought is that this would show that NOT every problem that can be checked quickly can be solved quickly. The specific case of the 60 degree angle trisection appears to be checked in P time and not solved in P time (or any time for that matter, because by using classical tools the problem of the 60 degree trisection cannot be solved at all).

I know I’m missing something, and I tried looking up the formal definition of P vs NP on the Clay Math website, and that was way over my level of understanding (I’m betting that the categories of P and NP don’t apply to my example for reasons I am just not aware of). I just went through the exercise and tried to intuit the question using some well-known math, and I’m having a tough time figuring out where my mistake is.

Any thoughtful feedback is very much appreciated :)

PS: This was moved from CS Theory StackExchange b/c it is not a research q.

# Answer
> 3 votes
Here is a possible analog of the P vs NP question for straightedge-and-compass constructions.

Suppose that we are given a line with three points $a,b,c$ on it, and consider the following question:

> Given just the line and the points $a,b$, can we construct the point $c$ using a straightedge and compass?

If we are *given* a construction, then we can verify that it indeed constructs the point $c$. But without such a construction, it is not clear how to check whether the point $c$ can be constructed.

However, this connection is a bit misleading, for various reasons, among which is that it is not completely clear how to specify the input, and what operations are allowed on it; in contrast, the P vs NP question is completely formal.

---

The P vs NP question is a scaled-down version of other questions in computability theory, whose answer is known. For example:

> Given a C program $P$, does $P$ ever halt?

If $P$ halts, then we can verify it by running $P$ and checking that it eventually halts; you can think of this as a verification process in which the witness is the execution trace of $P$. But without an execution trace, it is not so clear how to determine whether $P$ ever halts. Indeed, Turing *proved* that no algorithm can determine whether a given C program ever halts.

---

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question can be stated as follows:

> Is there a polynomial time algorithm to determine whether an input graph is 3-colorable?

(A graph is 3-colorable if we can color its vertices using 3 colors so that the endpoints of each edge get different colors.)

Given a 3-coloring, it is easy to check (in polynomial time) that it is a valid 3-coloring. But without such a 3-coloring, it is not clear how to check whether a given graph is 3-colorable. Indeed, people conjecture that this cannot be done in polynomial time (but it can obviously be done in exponential time, by trying all possible 3-colorings).

# Answer
> 1 votes
First of all, P vs NP is about computability by Turing machines/computers and not about straightedge and compass constructions.

Your "problem", as you suspect, does not really fit the definition of "problem" in the sense of P vs NP.

A problem in the sense of P vs NP (formally called a "language") is simply a set of (binary) strings. So, if $\\{0,1\\}^\*$ denotes the set of all binary strings, then a language is simply any $L\subseteq \\{0,1\\}^\*$. The "problem" associated with a language $L$ is simply to check, given an arbitrary binary string $x$, whether $x\in L$ or not.

As a simple example, "the set of all gramatically correct English sentences" could be a language (the sentences should be encoded as binary strings but this is just a detail). Another example would be "the set of all numbers that are composite numbers (i.e., numbers which are not prime)". Being able to solve these problems quickly means being able to quickly (i.e., polynomial time) determine whether a sentence is valid English or whether a number is composite.

Formally, a problem can be "quickly checked" if there exists a procedure/algorithm/Turing machine that takes two inputs (binary strings) $x,y$. Given $(x,y)$, the algorithm must output either "yes" or "no". The rules are as follows:

* If $x\not \in L$, then the output is always "no".
* If $x\in L$, then there is *some* $y$ such that the output for $(x,y)$ is "yes".

And this must be done quickly (in polynomial time in $|x|$). You can think of $y$ as a "solution" for the problem instance $x$ and the algorithm as checking whether a solution is correct.

Going back to the example of composite numbers, the string $y$ could be the prime factorization of $x$. The procedure would take $y$ and verify that the numbers in $y$ when multiplied give $x$ (and then either output "yes" or "no" accordingly). This means that the "composite number problem" is in NP.

To cast "angle trisection" as a computational problem we would first have to define an encoding of "angles" as binary strings. Supposing that could be done, we could define $L$ as the set of (binary encodings of) angles that admit a straightedge/compass trisection. Clearly $L$ would be the empty set (or just the set of representations of $0^\circ$ angles if you allow those). The problem $L$ is trivial to solve since we can just output "no" by default since no (non-trivial) angle can be trisected.

---
Tags: p-vs-np, introductory-lesson
---


title: Minimum steps to sort array

text:
# Question
Title: Minimum steps to sort array
Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array\_i$, $array\_j$ and $array\_k$ be the values at those indices and now you make a right shift to it, that is $new$ $array\_i$= $old$ $array\_j$ and $new$ $array\_j$= $ old$ $array\_k$ and $new$ $array\_k$=$old$ $array\_i$. Find the minimum number of operations required to sort the array or if is impossible how to determine it.

Example : Consider $array= \[3,1,2\]$; consider indices $(1,3,2)$ in the given order after applying one operation it is $s =\[1,3,2\]$.

Can anybody share your approach.

# Answer
Your operations correspond to applying a 3-cycle on the input permutation. You can reach the identity by applying 3-cycles iff the input permutation is even. Given the cycle decomposition of the input permutation, it shouldn't be hard to answer your question (though the answer is not immediate).
> 1 votes

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


# Question
Title: What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph?
I am trying to find the best time complexity of an algorithm that calculates the weights of all the nodes on a graph. The weight of the node is defined as the sum of the weights of the edges adjacent to it. I can argue that the algorithm is similar to the one which would calculate the degree of all the nodes and that certainly takes O(|V|+|E|) but can we say the same thing if we are trying to calculate the weights of nodes?

# Answer
```
for i in V:
    weight(i) = 0
for e=(i,j) in E:
    weight(i) = weight(i) + weight(e)
    weight(j) = weight(j) + weight(e)

```
> 1 votes

---
Tags: time-complexity, algorithm-analysis, weighted-graphs
---


# Question
Title: Why do logic gates behave the way they do?
I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why **logic gates**/**boolean logic** behave the way they do.

Why for example:

```
1 AND 1 = 1  // true AND true
1 OR 0 = 1   // true OR False
0 AND 1 = 0  // false AND true

```

And so on..
Is it a conditional definition for example, like it is like that by definition?
Or there is a logical/intuitive explanation for these results?

I have searched google, also looked at the Wiki page of logic gates for an explanation of 'why' but I can only find 'how'.
I would appreciate any answer or resources.

# Answer
> 77 votes
As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here:

```
A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
-+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1
0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1
1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1
1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1

```

A and B are the inputs, 0 through f are the possible permutations of outputs.

These gates have been named:

```
0 = FALSE
1 = AND
2 = A NIMPLY B (A AND NOT B)
3 = A
4 = B NIMPLY A (B AND NOT A)
5 = B
6 = XOR
7 = OR
8 = NOR
9 = XNOR
a = NOT B
b = B IMPLY A (A OR NOT B)
c = NOT A
d = A IMPLY B (B OR NOT A)
e = NAND
f = TRUE

```

6 of these (0,3,5,a,c,f) discard one or both inputs. The IMPLY and NIMPLY gates are rare, though they are certainly used in formal logic. AND, OR and XOR are easiest for humans to reason with, but for physical hardware, NOR and NAND are also used heavily, because they can be simpler to implement and make smaller circuits. The same probably holds for XNOR.

So, as stated earlier, it's not so much that we decided that the gates should behave this way, but that 16 possible gates can be defined, and we came up with descriptive names for them.

# Answer
> 25 votes
It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions.

Say you put two statements, $p,q$, together to form a new statement, $r$.

In the case of `and` (logical conjunction), both $p$ *and* $q$ must be true for $r$ to be true. In the case of `or` (logical disjunction), $r$ is true if at least one of $p$ *or* $q$ are true.

# Answer
> 23 votes
I think the questioner has it backwards. If we have a logical function such that

```
    A | B | result
   ---+---+-------
    0 | 0 | 0
    0 | 1 | 0
    1 | 0 | 0
    1 | 1 | 1

```

then we **decide** to call that function *and* because it is obvious that the result is 1 only when A *and* B are both 1.

Similarly for *or*, *exclusive-or*, etc.

There are 16 possible logical functions of 2 operands --it's easy to list them all, it's just the permutations of the 'result' column above. Some have obvious names.. The field probably dates from George Boole. As far as circuits are concerned, any of the 16 could in principle be built, but some are more useful than others.

# Answer
> 9 votes
The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that if you can reason about how human language works you can maybe reason about how reason works.

Since the language I'm answering you in English let's use English as an example even though the original study of logic was probably on the Greek language. First let's differentiate the study of logic (or what is true and what is not true) from the other study of language: grammar. Grammar involves interpreting the meaning of words put together involving elements of syntax, morphology, semantics etc., that is not what we are studying. We assume that grammar is a given and you and I understand it. What we are studying is if a statement is true.

So let's take a look at AND in English.

Example 1:

```
My nickname is slebetman AND I am a stackexchange user

```

Ok, so is my nickname slebetman? Yes, so the first part of the sentence before AND is true.

Am I a stackexchange user? Yes because I'm writing this answer, so the second part of the sentence after AND is true.

In the English language, is the above sentence truthful? Yes. So we can see the first behavior of AND:

```
true sentence = something true AND something true

```

Or we can simplify:

```
true = true AND true

```

So let's look at another sentence:

```
My nickname is slebetman AND I don't understand English

```

In this case the first part is unchanged so it is still true but the second part is obviously false because this entire answer is in English. So we have `true AND false`. Is the entire sentence true? Would you say I'm not lying if I said the sentence above? Of course not, the entire sentence is false. So here we see the second behavior of AND:

false = true AND false

Since we can rearrange the sentence and still keep it false: `I don't understand English AND my nickname is slebetman` we can say that AND is commutative. Which gives us:

```
true  = true  AND true
false = true  AND false
false = false AND true

```

Finally it shouldn't be hard to convince you that if I said two false things and joined them by AND the entire sentence would still be a lie. Which defines what AND does:

```
true  = true  AND true
false = true  AND false
false = false AND true
false = false AND false

```

The same reasoning can be applied to OR and NOT.

In a sense, this definition is just giving an operator a name. What the operator really does is make sure all conditions are true. We could have named AND something different, maybe ALL (short for **all must be true**) and we could have named OR something different like ANY (short for **if any of the following is true**) and the logic would still work:

```
XANY(a,b) = ANY( ALL(a, NOT(b)), ALL(NOT(a), b))

```

But we have decided to call the operators AND and OR so instead we write:

```
a XOR b = (a AND (NOT b)) OR ((NOT a) AND b)

```

It's a bit arbitrary what we call the operators but if you need to know where they come from they come from our language (originally probably Greek **not** English) and over time and the application of formality gets adopted into mathematics and engineering.

# Answer
> 3 votes
The boolean operators (and, or) are functions that map two inputs to an output, just like any other binary operator (i.e. +). Their exact behavior (the why question) is an axiom of boolean logic, just as the behavior of addition is an axiom of mathematics, which is to say that we agree that these operators do what they do. It is therefore the bedrock of the system and it is meaningless to try explain why they work in this way, just as it is meaningless to explain why a rose is a rose: it is because we agree it is.

How the operators are implemented in a computer (the how question) is a matter of engineering and there are may other ways of implementing these operators other than using logic gates built from transistors (there is a video floating around of an adder built from dominoes for example).

# Answer
> 1 votes
To answer this, I think it is best to go back to those early 'Truth Tables' you probably saw in algebra. The first ones you see are 'and' & 'or'. We have two statements #1 & #2 (usually called p & q) which can either be true or false. Then, when we test them we have a result (usually called r).

For example,

# #1 p = I like red

# #2 q = I like dogs

**NOW** let's test the affirmative and negative statements using 'and'.

If #1 is True **AND** #2 is True then the result(r) is True.

* I like red **AND** I like dogs. This is True. \[1 and 1 then r = T\]

If #1 is False **AND** #2 is True then r = F

* I *don't* like red **AND** I like dogs. This is false. \[0 and 1 then r = F\]

If #1 is True **AND** #2 is False then r = F

* I like red **AND** I *don't* like dogs. This is false. \[1 and 0 then r = F\]

If #1 is False **AND** #2 is False then r = F

* I *don't* like red **AND** I *don't* like dogs. This is false. \[0 and 0 then r = F\]

---

**NOW** look at 'OR'

If #1 is True **OR** #2 is True then the result(r) is True.

* I like red **OR** I like dogs this is True. \[1 or 1 then r = T\]

If #1 is False **OR** #2 is True then the result(r) is True. \[0 or 1 then r = T\]

If #1 is True **OR** #2 is False then the result(r) is True. \[1 or 0 then r = T\]

If #1 is False **OR** #2 is False then the result(r) is False. \[0 or 0 then r = F\]

---

**NOW** Your questions

1 and 1 = 1, I like red and dogs. True
1 or 0 = 1, I like red or I don't like dogs. True
0 and 1 = 0, I don't like red and I like dogs, False ... Voila

# Answer
> 1 votes
You can look at it as two stages.

The first stage is that we want some particular outcome, such as wanting a 1 if either of the (2) inputs is a 1. We call this an “OR” gate. Another outcome that people want is to get a 1 only if both inputs are a 1. We call this an AND gate.

The final stage is that we want a particular gate for every possible combination (of two inputs and one output). Now, the only problem is having meaningful names for them all.

This gives us confusing things such as IOR (Inclusive OR) — two 1’s gives a 1 — and XOR (exclusive OR) — two 1’s gives a 0. It gives us amusing things such as NAND — the opposite of AND. …But in the end we have every possible gate, and a more or less intuitive name for each and every one.

# Answer
> 1 votes
I interpret question 'why' as asking for the purpose.

So imagine OR, AND and NOT as the simplest building blocks from which you can build almost anything else. (Just remember it as some kind of simplification: NAND gate seems to be more universal and simpler from electronic engineering point of view but is less intuitive for learning purposes)

As an example, let think of building a device for adding numbers (a sumator).

> 01010b + 00110b = 10000b
> 10d + 6d = 16d

Notice that we can build it from simpler blocks. Each one computes single binary digit at each position and 'carry out'.

In order to compute digit at each position we need:

> (A XOR B) XOR C\_in

Where C\_in is a carry remaining from computing previous digit. To build XOR gate from simpler gates, we can:

> A XOR B = (A AND NOT B) OR (NOT A OR B)

Another possibility:

> A XOR B = (A OR B) AND NOT (A AND B)

I will stop explaining sumator here. For more information please visit: Full adder circuit or Adder and subtractor. My objective here was to only describe an idea of logic gates as building blocks.

There is a class of electronic circuits called 'combinational circuits'. It simply takes some N bits of input and computes M bits of output. We can prove that every possible combinational circuit can be made of only NOT, AND and OR gates. Let see an example:

> ABC | XY
> 000 | 00
> 001 | 11
> 010 | 00
> 011 | 00
> 100 | 10
> 101 | 00
> 110 | 01
> 111 | 10

To compute X output, we can simply take each row, where X is 1, construct condition that must be fulfilled by NOTs and ANDs and connect each conditions with ORs.

> X = (NOT A AND NOT B AND C) OR (A AND NOT B AND NOT C) OR (A AND B AND C)

Similarly for Y:

> Y = (NOT A AND NOT B AND C) OR (A AND B AND NOT C)

For more information: Disjunctive Normal Form

Please note that it is only for proof purpose, to show that it is possible. It is obviously not optimal. Finding circuits for minimum number of logic gates is NP computing problem. Please also see: Logic Optimization

But combinational circuits are not only things we can build using AND, OR and NOT gates. If we add some kind of *feedback loops* we can gain an ability to generate clock signals (Multivibrators) or to remember things (Latches).

# Answer
> 1 votes
AND
I like red AND ripe apples.
If the apple is red and the apple is ripe, then the result is true
1 and 1 makes 1 (true)
The apple is green, so I don't like it
0 and 1 makes 0 (false)
The apple is red but not ripe
1 and 0 makes 0 (false)

OR
I'll eat an apple if it's ripe OR if it's red
The apple is red, but not ripe so I'll eat it
1 or 0 makes 1 (true)
The apple is green but it's ripe - I eat it
0 or 1 makes 1 (true)
The apple is not ripe and it's purple - no thanks
0 or 0 makes 0 (false)

# Answer
> 0 votes
> Is it a conditional definition for example?

Yeah, that's a good way to look at it.

One way of writing the definition of the AND operator is:

> The AND operator is that operator that takes two bits as input and gives one bit as output, such that
>
> * 0 AND 0 = 0;
> * 0 AND 1 = 0;
> * 1 AND 0 = 0;
> * 1 AND 1 = 1.

Likewise, one way of writing the definition of the OR operator is:

> The OR operator is that operator that takes two bits as input and gives one bit as output, such that
>
> * 0 OR 0 = 0;
> * 0 OR 1 = 1;
> * 1 OR 0 = 1;
> * 1 OR 1 = 1.

So, the reason that 1 AND 1 = 1 is that the definition says so. Likewise, the reason that 1 OR 0 = 1 is that the definition says so. And likewise for the other 6 equations; they're true because the definition says so.

# Answer
> 0 votes
$\def\N#1{{\left\[\text{#1}\right\]}}$***tl;dr*** There're only 3 possible gates that satisfy these properties:

1. depend on both of 2 binary inputs to produce 1 binary output;
2. don't discriminate between the inputs;
3. aren't just another gate $\texttt{NOT}\text{'d} .$

These 3 gates are usually described as $\texttt{AND} ,$ $\texttt{OR} ,$ and $\texttt{XOR}$ as the $3$ possible gates, along with their $\texttt{NOT}\text{'d} .$ variants, $\texttt{NAND} ,$ $\texttt{NOR} ,$ and $\texttt{NXOR} .$

---

For each possible input, there's $1$ possible function for each possible output. This means $$ \N{functions} ~=~ {\N{possible outputs}} ^ {\N{possible inputs}} \\,. $$

Here, there're two possible outputs, $\left\\{0,\\,1\right\\} ,$ and there're four possible inputs, $\left\\{\left\\{0,\\,0\right\\}.\\, \left\\{0,\\,1\right\\}, \\,\left\\{1,\\,0\right\\}, \\, \left\\{1,\\,1\right\\} \right\\} ,$ so $$ \N{functions} ~=~ {2} ^ {4} ~=~ 16 \\,, $$ meaning that there're 16 possible gates. as shown @AI0867's answer.

If we exclude both of the inputs, that'd have been $2^1=2$ possible gates. These are the $\texttt{true}$ and $\texttt{false}$ gates, which always return $1$ or $0 ,$ respectively, without regard for their inputs.

If we exclude one of the inputs, that'd have been $2^2 = 4$ possible gates. These would be the identity-gate (return the input), the NOT-gate (invert the input), plus the {true, false}-gates again. So, that's $2$ gates that depend only on one of the inputs.

Since there're 2 inputs, there're:

* 2 gates that don't care about either input;
* 2 gates that don't care about the first input; and
* 2 gates that don't care about the second input;

for a total of 6 gates that don't care about both inputs, reducing the 16 possibilities down to 10 gates which can be meaningfully described as having 2 inputs.

Then, we can note that of these 10 gates, half of them just return the inverted input $(\text{e.g.},$ $\texttt{AND}$ vs. $\texttt{NAND}).$ So we can say that it's just 5 gates, plus their inversions. @AI0867's answer covered this, too.

The point I'd add is that this analysis assumes that inputs are ordered; for example, $\left\\{0,1\right\\}$ is distinct from $\left\\{1,0\right\\} .$ However, in practice, we don't tend to discuss gates which discriminate between the inputs.

So, instead of having $4$ distinguishable inputs, we have $3 .$ Then, that's $2^3 = 8$ possible gates. We again remove the $2$ that don't depend either gate; we don't remove the other $2+2=4$ that didn't depend on just one gate because we no longer distinguish between the two gates, so those cases already don't exist. This leaves $2^3-2=6$ possible gates that:

* depend on both inputs; and
* don't discriminate between the inputs.

Then, again, we can note the inversion of the outputs, so instead of saying $6$ different gates, we can say that there're $3$ gates with their inversions.

This leaves $\texttt{AND} ,$ $\texttt{OR} ,$ and $\texttt{XOR}$ as the $3$ possible gates, plus their inversions, $\texttt{NAND} ,$ $\texttt{NOR} ,$ and $\texttt{NXOR} .$

In short, when we talk about gates as though only 3 binary-gates exist (plus the unary $\texttt{NOT}$ gate), that's because there're only 3 that:

1. depend on both inputs;
2. don't discriminate between the inputs;
3. aren't just another gate with the output inverted.

---
Tags: computer-architecture, logic, boolean-algebra, definitions
---


title: PDA for parentheses language

text:
# Question
Title: PDA for parentheses language
> Construct a PDA for the language described by the following CFG: $$ S \to \[S\] \mid \\{S\\} \mid \Lambda $$

How can I develop a pushdown automaton for this language?

# Answer
> 0 votes
When you see \[ or {, push it onto the stack.

When you see \], pop \[ off the stack (if \[ is not the top of stack, reject).

When you see }, pop { off the stack (if { is not the top of stack, reject).

Accept if at end of input, the stack is empty.

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


# Question
Title: PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$
I'm pretty new to the PDA topic.

How do I construct an NPDA for the language $$L= \\{w : n\_a(w)+n\_b(w) = 2n\_c(w)\\}.$$

I've tried all the possibilities, but I still somehow end up accepting all words.

# Answer
The idea is to store a counter $n\_a(w) + n\_b(w) - 2n\_c(w)$ in the stack. If this number is positive, say $x$, we want to have $x$ many P's on the stack (and nothing else). If this number is negative, say $-y$, we want to have $y$ many N's on the stack (and nothing else). Otherwise we want to have a special indicator $O$ on the stack. At the end, we check that the stack consists of $O$.

I'll let you work out the details.
> 1 votes

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


# Question
Title: When computing asymptotic time complexity, can a variable dominate over other?
I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $n$ strings, each string of length $k$ letters. Using merge-sort, sorting a list of $n$ elements requires $O(n\log n)$. Comparing two strings of length $k$ has a cost of $O(k)$. Therefore, the cost would be $O(kn\log n)$.

However, I know some restrictions about $k$ and $n$ due to the nature of the problem. In particular, I know that for any list, $0 \lt k \leq 20$, and $0 \lt n \leq 80000$. In other words, the number of words in a list might vary in a much larger range than the length of the words.

In that case, would it be correct to say that $n$ dominates over $k$ and therefore the cost could be expressed as $O(n\log n)$? Or does the fact that we are discussing asymptotic costs make those restriction meaningless (as we are describing how the algorithm is impacted by the growth of each variable, regardless of how much they can actually grow)? In general, if two variables are independent, is it possible to dismiss one of them from the asymptotic cost under certain circumstances?

# Answer
First of all, if $k$ and $n$ are bounded then all complexities trivialize to $O(1)$. Hence a better assumption is something like $k = O(\log n)$. Under this assumption, you can, for example, say that $O(k + n) = O(n)$, and even $O(k + \log n) = O(\log n)$. However, you *cannot* say that $O(kn) = O(n)$, since it's not necessarily true! If $k = \log n$, then it's not true that $O(kn) = O(n)$. Instead, all you can say is that $O(kn) = O(n\log n)$.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: When directed graph is linear, return the nodes in order. Otherwise fail
# The Problem

I have a set of `edges` `(a, b)`, where `a` and `b` are nodes in a directed, acyclic graph (DAG).

The number of edges is guaranteed to be the number of nodes - 1.

I am looking for an algorithm that finds a sequence of nodes `[n_1, ... n_n]` so that the sequence contains *all* nodes in the graph, and that all edges `(n_i, n_i+1)` for `0 < i < n` exist in `edges`. If that sequence is not possible because the given set of `edges` is not equal to the set of edges required, then I need an error to be thrown.

Edit: the graph may have an arbitrary number of disconnected components. I obviously don't consider a graph with multiple disconnected components as linear.

# Ideas so far

Note that I am checking that the number of `edges` is exactly the number of edges required for such a sequence to exist. As a result, the algorithm can fail when there are two edges that share a source or a destination. However, I still need to get that sequence.

I realize that topological sort returns a linear order of a directed graph, which satisfies my requirements. However, I still want to fail when the graph is not exactly linear like that, instead of getting a linear order anyways.

Maybe I can validate, then do a topological sort. But that sounds inefficient. I am also not sure about the formal names of things in this problem, so it's hard to simply look up an algorithm. I feel like I am missing some simple connection or trick here.

**Could you provide me with an algorithm that accomplishes this? I'll take pseudocode or any language of your choice.**

# Answer
> 0 votes
I figured out an algorithm that at least passes my test cases:

```
let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
  if (next not in possibleStartNodes) fail
  remove next from possibleStartNodes
  nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode)
  ordering.push(next)
  currentNode = next
end while

return ordering

```

$O(n)$ looks pretty reasonable to me. Are there any ways to improve?

**Edit:** I would appreciate any hints about the correct technical terms for the concepts I'm using

# Answer
> 0 votes
Here is a quite non-optimal algorithm, to get you started.

Go over all edges $(a,b)$. For each edge, go again over all edges, and check how many times $a$ appears. Stop once you discover $a$ that appears only once (if this never happens, reject). We will take $n\_1 = a$.

Go over all edges again, looking for the unique edge $(n\_1,b)$ in which $n\_1$ appears. Take $n\_2 = b$.

Go over all edges again, looking for an edge $(n\_2,c)$ in which $n\_2$ appears on the left (if there is no such edge, reject). Take $n\_3 = c$.

Continue in this way, finding $n\_4,\ldots,n\_n$.

This algorithm runs in $O(n^2)$. Using hashing, you should be able to improve it to $O(n)$.

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


# Question
Title: Why $T(n)=6T(n-1) + n^3$ has such a mess solution?
I tried to solve the recurrence relation $T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^3$, and so on.

The formula as I understood it is: $\sum\_{i=0}^n 6^i(n-i)^3$.

After entering this in Wolfram, the result is:

$$ \sum\_{i=0}^n 6^i(n-i)^3 = \frac{1}{625}(-125n^3-450n^2-630n+366(6^n-1)). $$

And it doesn't look like a valid solution. Did I miss anything?

# Answer
> 2 votes
I'm not sure why you think this solution is invalid. It implies that $$ \sum\_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n, $$ and in particular, $$ \sum\_{i=0}^n 6^i(n-i)^3 = \Theta(6^n). $$ You can also check it for particular values of $n$.

For example, when $n = 0$ you clearly get zero, and for $n = 1$ you get $$ \frac{-125-450-630+366 \cdot 5}{625} = 1 = 6^0 (1-0)^3 + 6^1 (1-1)^3. $$

---
Tags: trees, recurrence-relation
---


# Question
Title: What is the time complexity of the following triple nested loop? Kindly solve in term of n
I want to ask that what is the time complexity of this function (triple nested loop) .Kindly analysis completely so that I can understand.

```
function loop_nested(n)
  r := 0
  for i := 1 to n - 1 do
    for j := i + 1 to n do
      for k := 1 to j do
        r := r + 1
  return(r)

```

# Answer
> 1 votes
The value of $r$ at the end is $$ \sum\_{i=1}^{n-1} \sum\_{j=i+1}^n \sum\_{k=1}^j 1 = \sum\_{i=1}^{n-1} \sum\_{j=i+1}^n j. $$ You take it from here. You can use a computer algebra system such as Wolfram alpha to help you with the calculations.

If you are only interested in asymptotics, then you can use the following upper bound: $$ \sum\_{i=1}^{n-1} \sum\_{j=i+1}^n j \leq \sum\_{i=1}^n \sum\_{j=1}^n n. $$ I'll let you work out what upper bound this gives. It turns out that this upper bound is quite good, as you can verify using the following lower bound (valid for large $n$): $$ \sum\_{i=1}^{n-1} \sum\_{j=i+1}^n j \geq \sum\_{i=1}^{n/2} \sum\_{j=n/2+1}^n n/2. $$

---
Tags: time-complexity, asymptotics, programming-languages, loops, computer-algebra
---


# Question
Title: Clock page replacement policy vs LRU page replacement policy, is Clock more efficient?
I'm currently learning about database systems and they mention a buffer management system which brings in pages from disk to memory. This buffer manager allows higher layers to operate as if the entire database on disk is actually in memory.

The video I am watching talks about LRU and Clock as the page replacement policies when a page doesn't exist in the buffer pool.

However what I am confused about is that this video mentioned that LRU was log n in efficiency, but Clock is a better algorithm.

Specifically, imagine the buffer pool being a hash table with page id as the key. The value is dependent on if we are doing LRU or Clock.

If LRU was implemented with a heap data structure, maintaining this structure would be O(log n). ie A read of a page is constant to see if it's in the hash table. If it is, the value points to somewhere on the LRU data structure, which needs an update since the 'last used' time has changed. This means every read, updates the LRU so this is O (log n).

For a clock page replacement policy, modifying a page's last used bit to 0 is constant time, because the page id is a key in the hash table and modifying it's value is O(1).

However for a clock replacement policy, finding a page with a last used bit = 0 requires scanning the buffer pool. That is o(n). For LRU, we just grab the root node which is O(1) and delete it which is log(n) and insert a new node which is log(n). So LRU should be O(log n) to replace a page.

So I'm confused why people would use a Clock page replacement policy and believe it is better than a LRU page replacement policy? Did the educational video I watch make an error in stating Clock is more efficient?

Or am I missing something?

# Answer
> 1 votes
If I understand correctly I think you are confusing the cache and the cache hit data structure. The structure isn't used to access the page, its used to store the hit count. For LRU, the OS needs to examine the hit count for every page in the cache memory to find the least recently used. When a page is hit, it is moved up in the list to prevent it from being evicted. I don't see how this would translate to a hash map.

The clock algorithm, only keeps track of a set of the most recently used pages (typically since the time since a new page was requested). The clock algorithm acts as an approximation of LRU without the maintenance of the linked list.

# Answer
> 1 votes
As you said, For `LRU`, if implemented using Heap data-structure:

```
Cost of a Read operation: O(log n)
Cost of a Write operation: O(log n)

```

For `Clock`:

```
Cost of a Read operation: O(1)
Cost of a Write operation: O(n)

```

A buffer management system uses a replacement policy to replace the pages in the buffer with the new page that is to be allocated some space in the buffer.

A buffer manager is more or like a cache mechanism.

As per your deduction, it is true that the cost of a write operation is cheaper in the Clock algorithm than compared to LRU.

But! Do you think there are going to be more writes than reads? If there are more number of writes, then the use of a buffer manager(or caching mechanism) comes into question. When there are more writes, one can directly fetch a data page from the disc and serve to the user rather than incurring the extra cost of replacing pages in the buffer.

So a caching mechanism, such as buffer manager, is preferable when there are more reads than writes. Since there are more reads, the Clock algorithm performs better than the LRU.

# Answer
> 0 votes
I'm unclear if you're asking about databases or operating systems here.

Databases have different tradeoffs, because "accessing" a page is a coarse-grained operation that typically includes locking it as part of a transaction, so you have the scope to do more work every time a page is "accessed". Operating systems don't have that luxury.

For example, imagine that you put all pages in a doubly-linked list. Every time you access a page, you move it to the head of the list. The least recently-used page is then always at the tail of the list. The time taken is $O(1)$ per access, with no heap needed.

This used to be practical for databases, but as the number of CPUs increased, the page list experienced high contention, and this limits concurrency. But there are modern variants that aren't as expensive and still require only $O(1)$ work per access.

---
Tags: algorithm-analysis
---


# Question
Title: Minimum Subsequence Sum Algorithm Verification
I have an algorithm which is meant to solve the following computational problem:

*Input: Sequence of positive integers*
*Output: A Sub-sequence of some desired length derived from original Sequence such that the sum of the sub-sequence's elements are the minimum sum possible*

The Algorithm I have to solve this problem is implemented as a method in Java:

```
public int[] runA(int k) {

        //k is desired length of sub-sequence

        /*Sequence S is the original sequence provided as input, it is available as a class variable
        for the class 'MinimumSubsequence' which this method 'runA' is apart of*/

        //A is Sequence S copy with pseudo-boolean values attached to each element in S
        int[][] A = new int[this.S.length][2];
        //B is size K array storing the k smallest elements found in S along with their indexes
        int[][] B = new int[k][2];

        //initialization
        for (int i = 0; i < this.S.length; i++) {
            A[i][0] = this.S[i];
            A[i][1] = False;
        }
        for (int i = 0; i < k; i++) {
            B[i][0] = this.S[i];
            B[i][1] = i;
        }

        //Execution
        //search for k smallest elements in sequence S
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < this.S.length; j++) {
                if (A[j][0] <= B[i][0] && A[j][1] == False) {
                    B[i][0] = A[j][0];
                    B[i][1] = j;
                }
                A[(B[i][1])][1] = True;
            }
        }

        //build subsequence
        int[][] C = new int[this.S.length][2];
        for (int i = 0; i < C.length; i++) {
            C[i][1] = False;
        }
        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (B[j][1] == i && (C[i][1] == False)) {
                    C[i][0] = B[j][0];
                    C[i][1] = True;
                }
            }
        }
        int[] D = new int[k];
        int j = 0;
        for (int i = 0; i < C.length; i++) {
            if (C[i][1] == True) {
                D[j] = C[i][0];
                j++;
            }
        }

        return D;
    }

```

The algorithm basically works by scanning the original sequence provided, each time scanning for the next smallest number. Once it has found the k smallest numbers in the sequence it builds and returns a sub-sequence made from those smallest elements in the original sequence

I believe that this algorithm does correctly solve the computational problem and that the running time of this algorithm is in O(N) (N being size of input sequence). I would just like some verification about the correctness and efficiency of this algorithm. I am also wondering if there exists are more efficient algorithm to solve this computational problem as I'm just not very satisfied with this one but can think of no other approach.

# Answer
The fact that your algorithm is in Java or the source itself are not really relevant. That said, your algorithm requires time $\Theta(n \cdot k)$, where $n$ is the length of the input sequence, and $k$ is the length of the desired subsequence. This can be as bad as $\Theta(n^2)$, when $k=\Theta(n)$.

You can improve the time complexity of your algorithm to $O(n)$ by first finding the $k$-th smallest element $x$ in $O(n)$ time, and then selecting all elements smaller than $x$, plus the necessary number of copies of $x$ (there might be multiple copies of $x$ in the input sequence and not necessarily all of them belong to the output).

An easy selection algorithm is quickselect with randomized pivot selection. This algorithm has complexity $O(n)$ with high probability. If you want a $O(n)$ worst-case complexity you'll have to be a bit more careful with the pivot selection. You can start by reading the Wikipedia pages on selection, quickselect, and median of medians.

If you want to be lazy and you don't care about losing a $O(\log n)$-factor over the optimal time complexity, then you can simply sort the input sequence in time $O(n \log n)$ (e.g., using Mergesort) and then return the first $k$ elements.

Another solution that is easy to implement if you have access to priority queues and has complexity $O(n \log k)$ is iterating over the input sequence while maintaining a max-Heap $H$ of the smallest $k$ elements encountered so far. Initially $H$ is empty and, for each element $x$ of the input you: (i) push $x$ into $H$, (ii) if $H$ contains $k+1$ elements, you extract one element from $H$. After examining all elements, $H$ contains exactly the $k$ smallest elements of the whole input sequence.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, runtime-analysis
---


title: Zero-Sum Games and Halting Problem

text:
# Question
Title: Zero-Sum Games and Halting Problem
Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do."

Suppose we have 2 neural networks, approximating f and g (allowing infinite size and depth limits). Is it wrong to assume that these two NNs can participate in a zero-sum game against each other, and that the Nash equilibrium (if it exists) of these 2 NNs contains the solution to the halting problem?

# Answer
> 3 votes
Turing proved that the halting problem is undecidable.

No algorithm that you can come up with will solve the halting problem.

# Answer
> 1 votes
It is not quite clear to me what you have in mind with infinite size + depth limits for your neural net, but once you have sorted that out you should end up with the following game:

Player I plays a program p, and Player II plays a program q.

Player 1 wins iff p halts on input q, and answer Yes if q halts on input q, and No otherwise. Player 2 wins iff Player 1 doesnt.

This game has no Nash equilibrium. Player I always has a winning best response amongst the programs "just output Yes" and "just output No". The diagonalization construction from the proof that the Halting problem is undecidable tells us how Player II could compute a winning best response if she knew Player I's choice p.

---
Tags: neural-networks, halting-problem, game-theory
---


# Question
Title: Theoretical question about Zobrist hashing and chances of collision with slight modification
I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any transpositions, but I still want to store the position in the hash table. So I'm trying to make the position's hash unique by XOR'ing it with the memory address of the object that holds the position structure. Here is some pseudocode:

```
hash = zobristHash(position);
if (makeItUnique)
    hash := h XOR [memory address of position object]

```

Is there any reason to suppose that what I'm doing will increase the likelihood of hash collisions?

# Answer
> 1 votes
it may be better to store them in separate hash table. or, if you need them in the same table:

```
tmp = position
if (makeItUnique)
    tmp := [memory address of position object]
hash = zobristHash(tmp);

```

It's better than your current code since it will avoid collisions of objects with the same position AND similar memory address (the definition of similarity here depends on how you use the hash value to address the hash table)

# Answer
> 0 votes
I don't see any reason to expect this to increase the chance of collisions. If the data in the object and the address of the object are independent, then XOR does not cause any harm.

It might be even simpler and faster to use a hash of the address, without hashing the object contents, when you want it to be unique.

---
Tags: hash, hash-tables
---