NP problems with exponentially complex average time solution? Assuming $P \ne NP$, is there a problem such that is NP such that:

There is always a solution

Alternatively, there is asymptotically almost surely a solution

On average, it takes exponential time to solve
The probability distribution can be any distribution which can be sampled from in polynomial time.

Also, what would such a complexity class be called?

We don't know.  It's possible that $P \ne NP$ but still all problems can be solved in subexponential time, as Yuval states.  The Exponential Time Hypothesis is a conjecture that a certain problem requires exponential time to solve, but it's a conjecture -- there's debate among researchers about whether we should expect it to hold or not.

Assuming the ETH, you can find problems that meet your requirements, at least for worst-case hardness: there is asymptotically almost surely a solution, and any deterministic algorithm must have worst-case running time that's exponential in the length of the input.  In particular, ETH implies that every problem in the class SNP takes exponential time to solve.  For instance, 3SAT would qualify.

It sounds like you really want average-case hardness.  There are some natural candidate problems: 3SAT with an appropriate clause density would be one reasonable one.

You could also use cryptographic hardness assumptions from the crypto community, e.g., inverting $f(k) = AES_k(0)$ probably takes exponential time yet is known to have a solution, as far as we can tell given our current state of knowledge.  This gives you a problem with a concrete parameter size, but with standard techniques you can build something asymptotic if you prefer an asymptotic family of problems.


Big Oh Time Complexity Involving 'for i in range(n)' Given the code below and the comment analysis:

n = len(L)  # O(1)
for i in range(n):  # O(n) - I read online that range(n) will take constant time
                      but the 'for i in range(n)' part would make this O(n)?
    if L[i] > 0 :  # O(1)
       for j in range(n):  # O(n)
           answer = answer + L[i]  # O(1) - since indexing takes constant time
    else :  # O(1)
        for j in range(n):  # O(n)
            answer = answer - L[i]   # O(1)

My Overall Analysis:

$O(1)$ for the first variable assignment
first if statement takes overall $O(n)$
else statement also takes overall $O(n)$
=> Overall if/else statements take $O(n)$ as well
for loop iterates n times => $O(n * n)$ => $O(n^2)$

=> Overall time complexity $O(n^2)$

Thanks in advance for the suggestions!

EDIT: I am wondering if the

for i in range(n)

portion of the code takes O(n) or O(1)? I read that range(n) would take O(1) but since its a for loop it would take O(n)?

So you have the right logic, if you have a loop of $O(n)$ iterations, the complexity of the entire loop will be $O(n*\text{complexity of loop operations})$. In this case, you again are correct that your loop's complexity is $O(n)$ for each iteration.

Your last bullet point shows that you understand this as well, as the total loop complexity is then $O(n^2)$. However, this trivially results in an overall time complexity of $O(n^2)$, not $O(n)$ as you concluded.

I imagine what you were really asking about is the complexity of range(n). While it is true that the initial call to range is $O(1)$, that is because it produces a generator which takes $O(1)$ to return the next successive value i.e. it doesn't produce the entire range right away, but instead on demand. However, keep in mind that the generator will be advanced $O(n)$ times (once for every iteration of the loop).


Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $(i,j,k)$, then every lattice point $(i,j,k)$ has a field vector $(\phi_1, \phi_2 , \phi_3)$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors  $(\phi_1, \phi_2 , \phi_3)$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $\phi$-space, with $\phi$-space being the 3D space given by the $(\phi_1,\phi_2,\phi_3)$ coordinates.

I am now interested if the volume spanned by these 8 points in $\phi$-space does the following things:

If it contains the origin, $(0 ,0 ,0 )$
If a Ray traveling from the origin in $(-1,0,0)$-direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $(-1,0,0)$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $10^6 ... 10^9$ cells to evaluate per sweep across my lattice.

I'd be interested in any other approaches as well, though.

Update:
So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?

You don't actually need the convex hull. This is a simple linear programming instance: find $a_i$ such that $$0 \le a_i \\
\sum a_i = 1 \\
\sum a_i \phi_{i, 1} \le 0 \\
\sum a_i \phi_{i, 2} = 0 \\
\sum a_i \phi_{i, 3} = 0$$ maximising $\sum a_i \phi_{i, 1}$. There are optimised LP solvers out there which you can use.


Find subsequence of maximal length simultaneously satisfying two ordering constraints We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to arrange these fruits in such a way that the sorted list contains prices in ascending order and vitamin contents in descending order.

Example 1: $N = 4$ and $F = \{(2, 8), (5, 11), (7, 9), (10, 2)\}$.

If we arrange the list such that all price are in ascending order and vitamin contents in descending order, then the valid lists are the following:

$[(2, 8)]$
$[(5, 11)]$
$[(7, 9)]$
$[(10, 2)]$
$[(2, 8), (10, 2)]$
$[(5, 11), (7, 9)]$
$[(5, 11), (10, 2)]$
$[(7, 9), (10, 2)]$
$[(5, 11), (7, 9), (10, 2)]$

From the above lists, I want to choose the list of maximal size. If more than one list has maximal size, we should choose the list of maximal size whose sum of prices is least. The list which should be chosen in the above example is $\{(5, 11), (7, 9), (10, 2)\}$.

Example 2: $N = 10$ and $$F = \{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\(90,18), (43,90),(13,100),(78,65)\}$$

The answer to this example instance is $[(13,100),(43,90),(78,65),(87,11),(99,10)]$.

Until now, this is what I have been doing:

Sort the original list in ascending order of price;
Find all subsequences of the sorted list;
Check whether the subsequence is valid, and compare all valid subsequences.

However, this takes exponential time; how can I solve this problem more efficiently?

A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers).
First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending).
Now, define $M[f, v]$ to be the maximal number of fruits in a sublist, containing only the last $f$ fruits (of the sorted list), having a vitamin content of at most $v$. $M[0, *] = 0$ and
$$M[f, v] = \begin{cases}
 \mathrm{max} \{M[f-1, v], 1 + M[f-1, V_f]\} & \text{if \(V_f <= v\)} \\
 M[f-1, v] & \text{otherwise} \\
\end{cases}$$
Using dynamic programming gives you a solution that runs in $O(\text{number of fruit} \times \text{possible vitamin values})$.


Complexity of Independent Set on Triangle-Free Planar Cubic Graphs I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?

Any ideas or referrences are appreciated, thank you in advance!

Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.


Removing left recursion with terminals only I have a grammar:
$G → id > id$
   $| id < id$
   $| G and id$
Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?

You'll need to introduce a new non-terminal to factor this, like:
$\begin{align*}
   G &\to id A \\
   A &\to < id \mid > id
\end{align*}$
Then you'll need to get rid of the left recursion.


What is the difference (if any) between transition systems and finite automata? is there any difference between transition systems and finite automata? Is it that transition systems consist of both NFA (nondeterministic finite automata)
and DFA (deterministic finite automata)?

Yes, did you try wikipedia?

To quote the second paragraph [in transition systems]:

  The set of states is not necessarily finite, or even countable.
  The set of transitions is not necessarily finite, or even countable.
  No "start" state or "final" states are given.


Using a combination of spatial and non-spatial inputs for convolutional neural networks I'm working on training a game AI using deep reinforcement learning to achieve specific examples based on pixel input and some additional state information.

Naturally, I'm using a convolutional neural network to deal with the pixel information, which has been working well so far. However, I still have additional information available, such as numeric values associated with current health and ammo.

I know it must be possible to create a network architecture to take advantage of both the spatial information provided by the screen buffer as well as non-spatial information such as the game states I mentioned earlier. Is there any way to create a neural net architecture that can handle both spatial and non-spatial state?

Yes.  One way is to start with several convolutional layers, and then end with one or two fully connected layers.  You can add the other features as inputs to the first of those fully connected layers.  This is basically serial composition of convolutional layers then fully connected layers.

There are other options for network architectures, but that'd be a reasonable one to try first.  The choice of architecture is an art and depends partly on how you think one might learn from the features, and how the value of one feature might affect the kinds of things you'd like for in other features.  The architecture I suggest above would be good if we pretty much want to look for the same kinds of information about the pixel input, regardless of the value of health, ammo, etc.  If you think the health, ammo, etc. would dramatically influence what kinds of information we'd want the network to extract from the pixel input, one might consider other network architectures.


Multiple matching in Maximum Flow problem? I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such:

Assume there are x restaurants, each with a capacity q, and y people, each of which can only eat from one restaurant. The x restaurants can only serve the people within radius r of its location. Try and find the maximum number of people that can be served by a restaurant and what restaurant each one must eat from.

My approach was to split it up into something similar to the bipartite matching problem. Have the x restaurants on one side and y people on the other. Then, I'd have a start node which connects to every restaurant using a directed edge of capacity q. Then, I'd connect all the y people with a directed edge of capacity 1 to a sink node, t. Lastly, I'd connect every restaurants to all the people within radius r using a directed edge of capacity 1.

Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could (for example, let's say we have two restaurants each with capacity 2, 4 people, and the first restaurant connects to the first three people and the second connects to the last two; then, if the path from the first restaurant to the third is augmented in the algorithm, we can only serve 3 people instead of an optimum of 4). My workaround to this is maybe augment an s-t path with the least amount of incoming edges to the person (so a situation like the above can be avoided), but this clearly slows down the efficiency significantly of the algorithm, as well as making it much more difficult to provide an argument saying it's optimal.

Is there any literature concerning problems like these, or any suggestions on how I can improve my approach? Thanks!

Your approach works.  The situation you're worried about can't happen.  It appears you haven't quite fully grasped how the Ford-Fulkerson algorithms yet, so focus on getting more familiar with it.  It always finds the max-flow, and the max-flow always solves your problem.

The key misunderstanding is where you wrote:

  Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could

This is false.  That actually can't happen.  Work through the proof of correctness for the Ford-Fulkerson algorithm to understand why not: if there's a larger flow, then there will always be an augmenting path you can find to increase the size of the flow.

This was presumably an exercise to help you get acquainted with network flow algorithms, and it worked: it uncovered a gap in your understanding.  This is great -- it means you have something yet to learn about how the algorithms work.  What a great opportunity!  Now you get to spend some time communing with a textbook learning this lovely subject.  Have fun!


Is binary tree just a two-dimension-doubly-linked-list? We all know the structure of a binary tree:

struct binary_tree {
  binary_tree *parent;
  int          data;
  binary_tree *left;
  binary_tree *right;
};

So a doubly linked list has the following structure:

struct linked_list {
  linked_list *prev;
  int          data;
  linked_list *next;
};

But a binary tree can also be manipulated like this:

struct my_linked_list {
  my_linked_list *prev;
  int             data;
  my_linked_list *next0;

  my_linked_list *next1;
} binary_tree;

By that, I have "proven" that binary tree shares a similarity to doubly linked list. (with the addition of another next element)

So my question is here: Is binary tree really a vertically-descending graph, or just an extension to the linked list, that can be drawn horizontally?

I know this is a kind of stupid and meaningless question but it was confusing me for years and years. I am just an apprentice to the computer science...

"[A] binary tree shares a similarity to doubly linked list"

Why, yes, it does, but the doubly linked list format you have made is really just a way to represent a connected graph, with the one limitation that a node can be connected to at most 3 other nodes. A lot of structures could fit into that format, for instance a binary tree or many cyclic structures in addition to lists.

You have made one limitation to a general graph, of which binary trees are a subset. The reason we care about more restricted versions of graphs is that it allows for many useful optimizations. Your two dimensional doubly linked list has many redundant properties regarding use as a binary tree, for instance it allows for cyclic structures, which a binary tree can not be, and it includes information about the parent node, which is also unnecessary as such trees are used for descending searches.


What Do Logical Operators In a Grammar Mean? Is there a way to figure out what the following CFG accepts?

$\qquad\begin{align}
  S &\to S \vee T \mid T \\
  T &\to T \wedge F \mid F \\
  F &\to p \mid\; \thicksim p
\end{align}$

I'm confused by the boolean algebra symbols. I know the first is S or T, the second is T and F and the third is not p but I'm not sure how they affect the grammar itself.

A grammar generates a language, it doesn't accept it. Automata accept languages.

The whole point of gramars is that they are easily able to generate quite complex languages. Even regular languages (accepted by finite automata or denoted by regular expressions) can be very hard to describe in simple terms.

In this case, the grammar generates (a subset of) logical formulas, with connectives and ($\wedge$), or ($\vee$), and not ($\thicksim$).


Is Morse code without spaces uniquely decipherable? Are all Morse code strings uniquely decipherable?  Without the spaces,

......-...-..---.-----.-..-..-..

could be Hello World but perhaps the first letter is a 5 -- in fact it looks very unlikely an arbitrary sequence of dots and dashes should have a unique translation.

One might possibly use the Kraft inequality but that only applies to prefix codes.

Morse code with spaces is prefix code in which messages can always be uniquely decoded.  Once we remove the spaces this is no longer true.

In the case I am right, and all Morse code message can't be uniquely decoded, is there a way to list all the possible messages?  Here are some related exercise I found on codegolf.SE

https://codegolf.stackexchange.com/questions/36735/morse-decode-golf
https://codegolf.stackexchange.com/questions/131/morse-code-translator


Show that LOOP is reducible to Complement of Halting problem LOOP = {<M,w1,w2,w3>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {<M,w> : M is a Turing machine that doesn't halt on w}
Show that LOOP is polynomial time Turing reducible to HPC
I am not sure how to begin solving this kind of problem.
Also the question I am trying to solve brings up the definition of A is polynomial reducible
to B if there is a B-oracle poly time Turing M such that M(x) accepts x iff x is in A.
Any hints or pointers on this ?
My thoughts :
What I understand by reducibility here is that If I have a Turing machine for HPC
Then I can use this turing machine to determine if <M,w1,w2,w3> is in LOOP
And same the other way If I have a turing machine for LOOP then I can use it
as a determiner for HPC. Is this a correct way to think about it?
This way it becomes simple and probably easier to prove. But not sure if it
is same as the question that is being asked

The question is given you have an oracle machine/black box for HPC can you decide if <M,w1,w2,w3> is in LOOP.
See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction_(recursion_theory)#Turing_reducibility
The proof is very straightforward as you already know.


Proving that grammar generates language with multi variable inequalities I am struggling with trying to come up with the inductive proofs to prove that the following grammar is equal to $ L = \{0^m1^n | m \leq 2n, n \leq 2m \}$
The grammar is
$ S → A \:|\: B $
$ A → 00A1 \:|\: C $
$ B → 0B11 \:|\: C $
$ C → 0C1 \:|\: ε $
How exactly do the proofs for proving $ L \subseteq L(G) $ differ from $L(G) \subseteq L$.
In specific, how do the inequalities affect the format of the inductive proof?

The grammar produces words that we can separate into two cases:

$S$ gets replaced by $A$, then the second rule is used $k\geq0$ times with the branch that keeps the $A$ present. Then it is used with the branch that replaces $A$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{2k+r}1^{k+r}$.
$S$ gets replaced by $B$, then the third rule is used $k\geq0$ times with the branch that keeps the $B$ present. Then it is used with the branch that replaces $B$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{k+r}1^{2k+r}$.

In the first case $m=2k+r,n=k+r$ satisfy $m=2k+r\leq 2(k+r)=2n$ and $n=k+r\leq 2(2k+r)=2m$. In the second case $m=k+r,n=2k+r$ satisfy $m=k+r\leq 2(2k+r)=n$ and $n=2k+r\leq 2(k+r)=2m$. Therefore, all words produced by the grammar belong to $L$.

Now, suppose that you take a word in $L$. This would be a word of the form $0^m1^n$ with $m\leq 2n$ and $n\leq 2m$. As before, let's separate the analysis in two cases:

Assume that $m\geq n$. Define $r=2n-m$. Observe that since $m\leq 2n$ we have $r\geq0$ and that $r\leq n$, since $m\geq n$. Define $k=n-r=m-n$ and note that $m-r=2(m-n)=2k$. Therefore, $0^m1^n=0^{2k+r}1^{k+r}$. Now you can see how to produce this word using the grammar by following the flow in case 1 above.
Assume that $n<m$. Define $r=2m-n$. Observe that $r\geq$, since $n\leq 2m$ and that $n-r=n-m\geq0$. Define $k=n-m$. Then $m=k+r$ and $n=2k+r$. Therefore, $0^m1^n=0^{k+r}1^{2k+r}$. Now you can see that you can produce this word using the grammar as in case $2$ above.


How is the literal meaning of "rendezvous" related to its usage in distributed computing? I am trying to figure out the difference between RPC and Rendezvous.  Is it correct that they differ only on their implementation on server side: RPC will involve creating a new process/thread to handle a request, and Rendezvous will pick an existing process/thread to handle a request?

The word "rendezvous" simply means a bunch of people meeting together. How is it related to its usage in computing?

Thanks.

In this context, the rendezvous would mean "a bunch of threads meeting together" instead of people. Rendezvous is a method of synchronisation in which at least two threads "meet". In other words, each thread that reaches the rendezvous point waits until all other threads have reached the same point before proceeding.

In the context of Distributed Algorithms the Rendezvous Problem is the task of devising an algorithm that will ensure that at least two entities (e.g., mobile agents) starting from different positions will meet after a finite amount of time in a specific environment (e.g., in a graph).


Lamport's Byzantine Generals Algorithm I've stumbled at the first OralMessage algorithm in Lamport, et al's paper.

I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping me.

Lamport claims the algorithm can handle (n-1)/3 traitors, and works when the commander is a traitor.

My restatement of the algorithm:

The commander sends a value to each of the lieutenants.(round 0)
Each lieutenant:
forwards each message he receives to the other lieutenants:
don't forward messages that already have your name          (eg you are b and receive 'cb1')
don't forward messages if they already have (N - 1)/3 names. (eg N=10 and you receive 'gcd0')
add your name to front of message before forwarding         (eg you are b and receive 'c0', send 'bc0')
after all messages have been sent, each lieutenant:
examines the received messages and makes their decision.
if its a tie, then decide 0.

I'm not sure how to do 3, the paper says the algorithm "assumes a sequence of [majority] functions" (nested?)
In the example, I'm assuming to take the majority in each vector of round 2 (ie left to right), and then take the majority of these.

EXAMPLE

Commander is a traitor, N=7, M=(7-1)/3=2, so 6 lieutenants one of whom is a traitor. I have assigned the lieutenants letters b-g.

Here are the messages received at each node in rounds 1 & 2, assuming a node can send to itself. (the messages in brackets are redundant from B's point of view. I don't know if this is important.):

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >
<(beX),ceX  ,deX  ,     ,feX  ,geX  >
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >

Note:
'dc0' is sent to everyone by 'd' (because 'd' was the last to prepend their name)
'X' indicates an unreliable message. 'e' is a traitor and always sends unreliable messages

BUT 'step 3' gives 1,0,0,X,1,1 which is no better than round 1.
AND the majority of these is 1 if X is 1, and 0 if X is 0. So the traitor can confound us.

What am I doing wrong?

----I'm not sure if this should be my answer. Many thanks to hengxin. It does explain my confusion, and may be helpful to others seeing the question----

I failed to realise that there are 2 types of unreliable messages,
- some are different for each lieutenant, (eg 'eX' in round 1)
- others are the same for all lieutenants (I will denote these as 'S')

the amended example is,

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>   1
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >   0
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >   0
<(beS),ceS  ,deS  ,     ,feS  ,geS  >   S
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >   1
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >   1

now the result from 'round 2' is different to 'round 1', and allows agreement.
however, we could have acheived the same result with:

<(b1) ,c0   ,d0   ,eX   >

<     ,(cb1),(db1),(ebX)>   1
<(bc0),     ,dc0  ,ecX  >   0
<(bd0),cd0  ,     ,edX  >   0
<(beS),ceS  ,deS  ,     >   S

Remember we have a traitor commander, but it seems more than coincidence that there is 1 traitor lieutenant out of 4 lieutenants (3t+1)?


Do the minimum spanning trees of a graph have the same number of edges with a given weight? I'm asking about the answer here:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

I didn't understand the best answer here

  Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T_1 \mathop{\Delta} T_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T_1$ and assume $T_1$ has more edges of weight $\min W$ than $T_2$.

First of all, what does minimum disagreeing weight mean?

  assume $T_1$ has more edges of weight $\min W$ than $T_2$.

Does the above line mean, $T_1$ has multiple edges with weight $\min W$

  Now consider all edges in $T_2$ that are also in the cut $C_{T_1}(e)$ that is induced by $e$ in $T_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

This paragraph seems to be a problem for me. So, we remove edges with weight $e$ which is also $\min W$ and replace it with $e'$. So we do that for all edge weight $e$ present in $T_1$

  Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

I didn't understand this line at all. What is supposed to be $g(e)$?

  Now we can always choose $e' \in C_{T_1}(e) \cap T_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

  $\qquad \displaystyle T_3 = \begin{cases}
  (T_1 \setminus \{e\}) \cup \{e'\}  &, w(e') \lt w(e) \\[.5em]
  (T_2 \setminus \{e'\}) \cup \{e\}  &, w(e') \gt w(e)
\end{cases}$

  which has smaller weight than $T_1$ and $T_2$; this contradicts the choice of $T_1,T_2$ as minimal spanning trees. Therefore, $W_1 = W_2$.

Why is $w(e') \lt w(e)$ here? isnt $e'$ same as $e$ ? and why does  $T_1,T_2$ contradict as minimal spanning trees?

The question and this post refers to this answer at its version 2.

  First of all, what does minimum disagreeing weight mean?

The better word should have been "distinguishing". If the set of edges of some fixed weight in $T_1$ is different from that of $T_2$, then $T_1$ and $T_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal trees.

  What is supposed to be $g(e)$?

That is a typo. It should have been $w(e)$.

  Why is $w(e') \lt w(e)$ here? isn't $e'$ same as $e$ ? and why does  $T_1,T_2$ contradict as minimal spanning trees?

Let us use a new dummy variable instead of $e'$ for the last part of that answer.

Let $f \in C_{T_1}(e) \cap T_2$. Had $f$ weighed the same as $e$, we should have update $T_1$ by using $f$ instead of $e$. Since we have done all such updates, $f$ must weigh differently from $e$. That is the conclusion in the previous paragraph, "all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $w(e)$".

There are two disjoint cases.

the case when $w(f)\lt w(e)$. Consider the spanning tree $(T_1 \setminus \{e\}) \cup \{f\}$, which is lighter than $T_1$.
the case when $w(f)\gt w(e)$. Consider the spanning tree $(T_2 \setminus \{f\}) \cup \{e\}$, which is lighter than $T_2$.

In either case, we have found a spanning tree that is lighter than a minimum spanning tree, which is a contradiction.


Finding all solutions to subset sum for integers with bounded weights Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer.  I am interested in determining all subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$.  I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?

The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A_{k,w}$ contains enough information to enumerate all subsets of $\{w_1,\ldots,w_k\}$ summing to $w$. When $k = 0$, this is trivial. Given $A_{k-1,\cdot}$, $A_{k,w}$ points at the two cells $A_{k-1,w},A_{k-1,w-w_k}$ (if they exist). The second pointer is also annotated with $w_k$. If you look at $A_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A_{0,0}$. This can be done using a simple recursive procedure.


How would one prove the pigeonhole principle with a SAT solver? Suppose I wanted to find a proof of the pigeonhole principle or show that no  proof shorter than $L$ exists. I understand that proof-checking is in NP, so I could write a CNF formula that is satisfiable iff. such a proof exists. What I want to know is, how exactly would one do that? I understand I would assume a set of axioms about sets or something and also the axioms of first-order predicate calculus, and probably also modus ponens and stuff... but how exactly does one do something like this? Can anyone give a construction of such a CNF formula? References to papers or general explanations would be appreciated.

SAT solvers work in the propositional calculus, and usually accept as input a formula in conjunctive normal form. There are several different propositional variants of the pigeonhole principle; they are all contradictions, and the actual pigeonhole principle is their negation. One of them, which states that there is a one-to-one mapping from $\{1,\ldots,n\}$ to $\{1,\ldots,n-1\}$, is described in page 2 of this book extract (apparently Jukna's Extremal Combinatorics), where you can also find an exponential lower bound for refuting the pigeonhole principle in the resolution proof system.

(Reiterating, to prove that there is no one-to-one mapping from $\{1,\ldots,n\}$ to $\{1,\ldots,n-1\}$, we instead refute the formula stating that such a mapping does exist.)

SAT solvers are (almost) all based on the DPLL procedure (with some hacks such as clause learning), and so when they refute a statement, their transcript can be converted to a resolution refutation. Therefore the lower bound mentioned above shows that SAT solvers will have a hard time refuting the pigeonhole principle.


Constructing a minimum spanning tree from an all-shortest path graph? Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a connected network $T$ of $n$ nodes and $n-1$ edges - i.e. the shortest path distance between two nodes in $T$.

About the network $T$:

There are exactly $n$ nodes and $n-1$ edges.
The network is one connected component, thus it is a tree.
All edges have positive length.

My problem is that if I compute a minimum spanning tree $T'$ of $G(D)$ using, for instance, Kruskal's algorithm will the resulting tree $T'= T$?

I tried to argue that they are indeed equal, because if we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

I am not sure if this argument holds. How can I argue that $T' = T$?

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been  determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, for all $0\le i\le k-1$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by a path in $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by a path in $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.


Reduction from Steiner tree to minimum set cover I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover
(given a set of items $I$, and a set $S$ of subsets of $I$ and an integer $k$, is there a subset $S'$ of $S$ such that $|S'|\leq k$ and $union(S')=I$)
 to weighted Steiner tree
(given a graph $G=(V, E)$, a weight function $w$, a subset $V'$ of $V$ and integer $k>0$, is there a subtree $G'$ of $G$ such that the sum of the weight of the edges in $G'\leq k$ and $V'$ is contained in $G'$?)
, but have gotten a bit stuck. I believe I am on the right path.

Here's what I have so far. Given an instance of minimum set cover, define a root node r, For every subset in $S_i\in S$, define a node $S_i$ and connect it by an edge to $r$ with weight one. For every element in $S_i$, define a node and connect them to $S_i$ via an edge of weight 0. This creates a tree. I believe something like this should work, but I cannot figure out how to define $G'$ for the constructed instance of STG such that there is an answer yes if there is a minimum set cover.

Any help would be greatly appreciated, thanks

It is your definition of Steiner tree problem that causes the difficulty here.

Your definition does not include the set of terminals $S\subseteq V(G)$. Then, a Steiner tree is a subtree $G'$ of the graph $G$ that spans $S$.

Keep this definition in mind, you can now move on to reduce $\mathrm{EXACT}$-$\mathrm{COVER}$-$\mathrm{BY}$-$3$-$\mathrm{SET}$ to your problem. The set of terminals would be the set of items to be covered, plus the root $r$. The construction is exactly your construction including your weight function.

But, the required weight $k$ is now $|U|/3$ where $U$ is the universe of items to be covered.

Clearly, a Steiner tree that spans $r$ and the whole universe should be a tree that can be rooted at $r$ with $k$ children as the set cover solution. Note that a Steiner tree is by no mean a rooted one but here we see that being seen as rooted at $r$ does help.


If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5? I learned that recursive Fibonacci is $O(2^N)$.

However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near abouts? It's like less then half!

$COUNT = 0

def fibonacci( n )
   $COUNT +=1
   return  n  if ( 0..1 ).include? n   # Base Case returns 0 or 1
   fibonacci( n - 1 ) + fibonacci( n - 2 ) # Recursive case
end

You ask,

  I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?

There are many things wrong in the implied conclusion.

$O(\_)$ only gives you an upper bound. The true behaviour may be of much smaller growth.
Asymptotics (like $O(\_))$ only give you only something in the limit, that is you can only expect the bound to hold for large $n$.
Since you use $O$ as though it was $\Omega$, note that a (lower) bound on runtime does not necessarily translate into a (lower) bound on recursive calls, each of which may take $\omega(1)$ time.

Similarly, a tight upper runtime bound (which you don't have) may not be a tight upper bound on the number of recursive calls for the same reasons.

You can analyse exactly how many recursive calls you need. Just solve the recurrence

$\qquad\displaystyle
\begin{align*}
  f(0) &= 1,\\
  f(1) &= 1,\\
  f(n) &= f(n-1) + f(n-2) + 1, \quad n \geq 3,
\end{align*}$

which adds up $1$ for every recursive call your program makes. See here for more detail on how you get to such recurrences.

See here how to do that, or use computer algebra. The result is

$\qquad f(n) = 2F_{n+1} - 1$;

insert $n=5$ and you will get $f(n) = 15$.
It's not that surprising that the Fibonacci numbers $F_n$ should show up. Inserting their known closed form, we get

$\qquad\displaystyle f(n) = \frac{2}{\sqrt{5}} \cdot \Bigl( \varphi^{n+1} - (1-\varphi)^{n+1} \Bigr) - 1$

with $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.62$ the golden ratio.
This closed form of $f(n)$ implies

$\qquad\displaystyle f(n) \sim \frac{2}{\sqrt{5}} \cdot \varphi^{n+1} \approx 1.45 \cdot 1.62^n$

since $0< 1 - \varphi < 1 < \varphi$.
We see that the $O(2^n)$-bound is rather loose -- it has exponential absolute and relative error.


How to Apply Binary Transformations? One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000.
To apply such transformation the following method is applied:

1) Find 2's complement of the index.
2) AND the result of 1 with index.
3) Subtract the result from 2 with index.

If the following method is applied to 1010 then we get 1000 as the answer. Now I want to understand how to create such formulas?  In Algebra we solve such type of problems by solving linear equations. How do we do it with Binary numbers to achieve such answers?

This is a one-off trick which is not part of a complete methodology. To see why the trick works, suppose that the index has the form $x10^m$. To calculate its two's complement, we first complement it to $\bar{x}01^m$, then add 1 to get $\bar{x}10^m$. ANDing the index and its two's complement, we get $0^{|x|}10^m$. Subtracting this from the index, we get $x0^{m+1}$, as needed.


How to handle dfa with countless states? I have a question regarding DFA:

Design a DFA M with alphabet $\sum = \ {\{0,1,2,R}\}$ where the states remember actual sums of the number, except that the sum is reset to 0 whenever the symbol $R$ appears. Show diagrammatically how this DFA can be constructed. What is the problem with this DFA?

One thing I do understand is that in order to remember the actual sums I would have to have the sums as states. But sums can be any number from 0 to  infinity. So would the states increase exponentially while reading the input string? How can I tackle this problem?

You seem to have missed the last sentence of the question:

  What is the problem with this DFA?

The problem with this DFA is that it isn't finite (so it's not really a DFA).

A DFA is a static object — the only way it interacts with the environment is by switching states.


Computational equivalences between a calculus and an automaton model This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages.

http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars

But I miss another relation: Lambda calculus (that can be described syntactically as a certain context free grammar) has the same computational strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore the correspondence between abstract programming languages and automata further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)

As I said, I am not sure how to answer your question.

However, given the current rephrasing of it, it finally rung a memory
bell. I think that, starting sometime in the 1970's, people have been
studying what they called program schemes.

A set of slides (in French) I found on the web seems to give a
historical perspective on the subject.

Slide 14 is about Iterative program schemes, corresponding to Regular
sets. They correspond to computational structures of the form X=f(X,Y) and Y=a, which are only a functional version of iteration loops.

Slide 15 is about Recursive program schemes, corresponding to
Algebraic (also known as Context-Free) languages. They correspond to more complex recursive computation structure, using a stack memory as in early recursive programming langages.

I am not certain that is the kind of correspondance you are looking
for, as it correspond (as much as I remember) to the computing power of uninterpreted programs, i.e. the structural aspects of the computationq. But it may be worth reading.

There are many more references, including fairly recent ones, if you
serach the web with: "program schemes".


Heuristic for Tournament Scheduling I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time.
The setup is as follows:

-Up to 42 groups of 2 persons each.
-3 groups will be paired to be one team
-a game is played between 2 teams (6 groups) and takes 20 minutes
-3 games will be played at the same time, there will be 12 rounds of 3 games
-Every group has the same amount of games
-after every game, the teams change
-What I want to optimize:
 minimize the amount of times a group gets put in a team with another group
 they have already played with (if they played against them it is ok)
 Bonus: Minimize the games a group has to wait until their next game
 (Since only 3 games can be played at once (so 6x3 = 18 groups), there are a lot of
 groups who have to wait for the next round of games.)

I want the program to give me the pairings of the groups and a schedule, if possible.
I am giving the exact numbers, because if it can't be done in polynomial time, but the instance is small enough so exponential time does not matter too much, it is fine with me.
The solution does not have to be optimal, but should be close.

What is a good algorithm or heuristic for my problem?

I would suggest that you use an integer linear programming (ILP) solver or a SAT solver.  This will probably be easier to formulate as ILP, so start there.

Let's check whether it is possible to ensure that no group ever gets teamed up with another group more than once.  (We'll ignore the bonus condition.)  Define a zero-or-one integer variable $x_{g,t,r}$, with the intent that $x_{g,t,r} = 1$ if group $g$ plays in team $t$ during round $r$, and $x_{g,t,r} = 0$ otherwise.  Now we can write some linear inequalities to capture the constraints on a valid solution:

$0 \le x_{g,t,r} \le 1$ ensures that each $x_{g,t,r}$ is zero or one.
$\sum_g x_{g,t,r} = 3$ ensures that exactly 3 groups are assigned to each team in each round.
$\sum_t x_{g,t,r} \le 1$ ensures that no group is assigned to more than one team in any given round.
Arbitrarily choose 36 groups to play 5 games; for those groups $g$, the linear equality $\sum_{t,r} x_{g,t,r} = 5$ ensures they will play 5 times.  The other 6 groups will play 6 games; for them, enforce the linear inequality $\sum_{t,r} x_{g,t,r} = 6$.
For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} \le 3$ for all $t,r,t',r'$; this ensures that $g,g'$ never play together on the same team more than once.

Feed this system of inequalities to an ILP solver.  If it has a feasible solution, then you have found a valid schedule for your tournament.

If it has no feasible solution, next check whether there's a feasible tournament where no group ever gets teamed up with any other group more than twice.  Do this by replacing the last set of inequalities above with the following:

For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} + x_{g,t'',r''} + x_{g',t'',r''} \le 5$ for all $t,r,t',r',t'',r''$; this ensures that $g,g'$ never play together on the same team more than twice.

If this doesn't have a feasible solution, check whether there's a way to do it where no group ever gets teamed up with any other group more than three times.  Do a linear search until you find the best solution.

Once you've found the best solution, now you can try to handle the bonus condition.  Let's say you want to see whether there's a way to do it where no group gets teamed up with another group more than once, and (here's the bonus condition:) no group has to wait more than three games.  The bonus condition is easy to enforce: for each $r$, simply add the linear inequality $\sum_t x_{g,t,r} + \sum_{t'} x_{g,t',r+1} + \sum_{t''} x_{g,t'',r+2} \ge 1$.  Now test whether that's feasible.  Of course, you can vary the waiting time (it doesn't have to be three games) to find the smallest waiting time possible.

I'd expect this might find a solution to your problem.  Modern ILP solvers are surprisingly good at solving many ILP instances, if there is sufficient structure -- and in this case I suspect there might be enough structure that off-the-shelf ILP solvers might work well.

There are variations possible to speed up the ILP solver, but I suspect that this straightforward formulation might just work with no tweaks or optimizations needed.  Give it a try!  It shouldn't be too hard to test out and see if it works.


If $M$ recognizes an infinite language, then $M$ has a cycle An NFA $M$ contains a cycle if there is a state $q$ and a string $x$ such that if $M$ is in state $q$ and reads string $x$, $M$ can return to state $q$. Prove:

If $M$ recognizes an infinite language, then $M$ has a cycle.

Whithout a cycle, each string can only traverse a state once. If it is at a state $q$, there exists no string $x$ that can return the machine to state $q$. So if a string can only traverse each state once, then we can bound the lenght of the string to k, the number of states. Thus you can only represent a finite number of strings if they are bounded in length ($\sum_{n=0}^{k-1} |\Sigma|^n$). Thus to recognize an infinite language, there must be a cycle.


On graph isomorphism over exponential word sizes Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes?

(Shamir's poly time Integer Factoring algorithm is over exponential word sizes).

Yes, this is known.  It has been shown that if you allow unlimited word sizes, then programs in the RAM model can compute arbitrary #PSPACE problems in polynomial time.  #PSPACE is a huge complexity class: it includes all of PSPACE and NP, and in particular, it includes graph isomorphism (and factoring).  Therefore, yes, graph isomorphism can be done in polynomial time if you allow unbounded word sizes.

This result was shown in the following research paper:

Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini.  A characterization of the class of functions computable in polynomial time on Random Access Machines.  STOC 1981.  https://dl.acm.org/citation.cfm?doid=800076.802470

The transdichotomous model was invented to eliminate this anomaly.


How to identify strongly confluent cellular automatas? Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule rule : (Bit,Bit,Bit) -> (Bit,Bit,Bit). Given any state of the system, a posterior state can be computed by taking any consecutive triple of bits (a,b,c) and replacing it by the result of rule(a,b,c).

Since rule is a map from 3 bits to 3 bits, there are (2^3) ^ (2^3) == 16777216 possible rules. Is it possible to identify if a specific rule is confluent?

Suppose we fix $n$ and want to ask about confluence of the system on $n$-bit states.  Then one approach you could try would be to use BDDs.

Build a BDD for the transition relation $\to$, where for two $n$-bit states $s,t$ we say $s \to t$ if you can get from $s$ to $t$ in a single step.  Now, build a BDD for the reflexive, transitive closure $\to^*$.  (This can be built in a fixpoint computation, by looking for the least fixpoint of the equation $\to^* = \to^* \circ \to \lor \; \text{id}$; i.e., set $R$ to be the identity relation, and then iteratively replace $R$ with $R \circ \to \lor \; \text{id}$, where the latter relation $R'$ is defined such that $sR'u$ holds iff $s=u$ or there exists $t$ such that $sRt$ and $t\to u$.  Iterate until convergence.)  If you're lucky, the BDD for $\to^*$ won't be too large.

Now, once you have a BDD for $\to^*$, you can use standard BDD operations to check directly whether the convergence criteria applies.  In other words, you check the validity of the formula

$$\forall a,b,c . (a\to^* b \land a\to^* c \implies \exists d . (b \to^* d \land c \to^* d)).$$

This only gives you the answer for fixed $n$.  If you want to know if it is confluent for all $n$, I don't know how to check that.  Also, this procedure might take exponential time in the worst case.  So, you might be able to systematically check small values of $n$, and then heuristically guess that if there is a counterexample to confluence, then hopefully it'll show up for some small $n$... but this isn't guaranteed to be sound in general.


Routing Algorithms and Hosts I'm reading a book about computer network theory, and one topic is discusses is routing algorithms.  It only mentions (probably not intentionally) how routers participate in forming the understood network topology stored in each routers memory - the routing tables.

So this brings me to my question, do Host acts like dedicated routers in this case and participate in and become part of that understood topology of the network in nearby routers?

For example, it says that routers communicate with each other to form their routing tables to find the best path. Do hosts as end user machines find themselves in this routing table (as an entry in dedicated router, routing tables) or routing topology?  Do they participate in forming it?

Likewise do Computer Hosts, have entries for nearby dedicate routers in their routing tables? I'm trying to find the relation ship between a router and a host in the this process.

The issue I'm having, is if they don't participate in this process, how do the routers not where the end user machines are in the topology?

Thanks :-)

I believe you are talking about the Internet and the IP. Here are answers of your questions:

First note the internet is a network of networks. Networks communicate with each other through routers. These big networks are like the ISP, your university or a big organization. Your computer belong to a small network in your ISP subnetwork. This small network is probably your WiFi switch and your computer.

Do hosts find themselves in the routing tables ? NO, but from the IP address of the host and its subnetwork, a router can tell whether they belong to the same subnetwork or not. If they do belong, then there is no need to route the message to another router. The message is simple sent down the subnetwork. You have to study in this case the BGP protocol and the structure of IP.
Your host got nothing to do with routing. The ISP takes care of all that. or your cellular company if you are using your mobile phone .. or etc .. It would be hugely complicated to let these terminals take care of that. Again, you must have a look on the IP structure.
If you try to send a message to X, then your router will look at X (which has an address probably similar to 122.23.12.11 or whatever !) from the upper digits, the router (which is your ISP router in this case) will know which neighbor router to send it to. In general, Internet routing is greedy. How a router selects its neighbors ? [that's another topic]

One advice: dont look to the Internet from a pure theoretical point-of-view.

I guess I answered your question ?


$f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance) Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function
$$f(x)=\left(\sqrt{x^{2}+1}-1\right)\left(\frac{\sqrt{x^{2}+1}+1}{\sqrt{x^{2}+1}+1}\right)=\frac{x^{2}}{\sqrt{x^{2}+1}+1}$$
Even though I can solve the problem, I do not know/understand why the solution has avoid the loss of significance?

Assume that due to rounding errors, when you try to calculate the square root of $x^2 + 1$ you actually get the square root plus $\epsilon$ for some small $\epsilon$. Assume that $\epsilon = 10^{-10}$ and $x = 10^{-6}$. Perform the calculations and write down the results.


Solving this recurrence: T(n) = 9 T(n/2) + n^3 lg n Would it be possible to use the master theorem to solve the following recurrence?

T(n) = 9 T(n/2) + n^3 lg n

This recurrence hasn't been mentioned before in any of the questions on StackOverflow.

Best,

You should use the Master Theorem to solve that kind of recurrence relation:

The general form of the Master Theorem is: $T(n) = a T(n/b) + O(n^d)$ or $T(n) = a T(n/b) + f(n)$, where $f(n)$ can take multiple forms (I'll let you dive into that).

That being said, let us begin solving the recurrence relation, step by step:

$$T(n) = 9 T(n/2) + n^3 \lg n$$

Step 1: Identify a, b and d. In your relation $a = 9$, $b = 2$. We need to work a little harder to find $d$, as you can see. The function $f(n)$ is of the form $n^\mathbf{d} \log^k n$. So $f(n) = O(n^3 \lg n)$, thus $\mathbf{d} = 3$.

Step 2: Analyze the a, b, d output of your recurrence relation and decide which of the following cases is valid:

I) $a = b^d$, then $T(n) = O(n^d \log^{k+1} n)$;

II) $a < b^d$, then $T(n) = O(n^d)$;

III) $a > b^d$, then $T(n) = O(n^{\log_b a})$.

In your situation, we have $9 > 2^3$, thus $T(n) = O(n^{\log_29}) = O(n^{3.17})$.

As you can see, this is a simple exercise on asymptotic notation. Next time try to give more insight on your thoughts regarding your problems, don't just post your homework blankly.


Construct binary palindrome by repeated appending and trimming I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating itself to wrap into the palindrome. The palindrome must always begin with 1 and contains maximum number of zeros.

I solved the problem using this algorithm-

I will declare a string of size n with all the entries 0.
Leftmost character has to be 1, so to be a palindrome rightmost should also be a 1 .
Now after every k-1 places starting from start, I will put a 1.
And before every k-1 places starting from end, I will put a 1.

This algorithm has O(n) runtime. Is there anything wrong with this algorithm?

In the article, They have declared an array of size n, and then laid the index of the k sized binary to hold into an array, for example if n = 7, k = 3 arr becomes [0, 1, 2, 0, 1, 2, 0]. And then connected the indices of the k sized binary which should be same by going through the property of palindrome which is kth and (n – k – 1)th variable should be same. And then they apply dfs on 0.
For more clearance, please see the article above.

We already know which nodes would be connected to index 0 (that I have done in my algorithm), then why are we connecting all the indices ?

Is there something, I am missing?

I suspect that when n is not a mutiple of k then you may not get the desired wrapping effect.

In particular, let me interpret "after every k places from the start" as "the (k+1)th position in the array" - assuming 1-based indexing. Then in the given example on that page, with k = 4 and n = 10, your algorithm produces 1 0 0 0 1 1 0 0 0 1 - which is not a 4-length binary string being repeated and wrapped off at the end (the right answer would be 1 1 0 0 1 1 0 0 1 1.

If I am off-by-one on interpreting "k places from the start" (so say you were refering to the kth position), then even with n = 5 and k = 3 we get 1 0 1 0 1, whereas the right answer would be 1 1 0 1 1.


Why is CNOT the only non-trivial reversible gate for two input bits? The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function:
$$
00 \to 00 \\ 01 \to 01 \\ 10 \to 11 \\ 11 \to 10
$$
I think I found a different non-trivial gate on two input bits:
$$
00 \to 01 \\
01 \to 00 \\
10 \to 10 \\
11 \to 11
$$
I think the matrix corresponding to this gate is
$$
\begin{bmatrix}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
\end{bmatrix}
$$
which is different from
$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
\end{bmatrix}
$$
and is also unitary.

The CNOT gate is definitely not the only non-trivial reversible gate on two input bits. For example, you could switch the order of inputs or the order of outputs. What Wikipedia means is that CNOT is the only non-trivial reversible gate up to some allowed operations, which consist of permuting the inputs and outputs, and applying reversible one-bit gates on the inputs and outputs.
If a two-input gate $G$ is reversible, then it is a permutation on $00,01,10,11$. By possibly negating the inputs (or the outputs), we can assume that $G(00) = 00$. By possibly switching the order of the inputs, we can assume that in $G(01) < G(10)$. We are left with three possibilities:
$$
00 \to 00 \quad 00 \to 00 \quad 00 \to 00 \\
01 \to 01 \quad 01 \to 01 \quad 01 \to 10 \\
10 \to 10 \quad 10 \to 11 \quad 10 \to 11 \\
11 \to 11 \quad 11 \to 10 \quad 11 \to 01
$$
The first possibility is the identity, which is trivial. The second possibility is CNOT. The third possibility is CNOT with outputs swapped.


Wiring Length Minimization My Problem is like this:

I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where wire can go.
There are some special Nodes, called splitters, from where a single wire can be splitted to  2 or more up to k. The k can be taken constant for now but it varies from node to node. Not all nodes are splitters.
There is one source of power from where a wire will emerge. It is the source. The wire has to be taken to n sinks.
An edge can take any number of wires traversing through it in either direction.
The the total wire length has to be minimized.
The nature of graph, planar or euclidean is not known.

Example: Below is a sample network. Nodes are named as numbers and edges are provided with equal weights of 1. Source is Node1 and Sinks are Node5, Node9 and Node13. In case 1 Node6 is Splitter node. In case 2 Node6 and Node4 are splitter nodes. The splitter node's k=3, i.e., it can take in one wire and split it out to 3 wires.

Case 1. Only one splitter Node. It makes sense to split at Node6.

Case 2. Two splitter Node. It makes sense to split at Node4 instead of Node6.

I am looking for different strategies to find out a generic solution for this problem. The graph presented here is of a smaller scale as compared to the problem in hand. The graph is static and can not be changed (i mean the solution should not suggest any new edge or propose new splitter location ).
Any reference to research paper published on this kind of problem is also welcomed.

Case 3. Two splitter Node. It makes sense to split at Node4 and Node14. Note that this case has edge weights changed for Edge 8-12, 6-10 and 10-11. The important thing in this case is retracing of a wire after getting splitted from Node14.

This problem is NP-hard.

Assume every vertex is a splitter that can split to any number of degrees, then your problem is precisely the Steiner tree problem on a graph, where the set of source and sink vertices are the required vertices.


Algorithm to test whether a binary tree is a search tree and count complete branches I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable. This is an assignment for my data structures class.

So far I have

void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

But I can't really figure this one out. I know that this algorithm won't solve the problem because the count will be zero if the second if statement isn't true.

Could anyone help me out on this one?

As others have already indicated in comments, you really have two unrelated functions here: testing whether the tree is a search tree, and counting the complete branches. Unless the assignment specifically calls for it, I would write two separate functions.

Let's see abount counting the complete branches first. That means counting the nodes that have both a left child and a right child. Then you need to increment the counter (count = count + 1) when both T.left and T.right are non-null (not T.left.data and T.right.data: the data doesn't matter for this task).

if (T.left and T.right) {
    count = count + 1

Furthermore, you need to explore the left subtree even if the right subtree is empty, and you need to explore the right subtree even if the left subtree is empty. So watch where you put the recursive calls.

To test whether the tree is a search tree, you need to inspect the data values. You've already got something close to the right comparison; not quite right. Write a few example trees with various shapes (not very big, 2 to 5 nodes) and run your algorithm on them to see what happens.

You still need to find some place to put the result of the validity check. Again, watch where you put the recursive calls (if you only do this part, there are several solutions, but at this stage don't worry if you only see one).

Finally, once you've managed to write both functions separately, and you've tested them on a few examples, put them together carefully (if required by the assignment).


Introduction to type theory for a beginner? I'm interested to read about type theory, but I'm quite a beginner. I know what sets are and how to work with them, but I don't have a deep understanding of set theory. I don't really understand the motivation behind type theory, other than that it was first developed to solve the problems with naive set theory.

I'm mainly interested in type theory because I heard it relates to proof theory (which I also don't understand well). I'm also not a mathematician or computer science by education.

Is there a good resource for beginners that introduces type theory, motivates it, shows how its different from set theory, why that's relevant, and shows how it can be used? I'd be satisfied if I have a thorough understanding of the general idea without understanding more advanced stuff.

Why has no one proposed Benjamin Pierce's Types and Programming Languages? That is a good introduction to type theory. Bob (Robert) Harper's Practical Foundations of Programming Languages is also a pretty good one.

Both of them introduce type theory from a computing perspective. If you like math better, try Rob Nederpelt and Herman Geuvers' Type Theory and Formal Proof: An Introduction. I have not taken a look at Basic Simple Type Theory by J. Roger Hindley yet, but I figure it should be good given the author (judging from the table of contents though, it looks hard).


Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables? This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17}^c \subseteq \text{Goto}$. This language contains exactly those $\text{Goto}$ programs in which no constant is ever above $17$ nor any variable ever above $c$.
$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:
With variables $v_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $L_i$
Haltcommand: halt
I am currently struggling with the formalization of a proof, but this is what I have come to so far, phrased very casually:
For any given program in this set we know that it is finite. A finite program contains a finite amount of variables and a finite amount of states, or lines to be in. As such, there is a finite amount of configurations in which this process can be. If we let this program run, we can keep a list of all configurations we have seen. That is, the combination of all used variable-values and the state of the program. If we let the program run, there must be one of two things that happens eventually:
The program halts. In this case, we return YES and have decided that it halts.
The program reaches a configuration that has been recorded before. As the language is deterministic, this means that we must have gone a full loop which will exactly repeat now.
No other case can exist as that would mean that we keep running forever on finite code without repeating a configuration. This means after every step, among our list of infinite steps, there is a new configuration. This would mean that there are infinite configurations, which is a contradiction.
Is this correct? Furthermore, how would a more formal proof look if it is? If not, how would a correct proof look?

There is a finite number of different states (the set of values of the variables and the program counter). Your "limited goto programs" are just a (messy) way to describe a deterministic finite automaton.
Or just reason that the program states being finite, it is certainly possible to map out all possible non-looping computations (by something like a breadth first search of the graph of states and neighbours).


Cluster Edge Deletion on 2-trees Definitions:
Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n > k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

Question:
Does exist a polynomial-time algorithm to solve Cluster Edge Deletion on 2-trees?

My idea: Let $G$ be the 2-tree.
I transform $G$ to a new graph $G'$ where, each node of $G'$ represents a $K_3$ in $G$. And two nodes of $G'$ are adjacent if and only if their corresponding $K_3$ share a common vertex in $G$.

Let $M$ be the resulting graph after removing the minimum edges from $G$.
I think that if always exist some graph $M$ contains a 3-clique $H$ which has a node with minimum degree in $G'$, then I can solve this problem on $G \backslash H$.

For example as below figure, I choose node $x$ with minimum degree 3 in $G'$, and after remove all vertices of clique $\{f,g,e\}$ in $G$, I got an union disjoint of two clique $\{f,g,e\}$ and $\{b,c,d\}$ in $G$.

Let me first formalize the problem:

Cluster edition
Instance: A graph $G$ and an integer $k$.
Question: Can $G$ be transformed into a cluster graph by deleting at most $k$ edges?

It is not difficult to see that the problem is, already for general graphs, fixed-parameter tractable (FPT) parameterized by the number of edge deletions $k$. Being FPT means the problem is solvable in time $f(k) n^{O(1)}$, where $f$ is a computable function depending solely on $k$.
The observation is the following: cluster graphs are precisely the $P_3$-free graphs, i.e., the graphs that don't contain the path on 3 vertices as an induced subgraph. So, in order to produce a cluster from $G$, the $k$ edge deletions must "hit" each $P_3$. Clearly, there are two ways to destroy a $P_3$: either we remove edge $a$ or edge $b$. The algorithm is as follows: as long as there is a $P_3$, branch by choosing either one of its edges to delete. This will give you a straightforward $2^k n^{O(1)}$-time algorithm, that will be quite practical if $k$ is not too large.
Looking up the literature, the problem can be solved in $O^*(1.77^k)$ time by a more clever yet simple branching algorithm (see Gramm et al. [1]). Here the $O^*$ notation hides polynomially bounded factors.
It is interesting to ask whether you can do better for chordal graphs, or indeed $q$-trees (I'm using $q$ here to make a distinction between $k$). The problem is solvable in polynomial-time for cographs [2], but NP-complete for chordal graphs [3]. I don't know if the complexity for $q$-trees is known, and I also didn't think hard about it but merely glanced the literature.

[1] Gramm, Jens, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. "Graph-modeled data clustering: Fixed-parameter algorithms for clique generation." In Italian Conference on Algorithms and Complexity, pp. 108-119. Springer Berlin Heidelberg, 2003.
[2] Gao, Yong, Donovan R. Hare, and James Nastos. "The cluster deletion problem for cographs." Discrete Mathematics 313, no. 23 (2013): 2763-2771.
[3] Bonomo, Flavia, Guillermo Duran, and Mario Valencia-Pabon. "Complexity of the cluster deletion problem on subclasses of chordal graphs." Theoretical Computer Science 600 (2015): 59-69.


Struggling with NP-Complete Problem I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows:

The Set Cover problem is the following:

Instance: A set $U = \{1,2,...,n\}$ of $n$ elements, a collection of subsets $S_1,S_2,...,S_m$ of U, and an integer $K$.

Question: Are there $K$ sets among the $S_i$’s whose union is equal to $U$?  In other words, are there $K$ sets which together cover all the elements of $U$?

Prove that Set Cover is NP-complete

Any guidance here would be greatly appreciated. My thought is that I should try reducing from the Vertex Cover problem, but I am not entirely sure how to reduce from there.

An instance of (the decision version of) vertex cover is a pair $\langle G, k \rangle$ where $G = (V,E)$ is a graph and $k$ is an integer. The problem is that of deciding whether $\exists S \subseteq V$ such that $|S| \le k$ and $\forall (u,v) \in E, \; \{u,v\} \cap S \neq \emptyset$.

Let $v_1, \dots, v_n$, be the vertices of $V$, in an arbitrary order.

You can see that vertex cover is a special case of set-cover. Indeed, it suffices to define $U=E$, $S_i = \{u \in V  : (v_i, u) \in E \}$ for $i=1,\dots,n$, and $K = k$.

If there is a set-cover $C$ of size at most $K$, then for each element $e = (v_i, v_j) \in U = E$ at least one of $V_i$ and $V_j$ is in $C$ (since these are the only two sets that contain $e$). This means that $S = \{v_h : V_h \in C \}$ is a vertex-cover for $G$ of size $|S| = |C| \le K = k$.

If there is a vertex cover $S$ of size at most $k$ for $G$, then for each edge $e = (v_i, v_j) \in E = U$,  $\exists v_k \in \{v_i, v_j\} \cap S$. This means that $V_k \ni e$ is in the set $C = \{ V_h : v_h \in S \}$ and hence $C$ is a set-cover of size $|C|=|S| \le k=K$.


Suggestions on Point Cloud fusion I am trying to fuse point clouds into one. These Point clouds are acquired from multiple cameras. Below is the detailed information about setup-

Three Kinect v2 sensors are mounted on tripods in such a way that they are making 120 degree angle from each other in a horizontal plane. Hence one can assume that these Kinect sensors are kept in the circumference of a sphere and pointing towards the center of the sphere. All three Kinect sensors are tilted vertically downwards approximately 30 degrees. The object which is being scanned is kept inside the sphere and visible from all Kinect sensors.

I am able to acquire three point clouds simultaneously from these sensors. Now I want to fuse three clouds to make 1 compete cloud.

What algorithm would I use for this?

You'll probably want to use a method for point cloud registration, also known as point set registration or point cloud alignment.  See, e.g., https://en.wikipedia.org/wiki/Point_set_registration.  RANSAC-like methods may also be useful.


Strongly connected components on a DAG What is supposed to be the right result of an SCC algorithm running on a DAG.
should it return "no components" or "there are V components of size 1"?

I suspect it will return the latter (since it will start with the last sink, and then go back and mark each single sized vertex as a component, since each DFS will be of a single node before it can continue)

But is this a convention? E.g. if a treat SCC as a "great way to find if a graph has cycles" then I would expect it to return an empty result if there are none. e.g. components of size 1, who don't have a self-loop, don't really "go from A to A". is there a SCC variant that is more explicitly "find all groups that has cycles in them"? (e.g. is there a named variation)

Or what I'm looking for is basically "run SCC, then remove all components of size 1, and you got yourself a cycle detector, e.g. if after you do that you end up with no components, then your graph is a DAG"

Is there a name for that special SCC case? (assuming my understanding in the beginning of the question is correct)

I know of no convention; the right result depends entirely on what you want to do with the result.  As an example, if you're trying to use strongly connected components to find satisfying assignments for 2SAT instances, then you likely want all the singleton cycles returned along with the larger components.  But if you're just trying to find out if a graph contains a cycle, then the singletons won't be of interest to the caller so the SCC function could usefully omit returning them.


Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$ I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:

Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the form $(L, R, i)$ $(L\leq i\leq R)$. For each query, you have to print the number of $j$ such that $L\leq j\leq R$ and $a[j] \leq a[i]$.

I tried coordinate compression and then sorting the queries by increasing order of $i$ (answering the queries offline), but the L, R part make things hard. I think we can convert the query $(L, R, i)$ into two parts $(1, R, i)$ and $(1, L-1, i)$ (and subtract them), but how to find the answer for that either?

Also note that this problem can be solved by Mo's algorithm, but I am looking for something like $O(q \log n)$ or $O (q \log^2 n)$ (maybe binary search on the answer and do some magic with bits?).

Thanks :)

Here is a solution in time $O((Q+n)\log^2 n)$ and space $O(n\log n)$. For simplicity, assume that $n$ is a power of $2$, and that the array is zero-based.

A dyadic interval is an interval of the form $[c \cdot 2^k,(c+1) \cdot 2^k)$ (that is, $c\cdot 2^k,\ldots,(c+1)\cdot 2^k-1$). For example, when $n = 8$ we have the following dyadic intervals:
$$
[0,8),[0,4),[4,8),[0,2),[2,4),[4,6),[6,8), \\
[0,1),[1,2),[2,3),[3,4),[4,5),[5,6),[6,7),[7,8).
$$
Each interval of the form $[0,x)$ is the disjoint union of at most $\log_2 n$ slices. For example, for $n = 8$ we have (for $x \neq 1,2,4,8$):
$$
[0,3) = [0,2) \cup [2,3),  \\
[0,5) = [0,4) \cup [4,5), \\
[0,6) = [0,4) \cup [4,6), \\
[0,7) = [0,4) \cup [4,6) \cup [6,7).
$$

A dyadic slice of the array $a$ consists of the elements $a[s],\ldots,a[t]$ for some dyadic interval $s,\ldots,t$.

As preprocessing, we sort (separately) each dyadic slice of $a$. This takes time $O(n\log^2 n)$ and consumes space $O(n\log n)$ (since each index participates in $\log_2 n$ slices).

As mentioned in the question, it is enough to handle the following type of query:

  Given $i,R$, count the number of indices $j <R$ such that $a[j] \leq a[i]$.

Given $i,R$, we retrieve $a[i]$, and present $[0,R)$ as a union of $O(\log n)$ dyadic intervals $I_1,\ldots,I_m$. Using binary search, for each $k$ we determine the number of indices $j \in I_k$ such that $a[j] \leq a[i]$. This takes time $O(\log^2 n)$ (altogether). Summing these numbers, we arrive at the answer to the query.


Why can't we just use preorder traversal to check if a tree is subtree of binary tree? Is preorder traversal enough to check if a tree is subtree of a binary tree?

Are there any scenarios which I can miss if I use just the preorder traversal?

What other methods can be used to check if a tree is subtree?

Also, what happens if my binary tree contains non-unique values at nodes?

Because different trees can have the same pre-order label sequence (easy exercise).

To check equality, recurse on both trees at the same time. That gives you a simple (if not terribly efficient) algorithm for checking whether a tree is a subtree of another one.


Chernoff bound when we only have upper bound of expectation If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$

for all $0<\delta<1$.

If $E[X]\leq\mu$ instead, does there exist a constant $c$ such that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-c\delta^2\mu}$$

for all $0<\delta<1$?

(This question is related, but the answer there doesn't help.)

Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved.  A relatively standard form of this kind of tail bound would assume that
$$
  X = X_1 + \cdots + X_n
$$
with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\sigma_i^2$.
The resulting tail bound ends up being that:
$$\operatorname{Pr}[X > \lambda\sigma]\le e^{-\lambda^2/4}$$
where $\sigma^2 = \sum_{i\in [n]} \sigma^2_i$ is the variance of $X$ and $\lambda\in[0,2\sigma]$.  (Here is a proof by Van Vu.)

I'm more or less going to first reproduce the proof, so you can get an idea of why decreasing the expectation turns out to be ok.

All Chernoff bounds are based on applying Markov's inequality to $e^{tX}$ to get that $\operatorname{Pr}[X > \lambda\sigma]\le \mathbb{E}[e^{tX}]e^{-t\lambda\sigma}$.  So the general method is to work out $\mathbb{E}[e^{tX}]$ and then optimize $t$.  We can do the MGF computation a little differently from the link, namely as
$$\mathbb{E}[e^{tX}] = \prod_{i\in [n]}\mathbb{E}[e^{tX_i}] \le
\prod_{i\in [n]}\mathbb{E}[(1 + tX_i + t^2X_i^2)]$$
where we first used independence of the $X_i$ and then $e^x\le 1 + x + x^2$ for $x\in [0,1]$.  Under the hypotheses we started with and linearity of expectation,
$$\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t^2\sigma_i^2\le e^{t^2\sigma_i^2}$$
so we get that
$$ \operatorname{Pr}[X > \lambda\sigma] \le e^{t^2\sigma^2 - t\lambda\sigma}$$
With $t = \lambda/2\sigma$ this is what we wanted (and since $t\in[0,1]$, all
the inequalities we used are valid).

Now let's assume that $\mu_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses.  Returning to the MGF computation, we get
$$
\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t\mu_i + t^2\mathbb{E}[X_i^2] = 1 + t\mu_i + t^2\sigma_i^2 + t^2\mu_i^2
$$
Using that $x^2 + x < 0$ for $x\in (-1,0)$, this implies that
$$
\mathbb{E}[(1 + tX_i + t^2X_i^2)] \le 1 + t^2\sigma_i^2
$$
and so we get the same tail bound as before.

Finally, note you always have $\sigma^2_i\le 4$, so $\sigma^2\le 4n$.


Encoding the sequence 0110 and determining parity, data bit and value I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense.
eg.1

eg.2

I don't really understand the above two examples and the calculations taking place.
How were the conclusions reached concerning the categories of bin position (dec/bin), parity/data bit and value in e.g 1?
Secondly I don't understand the process taking place in e.g. 2 at all. Does it follow that:

General rule: For any code C,

errors of less than $d(C)$ bits can be detected,
errors of less than $d(C)/2$ bits can be corrected.

Definition: A code C with $d(C) \geq 3$ is called error-correcting.

If this is correct then how would I put it into practice. Would really appreciate some assistance!

Well, these examples are not easy to read, by they are indeed correct.

e.g.1:

The word to code has 4 bits, and lets call them $b_1 b_2 b_3 b_4$.
To this "data" word add 3 parity bits
(adding is over $GF(2)$):

$p_1 = b_1 \oplus b_2  \oplus b_3$,
$p_2 = b_1 \oplus b_2 \oplus b_4$, and
$p_3 = b_1 \oplus b_3 \oplus b_4$.

[remark: for odd parity, add "1" to each equation, e.g., $p_1 = b_1 \oplus b_2  \oplus b_3 \oplus 1$]

Then we transmit the code word

$$C= b_1 b_2 b_3 p_1 b_4 p_2 p_3$$

Why this particular order? They want  the "position" of the parity bits to be "1" "2" and "4" (starting to count from the right side) which corresponds to bit positions "001" "010" and "100". This is meaningful in order for the decoding to work as they demonstrate.

You can see by the colors which parity bit belongs to which data-bits.

(Awful explanation in my eye, but, oh well.)

as for the decoding: e.g. 2

the procedure to decode is the following:

recompute $p_1, p_2, p_3$ from the received $b_1b_2b_3b_4$
if you got the same values as the received codeword (the $p_1,..$ you received) - then everything is fine
Otherwise - the error is located in position $x$ where $x$ is the sum of locations of the parity bits $\{1,2,4\}$. For instance, if only $p_3$ is incorrect, than the error is in bit no "1" - $p_1$ itself is the only one got flipped. If $p_3$ and $p_1$ mismatch, than you need to flip the bit in location $1+4=5$, that is, $b_3$.

Note that this code fixes only a single error.


Algorithm to find the minimum (additional) popular votes to win the electoral college So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election.
Assuming we are considering n states each with some different electoral votes. The candidate who has a majority receive all these votes from that state; and the one with the majority of electoral votes win the presidency. The number of electoral votes of a state is not necessarily proportional to its size of voters.
At a certain instance of vote counting, each candidate receives certain amounts of votes and there are still some uncounted in every states. I want to keep track of the minimum number of the remaining votes (regardless which state they are from) from these candidates to win the election until its secured.

So far the only algorithm in my head is to compute all the combinations of states to win the majority electoral votes, then weed out those which are not possible (the candidate won't win even he/she gains all the remaining votes). Compute the additional popular votes needed (win each of these states by exactly 1 vote) and then find_min among them.  But this would rather have redundant time complexity as it would take the same amount of time to compute no matter how many votes left...

Here's a hint (and a sketch).
I believe the problem is NP-hard and that it is equivalent to Subset Sum.
Reducing from Subset Sum:  Suppose your instance has sum $S$ and values $v_1, v_2, \dots, v_n$.
Create $n+1$ states, one with $S$ electorals that Party $A$ is guaranteed to win.  The remaining $n$ states is such that $i$ has $v_i$ electorals.  These cost Party $B$ $v_i$ to win.
Now, the optimum solution is $S$ which exists if and only if you have a yes instance for Subset Sum.


Proving the undecidability of a language knowing the language of polynomials evaluating to 0 is undecidable Knowing
D={p|p is a  polynomial evaluating to 0 for some assignment of integers to its variables} is not decidable, how can I prove that E={p|p is a  polynomial evaluating to a prime for some assignment of integers to its variables} is not decidable?

Proving that D is mapping reducible or Turing reducible to E would be enough, since if D < E ( where < means mapping reducible), then E decidable => D decidable, and using the contrapositive we get D not decidable => E not decidable.

Is showing that D is mapping or Turing reducible to E the right approach? I don't see how it can be proved. Thanks!

Yes like you say, you have to show that an algorithm that solves $E$ can be used to solve $D$.

A practical approach is to give a polynomial $p_E$ for every polynomial $p$ such that $p$ evaluates to $0$ iff $p_E$ evaluates to a prime number.


What is happening during "table walk"? I am trying to understand what is a table walk. I have found when it occurs -
whenever there is a TLB miss. If no descriptor is found – TLB miss occurs and further behavior depends on the implementation of a paging unit. (TLB - Translation look aside buffer)

But i still do not understand what exactly happens during table walk.

In present computers, the processor manipulates virtual addresses that are generated by the compiler, but the real physical address is determined at run time by the OS.

To do that, memory is organized in pages. Typical page size is 4kB (2^12bytes). To translate from virtual addresses to physical addresses, an address is considered as having two fields: address of a byte within a page (12 bits displacement) and page address (the remaining high order bits). Translation consists to replace virtual page address in he processor by physical address, with respect to a table generated at process creation by the OS (page table).

The problem is that these table can be HUGE. With 64bits virtual addresses (as in present processors), this page address have (64-12)bits (for 4kB pages) and a page table will hold 2^52 page addresses. This is an insane size (~10^18B) largely above most computer physical memory size. Fortunately, these tables are mostly empty and only a small part of potential virtual addresses have a physical translation.

To cope with that, page tables are multi level. Virtual addresses are split in fields addressing the successive table levels. For instance, with a 4kB page, and 64bits (8B) addresses, it is possible to store 512(2^9) addresses per page. The first 9 high order bits select an address within a page, that will give the address of a new page holding 512 page address. The next 9 high order bits select a new page, and so on.

If a page address is 52 bits in at most 6 steps, we can get the final physical page address corresponding  to a logical page address.

This "page walk" or "table walk" is a complex process that requires several memory accesses and that must be done for every memory access.

To reduce the translation time, the TLB memorize recent correspondences between virtual and phys page addresses. If the physical translation of a virtual address is in the TLB, it is immediately available.

And if translation is not in the TLB, it is recreated by table walk.
TLB misses (and table walk) are very expensive. If all the page tables are already copied to cache memory, it will require some tens of cycles. But if the TLB miss also implies cache misses, the time will be measured by hundreds of cycles.

There are several good tutorials on these problems. Look for instance at the wikepedia page that give good graphical illustrations of table walk.
https://en.wikipedia.org/wiki/Page_table


Can we reduce an NP complete item to an NP item which is $\bf{non}$ P? I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a single $NP$-complete problem?

If we could do this would it mean that the single $NP$ problem which is non $P$ is considered to be a part of the $NP$-complete problem set?

Is there a way to prove that all $NP$ problems which are non $P$ are considered to be a part of the $NP$-complete problem set?

No, it is not possible to prove that all $NP$ problems which are not $P$ are $NP$-complete. In fact, the opposite has been shown: unless $P=NP$, there are $NP$ intermediate problems, neither in $P$, nor $NP$-complete. See https://en.wikipedia.org/wiki/NP-intermediate

So if you reduce an $NP$-complete problem to another $NP$ problem, all you've done is proved that that problem is also $NP$-complete.


Number of pairs of indexes of two arrays such that one element is greater than the other Let $A$ and $B$ be two arrays of size $n$. How many pairs of indices $i, j$ satisfy $1 \le i < j \le n$ and $A[i] > B[j]$?

After quite a bit of thinking the best i had gotten to was make a for loop inside of another, which i don´t think it´s a good solution. So i´d like to know some ideas on how to implement this algorithm more efficiently (possibly $O(n)$, if it´s possible).

Thanks ahead.

When $A = B$, this is the same as counting the number of inversions, which can be accomplished in $O(n\log n)$ time using a divide-and-conquer algorithm, and in $O(n\sqrt{\log n})$ time using more sophisticated techniques (see Counting Inversions, Offline Orthogonal Range Counting, and Related Problems by Chan and Pătraşcu).

In the other direction, here is how to solve a similar but not identical problem.

Given $A,B$, let us construct the following array:
$$
C := A[1],B[1],A[2],B[2],\ldots,A[n],B[n].
$$
An inversion in this array is one of the follows:

A pair $A[i] > A[j]$ for $i < j$.
A pair $B[i] > B[j]$ for $i < j$.
A pair $A[i] > B[j]$ for $i < j$.
A pair $B[i] > A[j]$ for $i < j$.
A pair $A[i] > B[i]$.

Therefore you can deduce the number of $i < j$ such that either $A[i] > B[j]$ or $B[i] > A[j]$ given the number of inversions in each of $A,B,C$, augmented by the number of indices $i$ such that $A[i] > B[i]$. This yields a simple $O(n\log n)$ algorithm and a more complicated $O(n\sqrt{\log n})$ algorithm, as described above.


Is this algorithm of constant time? I have the following code in Python:

def is_unique(string):
    if len(string) <= 1:
        return True

    if len(string) > 128:
        return False

    char_set = defaultdict(lambda: False)

    for char in string:
        if not char_set[char]:
            char_set[char] = True
        else:
            return False

    return True

It's basically checking if a string is unique or not. I think that my algorithm is O(1):

No matter what it's the length of the string, I will only iterate over at most 128 times in the worst case. All the operations (len, dict lookup etc) are of constant time as well.

I guess my generic question here is if you can proof that your algorithm will always iterate for a constant number of times, can you claim that this is O(1)?

Under the assumptions you've stated, yes, the code runs in constant time.  The running time for any string can't be longer than the running time for a 128-character string, which is some constant number of steps.


programs compatible with different processors Ok, I've been told for years that during the old days, a program written on a certain machine would run only on that machine but now, programs run on multiple types of computers.

What does this really mean? I mean, does it mean that programs were written for certain instruction sets of the processor and would not run in different instruction sets? If so how did they overcome this problem?

Is it due to the standard x86, AMD64 or ARM architectures that most programs are written for these types of processors and they are abundant in the world?

Please enlighten this lost kid.

The intel line of processors (8086, x86) have backwards compatible instruction sets (i.e., unless you tell an x86 otherwise, it will behave like a 8086, and the 8086 instructions (and registers, etc) are just a subset of the x86 ones. Ditto for AMD64 (i.e., x86_64), they are able to run x86 software as is. This for pragmatic compatibility reasons: buying the shiny, new machine with the latest processor, and having it run your extant software in a slow emulator is not a way to make new buyers. So the 80286 could run 8086 software (operating system and all), and so on up. You can install an 32 bit (x86) operating system on x86_64 (64 bits) too.

ARM is a completely different kettle of fish, but also compatible (to an extent) along the line.

Besides, running software on some sort of virtual machine (Java Virtual Machine, .NET, ...) has advantages as the same "binary" runs on more platforms (simplifying the logistics of getting "the right version" to the user), today's processors are so ridiculously overpowered it doesn't make much of a difference for interactive applications. Besides, the Just In Time compilation technology has become the tool of choice, even rivaling native compiled binaries for some uses.


Is halting problem computable for particular inputs/assumptions From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a paradox when giving P as an input to the same P, having: P(P), trying to decide if P halts or not using P itself.

So my question is: is halting problem computable by program P for all other programs used as input but P itself? In other words: is halting problem not computable only in this special case or the proof is more general and I'm missing something?

is halting problem computable by program P for all other programs used as input but P itself?

No. Consider the infinite sequence of programs $P_1, P_2, \dots$, where $P_i$ is "Move the head $i$ squares to the right, then $i$ squares to the left, then do exactly what $P$ would do." Every one of these programs produces exactly the same output as $P$ for every input (including looping forever if $P$ loops forever), but they're all different programs.

And you can't get around this by only requiring $P$ to work on programs that aren't functionally equivalent to itself, since that property is also undecidable. Perhaps the problem would be decidable when restricted to those instances (though I suspect it wouldn't) but the set of instances is undecidable, so you couldn't actually perform the restriction.


What are all the decidable languages that can be constructed using a turing machine with only the Reject and Accept states? What languages can be decided by a two-state TM that has two states: one accepting and one rejecting?

As a newbie in TMs, there are some definitions I am not familiar with, of which the answer is obviously dependent,  like:

Can we draw an outgoing arrow from the Accept or Reject states?
Can either of these two states be the starting state?

If there are only two states, the rejecting state and the accepting state, then the machine must start in one of those states. That means it must immediately halt, which should tell you what language it can accept.